一、PPNP [2018]

《 Predict then propagate: Graph neural networks meet personalized pagerank》

1. 目前有很多流行的图神经网络算法。

   • graph embedding 算法使用随机游走或矩阵分解来直接训练每个节点的 embedding，这类算法通常以无监督的方式学习并且不需要节点的特征信息。

   • 另外一些方法以有监督方式学习，并且同时利用了图结构和节点特征信息，其中包括谱图卷积神经网络 （spectral graph convolutional neural network ）、消息传递 （message passing）方法（或者也称作邻域聚合 neighbor aggregation 方法）以及基于 RNN 的邻域聚合方法。

   所有这些方法中，消息传递方法由于其灵活性和良好的性能最近引起了特别的关注。已有一些工作通过使用 attention 机制、随机游走、edge feature来改善基础的邻域聚合方式，并使得邻域聚合可以扩展到大图。但是，所有这些方法对于每个节点仅支持非常有限的邻域规模。事实上，如果能够使用更大的邻域，则可以为模型提供更多的有效信息。尤其是对于图的外围节点或者标签稀疏的节点。

   增加这些算法的邻域大小并不简单，因为这些方法中的邻域聚合本质上是拉普拉斯平滑的一种，如果层数太多将导致过度平滑（over-smoothing ）。在JK-Net 的论文中，作者强调了这个挑战，并建立了随机游走和消息传递机制之间的关联。通过这个关联我们发现：随着层数的增加，GCN 会收敛到随机游走的极限分布。这个极限分布是整个图的属性，和随机游走的起始节点无关。因此这个分布无法描述随机游走起始节点的邻域（因为过度平滑）。因此 GCN 的性能必然会随着卷积层数量（具体而言是随着 aggregation 层的数量）的增加而下降。

   为解决这个问题，论文 《 Predict then propagate: Graph neural networks meet personalized pagerank》 首先分析了这个极限分布和 PageRank 之间的内在联系，然后提出了personalized propagation of neural predictions: PPNP 算法，该算法利用 Personalized PageRank 衍生而来的消息传递方案。PPNP 算法增加了消息回传根节点的机会，从而确保 PageRank Score 编码了每个根节点的局部邻域。这个回传概率（ teleport probability ）使得我们能够平衡以下两方面的需求：保留节点的局部性（即，避免过度平衡） vs 利用来自大型邻域的信息。

   作者表明，这种消息传递方案允许使用更多的层（理论上无限多），而不会导致过度平滑。另外，PPNP 的训练时间相比以前的模型相同或者更快，参数数量相比以前的模型相同或者更少，计算复杂度和边的数量呈线性关系。此外，PPNP 利用一个大的、可调整的邻域来分类，并且可以轻松地和任何神经网络相结合。实验表明，PPNP 超越了最近提出的几种 GCN-like 的半监督分类模型。

2. 在传统的消息传递方法中， propagation 和 classification 固有地耦合在一起，即 classification 依赖于 propagation。但是在 PPNP 中，作者将 propagation 和 classification 解耦，使得二者相互独立。这使得我们能够在不改变神经网络的情况下实现更大的邻域。而在消息传递方法中，如果想多传递一个 step 就需要多加一个 layer 。

   PPNP 的基本思想是：首先预测节点的标签（classification 步骤），然后利用标签传播算法重新修正得到最终的标签（propagation 步骤）。这种方法有效的前提是：相邻节点具有相似的 label 。

   PPNP 还允许传播算法、以及根据节点特征执行预测的神经网络独立开发。这意味着我们可以将任何 SOTA 预测方法和PPNP 的传播算法相结合。作者甚至发现：在训练期间没有使用到任何图结构信息的模型，仅在inference 阶段使用PPNP 的传播算法可以显著提升模型预测的准确性。

3. 相关工作：

   • 有些工作试图在每个节点添加跳跃连接，从而改善消息传递算法的训练，以及增加每个节点上可用的邻域大小。如，JK-Net 将跳跃连接和邻域聚合方案相结合。但是这些方法的邻域范围仍然有限，当消息传递的 layer 数量很少的情况下非常明显。

     虽然可以在我们的 PPNP 中使用的神经网络中添加跳跃连接，但是这不会影响我们的传播方案。因此，我们解决邻域范围的方法和这些模型无关。

   • 《Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning》通过将消息传递和 co-training & self-training 相结合来促进训练，通过这种组合实现的改善与其它半监督分类模型报告的结果相似。

     注意，大多数算法，包括我们的算法，都可以用 co-training & self-training 进行改进。但是，这些方法使用的每个 additional setp 都对应一个完整的训练周期，因此会大大增加训练时间。

   • 在最近的工作中，人们通过将跳跃连接和 batch normalization 相结合，提出了避免过度平滑问题的Deep GNN （《Mean-field theory of graph neural networks in graph partitioning》、《Supervised Community Detection with Line Graph Neural Networks》）。

     但是，我们的模型通过解耦预测和传播，从而简化了体系结构并解决该问题。并且我们的方法不依赖于任何临时性（ad-hoc）技术，这些临时性的技术进一步复杂化模型并引入额外的超参数。

     此外，我们的 PPNP 在不引入额外层的情况下增加了邻域范围，因此和 Deep GNN 相比，训练速度会更快更容易。

1.1 模型

1. 定义图 $G=(V,E)$$G=(V,E)$ ，其中 $V=\{v_1,\cdots ,v_n\}$$V=\{v_1,\cdots,v_n\}$ 为节点集合， $E=\{e_{i,j}\}$$E=\{e_{i,j}\}$ 为边集合， $n$$n$ 为节点数量， $m$$m$ 为边数量。

   假设每个节点 $v_i$$v_i$ 关联一个特征向量 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$\mathbf{\vec x}_i\in \mathbb R^{d_f}$ ，$d_f$$d_f$ 为特征向量的维度。所有节点的特征向量组成的矩阵为特征矩阵 $\mathbf{X}\in {\mathbb{R}}^{n\times d_f}$$\mathbf X\in \mathbb R^{n\times d_f}$ ，其中第 $i$$i$ 行为 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 。

   假设每个节点 $v_i$$v_i$ 关联一个类别 $y_i$$y_i$ ，类别数量为 $K$$K$ 。我们将 $y_i$$y_i$ 扩展为一个 one-hot 向量 ${\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^K$$\mathbf{\vec y}_i\in \mathbb R^K$ 。所有节点的类别向量组成的矩阵为类别矩阵 $\mathbf{Y}\in {\mathbb{R}}^{n\times c}$$\mathbf Y\in \mathbb R^{n\times c}$ ，第 $i$$i$ 行为 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 。

   假设图的邻接矩阵为 $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$ ，则 $\tilde{\mathbf{A}}=\mathbf{A}+{\mathbf{I}}_n$$\tilde{\mathbf A} = \mathbf A + \mathbf I_n$ 为添加了自循环（self-loops）的邻接矩阵。

1.1.1 GCN 及其限制

1. 卷积神经网络GCN是一种用于半监督分类的简单且应用广泛的消息传递算法。假设有两层消息传递，则预测结果为：

   $$\mathbf{Z}=\text{softmax}\left(\widehat{\tilde{\mathbf{A}}}\text{relu}\left(\widehat{\tilde{\mathbf{A}}}\mathbf{X}{\mathbf{W}}_0\right){\mathbf{W}}_1\right)$$

   其中：

   • $\widehat{\tilde{\mathbf{A}}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\in {\mathbb{R}}^{n\times n}$$\hat{\tilde{\mathbf A}} = \tilde{\mathbf D}^{-1/2} \tilde{\mathbf A}\tilde{\mathbf D}^{-1/2}\in \mathbb R^{n\times n}$ 为一个对称矩阵，它是带自循环的邻接矩阵的归一化形式。 $\tilde{\mathbf{D}}$$\tilde{\mathbf D}$ 为一个对角矩阵， ${\tilde{D}}_{i,i}=\sum _j{\tilde{A}}_{i,j}$$\tilde D_{i,i} = \sum_j \tilde A_{i,j}$ 。

   • $\mathbf{Z}\in {\mathbb{R}}^{n\times K}$$\mathbf Z\in \mathbb R^{n\times K}$ 为每个节点预测的 label 分布。

   • ${\mathbf{W}}_0,{\mathbf{W}}_1$$\mathbf W_0, \mathbf W_1$ 为待训练的权重矩阵。

   对于两层 GCN，它仅考虑 2-hop 邻域中的邻居节点。基本上有两个原因使得消息传递算法（如 GCN）无法自然地扩展到使用更大的邻域：

   • 首先，如果使用太多的层，则基于均值的聚合会导致过度平滑（over-smoothing）。因此，模型失去了局部邻域的信息。

   • 其次，最常用的邻域聚合方案在每一层使用可学习的权重矩阵，因此使用更大的邻域必然会增加神经网络的深度和参数数量。虽然参数数量可以通过权重共享来避免，但这不是通用的做法。

   理论上，邻域大小和神经网络的深度是不相关的、完全正交的两个因素。它们应该互不影响才对。实际上在 GCN 中它们是相互捆绑的（给定神经网络深度就意味着给定了邻域大小），并导致了严重的性能问题。

2. 我们首先关注第一个问题。在 JK-Net 中已经证明：对于一个 $L$$L$ 层的 GCN，任意节点 $y$$y$ 对节点 $x$$x$ 的影响力得分 $I(x,y)=\sum _{s=1}^{d_f}\sum _{t=1}^{d_h}|J(x,y{)}_{s,t}|$$I(x ,y) = \sum_{s=1}^{d_f}\sum_{t=1}^{d_h} |J(x,y)_{s,t}|$ 正比于在 $\tilde{G}$$\tilde G$ （每个节点带自循环的 $G$$G$ ）上从节点 $x$$x$ 开始到 $y$$y$ 的 $L$$L$ 步的随机游走概率 $P_{rw}(x\to y,L)$$P_{rw}(x\rightarrow y, L)$。 其中雅可比矩阵 $\mathbf{J}(x,y)=\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]$$\mathbf J(x,y) = \left[\frac{\partial \mathbf{\vec h}_x^{(L)}}{\partial \mathbf{\vec h}_y^{(0)}}\right]$ 。因此节点 $x$$x$ 的信息以随机游走的方式传播到节点 $y$$y$ 。

   如果选择极限 $L\to \mathrm{\infty }$$L\rightarrow \infty$，且图是不可约的 irreducible 且非周期性的，则这个随机游走概率分布 $P_{rw}(x\to y,L)$$P_{rw}(x\rightarrow y, L)$ 收敛到极限分布（或称作平稳分布） $P_{lim}(\to y)$$P_{\lim}(\rightarrow y)$ 。可以通过求解方程来获得该分布：

   $${\overrightarrow{\pi }}_{lim}=\widehat{\tilde{\mathbf{A}}}{\overrightarrow{\pi }}_{lim}$$

   显然，极限分布取决于整个图，并且独立于随机游走的起始节点 $x$$x$ （或称作根节点）。因此，极限分布不适合描述根节点 $x$$x$ 的局部邻域（因为它与节点 $x$$x$ 无关）。

1.1.2 PPNP

1. 我们可以考察极限分布和 PageRank 之间的联系来解决这个局部邻域失去焦点（lost focus）问题。

   极限分布和 PageRank 的区别仅在于前者在邻接矩阵中增加了自循环，并对分布进行了归一化。原始的 PageRank 的分布为：

   $${\overrightarrow{\pi }}_{\text{pr}}={\mathbf{A}}_{\text{rw}}{\overrightarrow{\pi }}_{\text{pr}}$$

   其中 ${\mathbf{A}}_{\text{rw}}=\mathbf{A}{\mathbf{D}}^{-1}\in {\mathbb{R}}^{n\times n}$$\mathbf A_\text{rw} = \mathbf A \mathbf D^{-1}\in \mathbb R^{n\times n}$ 。

   建立这种联系之后，我们现在可以考虑使用结合了根节点的 PageRank 变体： Personalized PageRank 。

2. 我们定义回传向量（ teleport vector ） ${\overrightarrow{\mathbf{i}}}_x$$\mathbf{\vec i}_x$ 来表示根节点 $x$$x$ ：它是一个 one-hot 向量，只有节点 $x$$x$ 对应的元素为1 、其它元素为 0 。

   对于节点 $x$$x$ ，其 Personalized PageRank 的分布为：

   $${\overrightarrow{\pi }}_{\text{ppr}}^{(x)}=(1-\alpha )\widehat{\tilde{\mathbf{A}}}{\overrightarrow{\pi }}_{\text{ppr}}^{(x)}+\alpha {\overrightarrow{\mathbf{i}}}_x$$

   其中 $\alpha \in (0,1]$$\alpha \in (0,1]$ 为回传概率（ teleport probability ）（也叫做重启概率）。

   通过求解该等式，我们得到：

   $${\overrightarrow{\pi }}_{\text{ppr}}^{(x)}=\alpha {({\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}})}^{-1}{\overrightarrow{\mathbf{i}}}_x$$

   可以看到：通过使用回传向量 ${\overrightarrow{\mathbf{i}}}_x$$\mathbf{\vec i}_x$ 之后，即使在极限分布中我们也能够保留节点 $x$$x$ 的局部邻域。

   因为在该模型中，节点 $y$$y$ 对根节点 $x$$x$ 的影响力得分 $I(x,y)$$I(x,y)$ 正比于 ${\overrightarrow{\pi }}_{\text{ppr}}^{(x)}$$\vec\pi_\text{ppr}^{(x)}$ 的第 $y$$y$ 个元素。对于每个根节点，该元素值都不相同。参数 $\alpha$$\alpha$ 决定了当我们远离根节点时，影响力得分的衰减速度。

3. 考虑所有节点的回传向量，则我们得到了完整的 Personalized PageRank 矩阵 ${\mathbf{\Pi }}_{\text{ppr}}\in {\mathbb{R}}^{n\times n}$$\mathbf \Pi_\text{ppr}\in \mathbb R^{n\times n}$ ：

   $${\mathbf{\Pi }}_{\text{ppr}}=\alpha {({\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}})}^{-1}$$

   其中 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 的第 $x$$x$ 列表示 ${\overrightarrow{\pi }}_{\text{ppr}}^{(x)}$$\vec\pi_\text{ppr}^{(x)}$ 。因此元素 ${\mathrm{\Pi }}_{\text{ppr}}(y,x)$$\Pi_\text{ppr}(y,x)$ 正比于节点 $y$$y$ 对节点 $x$$x$ 的影响力得分。

   注意到由于对称性 ${\mathbf{\Pi }}_{\text{ppr}}={\mathbf{\Pi }}_{\text{ppr}}^{\mathrm{\top }}$$\mathbf \Pi_\text{ppr} = \mathbf \Pi_\text{ppr}^\top$ ，因此节点 $y$$y$ 对节点 $x$$x$ 的影响力得分总是等于节点 $x$$x$ 对节点 $y$$y$ 的影响力得分。

   事实上这里需要考虑矩阵 ${\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}}$$\mathbf I_n - (1-\alpha) \hat{\tilde{\mathbf A}}$ 是否可逆，如果不可逆则 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 不存在。当且仅当 ${\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}}$$\mathbf I_n - (1-\alpha) \hat{\tilde{\mathbf A}}$ 可逆时， ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 才存在。可以证明 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 一定存在。

   证明：要想证明矩阵 ${\mathbf{\Pi }}_{\text{ppr}}=\alpha {({\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}})}^{-1}$$\mathbf \Pi_\text{ppr} = \alpha \left( \mathbf I_n - (1-\alpha) \hat{\tilde{\mathbf A}}\right)^{-1}$ 存在，则需要证明 $\text{det}({\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}})\ne 0$$\text{det}\left( \mathbf I_n - (1-\alpha) \hat{\tilde{\mathbf A}}\right)\ne 0$ 。

   由于 $1-\alpha \ne 0$$1-\alpha \ne 0$ ，因此要想证明 $\text{det}({\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}})\ne 0$$\text{det}\left( \mathbf I_n - (1-\alpha) \hat{\tilde{\mathbf A}}\right)\ne 0$ ，则需要证明 $det(\widehat{\tilde{\mathbf{A}}}-\frac{1}{(1-\alpha )}{\mathbf{I}}_n)\ne 0$$\det\left( \hat{\tilde{\mathbf A}} - \frac{1}{ (1-\alpha)}\mathbf I_n\right)\ne 0$。

   通过 Gershgorin circle theorem 可以证明 $\widehat{\tilde{\mathbf{A}}}$$\hat{\tilde{\mathbf A}}$ 的最大特征值为 1，因此 $\frac{1}{1-\alpha }>1$$\frac{1}{1-\alpha}\gt 1$ 一定不是 $\widehat{\tilde{\mathbf{A}}}$$\hat{\tilde{\mathbf A}}$ 的特征值，因此 $det(\widehat{\tilde{\mathbf{A}}}-\frac{1}{(1-\alpha )}{\mathbf{I}}_n)\ne 0$$\det\left( \hat{\tilde{\mathbf A}} - \frac{1}{ (1-\alpha)}\mathbf I_n\right)\ne 0$ 。因此证明了 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 一定存在。

4. 为了将上述影响力得分用于半监督分类，我们首先根据每个节点的自身特征来生成预测（prediction），然后通过我们的 Personalized PageRank 机制来传播prediction 从而生成最终的预测结果。这就是personalized propagation of neural predictions: PPNP 的基础。

   PPNP 模型为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i=f_{\theta }\left({\overrightarrow{\mathbf{x}}}_i\right)\\ \mathbf{Z}=\text{softmax}\left({\mathbf{\Pi }}_{\text{ppr}}\mathbf{H}\right)\end{array}$$

   其中：

   • $f_{\theta }(\cdot )$$f_{\theta}(\cdot)$ 为神经网络，$\theta$$\theta$ 为网络参数，它根据节点 $i$$i$ 的特征 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 来生成节点 $i$$i$ 的预测 ${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^K$$\mathbf{\vec h}_i\in \mathbb R^K$ 。$\mathbf{H}\in {\mathbb{R}}^{n\times K}$$\mathbf H\in \mathbb R^{n\times K}$ 为所有节点根据其特征来生成的预测的矩阵，每行对应一个节点。

     注意：由于 $f_{\theta }(\cdot )$$f_\theta(\cdot)$ 在每个节点的特征上独立执行，因此可以并行进行。

   • $\mathbf{Z}\in {\mathbb{R}}^{n\times K}$$\mathbf Z\in \mathbb R^{n\times K}$ 为PPNP每个节点预测的 label 分布。

   事实上，还可以用任何传播矩阵来代替 $\widehat{\tilde{\mathbf{A}}}$$\hat{\tilde{\mathbf A}}$ ，如 ${\mathbf{A}}_{\text{rw}}$$\mathbf A_\text{rw}$ 。

   可以看到，PPNP 将神经网络预测和图的传播相互分离。这种分离还解决了上述提到的第二个问题：神经网络的深度现在完全独立于传播算法。正如我们将在 GCN 和 PageRank 联系时所看到的，Personalized PageRank 能够有效地使用无限多个卷积层，这在传统的消息传递框架中显然是不可能的。此外，分离还使得我们可以灵活地运用任何方法来生成预测。

   这个就是标签传播 label propagation: LP 的思想，将 MLP 和 LP 相结合。该方法有效的前提是：相邻节点具有相似的 label 。

   PPNP 传播的是 prediction，而传统 GCN 传播的是 representation 。

5. 虽然在 inference 阶段，生成单个节点的预测和传播这个预测是连续进行的（看起来是多阶段的），实际上模型的训练是端到端的。即，在反向传播期间梯度流经传播框架（相当于隐式地考虑了无限多个邻域聚合层）。因此，采用传播框架之后大大提高了模型的准确性。

1.1.3 APPNP

1. 直接计算完整的 Personalized PageRank 矩阵 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 的计算效率较低，并且产生了一个稠密的 ${\mathbb{R}}^{n\times n}$$\mathbb R^{n\times n}$ 的矩阵。使用这个稠密矩阵将导致训练和推断时 $O(n^2)$$O(n^2)$ 的计算复杂度和空间复杂度。

   为解决这个问题，重新考虑等式：

   $$\begin{array}{c}\mathbf{T}={\mathbf{\Pi }}_{\text{ppr}}\mathbf{H}\\ \mathbf{Z}=\text{softmax}(\mathbf{T})\end{array}$$

   除了将 $\mathbf{T}$$\mathbf T$ 视为稠密的 Personalized PageRank 矩阵 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 和 prediction 矩阵 $\mathbf{H}$$\mathbf H$ 的乘积之外，还可以将其视为 Topic-sensitive PageRank 的变体，其中每个类别对应于一个主题。在这个角度下，$\mathbf{H}$$\mathbf H$ 的每一列都定义了一个在所有节点上的分布（非归一化的），这个分布充当 teleport set 。因此，我们可以通过采用 Topic-sensitive PageRank 来近似计算 PPNP，我们称其为 approximate personalized propagation of neural predictions: APPNP 。

   APPNP 通过 Topic-sensitive PageRank 的幂次迭代（ power iteration ）来达到线性复杂度。Topic-sensitive PageRank 的幂次迭代和带重启的随机游走相关，它的每个幂次迭代步定义为：

   $$\begin{array}{c}{\mathbf{T}}^{(0)}=\mathbf{H}=f_{\theta }(\mathbf{X})\\ {\mathbf{T}}^{(l+1)}=(1-\alpha )\widehat{\tilde{\mathbf{A}}}{\mathbf{T}}^{(l)}+\alpha \mathbf{H}\\ \mathbf{Z}=\text{softmax}((1-\alpha )\widehat{\tilde{\mathbf{A}}}{\mathbf{T}}^{(L-1)}+\alpha \mathbf{H})\end{array}$$

   其中：prediction 矩阵 $\mathbf{H}$$\mathbf H$ 扮演了 starting vector 和 teleport set 的作用；$L$$L$ 定义了幂次迭代的数量。

   注意：这个方法保持了图的稀疏性，并且从未构建一个 ${\mathbb{R}}^{n\times n}$$\mathbb R^{n\times n}$ 的矩阵（$\mathbf{H},{\mathbf{T}}^{(l)},\mathbf{Z}$$\mathbf H,\mathbf T^{(l)},\mathbf Z$ 都是 ${\mathbb{R}}^{n\times K},K\ll n$$\mathbb R^{n\times K}, K\ll n$ ）。

   但是， $\tilde{\mathbf{A}}=\mathbf{A}+{\mathbf{I}}_n$$\tilde{\mathbf A} = \mathbf A + \mathbf I_n$ 为 ${\mathbb{R}}^{n\times n}$$\mathbb R^{n\times n}$ 的稠密矩阵，$\widehat{\tilde{\mathbf{A}}}$$\hat{\tilde{\mathbf A}}$ 为 $\tilde{\mathbf{A}}$$\tilde{\mathbf A}$ 的归一化形式，因此也是稠密矩阵。$\widehat{\tilde{\mathbf{A}}}{\mathbf{T}}^{(l)}$$\hat{\tilde{\mathbf A}} \mathbf T^{(l)}$ 的计算复杂度为 $O(n^{2}K)$$O(n^2K)$ ，对于千万甚至亿级的图而言，这个计算复杂度仍然是不可行的。

2. 可以证明：当 $L\to \mathrm{\infty }$$L\rightarrow\infty$ 时， APPNP 收敛到 PPNP 。

   证明：APPNP 的迭代公式：

   $${\mathbf{T}}^{(l+1)}=(1-\alpha )\widehat{\tilde{\mathbf{A}}}{\mathbf{T}}^{(l)}+\alpha \mathbf{H}$$

   在经过 $L$$L$ 步传播之后：

   $${\mathbf{T}}^{(L)}=((1-\alpha {)}^L{\widehat{\tilde{\mathbf{A}}}}^L+\alpha \sum _{i=0}^{L-1}(1-\alpha {)}^i{\widehat{\tilde{\mathbf{A}}}}^i)\mathbf{H}$$

   当取极限 $L\to \mathrm{\infty }$$L\rightarrow\infty$ 时，第一项趋近于零，第二项为一个几何级数。当 $\alpha \in (0,1]$$\alpha \in (0,1]$ 时，另外考虑到 $\widehat{\tilde{\mathbf{A}}}$$\hat{\tilde{\mathbf A}}$ 为对称的归一化邻接矩阵，因此有 $\text{det}(\widehat{\tilde{\mathbf{A}}})\le 1$$\text{det}(\hat{\tilde{\mathbf A}}) \le 1$ ，因此第二项收敛。因此有：

   $$\begin{array}{c}{\mathbf{T}}^{(\mathrm{\infty })}=\alpha {({\mathbf{I}}_n-(1-\alpha )\widehat{\tilde{\mathbf{A}}})}^{-1}\mathbf{H}={\mathbf{\Pi }}_{\text{ppr}}\mathbf{H}\\ \mathbf{Z}=\text{softmax}\left({\mathbf{T}}^{(\mathrm{\infty })}\right)=\text{softmax}\left({\mathbf{\Pi }}_{\text{ppr}}\mathbf{H}\right)\end{array}$$

   这就是 PPNP。

3. PPNP/APPNP 的传播框架（ propagation scheme ）不需要训练任何其它额外的参数。与 GCN 这样的模型不同，GCN 通常需要为每个 propagation layer （GCN 中的传播层就是聚合层）提供更多的参数。因此，PPNP/APPNP 中可以使用很少的参数传播得更远。实验结果表明：这种传播能力确实非常有益。

4. 将 PPNP 视为不动点（fixed-point ）迭代，这和最原始的图神经网络 GNN 模型存在关联。图神经网络中也是需要通过迭代来求解不动点，但是PPNP 和GNN 存在以下几点不同：

   • PPNP 的不同点迭代实际上通过 Personalized PageRank 已经求解到，因此直接使用 Personalized PageRank 矩阵 ${\mathbf{\Pi }}_{\text{ppr}}$$\mathbf \Pi_\text{ppr}$ 。无需一步一步地迭代计算。

   • PPNP 在传播之前应用学到的特征变换，而 GNN 中在传播过程中应用学到的特征变换。

5. PPNP/APPNP 中，影响每个节点的邻域大小可以通过回传概率 $\alpha$$\alpha$ 进行调整，这可以使得我们能够针对不同类型的图（不同的图需要考虑不同的邻域大小）来优化模型。

   $\alpha$$\alpha$ 越大，则停留在局部的概率越大，邻域越小；反之，则邻域越大。

6. 最后，我们给出 PPNP 模型的示意图。

   • 首先利用神经网络 $f_{\theta }(\cdot )$$f_{\theta}(\cdot)$ 来对每个节点的特征 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 来生成预测 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$。

   • 然后使用 Personalized PageRank 来传播预测 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$。

   注意该模型是端到端训练的，而不是 pipeline 训练的。

   

1.2 实验

1. 数据集：我们使用四个文本分类数据集。

   • CITESEER：引文网络，每个节点代表一篇论文，边代表它们之间的引用。

   • CORA-ML：引文网络，每个节点代表一篇论文，边代表它们之间的引用。

   • PUBMED：引文网络，每个节点代表一篇论文，边代表它们之间的引用。

   • MICROSOFT ACADEMIC 数据集：引文网络，每个节点代表一篇论文，边代表 co-authorship。

   对于每个图，我们使用其最大连通分量。所有数据集都使用论文摘要的 bag-of-word 作为特征。下图给出了这些数据集的统计信息，其中 SP 表示平均最短路径长度。

   注意：更大的图不一定具有较大的直径（以 SP 来衡量）。总体而言，这些图的平均直径为 5~10，因此常规的两层 GCN 网络无法覆盖整个图。

   

2. 因为使用了不同的训练配置和过拟合，很多实验评估都遭受了肤浅的统计评估（superficial statistical evaluation ）和实验偏差（experimental bias ）。

   实验偏差的原因是：对于训练集/验证集/测试集的单次拆分没有明显区分验证集和测试集，或者对于每个数据集甚至是数据集的每次拆分都微调超参数。正如我们评估结果中显示的，消息传递算法对于数据集的拆分以及权重初始化非常敏感，因此精心设计的评估方法非常重要。

   我们的工作旨在建立一个全面彻底的评估方法：

   • 首先，我们对每个实验执行 100 次，其中每次都是随机拆分训练集并随机初始化权重。我们采用 Glorot 权重初始化方法。

   • 其次，我们将数据集拆分为可见集和测试集，这种拆分固定不变。其中测试集仅用于报告最终性能，并不会进行训练和超参数择优。

     • 对于引文网络，可见集采样了 1500 个节点，剩余节点为测试集。

     • 对于 MICROSOFT ACADEMIC 网络，可见集采样了 5000 个节点，剩余节点为测试集。

     可见集被随机拆分为训练集、验证集、以及早停集。训练集中每种类别包含 20 个节点，早停集包含 500 个节点，剩余节点作为验证集。

     我们选择20个不同的随机数种子并固定下来，接下来选择其中的一部分用于随机拆分可见集--测试集、另一部分用于随机拆分训练集--验证集。 另外，每种数据拆分都进行 5 次随机初始化，因此实验一共进行 100 次。

     

   • 为进一步防止过拟合，考虑到所有实验的数据集都使用 bag-of-word 特征，因此我们对所有数据集都采用相同数量的层数、相同的hiddel layer 维度、相同的 dropout 比例、相同的 $L_2$$L_2$ 正则化参数、 相同的学习率。

   • 为防止实验偏差，我们使用 CITESEER 和 CORA-ML 上的网格搜索来分别优化所有模型的超参数，并在模型之间使用相同的早停准则：patience = 100 的阈值，以及最多 $10000$$10000$ 个 epoch（实际上永远无法达到这么多 epoch）。

     只要在早停数据集的准确率提升或者损失函数降低，则重设 patience。我们选择在早停数据集上准确率最高的 patience。该准则受到 GAT 的启发。

   • 最后，为了确保我们实验配置的统计鲁棒性，我们通过 bootstrapping 计算出置信区间，并报告主要结论的 t-test 的 p-value。

   据我们所知，这是迄今为止对 GCN 模型的最严格的研究。

3. Baseline 方法：

   • GCN：图卷积神经网络。

   • N-GCN ：结合了无监督的随机游走和半监督学习两方面优势的 N-GCN 模型。

   • GAT ：图注意力神经网络。

   • bootstrapped feature propagation: FP ：将经典的线性的图扩散结合 self-training 框架，从而得到的 FP 网络。

   • jumping knowledge networks with concatenation: JK ：JK-Net 网络。

   • 对于 GCN 我们还给出了未经过超参数优化的普通版本 V.GCN 来说明早停和超参数优化的强大影响。

4. 模型配置：

   • V.GCN：使用原始论文的配置，其中包括两层的卷积层、隐层维度 $h=16$$h=16$、邻接矩阵上不使用 dropout、$L_2$$L_2$ 正则化系数 $\lambda =5\times {10}^{-4}$$\lambda = 5\times 10^{-4}$ 。并且采用原始论文的早停配置：在损失函数上最多迭代 200 个 step，以及早停的 patience = 10 。

   • 择优的 GCN：使用两层卷积层、隐层维度 $h=64$$h=64$、邻接矩阵上使用 dropout rate = 0.5 的 dropout、$L_2$$L_2$ 正则化系数为 $\lambda =0.02$$\lambda = 0.02$ 。

   • N-GCN：每个随机游走长度使用 4 个 head 以及隐层维度 $h=16$$h=16$，随机游走长度从 1 step 到 4 step 。使用 $\lambda ={10}^{-5}$$\lambda = 10^{-5}$ 的 $L_2$$L_2$ 正则化来正则化所有层。使用 attention 机制来合并所有head 的预测。

   • GAT：使用优化好的原始论文的超参数，除了 $L_2$$L_2$ 正则化系数为 $\lambda =0.001$$\lambda = 0.001$ 以及学习率为 0.01。和原始论文相反，对于 PUBMED 数据集我们并未使用不同的超参数。

   • FP：使用 $\alpha =0.2$$\alpha = 0.2$ 的回传概率，以及 10 个传播 step、10 个 self-training step ，每个 step 增加 $r=0.1\times n$$r=0.1\times n$ 个训练节点。

     我们在预测中添加交叉熵最小的训练节点。每个类别添加的节点数基于预测的类别的比例。注意，该模型在初始化时不包含任何随机性，因此我们在每个 train/early stopping/test 集合拆分时仅拆分一次。

   • JK-Net：我们使用 concatenation 层聚合方案，采用三层卷积神经网络，每层的隐层维度 $h=64$$h=64$ 。对所有层采用 $\lambda =0.001$$\lambda = 0.001$ 的 $L_2$$L_2$ 正则化，并在所有层执行 dropout rate = 0.5 的 dropout 。但是正则化和 dropout 并不作用在邻接矩阵上。

   • PPNP：为确保公平的模型比较，我们为 PPNP 的预测模型使用了神经网络，该网络在结构上和 GCN 非常相似，并具有相同的参数数量。我们使用两层网络，每层的隐层维度为 $h=64$$h=64$ 。

     我们在第一层的权重矩阵上应用 $\lambda =0.005$$\lambda = 0.005$ 的 $L_2$$L_2$ 正则化，在所有层的权重矩阵以及邻接矩阵上应用 dropout rate = 0.5 的 dropout 。

     • 对于 APPNP，我们在每个幂次迭代步之后，都会对邻接矩阵的 dropout 重新采样。

     • 对于传播过程，我们使用 $\alpha =0.1$$\alpha = 0.1$ 的重启概率，以及 $L=10$$L=10$ 个幂次迭代步。

       对于 MICROSOFT ACADEMIC 数据集，我们使用 $\alpha =0.2$$\alpha = 0.2$ 的重启概率，因为该数据集的结构不同。

     注意：PPNP 使用浅层的神经网络和较大的 $L$$L$ 相结合，从而获得最佳效果。下图表示 APPNP 不同深度的网络对于验证集的准确率。可以看到：更深的预测网络无法提高准确率，这可能是因为简单的 Bag-of-word 特征以及训练集太小导致的。

     

   另外，我们使用 Adam 优化器并且所有模型的学习率都为 0.01 。我们使用交叉熵损失函数，并且将特征矩阵按行进行 $L_1$$L_1$ 归一化。

5. 不同模型在测试集上的指标如下表所示，其中第一张表为 Micro-F1 Score，第二张表为 Macro-F1 Score，最后两张表为 t 检验结果。* 表示模型在 PUBMED, MS ACADEMIC 上 Out Of Memory 。

   结论：

   • 我们的 PPNP/APPNP 在所有数据集上均明显优于 SOA baseline 方法。

   • 我们的严格的比较方式可能会低估 PPNP/APPNP 的优势。通过 t 检验表明，该比较结果具有统计学意义 $p\le 0.05$$p \le 0.05$ 。

   • 这种严格的比较方式还表明：当考虑更多的数据集拆分、适当地超参数优化、合理地模型训练时，最近的一些工作（如 N-GCN, GAT, JK-Net, FP 等）的优势实际上消失了。

     在我们的配置中，一个简单的、经过超参数优化的 GCN 就超越了最近提出的这几种模型。

   

   

   

6. 我们给出不同模型在不同数据集上，由于不同的随机初始化以及不同的数据集拆分带来的测试准确率的变化。这表明严格的评估方式对于模型比较的结论至关重要。

   此外，这还展示了不同方法的鲁棒性。如 PPNP, APPNP, GAT 通常具有较低的方差。

   

7. 我们考虑不同模型的训练时间。这里考虑每个 epoch 的平均训练时间（而不是整个训练过程的时间）。我们并未考虑收敛速度（需要多少个 epoch 收敛），因为不同模型的超参数都各自调优，并且不同模型使用的 early stopping 准则不同（调优之后各自的 patience 不一样）。* 表示无法实现，因为无法训练；** 表示在 PUBMED, MS ACADEMIC 上 Out Of Memory 。

   结论：

   • PPNP 只能应用于中等规模的图，APPNP 可以扩展到大图。

   • 平均而言，APPNP 比 GCN 慢 25%，因为 APPNP 的矩阵乘法的数量更多。但是 APPNP 的可扩展性和 GCN 相似。

     APPNP 比 GCN 慢一些但是效果好一点点，所以这是一个速度和效果的 trade-off 。此外，如果 GCN 总的训练时间与 APPNP 相同（即，GCN 多 25% 的 epoch ），是否二者效果一致？这样的话，APPNP 就没有什么优势了。

   • APPNP 比其它更复杂的模型（如 GAT ）快得多。

   

8. 由于现实世界数据集的 label 比例通常很小，因此研究小样本模型的性能非常重要。下图依次给出 CORA_ML, CITESEER, PUBMED 数据集上，每个类别训练节点数量 $n_{\text{train,per}\text{class}}$$n_\text{train,per\;class}$ 对于模型性能的影响（以测试准确率为指标）。

   结论：训练的label 节点越稀疏，PPNP/APPNP 的优势越大。这可以归因于 PPNP/APPNP 较高的传播范围，从而将label 节点传播到更远的地方。

   为支持这种归因，我们找到了更多的证据：我们比较了 APPNP 和 GCN 的准确率的提升幅度 ，发现准确率提升幅度依赖于测试节点和训练集的距离（以最短路径衡量）。如下面最后一幅图所示，横坐标为最短路径（单位为 hop），纵坐标为提升幅度，$\overline{n}$$\bar n$ 为该最短路径的测试节点数量。可以看到：APPNP 相对于 GCN 的性能提升，随着测试节点到训练集的距离的增加而增加。这表明距训练集较远的节点从 APPNP 的传播范围的增加中收益更多。

   

   

   

9. 我们评估了幂次迭代（power iteration）数量 $L$$L$ （原始论文用 K 来表示）对于模型准确性的影响。

   结论：

   • 对于 GCN-like（对应于 $\alpha =0$$\alpha = 0$ ，即全局的 PageRank 方法），其性能随着 $L$$L$ 的增加而下降。

   • 对于 APPNP（对应于 $\alpha =0.1$$\alpha = 0.1$ ，即 Personalized PageRank），其性能随着 $L$$L$ 的增加而提升。这证明了个性化传播确实是有效的。

     当 $L$$L$ 增加到无穷大时，APPNP 收敛到 PPNP。但是我们发现，当 $L=10$$L=10$ 时，APPNP 已经足以有效地逼近 PPNP。有趣的是，我们发现这个数字和数据集的半径相符。

   

10. 我们评估了超参数 $\alpha$$\alpha$ （重启概率）对于模型准确率的影响。

    结论：

    • 尽管每个数据集的最优 $\alpha$$\alpha$ 略有不同，但是我们发现 $\alpha \in [0.05,0.2]$$\alpha \in [0.05,0.2]$ 之间时模型表现最佳。

    • 应该对不同的数据集采用不同的 $\alpha$$\alpha$ ，因为不同的图展示出不同的邻域结构。

    注意：较高的 $\alpha$$\alpha$ 会提高模型训练的收敛速度。

    

11. PPNP 和 APPNP 虽然分为预测网络 $f_{\theta }$$f_\theta$ 以及传播两个部分，但是它是端到端训练的。通过研究模型在没有传播时的表现，可以体现传播的价值。下图给出了传播如何影响模型训练和推断。

    • Never：表示从来不使用传播。这表示我们仅使用节点特征来训练和使用一个标准的多层感知机 MLP $f_{\theta }$$f_\theta$ 。

    • Training：表示我们使用APPNP 来训练模型（采用了传播），但是在inference 时仅使用 $f_{\theta }$$f_\theta$ 来预测（而不考虑传播）。

    • Inference：表示我们仅使用特征来训练多层感知机 $f_{\theta }$$f_\theta$ ，但是在 inference 时结合传播来预测。

    • Inf & Training ：表示常规的 APPNP 模型，即在训练和 inference 时总是使用传播。

    结论：

    • Inf & Training 总是可以获得最佳结果，这验证了我们的方法。

    • 在大多数数据集上，仅在 inference 中使用传播时，准确率下降得很少。

      训练期间跳过传播可以大大减少大型数据集的训练时间，因为所有节点都可以独立地处理。

      这也表明我们的模型可以与不包含任何图结构信息的预训练神经网络相结合，并可以显著提高其准确性。

    • Training 相对于 Never 也有较大的改善。这表明仅在训练期间进行传播也是有价值的。因此我们的模型也可以应用于 online/inductive learning，其中只有特征信息（而不是观察到的邻域信息）可用。