Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results

Abstract

While message passing Graph Neural Networks (GNNs) have become increasingly popular architectures for learning with graphs, recent works have revealed important shortcomings in their expressive power. In response, several higher-order GNNs have been proposed that substantially increase the expressive power, albeit at a large computational cost. Motivated by this gap, we explore alternative strategies and lower bounds. In particular, we analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we prove that this model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. Second, we show how recursive pooling can exploit sparsity to reduce the computational complexity compared to the existing higher-order GNNs. More generally, we provide a (near) matching information-theoretic lower bound for counting subgraphs with graph representations that pool over representations of derived (sub-)graphs. We also discuss lower bounds on time complexity.

26 pages, 4 figures

References in corpus (13)

• Deep learning for molecular design - a review of the state of the art
• Interaction Networks for Learning about Objects, Relations and Physics
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• SumGNN: Multi-typed Drug Interaction Prediction via Efficient Knowledge Graph Summarization
• Learning Multimodal Graph-to-Graph Translation for Molecular Optimization
• Neural Subgraph Matching
• Can Graph Neural Networks Count Substructures?
• Building powerful and equivariant graph neural networks with structural message-passing
• Graph Meta Learning via Local Subgraphs
• Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks
• Identity-aware Graph Neural Networks
• Reconstruction for Powerful Graph Representations
• Unsupervised Joint $k$-node Graph Representations with Compositional Energy-Based Models

Cited by in corpus (2)

• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Equivariant Subgraph Aggregation Networks