How Powerful are Graph Neural Networks?

Abstract

Graph Neural Networks (GNNs) are an effective framework for representation learning of graphs. GNNs follow a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs to capture different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theoretical findings on a number of graph classification benchmarks, and demonstrate that our model achieves state-of-the-art performance.

References in corpus (12)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Neural Message Passing for Quantum Chemistry
• Molecular Graph Convolutions: Moving Beyond Fingerprints
• Representation Learning on Graphs with Jumping Knowledge Networks
• Convolutional Networks on Graphs for Learning Molecular Fingerprints
• Interaction Networks for Learning about Objects, Relations and Physics
• Graph Isomorphism in Quasipolynomial Time
• Measuring abstract reasoning in neural networks
• Anonymous Walk Embeddings
• Graph Capsule Convolutional Neural Networks
• Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs
• The Weisfeiler-Lehman Method and Graph Isomorphism Testing

Cited by in corpus (178)

• Graph Contrastive Learning with Augmentations
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Scaling Graph Neural Networks with Approximate PageRank
• Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
• DeepGCNs: Making GCNs Go as Deep as CNNs
• Towards Sparse Hierarchical Graph Classifiers
• Examining COVID-19 Forecasting using Spatio-Temporal Graph Neural Networks
• InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization
• DGCN: Diversified Recommendation with Graph Convolutional Networks
• EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks
• Understanding Pooling in Graph Neural Networks
• Hierarchical Generation of Molecular Graphs using Structural Motifs
• DeepGCNs: Can GCNs Go as Deep as CNNs?
• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• StarNet: Targeted Computation for Object Detection in Point Clouds
• Generative Models for Automatic Chemical Design
• GoGNN: Graph of Graphs Neural Network for Predicting Structured Entity Interactions
• D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
• Deep learning of contagion dynamics on complex networks
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization
• Rethinking Graph Transformers with Spectral Attention
• Three-Dimensionally Embedded Graph Convolutional Network (3DGCN) for Molecule Interpretation
• When Does Self-Supervision Help Graph Convolutional Networks?
• Heterogeneous Deep Graph Infomax
• Directed Graph Convolutional Network
• Infrared and 3D skeleton feature fusion for RGB-D action recognition
• Tackling Over-Smoothing for General Graph Convolutional Networks
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
• Quantum Graph Neural Networks
• TabularNet: A Neural Network Architecture for Understanding Semantic Structures of Tabular Data
• Implicit Graph Neural Networks
• Revisiting Over-smoothing in Deep GCNs
• Multiple instance learning with graph neural networks
• BertGCN: Transductive Text Classification by Combining GCN and BERT
• Temporal Graph Convolutional Networks for Automatic Seizure Detection
• MagNet: A Neural Network for Directed Graphs
• Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Watermarking Graph Neural Networks by Random Graphs
• Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
• Learning to Extend Molecular Scaffolds with Structural Motifs
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• Learning Graph Neural Networks with Positive and Unlabeled Nodes
• Multi-View Graph Neural Networks for Molecular Property Prediction
• Cell Complex Neural Networks
• Natural Graph Networks
• On the design space between molecular mechanics and machine learning force fields
• paper2repo: GitHub Repository Recommendation for Academic Papers
• Inductive Matrix Completion Based on Graph Neural Networks
• Edge-labeling Graph Neural Network for Few-shot Learning
• Stochastic Graph Neural Networks
• Bag of Tricks for Node Classification with Graph Neural Networks
• Can Graph Neural Networks Count Substructures?
• Hierarchical Graph-to-Graph Translation for Molecules
• Multi-hop Reading Comprehension across Multiple Documents by Reasoning over Heterogeneous Graphs
• Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge
• Scalable Graph Neural Networks for Heterogeneous Graphs
• GraphCL: Contrastive Self-Supervised Learning of Graph Representations
• Understanding and Resolving Performance Degradation in Graph Convolutional Networks
• Understanding Negative Sampling in Graph Representation Learning
• Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning
• What graph neural networks cannot learn: depth vs width
• Fake News Detection in Social Media using Graph Neural Networks and NLP Techniques: A COVID-19 Use-case
• Permutation Invariant Graph Generation via Score-Based Generative Modeling
• Adversarial Defense Framework for Graph Neural Network
• A Behavioral Approach to Visual Navigation with Graph Localization Networks
• Capsule Neural Networks for Graph Classification using Explicit Tensorial Graph Representations
• Hit and Lead Discovery with Explorative RL and Fragment-based Molecule Generation
• NRGNN: Learning a Label Noise-Resistant Graph Neural Network on Sparsely and Noisily Labeled Graphs
• Pointer Graph Networks
• Motif-Driven Contrastive Learning of Graph Representations
• Understanding Isomorphism Bias in Graph Data Sets
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Unsupervised Graph Outlier Detection: Problem Revisit, New Insight, and Superior Method
• Geometry-enhanced graph neural network for learning the smoothness of glassy dynamics from static structure
• Learning to Drop: Robust Graph Neural Network via Topological Denoising
• Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures
• Deep Graph Neural Networks with Shallow Subgraph Samplers
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Advances in Continual Graph Learning for Anti-Money Laundering Systems: A Comprehensive Review
• Factor Graph Neural Network
• Stability and Generalization of Graph Convolutional Neural Networks
• Discriminative structural graph classification
• Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling
• Learning Universal Graph Neural Network Embeddings With Aid Of Transfer Learning
• Directional Graph Networks
• Knowledge-aware Contrastive Molecular Graph Learning
• Frame Averaging for Invariant and Equivariant Network Design
• DyGCN: Dynamic Graph Embedding with Graph Convolutional Network
• Can Graph Neural Networks Help Logic Reasoning?
• Multimodal Fusion Refiner Networks
• From Local Structures to Size Generalization in Graph Neural Networks
• Towards Domain-Agnostic Contrastive Learning
• Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
• L${}^2$-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks
• Where are the Keys? -- Learning Object-Centric Navigation Policies on Semantic Maps with Graph Convolutional Networks
• Artificial Intelligence in Drug Discovery: Applications and Techniques
• Learning Unknown from Correlations: Graph Neural Network for Inter-novel-protein Interaction Prediction
• Bidirectional Graph Reasoning Network for Panoptic Segmentation
• SpiralNet++: A Fast and Highly Efficient Mesh Convolution Operator
• On the Consistency of GNN Explanations for Malware Detection
• Neural Markov Logic Networks
• Stochastic Aggregation in Graph Neural Networks
• End-to-end Microphone Permutation and Number Invariant Multi-channel Speech Separation
• GNN-XML: Graph Neural Networks for Extreme Multi-label Text Classification
• EPNE: Evolutionary Pattern Preserving Network Embedding
• GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks
• GN-Transformer: Fusing Sequence and Graph Representation for Improved Code Summarization
• Price-aware Recommendation with Graph Convolutional Networks
• Equivariant Maps for Hierarchical Structures
• A framework for constructing a huge name disambiguation dataset: algorithms, visualization and human collaboration
• Adversarial Graph Disentanglement
• Explainable Deep Relational Networks for Predicting Compound-Protein Affinities and Contacts
• EvoNet: A Neural Network for Predicting the Evolution of Dynamic Graphs
• Graph Neural Network Architecture Search for Molecular Property Prediction
• Multitask Learning On Graph Neural Networks Applied To Molecular Property Predictions
• Fundamental Limits of Deep Graph Convolutional Networks
• Missing Data Estimation in Temporal Multilayer Position-aware Graph Neural Network (TMP-GNN)
• A pipeline for fair comparison of graph neural networks in node classification tasks
• Graph Sequential Network for Reasoning over Sequences
• Highly Accurate Disease Diagnosis and Highly Reproducible Biomarker Identification with PathFormer
• A benchmark study on reliable molecular supervised learning via Bayesian learning
• Molecular Dynamics and Machine Learning Unlock Possibilities in Beauty Design -- A Perspective
• A comprehensive study on the prediction reliability of graph neural networks for virtual screening
• Feature Interaction-aware Graph Neural Networks
• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
• Train on Small, Play the Large: Scaling Up Board Games with AlphaZero and GNN
• Local, global and scale-dependent node roles
• An In-depth Summary of Recent Artificial Intelligence Applications in Drug Design
• Enhance Information Propagation for Graph Neural Network by Heterogeneous Aggregations
• Stability of Neural Networks on Riemannian Manifolds
• Lossless Compression of Structured Convolutional Models via Lifting
• PINE: Universal Deep Embedding for Graph Nodes via Partial Permutation Invariant Set Functions
• GraLSP: Graph Neural Networks with Local Structural Patterns
• Learning with Molecules beyond Graph Neural Networks
• Hop Sampling: A Simple Regularized Graph Learning for Non-Stationary Environments
• Detecting structural perturbations from time series with deep learning
• HeMI: Multi-view Embedding in Heterogeneous Graphs
• CopulaGNN: Towards Integrating Representational and Correlational Roles of Graphs in Graph Neural Networks
• Efficient Colon Cancer Grading with Graph Neural Networks
• Identifying Non-Control Security-Critical Data through Program Dependence Learning
• Spotting Silent Buffer Overflows in Execution Trace through Graph Neural Network Assisted Data Flow Analysis
• Which Hyperparameters to Optimise? An Investigation of Evolutionary Hyperparameter Optimisation in Graph Neural Network For Molecular Property Prediction
• Knowledge Embedding Based Graph Convolutional Network
• Correlation-aware Unsupervised Change-point Detection via Graph Neural Networks
• Learning Conjoint Attentions for Graph Neural Nets
• Heterogeneous Graph based Deep Learning for Biomedical Network Link Prediction
• TreeRNN: Topology-Preserving Deep GraphEmbedding and Learning
• On Local Aggregation in Heterophilic Graphs
• Convergent Graph Solvers
• Learning Context-Aware Representations of Subtrees
• LW-GCN: A Lightweight FPGA-based Graph Convolutional Network Accelerator
• Out-of-Vocabulary Embedding Imputation with Grounded Language Information by Graph Convolutional Networks
• CGCL: Collaborative Graph Contrastive Learning without Handcrafted Graph Data Augmentations
• Relational Reasoning Network (RRN) for Anatomical Landmarking
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version
• Pretraining Neural Architecture Search Controllers with Locality-based Self-Supervised Learning
• Graph Neural Networks for Inconsistent Cluster Detection in Incremental Entity Resolution
• Improving Expressivity of Graph Neural Networks
• Towards Self-Explainable Graph Neural Network
• LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising
• Dynamic Virtual Graph Significance Networks for Predicting Influenza
• Fine-Grained Chemical Entity Typing with Multimodal Knowledge Representation
• Knowledge as Invariance -- History and Perspectives of Knowledge-augmented Machine Learning
• Online Graph Dictionary Learning
• A Collective Learning Framework to Boost GNN Expressiveness
• Towards Better Graph Representation: Two-Branch Collaborative Graph Neural Networks for Multimodal Marketing Intention Detection
• Pairwise Half-graph Discrimination: A Simple Graph-level Self-supervised Strategy for Pre-training Graph Neural Networks
• Deep Fraud Detection on Non-attributed Graph
• Non-autoregressive electron flow generation for reaction prediction
• Graph Structural-topic Neural Network
• An Energy-Based View of Graph Neural Networks
• Characterizing and Understanding GCNs on GPU
• PiNet: Attention Pooling for Graph Classification
• Cross-Modality Protein Embedding for Compound-Protein Affinity and Contact Prediction
• Action Recognition with Kernel-based Graph Convolutional Networks