Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

Abstract

While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture the structure of the underlying graph. It has been shown that the expressive power of standard GNNs is bounded by the Weisfeiler-Leman (WL) graph isomorphism test, from which they inherit proven limitations such as the inability to detect and count graph substructures. On the other hand, there is significant empirical evidence, e.g. in network science and bioinformatics, that substructures are often intimately related to downstream tasks. To this end, we propose "Graph Substructure Networks" (GSN), a topologically-aware message passing scheme based on substructure encoding. We theoretically analyse the expressive power of our architecture, showing that it is strictly more expressive than the WL test, and provide sufficient conditions for universality. Importantly, we do not attempt to adhere to the WL hierarchy; this allows us to retain multiple attractive properties of standard GNNs such as locality and linear network complexity, while being able to disambiguate even hard instances of graph isomorphism. We perform an extensive experimental evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings including molecular graphs and social networks. The code is publicly available at https://github.com/gbouritsas/graph-substructure-networks.

References in corpus (25)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Fast Graph Representation Learning with PyTorch Geometric
• Biological network comparison using graphlet degree distribution
• Interaction Networks for Learning about Objects, Relations and Physics
• Directional Message Passing for Molecular Graphs
• DeeperGCN: All You Need to Train Deeper GCNs
• Principal Neighbourhood Aggregation for Graph Nets
• Benchmarking Graph Neural Networks
• Subgraph Matching Kernels for Attributed Graphs
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Machine Learning for Scent: Learning Generalizable Perceptual Representations of Small Molecules
• Covariant Compositional Networks For Learning Graphs
• A Survey on The Expressive Power of Graph Neural Networks
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Generalization and Representational Limits of Graph Neural Networks
• Gauge Equivariant Mesh CNNs: Anisotropic convolutions on geometric graphs
• The Weisfeiler-Lehman Method and Graph Isomorphism Testing
• Neural Subgraph Matching
• Hierarchical Inter-Message Passing for Learning on Molecular Graphs
• Natural Graph Networks
• Breaking the Limits of Message Passing Graph Neural Networks
• Understanding Isomorphism Bias in Graph Data Sets
• Global Attention Improves Graph Networks Generalization
• A Hierarchy of Graph Neural Networks Based on Learnable Local Features
• Graph Homomorphism Convolution

Cited by in corpus (52)

• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• A Comprehensive Survey on Deep Graph Representation Learning
• Current and future directions in network biology
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• The Expressive Power of Graph Neural Networks: A Survey
• Natural Graph Networks
• Nested Graph Neural Networks
• Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization
• Can Graph Neural Networks Count Substructures?
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Graph Neural Networks with Learnable Structural and Positional Representations
• SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism
• Cell Attention Networks
• Graph Neural Networks with Diverse Spectral Filtering
• Building powerful and equivariant graph neural networks with structural message-passing
• ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting
• Graph Feature Preprocessor: Real-time Subgraph-based Feature Extraction for Financial Crime Detection
• Beltrami Flow and Neural Diffusion on Graphs
• Graph Neural Networks with Local Graph Parameters
• Graph Kernel Neural Networks
• Equivariant Subgraph Aggregation Networks
• RSEA-MVGNN: Multi-View Graph Neural Network with Reliable Structural Enhancement and Aggregation
• GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• Frame Averaging for Invariant and Equivariant Network Design
• Graph Contrastive Learning with Cohesive Subgraph Awareness
• MuGSI: Distilling GNNs with Multi-Granularity Structural Information for Graph Classification
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• On Graph Neural Networks versus Graph-Augmented MLPs
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
• Ranking Structured Objects with Graph Neural Networks
• A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions
• Weisfeiler and Lehman Go Cellular: CW Networks
• Molecular Graph Representation Learning via Structural Similarity Information
• Reconstruction for Powerful Graph Representations
• Graph Classification by Mixture of Diverse Experts
• Learnable Structural Semantic Readout for Graph Classification
• CHILI: Chemically-Informed Large-scale Inorganic Nanomaterials Dataset for Advancing Graph Machine Learning
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling
• Topological Graph Neural Networks
• Neural Trees for Learning on Graphs
• Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings
• Partition and Code: learning how to compress graphs
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels
• Graphlets in multilayer networks
• NuGraph2 with Context-Aware Inputs: Physics-Inspired Improvements in Semantic Segmentation
• Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
• RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs
• TME-BNA: Temporal Motif-Preserving Network Embedding with Bicomponent Neighbor Aggregation
• Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithm