Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search

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 Tr...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-11
Main Authors: Chiu, Alvin, Ghosh, Mithun, Reyan Ahmed, Kwang-Sung, Jun, Kobourov, Stephen, Goodrich, Michael T
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Graph neural networks
Isomorphism
Machine learning
Monte Carlo simulation
Searching
Traveling salesman problem
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422