A Survey on The Expressive Power of Graph Neural Networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningGraph LearningSurveySimilar Papers 제목 키워드 기반
The Expressive Power of Graph Neural Networks: A Survey
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 …
Subgraph CountingSurveyWeisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test
The expressive power of graph neural networks is usually measured by comparing how many pairs of graphs or nodes an architecture can possibly distinguish as non-isomorphic to those distinguishable by the $k$-dimensional …
Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey
Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, but their effectiveness is often constrained by two critical challenges: oversquashing, where the excessive compression of informat…
Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation
Graph neural networks (GNNs) can effectively model structural information of graphs, making them widely used in knowledge graph (KG) reasoning. However, existing studies on the expressive power of GNNs mainly focuses on …
The expressive power of kth-order invariant graph networks
The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yard…
Graph Neural Network