ELLIS header
University of Stuttgart Logo
Max Planck Institute for Intelligent Systems Logo

Ordered Subgraph Aggregation Networks

Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, Mathias Niepert

Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), pp. , 2022.


Numerous subgraph-enhanced graph neural networks (GNNs) have emerged recently, provably boosting the expressive power of standard (message-passing) GNNs. However, there is a limited understanding of how these approaches relate to each other and to the Weisfeilerā€“Leman hierarchy. Moreover, current approaches either use all subgraphs of a given size, sample them uniformly at random, or use hand-crafted heuristics instead of learning to select subgraphs in a data-driven manner. Here, we offer a unified way to study such architectures by introducing a theoretical framework and extending the known expressivity results of subgraph-enhanced GNNs. Concretely, we show that increasing subgraph size always increases the expressive power and develop a better understanding of their limitations by relating them to the established k-š¯–¶š¯–« hierarchy. In addition, we explore different approaches for learning to sample subgraphs using recent methods for backpropagating through complex discrete probability distributions. Empirically, we study the predictive performance of different subgraph-enhanced GNNs, showing that our data-driven architectures increase prediction accuracy on standard benchmark datasets compared to non-data-driven subgraph-enhanced graph neural networks while reducing computation time.



@inproceedings{qian22_neurips, title = {Ordered Subgraph Aggregation Networks}, author = {Qian, Chendi and Rattan, Gaurav and Geerts, Floris and Morris, Christopher and Niepert, Mathias}, year = {2022}, booktitle = {Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS)}, pages = {} }