Personalized PageRank to a Target Node, Revisited[KDD'20]

KDD20一篇近似计算单目标PPR相似度的论文

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

讲稿

今天我要讲的是KDD20年的一篇论文,解决的是针对目标顶点的个性化PageRank查询。个性化PageRank简称PPR,它来自于Google创始人于1998年提出的PageRank。PageRank用于度量web网络中各网页的重要性,它的核心思想有两点:被很多网页所链接的网页重要性较高;被重要的网页所链接的网页重要性较高。如果将web网络转化为图结构G(V,E),网页看作顶点,网页间的链接看作边,则PageRank的计算方式为下面的式子,$\pi$是PPR向量有n维,每一维对应一个顶点的PageRank分数,是一个迭代的计算过程。

它可以用于衡量各顶点的全局重要性,举个例子说明这个式子的含义,有A、B、C、D四个网页,假设一个上网的人在网页A,那他会以1/3的概率跳到B、C和D,访问一个网页的概率由链接到它的所有网页的概率来决定,例如A由B、C两个网页链接,就有第一个式子。各个网页间的转移可以用一个概率转移矩阵表示,初始时上网的人在每个网页停留的概率是相等的,右乘上转移矩阵后就得到了下一时刻对每个网页的访问概率。然后不断迭代直到收敛。实际上,如果存在一个网页只链接到自己,例如图里的C,那就会像一个陷阱一样,导致概率分布值全部转移到网页C上来,所以PageRank另一部分就是以一定的概率跳转到一个随机的网页,来避免这种问题。

而PPR是PageRank的一种特殊形式,它用于衡量图上顶点关于某一顶点的相对重要性,两者之间的关系为下面的式子。一个是相对重要性一个是全局重要性。这篇论文重点关注是单目标PPR的计算问题,即给定图上某一顶点t作为目标顶点,计算图上所有顶点关于t的PPR值,它希望找到使得目标顶点t重要性较高的一系列顶点。有别于我们传统上理解的单源PPR的计算问题,后者是希望找到相对源顶点较为重要的一系列顶点。

论文做的是一个近似求解,满足一定的误差要求来提升计算的效率。近似的方法是从PPR的另一个定义方式出发,即从源顶点出发的随机游走停止在目标顶点的概率。进一步地分解,就是以0步、1步到无穷步停止的概率进行求和,近似的做法就是进行一个截断,上限不需要是无穷,截断后满足误差小于给定极限即可。单目标PPR的计算问题相关研究较少,目前时间复杂度上最优的方法是Backward Search,为$O(\frac{\overline{d}}{\delta})$,

这篇论文的贡献就是在它的基础上引入随机性,使得复杂度降为$O(\frac{1}{\delta})$。这里先介绍Backward Search的做法,然后指出论文具体在哪几个步骤做了改动。Backward Search的做法是,给定一个目标顶点t,算法对图上的每个顶点u都维护两个变量residue和reserve,我这里简称为r值和$\pi$值,每次选取当前r值最大的顶点v,更新自己的$\pi$值,再将r值以一定比例push给所有的入度邻居并置零。最后每个顶点的$\pi$值就作为PPR值的近似计算结果。因为在push操作时需要遍历所有的入度邻居,所以复杂度上会带有一个$\overline{d}$,表示图中所有顶点的平均出度。

所以论文在push这一步做了改动,提出了自己的方法RBS。它不会push给所有的入度邻居,而是只push增长值超过阈值的部分。之所以这么做,是因为Backward Search里的增长值与入度邻居u的出度成反比,对于出度较大的这部分入邻居,这次push操作对它的\pi值改变不大,即使进行了本次push,它\pi值的变化幅度也小于误差要求,所以放弃对它的push操作以节省时间。

在RBS算法里,push操作有三种情况,当出度满足要求时才确定进行push操作,如果不满足条件,产生一个0、1之间的随机数,如果出度满足小于放宽后的要求,则push一个固定值,否则不进行本次push。这样,对于每个需要push操作的入度邻居,只确定地更新了一部分并且采样了一部分进行更新以保证结果的无偏。

在实际实现时不能遍历每个入度邻居u来判断它是否满足要求,这样同样会带来$\overline{d}$的复杂度,因为push操作的条件是逐渐递减的,只需要预先对所有的入度邻居按照出度进行排序,逐个扫描到临界条件后就可以放弃查看剩下的所有邻居,因为都不会满足条件。最后是实验部分,选用的几个图数据集描述如下,有无向图也有有向图,有小图也有大图,评测指标一个是最大计算误差,另外两个是推荐常用指标。

实验结果上,因为是基于Backward Search提出的,baseline只选了这一个。图中的横轴都是查询时间,纵轴分别是各个评测指标,结果上来说就是花费同等的时间,新的方法可以达到更好的结果,达到相同的结果新的方法只需要更少的时间。

论文所研究的单目标PPR计算虽然相对冷门,但实际应用可以结合许多问题,第一个相当于是该问题下的一个特例,对顶点的重要性有更高的要求,其次在图神经网络上也有利用PPR矩阵进行改进的工作,例如ICLR19年的这个方法。

最后想重点说一下的是与SimRank相似度的关系,因为前一篇讨论班论文我讲的就是ICDE20年一篇如何高效计算SimRank相似度的论文,里面提到SimRank相似度可以看成两条分别从源顶点和目标顶点出发的随机游走,以相同的步数相遇于同一个顶点的概率,因为定义上有相似之处,可以结合PPR来计算顶点u或v到这一系列顶点w的概率。

总结来说,这篇论文的贡献是在BackWard Search的基础上引进随机化来降低时间复杂度并且保证了理论上的近似精度,并且给出了数学证明说明做法的有效性。

PPT

cjNkPH.png
cjNERA.png
cjNiIe.png
cjNVxI.png
cjNAGd.png
cjNeMt.png
cjNmsP.png
cjNnqf.png
cjNKZ8.png
cjNMdS.png
cjNQIg.png
cjN3Gj.png
cjN1iQ.png
cjNGzn.png
cjN8Rs.png
cjNNLV.png
cjNYMq.png
cjNts0.png
cjNaZT.png
cjNwoF.png
cjNddU.png
cjNszR.png
cjNBi4.png
cjNDJJ.png
cjNrW9.png