​​SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks

Christopher Morris (McGill University and Mila), joint work with Gaurav Rattan, Sandra Kiefer (RWTH Aachen), and Siamak Ravanbakhsh (McGill University and Mila)

Standard graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs, i.e., their expressive power is bounded by the 1-WL (1,2). Hence, more expressive, higher-order graph neural networks have recently emerged, e.g., (1,3), which overcome these limitations.

However, they either operate on k-order tensors or consider all k-node subgraphs, implying an exponential dependence on k in memory requirements, and do not adapt to the sparsity of the graph. In (4), we introduce a new class of heuristics for the graph isomorphism problem, the (k,s)-WL, which offers a more fine-grained control between expressivity and scalability.

Essentially, the algorithm is a variant of the local k-WL (5) but only considers specific tuples to avoid the exponential memory complexity of the k-WL. Concretely, the algorithm only considers k-tuples or subgraphs on k nodes with at most s connected components, effectively exploiting the potential sparsity of the underlying graph. We show how varying k and s leads to a tradeoff between scalability and expressivity on the theoretical side.

Further, we derive a new hierarchy of permutation-equivariant graph neural networks, denoted SpeqNets, based on the above combinatorial insights, reaching universality in the limit. These architectures vastly reduce computation times compared to standard higher-order graph networks in the supervised node- and graph-level classification and regression regime, significantly improving standard graph neural network and graph kernel architectures in predictive performance.


(1) Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe, AAAI 2019.
(2) How Powerful are Graph Neural Networks? Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka, ICLR 2019.
(3) Provably Powerful Graph Networks. Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, Yaron Lipman, NeurIPS 2019.
(4) SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks (https://arxiv.org/abs/2203.13913). Christopher Morris, Gaurav Rattan, Sandra Kiefer, Siamak Ravanbakhsh, Geometrical and Topological Representation Learning (GT-RL, ICLR 2022).
(5) Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings.
Christopher Morris, Gaurav Rattan, Petra Mutzel, NeurIPS 2020.