APPNP:PREDICT THEN PROPAGATE: GRAPH NEURAL NETWORKS MEET PERSONALIZED PAGERANK

背景

发表论文时对应的对比算法。

KLICPERA J, BOJCHEVSKI A, GÜNNEMANN S. Predict then Propagate: Graph Neural Net-
works meet Personalized PageRank[C/OL] //7th International Conference on Learning Represen-
tations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. : OpenReview.net, 2019. https:
//openreview.net/forum?id=H1gL-2A9Ym.

理论部分

APPNP (Approximation Personalized Propagation of Neural Prediction)被应用在引文网络的节点分类任务中。在节点分类中,一般的网络方法对领域节点的考虑是不足的。APPNP利用图卷积神经网络与个性化页面排序结合, 利用PageRank传播的方式构建一种简单的模型,来进行邻域节点信息更好的传播。PageRank 算法通过网页链接重要性得分计算。重要性可认为是网页链接点击。PageRank算法给定一个概率值,定义为网页访问的概率。一般地, 1 N \frac{1}{N} N1 表示为每个网页节点初始化的概率, P R {\rm{PR}} PR也是一个初始化的概率值。PageRank 是一个迭代算法,因此 P R {\rm{PR}} PR 值初始化为 1 N \frac{1}{N} N1 N N N表示为节点的数量。 P R {\rm{PR}} PR值的总和一般为1,当 P R {\rm{PR}} PR越大,说明重要性越大。
给定节点 v v v,求节点 v v v P R {\rm{PR}} PR值,
P R ( v ) = ∑ u ∈ N v P R ( u ) O ( u ) {\rm{PR(}}v{\rm{) = }}\sum\limits_{u \in {{\mathcal N}_v}} {\frac{{{\rm{PR(}}u{\rm{)}}}}{{O(u)}}} PR(v)=uNvO(u)PR(u)
N v {{\mathcal N}_v} Nv表示所有链接到节点 v v v的集合。 O ( u ) O(u) O(u)表示节点 u u u的对外链接数。最早提出的PageRank算法存在着一些缺点,例如当一些节点存在自链接,或者是一些节点的出链节点形成循环圈时,PageRank在迭代过程中会出现 P R {\rm{PR}} PR 持续增大,不会减小的情况。对于上述问题,PageRank算法被重新进行改进。
P R ( v ) = α ∑ u ∈ N v P R ( u ) O ( u ) + ( 1 − α ) N {\rm{PR(}}v{\rm{) = }}\alpha \sum\limits_{u \in {{\mathcal N}_v}} {\frac{{{\rm{PR(}}u{\rm{)}}}}{{O(u)}}} + \frac{{(1 - \alpha )}}{N} PR(v)=αuNvO(u)PR(u)+N(1α)
α \alpha α是一个超参数,取值一般为0.85。 α \alpha α表示节点跳转时的概率,不依据节点之间的链接进行跳转。
PageRank算法衍生出的模型个性化的PageRank算法,主要利用图中节点的链接关系来迭代计算节点的权重。PageRank算法使用随机游走的策略来访问图中节点。PageRank算法与个性化Page Rank算法的区别在于随机游走时的跳转行为不同。个性化的PageRank算法对跳转行为进行约束,指定调转到的对外链接为特定的节点。例如在个性化排序时,用户只能跳转到一些特定的节点,这些节点表示用户偏好的那些节点。
P P R ′ ( v ) = α ∑ u ∈ N v P R ( u ) O ( u ) + ( 1 − α ) r v {\rm{PP}}{{\rm{R}}^{'}}{\rm{(}}v{\rm{) = }}\alpha \sum\limits_{u \in {{\mathcal N}_v}} {\frac{{{\rm{PR(}}u{\rm{)}}}}{{O(u)}}} + (1 - \alpha )r_v PPR(v)=αuNvO(u)PR(u)+(1α)rv
其中,
r v = { 1 v = u 0 v ≠ u {r_v} = \left\{ {\begin{matrix}{{}} 1&{v = u}\\ 0&{v \ne u} \end{matrix}} \right. rv={10v=uv=u
个性化PageRank算法中,用户的偏好表示为 ∣ r v ∣ = 1 |r_v| = 1 rv=1。原始的PageRank采用的计算方式为 ρ p r = A r w ρ p r {{\boldsymbol{\rho }}_{{\rm{pr}}}} = {{\bf{A}}_{{\rm{rw}}}}{{\boldsymbol{\rho }}_{{\rm{pr}}}} ρpr=Arwρpr ρ p r {{\boldsymbol{\rho }}_{{\rm{pr}}}} ρpr A r w {{\bf{A}}_{{\rm{rw}}}} Arw的特征向量, A r w = A D − 1 {{\bf{A}}_{{\rm{rw}}}} = {\bf{A}}{{\bf{D}}^{ - 1}} Arw=AD1,类似的,个性化的PageRank 算法可以表示为
ρ p p r ( x v ) = ( 1 − α ) A ~ ρ p p r ( x v ) + α x v {{\boldsymbol{\rho }}_{{\rm{ppr}}}}({{\bf{x}}_{\bf{v}}}) = (1 - \alpha ){\bf{\tilde A}}{{\boldsymbol{\rho }}_{{\rm{ppr}}}}({{\bf{x}}_{\bf{v}}}) + \alpha {{\bf{x}}_{\bf{v}}} ρppr(xv)=(1α)A~ρppr(xv)+αxv
对上式进行重新表示,得到
ρ p p r ( x v ) = α ( I − ( 1 − α ) A ~ ) − 1 x v {{\boldsymbol{\rho }}_{{\rm{ppr}}}}({{\bf{x}}_{\bf{v}}}) = \alpha {({\bf{I}} - (1 - \alpha ){\bf{\tilde A}})^{ - 1}}{{\bf{x}}_{\bf{v}}} ρppr(xv)=α(I(1α)A~)1xv
x v {{\bf{x}}_{\bf{v}}} xv表示的是节点 v v v对应的传送向量。
PPNP模型的输出结果可表示为 Z P P N P {{\bf{Z}}_{{\rm{PPNP}}}} ZPPNP
Z P P N P = s o f t m a x ( α ( I − ( 1 − α ) A ~ ) − 1 f w ( X ) ) {{\bf{Z}}_{{\rm{PPNP}}}}{\rm{ = softmax(}}\alpha {({\bf{I}} - (1 - \alpha ){\bf{\tilde A}})^{ - 1}}{f_w}{\rm{(}}{\bf{X}}{\rm{))}} ZPPNP=softmax(α(I(1α)A~)1fw(X))

f w ( X ) {f_w}{\rm{(}}{\bf{X}}{\rm{)}} fw(X)表示的是一个关于参数学习权重 w w w的神经网络。 A ~ = D ^ − 1 2 A ^ D ^ − 1 2 {\bf{\tilde A}} = {{\bf{\hat D}}^{^{ - \frac{1}{2}}}}{\bf{\hat A}}{{\bf{\hat D}}^{^{ - \frac{1}{2}}}} A~=D^21A^D^21 A ^ = A + I {\bf{\hat A}} = {\bf{A}} + {\bf{I}} A^=A+I。为加快PPNP的网络模型训练速度,因此APPNP在PPNP的基础上近似求逆的操作。被表示为:
Z A P P N P ( 0 ) = f w ( X ) {\bf{Z}}_{{\rm{APPNP}}}^{(0)}{\rm{ = }}{f_w}{\rm{(}}{\bf{X}}{\rm{)}} ZAPPNP(0)=fw(X)

Z A P P N P k + 1 = ( 1 − α ) A ~ Z A P P N P k + α f w ( X ) {\bf{Z}}_{{\rm{APPNP}}}^{k + 1}{\rm{ = (1 - }}\alpha {\rm{)}}{\bf{\tilde AZ}}_{{\rm{APPNP}}}^k + \alpha {f_w}{\rm{(}}{\bf{X}}{\rm{)}} ZAPPNPk+1=(1α)A~ZAPPNPk+αfw(X)

Z A P P N P K = s o f t m a x ( ( 1 − α ) A ~ Z A P P N P K − 1 + α f w ( X ) ) {\bf{Z}}_{{\rm{APPNP}}}^K{\rm{ = softmax}}({\rm{(1 - }}\alpha {\rm{)}}{\bf{\tilde AZ}}_{{\rm{APPNP}}}^{K - 1} + \alpha {f_w}{\rm{(}}{\bf{X}}{\rm{))}} ZAPPNPK=softmax((1α)A~ZAPPNPK1+αfw(X))

通过上述公式,矩阵的求逆操作被进行近似。在APPNP迭代到最后两步时,进行归一化操作。 k ∈ K k \in K kK K K K 表示迭代的次数。
个性化的页面排序算法加入 α \alpha α,表示节点跳转时依据一定的概率,使页面排序算法具有个性化。
APPNP算法利用图卷积神经网络与页面排序算法结合的方式,提出一种个性化页面排序算法解决图神经网络节点分类问题的模型。相比于一些基线模型,APPNP算法没有引入任何的参数量,但APPNP的算法收敛速度较慢。APPNP算法将个性化页面排序算法与图卷积神经网络结合,图卷积神经网络可以被替换为图注意力网络等。

理论部分注意事项

π p r = A r w π p r {{\boldsymbol{\pi}}_{{\rm{pr}}}} = {{\bf{A}}_{{\rm{rw}}}}{{\boldsymbol{\pi }}_{{\rm{pr}}}} πpr=Arwπpr
π p r {{\boldsymbol{\pi}}_{{\rm{pr}}}} πpr应该是 A r w {{\bf{A}}_{{\rm{rw}}}} Arw的特征向量。参考链接来自:

https://codeantenna.com/a/TmBbfN2SV1

相关资料

https://blog.csdn.net/fnoi2014xtx/article/details/107567629

数据

https://github.com/shchur/gnn-benchmark/tree/master/data

代码

https://github.com/benedekrozemberczki/APPNP

你可能感兴趣的