1. 论文介绍

论文名字：Joint Graph Rewiring and Feature Denoising via Spectral Resonance
论文发表：ICLR 2025 oral
论文领域：图神经网络
论文背景：

2. 论文摘要

本文提出了一种联合去噪和重布线图（JDR）算法，提高了下游节点分类图神经网络（GNN）的性能。JDR的工作原理是对齐图和特征矩阵的前导谱空间。它近似地解决了相关的非凸优化问题的方式，处理多类和不同层次的图的同胚或异胚。我们从理论上证明JDR在一个程式化的设置和显示，它始终优于现有的重新布线方法在广泛的合成和现实世界的节点分类任务。

3. 相关工作

最近的一些工作证明了对图进行适当的增减连接边会提高下游GNN的表现。在GNN中，图不仅仅做的是编码点的交互状态，而且也会承担信息传递计算。在很多时候，交互和信息传递是两个独立的概念，即使图有了正确的交互，图也不是一个在信息传递有足够效率的。

基于上面的观察，得到了GNN的两个机制：

• 1，真实世界的图是存在着噪声的，不正确的连接边
• 2，图的几何属性会妨碍图的信息传递

3.1 图重连接

针对图的几何属性会妨碍图的信息传递的问题，当前很多方法解决这个为图重连接方法。可分为预处理方式和end-to-end方式。
预处理方式会基于几何属性或谱属性来对图进行重连接。包含图弯曲，图扩展，基于扩散的图重连接（使用扩散核来平滑图）；
end-to-end方法中，早期的方式使用丢弃边来减少过度平滑，接着的是在训练过程中使用潜在特征来动态重新连接图。这种方法不能输出改进后的图，限制了其解释性和可复用性。

3.2 图去噪

目前有很多方法是使用图滤波器对图进行去噪。本文聚焦在修改图层面，借用了ESNR评价方法来衡量图的噪声。

3.3 图结构学习

本算法不是为了识别出噪声，而是主动承认现实数据是存在噪声的。

3.4 图正则化

源自半监督学习的拉普拉斯正则化，是在GNN训练过程中加入一个额外的关于图结构的loss来防止过度平滑。这个的主要限制是潜在的同源性假设，默认有连接的节点更有可能有着相同的标签。

4. 本文贡献

• 1，基于cSBM的灵感，设计了联合图重连接方法和特征去噪方法
• 2，本文设计了一个交互式优化算法，联合去噪和重连接方法JDR，在图级和特征之间近似最大化对其，在真实的复杂的图数据上，包括同质的和异质的。
• 3，进行实验，证明了JDR比现存的预处理重排线策略更加优秀

5. 前置知识

在无向图的特征谱域中，特征分解

和奇异值分解（singular value decomposition）SVD

将分解得到的特征值从大到小排序，是异亲图中我们得到的特征值的绝对值。
同亲图指的是节点更有可能和与其相似或者相同属性的节点连接；
异亲图是节点更有可能跟与其属性不同的节点连接

上下文随机块模型Contextual Stochastic Block Model。CSBMs方法是继承自SBMs，通过CSBMs方法来生成图。节点之间的连接是随机且独立的，有Cin/N的概率是类内连接，Cout/N的概率是跨类连接。
把节点的平均度数定义为d，那么类内类间连接的概率为：

和

其中参数入可以视为是图的信噪比SNR（signal-to-noise）
生成的最终的为：

使用A和X的信息来相互加强

图的特征对齐为，A和X对应分解隐私的谱范式。

所以，最终的优化问题变为：

6. 本文算法

我们提出了一种启发式方法，在谱插值和图综合之间交替优化。也证明了该算法能够提高对齐。
算法演示图

整个算法分为三个步骤不断循环，直到符合退出条件
步骤1： 对邻接矩阵A 和 特征矩阵 X，进行谱分解

步骤2：对图拉普拉斯矩阵L进行最大特征值的插值

步骤3：基于上面的u和v来合成新的图

步骤4：不断迭代1-3步骤，直到符合

算法的伪代码如下

算法解释
用了一个简单的例子来说明，当A或者X包含了所有的信息，只需要优化对应的u和v
JDR方法提高了对齐。

7. 实验设置

使用GCN作为基础的下游GNN模型，为了验证在复杂图上效果，还在最新的GPRGNN上进行测试。
对比的当前最优的预处理重连接技术

cSNB在对齐的作用，从图上可以发现有了很大的改观。

不同的cSBM的阈值下的JDR的表现，JDR显著提高了GNN的表现。

JDR算法和其他现存最优算法的对比，也体现了JDR算法的优越性。

8. 总结

作者拿cSBM算法结合图的重连接来做预处理环节，给出了详细的数学证明和实验证明，这是论文的关键。