Predict then Propagate Graph Neural Networks meet Personalized PageRank[ICLR'19]

ICLR19将PageRank与GNN结合以解决GCN层数无法加深的一篇论文

解决的问题

GCN层数增加后性能反而变差,如何加深GCN的层数。

根据GCN的定义,每一层网络用来捕获一跳邻居的信息,例如一个三层的GCN网络捕获的就是一个顶点三跳邻居以内的信息,而现在如果只能用浅层模型,表示只能捕获有限跳内的邻域信息,而有时候要多几跳才能捕获到有用的信息,例如JK-Net中的例子。

做法及创新

这一篇论文的工作其实是接着JK-Net继续往下,在那篇论文中,作者分析了GCN中信息传递这个过程与随机漫步之间的关系,说明一个K层GCN等价于从源顶点x出发到邻域顶点y的一个K步的随机游走,如果取$k\rightarrow\infin$,节点的极限分布与初始的顶点表示无关,只与图的拓扑结构有关,所以会导致层数加深后性能反而变差,因为不同顶点的表示会趋同,无法区分。另一个看待的角度是,因为原始GCN是对所有聚合的信息做平均操作,层数加深之后各个顶点的邻域都变得跟整张图差不多,既然每个顶点的邻域都变得差不多,做的又是平均操作,每个顶点聚合出来的样子就会都差不多。

论文做法是将预测与传递分离成两个独立的过程,信息传递时采用Personalized PageRank的方式将初始顶点纳入考虑。

PageRank的定义式:

Personalized PageRank的定义式:

$\alpha I_n$是因为加入随即转移概率,避免自环和无外链的顶点的影响,$I_n$是因为前半部分是矩阵需要进行转换。

PPNP对PPR的应用:

其中$A’=A+I_n$,$\hat{A’}=D’^{-1/2}A’D’^{-1/2}$,这么做的目的是,信息传递时,节点不能丢失自身特征,因此我们通过添加一个自环把节点自身特征加回来,来保证节点同时聚合邻域节点特征和自身特征;传递后,度大的节点的聚合特征值比较大,度小的节点的聚合特征值比较小。特征而项的取值范围不一致会带来影响,因此我们通过归一化消除这个问题。。

Personalized PageRank算法的目标是要计算所有节点相对于用户u的相关度。从用户u对应的节点开始游走,每到一个节点都以α的概率停止游走并从u重新开始,或者以1-α的概率继续游走,从当前节点指向的节点中按照均匀分布随机选择一个节点往下游走。这样经过很多轮游走之后,每个顶点被访问到的概率也会收敛趋于稳定,这个时候我们就可以用概率来进行排名了。

相较于原始的GCN模型,现在根顶点$x$对顶点$y$的影响程度$I(x,y)$,变得与$\pi_{ppr}(i_x)$中的第$y$个元素相关,这个影响程度对于每个根顶点都有不同的取值:

PPNP

经过上面的铺垫与介绍,论文提出的模型PPNP可以表示为:

ravXN9.png

APPNP

从前面的构造方式可以看到,矩阵$\prod_{ppr}$将会有$\mathbb{R}^{n\times n}$大小,会带来时间和空间上的复杂度。PPNP中涉及矩阵的求逆运算,因此论文提出了一种近似的计算方法APPNP,计算方式如下:

其中$K$为信息传递的跳数或者说是随机漫步的步数,$k\in[0,K-2]$,这样一来就不用构造一个$\mathbb{R}^{n\times n}$的矩阵了。

PPRGO[KDD’20]

APPNP需要在每次梯度更新时进行计算,而$\pi(i)=\Pi_{i,:}^{ppr}$等价于顶点$i$的PPR向量,其中$\Pi^{ppr}=\alpha(I_n-(1-\alpha)D^{-1}A)^{-1}$。所以PPRGO采用了近似计算PPR的方法来改进PPNP。用$\Pi^{(\epsilon)}$来代替$\Pi^{ppr}$:

$\pi^{(\epsilon)}(i)$由Backward Search得到,并且对近似矩阵取了一个Top-k操作。

数据集

Citeseer、Cora-ML、Pubmed、MS Academic