“演化与静态图上的快速准确CoSimRank搜索”

5990在演化和静态图上的快速准确CoSimRank搜索0Weiren Yu AstonUniversity Birmingham, B47ET, UKw.yu3@aston.ac.uk0Fan Wang AstonUniversity Birmingham, B47ET, UKwangf7@aston.ac.uk0摘要0在实际的Web应用中，CoSimRank被提出作为一种基于图拓扑的节点对相似性度量。然而，现有的CoSimRank工作仅限于静态图。当图随时间更新并出现新的边时，重新计算所有CoSimRank分数的开销很大，这是不切实际的。在本研究中，我们提出了一种快速动态方案D-CoSim，用于准确计算演化图上的CoSimRank搜索。基于D-CoSim，我们还提出了一种快速方案F-CoSim，大大加速了静态图上的CoSimRank搜索。我们的理论分析表明，D-CoSim和F-CoSim保证了CoSimRank分数的准确性。在静态图G上，为了高效检索CoSimRank分数S，F-CoSim基于三个思想：（i）首先在G上找到一个“跨度多叉树”T；（ii）在T上，设计了一种快速算法来计算“跨度多叉树”T上的CoSimRank分数S(T)；（iii）在G上，使用D-CoSim来计算S(T)对增量图(G�T)的变化。实验评估验证了D-CoSim在演化图上的优越性，以及F-CoSim在大规模静态图上相对于竞争对手的快速加速，而不会丢失准确性。01 引言0图被广泛用于建模复杂对象（例如网页）及其关系（例如超链接）。Rothe和Schütze提出的CoSimRank是一种基于图拓扑的强大的对象对相似性度量。它递归地遵循SimRank的哲学：“如果两个节点的入邻居相似，则认为它们相似”。CoSimRank是一种节点对相似性度量，与仅对节点进行排名的PageRank不同。直观地说，节点a和b之间的CoSimRank分数s(a,b)聚合了从a和b开始的两个随机浏览者的所有会面时间，与SimRank[8]只计算它们的第一次会面时间不同。因此，CoSimRank在许多应用中已被证明比SimRank更准确和有效。应用1（同义词扩展）。同义词扩展是搜索引擎查询重写[2,5]和文本简化[4]中的有用工具，它替换了目标词语中的一个0本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861260句子中有一个更合适的词。CoSim-Rank度量被用来衡量基于直觉的单词相似性，即“两个同义词应该具有相似的词汇邻居”，其中节点是出现在维基百科中的名词、形容词和动词，边表示从解析维基百科中提取的句法配置类型（例如，形容词-名词、动词-宾语和名词-名词协调）。他们评估了单词（同义词）的CoSim-Rank相似性，其结果优于两个个性化PageRank向量的余弦相似度，以识别有效的同义词。应用2（词典提取）。从语料库中自动构建双语词典是自然语言处理中的重要任务。Rothe和Schütze应用CoSimRank进行词典提取，并将英语和德语文本语料库表示为两个图，其中节点表示单词，边表示单词之间的语法关系。他们的核心观点是，“英语图中的一个节点和德语图中的一个节点是相似的（即很可能是彼此的翻译），如果它们的相邻节点是相似的”。他们使用英语-德语“种子”词典初始化CoSimRank分数，该词典的条目对应已知的等效节点（单词）对。他们的方法产生比基于SimRank的方法[11,22]更可靠的相似性结果。尽管其有效性，现有的CoSimRank工作仅限于静态图。然而，当图随时间更新并出现新的边时，这种方法很难处理动态图上的快速响应，因为重新计算CoSimRank分数的开销很大。这突出了我们需要考虑快速准确的动态CoSimRank搜索问题的需求。0问题1（演化图上的动态CoSimRank）。给定：图G，边更新集合∆G到G，查询集Q = {q1, q2, ...}。检索：关于(G ⊕∆G)上的CoSimRank分数的变化，快速准确地。为了解决这个问题，我们提出了一种快速准确的动态方案D-CoSim，用于演化图上的CoSimRank搜索。此外，作为D-CoSim的一个重要应用，我们展示了我们的动态D-CoSim也适用于静态图，以实现大规模CoSimRank搜索的巨大加速。因此，基于D-CoSim，我们还设计了一种快速准确的静态方案F-CoSim，来解决以下问题：0问题2（大规模图上的静态CoSimRank）。给定：图G和查询集Q= {q1, q2,...}。检索：关于Q在G上的CoSimRank分数，快速准确地。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France6000为了加速静态图G上CoSimRank分数S的计算，(i)F-CoSim首先在G上找到一个“生成树”T；(ii)在“生成树”T上，我们设计了一种快速方法来计算T的CoSimRank分数S(T)；(iii) 在(G �T)上，我们使用D-CoSim来计算S(T)相对于增量图(G �T)的变化。基于这些思想，F-CoSim和D-CoSim具有以下显著特点：0•快速。F-CoSim和D-CoSim在静态和动态图上分别比已知最佳竞争对手快几个数量级，而且没有准确性损失。•动态。D-CoSim在演化图上快速准确地回答特定的CoSimRank搜索，无需从头重新计算CoSimRank分数。•准确。F-CoSim和D-CoSim在巨大加速的同时不会损失任何准确性。•可扩展。我们的方案只需要线性内存空间，在百万节点图上具有良好的可扩展性。0简而言之，动态D-CoSim和静态F-CoSim都可以更高效、更准确地处理基于SimRank的应用程序[6, 14, 21, 30]。02 相关工作0以前关于CoSimRank搜索的工作主要集中在静态图上。[18]的开创性研究提出了一种高效的本地算法，它通过两个个性化PageRank向量的点积之和来计算每个CoSimRank分数。在进行K次迭代后，对于具有n个节点和d个平均度的静态图，计算单对CoSimRank分数需要O(Kdn)的时间和O(dn)的内存。然而，当图稍微更新时，所有的CoSimRank分数都必须从头开始重新计算。最近，Yu和McCann[27]提出了一种优化技术，即CoSimMate，它利用重复平方存储来将迭代次数从K减少到�log2K�，以便检索所有对的CoSimRank分数，但这种方法需要额外的O(n2)内存来存储重复平方结果，在大规模图上是不切实际的。更糟糕的是，[27]的方法是静态图上的非局部算法，这意味着即使只想计算单对分数，也必须同时计算所有对的分数。关于动态更新，除了对动态图中SimRank的一些相对较少的工作[9, 13,20, 25,26]之外，没有关于CoSimRank的工作。然而，当扩展到CoSimRank时，这些工作将变得低效，原因如下：首先，两个最先进的研究[9,20]基于随机游走采样，其优化技术严重依赖于聚合两个随机冲浪者的“仅第一次相遇时间”来计算SimRank。如果应用于聚合两个随机游走的“所有相遇时间”来计算CoSimRank，他们的方法将变得缓慢，因为采样更多的两个合并随机游走的相遇路径的成本很高。其次，一些工作[13,25]设计了低秩分解方法来更新所有对的SimRank分数，导致需要O(n2)的内存来存储分解的矩阵，这是不切实际的。0符号描述0G给定（旧）图G∆G将图更新为（旧）图G n/n˜n旧/新图中的节点数m/˜m旧/新图中的边数deg−i节点i在（旧）图G中的入度C阻尼因子（0 < C < 1）K迭代次数A/ ˜A旧/新列归一化的邻接矩阵S/˜S旧/新SimRank矩阵In × n单位矩阵ei n ×1只在第i个条目中有1的单位向量XT矩阵X的转置X[i,:]矩阵X的第i行X[:,j]矩阵X的第j列X[i,j]矩阵X的（i，j）-th条目0表1：主要符号描述0在大型图上不可扩展。更糟糕的是，这些方法基于一个假设，即即使只有少数得分对需要更新，所有旧的SimRank得分对也应该提前给出，这在实践中是不现实的。关于静态图上的SimRank（CoSimRank的变体）也有大量的研究[6-8, 10, 13, 15, 16, 19, 23,29]。它们的优化技术可以分为三大类：蒙特卡洛采样[6, 10, 19,23]，基于矩阵的方法[7, 13]和迭代方案[8, 15,29]。其中，采样方法SLING [23]是静态图上最好的SimRank算法。然而，如果将这些技术应用于CoSimRank，它们的速度不如SLING快，因为SLING的性能提升仅依赖于聚合两个合并行走的第一次相遇时间，而不是像CoSimRank那样聚合它们的所有相遇时间。还有很多关于计算增量个性化PageRank（PPR）向量[3]和动态重启随机游走（RWR）接近度[28]的工作。然而，直接将这些技术应用于动态CoSimRank更新是不高效的。这是因为第k次迭代的CoSimRank得分是每次迭代i = 1, 2, ...,k时两个个性化PageRank向量之间k个内积的和。因此，要更新第k次迭代的CoSimRank得分，现有的增量PPR（RWR）算法将会重复应用2k次，以更新每次迭代i = 1, 2, ...,k时的两个PPR（RWR）向量，然后再求和每两个PPR（RWR）向量在每次迭代时的k个点积，这将变得非常昂贵。03 准备工作0让我们正式回顾一下CoSimRank的定义。表1列出了本文中使用的主要符号。CoSimRank是由[18]提出的一种基于图拓扑的吸引力节点对相似度度量。它基于一种递归的哲学观点，“如果两个节点的入邻居相似，则它们被认为是相似的”。与SimRank[8]不同，每个节点的CoSimRank得分并不始终为1。从数学上讲，CoSimRank的公式如下：10S = C A T SA + I（1）0相比之下，SimRank [8] 定义为：S = max { C A T SA , I }。0Track：社交网络分析和Web的图算法WWW 2018年4月23日至27日，法国里昂∆Gf∆Ge∆Gg∆G = ∆Gf ∪ ∆Ge ∪ ∆Ggueg−uNote that if the new ˜A and old A are not of the same size(this case will happen when there are new nodes in ∆Gu),then prior to using Eq.(4), we should first border A with newzero-columns on the right and new zero-rows on the bottomto make it the same size of new ˜A.Example 2. In Figure 1, old graph G has 5 nodes, so theold A is of size 5 × 5. In ∆Ge = ([c, f, g] → e) there are twonew nodes f and g. Thus, to update A in answer to ∆Ge,we first border A to 7 × 7 with two zero columns and rows:a b c d e f ga 01212 0 0 0 0b 0 0 0 0120 0c 012 0 0 0 0 0d 0 012 0120 0e 0 0 0 0 0 0 0f0 0 0 0 0 0 0g 0 0 0 0 0 0 0borderedregion13+2 ×�2 ×a 0b12c 0d12e 0f0g 0+a 0b 0c 1d 0e 0f1g 1�=a 0b15c15d15e 0f15g151{c,f,g} new ˜A[:, e]old A[:, e]old A(bordered)deg−eδeThen, since deg−e = 2 and δe = 3, in light of Eq.(3), thee-th column of A in answer to ∆Ge is updated to˜A[:, e] =13+2(2A[:, e] + 1{c,f,g})= [0, 15, 15, 15, 0, 15, 15]T .□2In the following, ∆Gui = ([vi1, vi2, · · · , viδ ] → ui) is abbreviatedto ∆Gu = ([v1, v2, · · · , vδu] → u) for simplicity.Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France6010a b0f0c0e0d0g0∆G中的新边0在G中0将∆G的所有边分为3部分：0a b0f f e0c g0g0d0图1：旧网络图G的示例（实线箭头）由∆G（虚线箭头中的六条新边）更新0其中 S 是一个（对称的）CoSimRank矩阵，其元素S[i,j]是图G中节点i和j之间的相似度得分；C是一个介于0和1之间的常数衰减因子；A是列归一化的邻接矩阵；I是单位矩阵；而（*）T是矩阵转置。在公式（1）中，S的每个元素的上限是1/（1-C）。为了评估单个节点对的CoSimRank得分，Rothe和Schütze [18]采用了一种新方法来计算S[i, j]：0S [ i, j ] = ∑ ∞ k =0 C k ( p ( k ) i ) T p ( k ) j (2)0其中 p ( k ) j 是相对于种子节点 j 的个性化 PageRank向量，可以通过迭代从以下公式获得：0p ( k ) j =  Ap ( k − 1) j with p (0) j =  e j (3)0在静态图 G（具有 n 个节点和 m条边）上，通过公式（2）和（3）计算单对分数 S [ i, j ] 需要 O ( K (m  +  n )) 的时间和 O ( m  +  Kn ) 的内存，其中 K是迭代次数。当图动态更新时，重新计算所有 CoSimRank分数将产生昂贵的开销。04 提出的方案0我们首先提出了一种高效的动态方案D-CoSim，可以快速准确地检索大规模不断变化的图上的CoSimRank 分数。接下来，我们将展示我们的动态 D-CoSim如何适用于大大加速静态图上的 CoSimRank搜索，并提出我们的静态方案 F-CoSim。04.1 D-CoSim 在不断变化的图上0给定一个旧图 G 和一组更新到 G 的新边：0∆ G  =  { ( v 1  →  u 1 ) ,  ( v 2  →  u 2 ) ,  ( v 3  →  u 3 ) ,  ∙ ∙0根据每条边 ( v i  →  u i ) 的终点 u i，在 ∆ G中我们首先将所有边分块：0∆ G  = ∆ G u 1  ∪  ∆ G u 2  ∪ ∙ ∙ ∙ ∪  ∆ G u p，其中每个片段 ∆G u i 中的所有边共享一个公共终点 u i。因此，每个片段 ∆ G u i的形式如下：0∆ G u i  =  { ( v i 1  →  u i ) ,  ( v i 2  →  u i ) ,  ∙ ∙ ∙  ,  ( v i0即简写为 ∆ G u i  �  ([ v i 1 , v i 2 ,  ∙ ∙ ∙  , v i δ ]  →  u i)。0示例 1. 图 1 描述了旧图 G（实线箭头）和对 G 的更新图 ∆G（虚线箭头）：0∆ G  =  { ( a  →  f ) ,  ( c  →  e ) ,  ( d  →  g ) ,  ( f  →  e ) ,  ( b  →  f ) ,  ( g  →  e )0我们将 ∆ G 的边分为 3 个片段：∆ G  = ∆ G e ∪ ∆ G f  ∪ ∆ G g，其中∆ G e  =  { ( c  →  e ) ,  ( f  →  e ) ,  ( g  →  e ) }  �  ([ c, f, g ]  →  e )。0∆ G f  =  { ( a  →  f ) ,  ( b  →  f ) }  �  ([ a, b ]  →  f )，∆ G g  = ([ d ]  →  g )。□0我们对 ∆ G 的边进行分块有两个优点：首先，我们可以高效地描述 A对 ∆ G u i 的变化，将其视为旧 A 的第 u i列的线性变换。这种描述方式使我们能够动态地捕捉 CoSimRank分数在对更新 ∆ G u i 的响应中的“刷新区域”。其次，对 ∆ G的边进行分块有助于在每个片段 ∆ G u i上共享和重用公共信息，从而避免在不断变化的图上进行许多不必要的重复计算。例如，为了高效地更新 CoSimRank相似性以响应每个片段 ∆ G u i  �  ([ v i 1 , v i 2 ,  ∙ ∙ ∙  , v i δ ]  → u i)，一旦计算出更新边 ( v i 1  → u i )的中间结果，就可以最大限度地重用它来更新所有其他边（例如 ( v i2  →  u i )，( v i 3  →  u i )，∙ ∙ ∙ ）在 ∆ G u i 中。因此，D-CoSim在不断变化的图上非常高效。将 ∆ G的所有边分块后，我们提出了一种高效的方法，动态计算对每个更新片段 ∆ G u 的 CoSimRank 分数的变化。我们观察到，每个更新片段∆ G u 仅改变 A 的一列。具体来说，我们证明了以下引理。0引理 1. 给定旧图 G 和对 G 的更新片段：∆ G u  = ([ v 1 , v 2 ,  ∙ ∙ ∙  ,v δ u ]  →  u)，图 ( G  ⊕  ∆ G u ) 的新的列归一化邻接矩阵 ˜ A可以通过用其第 u 列替换旧 A 来动态更新：0˜A [: , u ] = 10( deg − u A [: , u ] +  1 { v 1 ,v 2 , ∙∙∙  ,vδu } ) (4)0其中 deg − u 是节点 u 在旧图 G 中的入度；δ u 是 ∆ G u中的边更新数；1 { v 1 ,v 2 , ∙∙∙  ,v δu }是一个列向量（其长度是新矩阵 ˜ A 的行数），在 ( v 1 , v 2 ,  ∙ ∙ ∙  ,v δ u ) 位置上为 1，其他位置为 0。Leveraging Lemma 1, we next show how to dynamicallyupdate CoSimRank scores in answer to each piece ∆Gu.Theorem 1. Given an old graph G, an update piece to G:∆Gu = ([v1, · · · , vδu] → u), and a query node q ∈ (G⊕∆Gu),the changes ∆S[:, q] to CoSimRank scores with respect to qare dynamically computed as∆S[:, q] =∞∑k=0Ck (t(k)[q] · p(k) + p(k)[q] · t(k))(5)where p(k)[q] and t(k)[q] denote the q-th entry of the vectorsp(k) and t(k), respectively, which are iteratively obtained by{ p(0) = eup(k) = ˜AT p(k−1){t(0) =C2(δu+deg−u )(A + ˜A)T rt(k) = ˜AT t(k−1)(6)and r = limK→∞r(K), which can be iteratively derived as{ r(0) = w(K)r(k) = CAT r(k−1) + w(K−k)(1 ≤ k ≤ K)(7)with{ w(0) = 1{v1,··· ,vδu } − δuA[:, u]w(k) = Aw(k−1)(1 ≤ k ≤ K)(8)Proof. After ∆Gu is updated to G, by definition in Eq.(1),the new CoSimRank scores (S + ∆S) in G ⊕ ∆Gu satisfyS + ∆S = C ˜AT (S + ∆S) ˜A + IRearranging the terms in the above equation yields∆S = C ˜AT ∆S ˜A + EwithE = C ˜AT S ˜A + I − S(9)Let ∆A = ˜A − A. From Eq.(4) in Lemma 1, we have∆A[:, u] =1δu+deg−u(1{v1,··· ,vδu } − δuA[:, u])(10)To simplify E in Eq.(9), we plug ˜A = A + ∆A[:, u]eTu andS = CAT SA + I, and let fu ≜ S∆A[:, u], which producesE = C(eu(f Tu A) + (AT fu)eTu + (∆A[:, u]T fu)eueTu )= euxT + xeTuwhere(11)x = CAT fu + C2 (∆A[:, u]T fu)eu= C(AT + 12eu∆A[:, u]T )fu{using Eq.(10)}= C2 (AT + ˜AT )fu(12){]kw(k)r(k)0[0, −1.5, 1, −1.5, 0, 1, 1]T[0, 0, 0, 0, 0, 0, 0]T1[−.25, 0, −.75, .5, 0, 0, 0]T[−.375, 0, 0, −.375, 0, 0, 0]T2[−.375, 0, 0, −.375, 0, 0, 0]T[−.25, −.113, −.975, .5, −.113, 0, 0]T3[0, 0, 0, 0, 0, 0, 0]T[0, −1.868, 1.075, −1.5, .116, 1, 1]Tkp(k)t(k)0[0, 0, 0, 0, 1, 0, 0]T[0, .065, −.09, 0, −.105, 0, 0]T1[0, 0, 0, 0, 0, 0, 0]T[0, −.045, 0, 0, −.005, 0, 0]T2[0, 0, 0, 0, 0, 0, 0]T[0, 0, 0, 0, −.009, 0, 0]T3[0, 0, 0, 0, 0, 0, 0]T[0, 0, 0, 0, 0, 0, 0]T6020因此，结合公式（9）和（11），我们得到：0∆S = 0k = 0 Ck(˜AT)kE˜Ak {使用公式（11）}0= ∑0k = 0 Ck((˜AT)keuxT ˜Ak + (˜AT)kxeTu˜Ak) (13)0通过直接迭代，根据公式（6）和（8），我们得到：0p(k) = (˜AT)keu, w(k) = Ak(1{v1, ∙∙∙, vδu} − δuA[:, u]) (14)0为了将r表示为公式（6）中的t(0)，通过迭代，公式（7）暗示：0r(K) = (CAT)Kw(K) + (CAT)K−1w(K−1) + ∙∙∙ + w(0)0= ((CAT)KAK + (CAT)K−1AK−1 + ∙∙∙ + I)0� �� �0(1{v1, ∙∙∙, vδu} − δuA[:, u])0� �� �0r � lim K→∞ r(K) = (δu + deg−u)S∆A[:, u] = (δu + deg−u)fu0因此，通过将r = (δu + deg−u)fu代入公式（6），我们得到：0t(0) = C02(A + ˜A)Tfu = {根据公式（12）} = x, t(k) = (˜Ak)Tx (15)0将公式（14）和0∆S = 0k = 0 Ck(p(k)(t(k))T + t(k)(p(k))T)0最后，将两边都乘以eq得到公式（5）。□0示例3。回顾图1中的旧G（实线箭头），并将片段∆Ge = ([c, f, g] →e)更新为G（虚线箭头）。给定查询q = e，迭代次数K =3，衰减因子C = 0.6，定理1将∆S[:,e]检索为下列内容：首先，我们通过公式（8）和（7）计算{w(k)}和{r(k)}：0接下来，我们通过公式（6）使用r = r(3)来获得{p(k)}和{t(k)}：0最后0∆S[:, e] = ∑3k=0 0.6k(t(k)[e] ∙ p(k) + p(k)[e] ∙ t(k))0= [0, .0645, −.09, 0, −.2091, 0, 0] T □0定理1暗示了一种高效的动态方法D-CoSim，用于检索CoSimRank分数的变化（算法1）。0正确性。虽然定理1仅保证了∆S相对于一个片段更新∆Gu的正确性，但以下定理进一步保证，在处理完一个片段更新∆Gu后，正在处理的其他片段不会扭曲正确的CoSimRank结果∆S[:, Q]。0定理2。令∆G � {∆G1, ∆G2, ∙∙∙,∆Gp}为一组边被分组更新到旧图G（第1行）。D-CoSim返回的CoSimRank变化∆S（第20行）是对更新图∆G的正确答案。0证明。令∆A，∆A1，∆A2，∙∙∙，∆Ap分别表示相对于图更新∆G，∆G1，∆G2，∙∙∙，∆Gp的列归一化邻接矩阵的变化。在第一轮for循环（第4-19行）中：D-CoSim从将G0（�G）视为旧图开始，将S0（�S）视为旧的CoSimRank分数，并将第一块∆G1更新到G0。定理1确保第一轮的s（第18行）是相对于更新∆G1到G0的CoSimRank变化，即∆S1满足0S0 + ∆S1 = C(A0 + ∆A1)T(S0 + ∆S1)(A0 + ∆A1) + I0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, Franceueg−6030算法1：D-CoSim(G, ∆G, C, Q, K)0输入：一个旧图G，一组对G的边更新∆G，衰减因子C，一个查询集合Q，迭代次数K 输出：对∆G的CoSimRank变化∆S[:, Q]的答案。01将∆G的所有边分块为{∆Gu}，使得∆G=∪u∆Gu且∆Gu中的边=([v1,...,vδu]→u)共享相同的末端u02对于查询q∈Q进行循环，初始化∆S[:,q]:=004初始化w(0):=1{v1,...,vδu}-δuA[:,u]05对于k=1到K进行循环，更新w(k):=Aw(k-1)06初始化r:=w(K)07对于k=1到K进行循环，更新r:=CATr+w(K-k)08∆A[:,u]:=10(1{v1,...,vδu}-δuA[:,u])09更新˜A:=A+∆A[:,u]eTu010初始化p(0):=eu011对于k=1到K进行循环，更新p(k):=˜ATp(k-1)012初始化t(0):=C02(δu+deg-u)(A+˜A)Tr013对于k=1到K进行循环，更新t(k):=˜At(k-1)014对于查询q∈Q进行循环015初始化s:=0；017s:=s+Ck(t(k)[q]∙p(k)+p(k)[q]∙t(k))；018更新∆S[:,q]:=∆S[:,q]+s；019更新A:=˜A020返回∆S[:,Q]:={∆S[:,q]|�q∈Q}；0然后，D-CoSim通过添加s（=∆S1）更新∆S（第18行），并更新当前图从G0到G1（第19行）：0∆S=0+∆S1=∆S1，A1=A0+∆A10for循环（第4-19行）持续到最后一个块∆Gp被更新。在for循环（第4-18行）的第p（最后）轮中：D-CoSim将Gp-1（=Gp-2+∆Gp-1）视为旧图，将Sp-1（=Sp-2+∆Sp-1）视为旧的CoSimRank分数，并将第p块∆Gp更新为Gp-1。定理1确保第p轮（第18行）的s（记为∆Sp）是相对于更新∆Gp到Gp-1的CoSimRank变化，即∆Sp满足0Sp-1+∆Sp=C(Ap-1+∆Ap)T∙(Sp-1+∆Sp)∙0∙(Ap-1+∆Ap)+I（16）0然后，D-CoSim通过添加s（=∆Sp）更新∆S（第18行），并更新当前图从Gp-1到Gp（第19行）：0∆S=(∆S1+...+∆Sp-1)+∆Sp，Ap=Ap-1+∆Ap0最后，我们检查∆S（=∆S1+∆S2+...+∆Sp）是否是相对于更新∆G到G的正确的CoSimRank变化。我们上面对于每一轮for循环的分析暗示了0Si=Si-1+∆Si，Ai=Ai-1+∆Ai（�i=1,...,p-1）0重复应用上述迭代得到0Ap-1+∆Ap=(Ap-2+∆Ap-1)+∆Ap=...=0=(A0+∆A1)+∆A2+...+∆Ap-1+∆Ap0=A0+∆A with ∆A�∆A1+...+∆Ap（17）0同样地，0Sp-1+∆Sp=S0+∆S with ∆S�∆S1+...+∆Sp（18）0将方程（17）和（18）代入方程（16）得到0S0+∆S=C(A0+∆A)T(S0+∆S)(A0+∆A)+I0因此，∆S满足CoSimRank的定义，这意味着D-CoSim返回的∆S（=∆S1+∆S2+...+∆Sp）恰好是相对于图更新∆G（=∆G1+...+∆Gp）到G0（�G）的CoSimRank变化。□0例4.回顾图G（实线箭头）和图更新∆G到G（虚线箭头）在图1中。给定查询q=e，迭代次数K=3，衰减因子C=0.6，D-CoSim根据∆G计算∆S的答案如下：首先，D-CoSim将∆G的所有边分块为三个片段：∆G=∆Ge∪∆Gf∪∆Gg，根据例1。然后，在CoSimRank变化∆S1[:,e]相对于第一个片段更新∆Ge到G0（=G）中被推导出（见例3）：0∆S1[:,e] = [0, .0645, −.09, 0, −.2091, 0, 0]T,0D-CoSim将G1(=G0⊕∆Ge)视为旧图，并计算相对于第二个片段更新∆Gf到G1的变化∆S2[:,e]：0∆S2[:,e] = [0, .009, 0, 0, .0239, .1, 0]T.0接下来，它将G2(=G1⊕∆Gg)视为旧图，并计算相对于第三个片段更新∆Gg到G2的变化∆S3[:,e]：0∆S3[:,e] = [0, .018, 0, 0, .0288, 0, .12]T.0最后，CoSimRank的变化∆S[:,e]相对于图更新∆G(=∆Ge⊕∆Gf⊕∆Gg)为：0∆S[:,e] = ∆S1[:,e] + ∆S2[:,e] + ∆S3[:,e]0= [0, .0915, −.09, 0, −.1564, .1, .12]T □0复杂性。我们分析了D-CoSim的计算成本。令˜n和˜m分别表示新图G⊕∆G中的节点数和边数。令δ为∆G中的边数，p为∆G中更新片段{∆Gu}的数量。显然，p≤δ。D-CoSim具有以下复杂性界：0定理3.D-CoSim在K次迭代后，动态计算∆S[:,Q]所需的时间为O(K(˜m+˜np|Q|))，内存为O(˜m+K˜n)，其中|Q|是Q中查询的数量。0证明。D-CoSim分为三个阶段：(1)对∆G的边进行分组(line1)，(2)迭代计算{p(k)}和{t(k)}(lines 4-13)，(3)在线查询(lines14-18)。具体来说，对∆G的边进行分组需要O(δ)的时间和O(δ)的内存，用于线性扫描∆G中的所有边。为了迭代计算{p(k)}和{t(k)}，对于每个查询q∈Q和每个片段更新∆Gu，需要O(K˜m)的时间和O(˜m+K˜n)的内存来计算方程(6)-(8)。O(K˜m)的时间主要由5个矩阵-向量乘积决定：Aw(k-1)(line 5)，ATr(k-1)(line 7)，˜ATp(k-1)(line11)，(A+˜A)Tr(line 12)和˜At(k-1)(line13)。O(˜m+K˜n)的内存主要由矩阵A和迭代向量的存储决定。对于在线查询，一旦计算出{p(k)}和{t(k)}，它们将被存储并在计算Q中的每个查询的∆S[:,q]时重复使用。在更新∆S[:,q]之后0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, Franceecfgdabegfdc=ecfgdab∆G ≜ G ⊖ T+2foreach weakly connected component GwccG do4while U ̸= ∅ do6T := Tunvisited in- and out-links of v;8return T ;Sl = CAl−1,lSl−1Al−1,l + Inl(l = 2, · · · , L)(19)6040对于每个片段更新∆Gu的回答，所有向量{p(k)}和{t(k)}都会被释放以供下一个片段更新使用。因此，对于|Q|个查询和p个更新片段，总共需要O(K(˜m+˜np|Q|))的时间和O(˜m+K˜n)的内存。□0定理3保证了D-CoSim在动态CoSimRank搜索中的高效性，其加速效果通过以下两点实现：(a)我们将“刷新区域”∆S[:,q]的特征化仅限于{p(k)}和{t(k)}的线性组合，(b)在回答每个片段∆Gu上的边更新时，最大程度地重用和共享公共中间结果。相比之下，[18]的现有方法需要O(K(˜m+˜n))的时间来从头开始计算每个边更新的单对˜S[i,j]，通过方程(2)和(3)，导致计算˜S[:,Q](˜n×|Q|对)的总时间为O(K(˜m+˜n|Q|)˜nδ)，这是相当昂贵的。04.2 F-CoSim在静态图上的应用0除了支持在演化图上快速动态CoSimRank检索外，D-CoSim还可以应用于静态图，以加速CoSimRank搜索。基于D-CoSim，我们接下来提出了一种高效的方案F-CoSim，它可以大大加快在静态图上的CoSimRank搜索。给定一个静态图G和一个查询集Q，F-CoSim基于三个思想检索G上的CoSimRank得分S[:,Q]：首先，我们提出了一种快速方法来找到G的“生成树”T，使得G被分解为G=T⊕(G�T)，可以将其视为旧的T加上其更新(G�T)。接下来，在T上，由于其特殊的“生成树”结构，我们注意到CoSimRank得分相对容易计算，并提出了一种新颖的快速算法来检索“生成树”上的CoSimRank得分S(T)[:,Q]。最后，我们应用我们的动态D-CoSim来计算相对于(G�T)的图更新对S(T)的变化。通过以上思想，F-CoSim在静态图上的CoSimRank搜索中实现了显著的加速，这是通过我们高效的方法在“生成树”上检索S(T)[:,Q]和我们快速的D-CoSim来计算相对于(G�T)的S(T)的变化实现的。接下来，我们将详细阐述这些思想。0定义1（生成Polytree）。对于一个连通图G，其生成PolytreeT是G的子图，包括