Graph Homomorphism Convolution

Hoang NT, Takanori Maehara

Abstract

In this paper, we study the graph classification problem from the graph homomorphism perspective. We consider the homomorphisms from $F$ to $G$, where $G$ is a graph of interest (e.g. molecules or social networks) and $F$ belongs to some family of graphs (e.g. paths or non-isomorphic trees). We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and $ $-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the $ $-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating $ $-invariant functions. In practice, by choosing $ $ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.

Benchmark Results

Tested on 4 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
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: Provably Powerful Graph Networks (NeurIPS 2019) best today: ProtGNN: Towards Self-Explaining Graph Neural Networks (AAAI 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.8940 ±0.0560 Δ today 0.0390
55	PATCHY-SAN GNN baseline actual #55 vs paper #59 4 places worse	0.9250 ±0.0420	actual #55 vs paper #59 4 places worse paper 0.9250 ±0.0420 prev best: DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification (KDD 2019) paper 0.9250 ±0.0420 Δ at pub 0.1300
63	GCN GNN global	0.9220 ±0.0440	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
164	WL kernel SVM baseline	0.9040 ±0.0570	This paper
191	GNTK SVM baseline	0.9000 ±0.0850	This paper
265	GHC-Tree Trad baseline	0.8928 ±0.0826	This paper
292	GHC-LabelTree Trad baseline	0.8886 ±0.0482	This paper
340	AWL kernel SVM baseline	0.8790 ±0.0980	This paper
343	GHC-Cycle Trad baseline	0.8781 ±0.0746	This paper
373	WL-W kernel SVM baseline	0.8727 ±0.0150	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
446	Graphlet Kernel SVM baseline	0.8520 ±0.0090	This paper
470	WL-OA kernel SVM baseline	0.8450 ±0.0017	This paper

IMDB-BINARY

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	ID-GNN+BEC Hyb global	0.8150 ±0.0240	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
2	GIN+BEC Hyb global	0.8080 ±0.0330	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
3	GCN+BEC Hyb global	0.7990 ±0.0340	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
4	GCN GNN global	0.7980 ±0.0230	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
14	GIN GNN baseline actual #14 vs paper #35 21 places worse	0.7810 ±0.0350 best reported	actual #14 vs paper #35 21 places worse paper 0.7510 ±0.0510 best today: Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature (KDD 2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7510 ±0.0510 Δ today 0.0300
17	GNTK SVM baseline	0.7690 ±0.0360	This paper
45	AWL kernel SVM baseline	0.7450 ±0.0590	This paper
47	WL-W kernel SVM baseline	0.7437 ±0.0083	This paper
79	WL kernel SVM baseline	0.7312 ±0.0040	This paper
105	GHC-Tree Trad baseline	0.7210 ±0.0262	This paper
128	PATCHY-SAN GNN baseline	0.7100 ±0.0220	This paper
131	GHC-Cycles Trad ★ proposed	0.7093 ±0.0454	This paper

IMDB-MULTI

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GraphSNN GNN global	0.7790 ±0.0360	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
2	SIN GNN global	0.7560 ±0.0320	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
3	CIN GNN global	0.7560 ±0.0370	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
5	GIN GNN baseline actual #5 vs paper #31 26 places worse	0.7510 ±0.0510 best reported	actual #5 vs paper #31 26 places worse paper 0.5230 ±0.0280 best today: Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm (TMLR 2022) paper 0.5230 ±0.0280 Δ today 0.2280
28	GNTK SVM baseline	0.5280 ±0.0460	This paper
38	GCN code ↗ GNN global	0.5190	AutoGEL: An Automated Graph Neural Network with Explicit Link Information code ↗
42	AWL kernel SVM baseline	0.5150 ±0.0360	This paper
84	GHC-Tree Trad baseline	0.4860 ±0.0440	This paper
92	GHC-Cycles Trad ★ proposed	0.4761 ±0.0367	This paper
107	PATCHY-SAN GNN baseline	0.4520 ±0.0280	This paper

GNNBenchmark

CSL

Global leaderboard →

#	Model	Accuracy ↑	Paper
6	GHC-Cycles Trad ★ proposed	1.0000	This paper
1	PPGN code ↗ GNN global	1.0000	Revisiting Random Walks for Learning on Graphs code ↗
2	RW-AgentNet code ↗ Walk global	1.0000	Revisiting Random Walks for Learning on Graphs code ↗
3	AgentNet code ↗ Trad global	1.0000	Revisiting Random Walks for Learning on Graphs code ↗
8	GCN code ↗ GNN global	1.0000	GNNBenchmark code ↗
40	GIN GNN baseline actual #40 vs paper #72 32 places worse	0.9933 ±0.0133 best reported	actual #40 vs paper #72 32 places worse paper 0.1000 best at pub: On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs (NeurIPS 2019) best today: GNNBenchmark (JMLR 2023) paper 0.1000 Δ today 0.8933
55	Ring-GNN GNN baseline actual #55 vs paper #72 17 places worse	0.8000 ±0.1570 best reported	actual #55 vs paper #72 17 places worse paper 0.1000 ±0.1570 best at pub: On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs (NeurIPS 2019) paper 0.1000 ±0.1570 Δ at pub 0.7000
73	GNTK SVM baseline	0.1000	This paper
74	GHC-Tree Trad baseline	0.1000	This paper

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) Best at pub — reported value improved over the best known when published Best today — OK at publication; today's leaderboard best is elsewhere