# Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 48 references that are in the map.
- First posted on arXiv 20 Sep 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (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)
- [Pre-trained Models for Natural Language Processing: A Survey](https://mlsanity.com/paper/2003.08271/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method](https://mlsanity.com/paper/1708.05930/) (2017)
- [A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems](https://mlsanity.com/paper/2002.03282/) (2020)
- [Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning](https://mlsanity.com/paper/2111.10810/) (2021)
- [Computing Steiner Trees using Graph Neural Networks](https://mlsanity.com/paper/2108.08368/) (2021)

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

- [Visual Diffusion Models are Geometric Solvers](https://mlsanity.com/paper/2510.21697/) (2025)
- [EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization](https://mlsanity.com/paper/2610.04953/) (2026)

## Abstract (arXiv)

The Euclidean Steiner tree problem seeks the min-cost network to connect a collection of target locations, and it underlies many applications of wireless networks. In this paper, we present a study on solving the Euclidean Steiner tree problem using reinforcement learning enhanced by graph representation learning. Different from the commonly studied connectivity problems like travelling salesman problem or vehicle routing problem where the search space is finite, the Euclidean Steiner tree problem requires to search over the entire Euclidean space, thereby making the existing methods not applicable. In this paper, we design discretization methods by leveraging the unique characteristics of the Steiner tree, and propose new training schemes for handling the dynamic Steiner points emerging during the incremental construction. Our design is examined through a sanity check using experiments on a collection of datasets, with encouraging results demonstrating the utility of our method as an alternative to classic combinatorial methods.