The Expressive Power of Graph Neural Networks: A Survey

Bingxue Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, Zhong Liu

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.

Benchmark Results

Tested on 6 datasets 16 baseline values reported too low

Tables show presented results in global context (best 3 papers + GCN + MLP).

Classic

Cora

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GraphSAGE+CNA code ↗ GNN global	0.9418 ±0.0033	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
2	GCN+CNA code ↗ GNN global	0.9366 ±0.0048	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
3	TransformerConv code ↗ GNN global	0.9350 ±0.0058	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
21	GCN GNN baseline actual #21 vs paper #599 578 places worse	0.9004 best reported	actual #21 vs paper #599 578 places worse paper 0.8110 ±0.0030 best at pub: Language is All a Graph Needs (2023) best today: Understanding Heterophily for Graph Neural Networks (ICML 2024) paper 0.8110 ±0.0030 Δ at pub 0.0668 Δ today 0.0894
39	SAGE GNN global	0.8911 ±0.0012	Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment
44	GAT GNN baseline actual #44 vs paper #578 534 places worse	0.8897 ±0.0014 best reported	actual #44 vs paper #578 534 places worse paper 0.8140 ±0.0100 best at pub: Learned Low Precision Graph Neural Networks (2020) best today: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.8140 ±0.0100 Δ at pub 0.0750 Δ today 0.0757
141	GraphSAGE GNN baseline actual #141 vs paper #636 495 places worse	0.8708 ±0.0085 best reported	actual #141 vs paper #636 495 places worse paper 0.8040 ±0.0040 best at pub: From Node Interaction to Hop Interaction: New Effective and Scalable Graph Learning Paradigm (2022) best today: Large Language Model Meets Graph Neural Network in Knowledge Distillation (AAAI 2024) paper 0.8040 ±0.0040 Δ at pub 0.0650 Δ today 0.0668
145	ID-GNN GNN baseline	0.8700 ±0.2200	This paper
165	GIN GNN baseline actual #165 vs paper #741 576 places worse	0.8660 ±0.0091 best reported	actual #165 vs paper #741 576 places worse paper 0.7680 ±0.0090 best at pub: Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings (TMLR 2022) best today: Large Language Model Meets Graph Neural Network in Knowledge Distillation (AAAI 2024) paper 0.7680 ±0.0090 Δ at pub 0.0500 Δ today 0.0980
207	Geom-GCN GNN baseline actual #207 vs paper #207	0.8540 ±0.0040	actual #207 vs paper #207 paper 0.8540 ±0.0040 prev best: Non-Local Graph Neural Networks (2020) Improvement within reported uncertainty; not highlighted. paper 0.8540 ±0.0040 Δ at pub 0.0010
282	MM-GNN GNN baseline	0.8420 ±0.0060	This paper
304	GNN-HF GNN baseline	0.8400 ±0.0020	This paper
316	GraphSNN GNN baseline actual #316 vs paper #316	0.8380 ±0.0120	actual #316 vs paper #316 paper 0.8380 ±0.0120 prev best: Union Subgraph Neural Networks (AAAI 2023) paper 0.8380 ±0.0120 Δ at pub 0.0836
328	GNN-LF GNN baseline	0.8370 ±0.0010	This paper
509	PEG GNN baseline	0.8220 ±0.0010	This paper
698	Eigen-GNN GNN baseline	0.7890 ±0.0070	This paper
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks
777	CL-GNN GNN baseline	0.7480 ±0.0010	This paper

CiteSeer

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	CNA code ↗ GNN global	0.9575 ±0.0058	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
2	IS-GIB code ↗ Hyb global	0.9390 ±0.0187	Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization code ↗
3	EERM code ↗ GNN global	0.9112 ±0.0145	Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization code ↗
15	GNN-LF GNN baseline actual #15 vs paper #457 442 places worse	0.8366 ±0.0006 best reported	actual #15 vs paper #457 442 places worse paper 0.7200 ±0.0030 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.7200 ±0.0030 Δ at pub 0.1166
16	GNN-HF GNN baseline actual #16 vs paper #426 410 places worse	0.8356 ±0.0010 best reported	actual #16 vs paper #426 410 places worse paper 0.7230 ±0.0030 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.7230 ±0.0030 Δ at pub 0.1126
35	GAT GNN baseline actual #35 vs paper #561 526 places worse	0.8080 ±0.0026 best reported	actual #35 vs paper #561 526 places worse paper 0.7090 ±0.0070 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.7090 ±0.0070 Δ at pub 0.0990
44	GCN GNN baseline actual #44 vs paper #616 572 places worse	0.8033 ±0.0088 best reported	actual #44 vs paper #616 572 places worse paper 0.7010 ±0.0040 best at pub: Gophormer: Ego-Graph Transformer for Node Classification (2021) best today: NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification (2024) paper 0.7010 ±0.0040 Δ at pub 0.0933 Δ today 0.1023
61	GraphSAGE GNN baseline actual #61 vs paper #634 573 places worse	0.7923 ±0.0053 best reported	actual #61 vs paper #634 573 places worse paper 0.6960 ±0.0030 best at pub: Gophormer: Ego-Graph Transformer for Node Classification (2021) paper 0.6960 ±0.0030 Δ at pub 0.0963
88	Geom-GCN GNN baseline actual #88 vs paper #135 47 places worse	0.7799 ±0.0115 best reported	actual #88 vs paper #135 47 places worse paper 0.7600 ±0.0150 best at pub: Feature Transportation Improves Graph Neural Networks (AAAI 2023) best today: Graph Neural Reaction Diffusion Models Submitted to the editors June 2023. Accepted in March 2024. (2024) Difference within reported uncertainty; not counted as underperformance. paper 0.7600 ±0.0150 Δ at pub 0.0199 Δ today 0.0199
203	AM-GCN Hyb baseline	0.7450 ±0.0100	This paper
218	ID-GNN GNN baseline	0.7420 ±0.0100	This paper
259	SAGE code ↗ GNN global	0.7361 ±0.0190	Efficient Tuning and Inference for Large Language Models on Textual Graphs code ↗
275	GraphSNN GNN baseline actual #275 vs paper #275	0.7350 ±0.0160	actual #275 vs paper #275 paper 0.7350 ±0.0160 prev best: Union Subgraph Neural Networks (AAAI 2023) paper 0.7350 ±0.0160 Δ at pub 0.0882
329	MM-GNN GNN baseline	0.7300 ±0.0060	This paper
350	MLP code ↗ Trad global	0.7289 ±0.0010	Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax code ↗
389	GIN GNN baseline actual #389 vs paper #696 307 places worse	0.7250 ±0.0080 best reported	actual #389 vs paper #696 307 places worse paper 0.6770 ±0.0030 best at pub: Towards Self-Explainable Graph Neural Network (2021) paper 0.6770 ±0.0030 Δ at pub 0.0480
468	PEG GNN baseline	0.7190 ±0.0010	This paper
732	Eigen-GNN GNN baseline	0.6650 ±0.0030	This paper

PubMed

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	LGTL GT global	0.9518 ±0.0011	Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models
2	MixHop (LO) code ↗ GNN global	0.9513 ±0.0038	LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework code ↗
3	GraphSAGE (LO) code ↗ GNN global	0.9511 ±0.0036	LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework code ↗
18	GCN GNN baseline actual #18 vs paper #628 610 places worse	0.9296 ±0.0015 best reported	actual #18 vs paper #628 610 places worse paper 0.7860 ±0.0060 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7860 ±0.0060 Δ at pub 0.1110 Δ today 0.1436
20	GAT GNN baseline actual #20 vs paper #661 641 places worse	0.9233 ±0.0018 best reported	actual #20 vs paper #661 641 places worse paper 0.7820 ±0.0080 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7820 ±0.0080 Δ at pub 0.1150 Δ today 0.1413
69	Geom-GCN GNN baseline actual #69 vs paper #160 91 places worse	0.9005 ±0.0047 best reported	actual #69 vs paper #160 91 places worse paper 0.8790 ±0.0250 best at pub: Feature Transportation Improves Graph Neural Networks (AAAI 2023) best today: Graph Neural Reaction Diffusion Models Submitted to the editors June 2023. Accepted in March 2024. (2024) Difference within reported uncertainty; not counted as underperformance. paper 0.8790 ±0.0250 Δ at pub 0.0215 Δ today 0.0215
116	SAGE GNN global	0.8881 ±0.0015	Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment
125	GraphSAGE GNN baseline actual #125 vs paper #711 586 places worse	0.8864 ±0.0030 best reported	actual #125 vs paper #711 586 places worse paper 0.7750 ±0.0080 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) best today: Non-backtracking Graph Neural Networks (TMLR 2023) paper 0.7750 ±0.0080 Δ at pub 0.1015 Δ today 0.1114
157	GIN GNN baseline actual #157 vs paper #739 582 places worse	0.8810 best reported	actual #157 vs paper #739 582 places worse paper 0.7700 ±0.0050 best at pub: Learning Conjoint Attentions for Graph Neural Nets (NeurIPS 2021) best today: UGSL: A Unified Framework for Benchmarking Graph Structure Learning (2023) paper 0.7700 ±0.0050 Δ at pub 0.0376 Δ today 0.1110
163	GNN-HF GNN baseline actual #163 vs paper #410 247 places worse	0.8783 ±0.0010 best reported	actual #163 vs paper #410 247 places worse paper 0.8040 ±0.0030 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.8040 ±0.0030 Δ at pub 0.0743
168	GNN-LF GNN baseline actual #168 vs paper #418 250 places worse	0.8779 ±0.0005 best reported	actual #168 vs paper #418 250 places worse paper 0.8030 ±0.0020 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.8030 ±0.0020 Δ at pub 0.0749
210	MLP code ↗ Trad global	0.8690 ±0.0074	On the Equivalence of Graph Convolution and Mixup code ↗
422	MM-GNN GNN baseline	0.8030 ±0.0070	This paper
463	PEG GNN baseline	0.7990 ±0.0010	This paper
489	GraphSNN GNN baseline actual #489 vs paper #489	0.7960 ±0.0140	actual #489 vs paper #489 paper 0.7960 ±0.0140 prev best: Union Subgraph Neural Networks (AAAI 2023) paper 0.7960 ±0.0140 Δ at pub 0.0284
629	Eigen-GNN GNN baseline	0.7860 ±0.0010	This paper
756	CL-GNN GNN baseline	0.7650 ±0.0020	This paper

ZINC

Global leaderboard →

#	Model	MAE ↓	Paper
1	TIGT GT global	0.0140 ±0.0010	Topology-Informed Graph Transformer
2	FloydNet code ↗ Hyb global	0.0160	FloydNet: A Learning Paradigm for Global Relational Reasoning code ↗
3	GSSC code ↗ GT global	0.0190 ±0.0010	What Can We Learn from State Space Models for Machine Learning on Graphs? code ↗
54	IGN GNN baseline	0.0450 ±0.0060	This paper
69	GIN GNN global	0.0880 ±0.0020	Using Random Noise Equivariantly to Boost Graph Neural Networks Universally

TU Dortmund

MUTAG

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9910 ±0.0030	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	ID-GNN+BEC Hyb global	0.9830 ±0.0360	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
3	SupCosine Hyb global	0.9830 ±0.0250	Supervised Contrastive Learning with Structure Inference for Graph Classification
4	ID-GNN GNN baseline actual #4 vs paper #157 153 places worse	0.9780 ±0.0370 best reported	actual #4 vs paper #157 153 places worse paper 0.9040 ±0.0540 best today: Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature (KDD 2025) Difference within reported uncertainty; not counted as underperformance. paper 0.9040 ±0.0540 Δ today 0.0740
12	KP-GNN GNN baseline	0.9610 ±0.0460	This paper
20	SAGNN GNN baseline	0.9520 ±0.0300	This paper
24	GraphSNN GNN baseline actual #24 vs paper #24	0.9470 ±0.0190	actual #24 vs paper #24 paper 0.9470 ±0.0190 prev best: Union Subgraph Neural Networks (AAAI 2023) paper 0.9470 ±0.0190 Δ at pub 0.1066
32	CLIP GNN baseline	0.9390 ±0.0400	This paper
39	GIN GNN baseline actual #39 vs paper #237 198 places worse	0.9330 ±0.0290 best reported	actual #39 vs paper #237 198 places worse paper 0.8940 ±0.0560 best at pub: ProtGNN: Towards Self-Explaining Graph Neural Networks (AAAI 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.8940 ±0.0560 Δ at pub 0.0390
63	GCN GNN baseline actual #63 vs paper #271 208 places worse	0.9220 ±0.0440 best reported	actual #63 vs paper #271 208 places worse paper 0.8910 ±0.0580 best at pub: Breaking the Limits of Message Passing Graph Neural Networks (ICML 2021) best today: Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature (KDD 2025) Difference within reported uncertainty; not counted as underperformance. paper 0.8910 ±0.0580 Δ today 0.0310
64	GSN GNN baseline	0.9220 ±0.0750	This paper
73	ESAN GNN baseline actual #73 vs paper #105 32 places worse	0.9200 ±0.0500 best reported	actual #73 vs paper #105 32 places worse paper 0.9110 ±0.0700 best at pub: Asynchronous Neural Networks for Learning in Graphs (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.9110 ±0.0700 Δ at pub 0.0090
103	GNN-AK+ GNN baseline	0.9130 ±0.0700	This paper
128	GNNML3 GNN baseline	0.9090 ±0.0550	This paper
140	PPGN GNN baseline	0.9060 ±0.0870	This paper
158	GraphSAGE GNN baseline actual #158 vs paper #446 288 places worse	0.9040 ±0.0780 best reported	actual #158 vs paper #446 288 places worse paper 0.8510 ±0.0760 best at pub: Asynchronous Neural Networks for Learning in Graphs (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8510 ±0.0760 Δ at pub 0.0530
183	GAT GNN baseline	0.9010 ±0.0580	This paper
193	Twin-GNN GNN baseline	0.9000 ±0.0390	This paper
194	GNNML1 GNN baseline	0.9000 ±0.0430	This paper
336	NGNN GNN baseline	0.8790 ±0.0820	This paper
359	3-hop GNN GNN baseline	0.8760 ±0.0070	This paper
398	Ring-GNN GNN baseline	0.8680 ±0.0640	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
420	3-GNN GNN baseline	0.8610 ±0.0010	This paper
492	IGN GNN baseline	0.8390 ±0.1300	This paper
718	SAGE code ↗ GNN global	0.7490 ±0.0870	Fast Graph Representation Learning with PyTorch Geometric code ↗
745	SUN GNN baseline	0.7270 ±0.0580	This paper

PROTEINS

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9410 ±0.0330	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	GRDL GNN global	0.8260 ±0.0120	Graph Classification via Reference Distribution Learning: Theory and Practice
3	GMN code ↗ Hyb global	0.8225	Memory-Based Graph Networks code ↗
15	KP-GNN GNN baseline	0.8010 ±0.0430	This paper
22	SAGNN GNN baseline	0.7980 ±0.0380	This paper
33	PIN GNN baseline	0.7880 ±0.0440	This paper
32	GIN GNN baseline actual #32 vs paper #135 103 places worse	0.7880 ±0.0410 best reported	actual #32 vs paper #135 103 places worse paper 0.7620 ±0.0280 best at pub: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7620 ±0.0280 Δ at pub 0.0080 Δ today 0.0260
39	GraphSNN GNN baseline actual #39 vs paper #40 1 place worse	0.7840 ±0.0270	actual #39 vs paper #40 1 place worse paper 0.7840 ±0.0270 prev best: Union Subgraph Neural Networks (AAAI 2023) paper 0.7840 ±0.0270 Δ at pub 0.0662
49	GAT GNN baseline actual #49 vs paper #154 105 places worse	0.7800 ±0.0300 best reported	actual #49 vs paper #154 105 places worse paper 0.7590 ±0.0430 best at pub: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7590 ±0.0430 Δ at pub 0.0210
67	SAGE GNN global	0.7726 ±0.0228	Semi-Supervised Hierarchical Graph Classification
73	PPGN GNN baseline	0.7720 ±0.0470	This paper
79	CLIP GNN baseline	0.7710 ±0.0440	This paper
80	GNN-AK+ GNN baseline	0.7710 ±0.0570	This paper
78	ESAN GNN baseline actual #78 vs paper #154 76 places worse	0.7710 ±0.0460 best reported	actual #78 vs paper #154 76 places worse paper 0.7590 ±0.0430 best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7590 ±0.0430 Δ today 0.0120
92	PG-GNN GNN baseline	0.7680 ±0.0380	This paper
102	GSN GNN baseline	0.7660 ±0.0500	This paper
100	IGN GNN baseline	0.7660 ±0.0550	This paper
119	MPSN GNN baseline	0.7640 ±0.0330	This paper
120	GNNML3 GNN baseline	0.7640 ±0.0510	This paper
148	GCN GNN baseline actual #148 vs paper #224 76 places worse	0.7600 ±0.0320 best reported	actual #148 vs paper #224 76 places worse paper 0.7520 ±0.0510 best at pub: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) best today: Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7520 ±0.0510 Δ at pub 0.0080 Δ today 0.0080
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
155	GraphSAGE GNN baseline actual #155 vs paper #464 309 places worse	0.7590 ±0.0320 best reported	actual #155 vs paper #464 309 places worse paper 0.6920 ±0.1000 best at pub: On Structural Expressive Power of Graph Transformers (KDD 2023) best today: Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.6920 ±0.1000 Δ at pub 0.0670 Δ today 0.0670
165	SUN GNN baseline	0.7580 ±0.0500	This paper
166	GNNML1 GNN baseline	0.7580 ±0.0490	This paper
176	Ring-GNN GNN baseline	0.7570 ±0.0290	This paper
192	3-GNN GNN baseline	0.7550 ±0.0010	This paper
203	ID-GNN GNN baseline	0.7540 ±0.0270	This paper
214	3-hop GNN GNN baseline	0.7530 ±0.0040	This paper
305	NGNN GNN baseline	0.7420 ±0.0370	This paper

SOTA performance (not significantly different from the best) Baseline / comparison (this paper) Global context (other papers) Best at pub — reported result worse than the best known when published (best reported in green) Best at pub — reported value improved over the best known when published