Использование графовых нейронных сетей для решения задачи Штейнера

Теория дискретной оптимизации играет важную роль в решении задач теории графов, таких как задача Штейнера. Она используется в транспортной инфраструктуре, логистике и проектировании коммуникационных сетей. Задача является NP-трудной, что требует применения эвристических методов, таких как генетические алгоритмы и искусственные нейронные сети. Для решения задачи Штейнера была выбрана графовая нейронная сеть (GNN). Архитектура GNN включает итеративное обновление признаков с использованием информации о смежных вершинах, что позволяет моделировать сложные зависимости в графах. Для агрегации информации применяется механизм передачи сообщений (MPNN), который обновляет состояние вершины, учитывая данные смежных вершин и ребер. Обучение модели осуществляется с использованием графов, сгенерированных с помощью эвристического алгоритма Мельхорна. В эксперименте показано, что GNN хорошо работает на графах, схожих с обучающими, но при увеличении размера входных графов метрики точности и полноты результатов значительно снижаются. Это снижение, скорее всего, связано с ограничениями механизма MPNN, который агрегирует информацию о соседних вершинах на ограниченном расстоянии. Графовые нейронные сети показывают высокий потенциал для задач на графах небольшой и средней размерности, особенно в анализе сложных систем, таких как беспроводные сети, где важны взаимосвязи между вершинами. Однако при увеличении размерности наблюдается снижение качества, что требует улучшений в алгоритмах агрегации и оптимизации.

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. Лотарев Д.Т., Уздемир А.П. Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе. Автоматика и телемеханика. 2005;(10):80–92.

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