# Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning

arXiv: https://arxiv.org/abs/2111.10810 · HTML: https://mlsanity.com/paper/2111.10810/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 21 Nov 2021.

## Builds on (most cited first, 18 of 18)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Learning Heuristics over Large Graphs via Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03332/) (2019)
- [Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning](https://mlsanity.com/paper/1809.03359/) (2018)
- [Co-training for Policy Learning](https://mlsanity.com/paper/1907.04484/) (2019)
- [Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art](https://mlsanity.com/paper/2008.12646/) (2020)

## Built on by (most cited first, 5 of 5)

- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem](https://mlsanity.com/paper/2209.09983/) (2022)
- [Visual Diffusion Models are Geometric Solvers](https://mlsanity.com/paper/2510.21697/) (2025)
- [NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems](https://mlsanity.com/paper/2210.12453/) (2022)
- [A Reinforcement Learning Approach for Scheduling Problems With Improved Generalization Through Order Swapping](https://mlsanity.com/paper/2302.13941/) (2023)

## Abstract (arXiv)

Steiner Tree Problem (STP) in graphs aims to find a tree of minimum weight in the graph that connects a given set of vertices. It is a classic NP-hard combinatorial optimization problem and has many real-world applications (e.g., VLSI chip design, transportation network planning and wireless sensor networks). Many exact and approximate algorithms have been developed for STP, but they suffer from high computational complexity and weak worst-case solution guarantees, respectively. Heuristic algorithms are also developed. However, each of them requires application domain knowledge to design and is only suitable for specific scenarios. Motivated by the recently reported observation that instances of the same NP-hard combinatorial problem may maintain the same or similar combinatorial structure but mainly differ in their data, we investigate the feasibility and benefits of applying machine learning techniques to solving STP. To this end, we design a novel model Vulcan based on novel graph neural networks and deep reinforcement learning. The core of Vulcan is a novel, compact graph embedding that transforms highdimensional graph structure data (i.e., path-changed information) into a low-dimensional vector representation. Given an STP instance, Vulcan uses this embedding to encode its pathrelated information and sends the encoded graph to a deep reinforcement learning component based on a double deep Q network (DDQN) to find solutions. In addition to STP, Vulcan can also find solutions to a wide range of NP-hard problems (e.g., SAT, MVC and X3C) by reducing them to STP. We implement a prototype of Vulcan and demonstrate its efficacy and efficiency with extensive experiments using real-world and synthetic datasets.