ICDE20一篇高效计算SimRank相似度的论文
这里我直接把组会分享的PPT和讲稿放上来了。
讲稿
大家好，今天我要讲的是ICDE2020年的一篇论文，“一种在静态和时序图上高效计算SimRank相似度的算法”。第一眼看到这个题目会想，首先什么是SimRank相似度，然后为什么它的计算是低效的，以及论文怎么进行高效计算。按照这个逻辑，首先介绍一下SimRank相似度，它是应用于图上的一种相似度计算方法，基本思想是，关联到相同顶点的两个顶点，相互之间具有相似性。以下面这个图片为例，两位教授相似度高因为他们来自同一所大学，而两位学生的相似度要相对低一些，在于他们并不直接来自于同一位教授。SimRank相似度原始的计算方式如下，它是一个迭代的过程。要计算顶点u和v的相似度，我们需要找到它们各自邻域中所有的顶点x和y，进行求和。前面的系数是为了避免热门顶点的影响而做的惩罚。因为是迭代计算，当图中顶点数量较多的时候计算就会变得低效。而VLDB17年的一篇论文证明了可以通过随机漫步近似计算SimRank相似度，这就为高效计算带来了新的思路。从随机漫步的角度来看，顶点u和v之间的SimRank相似度，可以看作从这两个顶点出发的随机漫步序列相交的概率。这个随机漫步的定义如下，以\sqrt{c}的概率漫步到下一个邻居，1-\sqrt{c}的概率终止于当前顶点。随机漫步可以看成是一种采样的方法，在图上的应用比较广泛，包括用来生成顶点的embedding如node2vec，或者在一个大图中构建子图捕获局部信息如GraphSAGE。既然是一个采样的方法，那么采样多少来保证获取到必要的信息就是一个关键的参数。同样地，在通过随机漫步近似计算SimRank相似度时，单次漫步的长度以及漫步的次数怎么选取，才能保证近似值与实际值之间的误差小于某个界限。论文的一个主要贡献就是给出了这两个参数的选取以及证明了它们的有效性。我对证明过程的每一步作了注解放在了ppt里，这里就不详细展开。主要是通过几何分布以及正态分布的3σ原则来证明。回到刚刚的式子，有了两个序列W(u)和W(v)，这时只剩下最后一步也就是怎么计算这里的概率。最直观的办法是通过蒙特卡洛模拟，给定一对查询顶点u和v，我们总共做n次随机漫步，用其中相遇的次数所占的比例作为概率的一个近似，然而这需要进行大量的尝试，直观但效率低。论文的改进做法是，与其去判断从u和v出发的随机漫步是否会相交，不如直接判断顶点v能否到达顶点u随机漫步的范围内。因为在静态图上固定了随机漫步的长度后，一个顶点能够漫步到的范围就是固定的，因此只需要在迭代之前计算一遍即可，不需要迭代时一次次地去计算。以左边的图为例，取漫步的长度$l_{max}=4$，在这个图中顶点A能够漫步到的范围就能用右边这颗树表示。因为随机漫步就是由概率决定是停止还是继续，所以只要将右边这棵树上的边用概率表示就可以进行近似计算。论文中给出的一个表示是下面这个式子，含义是这棵树每层之间边的一个关系。在实际编程实现时用的是一个二维矩阵$U\in \mathbb{R}^{l_{max}\times |\Omega|}$来表示这棵树，为什么这样的一个关系能够保证近似计算的有效性的证明我也放在了这里，同样不展开来讲了。单看表达式比较抽象，我就继续以刚才的例子说明这个计算过程，取参数$c=0.25$，初始时因为只能停留在起点A处，所以设这个概率值为1，$U(0,A)$表示以0步漫步到顶点A的概率。而一步能够漫步到的范围包括B、C两个顶点，以B为例，它的入度邻居数目为2，对应着上面的公式计算出它的概率值。所以漫步到顶点B的概率由先到顶点A的概率决定，这也符合随机漫步的定义。接下来以此类推。对于顶点A能够到达的顶点，它们在矩阵里对应位置的值都不为0。得到这么一个U矩阵后，迭代时不断地产生顶点v的随机漫步序列W(v)，根据这里的式子来近似计算SimRank相似度，直观上的理解是W(v)这个序列多大程度上走进了顶点u的这个漫步范围。还是刚才的例子，假设我们想得到顶点A和C之间的SimRank相似度，而某次迭代时顶点C产生的一条序列为$W(C)=(C,D,B,A)$，我们查阅刚刚得到的U矩阵中对应元素的值，进行累加，多次迭代后就得到了近似计算结果。回顾一下整个算法的流程，输入是单个顶点u和一系列顶点v，我们希望知道u和这些v之间的SimRank相似度大小。首先设定两个参数的取值，接下来在迭代前先预先计算顶点u的U矩阵，矩阵中的元素表示它漫步到某个顶点的概率。迭代过程中从顶点v产生一条随机漫步序列，通过U矩阵计算这条序列与u相遇的概率，多次取平均作为结果。到这里论文就完成了静态图部分的工作，接下来就是怎么将提出的方法继续用在时序图上。一个时序图通常由一系列快照图组成，每个快照图捕获了某个时间段内顶点之间的状态，图中就是一个包含三个快照图的时序图。联系现实可以拿微博举例子，假设我是顶点H，第一周关注了用户F，第二周取关了他，第三周用户G又新关注用户F。实际中因为用户的兴趣更新频率很快，所以时序图更能表达这种动态变化的兴趣。在时序图的情景下，最常见的两种SimRank查询分别为趋势查询和阈值查询。趋势查询的含义是，在给定的时间区间内，对于顶点u，我们希望找到一系列顶点v，它们与u的SimRank相似度在这个区间内是递增或递减的。而阈值查询是指在给定的时间区间内，它们与u的SimRank相似度大于某个阈值。因为时序图的每个快照图都可以看成静态图，最直观的想法就是把刚才的方法在每个快照图上算一遍，但这样只是照搬静态图的做法，没有用上时序图的特点，所以论文的后半部分针对时序图的特点提出了两个减少计算量的策略，分别是delta剪枝和差异剪枝，它们的思想也很直观，希望只对时序图中产生变化的顶点重新进行计算。回到刚才的例子图，会发现这三张快照图变的只是蓝框部分，红框部分一直维持不变。所以红框内的部分没必要每次都进行计算。具体到delta剪枝，一条新增或删除的边x->y影响的区域定义为下面两个部分，第一部分的意思是，如果顶点u能去的范围因为新增的边变大了，对应的这棵树也会改变。而第二部分的意思是，对于顶点y能到达的最远顶点$y_{lmax}$，反过来看顶点x刚好在它漫步范围之外，所以它在前后两个快照图里是不受影响的，涉及它的SimRank计算就可以省去。根据这个观察，delta剪枝的做法就是满足该前提的条件下，避免重计算未受影响区域的顶点。论证在下面主要从时间复杂度来说明，这里就省去了。而差异剪枝的想法要简单一些，因为近似计算依靠的就是随机漫步，如果前后两张快照图里漫步的范围没变，那计算结果也不会发生改变。所以差异剪枝的做法就是只要顶点u和v漫步范围不变，它们之间就不需要进行重计算。论证同样是通过复杂度说明。这两个策略具体放在流程里体现为图里的红框和蓝框，主要是判断是否达到对应的条件，然后删去不需要重计算的顶点来减少计算量。最后是实验部分，数据集和baseline的描述如下，结果主要是准确率和效率两方面，纵轴的ME表示近似值与真实值的最大误差，五个数据集上论文的方法都是又快又准，在时序图实验上也是一样。总结来说，论文的贡献是给出了一种高效计算SimRank相似度的方法并且证明了它的有效性，并且针对时序图的情景提出了两个优化策略。因为论文涉及比较多的证明和细节，看完可能不太明白这么计算的意义。图在许多领域应用广泛，而SimRank相似度既然是一种相似度，那它就可以应用在推荐系统、社交网络等一系列任务上，同时这些场景下往往有大量的用户，高效计算就有了实际的应用背景。不过这里也是我对论文有疑问的一个地方，因为实验用到的数据集都很小，最多的顶点也才三万多个，时序图也是以天为单位，而在现实生活中可能用户兴趣可能几个小时就发生改变了，例如微博热搜。而且即使在这么一个数据集上，论文的方法也要耗费75分钟的时间进行计算，感觉并不是很高效。
PPT
