10/03/2025
Graph Neural Networks (GNNs) are the leading method for learning on graph-structured data, primarily relying on the Message Passing (MP) paradigm, in which messages are passed locally between nodes in order to learn meaningful node or graph representations. However, MP-based models have limited expressive power, for example, they will always have the same output on any 2-regular graph. Subgraph GNNs, a new class of graph architectures in which MP is performed on several subgraphs of the original graph, improve expressiveness (and accuracy) but often come with high computational costs, making it challenging to operate on larger graphs.
In their latest NeurIPS paper, Guy Bar-Shalom, Yam Eitan (co-first author), Dr. Fabrizio Frasca, and Prof. Haggai Maron present “A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening”, which enables a fine-grained control over the trade-off between expressivity and efficiency. This allows for the processing of larger graphs while still retaining the expressivity benefits of Subgraph GNNs.
Their work extends a key insight from their previous research: Subgraph GNNs can be reformulated as message passing on the graph Cartesian product. They relax one element in the product by first applying a graph clustering algorithm to coarsen one copy before computing the product, allowing precise control of computational complexity. Notably, this leads to a new object—a product of a graph and its coarsened version—that reveals unexplored symmetries. Using geometric deep learning principles, they characterize these invariances and design neural network layers that respect them.
Key Findings:
* Significantly better accuracy compared to other efficient Subgraph GNNs.
* Scales to larger graphs while maintaining expressivity benefits.
* Matches the performance of original Subgraph GNNs when maximizing expressivity (at the cost of efficiency).
* Studying a new and interesting symmetry structure.
Notably, this work was also awarded **Best Paper** at NeurReps – Symmetry and Geometry in Neural Representations, a NeurIPS workshop! 🎉
Curious to dive deeper? Read the full paper: https://openreview.net/pdf?id=9cFyqhjEHC