Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings

Or Feldman, A. Boyarski, Shai Feldman, D. Kogan, A. Mendelson, Chaim Baskin

Abstract

Graph isomorphism testing is usually approached via the comparison of graph invariants. Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.e., obtained via the Weisfeiler-Leman (WL) test) and spectral invariants. While the exact power of the latter is still an open question, the former is regularly criticized for its limited power, when a standard configuration of uniform pre-coloring is used. This drawback hinders the applicability of Message Passing Graph Neural Networks (MPGNNs), whose expressive power is upper bounded by the WL test. Relaxing the assumption of uniform pre-coloring, we show that one can increase the expressive power of the WL test ad infinitum. Following that, we propose an efficient pre-coloring based on spectral features that provably increases the expressive power of the vanilla WL test. The above claims are accompanied by extensive synthetic and real data experiments. The code to reproduce our experiments is available at.

Benchmark Results

Tested on 8 datasets 16 baseline values reported too low Non-standard metric on 1 dataset

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 #712 691 places worse	0.9004 best reported	actual #21 vs paper #712 691 places worse paper 0.7810 ±0.0260 best at pub: SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels (2017) best today: Understanding Heterophily for Graph Neural Networks (ICML 2024) paper 0.7810 ±0.0260 Δ at pub 0.0907 Δ today 0.1194
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 #569 525 places worse	0.8897 ±0.0014 best reported	actual #44 vs paper #569 525 places worse paper 0.8160 ±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.8160 ±0.0100 Δ at pub 0.0730 Δ today 0.0737
141	GraphSAGE GNN baseline actual #141 vs paper #434 293 places worse	0.8708 ±0.0085 best reported	actual #141 vs paper #434 293 places worse paper 0.8290 ±0.0090 best at pub: The Impact of Global Structural Information in Graph Neural Networks Applications (2020) best today: Large Language Model Meets Graph Neural Network in Knowledge Distillation (AAAI 2024) paper 0.8290 ±0.0090 Δ at pub 0.0120 Δ today 0.0418
165	GIN GNN baseline actual #165 vs paper #550 385 places worse	0.8180 ±0.0050	actual #165 vs paper #550 385 places worse paper 0.8180 ±0.0050 prev best: Learning Conjoint Attentions for Graph Neural Nets (NeurIPS 2021) best today: Large Language Model Meets Graph Neural Network in Knowledge Distillation (AAAI 2024) Improvement within reported uncertainty; not highlighted. paper 0.8180 ±0.0050 Δ at pub 0.0022 Δ today 0.0480
488	SP-GCN Hyb baseline	0.8230 ±0.0140	This paper
539	SP-GIN Hyb baseline	0.8190 ±0.0180	This paper
540	SP-GraphSAGE Hyb baseline	0.8190 ±0.0230	This paper
689	SP-GAT Hyb baseline	0.7920 ±0.0190	This paper
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks

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 ↗
35	GAT GNN baseline actual #35 vs paper #791 756 places worse	0.8080 ±0.0026 best reported	actual #35 vs paper #791 756 places worse paper 0.6410 ±0.0450 best at pub: Gophormer: Ego-Graph Transformer for Node Classification (2021) best today: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.6410 ±0.0450 Δ at pub 0.1603 Δ today 0.1670
44	GCN GNN baseline actual #44 vs paper #800 756 places worse	0.8033 ±0.0088 best reported	actual #44 vs paper #800 756 places worse paper 0.6350 ±0.0440 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.6350 ±0.0440 Δ at pub 0.1593 Δ today 0.1683
61	GraphSAGE GNN baseline actual #61 vs paper #353 292 places worse	0.7923 ±0.0053 best reported	actual #61 vs paper #353 292 places worse paper 0.7280 ±0.0060 best at pub: Gophormer: Ego-Graph Transformer for Node Classification (2021) paper 0.7280 ±0.0060 Δ at pub 0.0643
259	SAGE code ↗ GNN global	0.7361 ±0.0190	Efficient Tuning and Inference for Large Language Models on Textual Graphs code ↗
338	SP-GraphSAGE Hyb baseline	0.7290 ±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 #463 74 places worse	0.7250 ±0.0080 best reported	actual #389 vs paper #463 74 places worse paper 0.7190 ±0.0060 best at pub: Towards Self-Explainable Graph Neural Network (2021) Difference within reported uncertainty; not counted as underperformance. paper 0.7190 ±0.0060 Δ at pub 0.0060
428	SP-GAT Hyb baseline	0.7230 ±0.0150	This paper
447	SP-GCN Hyb baseline	0.7210 ±0.0080	This paper
529	SP-GIN Hyb baseline	0.7130 ±0.0060	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 #410 392 places worse	0.9296 ±0.0015 best reported	actual #18 vs paper #410 392 places worse paper 0.8040 ±0.0050 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.8040 ±0.0050 Δ at pub 0.0930 Δ today 0.1256
20	GAT GNN baseline actual #20 vs paper #458 438 places worse	0.9233 ±0.0018 best reported	actual #20 vs paper #458 438 places worse paper 0.7990 ±0.0130 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.7990 ±0.0130 Δ at pub 0.0980 Δ today 0.1243
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 #428 303 places worse	0.8864 ±0.0030 best reported	actual #125 vs paper #428 303 places worse paper 0.8020 ±0.0060 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Non-backtracking Graph Neural Networks (TMLR 2023) paper 0.8020 ±0.0060 Δ at pub 0.0690 Δ today 0.0844
157	GIN GNN baseline actual #157 vs paper #487 330 places worse	0.8810 best reported	actual #157 vs paper #487 330 places worse paper 0.7960 ±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.7960 ±0.0050 Δ at pub 0.0116 Δ today 0.0850
210	MLP code ↗ Trad global	0.8690 ±0.0074	On the Equivalence of Graph Convolution and Mixup code ↗
385	SP-GCN Hyb baseline	0.8080 ±0.0040	This paper
386	SP-GraphSAGE Hyb baseline	0.8080 ±0.0050	This paper
411	SP-GAT Hyb baseline	0.8040 ±0.0070	This paper
615	SP-GIN Hyb baseline	0.7880 ±0.0070	This paper

PPI

Global leaderboard →

Non-default metric. This paper reports Accuracy; the dataset default is F1. Values below use Accuracy only.

Sorted by Accuracy. Highlighted rows are from other papers.

#	Model	Accuracy ↑	Paper
1	Cluster-GCN code ↗ GNN global	0.9936	Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks code ↗
2	GaAN code ↗ GNN global	0.9871	Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks code ↗
3	GeniePath code ↗ GNN global	0.9850	Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks code ↗
5	GAT GNN baseline actual #5 vs paper #14 9 places worse	0.9730 best reported	actual #5 vs paper #14 9 places worse paper 0.7960 ±0.0020 best at pub: Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks (KDD 2019) best today: Graph Self-Supervised Learning: A Survey (2021) paper 0.7960 ±0.0020 Δ at pub 0.1770 Δ today 0.1770
6	SP-GraphSAGE Hyb baseline	0.9600 ±0.0010	This paper
7	GraphSAGE GNN baseline actual #7 vs paper #7	0.9580 ±0.0010	actual #7 vs paper #7 paper 0.9580 ±0.0010 prev best: Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks (KDD 2019) paper 0.9580 ±0.0010 Δ at pub 0.3460
8	SP-GIN Hyb baseline	0.9140 ±0.0020	This paper
9	GIN GNN baseline	0.9110 ±0.0020	This paper
10	SP-GCN Hyb baseline	0.8920 ±0.0010	This paper
11	GCN GNN baseline	0.8880 ±0.0010	This paper
14	SP-GAT Hyb baseline	0.8070 ±0.0030	This paper

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
39	GIN GNN baseline actual #39 vs paper #330 291 places worse	0.9330 ±0.0290 best reported	actual #39 vs paper #330 291 places worse paper 0.8800 ±0.0700 best at pub: ProtGNN: Towards Self-Explaining Graph Neural Networks (AAAI 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.8800 ±0.0700 Δ at pub 0.0530
63	GCN GNN baseline actual #63 vs paper #519 456 places worse	0.9220 ±0.0440 best reported	actual #63 vs paper #519 456 places worse paper 0.8300 ±0.0600 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) paper 0.8300 ±0.0600 Δ at pub 0.0610 Δ today 0.0920
112	SP-GIN Hyb baseline	0.9100 ±0.0600	This paper
113	SP-GCN Hyb baseline	0.9100 ±0.0600	This paper
114	SP-GraphSAGE Hyb baseline	0.9100 ±0.0700	This paper
158	GraphSAGE GNN baseline actual #158 vs paper #519 361 places worse	0.9040 ±0.0780 best reported	actual #158 vs paper #519 361 places worse paper 0.8300 ±0.0800 best at pub: Graph Neural Networks With Convolutional ARMA Filters (2019) best today: Asynchronous Neural Networks for Learning in Graphs (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8300 ±0.0800 Δ at pub 0.0270 Δ today 0.0740
183	GAT GNN baseline actual #183 vs paper #614 431 places worse	0.9010 ±0.0580 best reported	actual #183 vs paper #614 431 places worse paper 0.8000 ±0.0900 best at pub: Breaking the Limits of Message Passing Graph Neural Networks (ICML 2021) best today: The Expressive Power of Graph Neural Networks: A Survey (2023) paper 0.8000 ±0.0900 Δ at pub 0.1010 Δ today 0.1010
188	SP-GAT Hyb baseline	0.9000 ±0.0500	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
718	SAGE code ↗ GNN global	0.7490 ±0.0870	Fast Graph Representation Learning with PyTorch Geometric code ↗

NCI1

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9954	1-WL Expressiveness Is (Almost) All You Need
2	GIN GNN baseline actual #2 vs paper #129 127 places worse	0.9934 best reported	actual #2 vs paper #129 127 places worse paper 0.8200 ±0.0100 best at pub: Provably Powerful Graph Networks (NeurIPS 2019) best today: 1-WL Expressiveness Is (Almost) All You Need (2022) paper 0.8200 ±0.0100 Δ at pub 0.0070 Δ today 0.1734
3	GCN GNN baseline actual #3 vs paper #129 126 places worse	0.9727 best reported	actual #3 vs paper #129 126 places worse paper 0.8200 ±0.0100 best at pub: Hierarchical Graph Capsule Network (AAAI 2020) best today: 1-WL Expressiveness Is (Almost) All You Need (2022) paper 0.8200 ±0.0100 Δ at pub 0.0165 Δ today 0.1527
4	GAT GNN baseline actual #4 vs paper #176 172 places worse	0.8100 ±0.0100	actual #4 vs paper #176 172 places worse paper 0.8100 ±0.0100 prev best: ifMixup: Interpolating Graph Pair to Regularize Graph Classification (AAAI 2021) best today: 1-WL Expressiveness Is (Almost) All You Need (2022) paper 0.8100 ±0.0100 Δ at pub 0.0260 Δ today 0.1523
130	SP-GIN Hyb baseline	0.8200 ±0.0100	This paper
131	GraphSAGE GNN baseline actual #131 vs paper #131	0.8200 ±0.0100	actual #131 vs paper #131 paper 0.8200 ±0.0100 prev best: Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels (NeurIPS 2019) paper 0.8200 ±0.0100 Δ at pub 0.0430
132	SP-GraphSAGE Hyb baseline	0.8200 ±0.0100	This paper
177	SP-GCN Hyb baseline	0.8100 ±0.0100	This paper
178	SP-GAT Hyb baseline	0.8100 ±0.0100	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 ↗
32	GIN GNN baseline actual #32 vs paper #245 213 places worse	0.7880 ±0.0410 best reported	actual #32 vs paper #245 213 places worse paper 0.7500 ±0.0300 best at pub: Breaking the Limits of Message Passing Graph Neural Networks (ICML 2021) best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7500 ±0.0300 Δ at pub 0.0110 Δ today 0.0380
49	GAT GNN baseline actual #49 vs paper #245 196 places worse	0.7800 ±0.0300 best reported	actual #49 vs paper #245 196 places worse paper 0.7500 ±0.0300 best at pub: Breaking the Limits of Message Passing Graph Neural Networks (ICML 2021) best today: 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.7500 ±0.0300 Δ at pub 0.0090 Δ today 0.0300
67	SAGE GNN global	0.7726 ±0.0228	Semi-Supervised Hierarchical Graph Classification
147	SP-GIN Hyb baseline	0.7600 ±0.0300	This paper
148	GCN GNN baseline actual #148 vs paper #245 97 places worse	0.7600 ±0.0320 best reported	actual #148 vs paper #245 97 places worse paper 0.7500 ±0.0300 best at pub: GraphiT: Encoding Graph Structure in Transformers (2021) best today: Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7500 ±0.0300 Δ at pub 0.0080 Δ today 0.0100
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
155	GraphSAGE GNN baseline actual #155 vs paper #363 208 places worse	0.7590 ±0.0320 best reported	actual #155 vs paper #363 208 places worse paper 0.7300 ±0.0400 best at pub: Graph Convolutional Networks with EigenPooling (KDD 2019) best today: Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7300 ±0.0400 Δ at pub 0.0160 Δ today 0.0290
246	SP-GCN Hyb baseline	0.7500 ±0.0300	This paper
247	SP-GAT Hyb baseline	0.7500 ±0.0400	This paper
364	SP-GraphSAGE Hyb baseline	0.7300 ±0.0400	This paper

COLLAB

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9792	1-WL Expressiveness Is (Almost) All You Need
2	MSH-GNN GNN global	0.9640 ±0.0070	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
3	CoCN code ↗ GNN global	0.8722 ±0.0013	Scalable Graph Compressed Convolutions code ↗
23	GCN GNN baseline actual #23 vs paper #227 204 places worse	0.8260 ±0.0220 best reported	actual #23 vs paper #227 204 places worse paper 0.7600 ±0.0100 best at pub: Fast Graph Representation Learning with PyTorch Geometric (ICLR 2019) best today: Scalable Expressiveness through Preprocessed Graph Perturbations (2024) paper 0.7600 ±0.0100 Δ at pub 0.0460 Δ today 0.0660
30	GIN GNN baseline actual #30 vs paper #300 270 places worse	0.8220 ±0.0210 best reported	actual #30 vs paper #300 270 places worse paper 0.7000 ±0.0100 best at pub: On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs (NeurIPS 2019) best today: Scalable Expressiveness through Preprocessed Graph Perturbations (2024) paper 0.7000 ±0.0100 Δ at pub 0.1020 Δ today 0.1220
136	GraphSAGE GNN baseline actual #136 vs paper #359 223 places worse	0.7970 ±0.0170 best reported	actual #136 vs paper #359 223 places worse paper 0.4000 ±0.0900 best at pub: Quaternion Graph Neural Networks (2020) best today: SignGT: Signed Attention-based Graph Transformer for Graph Representation Learning (2023) paper 0.4000 ±0.0900 Δ at pub 0.3970 Δ today 0.3970
137	SAGE code ↗ GNN global	0.7970 ±0.0170	Fast Graph Representation Learning with PyTorch Geometric code ↗
151	MLP Trad global	0.7920 ±0.0240	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
155	GAT GNN baseline actual #155 vs paper #358 203 places worse	0.7908 ±0.0136 best reported	actual #155 vs paper #358 203 places worse paper 0.4200 ±0.1000 best at pub: Improving Subgraph Recognition with Variational Graph Information Bottleneck (2021) best today: Graph Structure Refinement with Energy-based Contrastive Learning (AAAI 2024) paper 0.4200 ±0.1000 Δ at pub 0.3400 Δ today 0.3708
206	SP-GIN ext data Hyb baseline	0.7700 ±0.0100	This paper
207	SP-GCN ext data Hyb baseline	0.7700 ±0.0200	This paper
208	SP-GraphSAGE ext data Hyb baseline	0.7700 ±0.0200	This paper
263	SP-GAT ext data Hyb baseline	0.7400 ±0.0200	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 Improved at pub — later paper surpassed this result Best today — OK at publication; today's leaderboard best is elsewhere