强局部超图扩散：聚类和半监督学习

20920强局部超图扩散用于聚类和半监督学习0Meng Liuliu1740@purdue.edu 美国普渡大学0Nate Veldtnveldt@cornell.edu 美国康奈尔大学0Haoyu Songsong522@purdue.edu 美国普渡大学0Pan Lipanli@purdue.edu 美国普渡大学0David F. Gleichdgleich@purdue.edu 美国普渡大学0摘要0基于超图的机器学习方法现在被广泛认为是对数据对象之间的高阶和多向关系进行建模和使用的重要方法。局部超图聚类和半监督学习特别涉及在给定一组标记顶点附近找到一组连接良好的节点。尽管存在许多局部图聚类的方法，但是相对于超图的局部聚类方法相对较少。此外，现有的方法通常缺乏对一般类别的超图切割函数进行建模的灵活性，或者无法扩展到大规模问题。为了解决这些问题，本文提出了一种新的基于扩散的超图聚类算法，该算法解决了一个二次超图切割目标，类似于图的Andersen-Chung-Lang个性化PageRank聚类的超图模拟。我们证明，对于具有固定最大超边大小的图，该方法是强局部的，这意味着其运行时间仅取决于输出的大小而不是超图的大小，并且具有高度可扩展性。此外，我们的方法使我们能够计算各种基于基数的超图切割函数。我们还证明，通过解决新的目标函数找到的聚类满足类似Cheeger的质量保证。我们证明，在大型真实超图上，我们的新方法找到了更好的聚类，并且比现有方法运行速度更快。具体而言，与基于流的技术相比，对于具有几百万个超边的超图，它只需几秒钟即可运行，而基于流的技术需要几分钟。此外，我们还展示了我们的框架足够通用，可以用来解决超图上的其他基于p-范数的切割目标。0CCS概念0• 计算数学 → 超图；• 计算理论 → 半监督学习；• 计算方法论 →聚类分析。0关键词0超图，局部聚类，社区检测，PageRank0本文发表在知识共享署名4.0国际许可证（CC-BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW’21，2021年4月19日至23日，斯洛文尼亚卢布尔雅那，© 2021IW3C2（国际万维网会议委员会），根据知识共享CC-BY 4.0许可证发布。ACM ISBN978-1-4503-8312-7/21/04。https://doi.org/10.1145/3442381.34498870ACM参考格式：Meng Liu，Nate Veldt，Haoyu Song，Pan Li和David F.Gleich。2021年。强局部超图扩散用于聚类和半监督学习。在2021年Web会议论文集（WWW’21）中，2021年4月19日至23日，斯洛文尼亚卢布尔雅那。ACM，纽约，美国，12页。https: //doi.org/10.1145/3442381.344988701 引言0图形数据分析中的两种常见情况是：（i）图中的聚类、群组、模块或社区是什么？（ii）在图的节点上给出一些有限的标签信息，可以推断出什么样的缺失标签？这些陈述分别对应于聚类和半监督学习问题，虽然在图上存在强大的算法技术 [ 3 ,  13 ,  19 ,  29 ,  34 ,  35 ,  37 ,42 ]，但是对于超图，这些问题的研究目前非常活跃 [ 8 ,  17 ,  27 ,33 ,  38 ,  40 ,  41 ]，构建在新类型的结果 [ 15 , 26 ,  32]的基础上，与之前的方法 [ 1 ,  20 ,  43]相比。缺乏灵活、多样和可扩展的超图算法限制了研究数据中丰富结构的机会。例如，聚类可以是网络上的相关处理组 [ 10]，或者可以识别许多类型的稀疏网络上的共同结构 [ 24]。同样，半监督学习通过以偏差特征向量的方式对天文数据中星系的发射光谱进行表征，有助于表征微妙的结构 [ 23]。当前的超图算法集对于这些高级场景来说是不足够的。事实上，超图提供了一种灵活且丰富的数据模型，有潜力捕捉传统基于图的分析难以或不可能发现的微妙洞见 [ 5 ,  27 ,  33 ,  38 ,  40]。但是，超图算法的推广通常在可扩展性和解释性方面存在困难 [ 1 ,15]，并且仍然存在问题，即特定模型是否能够捕捉超图中的高阶信息。关于可扩展性，一个重要的特殊情况是强局部算法。强局部算法是指其运行时间取决于输出的大小而不是图的大小。这仅在各种超图聚类和半监督学习框架中最近得到解决 [ 17 ,  33]。该属性使得即使对于具有数亿个节点和边的大型图，也能够快速（秒到分钟）进行评估 [ 3 ]（与小时相比）。对于图形，20930WWW '21，2021年4月19日至23日，斯洛文尼亚卢布尔雅那，刘等人。0也许最著名的强局部算法是Andersen-Chung-Lang（以下简称ACL）近似的个性化PageRank[3]，应用于局部社区检测和半监督学习[42]。我们解决的具体问题是个性化PageRank的mincut启发式超图推广以及快速近似解的强局部算法。我们的公式与现有的拉普拉斯[43]和基于二次函数的超图PageRank推广[25, 27,31]在许多重要方面有所不同。虽然我们的局部超图PageRank在形式上相对简单（第3.2节），但问题陈述和算法解决方案都有许多微妙之处。首先，我们希望有一个公式，能够实现丰富的可能超图切割函数。这些超图切割函数是丰富超图模型的重要组成部分，因为它们确定了一组节点何时应该属于同一个聚类或获得半监督学习的潜在新标签。现有的基于星形扩展（类似于将超图视为二分图）或团扩展（为每个超边将边从团添加到图中，创建加权图）的技术只能模拟有限的一组切割函数[2，32]。基于Lovász扩展的更一般技术[25，27，40]存在重大的计算困难。其次，我们需要一个问题框架，能够给出稀疏解，以便可以以强局部方式计算这些解，然后我们需要一个实际能够计算这些解的算法。仅仅存在解是不足以将这些想法应用于实践的，我们希望能够做到这一点。最后，我们需要了解该算法的结果与各种图数量之间的关系，例如原始ACL方法中的最小导纳集。为了解决这些挑战，我们扩展并使用了一些最近提出的超图框架。首先，我们展示了一类超图到图的转换的新结果[32]。这些转换使用精心构造的有向图小工具，以及一组辅助节点，来编码一类基于基数的超图切割函数的属性。我们的简单新结果突出了这些转换不仅保留了切割值，还保留了超图导纳值（第3.1节）。然后，我们使用一种通用策略在简化图中进行计算，以构建强局部计算。这涉及到一种通常称为“局部切割”图或超图的特定修改[4，11，28，33]。然后，我们使用平方2-范数（即二次函数）代替mincut图中的1-范数，以产生强局部个性化PageRank的超图类比。换句话说，将所有这些步骤应用于图（而不是超图）上等价于个性化PageRank向量的表征[12]。一旦我们建立了框架（第3.1节，第3.2节），我们就能够证明个性化PageRank的推送方法的一种适应（第3.3节）将在仅依赖于本地化参数的时间内计算出一个近似解，并且与具有固定最大超边大小的超图的大小无关（定理3.5）。因此，这些算法是强局部的。我们最终产生的算法非常高效。它的速度比在超图的星形扩展上运行ACL算法慢一个小因子（2-5倍）。它也比运行经过优化的实现的ACL算法图快一个小因子（2-5倍）。0在超图的团扩展上使用ACL算法。然而，对于许多半监督学习问题的实例，它产生的结果的F1分数比替代方法要高得多。特别是，与最近提出的基于流的方法[33]相比，它的速度更快，在极其有限的标签信息下表现更好。附加贡献摘要。除了在第3.2节中提供了一个关于平方2-范数（即二次函数）的强局部算法，该算法在实证性能（第7节）上表现更好和更快之外，我们还讨论了如何改用p-范数（第6节）。最后，我们还展示了一个Cheeger不等式，将我们的结果与附近集合的超图导纳联系起来（第4节）。我们的方法是超图聚类的第一个算法，它包括以下所有特征：（1）强局部性，（2）可以从一个小种子集合中增长一个聚类，（3）模拟灵活的超边切割惩罚，（4）具有导纳保证。使用Yelp评论的激励案例研究。我们首先通过一个简单的例子来说明这些谱或PageRank风格的超图方法的需求和效用，以便将我们的算法与其他各种方法进行比较。我们从Yelp评论数据集（https://www.yelp.com/dataset）构建一个超图。每个餐厅是一个顶点，每个用户是一个超边。这个模型使得用户（即超边）能够捕捉微妙的社会经济地位信息，以及他们访问和评论哪种类型的餐厅的烹饪偏好。我们要解决的任务是局部聚类或半监督学习的一个实例。简而言之，给定拉斯维加斯内华达州的10家随机餐厅样本，我们希望找到拉斯维加斯的其他餐厅。整个超图大约有64k个顶点和616k个超边，最大超边大小为2566。拉斯维加斯约有7.3k家餐厅，构成了一个小的局部聚类。我们研究了一系列不同的算法，可以在超图中的种子节点附近识别一个聚类：（1）Andersen-Chung-LangPageRank在超图的星形和团扩展上（ACL-Star，ACL-Clique，分别），这些算法与[1，43]中提出的思想密切相关；（2）HyperLocal，一种最近提出的基于最大流的超图聚类算法[33]；（3）二次超图PageRank[25，31]（也与[15]密切相关），以及（4）我们的局部超图PageRank（LHPR）。除了（3）之外，这些算法都是强局部的，我们包括（3）是因为我们的算法LHPR本质上是（3）的强局部类比。结果如图1所示。基于流的HyperLocal方法很难找到整个聚类。众所周知，基于流的方法在扩展小种子集合方面存在困难[11，28，34]，这个实验显示了同样的行为。我们的强局部超图PageRank（LHPR）在性能上略微优于不是强局部的二次超图PageRank（QHPR）。特别地，它的解决方案中有10k个非零条目（64k个中的10k个）。这个实验展示了我们的方法在大型超图中的机会。我们能够建模一族灵活的超图切割函数，超越了使用团和星扩展的方法，并且在性能上等于或优于所有其他方法。例如，另一种更复杂的方法[17]专为小超边大小设计，显示出与ACL-Clique类似的性能（F1约为0.85），并且花费更长的时间。20940用于聚类和半监督学习的强局部超图扩散 WWW '21，2021年4月19日至23日，斯洛文尼亚卢布尔雅那0ACL-CliqueP=0.80，R=0.99，F1=0.8760ACL-StarP=0.76，R=0.98，F1=0.850HyperLocal [33]P=0.92，R=0.05，F1=0.100QHPR [25, 31]P=0.83，R=0.95，F1=0.8860LHPR（我们的方法）P=0.83，R=0.98，F1=0.9000图1：该图显示了拉斯维加斯的约7,300家在Yelp上有评论的餐厅的位置，以及算法从10个随机种子集中恢复它们的频率；我们的超图PageRank（LHPR）方法具有最高的准确性，并且仅通过探索总共10000个顶点就找到了结果，而QHPR则需要一个完全密集的向量，从而提高了在更大图上的可扩展性。颜色显示每个算法在15次试验中错过（红色或橙色）或找到（蓝色）的区域。HyperLocal是一种基于流的方法，已知在这个实验中很难扩展小的种子集。（HyperLocal的参数是与其作者协商选择的；其他参数是手动调整以获得最佳性能的。）02符号和准备工作0设G = (V, E,w)是一个有向图，其中|V|=n，|E|=m。为简单起见，我们要求每个有向边(i, j)∈E的权重w_ij≥1。我们将无向图解释为具有两个有向边(i,j)和(j,i)。为简单起见，我们假设顶点用索引1到n进行标记，以便我们可以使用这些标签来索引矩阵和向量。例如，我们将d定义为长度为n的出度向量，其中第i个分量di=∑j∈Vwij。关联矩阵B∈{0, -1,1}m×n测量相邻节点的差异。B的第k行对应于一条边，例如(i,j)，并且具有恰好两个非零值，节点i为1，节点j为-1。（请记住，我们有有向边，因此边的起点始终为1，目标始终为-1。）设H=(V,E)是一个超图，其中每个超边e∈E是V的一个子集。ζ=maxe∈E|e|是最大的超边大小。对于每个超边，我们关联一个分割函数fe，用于评估将超边分割为两个标签或将超边分割为两个簇的适当惩罚。形式上，设S是一个簇，设A=e∩S是超边在S中的节点，则fe(A)惩罚分割e。早期超图文献中常见的选择是全有或全无分割，即如果超边被分割，则分配一个固定值，如果超边中的所有节点都在同一个簇中，则分配零[14, 18,22]：如果A=e或A=�，则fe(A)=0，否则fe(A)=1（或其他常数）。最近，提出了各种替代的分割函数[26, 27,32]，提供了更大的灵活性。我们在下一节（§3.1）中讨论更多选择。确定分割函数后，任何给定集合S的切割值可以写成cutH(S)=∑e∈Efe(e∩S)。在这种情况下，节点度可以定义为di=∑e:i∈ef e({i})[26,33]，尽管在图和超图的情况下也可以使用其他类型的度向量。这导致了超图上导电的定义。0ϕH(S) = 0min(vol(S), vol(¯S)) (1)0其中 vol(S) = S中的每个节点di的总和。当每条边只有两个节点（ζ =2）且使用全有或全无惩罚时，这就变成了标准的图导电定义。用于半监督学习和局部聚类的扩散算法。给定一组种子，或者我们通常认为的0作为参考，设R是一个扩散方法，它产生一个在所有其他顶点上的实值向量x。例如，个性化PageRank方法使用R来定义过程的个性化向量或重启向量[3]。然后，PageRank解或稀疏的Andersen-Chung-Lang近似[3]就是扩散x。给定扩散向量x，我们通过执行称为扫描切割的过程将其舍入回集合S。这涉及将x从最大到最小排序，然后评估每个前缀集合Sj={[1],[2],...,[k]}的超图导电，其中[i]是第i个最大顶点的id。扫描切割返回的集合选择导电最小的集合Sj。由于扫描切割过程是通用且标准化的，我们重点关注x的计算。当这些算法用于半监督学习时，返回的集合S被假定与参考（种子）集合R共享标签；或者，它的值或排名信息可以用于消除多个标签的歧义[13, 42]。03 方法0我们的总体目标是计算一个超图扩散，以帮助我们执行扫描切割，以识别与图中参考顶点集合附近具有合理小的电导率的集合。我们通过两个转换来解释我们的方法：局部超图二次扩散（LHQD）或局部超图PageRank（LHPR）。我们采用这种策略是为了充分证明最终的提案是合理的，因为其中一些转换需要额外的上下文来理解。对于超图电导率，计算最终的扫描切割是直接的，因此我们不专注于该步骤。03.1 超图到图的转化0即使在简单图的情况下，最小化电导率也是NP难的，尽管已经设计了许多技术来近似理论和实践中的目标。在超图中搜索低电导率集合的常见策略是首先将超图转化为图，然后应用现有的基于图的技术。这听起来很“hacky”或至少是“特定场景的”，但这个想法既有原则性又严谨。最常见的方法是应用团扩展[1, 5, 26, 43,46]，它明确地模拟了形式为 f e ( A ) ∝ | A || e \ A | 的分割函数。20950WWW '21，2021年4月19日至23日，斯洛文尼亚卢布尔雅那，刘等。0例如，Benson等人[5]表明团扩展可以用于将3-均匀超图转化为保持全有或全无电导率值的图。对于更大的超边大小，全有或全无电导率可以在与超边大小相关的失真因子内保持。稍后，Li等人[26]首次引入了更一般的超边分割函数概念，专注于子模块函数。0定义3.1. 如果分割函数 f e 是子模块的，则称其为子模块的。0对于任意 A，B � e，有 f e ( A ) + f e ( B ) ≥ f e ( A ∪ B ) +0这些作者表明，在这种子模块情况下，可以使用团扩展来定义一个保持电导率在 O ( ζ ) 因子内的图形（其中 ζ是最大超边大小）。最近，Veldt等人[32]引入了图形缩减技术，可以完全保持基于基数的子模块超图切割函数。0定义3.2. 如果分割函数 f e 是基于基数的，则称其为基于基数的。0当且仅当 | A | = | B | 时，f e ( A ) = f e ( B )。 (3)0基于基数的分割函数对于许多应用来说是一个自然的选择，因为在实践中节点标识通常是无关紧要的，并且基于基数的模型产生的切割函数对节点排列是不变的。此外，先前关于应用广义超图切割惩罚的大部分研究都隐含地专注于基于基数的切割函数[5, 15, 20, 25, 27,46]。由于它们的普遍性和灵活性，在这项工作中，我们还专注于既是子模块又是基于基数的超图切割函数。我们简要回顾相关的图形转换，然后在之前的工作基础上，展示这些超图缩减可以用于保持超图电导率目标，而不仅仅是超图切割。基于基数的切割的缩减。Veldt等人[32]给出了结果，表明基于基数的子模块超图的切割属性可以通过用一组有向图“小工具”替换每个超边来保持。每个超边 e的小工具是通过引入一对辅助节点 a 和 b，并带有权重 δ e > 0的有向边 ( a , b ) 构建的。对于每个 v ∈e，引入两条单位权重的有向边：( v , a ) 和 ( b , v)。然后，整个小工具通过权重 c e ≥ 0进行缩放。得到的小工具表示以下形式的简化分割函数：f e ( A ) = ce ∙ min {| A | , | e \ A |, δ e }。0图2(b)说明了用一个装置替换超边的过程。任何基于基数的次模分割函数的割集属性都可以通过引入一组 O (| e |)或更少的这样的分割函数来精确建模 [ 32]。如果只需要近似，则只需要 O ( log  | e |) 个装置[6]。这些简化结果的一个重要结果是，为了开发任何基于基数的次模分割函数的简化技术，只需考虑具有简化形式 (4)的分割函数的超边即可。在本文的其余部分，我们将重点放在这种形式的分割函数上，理解所有其他基于基数的次模分割函数都可以通过在相同节点集上引入具有不同边权重的多个超边来建模。0在图2中，我们说明了将小超图简化为有向图的过程，其中我们为每个超边引入了一个装置。形式上，对于超图 H =  ( V ,  E )，此过程产生一个有向图 G =  ( ˆ V , ˆ E ) ，其中有向边集 ˆ E，节点集 ˆ V  =  V  ∪  V a  ∪  V b ，其中 V是原始超图节点的集合。集合 V a ，V b存储辅助节点，使得对于每对辅助节点 a ，b ，其中 ( a , b )是一条有向边，我们有 a  ∈  V a 且 b  ∈  V b。这种简化技术先前被开发为保留原始超图的最小割和最小  s - t割。在这里，我们将这个结果扩展到表明对于一种特定的节点度选择，这个简化也保留了超图电导。0定理 3.3. 为简化图 G  =  ( ˆ V , ˆ E ) 定义度向量  d，其中对于每个节点  v  ∈  V ，d ( v )  =  d v是出度，对于每个辅助节点  u  ∈  V a  ∪  V b ，d ( u )  =  d u  =0 。如果 T � 是 G 中的最小电导集，则 S � =  T � ∩ V 是 H中的最小超图电导集。0证明. 根据先前关于这些简化技术的工作 [ 6 , 32 ]，我们知道在 H中，对于集合 S  �  V，割惩罚等于在有向图中的割惩罚，只要辅助节点的排列方式产生了在选择的节点集合 S  �  V  的最小割惩罚。形式上，对于 S  �  V ，0割集 H ( S )  = 最小化 T  � ˆ V  :  S = T  ∩ V 割集 G0其中 cut G 表示在 S内部起始的被割断的有向出边的权重。根据我们选择的度向量，G中节点的总量等于 H 中非辅助节点的总量。也就是说，对于所有 T  �ˆ V ，vol G ( T )  = � v  ∈ V d v +  � u  ∈ V a ∪ V b d u = vol G ( T ∩  V  )  =  vol H ( T  ∩  V  ) 。设 T � � ˆ V 是 G 中的最小电导集，S �=  T � ∩  V  。不失一般性，我们可以假设 vol G ( T � ) ≤  vol G ( ¯ T �) 。由于 T �最小化电导，并且辅助节点对该集合的体积没有影响，cut G ( T � )  = minimize T  �  ˆ V  :  T  ∩ S �  cut G ( T )  =  cut H ( S � ) ，因此 cutG ( T � )/ vol G ( T � )  =  cut H ( S � )/ vol H ( S � ) 。因此，在 G中最小化电导也最小化了 H 中的电导。 □03.2 本地化二次超图扩散0在建立了从超图到有向图的保持电导的简化之后，我们现在提出了在简化图 G中检测局部聚类的框架。为了实现这一点，我们首先定义了一个局部有向割图，涉及源节点和汇节点以及新的加权边。这种方法与先前定义的用于局部图聚类和半监督学习的局部割图 [ 4 ,  7 ,  12 ,  28 ,  34,  44 ] 以及用于基于流的超图聚类的类似局部割超图 [ 33 ]密切相关。关键的概念差异在于我们直接将此构造应用于简化图 G，根据定理 3.3 保留了原始超图 H的电导。形式上，我们假设给定一个节点集合 R  �  V，我们希望在其周围找到低电导聚类，并且有一个参数 γ  >0。局部有向割图通过将以下步骤应用于 G 来定义：0• 引入源节点s，并为每个r ∈ R定义一个权重为γd r的有向边(s, r)0• 引入汇节点t，并为每个v ∈ ¯ R定义一个权重为γdv的有向边(v, t)。1235678456785678Dd1235678412356784AaEDCBedcb20960用于聚类和半监督学习的强烈局部超图扩散 WWW '21，2021年4月19日-23日，斯洛文尼亚卢布尔雅那0(a) 原始超图0(b) 单个超边缩减装置0A a0E0D0C0B0e0d0c0b0(c) 扩展图0s0t0γ02γ02γ0γ02γ 3γ02γ02γ0(d) 局部有向切割图0图2：超图缩减（第3.1节）和局部化（第3.2节）的简单示例。 (a) 一个有8个节点和5个超边的超图。 (b)用于δ-线性分割函数的超边转换装置的示意图。 (c)通过为每个超边添加一对辅助节点将超图缩减为有向图，并且这保留了超图导纳计算（定理3.3）。 (d)通过从源节点s到超图节点或从超图节点到t的边来创建局部有向切割图，以局部化解。0我们不将辅助节点连接到源节点或汇节点，这与定理3.3中定义它们的度为零是一致的。我们在图2(d)中说明了局部有向切割图的构造。重要的是要注意，在实践中，我们实际上并没有形成这个图并将其存储在内存中。相反，这提供了一个在G中找到局部低导纳集的概念框架，这些集合与H中的好的聚类相对应。定义：局部超图二次扩散。设B和w是具有γ的局部有向切割图的关联矩阵和边权重向量。我们的超图聚类扩散的目标函数，我们称之为局部超图二次扩散或简称局部超图PageRank，是0minimize x 1 2 w T ( Bx ) 2 + + κγ � i ∈ V x i d isubject to x s = 1, x t = 0, x ≥ 0. (6)0我们使用函数( x ) + = max { x , 0}，应用于Bx的每个元素，以表示我们只保留这个乘积的正元素。这类似于我们只将有向边视为被切割，如果它从源端穿过到汇端；这类似于以前在图和超图上的有向切割次小值[39]。目标函数中的第一项对应于局部有向切割图上最小s-t切割目标的2-范数次小值。（在无向正则图中，项w T ( Bx )+变成一个包含拉普拉斯算子的表达式，可以与PageRank[12]形式上相关联）。如果我们将指数2替换为1并忽略第二项，这将等同于找到一个最小s-t切割（可以通过最大流来解决）。目标函数中的第二项是为了鼓励解的稀疏性，其中κ ≥0控制所需的稀疏水平。通过下一节中的结果，我们能够证明我们可以以仅依赖于κ、γ和vol(R)的时间计算出解，这使得我们能够以强烈的局部方式评估(6)的解。03.3 LHQD (6)的强烈局部求解器0在本节中，我们将提供一种强烈的局部算法来近似满足(6)的最优性条件。我们首先在定理3.4中陈述最优性条件，然后提出解决这些条件的算法。理解这个算法最简单的方法是将其视为Andersen-Chung-Lang推送过程的一般化。0对于PageRank [ 3]，我们也将其称为ACL，以及更近期的非线性推送过程 [ 28]。关于这个新算法的两个新挑战是：(1)这个新算法在一个有向图上操作，这意味着与ACL不同，每次迭代没有单一的闭式更新；(2)对于辅助节点没有稀疏正则化，这将破坏现有推送过程的强局部保证。我们从 (6) 的最优性条件开始。0定理3.4. 固定种子集合  R ，  γ  >  0 ，  κ  >  0 ，定义残差函数  r ( x )  =  − 10γ B T  diag (( Bx ) + ) w 。满足 (6)的KKT条件的必要和充分条件是找到  x � ，其中  x � ≥  0 ， r ( x � )  =[ r s ,  g T , r t  ] T ，其中  д i  ≤  κd i  （其中  d 反映了在添加  s和  t  之前的图，但包括  0 度节点），( κd i  − д i ) T x � i =  0 对于i  ∈  V ，并且对于所有添加的辅助节点，  д i  =  0 。0这是对凸规划的最优性条件的直接应用。详细的证明将在本材料的较长版本中包含。我们进一步指出，解  x �是唯一的，因为该问题由于二次项是强凸的。在第3.1节中，我们已经证明了任何基于基数次模型的分割函数的约简技术足以引入具有不同  δ e  和  c e的多个有向图小工具。为了简化我们的阐述，我们假设每个超边都有一个 δ -线性阈值分割函数 [ 33 ]  f e  =  min {| A | ,  | e \ A | , δ}，其中  δ  ≥  1 是一个可调参数。这个分割函数可以通过用一个具有 c e  =  1 和  δ e  =  δ的有向图小工具替换每个超边来精确建模。（这就是图2中所示的情况。）当  δ  =  1  时，它模拟了标准的非加权全有或全无割 [ 14 ,18 ,  22 ]，当  δ  趋近于无穷大时，它模拟了星扩展 [ 46]。因此，这个分割函数可以通过变化  δ来插值超图上的这两个常见割目标。通过假设我们有一个 δ-线性阈值分割函数，这意味着我们可以将每个超边与两个辅助节点精确地关联起来。我们将这些节点简称为  a  和  b 。我们还将  V a定义为所有  a  辅助节点的集合，将  V b  定义为所有  b节点的集合。在高层次上，解决这个问题的算法如下：每当存在一个图节点  i  ∈  V  违反最优性条件，即  r i  >  κd i ，我们首先在  i上执行一个超级推送，增加  x i  以使最优性条件近似满足，即  r i  =20970WWW '21，2021年4月19日至23日，斯洛文尼亚卢布尔雅那 Liu等。0算法1 LHQD ( γ , κ ,  ρ ) 用于集合 R 和超图 H，其中 δ-线性惩罚，其中 0  <  ρ  <  1 决定了精度01: 令  x = 0，除了  x s  = 1，并设置  r = − γ − 1 B T diag (( Bx )02: 当存在任何顶点  i  ∈  V  满足  r i  >  κd i时，或者如果不存在这样的顶点，则停止（找到一个最优性违规）03: 在顶点  i  上执行 LHQD-hyperpush，使得  r i  =  ρκd i，在每次迭代后更新  x  和  r 。 (满足 i 上的最优性)04: 对于每一对相邻的辅助节点  a ,  b ，其中  a  ∈  V a ， b  ∈  Vb ，且  a  →  b ，在  a  和  b  上执行 LHQD-auxpush，使得 r a=  r b  =  0，然后在每次 auxpush 后更新  x  和  r 。05: 返回  x0ρκd i  其中 0  <  ρ  <  1是一个给定的参数，影响着近似解。这会改变解  x  仅在当前节点 i和相邻辅助节点的残差上。然后我们立即对相邻的辅助节点进行推送，这意味着我们增加它们的值，以使残差保持为零。在推送每对相关的辅助节点 ( a , b ) 之后，我们然后更新 V中相邻节点的残差。然后我们搜索另一个优化违规。(详见算法1对此策略的形式化描述。) 当  ρ  <  1时，我们只能近似满足最优性条件；这种近似策略已经在现有的局部图聚类算法中反复成功使用过 [3, 12,28]。优化该过程的注意事项。算法1将这些扩散问题近似解决的一般策略形式化了。我们现在注意到一些优化方法，这些方法可以极大地加速这个策略。首先，注意到  x  和  r可以保持为稀疏向量，只存储少量的条目。其次，注意到我们可以维护一个最优性违规的列表，因为每次对  x  的更新只会导致  r增加，所以我们只需检查每个坐标增加是否创建了一个新的违规，并将其添加到队列中。第三，为了找到需要“推送”到每个节点的值，一般的策略是使用二分搜索过程，就像我们将在第6节中使用的p-范数广义化一样。然而，如果二分搜索的容差太小，它会减慢每次迭代的速度。如果容差太大，解将离真解太远，无法使用。在本节的剩余部分，我们将展示在二次目标 (6) 的情况下，我们可以 (i)经常避免二分搜索，以及 (ii)当仍然需要时，使二分搜索过程与我们需要它的那些迭代的容差选择无关。这些详细的技术不会改变整体算法的时间复杂度，但在实践中会有很大的差异。我们将从查看残差向量的扩展形式开始。当  i  ∈V  时，r i  扩展为：0r i = 10γ0b ∈ Vb w bi ( x b −x i ) + − 10γ0�0a ∈ Va w ia ( x i − x a ) + + d i [ Ind( i ∈ R )− x i ]。0(7)同样，对于每个a ∈ Va，b ∈ Vb，其中a →b，它们将共享相同的一组原始节点，它们的残差可以扩展为：0r a = − w ab ( x a − x b ) + � r b = w ab ( x a − x b ) −� i ∈ V w ia ( x i − x a ) + i ∈ V w bi ( x b − x i ) + (8)0请注意，这里使用了一个结果，即xa ≥xb（引理A.1）。0算法2 LQHD-hyperpush ( i , γ , κ , x , r , ρ )01：使用(9)解决∆ x i，其中s ( i ) a，s ( i ) b，a ( i ) min和b ( i )min的顺序不变。02：如果(10)不成立（添加∆ x i改变了i的顺序），则03：对∆ x i进行二分搜索，直到找到包含xi + ∆xi的所有相邻节点中最小的区间，更新s ( i ) a，s ( i ) b，a ( i )min和b ( i ) min。04：使用找到的区间解决∆ x i，通过设置r i = ρκd i在(7)中。05：结束如果06：更新x和r，xi ← xi + ∆ xi，ri ← ρκd i0每次超推的目标是首先找到∆ x i，使得r ′ i = ρκdi，然后在auxpush中，对于每对相邻的辅助节点(a，b)，找到∆ xa和∆ x b，使得r ′ a和r ′ b保持为零。 (∆ x i，∆ x a和∆ xb是唯一的，因为二次函数是强凸的。)注意，r i，r a和rb都是分段线性函数，这意味着一旦确定了相邻节点的相对顺序，我们可以推导出一个闭合形式的解。此外，在大多数情况下，相对顺序在几次初始迭代后不会改变。因此，我们可以首先重用上一次迭代的排序信息来直接解决∆ x i，∆ x a和∆ xb，然后检查排序是否改变。给定这些观察结果，我们将记录和更新每个推送节点的以下信息。同样，这些信息可以以稀疏方式记录。当推送节点i是原始节点时，对于其相邻的a ∈ Va和b ∈Vb，我们记录：0• s ( i ) a：边权重w ia的总和，其中x a < x i0• s ( i ) b：边权重w bi的总和，其中x b > x i0• a ( i ) min：x a ≥ x i的最小值0• b ( i ) min：x b > x i的最小值0现在假设顺序相同，r ′ i可以写成r ′ i =0r i - 10γ ( s ( i ) a + s ( i ) b ) ∆ x i= ρκd i，所以0∆ x i = γ ( r i - ρκd i )/( s ( i ) a + s ( i ) b ) . (9)0然后我们需要检查假设是否成立，通过检查0x i + ∆ x i ≤ min � a ( i ) min，b ( i ) min � (10)0如果不成立，我们需要使用二分搜索找到xi + ∆xi的新位置（注意这里的∆ xi是仍然未知的真实值），更新s ( i ) a，s( i ) b，a ( i ) min和b ( i ) min，并重新计算∆xi。此过程在LQHD-hyperpush中总结。同样，当推送节点a ∈Va，b ∈ Vb，其中a → b是一对辅助节点时，对于其相邻节点i ∈V，我们记录：0• z a：边权重w ia的总和，其中x a < x i • z b：边权重wbi的总和，其中x b > x i • x ( a ) min：x a < x i的最小值0• x ( b ) min：x b < x i的最小值20980强局部超图扩散用于聚类和半监督学习WWW '21，2021年4月19日至23日，斯洛文尼亚卢布尔雅那0算法3 LQHD-auxpush ( i, a, b, γ, x, r, ∆ x i )01: 使用 z a, z b, x ( a ) min 和 x ( b ) min，使用 (11) 解 ∆ x a, ∆ x02: 如果 (12) 不成立（添加 ∆ x a, ∆ x b 改变了顺序），则03: 对 ∆ x a 进行二分搜索，直到找到包含 x a + ∆ x a的所有相邻原始节点中最小的区间，更新 z a, x ( a ) min，对于 zb, x ( b ) min 也是类似的。04: 使用找到的区间通过在 (8) 中设置 r a = r b = 0 来解 ∆ x a, ∆ xb。05: end if06: 更改 x 和 r 中的以下条目以更新解和残差07: (a) x a ← x a + ∆ x a and x b ← x b + ∆ x b 8: (b) 对于每个邻居节点 i →a，其中 i ∈ V，r i ← r i + 10γ w bi ( x b - x i ) + + 1 γ w bi ( x b + ∆ x b - x i ) +0然后我们通过解下面的线性系统来求解 ∆ x a, ∆ x b（这里我们假设x b ≥ x i）0�0�0- w ab ( ∆ x a - ∆ x b ) + w 0γ (( x ′ i - x a ) + - ( x i - x a ) + ) - z a ∆ = 00w ab ( ∆ x a - ∆ x b ) - w 0γ (( x b - x ′ i ) + - ( x b - x i ) + ) + z b ∆0(11) 其中 x ′ i 是应用 LQHD-hyperpush 后更新的 xi。只有当以下不等式都满足时，假设才成立：0x ′