Research map / Graph learning / GNN architectures
Graph Sparsification via Mixture of Graphs
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 Mixture-of-Graphs (MoG), a mixture-of-experts graph sparsifier that routes each node to tailored sparsifier experts (varying sparsity and pruning criteria) and merges their sparse ego-graphs on the Grassmann manifold.
Problem
Global, uniform graph sparsification rules ignore that nodes need different sparsity levels and pruning criteria, which limits both GNN acceleration at high sparsity and performance gains from removing noisy edges on large-scale graphs.
Approach
Use a noisy top-k gated mixture of sparsifier experts (four pruning criteria times three sparsity levels) chosen per node from its 1-hop ego graph, and ensemble the resulting sparse ego-graphs via a closed-form Grassmann-manifold subspace mixture of their Laplacians, followed by post-sparsification.
Key results
- MoG achieves 1.47-2.62x inference speedup with negligible performance drop, and identifies subgraphs at 8.67%-50.85% sparsity with performance equal to or better than the dense graph.
- As a performance booster, MoG improves RevGNN on ogbn-proteins by 1.02% ROC-AUC (88.14 to 89.04) and DeeperGCN on ogbg-ppa by 1.74% accuracy (77.09 to 78.43).
- On ogbn-proteins with DeeperGCN at 50% sparsity, the ROC-AUC drops only 0.81% relative to the dense graph.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add MoG sparsification at 30% edge sparsity | GraphSAGE · ogbn-arxiv | accuracy: 71.49_{\pm0.01} -> 70.53 | Hurt |
| Add MoG sparsification at 30% edge sparsity | GraphSAGE · ogbn-proteins | ROC-AUC: 77.40_{\pm0.1} -> 77.49 | Helped |
| Add MoG sparsification at 10% edge sparsity | PNA · MNIST | accuracy: 97.35_{\pm0.07} -> 97.80 | Helped |
| Add MoG sparsification at 10% edge sparsity | DeeperGCN · ogbg-ppa | accuracy: 77.09_{\pm0.04} -> 78.43 | Helped |
| Add MoG sparsification | RevGNN · ogbn-proteins | ROC-AUC: 88.14 -> 89.04 | Helped |
| Add MoG sparsification | DeeperGCN · ogbg-ppa | accuracy: 77.09 -> 78.43 | Helped |
| Increase the number of sparsifier settings from m=1 to m=2 (ablation) | MoG + GraphSAGE · ogbn-products, 30% sparsity | accuracy: 77.75 -> 78.23 | Helped |
| Increase the number of sparsifier settings from m=2 to m=3 (ablation) | MoG + GraphSAGE · ogbn-products, 30% sparsity | accuracy: 78.23 -> 78.15 | Hurt |
| Set the expert importance loss coefficient to 1e-2 instead of 0 (ablation) | MoG + DeeperGCN · ogbn-proteins, 50% sparsity | ROC-AUC: 79.40_{\pm 0.06} -> 81.79_{\pm 0.21} | Helped |
| Set the expert importance loss coefficient to 1e-1 instead of 1e-2 (ablation) | MoG + DeeperGCN · ogbn-proteins, 50% sparsity | ROC-AUC: 81.79_{\pm 0.21} -> 82.04_{\pm 0.20} | Helped |
| Select 4 experts per node instead of 1 (ablation) | MoG + GraphSAGE · ogbn-arxiv, 50% sparsity | accuracy | Helped |
| Select 6 experts per node instead of 4 (ablation) | MoG + GraphSAGE · ogbn-arxiv, 50% sparsity | accuracy | Hurt |
Surprising findings
- Removing up to 50% of edges on MNIST with GraphSAGE/PNA slightly increases accuracy, suggesting sparsification can act as denoising.
Limitations
- Relies on 1-hop ego-graph decomposition to represent local context; extension to k-hop contexts is unexplored.
- Some baselines (ER, MGSpar, WD-GLT) run out of time or memory on large graphs.
Experimental setup
Datasets: ogbn-arxiv ogbn-proteins ogbn-products ogbg-ppa MNIST CIFAR-10
Benchmarks: ogbn-arxiv ogbn-proteins ogbn-products ogbg-ppa MNIST CIFAR-10
Metrics: accuracy ROC-AUC inference speedup per-epoch time
Baselines: Random Rank Degree Local Degree Forest Fire G-Spar ER DSpar UGS AdaGLT ACE-GLT
Builds on: sparsely-gated mixture of experts UGS AdaGLT effective resistance sparsification
Closest papers by meaning
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · similarity 0.89)
- EAGLES: Towards Effective, Efficient, and Economical Federated Graph Learning via Unified Sparsification (ICML 2025 · similarity 0.88)
- Mixture of Weak and Strong Experts on Graphs (ICLR 2024 · similarity 0.87)
- GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning (NeurIPS 2024 · similarity 0.87)
- Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization (NeurIPS 2025 · similarity 0.87)
- Unifews: You Need Fewer Operations for Efficient Graph Neural Networks (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.