Embedding Graphs on Grassmann Manifold

Bingxin Zhou, Xuebin Zheng, Yu Guang Wang, Ming Li, Junbin Gao

Abstract

Learning efficient graph representation is the key to addressing downstream tasks on graphs, such as node or graph property prediction. Given the non-Euclidean structural property of graphs, preserving the original graph data's similarity relationship in the embedded space needs specific tools and a similarity metric. This paper develops. The proposed to a Grassmann point of a low dimensional manifold through singular value decomposition (SVD).

Benchmark Results

Tested on 7 datasets 1 baseline value reported too low

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

Classic

Coauthor-CS

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DoG code ↗ GNN global	0.9690 ±0.0030	Diffusion on Graph: Augmentation of Graph Structure for Node Classification code ↗
2	GWN-fa code ↗ Hyb global	0.9667 ±0.0026	Graph Wave Networks code ↗
3	GWN-sym code ↗ GNN global	0.9666 ±0.0026	Graph Wave Networks code ↗
6	GraphSAGE code ↗ GNN global	0.9593 ±0.0025	Graph Wave Networks code ↗
88	MLP Trad global	0.9280 ±0.0020	Revisiting the Necessity of Graph Learning and Common Graph Benchmarks
202	k-means+EGG 0.8 (99.48%) baseline	0.6700 ±0.0201	This paper
203	K-means Trad baseline	0.6410 ±0.0171	This paper
204	k-means+EGG 0.5 (90.73%) baseline	0.5878 ±0.0188	This paper
205	k-means+EGG 0.2 (45.28%) baseline	0.5483 ±0.0250	This paper

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 global	0.9330 ±0.0290	ProtGNN: Towards Self-Explaining Graph Neural Networks
80	Attention GT baseline actual #80 vs paper #611 531 places worse	0.9170 ±0.0120 best reported	actual #80 vs paper #611 531 places worse paper 0.8025 ±0.0222 best today: Mind the Label Shift of Augmentation-based Graph OOD Generalization (2023) paper 0.8025 ±0.0222 Δ today 0.1145
101	TopKPool GNN baseline actual #101 vs paper #623 522 places worse	0.9130 ±0.0070 best reported	actual #101 vs paper #623 522 places worse paper 0.7984 ±0.0246 best today: Mind the Label Shift of Augmentation-based Graph OOD Generalization (2023) paper 0.7984 ±0.0246 Δ today 0.1146
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
545	EGG Hyb ★ proposed	0.8253 ±0.0072	This paper
589	EdgePool GNN baseline actual #589 vs paper #589	0.8101 ±0.0082	actual #589 vs paper #589 paper 0.8101 ±0.0082 prev best: Graph Information Bottleneck for Subgraph Recognition (ICLR 2020) Improvement within reported uncertainty; not highlighted. paper 0.8101 ±0.0082 Δ at pub 0.0511
623	SAGPool GNN baseline actual #623 vs paper #623	0.7986 ±0.0236	actual #623 vs paper #623 paper 0.7986 ±0.0236 prev best: Graph Neural Networks in TensorFlow and Keras with Spektral (2020) Improvement within reported uncertainty; not highlighted. paper 0.7986 ±0.0236 Δ at pub 0.0136
660	PanPool GNN baseline	0.7809 ±0.0127	This paper

NCI1

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9954	1-WL Expressiveness Is (Almost) All You Need
2	GIN GNN global	0.9934	1-WL Expressiveness Is (Almost) All You Need
3	GCN GNN global	0.9727	1-WL Expressiveness Is (Almost) All You Need
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
162	EGG Hyb ★ proposed	0.8131 ±0.0155	This paper
259	SAGPool GNN baseline actual #259 vs paper #366 107 places worse	0.7910 ±0.0300 best reported	actual #259 vs paper #366 107 places worse paper 0.7697 ±0.0294 best at pub: Contrastive Self-supervised Learning for Graph Classification (AAAI 2020) best today: The expressive power of pooling in Graph Neural Networks (NeurIPS 2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7697 ±0.0294 Δ at pub 0.0091 Δ today 0.0213
267	EdgePool GNN baseline actual #267 vs paper #329 62 places worse	0.7779 ±0.0280	actual #267 vs paper #329 62 places worse paper 0.7779 ±0.0280 prev best: Contrastive Self-supervised Learning for Graph Classification (AAAI 2020) Improvement within reported uncertainty; not highlighted. paper 0.7779 ±0.0280 Δ at pub 0.0123
308	Attention GT baseline	0.7822 ±0.0132	This paper
355	TopKPool GNN baseline	0.7706 ±0.0090	This paper
465	PanPool GNN baseline	0.7168 ±0.0445	This paper

PROTEINS

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9410 ±0.0330	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	GRDL GNN global	0.8260 ±0.0120	Graph Classification via Reference Distribution Learning: Theory and Practice
3	GMN code ↗ Hyb global	0.8225	Memory-Based Graph Networks code ↗
21	EGG Hyb ★ proposed	0.7980 ±0.0109	This paper
32	GIN GNN global	0.7880 ±0.0410	Permutation-Invariant graph partitioning: How graph neural networks capture structural …
58	TopKPool GNN baseline actual #58 vs paper #333 275 places worse	0.7768 best reported	actual #58 vs paper #333 275 places worse paper 0.7366 ±0.0600 best at pub: Memory-Based Graph Networks (ICLR 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.7366 ±0.0600 Δ at pub 0.0402
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
154	SAGPool GNN baseline actual #154 vs paper #154	0.7595 ±0.0452	actual #154 vs paper #154 paper 0.7595 ±0.0452 prev best: How Framelets Enhance Graph Neural Networks (ICML 2021) Improvement within reported uncertainty; not highlighted. paper 0.7595 ±0.0452 Δ at pub 0.0006
181	Attention GT baseline actual #181 vs paper #181	0.7563 ±0.0113	actual #181 vs paper #181 paper 0.7563 ±0.0113 prev best: How Framelets Enhance Graph Neural Networks (ICML 2021) Improvement within reported uncertainty; not highlighted. paper 0.7563 ±0.0113 Δ at pub 0.0170
184	EdgePool GNN baseline actual #184 vs paper #184	0.7560 ±0.0240	actual #184 vs paper #184 paper 0.7560 ±0.0240 prev best: Graph Information Bottleneck for Subgraph Recognition (ICLR 2020) Improvement within reported uncertainty; not highlighted. paper 0.7560 ±0.0240 Δ at pub 0.0330
390	PanPool GNN baseline	0.7241 ±0.0358	This paper

COLLAB

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9792	1-WL Expressiveness Is (Almost) All You Need
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 ↗
16	Attention GT baseline	0.8322 ±0.0030	This paper
18	EGG Hyb ★ proposed	0.8294 ±0.0106	This paper
23	GCN code ↗ GNN global	0.8260 ±0.0220	Scalable Expressiveness through Preprocessed Graph Perturbations code ↗
39	SAGPool GNN baseline actual #39 vs paper #39	0.8176 ±0.0157	actual #39 vs paper #39 paper 0.8176 ±0.0157 prev best: OOD-GNN: Out-of-Distribution Generalized Graph Neural Network (2021) paper 0.8176 ±0.0157 Δ at pub 0.1476
57	TopKPool GNN baseline actual #57 vs paper #57	0.8140 ±0.0094	actual #57 vs paper #57 paper 0.8140 ±0.0094 prev best: Memory-Based Graph Networks (ICLR 2020) paper 0.8140 ±0.0094 Δ at pub 0.0384
111	PanPool GNN baseline	0.8022 ±0.0202	This paper
150	EdgePool GNN baseline actual #150 vs paper #150	0.7920 ±0.0166	actual #150 vs paper #150 paper 0.7920 ±0.0166 prev best: Edge Contraction Pooling for Graph Neural Networks (2019) paper 0.7920 ±0.0166 Δ at pub 0.1210
151	MLP Trad global	0.7920 ±0.0240	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors

D&D

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GC-GNN (GCN) GNN global	0.9210 ±0.0810	Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability
2	SUGAR code ↗ Hyb global	0.8403 ±0.0133	SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information … code ↗
3	Ortho-g-U-Nets global	0.8387	Orthogonal Graph Neural Networks
13	EGG Hyb ★ proposed	0.8118 ±0.0114	This paper
15	SAGE GNN global	0.8088 ±0.0233	Semi-Supervised Hierarchical Graph Classification
41	EdgePool GNN baseline actual #41 vs paper #157 116 places worse	0.7920 ±0.0261 best reported	actual #41 vs paper #157 116 places worse paper 0.7282 ±0.0140 best at pub: Contrastive Self-supervised Learning for Graph Classification (AAAI 2020) paper 0.7282 ±0.0140 Δ at pub 0.0638
56	SAGPool GNN baseline actual #56 vs paper #137 81 places worse	0.7870 ±0.0229 best reported	actual #56 vs paper #137 81 places worse paper 0.7496 ±0.0360 best at pub: Contrastive Self-supervised Learning for Graph Classification (AAAI 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.7496 ±0.0360 Δ at pub 0.0374
92	Attention GT baseline	0.7748 ±0.0265	This paper
110	TopKPool GNN baseline actual #110 vs paper #110	0.7640 ±0.0232	actual #110 vs paper #110 paper 0.7640 ±0.0232 prev best: How Framelets Enhance Graph Neural Networks (ICML 2021) Improvement within reported uncertainty; not highlighted. paper 0.7640 ±0.0232 Δ at pub 0.0153
158	PanPool GNN baseline	0.7275 ±0.0232	This paper

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
94	TopKPool GNN baseline	0.7814 ±0.0062	This paper
108	EGG Hyb ★ proposed	0.7782 ±0.0090	This paper
109	GIN GNN 510.0M global	0.7780 ±0.0182	GRPE: Relative Positional Encoding for Graph Transformer
124	Attention GT baseline actual #124 vs paper #124	0.7744 ±0.0127	actual #124 vs paper #124 paper 0.7744 ±0.0127 prev best: Discovering Invariant Rationales for Graph Neural Networks (ICLR 2022) Improvement within reported uncertainty; not highlighted. paper 0.7744 ±0.0127 Δ at pub 0.0160
139	PanPool GNN baseline	0.7718 ±0.0113	This paper
229	SAGPool GNN baseline	0.7536 ±0.0182	This paper
230	EdgePool GNN baseline	0.7530 ±0.0201	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