Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search
This addresses the problem of efficiently approximating graph sparsifiers for combinatorial optimization, though it appears incremental as it builds on existing techniques like GNNs and MCTS.
The authors tackled the problem of computing graph sparsifiers by combining a graph neural network with Monte Carlo Tree Search, where the neural network proposes nodes to add to a partial solution. The method consistently outperformed standard approximation algorithms on various graph types and often found optimal solutions.
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.