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

• 概
• 符号说明
• Motivation
• JGCF
• 代码

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]