高效计算Personalized PageRank小综述

本学期最后一次组会我做了这两三年近似计算Personalized PageRank(PPR)的小综述,包含理论及图神经网络上的应用。

这里我直接把组会分享的PPT和讲稿放上来了。

讲稿

大家好,今天我在组会本来要分享ICDE20年一篇高效计算个性化PageRank的论文,但因为论文涉及过多方法上的细节而大家都不是PageRank近似计算的研究方向,所以我想转为介绍一下近几年顶会上对近似计算个性化 pagerank这个问题是怎么做的以及有哪些应用场景,涉及下面这些论文,其中前面四篇为理论而后面两篇是在GNN上的应用。

首先再简单回顾一下个性化PageRank。个性化PageRank简称PPR,它来自于Google创始人于1998年提出的PageRank。PageRank用于度量web网络中各网页的重要性,它的核心思想有两点:被很多网页所链接的网页重要性较高;被重要的网页所链接的网页重要性较高。原始的PageRank的计算方式是一个迭代的过程。$\pi$是n维的PageRank向量,每一维对应一个顶点的PageRank分数,下面的例子是说明PageRank的计算过程以及式子中两部分的由来,之前介绍过这里就不重复了。因为PageRank 相当于站在全局视角评价所有节点的重要程度,必须遍历所有网络上的节点,实际中很难做到,而且为了更个性化的评价,就有了PPR。它是PageRank的一种特殊形式,用于衡量图上顶点关于某一顶点的相对重要性,两者之间的关系为下面的式子。一个是相对重要性一个是全局重要性。

因为PPR的计算复杂度较高,所以有一些对它的近似估计方法,主要是下面这三种,它们作为后面要介绍的几篇论文的基本方法,这里大致地介绍一下。首先是蒙特卡洛模拟。它作为一种采样的方法,是通过以随机游走的概率来估计PPR值,至于为什么可以这样来估计,主要来自PPR的另一个定义,即两点之间的PPR值等价于从起始顶点出发的随机游走终止于目标顶点的概率。从大数定律知道,次数足够多时频率可以近似于概率,蒙特卡洛的做法就是进行若干次随机游走,将其中终止于目标顶点的比例作为PPR的近似值。做法很简单,关键在于随机游走的次数怎么选取来保证近似的精度。这里直接给出结论,证明过程要用到切尔诺夫界限,这里不展开了。

下一个是Forward Push,它为每个顶点维护两个变量,残差值和$\pi$值。在每轮迭代时,对于满足条件的顶点,首先将出度邻居的残差值增加一定比例,随后增加自己的$\pi$值并将残差值置零。直到所有顶点都不满足条件时迭代中止,将$\pi$值作为近似的PPR值。有前向类似地就有后向,做法基本一致,区别在于后向考虑的是入度邻居。两个方法的联系在于,前向的输入是源顶点s,考虑的是出度邻居;而后向的输入是目标顶点t,考虑的是入度邻居。

从刚刚的介绍可以看到,蒙特卡洛准确但效率低,因为需要大量的随机游走;Forward Push效率高但无法保证准确度。因此有学者将两者结合起来,就有了KDD17年的这篇论文FORA。Forward Push之所以无法保证准确度,是因为它返回的近似值与真实值之间本来就不保证接近,这篇论文找到了两者之间的一个联系,通过新加的尾项来建立两个值之间的关系。因为新加的尾项中$\pi(v,t)$同样是未知的,所以论文通过随机游走的办法来近似得到这个值,这就是蒙特卡洛的部分。那既然是通过随机游走来进行近似,具体要游走多少次来保证近似的精度,以及在Forward Push中的终止条件怎么确定就是两个关键的问题。这两个参数的选取都涉及证明这里就略过了。看论文的算法流程图,就是分为两个部分。Forward Push得到一个近似值,再通过蒙特卡洛提高近似值的精度。蒙特卡洛部分,蓝色下划线都是参数的取值,关键在于蓝色框内这个增量的操作。刚才说到论文通过新添加了一个尾项来建立Forward Push近似值与真实值之间的联系,而这里算法中+=这部分增量的期望是等于这个尾项的。

到这里对KDD17年这篇论文的介绍就结束了,接下来是本来组会要分享的ICDE20年的这篇论文,它主要是针对上一篇中的一些不足进行了改进,整体的算法流程没有改变。提出的第一个改进是所谓的“残差累积”,目的是为了减少Forward Push中每个顶点的转移次数。拿图中的这个简单图为例子,对于每个节点的残差值,Forward Push中涉及的操作只有两个,就是图中用红框圈出来的部分。将一部分转移给出度邻居之后置零。以顶点v1为源顶点,初始时只有v1的残差值为1。因为它的出度邻居是v2和v3,所以第一步的时候把自己的残差值转移了一部分给v2和v3,随后置零。所以这里矩阵的第一行只有v2和v3的值非零。下一步到v2,同样地把残差值转移给唯一的出度邻居v4并置零,所以第二行只有v3和v4的值非零,以此类推,可以得到矩阵每一行的值。在这个过程中,会发现顶点v2的残差值转移了两次,v1转移给它后它转给了v4,v3转移给它后它也转给了v4,这篇论文就认为这种单个顶点重复的转移是冗余的,实际上可以v1和v3都转移给v2后v2再一次性转移给v4,也就是右下角这个矩阵,这时候得到相同的结果只需要三步就可以了,虽然相对于原来的做法只减少了一步,但如果在大图上节省的操作次数是比较可观的。这种不断累积最后一次性转移出去的操作就是论文提出的第一个改进“残差累积”。

第二个改进是针对图中有自环的情况,拿图中的简单图为例,在顶点s处有一个自环,如果是原始的Forward Push,残差值会沿着s->v1->v2->s这样不断循环下去,直到某个节点的残差值不满足转移条件才会终止。论文给出的解决方法是在顶点s第一次转移后,就只接受其他顶点转移过来的残差值进行累积,不再把自己的残差值转移出去,这样就切断了自环的循环。但是对于一个大图来讲,要让除了顶点s外的其他顶点都转移完是非常耗时间的,所以论文提出在s的一个子图上完成这个残差累积的过程。这个过程结束后,子图中其他顶点的残差值和$\pi$值能够通过顶点s的残差值直接计算得到,不需要再重复进行转移的操作。之所以能这么做是因为论文证明了不管是否进行残差累积,顶点s涉及的转移操作都是一样的,区别只在于转移的残差值是多少,而这个残差值在两种操作间有种比例关系,根据这个比例关系和顶点s累积后的残差值就能直接计算出来。这部分在论文中涉及的定理引理和证明比较多,我就不在这里介绍了,论文是为了说明这种残差累积能够切断自环情况的同时还能保证结果的准确。因为按照论文对子图的定义,子图外的顶点即使满足转移条件也是不能进行残差值的转移的,所以还有额外的一步是扫描子图外的顶点进行残差值转移的操作。我们看论文的算法流程图会发现,也是可以分为两个部分,Forward Push和蒙特卡洛,只是Forward Push在上一篇的基础上进行了两点改进。
刚刚介绍的这两篇都是围绕Forward Push+蒙特卡洛展开,那有没有办法将另外一个基本方法也考虑进来?SIGMOD18年的这篇论文就是结合了这三者,来解决topk PPR查询问题。结合的动机是通过Backward Search进一步提升蒙特卡洛的精度。把前向和后向两个方法的表达式放在一起,把后向的表达式直接带入前向的尾项中,就是对应标红的部分,就得到了这篇论文的一个表达式。在第三项中的真实值$\pi(u,v)$同样是未知的,这时候通过蒙特卡洛来近似这个值,所以就完成了对三个基本方法的结合。前面针对的的问题都是点对点的PPR查询,给定两个顶点s和t,希望知道它们之间的PPR值。实际应用中我们可能更想知道,对于一个顶点s来说,topk PPR的顶点是哪些,典型的应用就是社交网络上的好友推荐,希望找到和用户相关的好友,而不是查询用户和某个好友之间的亲密程度。对于topk PPR查询问题,最直观的想法就是做一次全图PPR查询之后排序取topk,但这么做显然复杂度很高。类似地,求解topk查询也是希望在较快的时间内给出一个精度较高的近似解,按照定义需要满足topk中的近似值与真实值之间的误差也小于某个界限,但界限中的PPR真实值是预先不知道的,就无法确定topk PPR的一个大概范围。回到刚才KDD17年的那篇论文,它对于topk问题给出的解决方案是试错然后调整。首先假设真实值是一个较大的值进行查询,如果查询结果不如假设的大,将假设值调低进行下一次迭代,直到查询结果满足要求。在算法流程图里这个试错的过程体现在第一个红框,将$\delta$的值从1/2一直设到1/n。在候选集C有了k个顶点后,为每个顶点计算一个上限和下限来判断近似的精度是否满足要求,判断条件是图中的两个红色下划线部分,如果两个条件均满足则返回当前结果作为topk查询的结果。上下限的定义及判断条件的构造也是涉及一些定理和证明,这里同样就略去了。回到SIGMOD18年的这篇论文,它的做法也是类似的,维护一个候选集C,为候选集C中的顶点计算一个界限,如果界限满足某个条件则把候选集C中的节点移入结果集Vk中,直到结果集中的数量满足要求。这个界限和判断条件也是涉及定理和证明这里一样略去了。对于候选集来说,里面的顶点大致可以分为三类,确定为topk的顶点,位于topk边界的顶点以及不可能为topk的顶点,对于第二类边界的顶点希望进行更深的Backward Search来得到更精确的一个近似值,做进一步的判断。

实验部分的话因为几种方法都有理论上证明近似的精确度,所以这里只放了效率之间的比较,最快的方法是ICDE2020年的ResAcc,其次是SIGMOD18的TopPPR以及KDD17的FORA。到这里就介绍完了所有的理论部分,最后介绍两篇将PPR应用于图神经网络上的论文,ICLR19年的这篇论文是最早将PPR引入GNN来解决GNN层数无法加深的问题,从最开始的介绍我们知道了PPR的原始定义式,一个迭代求解的过程,它的解可以表示为下面第二个式子,这篇论文就是将求解得到的PPR矩阵作为GNN中信息传递的模式,同时将预测和传递分离开来,解决传统GNN层数无法加深的问题。那么导致GNN无法加深的一个原因是所谓的过平滑现象,就是随着层数的加深,不同顶点经过网络学习得到的特征表示会趋于相同,导致顶点间没有区分度。拿下面的图为例,从左到右从上到下是网络层数加深后顶点特征表示的可视化结果,可以看到在六层的时候顶点几乎都已经混在了一起,远没有二三层时表现来的好。

导致这种过平滑现象的原因ICML18年的一篇论文从随机游走的角度给出了解释。一个K层的GNN相当于从源顶点出发到目标顶点的一个K步的随机游走,当K趋向于无穷即层数不断加深时, 顶点的极限分布与初始的顶点表示无关,只与图的结构相关。也就是说,随着层数加深聚合的信息越多,反而得到的表示与中心顶点无关。所以ICLR19年这篇论文引入PPR就是引入其中的重启概率$\alpha$,每一步时会以一定的概率重新回到初始顶点,这样来保证层数加深后与中心顶点间依然有联系。而且与GCN的表达式比较,这篇论文的表达式与层数l无关。最后是KDD20年的PPRGo,从表达式来看做法几乎和上一篇是一样的,不同之处在于这里用到的PPR矩阵是一个近似值,而且对每一行取了topk来控制信息传递时的规模。

PPT

RfWGee.png
RfW1sO.png
RfW3LD.png
RfW0Qf.png
RfWlQK.png
RfWNFA.png
RfWaWt.png
RfWYod.png
RfWUJI.png
RfWwSP.png
RfWBy8.png
RfWDOS.png
RfWseg.png
RfWywQ.png
RfWgFs.png
RfW6oj.png
RfW2Yn.png
RfWhlV.png
RfWRWq.png
RfW4yT.png
RfWfS0.png
RfW5OU.png
RfWomF.png
RfWTw4.png
RfW7TJ.png
RfWbk9.png
RfWqYR.png
RfWLf1.png
RfWXSx.png
RfWjl6.png
RffSmD.png
RfWv6K.png
RfWxOO.png
Rffp0e.png
Rff9TH.png
RffPkd.png
RffitA.png
RffFfI.png
RffApt.png
RffE1P.png
RffV6f.png
RffZX8.png
RffmnS.png
Rffu7Q.png
Rffn0g.png
RffMkj.png
RffQts.png

RfqIoV.png
Rfq7JU.png
RfqTiT.png
Rfqbz4.png
RfqHWF.png
RfqLQJ.png
RfqOy9.png
RfqXLR.png
Rfqve1.png
Rfqxdx.png
Rfqzo6.png
RfLCWD.png
RfLpFK.png
RfL9JO.png

参考