mlsanityData to 7 Oct 2026

Learning on Large Graphs using Intersecting Communities

arXiv 2405.20724 ↗First posted 31 May 2024cs.LG cs.SI stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

Message Passing Neural Networks (MPNNs) are a staple of graph machine learning. MPNNs iteratively update each node's representation in an input graph by aggregating messages from the node's neighbors, which necessitates a memory complexity of the order of the number of graph edges. This complexity might quickly become prohibitive for large graphs provided they are not very sparse. In this paper, we propose a novel approach to alleviate this problem by approximating the input graph as an intersecting community graph (ICG) -- a combination of intersecting cliques. The key insight is that the number of communities required to approximate a graph does not depend on the graph size. We develop a new constructive version of the Weak Graph Regularity Lemma to efficiently construct an approximating ICG for any input graph. We then devise an efficient graph learning algorithm operating directly on ICG in linear memory and time with respect to the number of nodes (rather than edges). This offers a new and fundamentally different pipeline for learning on very large non-sparse graphs, whose applicability is demonstrated empirically on node classification tasks and spatio-temporal data processing.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 47 of its 68 references that are in the map. First posted on arXiv 31 May 2024.

Builds on

47 of 68 references.

References · 47

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Dynamic Graph CNN for Learning on Point Cloudscited by 2,220
  7. 2016Variational Graph Auto-Encoderscited by 1,373
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  9. 2019Graph WaveNet for Deep Spatial-Temporal Graph Modelingcited by 820
  10. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  12. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
35 more
  1. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  2. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  3. 2019Multi-scale Attributed Node Embeddingcited by 543
  4. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  5. 2020Adaptive Graph Convolutional Recurrent Network for Traffic Forecastingcited by 525
  6. 2019Graph Transformer Networkscited by 520
  7. 2020Dataset Condensation with Gradient Matchingcited by 510
  8. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  9. 2019Diffusion Improves Graph Learningcited by 414
  10. 2018Neural Relational Inference for Interacting Systemscited by 339
  11. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  12. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  13. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  14. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  15. 2021Graph Condensation for Graph Neural Networkscited by 150
  16. 2019Attributed Graph Clustering: A Deep Attentional Embedding Approachcited by 149
  17. 2020Structural Deep Clustering Networkcited by 145
  18. 2021SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networkscited by 108
  19. 2022Condensing Graphs via One-Step Gradient Matchingcited by 100
  20. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  21. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
  22. 2023Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Datacited by 71
  23. 2020Hierarchical Inter-Message Passing for Learning on Molecular Graphscited by 59
  24. 2020Pointer Graph Networkscited by 52
  25. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  26. 2019A Review of Stochastic Block Models and Extensions for Graph Clusteringcited by 46
  27. 2020Latent-Graph Learning for Disease Predictioncited by 39
  28. 2020Graphon Signal Processingcited by 37
  29. 2023Taming Local Effects in Graph-based Spatiotemporal Forecastingcited by 37
  30. 2023Fast Graph Condensation with Structure-based Neural Tangent Kernelcited by 36
  31. 2023A graphon-signal analysis of graph neural networkscited by 29
  32. 2019A Flexible Generative Framework for Graph-based Semi-supervised Learningcited by 24
  33. 2020Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Networkcited by 19
  34. 2018On estimation and inference in latent structure random graphscited by 9
  35. 2022Unveiling the Sampling Density in Non-Uniform Geometric Graphscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 2.

8 papers.

  1. 2024Even Sparser Graph Transformerscited by 12
  2. 2024Graph neural networks and non-commuting operatorscited by 5
  3. 2024Equivariant Machine Learning on Graphs with Nonlinear Spectral Filterscited by 2
  4. 2025ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusioncited by 2
  5. 2025Efficient Learning on Large Graphs using a Densifying Regularity Lemmacited by 2
  6. 2025A Note on Graphon-Signal Analysis of Graph Neural Networkscited by 1
  7. 2026Neural Networks With Dense Weights Are Not Universal Approximatorscited by 0
  8. 2026CoRe-GNN: Multilevel Message passing on Coarsened graphscited by 0