The Expressive Power of Graph Neural Networks: A Survey
arXiv:2308.08235 · doi:10.1109/TKDE.2024.3523700
Abstract
Graph neural networks (GNNs) are effective machine learning models for many graph-related applications. Despite their empirical success, many research efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive power. Early works in this domain mainly focus on studying the graph isomorphism recognition ability of GNNs, and recent works try to leverage the properties such as subgraph counting and connectivity learning to characterize the expressive power of GNNs, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for models for enhancing expressive power under different forms of definition. Concretely, the models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.
References in corpus (15)
- A Comprehensive Survey on Graph Neural Networks
- KGAT: Knowledge Graph Attention Network for Recommendation
- Learning Combinatorial Optimization Algorithms over Graphs
- Deep learning for molecular design - a review of the state of the art
- AM-GCN: Adaptive Multi-channel Graph Convolutional Networks
- Everything is Connected: Graph Neural Networks
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
- SIGN: Scalable Inception Graph Neural Networks
- Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
- Measuring abstract reasoning in neural networks
- MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distribution
- Inductive Meta-path Learning for Schema-complex Heterogeneous Information Networks
- Sequential Attention Source Identification Based on Feature Representation
- Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
- On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties