Using graph neural networks for solving the Steiner tree problem

The theory of discrete optimization plays a crucial role in solving graph theory problems, such as the Steiner tree problem. It is widely applied in transportation infrastructure, logistics, and communication network design. Since the problem is NP-hard, heuristic methods such as genetic algorithms and artificial neural networks are often required. To solve the Steiner tree problem, a graph neural network (GNN) was selected. The GNN architecture involves iterative feature updates using information from neighboring nodes, allowing it to model complex dependencies in graphs. A message-passing neural network (MPNN) mechanism is employed for information aggregation, updating node states based on data from adjacent nodes and edges. The model is trained on graphs generated using the Melhorn heuristic algorithm. Experiments show that GNN performs well on graphs similar to the training data but experiences a significant drop in precision and recall metrics as the input graph size increases. This decline is likely due to the limitations of the MPNN mechanism, which aggregates information only from neighboring nodes within a limited range. Graph neural networks demonstrate strong potential for small- and medium-scale graph problems, particularly in analyzing complex systems such as wireless networks, where node interconnections are critical. However, as graph size increases, performance deteriorates, highlighting the need for improvements in aggregation and optimization algorithms.

1. Hwang F.K., Richards D.S. Steiner Tree Problems. Networks. 1992;22(1):55–89. https://doi.org/10.1002/net.3230220105

2. Ljubić I. Solving Steiner trees: Recent advances, challenges, and perspectives. Networks. 2021;77(2):177–204. https://doi.org/10.1002/net.22005

3. Basok M., Cherkashin D., Rastegaev N., Teplitskaya Ya. On Uniqueness in Steiner Problem. International Mathematics Research Notices. 2024;2024(10):8819–8838. https://doi.org/10.1093/imrn/rnae025

4. Lotarev D.T., Uzdemir A.P. Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph. Automation and Remote Control. 2005;66(10):1603–1613. https://doi.org/10.1007/s10513-005-0194-y

5. Grigoreva D.R., Faizullina A.G., Basyrov R.R., Sharipov R.S. Use of Steiner Problem in Solving Practical Problems of Road Construction. Modern Applied Science. 2015;9(4):294–302. https://doi.org/10.5539/mas.v9n4p294

6. Winter P. Steiner Problem in Networks: A Survey. Networks. 1987;17(2):129–167. https://doi.org/10.1002/net.3230170203

7. Morrison D.R., Jacobson S.H., Sauppe J.J., Sewell E.C. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization. 2016;19:79–102. https://doi.org/10.1016/j.disopt.2016.01.005

8. Fampa M., Lee J., Melo W. A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space. Computational Optimization and Applications. 2016;65(1):47–71. https://doi.org/10.1007/s10589-016-9835-z

9. Do T.A., Ban H.-B., Huynh T.T.B., Le M.T., Nguyen B.L. Genetic algorithm based approach to solve the Clustered Steiner Tree Problem. Evolutionary Intelligence. 2023;17:1547–1566. https://doi.org/10.1007/s12065-023-00848-w

10. Jayadeva, Bhaumik B. A neural network for the Steiner minimal tree problem. Biological Cybernetics. 1994;70:485–494. https://doi.org/10.1007/BF00203241

11. Yen B.P.-C., Luo Yu. Deep Reinforcement Learning for Solving Directed Steiner Tree Problems. In: TENCON 2022 – 2022 IEEE Region 10 Conference (TENCON), 01–04 November 2022, Hong Kong, China. IEEE; 2022. pp. 1–5. https://doi.org/10.1109/TENCON55691.2022.9977539

12. Kahng A.B., Nerem R.R., Wang Yu., Yang Ch.-Yi. NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem. In: Proceedings of the AAAI Conference on Artificial Intelligence: The Thirty-Eighth AAAI Conference on Artificial Intelligence, 20–27 February 2024, Vancouver, Canada. Washington: AAAI Press; 2024. pp. 13022–13030. https://doi.org/10.1609/aaai.v38i12.29200

13. Wu Z., Pan Sh., Chen F., Long G., Zhang Ch., Yu Ph.S. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems. 2021;32(1):4–24. https://doi.org/10.1109/TNNLS.2020.2978386

14. Gilmer J., Schoenholz S.S., Riley P.F., Vinyals O., Dahl G.E. Message Passing Neural Networks. In: Machine Learning Meets Quantum Physics. Cham: Springer; 2020. pp. 199–214. https://doi.org/10.1007/978-3-030-40245-7_10

15. Koch T., Martin A., Voß S. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. In: Steiner Trees in Industry. New York: Springer; 2001. pp. 285–325. https://doi.org/10.1007/978-1-4613-0255-1_9

16. Mehlhorn K. A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters. 1988;27(3):125–128. https://doi.org/10.1016/0020-0190(88)90066-X