arXiv:2501.06002cs.LG2025-01TPAMI被引 2

提出信息流控制机制,让图神经网络更高效地捕捉远距离节点关系。

DeltaGNN: Graph Neural Network with Information Flow Control

  • 设计信息流评分机制,动态调节消息传递路径
  • 在10个数据集上实现超越现有方法的准确率
  • 适合处理各种拓扑结构的大规模图数据

图神经网络(GNN)通过消息传递机制递归聚合邻域信息,广泛用于半监督节点分类。但该过程易导致过平滑和过压缩问题,限制模型表达能力,难以构建深层网络以捕捉图中的长程节点交互(LRIs)。现有解决方法或计算复杂度高,无法处理大规模图;或在不同图结构间泛化能力差。为此,我们提出一种名为‘信息流控制’的新机制,基于新颖的‘信息流评分’来缓解上述问题,具有线性计算开销,并有理论支持。在此基础上,我们构建了DeltaGNN,据我们所知是首个兼具可扩展性(线性时间与内存开销)和泛化能力(有效处理异质同质性、密度与拓扑结构)的长程与短程交互检测架构。我们在10个真实世界数据集上进行测试,涵盖不同规模、拓扑、密度与同质性比率的图,均展现出优异性能且计算开销有限。代码已公开于https://github.com/basiralab/DeltaGNN。

原文摘要 · Abstract (English)

Graph Neural Networks (GNNs) are popular deep learning models designed to process graph-structured data through recursive neighborhood aggregations in the message passing process. When applied to semi-supervised node classification, the message-passing enables GNNs to understand short-range spatial interactions, but also causes them to suffer from over-smoothing and over-squashing. These challenges hinder model expressiveness and prevent the use of deeper models to capture long-range node interactions (LRIs) within the graph. Popular solutions for LRIs detection are either too expensive to process large graphs due to high time complexity or fail to generalize across diverse graph structures. To address these limitations, we propose a mechanism called \emph{information flow control}, which leverages a novel connectivity measure, called \emph{information flow score}, to address over-smoothing and over-squashing with linear computational overhead, supported by theoretical evidence. Building on this mechanism, we introduce DeltaGNN, to the best of our knowledge among the first \textit{scalable} (featuring linear computational and memory complexity overhead) and \textit{generalizable} (capable of effectively handling graphs with diverse homophily, density, and topology) architectures for long-range and short-range interaction detection. We benchmark our model across 10 real-world datasets, including graphs with varying sizes, topologies, densities, and homophilic ratios, showing superior performance with limited computational complexity. The implementation of the proposed methods are publicly available at https://github.com/basiralab/DeltaGNN.

图神经网络长程交互可扩展性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。