论文题目：Understanding Oversquashing in GNNs through the Lens of Effective Resistance
论文领域：图神经网络，图重连算法
论文发表：ICML 2023
论文背景：
消息传递图神经网络（GNNs）是一种流行的图结构数据学习结构。然而，GNN遇到的一个问题是过压缩，GNN很难在远程节点之间发送信息。理解和减轻过度压缩最近受到了研究界的极大关注。在本文中，我们通过分析输入图中节点间有效电阻透镜的过拟量来继续这一工作。有效阻力通过图中的路径直观地捕捉到两个节点之间连接的“强度”，并且在图论的许多领域都有丰富的文献。我们建议使用总有效阻力作为图中过拟总数的界，并为其使用提供理论依据。我们进一步发展了一种算法来识别要添加到输入图中的边，以最小化总有效电阻，从而减轻过拟。我们提供的经验证据的有效性，我们的总有效电阻为基础的重布线策略，以提高性能的GNNs。
有效电阻的概念源于电力工程，指的是在电路中，当在节点u注入单位电流并在节点v移除时，两个节点u和v之间的有效电阻即为u与v之间的电势差。
一条边的两个端点之间的有效电阻与该边被包含在图的一棵生成树中的概率成正比。更形象的是：有效电阻与描述图瓶颈的图Cheeger常量更类似。由于其与众多其他对象（如随机游走和拉普拉斯算子）的多种关联，有效电阻在实践中得到了广泛应用。
总而言之，有效电阻是描述两个节点的连接程度的度量。在GNN中，有效电阻值也可作为衡量节点间信息挤压程度的边界指标。当两个节点间的有效电阻值越低时，图神经网络在这些节点间传递信息时所遭遇的信息挤压效应就越微弱。
1，给出了有效电阻这个指标来衡量过度挤压问题，
2，理论证明了通过图神经网络的任意层数从一个节点传递到另一个节点的信息量，其上限与节点间的有效电阻相关。
3，使用总的有效电阻作为一个整体过度挤压的度量，并提出基于此指标的图重连算法
4，用实验证明了本文算法的有效性
在图结构重连过程中，底层图的结构将被改变。为了保留原始图的信息并充分利用图重连产生的新图结构，我们采用关系型图神经网络来兼容这两种信息R。
R-GNN网络的输入输出可以为
其中ϕ和ψ都是可学习的函数
有效电阻的定义，两个节点uv之间的有效电阻可以为
其中$1_v$是顶点v的指示向量，$L^+$是L的伪逆矩阵。
同样的，有效电阻也可以使用归一化的拉普拉斯矩阵来表达
总之，节点uv两者的路径越多越短，其有效电阻则越小。
GNN的雅可比范式的的上界是归一化邻接矩阵的多次幂。
基于上面的定理3.2可以给有效电阻一个新的边界
上面的不等式在雅可比和邻接矩阵的多次幂建立联系，那么需要在邻接矩阵多次幂和有效电阻建立联系
拉普拉斯的伪逆矩阵在非二部图中可以为
所以有：
总的有效电阻 $R_{tot}$为一个图中所有节点对的有效电阻的总和。
总有效电阻限定了图中所有顶点对之间雅可比矩阵之和的上界
有效电阻是面对全局的，而曲率是针对局部，如下图，ab和uv有着同样的曲率，但有效电阻不一。
节点u与v之间的过度挤压现象也可以通过通勤时间τ(u,v)，即在随机游走中从u出发到v再返回u的预期步数来界定。
通勤时间与有效电阻呈正比关系，两项研究还采用了类似的技术手段将有效电阻/通勤时间与图神经网络的雅可比矩阵相关联。
两者主要差异源于：（1）所界定量的不同（两者均与图神经网络雅可比矩阵相关）；（2）对图神经网络假设条件的不同。
理论证明了节点间的最坏情况有效电阻与谱隙成正比关系。
和
图的过度挤压行为不仅与谱间隙相关，更与拉普拉斯算子的整个谱系紧密相连。因此，提升拉普拉斯算子的整个谱系（而不仅仅是谱间隙）可能进一步缓解过度挤压现象。
首先是推导一个公式来确定添加特定边能在多大程度上降低总电阻，然后基于公式来增加新的边以最小化整体有效电阻。
首先引入双调和距离，u和v之间的双调和距离定义为
根据定义有，节点u与v之间的双调和距离平方与总电阻对该边权重的偏导数成正比。
所以有理论
给图添加边后，整个拉普拉斯也会发生变化。从L到L+(1u-1v)(1u+1v)^T的变化。
有引理
根据上面的可以得到
下图展示了在不同形态的图下边的对应的值的变化。
全称是基于贪心的全局有效电阻算法Greedy Total Resistance
根据定理4.1，每次不断加边以最大化变量。
对于不连通的图而言，不同连通分量中顶点间的有效电阻和双调和距离并不具备实际意义。因此，我们仅会在已属于同一连通分量的顶点之间添加边。
添加多条边，定理4.1只表述了找到一条边可以最大减少总的有效电阻。但也给出一些例子说明了添加多条边会更优的情况，添加边和减小总电阻的关系并不是单调的。最好的方式则是利用全局暴力搜索。
先来看FoSR和GTR在谱间隙和总的阻尼的变化，数据集基于Cora。
任务是基于图分类任务，数据集全部来自TUDataset，基座模型采用GCN，R-GCN，GIN和R-GIN
实验结果为
def compute_edges(self, num_edges : int) -> torch.Tensor:
""" Calculate edges to add to the graph using the GTR heuristic. """
ret_edges = torch.zeros((2,0), dtype=torch.long)
for _ in range(num_edges):
# The entries resistance_matrix[s,t] and biharmonic_matrix[s,t]
# are the effective resistance and biharmonic distance between s and t.
pinv_diagonal = torch.diagonal(self.pinv)
resistance_matrix = pinv_diagonal.unsqueeze(0) + pinv_diagonal.unsqueeze(1) - 2*self.pinv
squared_pinv_diagonal = torch.diagonal(self.squared_pinv)
biharmonic_matrix = squared_pinv_diagonal.unsqueeze(0) + squared_pinv_diagonal.unsqueeze(1) - 2*self.squared_pinv
# diff_matrix[s,t] stores the change in total resistance when the edge {s,t} is added to the graph
diff_matrix = (biharmonic_matrix / (1 + resistance_matrix))
# We only want to add an edge not already in the graph and not between connected components.
# Multiplying by edge_mask sets the value of all self-loops
# and edges already in the graph to 0.
# Multiplying by component_mask sets the value
# of all edges between connected components to 0.
masked_diff_matrix = diff_matrix * self.edge_mask * self.component_mask
# Find the endpoints of the edge that most decrease the total resistance.
# torch.argmax returns the index of max in flattened coordinates, hence the divmod.
s, t = divmod(torch.argmax(masked_diff_matrix).cpu().item(), self.data.num_nodes)
# Add the edge {s,t} to the return array
new_edges = torch.Tensor([[s, t], [t, s]]).long()
ret_edges = torch.cat([ret_edges, new_edges], 1)
# Update the matrices for the next iteration
self.update_pseudoinvere(s, t)
self.update_squared_pseudoinverse(s, t)
self.update_laplacian(s, t)
self.update_edge_mask(s, t)
return ret_edges
围绕着有效电阻为核心，同时充分对比了其他同样描述邻接矩阵的连接特征的属性，如曲率，谱间隙，针对全局有效电阻来设计一个简单可行的GTR算法，重在分析。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。