Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search

2023/04/30 by Reyan Ahmed, Ahmed, Reyan, Mithun Ghosh +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Natural Language Processing Techniques #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2305.00535

openalex publication_date 2023/04/30 · openalex created_date 2023/05/03 · openalex updated_date 2026/07/28

Abstract

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 Steiner Trees 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 Steiner tree. The proposed method consistently outperforms the standard 2-approximation algorithm on many different types of graphs and often finds the optimal solution.

Related

• Computing Steiner Trees using Graph Neural Networks
• Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search
• Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
• Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem
• Solving the Steiner Tree Problem in graphs with Variable Neighborhood Descent