关于图神经网络中联合图重连与特征去噪新方法的学术研究报告
本文档介绍了一项发表于国际机器学习顶级会议ICLR 2025的原创性研究。该研究由来自瑞士巴塞尔大学数学与计算机科学系的Jonas Linkerhägner、Cheng Shi和Ivan Dokmanić共同完成。论文标题为《通过谱共振进行联合图重连与特征去噪》（Joint Graph Rewiring and Feature Denoising via Spectral Resonance）。
一、 研究背景与目标
本研究隶属于图机器学习领域，特别是图神经网络（Graph Neural Networks, GNNs）的预处理与性能优化方向。GNNs在处理图结构数据（如社交网络、引用网络、蛋白质相互作用网络）方面取得了巨大成功，广泛应用于节点分类、链接预测等任务。然而，现实世界中的图数据通常包含噪声：图结构（邻接矩阵）可能存在虚假或缺失的边，而节点特征也可能不准确或不完全与节点标签相关。这种噪声会严重损害下游GNN模型的性能。此外，即使图结构正确反映了真实交互，其几何特性（如瓶颈结构）也可能阻碍GNN中的消息传递过程，导致“过挤压”（oversquashing）或“过平滑”（oversmoothing）问题。
现有的图重连（Graph Rewiring）方法主要分为两类：预处理方法和端到端方法。预处理方法（如基于曲率、谱间隙的方法）在训练前修改图结构以改善信息流动的几何特性，但大多忽略了节点特征信息。端到端方法在训练过程中动态调整图结构，虽然利用了特征，但通常不输出一个改进后的、可解释和可复用的图。另一方面，图结构学习（Graph Structure Learning）方法通常假设对干净图进行对抗性扰动，而非处理原始数据中固有的噪声。
本研究团队观察到，在图数据中，图结构和节点特征都提供了关于节点标签的、带有噪声的信息。他们提出了一个核心问题：能否通过一种简单、联合的特征和图去噪方法来提升下游GNN的性能？为此，他们从上下文随机块模型（Contextual Stochastic Block Model, CSBM）这一经典生成模型中获得启发。在CSBM中，理论和实践均表明，联合利用图结构和特征信息进行社区检测，其效果优于单独使用任何一种信息。然而，基于CSBM的推断算法（如信念传播）依赖于对模型分布的完美已知，难以应用于复杂的真实世界数据。
因此，本研究的目标是设计一种实用的、基于谱对齐思想的算法，能够联合进行图重连和特征去噪，从而提升任何下游GNN在真实世界节点分类任务上的性能。该方法的核心思想是：通过调整图和特征，最大化它们各自主导特征子空间之间的对齐程度，当对齐度高时，称图和特征处于“谱共振”（Spectral Resonance）状态。
二、 研究方法与流程
本研究提出了一种名为“联合去噪与重连”（Joint Denoising and Rewiring, JDR）的新算法。其核心工作流程是一个迭代优化过程，旨在近似求解一个非凸的谱对齐最大化问题。具体步骤如下：
问题形式化与对齐度量定义： 研究首先定义了图-特征对齐（Graph-Feature Alignment）的度量。给定图邻接矩阵 (A) 和节点特征矩阵 (X)，设其谱分解分别为 (A = V \Lambda V^T) 和 (X = U \Sigma W^T)。令 (V_l) 和 (U_l) 分别代表 (A) 和 (X) 的前 (l) 个特征向量/左奇异向量构成的矩阵。对齐度定义为这两个子空间之间夹角的余弦值：(\text{alignment}_l(A, X) = |V_l^T Ul|{sp})，其中 (|\cdot|_{sp}) 表示谱范数。对于具有 (k) 个类别的数据，通常取 (l = k)，因为标签信息主要蕴含在这些主导谱成分中。
JDR算法流程： 直接最大化上述对齐度量是计算困难的。JDR采用了一种启发式的交替优化算法，包含三个核心步骤，迭代执行 (k) 次：
- 步骤1：分解：计算当前图 (A) 和特征 (X) 的谱分解（特征值分解和奇异值分解），得到特征向量矩阵 (V)、(U) 及对应的特征值/奇异值。
- 步骤2：插值（对齐）：对于前 (l) 个主导成分，进行相互引导的插值更新。
- 更新图的第 (i) 个特征向量：(\tilde{v}_i = (1 - \eta_a) v_i + \eta_a \cdot \text{sign}(\langle v_i, u_j \rangle) u_j)。
- 更新特征的第 (i) 个左奇异向量：(\tilde{u}_i = (1 - \eta_x) u_i + \eta_x \cdot \text{sign}(\langle u_i, v_j \rangle) v_j)。 其中，(j) 被选为与当前向量最相似（内积绝对值最大）的对应矩阵中的向量索引。超参数 (\eta_a) 和 (\eta_x) 控制着从对方谱信息中汲取信息的强度，通过在验证集上优化下游GNN性能来确定。
- 步骤3：合成：使用更新后的特征向量和奇异向量，结合原始的特征值/奇异值，重新合成新的加权稠密图 (\tilde{A} = \tilde{V} \Lambda \tilde{V}^T) 和新的特征矩阵 (\tilde{X} = \tilde{U} \Sigma W^T)。
- 迭代与后处理：将新合成的 (\tilde{A}) 和 (\tilde{X}) 作为下一轮迭代的输入。迭代结束后，通常对 (\tilde{A}) 进行稀疏化处理（例如，保留每个节点权重最大的前几条边），以便高效应用于GNN。
理论验证： 为了给JDR提供理论依据，研究团队在一个简化的生成模型（用高斯正交系综噪声替代CSBM中的二进制噪声）下进行了分析。他们提出了一个命题并给出了证明（详见附录）：在一定的信噪比条件下，存在正的插值参数 (\eta_a, \eta_x)，使得经过JDR一步迭代后，图的主特征向量和特征的主左奇异向量与真实标签向量的对齐程度（以平方内衡量）几乎必然（almost surely）得到提升。这为JDR能够通过迭代改善与标签的对齐提供了理论支持。
实验设计与评估： 研究进行了广泛的实验来验证JDR的有效性、鲁棒性和可扩展性。
- 研究對象：
- 合成数据：基于CSBM生成的数据，可以精确控制图与特征的信号噪声比（SNR）以及同配性（homophily）/异配性（heterophily）水平（通过参数 (\phi) 调节）。
- 真实世界数据：包括5个同配性数据集（Cora, Citeseer, PubMed, Computers, Photo）和5个异配性数据集（Chameleon, Squirrel, Actor, Texas, Cornell），以及3个大型异配性图（Questions, Penn94, Twitch-Gamers）。
- 对比基线：与当前先进的预处理图重连方法进行比较，包括：基于扩散的DIGL（扩散改进图学习）、基于谱间隙的FOSR（一阶谱重连）、基于曲率的BORF（批量Ollivier-Ricci流）。在CSBM上，还与理论上最优的近似消息传递-信念传播（AMP-BP）算法进行了对比。
- 下游模型与评估指标：使用两种代表性的GNN作为下游模型：经典的图卷积网络（GCN）和更广义的PageRank GNN（GPRGNN）。采用节点分类准确率作为主要评估指标，并报告多次随机数据划分下的平均准确率和95%置信区间。
- 实验流程：
- 在CSBM数据上，系统地在不同 (\phi) 值下运行JDR及基线方法，观察对齐度量的变化以及下游分类准确率的变化，验证JDR的去噪和重连能力。
- 在真实数据集上，按照标准稀疏划分（2.5%/2.5%/95%用于训练/验证/测试）或稠密划分（60%/20%/20%），分别评估同配性和异配性图上的性能。
- 在大型图上测试JDR的可扩展性。
- 通过网格搜索和随机搜索在验证集上优化JDR的超参数（(\eta_a, \eta_x, l, k) 等）。
三、 主要研究结果
在CSBM上的验证：
- 对齐度提升：实验证实，运行JDR后，图与特征之间的对齐度量 (\text{alignment}_l(A, X)) 在所有 (\phi) 值下均得到显著提升（图3）。这表明算法有效实现了其设计目标。
- 性能提升：在广泛的 (\phi) 设置下（从强异配性到强同配性），JDR都能显著提升下游GCN和GPRGNN的分类准确率（图4）。特别是在“弱图区域”（(|\phi| \leq 0.25)，即图信号很弱时），JDR帮助GNN的性能大幅提升，几乎追平了需要知道数据生成分布的AMP-BP算法，并显著超越了仅使用特征的MLP基线。这表明JDR能有效利用特征信息来补强噪声图，反之亦然。
在真实世界数据集上的性能：
- 同配性图：如表2所示，JDR在Cora、Citeseer、PubMed、Photo四个数据集上取得了最佳平均准确率。在Computers数据集上，DIGL表现略优，但JDR仍具竞争力。总体而言，JDR相比原始GCN和GPRGNN以及FOSR、BORF等基线带来了稳定且显著的提升。
- 异配性图：如表3所示，JDR的优势更为明显。在Chameleon、Squirrel、Actor、Cornell数据集上，JDR（尤其是结合GPRGNN时）取得了最佳性能。在Texas数据集上，GPRGNN+JDR也达到了最优。值得注意的是，DIGL因其同配性假设在部分异配性数据集上表现不佳甚至有害，而BORF则因计算复杂度高在Squirrel数据集上内存溢出（OOM）。JDR则能有效处理异配性。
- 大规模图：如表4所示，在包含数万到数十万节点的大规模图上，JDR依然能够有效运行并带来性能提升，而BORF因复杂度问题无法运行，DIGL和FOSR的提升有限或为负。这证明了JDR具有良好的可扩展性。
与现有方法的比较： JDR在大多数数据集和设置下都优于或与其他最佳方法持平。研究指出，JDR是首个联合利用图结构和节点特征进行预处理重连和去噪的方法。与仅基于图几何性质的重连方法（FOSR, BORF）相比，JDR通过特征引导的重连直接针对数据噪声。与端到端方法相比，JDR能输出一个改进后的、可解释和可复用的图。与图结构学习方法相比，JDR专注于处理真实数据中固有的噪声，而非对抗性扰动。
四、 研究结论与意义
本研究得出结论：谱共振是构建图重连（和特征去噪）算法的一个强大原理。基于此原理提出的JDR算法，通过迭代地对齐图和特征的领先谱空间，能够有效地对两者进行联合去噪与重连。
科学价值：
- 提出了新的问题视角：将图重连问题从纯粹的“改善计算图几何”视角，部分地转向了“数据去噪”视角。实验结果暗示，对于现实世界图数据，噪声（缺失和虚假连接）可能是限制GNN性能的更重要因素。
- 建立了理论与实践的桥梁：从CSBM的理论分析出发，设计了具有理论动机（谱对齐最大化）的实用算法，并在简化模型下提供了理论保证。
- 引入了“谱共振”概念：为理解和优化图与特征的协同作用提供了一个新颖的、可量化的框架。
应用价值：
- 通用且有效的预处理工具：JDR可以作为一个即插即用的预处理模块，与任何下游GNN模型结合，在广泛的同配性和异配性图数据上稳定提升节点分类性能。
- 可解释性与可复用性：与端到端方法不同，JDR输出一个经过改进的图，可供进一步分析和不同模型使用。
- 良好的可扩展性：通过截断谱分解，JDR能够处理大规模图数据。
五、 研究亮点与创新点
- 核心创新：首次提出了联合进行图重连与特征去噪的预处理框架，并创新性地使用谱对齐（谱共振） 作为联合优化的目标。
- 算法设计：设计了一种简单而有效的交替插值-合成算法（JDR）来近似求解谱对齐最大化这一非凸问题，并引入了处理符号模糊性和子空间旋转的启发式策略。
- 理论支撑：在简化的生成模型下，为算法能够提升与真实标签的对齐性提供了理论证明，增强了方法的可信度。
- 实证全面性：在从合成到真实、从同配到异配、从小型到大规模的一系列数据集上进行了全面评估，证明了方法的有效性、鲁棒性和通用性。
- 启发性发现：实验结果表明，对于现实图数据，去噪可能是比改善几何特性更关键的环节，这为未来图重连研究提供了新的方向。
六、 局限性与未来工作
作者也指出了JDR的局限性及未来方向： 1. 依赖节点特征：JDR需要节点特征作为输入，无法应用于仅有图结构的数据。这是其与特征无关的重连方法相比的一个限制。 2. 任务局限性：目前JDR主要针对节点分类任务，如何将其扩展到图级别任务（如图分类）是一个开放问题。 3. 与几何重连的结合：作者尝试但未能成功地将JDR与基于几何的（如曲率）重连方法有效结合。探索一种能同时受益于“去噪”和“改善计算流”的混合方法是有趣的未来方向。 4. 超参数调优：JDR包含几个超参数（如 (\eta_a, \eta_x, l, k)），需要通过验证集进行调整，增加了使用成本。
这项研究为图神经网络的前处理提供了一种新颖、强大且理论基础扎实的工具，通过促进图与特征之间的谱共振，显著提升了模型在各种复杂图数据上的学习能力。