1. 论文介绍
论文题目：An Empirical Evaluation of Rewiring Approaches in Graph Neural Networks
论文邻域：图神经网络，图重连
论文发布：Pattern Recognition 2025
论文背景：
2. 论文摘要
图神经网络通过执行多个消息传递步骤来计算节点表示，这些步骤包括节点特征的局部聚合。拥有可以利用节点之间长距离交互的深度模型会受到过度平滑和过度压缩问题的阻碍。特别是，后者归因于引导消息传递的图拓扑，导致节点表示对远处节点包含的信息变得不敏感。已经提出了许多图重新布线方法来补救或缓解这个问题。然而，由于过度压缩与其他与模型训练严格相关的问题（如梯度消失）的耦合，很难正确评估这些方法的好处。因此，我们提出了一种基于消息传递模型的评估设置，该模型不需要训练来计算节点和图表示。我们对真实世界的节点和图分类任务进行了系统的实验比较，表明重新连接底层图很少能为消息传递带来实际好处
3. 相关介绍
当图重连接给训练过的GNN中表现更好的性能时候，不清楚这个改进的是否来源于
1，由于改进的图结构带来的更好的消息传递
2，与训练相关的效应，例如梯度流的改变
3，隐式正则化效应
4，更好的超参数
4. 图重连算法介绍
本文将图重连技术的主要分为以下五类，基于扩散过程，基于曲率的方法，基于谱间隙的方法，基于扩展器传播，基于有效阻尼的方法。
4.1 图扩散模型
图扩散最初是作为一种聚合超越直接1跳邻域节点的方法提出的，这使得单个消息传递层能够直接考虑来自更远节点的信息。
一般的图扩散矩阵是幂级数
其中A是转移矩阵
两种图扩散方法，其中热核和PPR方法的转移矩阵为
4.2 局部图瓶颈
在过度挤压的分析中，图拓扑产生了局部的树形则表示局部图瓶颈。为了衡量局部拓扑结构的指标，有平衡Forman曲率
4.3 全局瓶颈
等式4的曲率不仅仅可以衡量图拓扑结构的瓶颈，更全局的指标，Cheeger常量h_G，可以描述边的最小曲率分数。但是计算Cheeger常量是一个NP难问题。
GRLEF方法是旨在提高整个图的谱间隙。
4.4 扩展器传播方法
为了避免图瓶颈的出现，通过重新构造图来实现。
EGP方法基于有限图的Cayley图来作为新的扩展器，是4-regular的，稀疏的。
4.5 有效阻尼方法
该方法提供了另一种衡量图拓扑结构瓶颈的方法，两个节点之间的阻尼可以视为uv的交流跳跃数
4.6 GNN模型
使用无需训练的GNN模型，直接将图拓扑对消息传递的影响和训练相关的复杂性分离开来。
简化图卷积SGC，该模型移除了消息传递层中的所有非线性和可学习参数，将节点表示为
图回声状态网络，基于水库计算RC原理，使用随机初始化，固定的内部权重，同时只训练一个简单的线性读出层，模型计算为
读出层Readout layer
为了解决下游模型的分类任务，还是需要去训练一个预测器，本文使用线性readout层
5. 实验设置
使用不同的图重连算法，结合非训练的GNN模型。本文实验的目的是检验不同重连算法在不同视角下的表现。
任务分为两类，节点分类和图分类，采用的数据集的属性为
在对比来自五类的6种算法，节点分类的效果为
各大算法的计算复杂度
6. 结论
原来的名字起得比较大，Is Rewiring Actually Helpful in Graph Neural Networks，直接否定graph rewiring这个领域。后面改温和一点才被PR接受。
对GNN图重连线技术的未来发展的建议：1，重新思考图重连技术；2，训练鲁棒性；3，免训练基线