SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks

arXiv (Cornell University)

Abstract

While (message-passing) graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs or general relational data, more expressive, higher-order graph neural networks do not scale to large graphs. 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. By introducing new heuristics for the graph isomorphism problem, we devise a class of universal, permutation-equivariant graph networks, which, unlike previous architectures, offer a fine-grained control between expressivity and scalability and adapt to the sparsity of the graph. These architectures lead to vastly reduced computation times compared to standard higher-order graph networks in the supervised node- and graph-level classification and regression regime while significantly improving over standard graph neural network and graph kernel architectures in terms of predictive performance.

Authors 3

1. Gaurav Rattan Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

2. Sandra Kiefer

   Max Planck Institute for Software Systems

   Affiliation as printed

   Max Planck Institute for Software Systems

3. Siamak Ravanbakhsh

   McGill University · Mila - Quebec Artificial Intelligence Institute

   Affiliation as printed

   McGill University and Mila Quebec AI Institute