图神经网络

PPNP & APPNP (ICLR 2019)

Predict Then Propagate:Graph Neural Networks Meet Personalized PageRank

arixv:https://arxiv.org/abs/1810.05997

前言前言前言

主要针对的问题是现有的半监督gcn只考虑很少几步的聚合，要想拓展利用到的邻居节点非常困难（主要是因为这些邻居信息聚合是一种拉普拉斯平滑，叠加过多的层数很容易导致过平滑，即同一联通分量内的节点的隐层向量表征会倾向于收敛到同一个值）。Representation Learning on Graphs with Jumping Knowledge Networks也提到了这个问题，同时，该论文提出了Kipf&Welling提出的GCN与random walk之间的关系。通过这个关系我们可以知道GCN的消息传递矩阵会最终收敛到随机游走的状态概率极限分布。这个极限分布是全图的一个属性，然而他并没有将随机游走的起始点（root）考虑进来，所以这个分布并不适合用来表示起始点的局部邻居信息。（这里的意思是指状态概率极限分布考虑的是全局信息，对应于过平滑问题中局部信息被全局信息刷掉的情况）

为了解决这个问题，论文首先强调了PageRank和这个状态概率极限分布的关系。由于这两者之间具有一定的相关性，所以提出了一种基于personalized PageRank聚合方法，这种方法添加了一个转移回根节点的概率，以保证pagerank的得分同时编码了所有根节点的邻居信息。这个概率使得我们在聚合的过程中能平衡局部和全局的信息，以达到缓解过平滑的效果。

同时，由于该论文提出的算法将神经网络与聚合方法分离，这使得很多方法可以在不改变神经网络结构的基础上实现更大范围的邻居节点聚合，而仅需要在每个聚合层上增加一个附加层。

图卷积神经网络及其限制范围

文章利用Kipf&Welling提出的一阶切比雪夫多项式近似的GCN为例，公式如下：
ZGCN=softmax(A~^ReLU(A~^XW0)W1) Z_{GCN}=softmax(\hat{\widetilde{A}}ReLU(\hat{\widetilde{A}}XW_0)W_1) 需要注意的是，这里完全就是那篇半监督论文里节点分类的公式。Z∈Rn×cZ\in\mathbb{R}^{n\times c}表示预测的标签。A~^=D~−12A~D~−12\hat{\widetilde{A}}=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}是标准化后对称的带self-loop的邻接矩阵，其中D~\widetilde{D}是度对角矩阵。

上面的公式是两层的GCN，能聚合的邻居也只有两阶的邻居。GCN聚合的邻居不能拓展到很大的范围主要有两个原因：1、过多的层数会导致过平滑问题，在引入全局信息的同时会丢失局部信息；2、很多GCN在每一层使用独立的学习参数，过多的层数会导致过多的学习参数（当然这个问题可以通过共享参数解决）。

下面主要介绍第一个原因：

Representation Learning on Graphs with Jumping Knowledge Networks 论文中提出，对于一个k层的gcn，节点xx对yy的影响得分可以表示为I(x,y)=∑i∑j∂Zyi∂ZxjI(x,y)=\sum_{i}\sum_{j}\frac{\partial Z_yi}{\partial Z_xj},这个得分的期望成比例近似于从节点xx开始的k步随机游走的分布Prw′(x→y,k)P_{rw^{'}}(x\to y,k)。换句话说，节点x的特征近似于通过随机游走传播到节点y。如果图是不可约的且非周期性的，且我们让k趋向于无穷大，那么这个随机游走概率分布就会收敛到一个极限分布，Plim(→y)P_{lim}(\to y)。
这个分布可以通过计算等式πlim=A~^πlim\pi_{lim}=\hat{\widetilde{A}}\pi_{lim}获得，正如上面所说的，这个公式独立于随机游走的起始点，不适合表示起始节点的邻居节点。

神经预测的个性化传播

论文中提到，上面提到的极限分布和PageRank中的状态概率矩阵非常类似。原始的PageRank公式为πpr=Arwπpr\pi_{pr}=A_{rw}\pi_{pr}，其中Arw=AD−1A_{rw} = AD^{-1}。我们可以对照一下上下两个等式，发现主要差别就在于A~^\hat{\widetilde{A}}。于是论文就开始考虑使用PageRank的变体——personalized PageRank来引入根节点的信息。论文设置了一个转移向量ixi_x来表示根节点x，这个转移向量是一个one-hot类型的指示向量。论文将这个指示向量引入personalized PageRank得到一个新的迭代公式：πppr(ix)=(1−α)A~^πppr(ix)+αix\pi_{ppr}(i_x)=(1-\alpha)\hat{\widetilde{A}}\pi_{ppr}(i_x)+\alpha i_x，这里的α\alpha是一个转移概率，α∈(0,1]\alpha\in(0,1]，这个参数决定了有多少概率回到初始节点。把公式化简，可得：
πppr(ix)=α(In−(1−α)A~^)−1ix \pi_{ppr}(i_x)=\alpha(I_n-(1-\alpha)\hat{\widetilde{A}})^{-1}i_x

引入了这个转移向量可以使得在极限概率中也保留起始节点的邻居域。在论文提出的模型中节点xx对节点yy的影响力得分I(x,y)I(x,y)成比例于πppryx\pi_{ppr}^{yx}(需要注意的是，由于对称性，πppryx=πpprxy\pi_{ppr}^{yx}=\pi_{ppr}^{xy})。之后，就只需要把转移向量用矩阵替换(one-hot向量的全量矩阵就是一个单位矩阵)，就可以获得一个fully personalized PageRank:πppr=α(In−(1−α)A~^)−1\pi_{ppr}=\alpha(I_n-(1-\alpha)\hat{\widetilde{A}})^{-1}。在这个πppr\pi_{ppr}中，每个元素(xy)表示了节点x对节点y的影响力分数，I(x,y)∝πppryxI(x,y)\propto\pi_{ppr}^{yx}

模型模型模型
Personalized propagation of neural predictions (PPNP)

先给一张结构图:

PPNPPPNP

基于上面提出的fully personalized PageRank,论文提出了PPNP模型，公式如下：
ZPPNP=softmax(α(In−(1−α)A~^)−1H),Hi,:=fθ(Xi,:) Z_{PPNP}=softmax(\alpha(I_n-(1-\alpha)\hat{\widetilde{A}})^{-1}H),\qquad H_{i,:}=f_\theta(X_{i,:}) 其中XX是一个特征向量而fθf_\theta是个神经网络,θ\theta表示参数集合，用来产生预测输出。值得注意的是fθf_\theta可以在每个节点的特征上分别操作，这使得这个方法能够并行化进行。

从上面的公式里我们可以看出，PPNP把聚合层和预测层分开，这使得上面提到的第二个参数过多的问题也迎刃而解。现在神经网络的深度彻底独立于参数量了。

有效性分析

但是要想直接计算完整的个性化PageRank矩阵是十分低效，这个操作会返回一个R(n×n)\mathbb{R}^{(n×n)}的稠密矩阵，利用这个矩阵进行计算会导致无论在时间还是空间上都达到了O(N2)O(N^2 )的复杂度。要想解决这个问题，就要从另一个角度重新看待公式Z=α(In−(1−α)A~^)−1HZ=\alpha(I_n-(1-\alpha)\hat{\widetilde{A}})^{-1}H。公式同样可以被视作是topic-sensitive PageRank的变体，其中预测得出的每一类都与一个class相关。从这个角度看，HH中每一列都可以看作是未标准化的状态概率矩阵。于是，我们就可以通过近似求解topic-sensitive PageRank来计算PPNP。

Approximate personalized propagation of neural predictions (APPNP)

APPNP就是通过幂迭代topic-sensitive PageRank来以一种几乎是线性复杂度的方式计算结果。每一轮幂迭代可以用下面的公式表示：
Z(0)=H=fθ(X)z(k+1)=(1−α)A~^Z(k)+αHZ(K)=softmax((1−α)A~^Z(K−1)+αH) \begin{aligned} Z^{(0)}&=H=f_\theta(X)\\ z^{(k+1)}&=(1-\alpha)\hat{\widetilde{A}}Z^{(k)}+\alpha{H}\\ Z^{(K)}&=softmax((1-\alpha)\hat{\widetilde{A}}Z^{(K-1)}+\alpha H) \end{aligned}

其中，HH同时表示初始向量和传播集合，KK表示幂迭代的次数。从迭代公式里可以看出，这个方法在保留了图稀疏性的同时也不用计算Rn×n\mathbb{R}^{n\times n}。迭代公式的收敛性这里不再展开了，有兴趣的同学们可以去瞄一眼原文。

需要注意的是，与GCN不同，这种方法不需要任何额外参数进行信息聚合层的操作，因此其也能用非常少的参数完成更大范围的邻居信息聚合。

从训练的模式上看，PPNP采用了一步到位的层设计，在实际训练种不用叠加多个层实现多跳邻居聚合，而APPNP和GCN一样需要预设聚合的k跳邻居，并通过迭代叠加实现信息聚合。

无论是在PPNP或APPNP中，领域大小对每个节点的影响可以通过调整转移概率α\alpha来调节，这就使得该模型可以运用于不同类型的网络。

总结总结总结

突然接了个活发现有点坑，短期从时空图转回一下图神经网络的相关内容介绍。这篇论文的内容相对更偏理论，需要一些关于PageRank，personalized PageRank，topic-sensitive PageRank以及JK-nets的前置知识。我学识有限，上面介绍的内容可能有失偏颇，欢迎讨论。总体来说，这篇paper从GCN与PageRank的关系出发，针对过平滑问题提出了改进方法，和JK-nets解决同一类型的问题，但是给出了不一样的方案，很值得一看。(这种论文对我来说一般属于看看就好基本不可能想出这么硬核的改进系列)。