# A Generic Graph Sparsification Framework using Deep Reinforcement Learning

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 64 references that are in the map.
- First posted on arXiv 2 Dec 2021.

## Builds on (most cited first, 10 of 10)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Structure-Preserving Sparsification Methods for Social Networks](https://mlsanity.com/paper/1601.00286/) (2016)
- [Learning Robust Representations with Graph Denoising Policy Network](https://mlsanity.com/paper/1910.01784/) (2019)
- [An SDP-Based Algorithm for Linear-Sized Spectral Sparsification](https://mlsanity.com/paper/1702.08415/) (2017)
- [Graph Sparsification with Generative Adversarial Network](https://mlsanity.com/paper/2009.11736/) (2020)

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

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Can ChatGPT Enable ITS? The Case of Mixed Traffic Control via Reinforcement Learning](https://mlsanity.com/paper/2306.08094/) (2023)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [Efficient Large-Scale Urban Parking Prediction: Graph Coarsening Based on Real-Time Parking Service Capability](https://mlsanity.com/paper/2410.04022/) (2024)
- [Analyzing Behaviors of Mixed Traffic via Reinforcement Learning at Unsignalized Intersections](https://mlsanity.com/paper/2312.05325/) (2023)
- [Balanced Edge Pruning for Graph Anomaly Detection with Noisy Labels](https://mlsanity.com/paper/2407.05934/) (2024)
- [Neighbor-Aware Reinforcement Learning for Mixed Traffic Optimization in Large-scale Networks](https://mlsanity.com/paper/2412.12622/) (2024)

## Abstract (arXiv)

The interconnectedness and interdependence of modern graphs are growing ever more complex, causing enormous resources for processing, storage, communication, and decision-making of these graphs. In this work, we focus on the task graph sparsification: an edge-reduced graph of a similar structure to the original graph is produced while various user-defined graph metrics are largely preserved. Existing graph sparsification methods are mostly sampling-based, which introduce high computation complexity in general and lack of flexibility for a different reduction objective. We present SparRL, the first generic and effective graph sparsification framework enabled by deep reinforcement learning. SparRL can easily adapt to different reduction goals and promise graph-size-independent complexity. Extensive experiments show that SparRL outperforms all prevailing sparsification methods in producing high-quality sparsified graphs concerning a variety of objectives.