6190低秩谱网络对齐0HudaNassar计算机科学系，普渡大学，印第安纳州西拉法叶，美国hnassar@purdue.edu0NateVeldt数学系，普渡大学，印第安纳州西拉法叶，美国lveldt@purdue.edu0Shahin Mohammadi CSAILMIT & BroadInstitute，马萨诸塞州剑桥市，美国mohammadi@broadinstitute.org0AnanthGrama计算机科学系，普渡大学，印第安纳州西拉法叶，美国ayg@cs.purdue.edu0David F.Gleich计算机科学系，普渡大学，印第安纳州西拉法叶，美国dgleich@purdue.edu0摘要0网络对齐或图匹配是在网络去匿名化和生物信息学中应用的经典问题，存在着各种各样的算法，但对于所有算法来说，一个具有挑战性的情况是在没有任何关于哪些节点可能匹配良好的信息的情况下对齐两个网络。在这种情况下，绝大多数有原则的算法在图的大小上要求二次内存。我们展示了一种方法——最近提出的并且在理论上有基础的EigenAlign算法——允许一种新颖的实现，其在图的大小上需要线性内存。这个洞察力的关键步骤是识别EigenAlign用于确定匹配的节点相似度矩阵中的低秩结构。通过一个精确的、闭合的低秩结构，我们然后在这个低秩矩阵上解决一个最大权重二分匹配问题，以产生图之间的匹配。对于这个任务，我们展示了一个新的、后验的、近似界限，用于近似一个低秩矩阵上的最大权重二分匹配问题。我们两个新方法的组合使我们能够处理比以前可能的更大的网络对齐问题，并且可以快速完成。对于现有方法需要几个小时的问题，我们的新算法只需要几秒钟。我们对我们的低秩算法进行了全面的验证，并在生物信息学和社交网络的问题上比较了各种现有算法。我们的方法还可以与现有算法结合，以提高其性能和速度。0关键词0网络对齐；图匹配；低秩矩阵；低秩二分匹配0ACM参考格式：Huda Nassar，Nate Veldt，ShahinMohammadi，Ananth Grama和David F.Gleich。2018年。低秩谱网络对齐。在WWW 2018：0本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在其个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂。© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.318612802018年Web会议，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318612801 引言和动机0网络对齐是将两个不同图中的节点进行配对，以保持边缘结构并突出网络之间的相似性的问题。节点配对可以是一对一或多对多的。虽然我们提出的方法都可以适应这两种情况，但我们主要关注一对一的情况，因为它有最广泛的文献。网络对齐的应用包括：（i）在社交网络中查找相似节点，这可以揭示有关配对节点中的一个或两个的信息，并可以帮助定制广告和为相似用户建议活动；（ii）社交网络去匿名化[10]；以及（iii）图中的模式匹配[3]。生物学中一个非常流行的例子是在蛋白质相互作用网络中进行对齐[6, 14,27]。在生物学中，通过将一个蛋白质网络与另一个已经研究过的蛋白质网络进行对齐，可以从中提取关于蛋白质的宝贵知识，尤其是对于那些了解很少的蛋白质。通过这样做，可以通过了解第一个网络中的蛋白质与第二个网络中的蛋白质的相似性来得出关于第一个网络中蛋白质的结论。网络对齐问题有两种主要方法[1]：局部网络对齐，目标是找到与任何给定节点相似的图的局部区域；全局网络对齐，目标是理解两个大图如何相互对齐。许多网络对齐方法依赖于解决一个优化问题，以计算两个网络中节点对之间的拓扑相似度得分。在这里，我们专注于两个图之间的一对一全局对齐。一些应用还提供了关于一个网络中的哪些节点可能与另一个网络的节点匹配良好的先验信息，这隐含地对必须在实践中计算和存储的相似度得分的数量施加了限制[2]。然而，对于缺乏这种先验信息的问题，存储相似度得分的数据要求是二次的，这严重限制了解决这类问题的方法的可扩展性。例如，Klau等人的拉格朗日松弛方法[7]至少需要二次内存。0研究方向：社交网络分析和Web上的图算法WWW 2018，2018年4月23日至27日，法国里昂(1)6200对于没有先验知识的网络对齐问题，可以使用可扩展的启发式方法，包括Patro等人的GHOST过程[24]，或者Kuchaieve等人的GRAAL算法[12]及其变体。然而，这些方法通常涉及图中顶点邻域的立方或更差的计算（例如，在本地区域内枚举所有5节点图形）。一种避免二次内存需求的基本方法是网络相似性分解（NSD）[8, 9,22]，它基于IsoRank方法[27]提供了一个有用的低秩分解特定相似性矩阵的方法。该方法使得可以在极大网络之间计算对齐。然而，自IsoRank发表以来，网络对齐方法已经有了许多改进。最近的一种创新是一种基于特征向量的方法，称为EigenAlign。EigenAlign方法使用与两个网络之间的乘积图相关的矩阵的主特征向量来估计相似性。通过在稠密二分图上解决最大权重二分匹配问题，将特征向量信息舍入为图的顶点之间的匹配[5]。IsoRank方法也基于特征向量，或者更具体地说，使用了两个网络的乘积图的PageRank向量来达到相同的目的[27]。相比之下，EigenAlign的一个关键创新是它明确地对可能在网络中没有匹配的节点进行建模。通过这种方式，当图形没有太多噪声时，它能够对齐许多简单的图形模型，如Erdős-Rényi。这给了它一个坚实的理论基础，尽管它仍然需要二次内存。在我们的手稿中，我们强调了一些创新，使得EigenAlign方法能够在没有二次内存需求的情况下工作。我们首先展示了EigenAlign解的一个低秩矩阵的显式表达式，并且我们可以使用一个简单的过程精确和明确地计算这些低秩因子。使用我们的新方法提供的低秩信息的一个挑战是如何在匹配步骤中使用相似性分数的低秩结构的想法很少[15,22]。我们提供了一个关于如何使用低秩结构的新分析，给出了一个可计算的后验近似保证。在实践中，这个近似保证非常好：约为1.1。这样的过程应该能够实现进一步的低秩应用，而不仅仅是网络对齐。我们的贡献：•EigenAlign特征向量解的一个低秩矩阵的显式表达式（定理3.1）。•一种O(n logn)的方法，用于在低秩矩阵上解决最大权重二分匹配问题，并具有后验近似保证（算法3，定理4.2）。在实践中，这些近似保证对我们的实验来说比1.1更好（图7）。这改进了[22]中的最近工作，该工作提供了一个简单的k近似算法，其中k是秩。•对我们的方法进行了全面评估，以表明我们的低秩方法的结果与原始的EigenAlign方法之间几乎没有区别（第5.1节），而且我们的方法更具可扩展性。•演示了我们的低秩方法可以与现有的网络对齐方法相结合，以获得更好的质量结果（第5.2节）。0•演示了这些方法足够可扩展，可以在大图中的每两个相连节点的顶点邻域所诱导的所有网络对之间运行。也就是说，当顶点之间存在边时，我们希望将两个顶点邻域对齐在一起。为了验证对齐结果，我们展示了这些对齐结果与邻居集合的Jaccard相似度之间的关联（图10）。02 网络对齐的公式和当前技术0我们现在回顾一下网络对齐算法的状态以及我们的特定设置和目标。图1显示了一个有用的说明。02.1 典型的网络对齐问题0对于网络对齐问题，我们给定两个具有邻接矩阵A和B的图G A和GB。目标是在网络之间保持拓扑相似性的情况下产生G A和GB节点之间的一对一映射[3]。在某些情况下，我们还会收到关于一个网络中的哪些节点可以与另一个网络中的节点配对的信息。这个额外的信息以一个二分图的形式呈现，其边权重存储在矩阵L中；如果Luv > 0，则表示外部证据表明G A中的节点u应该与GB中的节点v匹配。我们将这个外部证据称为对齐的先验。当存在先验时，先验和拓扑信息一起确定一个对齐。更正式地说，我们寻找一个二进制矩阵P，它编码了网络节点之间的匹配，并最大化下面讨论的几个可能的目标函数之一。当矩阵P满足约束条件时，它编码了一个匹配0P u, v = 01 u与v匹配，否则为0，u P u, v ≤1对于所有v，v P u, v ≤ 1对于所有u。0不等式约束保证第一个网络中的节点只与另一个网络中的一个或零个节点匹配。02.2 网络对齐的目标函数0问题的经典公式寻求一个矩阵P，最大化G A和GB之间重叠边的数量，即G A中的相邻节点对(i A, j A)映射到GB中的相邻节点对(i ′ B, j ′ B)的数量。这导致以下整数二次规划问题：0最大化P � ij [ P T AP ] ij [ B ]ij，满足� � u P u, v ≤1对于所有v，v P u, v ≤1对于所有u，P u, v ∈ {0, 1}0最近的目标函数变体包括对重叠三角形的扩展[21]，将边重叠与先前的相似度得分相结合的扩展[2,27]，以及特定于二分图的扩展[11]。02.3 EigenAlign算法0先前目标函数的一个缺点是对于不产生重叠的匹配没有任何不利影响，即0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France(3)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France6210网络对齐的目标是在没有任何提示或先验信息的情况下找到两个网络节点之间的匹配。0我们的方法使用重叠、非信息和冲突匹配得分来计算所有成对对齐的大规模矩阵的低秩形式的特征向量。0重叠0非信息0冲突0图1：我们的网络对齐设置遵循Feizi等人的方法[5]，我们寻求在没有其他元数据的情况下对齐两个网络。基于三种情况之一对GA中的任意节点对(i, j)和G B中的任意节点对(i ′, j′)进行评分，并将其组装成一个大规模但高度结构化的对齐矩阵M。0在G A中映射到G B中的非边或反之亦然的GA中的边。这些目标函数也不考虑在G A中的非边映射到GB中的非边的情况。第一个问题在[25]中被认识到，该论文提出了一种基于SDP的方法来最小化冲突匹配的数量。最近，EigenAlign目标函数[5]包括了这三种情况的明确项：重叠、非信息匹配和冲突，见图1。在这种情况下，与P对应的对齐分数是0AlignmentScore(P) =0sO（#重叠）+ sN（#非信息）+ sC（#冲突）（2）0其中sO，sN和sC是重叠、非信息和冲突的权重。这些常数应该选择使得sO > sN >sC。通过将sN和sC设置为零，我们可以恢复最大化重叠数量的普通概念。虽然最大化冲突数量可能看起来很奇怪，但当图形的大小或边的数量非常不同时，这个术语起到了正则化的作用。重要的是，非信息比冲突更有价值。这个目标可以通过首先引入一个大规模的对齐矩阵M来形式化表达，该矩阵定义如下：对于GA中的所有节点对iA，jA和GB中的所有节点对i′B，j′B，如果P(iA, i′B) = 1且P(jA, j′B) =1，则0M[(iA, i′B), (jA, j′B)] =0sO，如果（iA，jA），（i′B，j′B）是重叠的；sN，如果（iA，jA），（i′B，j′B）是非信息的；sC，如果（iA，jA），（i′B，j′B）是0在这个定义中，我们有点滥用符号，并使用对iA和i′B进行索引的对来索引该矩阵的行和列。对于这些对iA，i′B的直接、规范排序，矩阵M可以用A和B的邻接矩阵来重新表示：0M = c1(B � A) + c2(EB � A) + c2(B � EA) + c3(EB � EA)0其中�表示Kronecker积，c1 = sO + sN - 2sC，c2 = sC - sN，c3 =sN，EA和EB是由1组成的矩阵，与A和B的大小相同。矩阵M是对称的。0只要GA和GB是无向的（有关有向扩展的讨论在[5]中有提到，但我们在这里不考虑）。最大化对齐分数（2）等价于以下二次分配问题：0maximize y y T M y0满足 y i ∈ {0, 1}，对于所有 v ∈ V，Bv y [u, v] ≤1，对于所有 u ∈ V A0其中VA和VB分别是GA和GB的节点集。向量y实际上就是表示匹配矩阵P的数据向量，约束条件只是从（1）中翻译的匹配约束。一个在经验和理论上成功的优化这个目标的方法是解决一个特征向量方程，而不是二次规划。这正是EigenAlign的方法，它使用以下两个步骤计算网络对齐：（1）找到与最大幅值的特征值对应的M的特征向量x。注意，M的维度是nA nB × nAnB，其中nA和nB分别是GA和GB中节点的数量；因此，特征向量的维度将是nA nB，并且可以重塑为一个nA ×nB的矩阵X，其中每个条目表示两个图之间每对节点的分数。我们称之为相似矩阵，因为它反映了GA和GB之间的拓扑相似性。（2）在相似矩阵X上运行一个二分图匹配算法，最大化最终对齐的总权重。0我们的贡献。在我们的工作中，我们通过改进两个步骤来扩展EigenAlign所奠定的基础。我们首先展示相似矩阵X可以通过精确的低秩分解准确表示。这使我们能够避免EigenAlign的二次内存需求。然后，我们提出了几种在低秩矩阵上进行二分图匹配问题的新的快速技术。这些改进共同产生了一个在实践中更具可扩展性的低秩EigenAlign算法。0其他技术的总结0我们的工作与网络相似性分解（NSD）[ 8]具有许多相似之处，NSD是一种基于不同相似性矩阵的低秩分解技术，该矩阵是IsoRank算法[ 27 ]使用的矩阵。[ 8]的作者表明，可以通过分别在两个图上执行计算来获得这种分解，这显著加快了节点之间相似性分数的计算。另一种用于对齐没有先验信息的网络的方法是图对齐工具（GRAAL）[ 12]。GRAAL为每个节点计算所谓的图元度特征签名，这是一种推广了节点度数并表示节点局部邻域的拓扑结构的向量。该方法通过测量图元度之间的距离来获得相似性分数，然后使用贪婪的种子扩展过程根据这些分数在两个网络之间匹配节点。还引入了许多与该方法相关的算法，这些算法通过考虑其他拓扑相似性度量以及不同的舍入方法来扩展原始技术。Xk+1 = c1AXkBT + c2AXkET + c2EXkBT + c3EXkET .(5)Xk = U kVTk(6)U k = [c1AU k−1 | c2EU k−1 | c2AU k−1 | c3EU k−1]V k = [BV k−1 | BV k−1 | EV k−1 | EV k−1].Xk+1= c1AXkBT + c2AXkET + c2EXkBT + c3EXkET= c1AU kVTk BT + c2AU kVTk ET + c2EU kVTk BT + c3EU kVTk ET= [c1AU k | c2EU k | c2AU k | c3EU k][BV k | BV k | EV k | EV k]T= U k+1VTk+1.Rk = [B v | Be | . . . | Be | e]Ck =�c1Ck−10c2Ck−100Tc2rTkCk−10Tc3rTkCk−1�T k =�T k−1T k−1000T0ThTT k 1hTT k 1�.rk = [ eT Ak−1ueT Ak−2e· · ·eT A1eeT A0e ]Thk = [ eT Bk−1veT Bk−2eeT B1eeT B0e ]TU k+1 = [c1AU k | c2EU k | c2AU k | c3EU k]= [AU k | EU k]� c1I0c2I00c2I0c3I�c1I0c2I0U k+1 = Sk+1I00T rTk+1C k00 C kc1I0c2I00c2I0c3I= Sk+1Ck+1Xk = SkW kRk .6220将相似性分数转化为对齐[ 13 , 17 , 18 , 20]。GHOST算法也采用了种子扩展对齐过程[ 24]，该算法基于每个节点的新颖谱特征计算拓扑相似性分数。最近，[21]引入了一种寻找最大化网络之间保留的高阶结构（如三角形）数量的对齐的概念。这导致了一个整数规划问题，可以通过三角对齐算法（TAME）来近似求解，该算法通过解决一个松弛原始目标的张量特征值问题来获得相似性分数。改进网络对齐的其他方法包括允许用户从大量潜在近似匹配中选择匹配项的主动方法[16]。03 EigenAlign的低秩因子0EigenAlign算法的第一步是计算对称矩阵 M的主特征向量。Feizi等人建议通过首先形成矩阵 M，对该矩阵进行幂迭代，并将最终输出的特征向量 x 重塑为矩阵 X来获得相似性矩阵 X [ 5 ]。由于矩阵 M中的Kronecker结构，这可以等价地直接表示为满足以下条件的矩阵X ：0满足 ∥ X ∥ F = 1 , X ∈ R n A × n B . (4)0在这个表达式中， X • Y = � ij X ij Y ij 是矩阵内积，从矩阵 M的特征向量的转换来自Kronecker积性质 vec ( AXB T ) = ( B � A )vec ( X ) 。我们还从所有元素都为1的矩阵 E 中省略了维度。矩阵M 的特征向量是对矩阵 X 进行 vec操作的结果，该操作通过连接列将矩阵转换为向量。我们的第一个重要贡献是表明，如果从秩为1的矩阵开始使用幂法估计矩阵 X，那么幂法的第k次迭代将产生一个秩为k +1的矩阵，我们可以明确且准确地计算出来。03.1 一个四因子低秩分解0在问题（4）的矩阵形式中，幂法的一步对应于迭代：0如果我们从秩为1的矩阵 X 0 = uv T 开始，其中 u ∈ R n A 且v ∈ R n B ，并且令 U 0 = u ， V 0 = v ，以便 X 0 = U 0V T 0 。我们首先通过归纳证明 X k 可以写成：0其中0我们归纳的基本情况直接来自于我们对 X 0 的定义。现在假设在 k之前的等式 (5) 和 (6) 成立，我们将证明 k + 1的等式成立。我们从以下开始0等式 (5) 并插入从 (6) 得到的 X k 的分解：0这种形式的分解还不够有用，因为矩阵 U k 的维数为 n A × 4 k。为了证明这确实是一个秩为 k + 1 的矩阵，我们证明0X k = S k C k T T k R T k 其中： S k = [ A k u| A k − 1 e | . . . | A e | e ]0在上述中， 0 是适当大小的全零矩阵或向量，而 e是全一向量。此外， C 0 = T 0 = 1，且 r k 和 h k定义如下：0其中 r 1 = [ e T A 0 u ] 和 h 1 = [ e T B 0 v]。注意，这种形式给出了我们所需的秩为 k + 1 的分解，因为 S k 和 R k 都有 k + 1列。为了完成我们的推导，我们再次使用归纳法证明 U k = S k Ck 。基本情况 k = 0可以通过对初始定义的简单展开立即得到，因此假设结果对整数 k成立。然后，0现在，注意到 AS k = S k + 1 � I 0 T � 和 ES k = S k + 1 � 0 r T k + 10� . 因此0再次应用相同的步骤将得到 V k = R k T k 。03.2 三因子和二因子分解0虽然这种四因子分解对于揭示 X k的秩很有用，但我们不希望在实践中使用矩阵 C k 和 T k，因为每个矩阵都有 4 k 列。现在我们将展示它们的乘积 C k T T k产生一个易于计算的大小为 ( k + 1 ) × ( k + 1 ) 的矩阵 W k，从而给出一个三因子分解 (3FD)：0主题：社交网络分析和Web图算法 WWW 2018，2018年4月23日至27日，法国里昂��.�6230输入: A , B , u , v , c 1 , c 2 , c 3 , k0输出：ˆ U 和 ˆ V，使得 X k = ˆ U ˆ V T0计算 ˜ U k , ˜ V k 并将范数保存在 a [1] , . . . , a [ k + 1]; b [1] , . . . , b [ k + 1]中。计算构建 r 1 , . . . , r k 和 h 1 , . . . , h k 所需的项。0定义向量ai = a[i+1]a[1...i]，其中i = 1, ..., k0定义向量bi = b[i+1]b[1...i]，其中i = 1, ..., k0设置˜W0 =a[1]b[0更新˜Wi = �c1˜Wi−1c2˜Wi−1(bi◦hi)0c2(ri◦ai)T˜Wi−1c3(ri◦ai)T˜Wi−1(bi◦hi)0结束0计算UW，SW，VW = SVD(˜Wk)，并设置D = S1/2W，返回ˆU =˜UkUWD，ˆV = ˜VkVWD0图2：将X分解为两个低秩矩阵的算法伪代码。注意，◦表示两个向量之间的逐元素Hadamard乘积。0矩阵Wk的0Wk = CkTTk = �c1Wk−1c2Wk−1hkc2rTkWk−1c3rTkWk−1hk0其中W0 = C0TT0 = 1 ∙ 1 =1。这是通过将Ck与TTk相乘得到的。这个分解离我们的最终目标更近了一步，但是因子中的数字缩放很差。因此，我们可以通过使用缩放对角矩阵来纠正这个问题，以便呈现我们的最终缩放良好的三因子分解Xk，我们将其作为一个总结定理呈现：0定理3.1. 如果X0 = uv T，其中u ∈ RnA×1，v ∈RnB×1，则更新(5)的第k次迭代允许以下低秩分解：0Xk = ˜Uk˜Wk˜VTk，其中0˜Uk = �Aku∥Aku∥∞Ak−1e∥Ak−1e∥∞...Ae∥Ae∥∞e∥e∥∞0˜Vk = �Bku∥Bku∥∞Bk−1e∥Bk−1e∥∞...Be∥Be∥∞e∥e∥∞0˜Wk =DuWkDv。这里Du是一个(k+1)×(k+1)的对角矩阵，对角线上的元素为(∥Aku∥, ∥Ak−1e∥, ..., ∥Ae∥,∥e∥)，Dv是一个对角矩阵，其元素为(∥Bkv∥, ∥Bk−1e∥, ..., ∥Be∥,∥e∥)。0定理(3.1)中的对角矩阵是专门设计的，以满足SkD−1u =˜Uk，RkD−1v =˜Vk，因此缩放和未缩放的三因子分解之间的等价性是直接的。然而，结果仍然是非标准化的。然而，我们可以通过根据需要缩放矩阵˜Wk来轻松实现实际规范化。请注意，在实践中计算这个分解时，我们不仅仅构造S、R和W，然后用Du和Dv进行缩放。相反，我们通过注意到第k步的每个因子与第k+1步的相应因子之间的相似性，递归地形成缩放的因子。我们的实现直接计算这些的伪代码如图2所示。正如我们将在下一节中看到的，我们最终希望用一个左因子和一个右因子来表示Xk。0为了应用我们的低秩二分匹配技术，我们希望产生两个具有大致相等缩放的因子，因此我们通过对˜Wk进行奇异值分解并将˜Wk的部分分割为左右项来实现这一目标。图2的最后几步完成了这个目标。04 低秩匹配0在本节中，我们考虑在低秩矩阵上解决最大权重二分匹配问题，并提供有用的后验近似保证。在我们的网络对齐例程中，我们的算法将在图2的低秩矩阵上使用。然而，在本节中，我们将根据一个一般的矩阵Y进行处理，该矩阵具有低秩因子Y = UVT。矩阵Y表示二分图的边权重，因此最大权重匹配问题是：0最大化 M M • Y0满足 M i , j ∈ { 0 , 1 } ，对于所有的 j ，有 M i , j ≤ 1，对于所有的 i ，有 � ij M i , j ≤ 1 ，(7)0其中 • 是矩阵内积（参见 (4) ）。 M i , j的元素表示双分图一侧的节点 i 与另一侧的节点 j之间的匹配。满足匹配约束的任何 M 都被称为匹配矩阵。04.1 秩1矩阵上的最优匹配0我们首先考虑秩1矩阵 Y = uv T 的最优匹配，其中 u , v ∈ R n（这些结果很容易适应不同长度的向量）。0情况1： u , v ∈ R n ≥ 0 或 u , v ∈ R n ≤ 0 。如果 u 和 v只包含非负元素，或者都只包含非正元素，则找到最优匹配的过程是相同的：我们按照大小对两个向量的元素进行排序，并按照排序列表中的顺序配对元素。如果任何一对元素的权重为0，我们不会匹配这对元素，因为它不会改善整体匹配得分。这种特殊情况下的匹配的最优性可以看作是重新排列不等式的直接结果。0情况2：一般情况下， u , v ∈ R n 。如果 u 和 v的元素可以是正数、负数或零，我们需要一种稍微复杂一点的方法来找到 Y上的最优匹配。在这种情况下，定义 ˜ Y 为通过复制 Y并删除所有负元素得到的矩阵。为了找到 Y的最优匹配，我们永远不会配对给出负权重的元素，因此 ˜ Y 的最优匹配与 Y的最优匹配相同。现在，令 u + 和 u − 分别为 u中包含的严格正元素和负元素的向量，类似地，定义 v + 和 v − 为 v中包含的严格正元素和负元素的向量。然后， ˜ Y = ˜ Y 1 + ˜ Y 20其中 ˜ Y 1 = u + v T + ， ˜ Y 2 = u − v T − 。令 M 1 和 M 2分别为 ˜ Y 1 和 ˜ Y 2 的最优匹配矩阵，使用排序技术得到。由于u + ， u − ， v + 和 v − 中可能包含一些为零的元素，所以 M 1和 M 2可能会使某些节点无法匹配。下面的引理表明，将这些匹配组合起来可以得到 ˜ Y 的最优结果：0Track: 社交网络分析和Web图算法 WWW 2018，2018年4月23-27日，法国里昂M • ˜Y 1 + M • ˜Y 2 > ˜M • ˜Y 1 + ˜M • ˜Y 2Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France6240引理 4.1. 由 M 1 匹配的节点集将与 M 2匹配的节点集不相交。由这两个匹配组合而成的匹配 ˜ M 对于 Y是最优的。0证明。我们将通过反证法证明 M 1 和 M 2 之间没有冲突。假设M 1 包含匹配 ( i , j ) ，而 M 2 包含冲突的匹配 ( i , k ) 。由于M 1 包含匹配 ( i , j ) ，则 ˜ Y 1 ( i , j ) 必须非零，意味着 u + ( i) 和 v + ( j ) 都是正数。类似地， M 2 包含匹配 ( i , k ) ，所以u − ( i ) 和 v − ( k ) 都是负数。这是一个矛盾，因为 u + ( i ) 和u − ( i ) 中至少有一个必须为零。我们只需要证明 ˜ M 是 Y的最优匹配。如果不是这样，就会存在某个匹配 M ，使得 M • ˜Y > ˜ M • ˜ Y 。如果存在这样的 M ，我们将有0然而， ˜ M • ˜ Y 1 = M 1 • ˜ Y 1 ≥ M • ˜ Y 1 ，而 ˜ M • ˜ Y2 = M 2 • ˜ Y 2 ≥ M • ˜ Y 2 。因此，产生了矛盾；˜ M 是 ˜ Y的最优匹配。□04.2 低秩因子上的匹配0现在我们来解决矩阵 Y = UV T 的匹配问题，其中 Y ∈ R m × n， U ∈ R m × k ， V ∈ R n × k 。令 u i 和 v i 分别为 U和 V 中的第 i 列，令 Y i = u i v T i ，则 Y = � k i = 1 Y i。我们可以使用第4.1节的结果找到每个 Y i 上的最优匹配。令 M i 为对应于 Y i 的匹配矩阵，令 M � 为在 Y上达到最优最大权重的匹配矩阵。注意， M � • Y i ≤ M i • Y i，因此，0M�•Y ≤ Σki=1Mi•Yi。(8)0通过定义以下术语，我们可以分析Mi在整个矩阵Y上的匹配程度。0di,j = Mi•Yi0Mj•Yi dj = maxi di,j D = minjdj (9)0令j� = argminjdj，即D =dj�。注意对于任意固定的索引i，j，我们有di,j ≤ dj。将此应用于j =j�，我们得到对于所有i，0Mi•Yi Mj�•Yi = di,j� ≤ dj� = D � Mi•Yi ≤ D(Mj�•Yi) (10)0通过结合(8)和(10)，我们得到以下结果。0定理4.2。通过选择Y的低秩因子之一的最优匹配，我们可以实现D-近似的二分匹配问题。0证明。M�•Y ≤ Σki=1Mi•Yi ≤ Σki=1D(Mj�•Yi) = D(Mj�•Y)。□0该过程（图3）的运行时间为O(k2n +knlogn)，其中k是秩，U和V有O(n)行。空间需求为O(nk)。在实践中，近似因子D小于1.1（见图7）。图3显示了实现此匹配算法的伪代码。0输入：U，V，使得Y = UVT0输出：近似的最大权重匹配M，近似值D 找到每个秩-1矩阵的最优匹配Mi（参见§4.1）计算匹配的权重vi = Mi•Yi 计算di,j = vi / (Mj•Yi) for all i,j = {1,...,k} 计算dj = maxidi,j, D = minimum(dj), j� = argmin(dj)0返回M = Mj�，D0图3：从低秩矩阵中找到D-近似匹配的伪代码。04.3 改进的实际变体0我们的方法（图3）可以在不实质性改变其运行时间或内存需求的情况下进行改进。关键思想是创建一个包括匹配Mj�和其他有用边的稀疏最大权重二分匹配问题。通过最优地解决这些问题，我们只会改进近似度。这些问题的解决成本是最优解决这些问题，但是对于具有数百万条边的问题，稀疏最大权重匹配求解器是实用且快速的。匹配的并集。最简单的改进是基于完整的匹配集M1,...,Mk创建一个稀疏图。我们可以通过将由Y定义的完全二分网络转换为只有当节点(j,k)由某个Mi匹配时，边(j,k)的权重Yj,k非零的稀疏网络ˆY来实现这一点。然后，我们在稀疏矩阵ˆY上解决一个最大二分匹配问题，该矩阵具有O(nk)个非零元素或边。这只会改进近似度，因为我们包括了匹配Mj�。在秩-1因子上扩展非匹配项。由于算法3在构建Mi时依赖于排序过程，并且由于这些数字很可能彼此接近，我们可以选择扩展可能的匹配集，并让每个节点与其最接近的c个值配对。例如，如果c =3，并且我们已经排序了索引0排序后的u：i1 i2 i3 i4 i5 排序后的v：j1j2 j3 j4 j5 然后我们添加边0(i1,j1) (i1,j2) (i2,j1)(i2,j2) (i2,j3) (i3,j2)...0我们将所有这些边添加到稀疏矩阵ˆY中，并使用来自Y的真实值解决生成的矩阵上的最大二分匹配问题。再次强调，这包括了Mj�中的所有边。在添加了ui、vi集合中的所有边之后，最终边的数量是O(kcn)，因此，当kc为o(n)时，生成的匹配矩阵是一个稀疏矩阵。05 实验0为了评估我们的方法，我们首先研究了低秩EigenAlign和原始EigenAlign算法之间的关系。这些初步实验的目标是展示：（i）我们需要大约8次迭代（得到一个秩为9的矩阵）才能得到与EigenAlign相等的结果（图4）；（ii）我们的方法在各种图模型上表现相同（图5）；（iii）方法的可扩展性更好（图6）；（iv）计算得到的近似界限小于1.1（图7）。我们还在图8中与其他可扩展技术进行了比较，发现我们的方法是最好的。接下来，我们使用来自生物学[28]的已知对齐的网络测试集来评估我们的算法（第5.2节）。最后，我们结束MMtrue F .(11)6250我们的实验中，我们研究了一个协作网络的顶点邻域对齐（第5.3节）。我们的低秩EigenAlign在所有这些实验中，我们的低秩技术使用具有c =3的扩展匹配（第4.3节），并将初始秩-1因子设置为均匀的：v = e，u = e。令α = 1 +nnz(A) / nnz(B)0nnz(A)(n^2B - nnz(B)) + nnz(B)(n^2A - nnz(A)) .0加上可能重叠与可能冲突的比值。令γ = 0.001，那么sO = α +γ，sN = 1 + γ，sC =γ。这些参数与[5]中使用的参数相对应。最后，我们将迭代次数设置为8，适用于除了那些明确变化迭代次数的实验之外的所有实验。理论运行时间。当我们将低秩计算和随后的扩展低秩匹配结合在一起时，我们的方法的运行时间为0O(nk^2)0低秩因子0计算dij0+ k 3次奇异值分解 +kn log n次排序0+匹配与ckn条边0和O(nck)的内存。（注意，在我们的实验中，k = 8，c =3。）EigenAlign基准。对于EigenAlign，我们使用相同的参数集sO，sN，sC，并使用从全1向量开始的幂法。我们运行带有归一化的幂法，直到达到残差值10^-12的特征值-特征向量对。这通常在15-20次迭代后发生。05.1 Erdős-Rényi和preferential attachment0我们第一个实验的目标是评估我们的方法与EigenAlign的性能。这些实验都是针对具有已知图形对齐的合成问题进行的。我们用恢复度[5]来评估性能，我们希望恢复度值较大。恢复度的取值范围在0到1之间，并且定义为0恢复度(M) = 1 - 10换句话说，恢复度是正确对齐的比例。图模型。为了生成问题中起始的无向网络(GA)，我们使用Erdős-Rényi和平均度ρ（其中边的概率为ρ/n）或preferentialattachment和一个随机的6个节点的初始图，并添加θ条边到每个顶点。噪声模型。给定一个网络GA，我们添加一些噪声来生成我们的第二个网络GB[5]。以概率pe1，我们删除一条边，以概率pe2，我们添加一条边。然后，代数上，B可以写成A ◦ (1 - Q1) + (1 - A) ◦Q2，其中Q1和Q2是密度分别为pe1和pe2的无向Erdős-Rényi图，◦是Hadamard（逐元素）乘积。我们固定pe2 = pe1 / (1 -p)，其中p是GA的密度。由于一些算法在存在多个可能解时具有偏差，生成B后，我们按相反顺序重新标记B中的节点。8次迭代足够了。我们首先研究迭代次数对结果的影响。我们使用平均度为20的Erdős-Rényi图，分析我们的方法在迭代次数变化时的性能。图4显示了相对于EigenAlign结果的恢复度（左）和重叠度（右），值为1.0表示与EigenAlign相同数量。经过8次迭代，恢复度停止变化0相对于EigenAlign的重叠边缘。相对于EigenAlign的恢复结果。0图4：左侧是我们的低秩方法相对于EigenAlign对齐计算的重
