Graph Sparsifications using Neural Network Assisted Monte Carlo Tree
  Search
Alvin Chiu Mithun Ghosh Reyan Ahmed Kwang-Sung Jun Stephen Kobourov Michael T. Goodrich
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.