1. 论文介绍
论文题目：FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
论文发表：ICLR 2023
论文领域： 图神经网络，图重连
论文背景：
2. 论文摘要
图神经网络（GNN）能够通过沿图的边缘传递消息来利用图数据的结构。虽然这允许GNN根据图结构学习特征，但对于某些图拓扑结构，它会导致信息传播效率低下和被称为过压缩的问题。最近，这与图的曲率和谱域间隙有关。另一方面，在消息传递图中添加边可能会导致节点表示越来越相似，并出现所谓的过平滑问题。我们提出了一种计算效率高的FoSR算法，通过基于谱展开向图中系统地添加边来防止过压缩。我们将其与关系架构相结合，使GNN保留了原始的图结构，并可证明地防止了过度平滑。我们通过实验发现，我们的算法在几个图分类任务中优于现有的图重新布线方法。
3. 相关工作
图卷积是一个局部操作，浅层的GNN在节点上仅仅捕获附近的节点信息。
对于有l层的GNN，每一个节点的感受野仅仅是一个以l为半径的球体。
当l取值较小时，会导致"欠覆盖"现象，这直接限制了图神经网络所能表示的函数范围。值得注意的是，具有l层的图神经网络可表示的函数，其范围仅限于通过威斯菲勒-莱曼(WL)图同构测试l步运算可计算的函数。
一个通用的解决过度挤压问题的方法是图重连。当前很多图重连方法的虽然提高了图的连通性，但是缺点是图结构的更改导致丧失了图的原始拓扑信息。在另一方面，如果增加了太多的边，则会让GNN陷入过度平滑的问题。
本文的方法是在过度平滑和过度挤压之间做一个平衡。
3.1 已有的方法
1，SDRF（stochastic discrete Ricci Flow），旨在通过添加新边来增加负曲率边的平衡福尔曼曲率。
还有一些其他方法使用其他概念的曲率来作指标的
2，G-RLEF（greedy random local edge flip），从信息论视角探讨过度挤压现象，通过图的谱间隙进行量化测量，并实证表明该方法能提升特定图分类任务的准确率。这个方法是受基于有效阻尼的边缘采样策略所启发的扩展图构造方法
3，除了图重连方法，其他例如受Transformer架构启发，为节点或边创建位置嵌入，最直接的方法是拉普拉斯嵌入方法
3.2 算法比较
FoSR方法跟其他方法的比较，通过连接图的瓶颈连接处，以优化整个图的信号传递。
3.3 本文贡献
- 1， 提出了一个全新的图重连方法，不同于过去方法仅仅修改图，本方法会对新增的边以特殊的标签标记。在保持原图的拓扑结构的同时，使用新边来提高整个图的连通性。
- 2， 提出了FoSR（First-order Spectral Rewiring），目标是优化整个图的谱间隙，来实现节点的平滑。算法通过计算一阶谱间隙的近似来添加边。
- 3，实验证明了提出方法的有效性，证明了更快的算法效率。
3.4 谱图理论
一个无向图的归一化拉普拉斯矩阵L为
$$ L = I- D{-1/2}AD $$
归一化后拉普拉斯矩阵的n个特征值为：
$$ 0 = \lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n \leq 2 $$
设1表示在每个节点上取值均为1的常函数。那么D1/21就是拉普拉斯矩阵L的特征函数，对应的特征值为0。图G的谱隙即为λ2 − λ1 = λ2。
G具有较大的谱隙说明G有良好的谱展开特性。
3.5 关系型GNN
定义一个通用的R-GNN层为
我们所考虑的所有图神经网络层类型，都将成为这种通用关系图神经网络层的特例。当仅存在单一关系（即|R|=1）时，我们就能还原出经典的非关系型图神经网络。
在第一种情况下，R-GNN层可以被定义为
其中σ是非线性激活函数，c是归一化因子，W是关系型映射权重
第二种情况是
第三种情况是
3.6 GNN的关系重构
为重新连接的边添加独立权重，可使网络在学习适当平滑率时获得更大灵活性。
对于原始图G=(V, ε1)，重连后的图为G‘=(V, ε1 U ε2)，原始的边ε1的类型为1，添加的边ε2的类型为2，那么层的表达式为
原始的图只包含前两项，图重连后的图会包含第三项，但会使用相同的权重 W2=W1。
关系型GNN可以提供更多的灵活性，在最坏的情况下，如果我们添加过多边线，图神经网络（GNN）可能会通过将大部分权重W2(k)设置为0来抵消这种影响，从而将其注意力集中在原始图上。
3.7 R-GCN图重连的平滑率
一个图有着高谱间隙那么意味着有着高的Cheeger常数。根据定义，向图中添加边会提高其Cheeger常数。
在极端情况下，把一个图变为完全图，GCN层捕获到的每个节点的特征会高度一致。
定义1：迪利克雷能量函数
对于一个标量场f 属于R，迪利克雷能量函数为
那么对于一个向量场X，有
图节点上单位范数函数的狄利克雷能量，是衡量其“非平滑”程度的指标。
定义2，图G的平滑率
上述分数的分子表示应用映射φ时狄利克雷能量的衰减（或扩张）速率。我们对X取上确界，以找出应用φ时能量可能发生的最大相对变化。同时希望我们的平滑速率定义具有尺度不变性——将φ乘以标量不应改变其平滑速率。为实现尺度不变性，我们在分母中除以一个反映φ对X各条目缩放程度的因子。通过将平滑速率定义为两种范数的比值，我们可以分别估算它们，这为平滑过程提供了良好的理论把控。
以下定理表明，R-GCN层能够灵活地为图选择适当的平滑速率
4. FoSR 一阶谱重连
谱扩展率，即谱间隙随重连迭代次数改善的速率，是决定过度挤压现象的关键因素之一。FoSR算法通过添加边的方式来优化图的谱间隙，从而最大化谱扩展率。
在算法的每一步迭代中，我们希望加入的边可以最大化谱间隙，但是计算每一条边的谱间隙就需要去计算整个矩阵的特征值，计算量很大。所以采用基于矩阵扰动理论的一阶近似方法来计算谱间隙，而非直接求解该量。
定理4确定了扰动对称矩阵特征值的一阶变化：
根据定理可以有图特征值的线性近似
我们的目的是为了添加边后可以最大化谱间隙，所以第二大的特征值应该尽可能小。
那么一阶的改变在第二大的特征值为
在上面的式子中可以选择最小化第一项（因为更为简单和低计算量）
所以总结下来，FoSR算法的每一次迭代，通过计算第二大特征值对应的特征向量x，选择一个边能够最小化
所以每次迭代x的映射如下，以此来不断近似
算法流程
其中k和r是超参数。r需要足够大才能够产生一个初始近似值，经验值是5到10的范围。
5. 实验设置
本文主要考虑在图分类任务上，采用的数据集来自TUDataset的 REDDIT-BINARY，IMDB-BINARY，MUTAG，ENZYMES，PROTEINS和COLLAB
比较的方法有：DIGL，SDRF，全邻居层算法，三个核心的图重连算法
实验效果如下
6. 总结
算法的图重连核心是保留原有的拓扑结构，以增大平滑率为目标的算法。通过定义平滑率，并把谱间隙和平滑率联系起来，最后将优化目标落实到具体的近似迭代步骤中。