A Survey on The Expressive Power of Graph Neural Networks

Abstract

Graph neural networks (GNNs) are effective machine learning models for various graph learning problems. Despite their empirical successes, the theoretical limitations of GNNs have been revealed recently. Consequently, many GNN models have been proposed to overcome these limitations. In this survey, we provide a comprehensive overview of the expressive power of GNNs and provably powerful variants of GNNs.

arXiv comment42 pages

References in corpus (18)

• The structure and function of complex networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• KGAT: Knowledge Graph Attention Network for Recommendation
• Graph Neural Networks: A Review of Methods and Applications
• Learning Combinatorial Optimization Algorithms over Graphs
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Universal Invariant and Equivariant Graph Neural Networks
• Invariant and Equivariant Graph Networks
• Covariant Compositional Networks For Learning Graphs
• Deep Models of Interactions Across Sets
• Kernel Belief Propagation
• Generalization and Representational Limits of Graph Neural Networks
• Can Graph Neural Networks Count Substructures?
• Local algorithms in (weakly) coloured graphs
• Constant Time Graph Neural Networks

Cited by in corpus (29)

• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Principal Neighbourhood Aggregation for Graph Nets
• Graph Neural Networks: Taxonomy, Advances and Trends
• Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective
• Understanding Pooling in Graph Neural Networks
• A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
• Graph Neural Networks: Methods, Applications, and Opportunities
• Incorporating Symbolic Domain Knowledge into Graph Neural Networks
• Can Graph Neural Networks Count Substructures?
• Subgroup Generalization and Fairness of Graph Neural Networks
• Graph Neural Networks with Learnable Structural and Positional Representations
• SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks
• Building powerful and equivariant graph neural networks with structural message-passing
• How hard is to distinguish graphs with graph neural networks?
• Graph Neural Networks with Local Graph Parameters
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Equivariant Subgraph Aggregation Networks
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• On Graph Neural Networks versus Graph-Augmented MLPs
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• The expressive power of kth-order invariant graph networks
• An Overview on the Application of Graph Neural Networks in Wireless Networks
• Weisfeiler and Lehman Go Cellular: CW Networks
• Breaking the Expressive Bottlenecks of Graph Neural Networks
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks
• Fea2Fea: Exploring Structural Feature Correlations via Graph Neural Networks
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations
• Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithm