论文题目：Oversquashing in GNNs through the lens of information contraction and graph expansion
论文核心算法：G-RLEF
论文领域：图神经网络
论文发表：58th Annual Allerton Conference on Communication, Control, and Computing
论文背景：
消息传递图神经网络（GNNs）中信号传播的质量对其表达能力有很大的影响。特别地，对于依赖于远程交互的预测任务，节点特征的递归聚合可能会导致称为“过拟”的不期望的现象。本文提出了一个基于信息压缩的过拟分析框架。我们的分析是由一个可靠的计算模型，由于冯诺依曼借出了一个新的洞察过拟作为信号熄灭在噪声计算图。在此基础上，我们提出了一个图重布线算法，旨在减轻过拟。我们的算法采用了一个随机的局部边缘翻转原语的动机扩展图建设。我们比较了我们的算法与现有的基于曲率的非局部重布线策略的谱扩展特性。综合实验表明，虽然我们的算法通常具有较慢的扩展速度，但总体计算成本较低，能够准确地保留节点度，并且不会断开图。
1，提出一个用于分析图神经网络中过度挤压导致信息衰减的框架，并证明信息渗透边界（定理3）如何捕捉过度挤压现象的本质——即噪声计算图中的信号淬灭。
2，提出了一种新的局部图重连算法G-RLEF，构思来源于扩展图构造。实验证明了算法的效果，同时G-RLEF保持节点的度且不会断连图。
基于新理论来理解过度挤压，信息论下的过度挤压问题
将GNN和冯诺依曼的噪声布尔电路模型进行类比，在两种情况下，信息都必须经过一系列计算步骤，这些步骤可能引入噪声并导致信号衰减，正如布尔电路中的噪声门会导致信息随着电路深度呈现指数级损失，GNN的消息传递层也可能会导致来自远距离的节点的信号衰减消失。
用信息论和扩展图理论的工具来更好的解释图的过度挤压问题。
噪声图中的信息计算瓶颈：
在信息论中，马尔科夫链上的互信息收缩量可通过著名的数据处理不等式进行定量捕捉。表明了信息在传导过程中的衰减。
通过引入适当的通道相关"收缩系数"来捕捉信号在噪声信道中传播时的信息损失率，可以获得这些不等式的强化版本。在过压缩问题的背景下，我们展示了噪声计算图中的信号衰减在概念上如何类似于冯·诺伊曼提出的噪声电路模型中的信息收缩现象。
扩展图上的结构瓶颈
扩展图是指具有高等周性质（图形各部分与整体保持高度连通性的数学性质）的图：图的每个部分都通过其大部分边与其余部分相连。
核心理论贡献在于将过度压缩问题定义为信息压缩问题，利用强数据处理不等式，对于具有KL收缩稀疏和最大扇入k的噪声电路，互信息边界为
对于电路中存在节点间长程依赖关系的问题，输入输出互信息值较小往往意味着信息收缩程度较高。这种现象与因过度压缩而产生的状况类似。
图的等周比概率定义为
当且仅当每个不超过半数节点的子集都具有较大的表面积体积比时，等周比h(G)才会较大。
当然，所有有限连通图对于某些β > 0都是扩展图，理论上，对于稀疏大型扩展图而言，d = O(1)且n ≫ d的情况因其极值性质而受到最广泛研究。
Cheeger常数是衡量图连接的鲁棒性程度的变量。
对于直线型的图（两端的节点度为1，其他节点度为2），其Cheeger常数为 $\frac{2}{n}$，如哑铃状的图（下图a），其Cheeger常数为$O(\frac{1}{n})$，环状的子块图，诸如路径图、哑铃图以及由m个规模为(d+1)的团通过环形连接构成的d-正则团环这类易断裂的图结构属于劣等扩展器，而完全图这类高度连通的图结构则属于优良扩展器。
根据离散Cheeger不等式，G的谱间隙和其Cheeger常数的关系有
基于扩展器的图重连算法
相较于SDRF方法，我们提出的重布线算法旨在通过仅进行局部调整来提升"全局"Cheeger常数h(G)，过程中始终保持图结构的连通性并严格保持节点度数不变；具体示意图参见图3(a)。
基础RLEF算法随机选择边进行翻转，逐渐改善图的扩展性质。虽然简单，但这种方法在实现谱间隙（图扩展的度量）的显著改进方面可能很慢。
基于”翻转马尔可夫链“的思想，将任何规则连通图以高概率转化为扩展图。
根据设计，RLEF变换保留了所有节点的度数以及连通性。对于d-正则连通输入，FlipMarkov链会收敛到连通d-正则图集合上的均匀分布。对于具有n个节点的d-正则输入图G，重复应用RLEF变换极有可能在O(d²n²√log n)步内生成一个谱扩展图。
在实验中，谱扩展在RLEF重连过程中的演变呈现出三个显著阶段，具体表现为（a）初始阶段基本没有扩张，（b）以快速扩张为特征的相对短暂中间阶段，以及（c）扩张达到饱和时的稳定阶段。
提出一种贪心版本的RLEF算法——G-RLEF，该算法通过根据"有效电阻"比例对枢纽边(u,v)进行非均匀采样，从而加速谱展开过程。
在我们的贪婪采样策略中，我们将借助物理隐喻将图视为阻力网络。对于图G同一连通分量中的任意两个顶点u和v，u与v之间的有效阻力定义为：当向其中一个顶点注入单位电流并从另一个顶点抽取单位电流时，网络所消耗的能量，其数值由以下表达式给出：
若节点u、v位于不同的连通分量中，则其关联有效电阻为无穷大。
因此，直观而言，有效电阻捕捉了边的"电气重要性"。跨越瓶颈的高电阻路径（例如图3中哑铃状图中的桥接边）具有更高的电气重要性，这类路径应以更高概率被采样。
计算有效电阻可能代价高昂。我们的贪婪采样方案转而利用边有效电阻与其反向三角形计数之间的关系。
采样机制在本质上是相似的，因为图上的曲率与三角形存在及其相对丰富度密切相关，这正是正曲率的标志特征：两个相邻节点共享的三角形数量越多，它们的邻域重叠度就越大，因此这两个节点间连边的曲率也就越大。
总的来说，增强型G-RLEF算法引入了一种贪婪采样策略以加速扩展，它与边的有效电阻成比例的概率对边进行采样，并使用逆三角形计数作为有效的代理。三角形数量较少的边更有可能被选中进行重新连接。
该算法还通过最小化三角形计数的净变化来优化选择用于翻转的特定节点，利用了三角形减少与谱扩展之间观察到的相关性。
图4显示谱扩展过程与三角形消除过程密切相关。这一观察结果启发了G-RLEF的贪婪采样策略，同时也解释了其高效性。无论是哑铃图还是团状环结构，G-RLEF的收敛速度始终快于RLEF。
在G-RLEF与SDRF的对比中，我们发现SDRF的谱扩展速率通常更快（如哑铃图案例所示）。这归因于SDRF采用了更丰富的变换集合。
SDRF框架的加速扩张往往以一致性为代价：RLEF和G-RLEF都是局部算法——它们在相同位置添加和删除边，同时保持图的节点度数和连通性。
在团环结构中，三角形数量及谱隙会不可预测地波动，直至图结构变得不连通（见图4）。需知SDRF的运作机制是通过在瓶颈处"支撑"一条负曲率边，并增加其周边边的数量。由于这些新增的支撑边同样位于瓶颈区域，它们更可能呈现负曲率特征。
在哑铃状结构中，尽管SDRF重连过程会局部增加瓶颈边周围的曲率，但通过三角形数量粗略测量的整体曲率却呈现下降趋势。这种现象源于负曲率边数量的整体增加，而非特定边曲率的进一步恶化。
我们测试了G-RLEF在缓解基于NEIGHBORSMATCH问题（见第三节C部分所述）建模的学习任务中过度挤压现象的效果。给定输入图G、靶区节点T和G节点的子集S，我们为S中的每个节点分配不同的|S|维独热向量编码，表示橙色邻居的数量。同样地，我们将T的标签表示为|S|维独热向量，目标是预测与T具有相同标签的节点T'∈S。
我们设定输入图G为一条团路径，该路径由三个规模均为10的团组成，这些团通过两条边以路径形式相连：一条边连接团1的末节点与团2的首节点，另一条边连接团2的末节点与团3的首节点。集合S包含团1的前9个节点，靶区T则为团3的末节点。问题半径（即T与S中节点之间的最大距离）为r=5。我们在包含10000个G副本的训练数据集上，训练了一个具有r+1层（每层宽度64）的图注意力网络，其中每个副本都具有符合上述描述的、与靶区相匹配的不同映射关系。
图5展示了归一化谱隙与训练准确率随G-RLEF迭代次数的演变规律。我们观察到，归一化谱隙和训练准确率都随着G-RLEF迭代次数的增加而单调上升，直至约150次迭代后趋于饱和。
# G-RLEF算法，整个预处理过程可以写为一个函数
def grlef(G, triangle_data=None, temperature=5):
# samples greedily according to inverse triangle count
if triangle_data == None:
triangle_data = {}
for (u,v) in G.edges:
u_nbhd = set(G.neighbors(u))
v_nbhd = set(G.neighbors(v))
num_triangles = len(u_nbhd.intersection(v_nbhd))
triangle_data[(u,v)] = num_triangles
triangle_data[(v,u)] = num_triangles
triangle_data_list = [[e, triangle_data[e]] for e in triangle_data]
edge_list = [x[0] for x in triangle_data_list]
weights = np.array([1/(2 + x[1]) for x in triangle_data_list])
selected_index = sample(weights, temperature=temperature)
(u, v) = edge_list[selected_index]
u_nbhd = set(G.neighbors(u))
v_nbhd = set(G.neighbors(v))
eligible_i = list(u_nbhd.difference(v_nbhd).difference({v}))
if not eligible_i:
return triangle_data
# choose the value of i which removes as many triangles as possible
i_scores = {}
for node in eligible_i:
node_nbhd = set(G.neighbors(node))
triangles_added = len(v_nbhd.intersection(node_nbhd))
triangles_removed = len(u_nbhd.intersection(node_nbhd))
i_scores[node] = triangles_added - triangles_removed
i = argmin(i_scores)
eligible_j = list(v_nbhd.difference(u_nbhd).difference({u}))
if not eligible_j:
return triangle_data
# choose the value of j which removes as many triangles as possible
j_scores = {}
for node in eligible_j:
node_nbhd = set(G.neighbors(node))
triangles_added = len(u_nbhd.intersection(node_nbhd))
triangles_removed = len(v_nbhd.intersection(node_nbhd))
j_scores[node] = triangles_added - triangles_removed
j = argmin(j_scores)
#print(u, v, i, j)
G.remove_edge(j,v)
G.remove_edge(i,u)
G.add_edge(i,v)
G.add_edge(j,u)
triangle_data.pop((i,u))
triangle_data.pop((u,i))
triangle_data.pop((j,v))
triangle_data.pop((v,j))
u_nbhd = set(G.neighbors(u))
v_nbhd = set(G.neighbors(v))
i_nbhd = set(G.neighbors(i))
j_nbhd = set(G.neighbors(j))
triangle_data[(i,v)] = len(i_nbhd.intersection(v_nbhd))
triangle_data[(v,i)] = len(i_nbhd.intersection(v_nbhd))
triangle_data[(j,u)] = len(j_nbhd.intersection(u_nbhd))
triangle_data[(u,j)] = len(j_nbhd.intersection(u_nbhd))
return triangle_data
基于扩展性图为基础概念，扩展性对应的是整个图的连通性，调整图的拓扑结构为了让消息传递更加流畅。
为了算法更加高效率，加入有效电阻作为边的采样标准，实现更快地算法收敛。
整个论文的亮点是以扩展图为基础后，用有效电阻来辅助求优。核心在于对基础理论的理解和运用。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。