Computing Steiner Trees using Graph Neural Networks

Abstract

Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problems such as subgraph isomorphism, detecting cliques, and the traveling salesman problem. However, many NP-complete problems are as of yet unexplored using this method. In this paper, we tackle the Steiner Tree Problem. We employ four learning frameworks to compute low cost Steiner trees: feed-forward neural networks, graph neural networks, graph convolutional networks, and a graph attention model. We use these frameworks in two fundamentally different ways: 1) to train the models to learn the actual Steiner tree nodes, 2) to train the model to learn good Steiner point candidates to be connected to the constructed tree using a shortest path in a greedy fashion. We illustrate the robustness of our heuristics on several random graph generation models as well as the SteinLib data library. Our finding suggests that the out-of-the-box application of GNN methods does worse than the classic 2-approximation method. However, when combined with a greedy shortest path construction, it even does slightly better than the 2-approximation algorithm. This result sheds light on the fundamental capabilities and limitations of graph learning techniques on classical NP-complete problems.

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• Emergence of scaling in random networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Intensity and coherence of motifs in weighted complex networks
• Learning Combinatorial Optimization Algorithms over Graphs
• Generalizations of the clustering coefficient to weighted complex networks
• Interaction Networks for Learning about Objects, Relations and Physics
• graph2vec: Learning Distributed Representations of Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• Attention, Learn to Solve Routing Problems!
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Node Masking: Making Graph Neural Networks Generalize and Scale Better