TinyGraph: Joint Feature and Node Condensation for Graph Neural Networks

Yezi Liu, Yanning Shen

Abstract

Training graph neural networks (GNNs) on large-scale graphs can be challenging due to the high computational expense caused by the massive number of nodes and high-dimensional nodal features. Existing graph condensation studies tackle this problem only by reducing the number of nodes in the graph. However, the resulting condensed graph data can still be cumbersome. Specifically, although the nodes of the dataset are reduced to $0.9\

Benchmark Results

Tested on 3 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
585	Original Graph GNN baseline	0.8130 ±0.0040	This paper
615	GCond GNN baseline actual #615 vs paper #615	0.8090 ±0.0320	actual #615 vs paper #615 paper 0.8090 ±0.0320 prev best: Two Trades are not Baffled: Condensing Graph via Crafting Rational Gradient Matching (2024) Improvement within reported uncertainty; not highlighted. paper 0.8090 ±0.0320 Δ at pub 0.0080
655	TinyGraph ★ proposed	0.8010 ±0.0110	This paper
719	GCond-LDA Trad baseline	0.7780 ±0.0410	This paper
720	GCond-VGAE GNN baseline	0.7780 ±0.0410	This paper
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks
728	GCond-PCA Trad baseline	0.7760 ±0.0320	This paper
768	GCond-ICA Trad baseline	0.7540 ±0.0350	This paper
771	GraphPCA Trad baseline	0.7530 ±0.0200	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
350	MLP code ↗ Trad global	0.7289 ±0.0010	Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax code ↗
572	GCond GNN baseline actual #572 vs paper #572	0.7080 ±0.0450	actual #572 vs paper #572 paper 0.7080 ±0.0450 prev best: Condensing Graphs via One-Step Gradient Matching (KDD 2022) Improvement within reported uncertainty; not highlighted. paper 0.7080 ±0.0450 Δ at pub 0.0020
690	GCond-VGAE GNN baseline	0.6790 ±0.0280	This paper
715	GCond-LDA Trad baseline	0.6720 ±0.0120	This paper
728	GCond-PCA Trad baseline	0.6680 ±0.0220	This paper
741	GCond-ICA Trad baseline	0.6630 ±0.0330	This paper
802	GraphPCA Trad baseline	0.6340 ±0.0080	This paper

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	GAP-EDP code ↗ GNN global	0.9870 ±0.0003	GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation code ↗
2	NE-ASGCN ext data Hyb global	0.9758 ±0.0027	Neighbor Enhanced Graph Convolutional Networks for Node Classification and Recommendation
3	HSGT GT global	0.9730 ±0.0024	Hierarchical Transformer for Scalable Graph Learning
21	GraphSAGE GNN global	0.9653 ±0.0011	Hierarchical Transformer for Scalable Graph Learning
82	Original Graph GNN baseline	0.9390	This paper
120	GCond GNN baseline actual #120 vs paper #120	0.9030 ±0.0310	actual #120 vs paper #120 paper 0.9030 ±0.0310 prev best: Graph Condensation for Inductive Node Representation Learning (2023) Improvement within reported uncertainty; not highlighted. paper 0.9030 ±0.0310 Δ at pub 0.0067
129	TinyGraph ★ proposed	0.8950 ±0.0130	This paper
131	GCond-ICA Trad baseline	0.8920 ±0.0370	This paper
135	GCond-VGAE GNN baseline	0.8820 ±0.0140	This paper
136	GCond-LDA Trad baseline	0.8740 ±0.0170	This paper
137	GCond-PCA Trad baseline	0.8730 ±0.0140	This paper
146	GraphPCA Trad baseline	0.8420 ±0.0190	This paper
147	MLP code ↗ Trad global	0.8240 ±0.0010	GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation code ↗

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

Abstract

Benchmark Results

Classic

Cora

CiteSeer

Reddit