Non-Local Graph Neural Networks

Meng Liu, Zhengyang Wang, Shuiwang Ji

Abstract

Modern graph neural networks (GNNs) learn node embeddings through multilayer local aggregation and achieve great success in applications on assortative graphs. However, tasks on disassortative graphs usually require non-local aggregation. In addition, we find that local aggregation is even harmful for some disassortative graphs. In this work, we propose a simple yet effective non-local aggregation framework with an efficient attention-guided sorting for GNNs. Based on it, we develop various non-local GNNs. We perform thorough experiments to analyze disassortative graph datasets and evaluate our non-local GNNs. Experimental results demonstrate that our non-local GNNs significantly outperform previous state-of-the-art methods on my_colorseven benchmark datasets of disassortative graphs, in terms of both model performance and efficiency.

Benchmark Results

Tested on 8 datasets

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 global	0.9004	Understanding Heterophily for Graph Neural Networks
66	NLGAT Hyb baseline	0.8850 ±0.0180	This paper
89	NLGCN Hyb baseline	0.8810 ±0.0100	This paper
146	Geom-GCN-g ext data GNN baseline	0.8700	This paper
207	Geom-GCN ext data GNN baseline actual #207 vs paper #213 6 places worse	0.8540 ±0.0040 best reported	actual #207 vs paper #213 6 places worse paper 0.8530 best today: The Expressive Power of Graph Neural Networks: A Survey (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.8530 Δ today 0.0010
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks
739	NLMLP Trad baseline	0.7690 ±0.0180	This paper
794	Geom-GCN-S ext data GNN baseline	0.7330	This paper

Heterophilic Graphs

Texas

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	P^2GNN Hyb global	0.9672 ±0.0147	$P^2$GNN: Two Prototype Sets to boost GNN Performance
2	DoG code ↗ ext data GNN global	0.9660 ±0.0210	Diffusion on Graph: Augmentation of Graph Structure for Node Classification code ↗
3	GPF-plus code ↗ ext data GNN global	0.9583 ±0.0419	ProG: A Graph Prompt Learning Benchmark code ↗
34	MLP Trad baseline actual #34 vs paper #221 187 places worse	0.9230 ±0.0070 best reported	actual #34 vs paper #221 187 places worse paper 0.8130 ±0.0710 best today: Design your own universe: a physics-informed agnostic method for enhancing graph neural networks (2024) Difference within reported uncertainty; not counted as underperformance. paper 0.8130 ±0.0710 Δ today 0.1100
53	GraphSAGE code ↗ GNN global	0.9000 ±0.0365	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
136	NLMLP Trad baseline	0.8540 ±0.0380	This paper
147	H_2GCN GNN baseline	0.8490 ±0.0680	This paper
211	GAT GNN baseline actual #211 vs paper #542 331 places worse	0.8162 ±0.0645 best reported	actual #211 vs paper #542 331 places worse paper 0.5790 ±0.0610 best at pub: Heterophilic Graphs (ICLR 2020) best today: Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (2025) paper 0.5790 ±0.0610 Δ at pub 0.0048 Δ today 0.2372
213	SimP-GCN GNN baseline	0.8160	This paper
257	GCN GNN baseline actual #257 vs paper #489 232 places worse	0.6110 ±0.0700	actual #257 vs paper #489 232 places worse paper 0.6110 ±0.0700 prev best: Heterophilic Graphs (ICLR 2020) best today: Graph Wave Networks (WWW 2025) Improvement within reported uncertainty; not highlighted. paper 0.6110 ±0.0700 Δ at pub 0.0894 Δ today 0.1823
348	Geom-GCN-S ext data GNN baseline actual #348 vs paper #348	0.7350	actual #348 vs paper #348 paper 0.7350 prev best: Heterophilic Graphs (ICLR 2020) paper 0.7350 Δ at pub 0.1377
350	Geom-GCN-g ext data GNN baseline	0.7310	This paper
415	Geom-GCN ext data GNN baseline	0.6760	This paper
438	NLGCN Hyb baseline	0.6550 ±0.0660	This paper
467	NLGAT Hyb baseline	0.6260 ±0.0710	This paper

Cornell

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	P^2GNN Hyb global	0.9541 ±0.0272	$P^2$GNN: Two Prototype Sets to boost GNN Performance
2	ACM-GCN code ↗ GNN global	0.9480 ±0.0380	Heterophily-informed Message Passing code ↗
3	RF-GCN GNN global	0.9429	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
24	MLP Trad baseline actual #24 vs paper #160 136 places worse	0.9136 ±0.0070 best reported	actual #24 vs paper #160 136 places worse paper 0.8160 ±0.0630 best today: Node-oriented Spectral Filtering for Graph Neural Networks (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8160 ±0.0630 Δ today 0.0976
92	NLMLP Trad baseline	0.8490 ±0.0570	This paper
110	SimP-GCN GNN baseline	0.8410	This paper
138	SAGE GNN global	0.8269	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
149	H_2GCN GNN baseline	0.8220 ±0.0600	This paper
226	Geom-GCN-S ext data GNN baseline	0.7540	This paper
311	Geom-GCN-g ext data GNN baseline	0.6700	This paper
342	Geom-GCN ext data GNN baseline actual #342 vs paper #371 29 places worse	0.6412 best reported	actual #342 vs paper #371 29 places worse paper 0.6080 best today: Steering Graph Neural Networks with Pinning Control (2023) paper 0.6080 Δ today 0.0332
407	NLGCN Hyb baseline	0.5760 ±0.0550	This paper
430	NLGAT Hyb baseline	0.5470 ±0.0760	This paper

Actor

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DiGGR Hyb global	0.4535 ±0.0353	Disentangled Generative Graph Representation Learning
2	TRIGON code ↗ Hyb global	0.4402 ±0.0028	Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks code ↗
3	DoG code ↗ ext data GNN global	0.4320 ±0.0120	Diffusion on Graph: Augmentation of Graph Structure for Node Classification code ↗
42	MLP Trad baseline actual #42 vs paper #229 187 places worse	0.4026 ±0.0108 best reported	actual #42 vs paper #229 187 places worse paper 0.3510 ±0.0080 best today: Heterophily-Aware Graph Attention Network (2023) paper 0.3510 ±0.0080 Δ today 0.0516
68	GraphSAGE code ↗ GNN global	0.3899 ±0.0085	A Quasi-Wasserstein Loss for Learning Graph Neural Networks code ↗
87	Geom-GCN ext data GNN baseline actual #87 vs paper #307 220 places worse	0.3810 best reported	actual #87 vs paper #307 220 places worse paper 0.3160 best today: Beyond Low-frequency Information in Graph Convolutional Networks (AAAI 2021) paper 0.3160 Δ today 0.0650
97	NLMLP Trad baseline	0.3790 ±0.0130	This paper
135	GCN GNN baseline actual #135 vs paper #342 207 places worse	0.3030 ±0.0160	actual #135 vs paper #342 207 places worse paper 0.3030 ±0.0160 prev best: Heterophilic Graphs (ICLR 2020) best today: Beyond Low-frequency Information in Graph Convolutional Networks (AAAI 2021) paper 0.3030 ±0.0160 Δ at pub 0.0344 Δ today 0.0660
176	H_2GCN GNN baseline actual #176 vs paper #190 14 places worse	0.3622 ±0.0033 best reported	actual #176 vs paper #190 14 places worse paper 0.3590 ±0.0100 best today: Hierarchical Graph Transformer with Adaptive Node Sampling (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.3590 ±0.0100 Δ today 0.0032
177	SimP-GCN GNN baseline	0.3620	This paper
182	GAT GNN baseline actual #182 vs paper #362 180 places worse	0.2940 ±0.0120	actual #182 vs paper #362 180 places worse paper 0.2940 ±0.0120 prev best: Heterophilic Graphs (ICLR 2020) best today: Hierarchical Graph Transformer with Adaptive Node Sampling (NeurIPS 2022) Improvement within reported uncertainty; not highlighted. paper 0.2940 ±0.0120 Δ at pub 0.0095 Δ today 0.0665
248	Geom-GCN-S ext data GNN baseline actual #248 vs paper #248	0.3460	actual #248 vs paper #248 paper 0.3460 prev best: Heterophilic Graphs (ICLR 2020) paper 0.3460 Δ at pub 0.0430
301	Geom-GCN-g ext data GNN baseline	0.3200	This paper
308	NLGCN Hyb baseline	0.3160 ±0.0100	This paper
362	NLGAT Hyb baseline	0.2950 ±0.0130	This paper

Chameleon

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	Hetero-S (GAT 8-layer) code ↗ Hyb global	0.8693	The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs code ↗
2	Dir-GNN+CNA code ↗ GNN global	0.8586 ±0.0180	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
3	GAT GNN baseline actual #3 vs paper #92 89 places worse	0.8560 best reported	actual #3 vs paper #92 89 places worse paper 0.6500 ±0.0370 best today: The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs (KDD 2024) paper 0.6500 ±0.0370 Δ today 0.2060
52	GCN GNN baseline actual #52 vs paper #71 19 places worse	0.7033 best reported	actual #52 vs paper #71 19 places worse paper 0.6760 ±0.0240 best today: Understanding Heterophily for Graph Neural Networks (ICML 2024) Difference within reported uncertainty; not counted as underperformance. paper 0.6760 ±0.0240 Δ today 0.0273
55	NLGCN Hyb baseline	0.7010 ±0.0290	This paper
70	Geom-GCN-g ext data GNN baseline	0.6800	This paper
82	NLGAT Hyb baseline	0.6570 ±0.0140	This paper
107	FAGCN GNN baseline actual #107 vs paper #118 11 places worse	0.6344 ±0.0205 best reported	actual #107 vs paper #118 11 places worse paper 0.6170 best today: Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating (AAAI 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.6170 Δ today 0.0174
108	SAGE code ↗ GNN global	0.6340 ±0.0300	Scale-aware Message Passing For Graph Node Classification code ↗
121	H_2GCN GNN baseline actual #121 vs paper #138 17 places worse	0.6120 ±0.0095 best reported	actual #121 vs paper #138 17 places worse paper 0.5940 ±0.0200 best today: Hierarchical Graph Transformer with Adaptive Node Sampling (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.5940 ±0.0200 Δ today 0.0180
124	Geom-GCN ext data GNN baseline	0.6090	This paper
169	MLP Trad global	0.5429	Understanding Heterophily for Graph Neural Networks

Squirrel

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	IBG-NN GNN global	0.7763 ±0.0179	Efficient Learning on Large Graphs using a Densifying Regularity Lemma
2	Dir-GNN+CNA code ↗ GNN global	0.7747 ±0.0128	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
3	DHGNN GNN global	0.7684 ±0.0161	Directed Homophily-Aware Graph Neural Network
46	GCN GNN baseline actual #46 vs paper #72 26 places worse	0.6067 best reported	actual #46 vs paper #72 26 places worse paper 0.5490 ±0.0190 best today: Understanding Heterophily for Graph Neural Networks (ICML 2024) paper 0.5490 ±0.0190 Δ today 0.0577
54	NLGCN Hyb baseline	0.5900 ±0.0120	This paper
62	NLGAT Hyb baseline	0.5680 ±0.0250	This paper
67	GAT GNN baseline actual #67 vs paper #86 19 places worse	0.5630 ±0.0220 best reported	actual #67 vs paper #86 19 places worse paper 0.5130 ±0.0250 best today: Restructuring Graphs for Higher Homophily via Adaptive Spectral Clustering (AAAI 2022) paper 0.5130 ±0.0250 Δ today 0.0500
109	Geom-GCN-g ext data GNN baseline	0.4600	This paper
120	SAGE code ↗ GNN global	0.4460 ±0.0130	Scale-aware Message Passing For Graph Node Classification code ↗
139	FAGCN GNN baseline actual #139 vs paper #166 27 places worse	0.4259 ±0.0069 best reported	actual #139 vs paper #166 27 places worse paper 0.3970 best today: Graph Neural Reaction Diffusion Models Submitted to the editors June 2023. Accepted in March 2024. (2024) paper 0.3970 Δ today 0.0289
172	MLP code ↗ Trad global	0.3930 ±0.0079	Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification code ↗
179	Geom-GCN ext data GNN baseline actual #179 vs paper #182 3 places worse	0.3832 ±0.0092 best reported	actual #179 vs paper #182 3 places worse paper 0.3810 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.3810 Δ today 0.0022
185	H_2GCN GNN baseline	0.3790 ±0.0200	This paper

Wisconsin

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DMD++ Hyb global	0.9190 ±0.0260	When Graph Neural Networks Meet Dynamic Mode Decomposition
2	F-GREAD-BS code ↗ GNN global	0.9059 ±0.0380	Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND code ↗
3	APPNP GNN global	0.9010 ±0.0350	When Graph Neural Networks Meet Dynamic Mode Decomposition
25	NLMLP Trad baseline	0.8730 ±0.0430	This paper
34	H_2GCN GNN baseline	0.8670 ±0.0470	This paper
37	MLP Trad baseline actual #37 vs paper #45 8 places worse	0.8629 ±0.0450 best reported	actual #37 vs paper #45 8 places worse paper 0.8490 ±0.0530 best today: Is Homophily a Necessity for Graph Neural Networks? (ICLR 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.8490 ±0.0530 Δ today 0.0139
41	SimP-GCN GNN baseline	0.8550	This paper
53	GAT GNN baseline actual #53 vs paper #174 121 places worse	0.8430 ±0.0370 best reported	actual #53 vs paper #174 121 places worse paper 0.5780 ±0.0430 best today: Restructuring Graphs for Higher Homophily via Adaptive Spectral Clustering (AAAI 2022) paper 0.5780 ±0.0430 Δ today 0.2650
63	GCN GNN baseline actual #63 vs paper #171 108 places worse	0.8310 ±0.0320 best reported	actual #63 vs paper #171 108 places worse paper 0.5960 ±0.0450 best today: Restructuring Graphs for Higher Homophily via Adaptive Spectral Clustering (AAAI 2022) paper 0.5960 ±0.0450 Δ today 0.2350
69	GraphSAGE code ↗ GNN global	0.8118 ±0.0556	Graph Navier–Stokes Networks code ↗
74	Geom-GCN-S ext data GNN baseline	0.8040	This paper
132	Geom-GCN-g ext data GNN baseline	0.6940	This paper
139	Geom-GCN ext data GNN baseline actual #139 vs paper #151 12 places worse	0.6757 best reported	actual #139 vs paper #151 12 places worse paper 0.6410 best today: Global-Local Graph Neural Networks for Node-Classification (2024) paper 0.6410 Δ today 0.0347
170	NLGCN Hyb baseline	0.6020 ±0.0530	This paper
178	NLGAT Hyb baseline	0.5690 ±0.0730	This paper

LINKX Benchmarks

snap-patents

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	FaberNet GNN global	0.7510 ±0.0003	HoloNets: Spectral Convolutions do extend to Directed Graphs
2	LargeScaleNet code ↗ Hyb global	0.7505 ±0.0005	Scale-aware Message Passing For Graph Node Classification code ↗
3	DirGNN code ↗ GNN global	0.7395 ±0.0005	Scale-aware Message Passing For Graph Node Classification code ↗
16	GCN GNN baseline actual #16 vs paper #22 6 places worse	0.5102 ±0.0006 best reported	actual #16 vs paper #22 6 places worse paper 0.4570 best today: Scale-aware Message Passing For Graph Node Classification (2024) paper 0.4570 Δ today 0.0532
17	NLGCN Hyb baseline	0.5080 ±0.0040	This paper
20	NLGAT Hyb baseline	0.4830 ±0.0020	This paper
23	GAT GNN baseline	0.4540 ±0.0040	This paper
32	MLP Trad baseline actual #32 vs paper #32	0.3150 best reported	actual #32 vs paper #32 paper 0.3130 ±0.0010 best today: Understanding Heterophily for Graph Neural Networks (ICML 2024) paper 0.3130 ±0.0010 Δ today 0.0020

SOTA performance (not significantly different from the best) Baseline / comparison (this paper) Global context (other papers) Best at pub — reported value improved over the best known when published Improved at pub — later paper surpassed this result Best today — OK at publication; today's leaderboard best is elsewhere