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

概
符号说明
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)}. \]