Combining Label Propagation and Simple Models Out-performs Graph Neural Networks

• 概
• 符号说明
• C&S
• 代码

Huang Q., He H., Singh A., Lim S. and Benson A. R. Combining label propagation and simple models out-performs graph neural networks. ICLR, 2021.

概

将预测概率作为信号进行传播.

符号说明

• \(G = (V, E)\), 图;
• \(|V|=n\);
• \(X \in \mathbb{R}^{n \times p}\);
• \(A \in \mathbb{R}^{n \times n}\), 邻接矩阵;
• \(S := D^{-1/2} A D^{-1/2}\), normalized 邻接矩阵;
• \(Y \in \mathbb{R}^{n \times c}\), ont-hot-encoding matrix;
• \(L\), labled nodes;
• \(L_t\), training set;
• \(L_v\), validation set.

C&S

• 假设我们有一个基本的 predictor, 它返回的是结点的标签的预测概率 \(Z \in \mathbb{R}^{n \times c}\).

• 现在我们有训练集合上的真实标签 \(Y_{L_t}\), 则我们有误差:

  \[E = E^{(0)} = E_{L_t} = Z_{L_t} - Y_t. \]

• 但是, 我们不清楚其它的非训练中的结点的误差, 但是我们可以通过图来传播这些误差, 这么做的目的是为了误差更加平滑 (或许能够起到去除噪声的作用):

  \[\hat{E} = \text{argmin}_{W} \: \text{trace}(W^T (I - S) W) + \mu \|W - E\|_F^2, \]

  它的最优解可以通过不停地迭代下式而收敛:

  \[E^{(t+1)} = (1 - \alpha) E + \alpha S E^{(t)}, \]

  其中 \(\alpha = 1 / (1 + \mu)\).

• 但是, 作者发现这种方式, 由于:

  \[\|E^{(t+1)}\|_2 \le (1 - \alpha) E + \alpha \|S\|_2 \|E^{(t)}\|_2 \le \|E\|_2, \]

  故很难保证最终的 scale 是正确的.

• 故作者提出了两种 scale 的方式:

  1. AutoScale: 定义 \(\sigma = \frac{1}{|L_t|} \|E^{(0)}\|_1\), 则 unlabeled node \(i\) 上的误差为:

     \[Z_{i, :}^{(r)} = Z_{i,:} + \sigma \hat{E}_{:, i} / \|\hat{E}_{:,i}^T\|_1. \]

  2. Scaled Fixed Diffusion: 每次迭代, 保持 \(E_L^{(t)} = E_L\) 然后传播:

     \[E_{U}^{(t+1)} = [D^{-1}A E^{(t)}]_U. \]

     最后, 作者发现加一个超参数 \(s\) 用于调节

     \[Z^{(r)} = Z + s \hat{E} \]

     会有比较好的效果.

• 如此, 我们得到了修正后的预测: \(Z^{(r)}\). 作者接着令:

  \[G_{L_t} = Y_{L_t}, G_{L_v, U} = Z_{L_v, U}^{(r)}, \]

  并通过如下公式迭代:

  \[G^{(t+1)} = (1 - \alpha) G + \alpha SG^{(t)}. \]

代码

official