🤖 machine learning

DeltaGNN: Graph Neural Network with Information Flow Control

本文介绍了 DeltaGNN，这是一种可扩展且具有泛化能力的图神经网络架构，它利用一种具有线性计算开销的新型信息流控制机制，有效地克服了过度平滑和过度挤压挑战，从而能够在多种图结构中实现对短程和长程节点交互的检测。

原作者： Kevin Mancini, Islem Rekik

发布于 2026-08-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Kevin Mancini, Islem Rekik

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字世界中，数据往往不是以电子表格中整齐的行形式呈现，而是以复杂的连接网络形式存在。想象一个由友谊连接着人们的社交网络，或者一张显示器官不同部分通过组织相连的医学扫描图。为了理解这些网络，科学家们使用了一种被称为图神经网络（Graph Neural Network）的人工智能模型。这些模型的工作原理是让网络中的每个点观察其直接相邻的邻居，收集来自它们的信息，并更新自身的理解。通过重复这一过程，模型能够构建出整个系统的全貌，从而解决诸如识别组织样本中的疾病或预测化学分子行为等问题。

然而，当这些网络试图观察得过于长远时，会面临一个根本性的问题。如果模型连续观察过多的邻居，每个点的独特细节就会被冲淡，导致所有点看起来都变得一样。这被称为“过度平滑”（over-smoothing）。与此同时，如果网络存在一个狭窄的瓶颈——即连接两个大型群体的单一路径——试图通过该路径传递的信息会被挤压并丢失，这种问题被称为“过度挤压”（over-squashing）。这些问题阻碍了人工智能理解数据中的远程关系，而这些关系往往是做出准确预测的关键。多年来，研究人员一直试图通过构建更复杂的模型来修复这些问题，但这些解决方案在处理大规模现实世界数据集时通常运行过慢。

伦敦帝国理工学院的一个研究小组现在提出了一种不同的前进方向。他们并没有让模型变得更加复杂，而是引入了一种控制信息如何在网络中流动的机制，有效地在模型学习过程中清理连接。他们将这个新系统称为 DeltaGNN。他们方法的核心是一个简单而强大的想法：他们测量网络中的一个点在从邻居收集信息时，其理解变化的速度和幅度。通过追踪这些变化，系统可以识别哪些连接是有帮助的，而哪些连接正在造成混乱或瓶颈。

研究人员开发了一套评分系统来评估网络中的每一个连接。如果一个连接导致一个点的理解发生过于剧烈或过于缓慢的变化，系统就会将其标记为问题连接。那些连接差异极大的点之间的连接，或者充当狭窄咽喉要道的连接，会获得低分。随后，模型利用这些分数有选择性地移除最差的连接，同时保持其余网络结构的完整。这个过程是逐层、分步骤进行的，使得网络能够逐步自我重塑成一个更高效的结构。这就像园丁修剪灌木丛：通过剪掉纠缠不清、毫无用处的枝条，植物可以在无需重新栽种的情况下长得更强壮、更健康。

这种方法的独特之处在于，它不需要昂贵的预计算或大量的额外计算能力。评分是在模型学习的过程中自然发生的，几乎不会增加处理时间。研究人员在十个不同的现实世界数据集上测试了他们的系统，涵盖了从科学引用网络到肝脏肿瘤医学图像的广泛领域。这些数据集在规模、密度以及连接点之间的相似性方面各不相同。在每种情况下，DeltaGNN 的表现都优于现有的最先进方法，且往往优势显著。在其他模型因内存耗尽或耗时过长而完全失效的大型密集图中，它的表现尤为出色。

研究还表明，无论数据的具体形状如何，这种新方法都能有效运作。无论网络是由高度相似的点组成，还是由差异巨大的点组成，系统都能适应并找到最佳连接。研究人员发现，通过移除有问题的链路，模型可以同时学习短期细节和远程模式。这种双重能力使它能够比以往的模型更准确地区分不同类型的数据。例如，在医学影像测试中，该系统通过识别其他模型可能会忽略的细微模式，成功识别出了不同类型的肝脏肿瘤。

该团队的工作表明，解决人工智能领域这些长期存在的关键不在于构建更大、更复杂的“大脑”，而在于更仔细地管理信息的流动。通过引入一种衡量和控制信息如何在网络中传输的方法，他们创造了一个既强大又高效的工具。这种方法为分析大规模数据集提供了可扩展的解决方案，从绘制人脑图谱到理解全球社会趋势。研究人员已向公众开放了他们的代码，邀请他人测试并基于此方法进行开发。他们的研究结果表明，只要拥有正确的连接过滤方式，人工智能终将能够看到那些一直隐藏在显而易见之处的远程关系。

技术摘要：DeltaGNN：具有信息流控制功能的图神经网络

问题陈述
图神经网络（GNNs）在处理图结构数据方面非常有效，但在半监督节点分类中面临显著的局限性，特别是关于**过度平滑（over-smoothing）和过度挤压（over-squashing）**的问题。

过度平滑： 随着层数的增加，节点表示变得难以区分，尤其是在存在异质边（连接不同类别节点的边）的图中。
过度挤压： 图瓶颈导致节点的感受野呈指数级增长，迫使大量信息被压缩进固定大小的特征向量中，从而抑制了捕捉长程相互作用（LRIs）的能力。

现有的解决方案，如图 Transformer（全局注意力机制）和拓扑重连（基于曲率的方法），通常面临高计算复杂度（通常是二次方复杂度或需要昂贵的预处理），或者无法在多样化的图拓扑、密度和同质性比例之间进行泛化。因此，需要一种能够以线性计算开销解决这两个问题的可扩展且通用的方法。

方法论
作者提出了 DeltaGNN，这是一种基于两个核心概念构建的新型架构：信息流评分（Information Flow Score, IFS）和信息流控制（Information Flow Control, IFC）。

信息流评分 (IFS)：
- 作者将图信息流（GIF）定义为消息传递过程中节点嵌入聚合的速率。
- 他们引入了一阶增量嵌入（ $\Delta^t_u$ ），代表嵌入更新的“速度”，以及二阶增量嵌入（ $( \Delta^2 )^t_u$ ），代表“加速度”（速度的变化率）。
- IFS ( $S_u$ ) 是一个连通性度量，计算公式为：
  $S_u = V_t[\Delta^2_u] + \frac{1}{\Delta_u + 1}$
  其中 $V_t[\Delta^2_u]$ 是二阶增量嵌入的时间方差。
- 理论基础：
  - 高 $\Delta$ 值与低同质性（异质交互）相关。
  - $\Delta^2$ 的低方差与靠近图瓶颈相关（过度挤压）。
- 该评分旨在为靠近瓶颈或具有低同质性的节点设定较低的分数，从而识别易发生过度平滑和过度挤压的区域。
信息流控制 (IFC)：
- 与静态重连不同，IFC 是一种序列化的、在训练过程中进行的边过滤机制。
- 它与标准 GNN 层集成，迭代地移除 IFS 值较低的边。
- 该过程使用通过爬山算法优化的参数 $\theta$ 来最大化平均节点得分，从而在确保保持稀疏性的同时移除有害边。
- 该机制以线性计算开销（ $O(|V|)$ ）和内存复杂度运行。
DeltaGNN 架构：
- 序列变换阶段：
  - 同质路径（Homophilic Path）： 通过带有 IFC 的标准 GNN 处理图。该路径会移除异质边和瓶颈，创建一个高度同质的子图（ $G_{ho}$ ），以捕捉短程依赖关系。
  - 异质路径（Heterophilic Path）： 执行异质图凝聚。选择具有最高 IFS（可靠表示）的节点来形成一个较小的、全连接的、高度异质的子图（ $G_{he}$ ）。一个单独的 GNN 在该凝聚图上聚合长程依赖关系。
- 预测阶段： 拼接两个路径的输出，随后通过一个线性读出层进行分类。

核心贡献

新型连通性度量： 引入了信息流评分（IFS），它基于嵌入更新的动力学（速度和加速度）来识别图瓶颈和异质交互，并得到了理论引理的支持。
信息流控制 (IFC)： 一种用于序列化边过滤的机制，能够以线性时间和内存复杂度缓解过度平滑和过度挤压，并可集成到任何 GNN 架构中。
DeltaGNN 架构： 一个可扩展且通用的框架，它将同质交互和异质交互解耦，从而有效地检测短程和长程相互作用。据称，这是第一个以线性开销实现此目标的架构，并在不同图属性下表现出一致的性能。

实验结果
该模型在 10 个真实世界数据集（包括 Cora, CiteSeer, PubMed, Cornell, Texas, Wisconsin 和 MedMNIST）上进行了基准测试，这些数据集具有不同的规模、拓扑、密度和同质性比例。

准确率： 在 4 个出 6 个 同质性变化的测试数据集中，DeltaGNN 优于最先进的方法（包括 GCN, GIN, GAT, 图 Transformer 以及各种重连算法），平均准确率提升了 1.23%。它在低同质性数据集（如 Texas, Wisconsin）上表现尤为出色。
可扩展性：
- 时间： 在测试的 5 个数据集中，DeltaG
DeltaGNN 在 3 个数据集中实现了最低的每轮（epoch）时间，与表现最差的模型相比，平均每轮时间减少了 30.61%。它成功处理了其他方法（如 GAT 和图 Transformer）因显存溢出（OOM）或超时（OOT）而无法处理的稠密图。
- 内存： 虽然由于双路径聚合，其使用的内存大约是标准 GCN 的两倍，但仍比完全无法处理稠密数据集的 GAT 和图 Transformer 要高效得多。
连通性度量： 与拓扑度量（如 Ollivier-Ricci 曲率、介数中心性）相比，IFS 在边过滤过程中提升图同质性的表现更为出色（提升了 8.65%），后者往往难以扩展或泛化。

意义与主张
论文声称 DeltaGNN 解决了捕捉长程相互作用与保持计算效率之间的根本权衡。通过利用消息传递的动力学（嵌入的速度和加速度）而非静态拓扑属性，所提出的方法提供了一种可泛化的解决方案，能够在不具备注意力机制的二次方复杂度或基于曲率重连的高昂预处理成本的情况下，适用于多样化的图结构。作者将 DeltaGNN 定位为一个可扩展的框架，旨在扩大 GNN 在半监督节点分类任务中的适用性，特别是在长程依赖至关重要的复杂大型图中。

技术摘要：DeltaGNN：具有信息流控制功能的图神经网络

类似论文