Predict then Propagate: Graph Neural Networks meet Personalized PageRank

• 概
• 符号说明
• 本文思路
• 代码

Gasteiger J., Bojchevski A. and G\ddot{u}nnemann S. Predict then propagate: graph neural networks meet personalized pagerank. In International Conference on Learning Representations (ICLR), 2019.

概

一种结合 PageRank 的 propagation 方式.

符号说明

• \(G = (V, E)\);
• \(A\), 邻接矩阵;
• \(X\), 结点特征;
• \(\tilde{A} = A + I\);
• \(\hat{\tilde{A}} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}\);

本文思路

• 传统的 GCN:

  \[Z_{GCN} = \text{softmax}(\hat{\tilde{A}}\text{ ReLU}(\hat{\tilde{A}}(XW_0))W_1), \]

  由于 over-smoothing 现象的存在, 很难利用到 high-order 的一个信息;

• 而另一方面, PageRank with restarts 采用如下的一种更新方式:

  \[\pi_{ppr}(i_x) \leftarrow (1 - \alpha)\hat{\tilde{A}} \pi_{ppr}(i_x) + \alpha i_x, \: \alpha \in (0, 1]. \]

  使得每一次迭代都会保留一定的初始状态的信息, 这就避免了 over-smoothing 现象的发生, 从而能够用到更高阶的信息.

• 上述过程, 可以有一个显式解

  \[\pi_{ppr}(i_x) = \alpha (I_n - (1 - \alpha)\hat{\tilde{A}})^{-1} i_x. \]

  于是本文的 PPNP 实际上就是

  \[Z_{PPNP} = \text{softmax}(\alpha(I_n - (1 - \alpha)\hat{\tilde{A}})^{-1}H), \: H_{i,:} = f_{\theta}(X_{i,:}); \]

• 为了避免求逆的运算, 我们可以用下式进行替代:

  \[Z^{(0)} = H = f_{\theta}(X), \\ Z^{(k+1)} = (1 - \alpha)\hat{\tilde{A}} Z^{(k)} + \alpha H, Z^{(K)} = \text{softmax}((1 - \alpha) \hat{\tilde{A}}Z^{(K-1)} + \alpha H). \]

代码

[[official]]