梯度注入恢复图神经网络中O(n2)残差解码

《Mathematics》：The Missing Signal: Gradient Injection Recovers O(n2) Residual Decoding in GNNs

　　

残差解码算法反复对当前元素进行评分，剪枝得分最低的候选元素，并更新残差状态。经典实现之所以高效，是因为其评分建立在可局部维护的统计量（如度）之上：删除操作后，存活的评分通过局部修正进行变化，从而产生O(n²)的总解码成本。然而，图神经网络（GNN）的评分并不自动具备此特性。在经过非线性激活函数（如tanh或sigmoid）后，底层统计量的等量变化未必导致输出等量变化，因此在删除操作后，通常不存在固定的加性修正来更新评分。标准的自适应替代方案是在每次删除后重新运行整个网络，这将解码成本膨胀至O(n³)。研究人员表明，对于最大团问题，无监督团目标函数的梯度提供了一个更新兼容的残差信号。每次顶点删除后，每个存活的梯度坐标通过一个局部的、可维护的量进行变化，每一步可在O(n)时间内更新。将这个实时梯度提供给一个轻量级的学习更新器，可以在Easy和Medium难度的植入团（planted clique）机制下，以最先进的性能恢复O(n²)解码。在六个真实世界图基准上的零样本评估证实，与仅使用评分的更新相比，该方法取得了持续的增益。

**研究背景与问题**
在组合算法中，许多方法具有相同的残差结构：对当前对象评分，移除或选择一个，更新剩余实例，并重复此过程。当所维护的统计量具有局部更新规则时，该循环是高效的。度（degree）是典型例子：删除一个顶点后，每个存活的度根据一个依赖于局部邻接关系的修正量进行变化，因此所有度可以在O(n)时间内更新，整个稠密图删除循环的成本为O(n²)。本研究聚焦于最大团（Max-Clique）问题的残差解码：给定一个图，找出一个最大的两两相邻的顶点集合。该问题是NP难的，其最坏情况近似也是困难的。然而，实用算法和启发式方法通过分支定界、贪婪剪枝、局部度优化、用于平均情况恢复的谱方法以及连续化公式等来利用结构。在本研究使用的植入团（planted clique）设定中，一个团被隐藏在一个随机背景图中；解码器必须在剪枝过程中保留植入的顶点以恢复它。

图神经网络（GNN）为这些人工设计的评分启发式方法提供了学习的类比。先前的可解释性工作表明，对于最大团问题，GNN的排序通常坍缩为类似度的概念。这引发了一个简单的希望：用学习到的GNN评分替换人工设计的残差统计量，并保持相同高效的删除循环。障碍在于更新兼容性。经典的统计量（如度）在删除下是加性变化的，但经过非线性层的GNN评分则未必。底层统计量的等量变化可能导致评分的不等量变化，因此在删除后，通常无法通过固定的局部修正来更新评分。标准的自适应替代方案是在每个残差图上重新运行完整的GNN，这能提供新的评分，但将解码成本从O(n²)提高到O(n³)。这引出了核心问题：学习的残差解码器能否在恢复经典残差算法O(n²)更新结构的同时，匹配每次删除后重新运行GNN所获得的解质量？

**研究内容与意义**
本论文发表在《Mathematics》期刊上，研究人员提出了一种用于最大团问题的更新兼容的神经残差解码器。其主要贡献是将学习评分与维护的残差状态分离开来。原始评分并非可靠可更新，但团目标函数在概率空间中的梯度是可更新的：删除一个顶点后，每个存活的梯度坐标通过局部修正进行变化。因此，研究人员将缓存的、增量维护的梯度输入到一个轻量级更新器中。该更新器仍然学习如何修改评分，但它作用于一个实时的残差信号，而不仅仅是过时的非线性评分。该方法的核心在于，概率空间团梯度g(p)在每次删除后允许精确的局部更新，这使得通过缓存的充分统计量以O(n)时间维护成为可能，从而在初始GNN传递后恢复了O(n²)的总解码成本。

**关键技术方法**
研究人员提出了可更新的最小概率移除（U-LPR）解码器，它运行GNN一次，并通过一个轻量级学习更新器来更新评分。研究比较了仅使用评分的更新器（SGNN + U）与注入梯度的更新器（SGNN + GU），并使用自模仿训练（SIT）对两者进行训练，其中学生模仿一个基于重新运行的教师。SGNN直接使用骨干网络的评分，SGNN + U添加了一个没有梯度信息的增量评分更新器，而SGNN + GU为更新器提供了缓存的残差梯度——这是实现O(n²)解码的、可局部维护的信号。模型架构基于标准消息传递神经网络（MPNN），包含L层，隐藏维度为64，并使用tanh激活函数。输入特征是标量的存活指示符；不提供度、团成员或结构特征。SGNN + U和SGNN + GU添加了一个轻量级多层感知机（MLP）更新器f_θ，它在每次删除顶点v后修正存活的评分。对于SGNN + GU，更新器的输入包括缓存的梯度通道g(p)_i，该梯度通过缓存的充分统计量以O(n)每次删除的成本进行维护。所有模型都使用无监督团目标函数进行训练，并通过自模仿训练（SIT）进行监督，其中基于重新运行的教师为学生的增量解码器提供模仿目标。评估在合成植入团实例和六个真实世界图基准（来自Shoham等人）上进行，采用零样本评估。

**研究结果**
**5.1. 设置**：实验在n=200的植入团实例上进行，硬件配置和软件环境如文中所述。SGNN骨干网络的性能与Min等人及Karalias和Loukas的方法相当，因此作为代表性基线。

**5.2. 主要结果**：表3展示了主要恢复结果比较。在Easy和Medium机制下，SGNN + GU结合SIT训练和U-LPR解码器是唯一一个在保持O(n²)解码成本的同时，匹配重新运行基线的近似比、重叠率和精确恢复率的条目。具体而言，在Easy机制下，SGNN + GU+SIT U-LPR实现了1.00的近似比、1.00的重叠率和1.00的精确恢复率；在Medium机制下，实现了0.99±0.01的近似比、0.99±0.01的重叠率和0.99±0.01的精确恢复率。而仅使用评分的更新器SGNN + U在Medium机制下，近似比下降至0.89±0.02。重新运行解码虽然强大但成本高昂，其成本为O(n³)，在n=200时耗时显著更长（见表4）。梯度通道被证明是经验上关键的：移除梯度会使SGNN + U无法在Medium实例上维持重新运行质量的U-LPR解码。在Hard机制下，所有解码器和基线的性能都在彼此的标准差范围内，这与植入团硬度猜想一致。

**5.3. 行为剪枝诊断**：通过删除诊断测试U-LPR移除是否遵循粗略的残差低度规则。骨干网络恢复了类似度的排序（最终层对数与顶点度的绝对斯皮尔曼相关系数接近1.0）。更新器表现出低度剪枝行为：成功的更新器（SGNN + GU）防止U-LPR删除残差度过高的顶点。具体而言，SGNN + GU在约99.9%的U-LPR步骤中移除残差度处于或低于第15百分位的顶点，而SGNN + U的比率仅为约15.1%，与随机选择一致。

**5.4. 真实世界实验**：在六个真实世界基准上的零样本评估表明，SGNN + GU U-LPR在所有数据集上都显著优于SGNN + U U-LPR，证实了梯度通道对于增量解码的必要性。在四个数据集（IMDB Binary, com-youtube, com-orkut, Collab）上，SGNN + GU U-LPR接近重新运行基线的近似比。然而，在Twitter和Facebook这两个具有显著枢纽结构的数据集上，仍存在质量-效率差距。

**讨论与结论**
**讨论**：本文的核心贡献并非梯度对神经解码器有用，而在于梯度允许一个有效的残差状态转移。删除顶点后，每个存活的坐标具有精确的局部修正，这使得梯度成为残差图的可维护状态变量。这一区别很重要，因为失败模式并非初始评分不佳。骨干网络学习了预期的类度排序，每次删除后重新运行GNN证实了新的神经评分可以支持强大的剪枝决策。问题在于这些评分本身并非残差统计量。一旦相关信息通过非线性激活函数表示，底层图的等量变化未必对应评分的等量变化。因此，一个评分在当前图上可能是准确的，但在下一次删除后仍不适合进行局部维护。梯度注入修复了这种特定的不兼容性。它没有使GNN更具表达力，也不仅仅是附加到更新器上的额外特征。它暴露了一个概率空间坐标，其删除动态即使在GNN评分经过非线性层后仍然是局部的。然后，学习的更新器可以作用于实时的残差状态，而不是试图从过时的激活后评分中重建缺失的修正。从这个意义上说，梯度通道是一个结构装置：它恢复了经典残差启发式方法所具有、而非线性神经评分所缺乏的局部更新特性。这也澄清了SIT的作用。重新运行教师提供了目标删除轨迹，但仅靠模仿并不能使该轨迹可维护。仅使用评分的更新器可以看到相同的教师决策但仍然失败，因为其状态没有与残差图一致地演化。有了缓存的概率空间梯度，学生获得了一个可以贯穿删除过程的坐标系。然后，SIT教导如何在该坐标系上行动；它本身并不是更新兼容性的来源。剩余的差距应以同样的术语解释。在Hard机制中，重新运行GNN可以利用对当前残差图有用但不一定被此处使用的缓存梯度捕获的信号。因此，更新兼容性不同于一般的残差智能：梯度修复了特定的非线性引起的维护问题，但它不能保证重新运行解码器可用的所有信息都已变得增量可访问。同样，在异构的真实世界图上，缓存梯度仍然有用，但未能完全弥合与重新运行解码的差距。这表明下一个问题不是是否“使用梯度”，而是哪个残差坐标对于特定的图族和目标具有正确的局部转移。

更广泛地说，这些结果提出的设计标准很简单。神经残差解码器不仅应暴露一个好的评分，还应暴露一个其含义能在残差操作中存活的状态变量。对于团目标函数，概率空间梯度满足这一标准，因为其删除更新是局部且精确的。对于其他目标函数，同样的想法应通过同样的测试来判断：所提出的信号是否具有有效的局部更新规则，或者它只是另一个信息特征？

**局限性与未来工作**：局限性包括更新兼容坐标是手动提供的；暴露有效的残差坐标不能保证SGD正确使用它；SIT具有离线蒸馏成本；O(n²)声明在Easy和Medium植入团机制中得到验证，在Hard实例和某些真实世界图上仍存在差距；设计将p视为固定参考而非演化状态。未来工作方向包括学习局部可维护坐标、研究无需重新运行教师即可使行为涌现的目标或架构、探索更短的教师范围或稀疏蒸馏、将方法扩展到其他可局部分解的目标函数，以及研究学习所有L层的完整梯度或让p演化同时保持有效缓存的方法。

**结论**（Conclusion）：本文确定了更新兼容性是神经残差解码器中与评分质量分开的一个要求。GNN可以为最大团问题学习一个信息丰富的类度排序，但由此产生的非线性评分在顶点删除后不能自动维护。注入并增量维护概率空间目标梯度提供了一个残差坐标，其删除更新是局部且精确的。经验表明，这使得SGNN + GU结合自模仿训练能够恢复二次残差解码，同时在Easy和Medium植入团实例上匹配重新运行基线，并在真实世界图上显著优于仅使用评分的增量解码。主要的设计启示是，神经组合求解器应暴露那些变化保持局部可维护的量，而不仅仅是那些在残差状态变化之前准确的评分。