Research map / Graph learning / GNN architectures

Graph Distillation with Eigenbasis Matching

ICML 2024 · Graph learning › GNN architectures · approach: Robustness, privacy, and fairness of GNNs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GDEM, a graph distillation method that matches the eigenbasis and node features of real and synthetic graphs (without GNN in the loop) and reuses the real spectrum to construct the synthetic adjacency, achieving cross-architecture generalization and fast distillation.

Problem

Existing graph distillation methods depend on a chosen GNN's gradients, representations, or trajectories, which induces spectrum bias in the synthetic graph and requires traversing GNN architectures to get good performance.

Approach

Decompose the real graph Laplacian and match only its top/bottom-K eigenvectors (projected onto node features) with synthetic eigenbasis, plus an orthogonality and a class-discrimination constraint; the synthetic adjacency is then built as sum of (1-lambda_k) u_k u_k^T from the real spectrum, so no GNN is needed during distillation.

Key results

• GDEM achieves the best result in 6 of 7 datasets in node classification (e.g., Reddit 92.9% at 0.05% ratio vs. GCOND 88.0%).
• Cross-architecture evaluation across six GNNs gives GDEM the highest average accuracy on most datasets, e.g., Pubmed 77.92 avg and Flickr 49.33 avg, with lower variance than GCOND.
• Overall distillation time on Pubmed is 1.79 s for GDEM versus 68.75 s for GCOND and 74.76 s for SGDD when traversing GNN architectures.

Measured effects reported in the paper

Surprising findings

• GDEM underperforms on Ogbn-arxiv, which the authors attribute to its structure being spread across many eigenvectors (about 5,000 needed to approximate the full graph).
• The discrimination constraint improves accuracy but hurts cross-architecture generalization, revealing a trade-off from injecting spectral information.

Limitations

• Requires eigendecomposition of the real graph, adding preprocessing cost (O(N^3) or O(KN^2)).
• Performance degrades at extremely high compression ratios where only a few eigenvectors can be matched.
• Underperforms on Ogbn-arxiv where structural information is widely distributed across the eigenbasis.

Experimental setup

Datasets: Citeseer Pubmed Ogbn-arxiv Flickr Reddit Squirrel Gamers

Benchmarks: Citeseer Pubmed Ogbn-arxiv Flickr Reddit Squirrel Gamers

Metrics: node classification accuracy standard deviation time overhead (s) total variation

Baselines: Random Herding K-Center Coarsening GCOND SGDD SFGC

Builds on: GCOND SGDD SFGC GCond gradient matching graph coarsening

Closest papers by meaning

• Mirage: Model-agnostic Graph Distillation for Graph Classification (ICLR 2024 · similarity 0.89)
• Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning (ICLR 2025 · similarity 0.88)
• Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.88)
• On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.88)
• VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPs (ICLR 2024 · similarity 0.88)
• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.87)