摘要
图神经网络（Graph Neural Networks, GNNs）是一类流行的深度学习模型，通过消息传递过程中的递归邻域聚合机制，用于处理图结构数据。在半监督节点分类任务中，消息传递机制使GNN能够捕捉短距离的空间交互关系，但也导致模型面临过平滑（over-smoothing）和过挤压（over-squashing）问题。这些问题限制了模型的表达能力，阻碍了通过加深网络结构来捕获图中长程节点交互（Long-Range Interactions, LRIs）的能力。现有的长程交互检测方法要么因时间复杂度较高而难以处理大规模图，要么在不同图结构之间缺乏泛化能力。为解决上述局限性，本文提出一种名为信息流控制（information flow control）的新机制，该机制基于一种新颖的连通性度量——信息流得分（information flow score），在仅引入线性计算开销的前提下，有效缓解过平滑与过挤压问题，并获得了理论支持。为进一步验证所提方法的有效性，我们设计了DeltaGNN，这是首个兼具可扩展性与泛化能力的长程与短程交互检测框架。我们在10个真实世界数据集上进行了全面评估，涵盖不同规模、拓扑结构、密度以及同质性比率的图数据，结果表明，DeltaGNN在保持较低计算复杂度的同时，展现出卓越的性能表现。所提出方法的开源实现已公开发布于：https://github.com/basiralab/DeltaGNN。