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 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.
Code (1)
Tasks
Graph Neural NetworkTraveling Salesman ProblemMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search
Graph neural networks are useful for learning problems, 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 S…
Graph Neural NetworkTraveling Salesman ProblemA Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem
We present a graph neural network assisted Monte Carlo Tree Search approach for the classical traveling salesman problem (TSP). We adopt a greedy algorithm framework to construct the optimal solution to TSP by adding the…
Graph Neural NetworkTraveling Salesman ProblemSurrogate Assisted Monte Carlo Tree Search in Combinatorial Optimization
Industries frequently adjust their facilities network by opening new branches in promising areas and closing branches in areas where they expect low profits. In this paper, we examine a particular class of facility locat…
Combinatorial OptimizationMonte-Carlo Graph Search for AlphaZero
The AlphaZero algorithm has been successfully applied in a range of discrete domains, most notably board games. It utilizes a neural network, that learns a value and policy function to guide the exploration in a Monte-Ca…
Board GamesMonte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms
Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms f…