@inproceedings{
finkelshtein2024learning,
title={Learning on Large Graphs using Intersecting Communities},
author={Ben Finkelshtein and Ismail Ilkan Ceylan and Michael M. Bronstein and Ron Levie},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=pGR5X4e1gy}
}
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.
Learning on Large Graphs using Intersecting Communities
Ben Finkelshtein Ismail Ilkan Ceylan Michael M. Bronstein Ron Levie