# Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 28 references that are in the map.
- First posted on arXiv 17 Nov 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Multi-Level Steiner Trees](https://mlsanity.com/paper/1804.02627/) (2018)
- [Approximation algorithms and an integer program for multi-level graph spanners](https://mlsanity.com/paper/1904.01135/) (2019)
- [Improved Weighted Additive Spanners](https://mlsanity.com/paper/2008.09877/) (2020)
- [Multi-Priority Graph Sparsification](https://mlsanity.com/paper/2301.12563/) (2023)

## Abstract (arXiv)

Graph neural networks have been successful for machine learning, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing graph sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a sparsifier. The proposed method consistently outperforms several standard approximation algorithms on different types of graphs and often finds the optimal solution.