Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and
  Deep Reinforcement Learning
  Steiner Tree Problem (STP) in graphs aims to find a tree of minimum weight in
the graph that connects a given set of vertices. It is a classic NP-hard
combinatorial optimization problem and has many real-world applications (e.g.,
VLSI chip design, transportation network planning and wireless sensor
networks). Many exact and approximate algorithms have been developed for STP,
but they suffer from high computational complexity and weak worst-case solution
guarantees, respectively. Heuristic algorithms are also developed. However,
each of them requires application domain knowledge to design and is only
suitable for specific scenarios. Motivated by the recently reported observation
that instances of the same NP-hard combinatorial problem may maintain the same
or similar combinatorial structure but mainly differ in their data, we
investigate the feasibility and benefits of applying machine learning
techniques to solving STP. To this end, we design a novel model Vulcan based on
novel graph neural networks and deep reinforcement learning. The core of Vulcan
is a novel, compact graph embedding that transforms highdimensional graph
structure data (i.e., path-changed information) into a low-dimensional vector
representation. Given an STP instance, Vulcan uses this embedding to encode its
pathrelated information and sends the encoded graph to a deep reinforcement
learning component based on a double deep Q network (DDQN) to find solutions.
In addition to STP, Vulcan can also find solutions to a wide range of NP-hard
problems (e.g., SAT, MVC and X3C) by reducing them to STP. We implement a
prototype of Vulcan and demonstrate its efficacy and efficiency with extensive
experiments using real-world and synthetic datasets.
