526互联

On Manipulating Signals of User-Item Graph A Jacobi Polynomial-based Graph Collaborative Filtering

发布时间 2023-11-22 10:49:06作者: 馒头and花卷

目录

Guo J., Du L, Chen X., Ma X., Fu Q., Han S., Zhang D. and Zhang Y. On manipulating signals of user-item graph: A jacobi polynomial-based graph collaborative filtering. KDD, 2023.

概

利用 Jacobi Convolution 来区分高中低频信号.

符号说明

  • \(\mathcal{U}\), user set;

  • \(\mathcal{I}\), item set;

  • \(N = |\mathcal{U}| + |\mathcal{I}|\);

  • \(\mathbf{R} \in \mathbb{R}^{|\mathcal{U}| \times |\mathcal{I}|}\), rating matrix;

  • 邻接矩阵:

    \[\mathbf{A}= \left[ \begin{array}{ll} \mathbf{0} & \mathbf{R} \\ \mathbf{R}^T & \mathbf{0} \end{array} \right] \in \mathbb{R}^{N \times N}. \]

  • \(\mathbf{\hat{A}} = \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}\), normalized adjacency matrix, \(\mathbf{D}_{ii} = \sum_j \mathbf{A}_{ij}\).

  • \(\mathbf{L} = \mathbf{D - A}\), graph Laplacian matrix, 并假设它的矩阵分解为:

    \[\mathbf{L} = \mathbf{\tilde{U}\tilde{\Lambda} \tilde{U}}^T. \]

  • \(\mathbf{\hat{L}} = \mathbf{I} - \mathbf{\hat{A}}\),

Motivation

  • 一般的谱图网络可以理解为:

    \[\bm{y} = g_{\theta}(\mathbf{L}) \bm{x} = \mathbf{\tilde{U}} g_{\theta}(\mathbf{\tilde{\Lambda}}) \mathbf{\tilde{U}}^T x, \]

    其中

    \[g_{\theta}(\mathbf{\tilde{\Lambda}}) = \sum_{k=0}^K \theta_k \mathbf{P}_k(\mathbf{\tilde{\Lambda}}), \]

    \(\mathbf{P}_k\) 为多项式基.

  • 我们知道 \(\mathbf{R}_{ij} = 0\) 的位置有三种可能:

    1. user \(u_i\) 见过但不喜欢 item \(v_j\);
    2. user \(u_i\) 没见过但喜欢 item \(v_j\).
    3. user \(u_i\) 没见过也不喜欢 item \(v_j\).

  • 假设, 我们知道真正的 \(\mathbf{R}^*\), 其中为 \(0\) 的元素就表示不喜欢的情况, 并令其得到的邻接矩阵为 \(\mathbf{B}\). 则推荐需要做的就是找到一个映射 \(f(\cdot)\) 使得:

    \[\min_{f} \quad \|f(\mathbf{A}) - \mathbf{B}\|_F, \]

    倘若 \(f\) 是多项式类的, 则有

    \[\|f(\mathbf{A}) - \mathbf{B}\|_F = \|f(\mathbf{\Lambda}) - \mathbf{U}^T \mathbf{B} \mathbf{U} \|_F. \]

  • u哦这比较了 \(\Lambda\) 和 \(\mathbf{U}^T \mathbf{B} \mathbf{U}\) 对角线元素的一个相关性质 (我不理解是怎么计算这个相关性的):

  • 得出的结果是, 往往低频和高频信息有比较简单的线性相关性质, 而中间的则不然, 所以作者的建议是分别处理这两部分.

JGCF

  • 作者希望用 Jacobi Polynomial Bases 来拟合, 注意到 (下图的值是 normalized 的):

  • 很明显, 传统的 LightGCN 所采用的 Monomial Bases 重视低频信息, 而压制中高频, \(P_k^{1, 1}\) 则是偏中高频, \(1 - P_k^{1, 1}\) 则是偏中高频.

  • 按照, 上一节的启发, 作者希望通过 \(P_k^{a,b}\) 去提取中高频特征, \(1 - P_k^{a, b}\) 去提取中频特征.

  • 高低频:

    \[\mathbf{E}_{band-stop}^{(K)} = \frac{1}{K+1} \sum_{k=0}^K \mathbf{P}_k^{a, b} (\mathbf{\hat{A}}) \mathbf{E}^{(0)}, \\ \]

  • 中频:

    \[\mathbf{E}_{band-pass}^{(K)} = \text{tanh}\bigg( \big( \alpha \mathbf{I} - \frac{1}{K+1} \sum_{k=0}^K \mathbf{P}_k^{(a, b)}(\mathbf{\hat{A}}) \big) \mathbf{E}^{(0)} \bigg). \]

  • 最后的表示为:

    \[\mathbf{E} = [\mathbf{E}_{band-stop}^{(K)}; \mathbf{E}_{band-pass}^{(K)}]. \]

代码

[official]