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