Search papers, labs, and topics across Lattice.
This paper introduces CoRe-GNN, a novel Graph Neural Network architecture that simultaneously utilizes coarsened inter-cluster and local intra-cluster message passing to enhance performance on large graphs. By addressing the limitations of existing scalable approaches, which either oversimplify node representations or restrict information flow, CoRe-GNN achieves a balance that retains both long-range structural information and node-specific discriminability. Experimental results demonstrate that CoRe-GNN outperforms traditional methods on various node classification benchmarks, particularly excelling in long-range tasks while maintaining memory efficiency through an innovative batching scheme.
CoRe-GNN achieves competitive accuracy on long-range graph tasks while dramatically improving memory efficiency through a novel dual-message passing approach.
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.
