arXiv:2608.02128cs.LG2026-08

提出CoRe-GNN,兼顾长程信息与内存效率的图神经网络新架构。

CoRe-GNN: Multilevel Message passing on Coarsened graphs

论文配图:CoRe-GNN: Multilevel Message passing on Coarsened graphs
图 1 · 摘自论文原文
  • 并行处理粗化图间的长程传播与局部聚类内传播
  • 在百万级节点图上实现高精度与低内存占用
  • 适合大规模长距离依赖图任务,如社交网络分析

在大规模图上训练图神经网络面临存储所有层节点表示的内存瓶颈。本文表明,现有可扩展方法均可视为对GNN传播矩阵的结构化修改,统一视角揭示了其各自局限:图粗化通过低秩近似替代传播矩阵,虽有谱保证但使聚类内节点共享相同表示;Cluster-GCN仅保留簇内连接,利于高效批处理,却切断长程信息。二者本质源于同一节点分组分解的缺陷。为此,我们提出CoRe-GNN,每层并行执行两种传播:粗化图上的跨簇项捕捉长程结构,局部簇内项保持节点可区分性。理论证明,CoRe-GNN继承图粗化的近似保证,并引入自然的基于聚类的批处理方案,可扩展至百万级节点。在涵盖同质、异质、大规模及长距离依赖的节点分类基准上,CoRe-GNN均优于图粗化与Cluster-GCN基线。尤其在长距离任务中表现优异,同时保持内存效率。

原文摘要 · Abstract (English)

Training Graph Neural Networks on large graphs is challenged by the memory cost of storing all node representations across layers. We show that several existing scalable approaches can be written as structured modifications of the GNN propagation matrix, providing a unified perspective that exposes their respective limitations. In particular, graph coarsening replaces it by a low-rank approximation that enables spectral guarantees but assigns uniform representations to clustered nodes, while Cluster-GCN restricts the propagation matrix to intra-cluster connections that allow efficient batching but sever long-range information. These are complementary failures of the \emph{same} decomposition of the graph into groups of nodes. To obtain the best of both worlds, we propose \textbf{CoRe-GNN}, which performs both propagations in parallel at each layer: a coarsened inter-cluster term capturing long-range structure, and a local intra-cluster term preserving per-node discriminability. We prove that CoRe-GNN inherits analogous approximation guarantees to those of graph coarsening, and introduce a natural cluster-based \emph{batching scheme} that scales to graphs with millions of nodes. On node classification benchmarks spanning homophilic, heterophilic, large-scale, and long-range graphs, CoRe-GNN outperforms both graph coarsening and Cluster-GCN baselines. Notably, CoRe-GNN reaches competitive accuracy on \emph{long-range} tasks, while remaining memory-efficient through batching.

图神经网络内存优化长程依赖聚类

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