Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

Xiang Wu, Ronghua Li, Xunkai Li, Kangfei Zhao, Hongchao Qin, Guoren Wang

Abstract

Graph coarsening reduces the size of a graph while preserving certain properties. Most existing methods preserve either spectral or spatial characteristics. Recent research shows that topology-preserving coarsening methods maintain GNN performance on coarsened graphs but suffer from exponential time complexity. To address these problems, we propose Scalable Topology-Preserving Graph Coarsening (STPGC) by introducing the concepts of graph strong collapse and graph edge collapse extended from algebraic topology. STPGC comprises three new algorithms, GStrongCollapse, GEdgeCollapse, and NeighborhoodConing based on these two concepts, which eliminate dominated nodes and edges while rigorously preserving topological features. We further prove that STPGC preserves the GNN receptive field and develop approximate algorithms to accelerate GNN training. Experiments on node classification with GNNs demonstrate the efficiency and effectiveness of STPGC.

Benchmark Results

Tested on 6 datasets 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 global	0.9004	Understanding Heterophily for Graph Neural Networks
255	STPGC GNN ★ proposed	0.8450 ±0.0030	This paper
461	Kron GNN baseline	0.8260 ±0.0080	This paper
469	Alg. JC GNN baseline	0.8250 ±0.0050	This paper
479	Aff. GS GNN baseline	0.8240 ±0.0060	This paper
521	Var. Edg. GNN baseline	0.8210 ±0.0060	This paper
565	Var. Nei. GNN baseline	0.8170 ±0.0030	This paper
566	GEC GNN baseline	0.8170 ±0.0050	This paper
641	FGC GNN baseline	0.8040 ±0.0160	This paper
708	UGC GNN baseline	0.7850 ±0.0120	This paper
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks
776	MPG GNN baseline	0.7500 ±0.0120	This paper

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 ↗
44	GCN GNN global	0.8033 ±0.0088	NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification
222	STPGC GNN ★ proposed	0.7420 ±0.0001	This paper
350	MLP code ↗ Trad global	0.7289 ±0.0010	Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax code ↗
401	UGC GNN baseline	0.7250 ±0.0001	This paper
443	Kron GNN baseline	0.7220 ±0.0001	This paper
455	GEC GNN baseline	0.7210 ±0.0001	This paper
500	Var. Nei. GNN baseline	0.7160 ±0.0080	This paper
518	Alg. JC GNN baseline	0.7140 ±0.0001	This paper
519	FGC GNN baseline	0.7140 ±0.0002	This paper
533	Aff. GS GNN baseline	0.7130 ±0.0000	This paper
620	Var. Edg. GNN baseline	0.7010 ±0.0001	This paper
654	MPG GNN baseline	0.6900 ±0.0003	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 global	0.9230 ±0.0070	Design your own universe: a physics-informed agnostic method for enhancing graph neural networks
53	GraphSAGE code ↗ GNN global	0.9000 ±0.0365	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
513	Kron GNN baseline	0.5950	This paper
532	Var. Edg. GNN baseline	0.5860	This paper
539	GEC GNN baseline	0.5810	This paper
546	STPGC GNN ★ proposed	0.5780	This paper
547	Var. Nei. GNN baseline	0.5760	This paper
551	Alg. JC GNN baseline	0.5700	This paper
556	Original GNN baseline	0.5650	This paper
569	Aff. GS GNN baseline	0.5510	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 global	0.9136 ±0.0070	Node-oriented Spectral Filtering for Graph Neural Networks
138	SAGE GNN global	0.8269	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
522	GEC GNN baseline	0.4620	This paper
526	STPGC GNN ★ proposed	0.4520	This paper
527	Aff. GS GNN baseline	0.4510	This paper
533	Var. Nei. GNN baseline	0.4430	This paper
535	Original GNN baseline	0.4410	This paper
539	Alg. JC GNN baseline	0.4320	This paper
544	Kron GNN baseline	0.4270	This paper
548	Var. Edg. GNN baseline	0.4190	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
37	MLP code ↗ Trad global	0.8629 ±0.0450	Is Homophily a Necessity for Graph Neural Networks? code ↗
63	GCN code ↗ GNN global	0.8310 ±0.0320	Restructuring Graphs for Higher Homophily via Adaptive Spectral Clustering code ↗
189	STPGC GNN ★ proposed	0.5460	This paper
191	GEC GNN baseline	0.5410	This paper
194	Var. Nei. GNN baseline	0.5350	This paper
196	Alg. JC GNN baseline	0.5330	This paper
198	Original GNN baseline	0.5250	This paper
199	Var. Edg. GNN baseline	0.5250	This paper
200	Aff. GS GNN baseline	0.5240	This paper
205	Kron GNN baseline	0.5200	This paper

Heterogeneous Graph Benchmarks

DBLP

Global leaderboard →

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

Sorted by Accuracy. Highlighted rows are from other papers.

#	Model	Accuracy ↑	Paper
1	HG-SCM Hyb global	0.9490 ±0.0015	Towards Human-like Perception: Learning Structural Causal Model in Heterogeneous Graph
2	SeHGNN GNN global	0.9489 ±0.0018	Towards Human-like Perception: Learning Structural Causal Model in Heterogeneous Graph
3	AdvSynGNN Hyb global	0.9486 ±0.0012	AdvSynGNN: Structure-Adaptive Graph Neural Nets via Adversarial Synthesis and Self-Corrective …
36	GCN code ↗ GNN global	0.8758 ±0.0020	I'm Me, We're Us, and I'm Us: Tri-directional Contrastive Learning on Hypergraphs code ↗
44	UGC GNN baseline	0.8560 ±0.0020	This paper
46	STPGC GNN ★ proposed	0.8520 ±0.0010	This paper
47	MPG GNN baseline	0.8480 ±0.0080	This paper
53	GEC GNN baseline	0.8430 ±0.0030	This paper
56	Var. Nei. GNN baseline	0.8250 ±0.0060	This paper
58	Var. Edg. GNN baseline	0.8220 ±0.0080	This paper
59	Aff. GS GNN baseline	0.8210 ±0.0050	This paper
64	FGC GNN baseline	0.8140 ±0.0050	This paper
65	MLP code ↗ Trad global	0.8118 ±0.0020	I'm Me, We're Us, and I'm Us: Tri-directional Contrastive Learning on Hypergraphs code ↗
67	Alg. JC GNN baseline	0.8060 ±0.0070	This paper
68	Kron GNN baseline	0.8060 ±0.0060	This paper

SOTA performance (not significantly different from the best) Proposed method (this paper) Baseline / comparison (this paper) Global context (other papers)