摘要

本文发表在ICLR 2019上面，作者来自于德国慕尼黑工业大学。作者首先分析了基于消息传递框架的图卷积神经网络存在的问题及局限性，进一步地提出利用Personalized PageRank来增强流行的图神经网络的Propagation过程。

Graph Convolutional存在的问题

Graph Convolutional Networks

对于图 $G = (V, E)$, 有 $ \tilde{A} = A + I_n$。一般而言，GCN通常采用两层的结构，即：

$Z_{GCN} = softmax( \hat{\tilde{A}} ReLu(\hat{\tilde{A}}X W_0)W_1)$

其中 $ \hat{\tilde{A}} = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} $。对于图神经网络，首先，平均聚合的方式会带来过平滑问题，因此常用的图神经网络只关注局部的邻域。其次，网络越深能够带来能好的拟合效果和更加全局的特征对于某些节点。可以看到，参与计算的邻域数量与网络的深度是正交的。

从Random Walk出发探索GNN局限性

从Jumping Knowledge Networks已知，K层的GCN相当于从源节点x出发到y的一个K步的Random Walk，取$k\to\infty$, 节点的极限分布与初始的节点表示无关，只与图拓扑相关（类似于马尔可夫模型，极限状态与初始分布无关)。显然，当前的GNN模式并不适合描述节点的表示。

Personalized Propagation

PPNP算法

为了使节点的极限分布与初始节点有关，考虑采用Personalized PageRank传播模式。对于图G，有初始的节点表示$i_x$, 则有

$PPR(i_x) = (1-\alpha)\hat{\tilde{A}} + \alpha i_x$

其中$\alpha \in (0, 1]$是超参数。进一步地推导可得

$PPR(i_x) = \alpha (I_n - (1 - \alpha)\hat{\tilde{A}})^{-1} i_x$

由此可得

$Z_{PPNP} = softmax(\alpha (I_n - (1 - \alpha)\hat{\tilde{A}})^{-1} H)$ $H = f(X_i)$

上式中$ f(\dot)$表示全连接神经网络。上述算法的复杂度为$O(n^2)$。

近似PPNP算法

PPNP算法中存在矩阵求逆的计算，算法复杂度较高，为了计算更加有效，考虑利用Topic-sensitive PageRank来迭代地近似PPNP算法。可得近似PPNP算法如下所示

$Z^{(0)} = H = f_{\theta}(X)$ $Z^{(k + 1)} = (1 - \alpha)\hat{\tilde{A}}Z^{(k)} + \alpha H$ $Z^{K} = softmax((1 - \alpha)\hat{\tilde{A}}Z^{(K - 1)} + \alpha H)$

其中$k$表示迭代次数。证明可得，当$k \to \infty$时，近似PPNP与PPNP算法相同。

总结

作者通过分析流行的GCN模型，给出了GCN的局限性，并通过引入个性化PageRank来克服局限性。算法模型简单，实验清晰。

Graph Neural Networks Meet Personalized PageRank解读与思考

摘要