# Graph Sparsification via Mixture of Graphs

arXiv: https://arxiv.org/abs/2405.14260 · HTML: https://mlsanity.com/paper/2405.14260/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in MoE for time series and graphs, one of 12 directions in Mixture-of-experts.
- Builds on 59 of its 97 references that are in the map.
- First posted on arXiv 23 May 2024.

## Placed in

- Mixture-of-experts / [MoE for time series and graphs](https://mlsanity.com/moe/moe-for-time-series-and-graphs/)

## Builds on (most cited first, 30 of 59)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Scaling Vision with Sparse Mixture of Experts](https://mlsanity.com/paper/2106.05974/) (2021)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Self-supervised Graph Learning for Recommendation](https://mlsanity.com/paper/2010.10783/) (2020)
- [Unified Scaling Laws for Routed Language Models](https://mlsanity.com/paper/2202.01169/) (2022)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Hash Layers For Large Sparse Models](https://mlsanity.com/paper/2106.04426/) (2021)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Multimodal Contrastive Learning with LIMoE: the Language-Image Mixture of Experts](https://mlsanity.com/paper/2206.02770/) (2022)
- [Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2112.08679/) (2021)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Training Graph Neural Networks with 1000 Layers](https://mlsanity.com/paper/2106.07476/) (2021)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [All in One: Multi-task Prompting for Graph Neural Networks](https://mlsanity.com/paper/2307.01504/) (2023)

## Built on by (most cited first, 17 of 17)

- [G-Safeguard: A Topology-Guided Security Lens and Treatment on LLM-based Multi-agent Systems](https://mlsanity.com/paper/2502.11127/) (2025)
- [Graph-Augmented Large Language Model Agents: Current Progress and Future Prospects](https://mlsanity.com/paper/2507.21407/) (2025)
- [Rethinking Fair Graph Neural Networks from Re-balancing](https://mlsanity.com/paper/2407.11624/) (2024)
- [Epidemiology-Aware Neural ODE with Continuous Disease Transmission Graph](https://mlsanity.com/paper/2410.00049/) (2024)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [Mixture of Length and Pruning Experts for Knowledge Graphs Reasoning](https://mlsanity.com/paper/2507.20498/) (2025)
- [IceBerg: Debiased Self-Training for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2502.06280/) (2025)
- [MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts](https://mlsanity.com/paper/2509.09337/) (2025)
- [Modeling Expert Interactions in Sparse Mixture of Experts via Graph Structures](https://mlsanity.com/paper/2510.16411/) (2025)
- [Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs](https://mlsanity.com/paper/2412.08835/) (2024)
- [Fast Track to Winning Tickets: Repowering One-Shot Pruning for Graph Neural Networks](https://mlsanity.com/paper/2412.07605/) (2024)
- [Adaptive Substructure-Aware Expert Model for Molecular Property Prediction](https://mlsanity.com/paper/2504.05844/) (2025)
- [Boolean Satisfiability via Imitation Learning](https://mlsanity.com/paper/2509.25411/) (2025)
- [CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support](https://mlsanity.com/paper/2607.10969/) (2026)
- [Does Graph Compression Preserve Signal Propagation?](https://mlsanity.com/paper/2607.23338/) (2026)
- [Edge Sparsification via Temporal Forman-Ricci Curvature for Dynamic Graph Learning](https://mlsanity.com/paper/2608.07158/) (2026)
- [Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks](https://mlsanity.com/paper/2609.31466/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have demonstrated superior performance across various graph learning tasks but face significant computational challenges when applied to large-scale graphs. One effective approach to mitigate these challenges is graph sparsification, which involves removing non-essential edges to reduce computational overhead. However, previous graph sparsification methods often rely on a single global sparsity setting and uniform pruning criteria, failing to provide customized sparsification schemes for each node's complex local context. In this paper, we introduce Mixture-of-Graphs (MoG), leveraging the concept of Mixture-of-Experts (MoE), to dynamically select tailored pruning solutions for each node. Specifically, MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Subsequently, MoG performs a mixture of the sparse graphs produced by different experts on the Grassmann manifold to derive an optimal sparse graph. One notable property of MoG is its entirely local nature, as it depends on the specific circumstances of each individual node. Extensive experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNN backbones, demonstrate that MoG (I) identifies subgraphs at higher sparsity levels (8.67%~ 50.85%), with performance equal to or better than the dense graph, (II) achieves 1.47-2.62× speedup in GNN inference with negligible performance drop, and (III) boosts ``top-student'' GNN performance (1.02%uparrow on RevGNN+textscogbn-proteins and 1.74%uparrow on DeeperGCN+textscogbg-ppa).