The Expressive Power of Graph Neural Networks: A Survey
It provides a foundational resource for researchers in machine learning and graph theory by consolidating theoretical advancements in GNN expressiveness, though it is incremental as a survey paper.
This survey addresses the lack of comprehensive summaries on models enhancing the expressive power of graph neural networks (GNNs), reviewing them across three categories: graph feature enhancement, graph topology enhancement, and GNN architecture enhancement.
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.