1-WL Expressiveness Is (Almost) All You Need

Markus Zopf

Abstract

It has been shown that a message passing neural networks (MPNNs), a popular family of neural networks for graph-structured data, are at most as expressive as the first-order Weisfeiler-Leman (1-WL) graph isomorphism test, which has motivated the development of more expressive architectures. In this work, we analyze if the limited expressiveness is actually a limiting factor for MPNNs and other WL-based models in standard graph datasets. Interestingly, we find that the expressiveness of WL is sufficient to identify almost all graphs in most datasets. Moreover, we find that the classification accuracy upper bounds are often close to 100\

Benchmark Results

Tested on 2 datasets 3 baseline values reported too low

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

TU Dortmund

NCI1

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT ★ proposed	0.9954	This paper
2	GIN GNN baseline actual #2 vs paper #2	0.9934	actual #2 vs paper #2 paper 0.9934 prev best: Provably Powerful Graph Networks (NeurIPS 2019) paper 0.9934 Δ at pub 0.1664
3	GCN GNN baseline actual #3 vs paper #3	0.9727	actual #3 vs paper #3 paper 0.9727 prev best: Hierarchical Graph Capsule Network (AAAI 2020) paper 0.9727 Δ at pub 0.1362
4	GAT GNN baseline actual #4 vs paper #4	0.9623	actual #4 vs paper #4 paper 0.9623 prev best: Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings (TMLR 2022) paper 0.9623 Δ at pub 0.1523
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗

COLLAB

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT ★ proposed	0.9792	This paper
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 #286 263 places worse	0.8260 ±0.0220 best reported	actual #23 vs paper #286 263 places worse paper 0.7170 best at pub: Fast Graph Representation Learning with PyTorch Geometric (ICLR 2019) best today: Scalable Expressiveness through Preprocessed Graph Perturbations (2024) paper 0.7170 Δ at pub 0.0890 Δ today 0.1090
30	GIN GNN baseline actual #30 vs paper #225 195 places worse	0.8220 ±0.0210 best reported	actual #30 vs paper #225 195 places worse paper 0.7618 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.7618 Δ at pub 0.0402 Δ today 0.0602
136	GraphSAGE GNN global	0.7970 ±0.0170	SignGT: Signed Attention-based Graph Transformer for Graph Representation Learning
151	MLP Trad global	0.7920 ±0.0240	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
155	GAT GNN baseline actual #155 vs paper #344 189 places worse	0.7908 ±0.0136 best reported	actual #155 vs paper #344 189 places worse paper 0.5200 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.5200 Δ at pub 0.2400 Δ today 0.2708

SOTA performance (not significantly different from the best) Proposed method (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