VPF:一种保持拓扑结构的虚拟路径融合技术,用于解决过度压缩问题
《Pattern Recognition》:VPF: Topology-preserving Virtual Path Fusion to tackle over-squashing
【字体:
大
中
小
】
时间:2026年04月17日
来源:Pattern Recognition 7.6
编辑推荐:
虚拟路径融合框架通过有效电阻识别图结构中的信息瓶颈,构建虚拟路径增强远节点信息传播,解决图神经网络中的过压缩问题,不改变图结构且兼容主流GNN架构,实验验证其有效性。
白慧文|丁立忠|张俊宇|张春辉|傅家润|常亮|顾天龙|李长胜|袁叶|王国仁
北京工业大学,中国北京100081
摘要
尽管图神经网络(GNNs)在各种图学习任务中取得了广泛的成功,但它们的性能经常受到过压缩问题的影响,这阻碍了来自远端节点的信息传播,并限制了模型的表达能力。现有的缓解过压缩问题的方法主要依赖于改变图拓扑结构来改善信息流动。然而,这种结构修改可能会破坏图的内在拓扑和相应的归纳偏见,而引入额外的边可能会增加过平滑的风险。为了解决这些限制,我们提出了虚拟路径融合(VPF)框架,这是一种改进的GNN,通过促进虚拟路径中的信息流动来应对过压缩问题,提供了一种保持拓扑结构的解决方案,从而避免了结构扭曲和过平滑的固有风险。具体来说,我们的方法利用了有效抵抗(effective resistance)这一通用度量,它同时捕捉了敏感性和谱属性,来指导构建针对结构脆弱瓶颈的虚拟路径。这些路径通过序列模型进行编码,以捕捉长距离依赖性,从而自适应地加强远端节点之间的交互。VPF被设计为一个与模型无关的即插即用模块,可以与多种消息传递GNN架构兼容,同时也有助于缓解过平滑问题。广泛的实验表明,VPF在多个基准测试中一致且显著地优于基线方法,验证了虚拟路径增强作为一种有效且多用途的策略来应对过压缩问题的有效性。代码可在以下链接获取:
https://github.com/BHuiwen/VPF。
引言
图神经网络(GNNs)[1]、[2]在各种与图相关的下游任务[3]、[4]、[5]中取得了显著的成功。GNNs的核心机制之一是消息传递,这一机制由消息传递神经网络(MPNNs)正式描述,在其中节点特征在节点邻域内进行局部聚合并迭代更新(在本工作中,我们交替使用GNN和MPNN这两个术语)。然而,这一机制的一个关键限制是它容易受到过压缩[6]、[7]的影响,这会削弱消息传递过程的有效性。过压缩是指在邻域聚合过程中,大量信息被压缩成固定大小的向量,导致判别能力的丧失,并限制了GNNs的表达能力[8]。当处理节点之间的长距离交互时,这个问题尤为严重,因为信息必须跨越许多跳数进行传播,这往往会导致相关信号的稀释[9]、[10]。
一种常见的缓解过压缩的策略是修改输入图的结构以减轻信息瓶颈。早期的方法通常将图转换为全连接(FC)拓扑结构,将这种转换应用于基础GNN的最后一层或所有层[11]。最近的努力集中在有针对性的结构调整上,通过战略性地添加或删除边来促进信息流动。这些方法受到了物理信息方法[12]、基于谱的调整[13]和随机规则图拓扑[14]的启发。另一种重要的方向是使用图变换器(GTs)[15]、[16],它们通过自注意力机制实现所有节点对之间的全局消息传递,从而重新定义节点连接。然而,这些结构修改不可避免地会扭曲原始图拓扑,可能会破坏输入结构中固有的归纳偏见,可能导致不必要的信息丢失。此外,添加边在某种程度上可能会加剧过平滑[17]、[18]——即由于通过消息传递层的过度聚合,节点特征变得无法区分。
为了解决这些限制,我们提出了一种名为虚拟路径融合(VPF)的保持拓扑结构的方法,该方法在不改变原始图结构的情况下缓解过压缩问题。我们的方法通过将潜在的瓶颈表征为虚拟路径(VPs)来识别它们。这些VPs通过序列模型进行自适应处理,以创建辅助通道用于信息传播。这种机制通过明确建模容易受到过压缩影响的交互来增强消息传递方案,从而弥补其局限性。关键的是,我们的方法完全保留了原始拓扑的归纳偏见。如图1所示,我们将VPF与在一个带有瓶颈的玩具图上的图重连方法进行了比较,我们的框架通过增强通过VPs的信息流动有效缓解了过压缩问题,而没有任何结构上的改变。
具体来说,我们首先分析了几个量化过压缩的指标,研究了它们之间的相关性和区别。分析表明,有效抵抗是一个通用的、成对的量,它同时限制了雅可比敏感性并捕捉了全局谱属性——这种组合激发了将其作为诱导VPs的基础工具的使用。基于这一见解,我们的VPF框架根据有效抵抗定义了一个节点对采样分布。通过采样具有高有效抵抗值的节点对来构建VPs,这些节点对对应于特别容易受到过压缩的结构路径。为了有效地捕捉沿这些VPs的上下文信息,我们使用了序列编码器,这些编码器在建模长距离依赖性方面已被证明是成功的[19]、[20]。然后,将基于VP的序列编码器得到的特征与传统的消息传递编码器的特征结合起来,自适应地增强通过容易受到过压缩的路径的信息传播。值得注意的是,VPF被设计为与各种消息传递架构兼容。此外,对狄利克雷能量的实证分析表明,通过使用序列模型明确建模VPs,我们的方法不仅缓解了过压缩问题,还有助于减轻过平滑问题。实验结果验证了VPF在多个基准测试中取得了显著的性能提升,表明虚拟路径增强是一种有效且灵活的策略,用于解决图神经网络中的过压缩问题。本工作的主要贡献如下:
- •
一种通过虚拟路径建模来缓解过压缩的保持拓扑结构的框架。我们提出了VPF,它通过明确建模VPs来缓解过压缩问题,而不是通过改变图结构,VPs是通过有效抵抗识别出的关键结构路径,使用序列编码器来实现。这种方法在完全保留原始图的归纳偏见的同时缓解了过压缩问题。
- •
一种灵活高效的即插即用增强方法,适用于主流GNNs。我们的框架与架构无关,可以作为多功能模块集成到各种GNN框架中。其实际效率通过基于采样的策略来构建虚拟路径得到保证,确保了在大图上的计算可行性。
- •
对过平滑的固有抵抗力。我们展示了我们的方法具有对过平滑的固有抵抗力。通过虚拟路径整合非局部信息,它自然地在网络层之间保持了更高的表示多样性,从而缓解了与过平滑相关的表示崩溃。
章节片段
过压缩
过压缩描述了消息传递神经网络(MPNNs)中的一个根本限制,即在邻域聚合过程中,来自远端节点的信息被压缩成固定大小的向量。这种压缩阻碍了长距离依赖性的传播,最终限制了模型的表达能力。一个公认的研究方向将这一瓶颈主要归因于底层的图拓扑结构。因此,许多最新的方法专注于修改
初步介绍
我们考虑一个连接的、无向的、无权重的图,具有个顶点和条边,遵循图结构的传统表示法。其邻接矩阵和度矩阵分别用和表示,拉普拉斯矩阵定义为,相应的归一化拉普拉斯矩阵为,也可以表示为。对于添加了自环的图,我们定义
虚拟路径融合
本节概述了我们提出的VPF框架,如图2所示。我们首先分析了量化过压缩的各种指标,这使我们采用了有效抵抗——一个通用的、成对的量,它限制了雅可比敏感性并反映了全局谱属性——作为诱导虚拟路径的基础。接下来,虚拟路径采样器识别出捕获潜在过压缩源的关键路径。然后我们描述了如何通过这些路径进行建模
VPF的理论分析
本节从两个角度对我们的模型进行了全面分析:评估其计算复杂性,以及通过敏感性研究量化其在缓解过压缩方面的有效性。
实验
在本节中,我们对提出的VPF框架进行了全面的实证评估。我们首先详细介绍了实验设置,然后与最先进的方法在节点和图分类任务上进行了严格的比较。为了进一步验证我们的设计,我们对以下方面进行了深入研究:虚拟路径的有效性、过平滑分析、模型架构和参数敏感性。这些分析共同提供了全面的
结论
在这项研究中,我们提出了虚拟路径融合(VPF)框架,这是一种专门为解决GNNs中普遍存在的过压缩问题而设计的保持拓扑结构的方法。我们工作的一个主要优势是它避免了永久性图结构修改的需要,这种修改通常会破坏固有的归纳偏见,并无意中加剧过平滑问题。通过利用有效抵抗系统地识别结构瓶颈并通过
CRediT作者贡献声明
白慧文:撰写——原始草稿、可视化、软件、方法论、概念化。丁立忠:撰写——审阅与编辑、监督、方法论、概念化。张俊宇:撰写——审阅与编辑。张春辉:撰写——审阅与编辑。傅家润:撰写——审阅与编辑。常亮:监督。顾天龙:监督。李长胜:监督。袁叶:撰写——审阅与编辑。王国仁:监督。
利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。
致谢
本工作得到了国家自然科学基金联合资助[资助编号:U22A2099]、国家自然科学基金的一般项目[资助编号:62376028]、国家自然科学基金的优秀青年科学家基金(海外)、国家自然科学基金的国家重大科学仪器设备发展项目[资助编号:62427808]以及国家重点研究的支持
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号