Agent-based Graph Neural Networks

Karolis Martinkus, P. Papp, Benedikt Schesch, Roger Wattenhofer

Abstract

We present a novel graph neural network we call AgentNet, which is designed specifically for graph-level tasks. AgentNet is inspired by sublinear algorithms, featuring a computational complexity that is independent of the graph size. The architecture of AgentNet differs fundamentally from the architectures of traditional graph neural networks. In AgentNet, some trained neural agents intelligently walk the graph, and then collectively decide on the output. We provide an extensive theoretical analysis of AgentNet: We show that the agents can learn to systematically explore their neighborhood and that AgentNet can distinguish some structures that are even indistinguishable by 2-WL. Moreover, AgentNet is able to separate any two graphs which are sufficiently different in terms of subgraphs. We confirm these theoretical results with synthetic experiments on hard-to-distinguish graphs and real-world graph classification tasks. In both cases, we compare favorably not only to standard GNNs but also to computationally more expensive GNN extensions.

Benchmark Results

Tested on 5 datasets 1 baseline value reported too low

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

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
35	AgentNet Trad ★ proposed	0.9360 ±0.0860	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 global	0.9220 ±0.0440	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
140	PPGN GNN baseline	0.9060 ±0.0870	This paper
162	CRaWl Trad baseline	0.9040 ±0.0710	This paper
248	1-AgentNet Hyb ★ proposed	0.8940 ±0.1090	This paper
294	1-2-3 GNN GNN baseline actual #294 vs paper #294	0.8880 ±0.0700	actual #294 vs paper #294 paper 0.8880 ±0.0700 prev best: Provably Powerful Graph Networks (NeurIPS 2019) Improvement within reported uncertainty; not highlighted. paper 0.8880 ±0.0700 Δ at pub 0.0270
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗

RDT-B

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	OEPG Hyb global	0.9630 ±0.0090	Omni-Granular Ego-Semantic Propagation for Self-Supervised Graph Representation Learning
2	MSH-GNN GNN global	0.9580 ±0.0090	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
3	GNN-AK+ code ↗ GNN global	0.9480 ±0.0080	From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness code ↗
4	AgentNet Trad ★ proposed	0.9420 ±0.0120	This paper
7	ESAN GNN baseline	0.9330 ±0.0130	This paper
9	CRaWl Trad baseline	0.9280 ±0.0220	This paper
13	GIN GNN baseline	0.9240 ±0.0250	This paper
41	DropGIN GNN baseline	0.8990 ±0.0170	This paper
74	1-AgentNet Hyb ★ proposed	0.7790 ±0.0300	This paper
84	GCN GNN global	0.7060 ±0.0369	Motif-driven Subgraph Structure Learning for Graph Classification

OGB

ogbg-molhiv

Global leaderboard →

#	Model	ROC-AUC ↑	Paper
1	Multi-RF Fusion with Multi-GNN Blending global	0.8476 ±0.0002	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
2	HyperFusion global	0.8475 ±0.0003	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
3	PAS+FPs global	0.8420 ±0.0015	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
9	GatedGCN GNN 2.8M global	0.8090 ±0.0160	Deep Prompt Tuning for Graph Transformers
89	AgentNet Trad ★ proposed	0.7833 ±0.0069	This paper
101	ESAN GNN baseline	0.7800 ±0.0142	This paper
109	GIN GNN baseline actual #109 vs paper #221 112 places worse	0.7780 ±0.0182 best reported	actual #109 vs paper #221 112 places worse paper 0.7558 ±0.0140 best at pub: GRPE: Relative Positional Encoding for Graph Transformer (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7558 ±0.0140 Δ at pub 0.0222
110	CRaWl Trad baseline	0.7778 ±0.0087	This paper
146	GIN+virtual node GNN baseline actual #146 vs paper #150 4 places worse	0.7710 ±0.0150 best reported	actual #146 vs paper #150 4 places worse paper 0.7707 ±0.0149 best at pub: Wasserstein Embedding for Graph Learning (ICLR 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.7707 ±0.0149 Δ at pub 0.0003
160	GraphSAGE code ↗ GNN global	0.7690 ±0.0136	SoGCN: Second-Order Graph Convolutional Networks code ↗

ogbg-molpcba

Global leaderboard →

#	Model	AP ↑	Paper
1	GRPE-Large GT global	0.3150 ±0.0010	GRPE: Relative Positional Encoding for Graph Transformer
2	Graphormer code ↗ GT global	0.3140	Unified 2D and 3D Pre-Training of Molecular Representations code ↗
3	Graphormer-FLAG GT 47.0M global	0.3139 ±0.0032	GRPE: Relative Positional Encoding for Graph Transformer
9	CRaWl Trad baseline	0.2986 ±0.0025	This paper
31	GIN GNN baseline actual #31 vs paper #90 59 places worse	0.2902 ±0.0017 best reported	actual #31 vs paper #90 59 places worse paper 0.2266 ±0.0028 best at pub: GRPE: Relative Positional Encoding for Graph Transformer (2022) paper 0.2266 ±0.0028 Δ at pub 0.0636
53	GIN+virtual node GNN baseline	0.2703 ±0.0023	This paper
56	GCN GNN global	0.2690 ±0.0020	Latent-Hysteresis Graph ODEs: Modeling Coupled Topology-Feature Evolution via Continuous Phase …
59	ESAN GNN baseline	0.2664 ±0.0027	This paper
72	AgentNet Trad ★ proposed	0.2549 ±0.0027	This paper

ogbg-ppa

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	A-NLSF code ↗ Hyb global	0.8149 ±0.0067	Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networks code ↗
2	differential encoding global	0.8096 ±0.0029	Differential Encoding for Improved Representation Learning Over Graphs
3	MPNN + VN + NoPE code ↗ GNN global	0.8055 ±0.0038	On the Connection Between MPNN and Graph Transformer code ↗
16	GatedGCN code ↗ GNN global	0.7531 ±0.0083	Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networks code ↗
24	AgentNet Trad ★ proposed	0.7233 ±0.0062	This paper
33	GIN GNN baseline actual #33 vs paper #37 4 places worse	0.7037 ±0.0107 best reported	actual #33 vs paper #37 4 places worse paper 0.6892 ±0.0100 best at pub: Parameterized Hypercomplex Graph Neural Networks for Graph Classification (2021) best today: Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networks (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.6892 ±0.0100 Δ today 0.0145
35	GIN+virtual node GNN baseline	0.7037 ±0.0107	This paper
37	CRaWl Trad baseline	0.7025 ±0.0052	This paper
38	GCN code ↗ GNN global	0.6857 ±0.0061	Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networks code ↗

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