Vulcan: A Machine Learning Approach to Solving Steiner Tree Problem in Graphs

Home

Discover

Bookmarks

Keep Up With Latest Trending Papers. Computer Science, AI and more.Subscribe

CC BY

Source arXiv

Machine Learning

Artificial Intelligence

Vulcan: A Machine Learning Approach to Solving Steiner Tree Problem in Graphs

Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning

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 the classic np-hard combinatorial problem of finding a tree of minimum weight in the graph that connects a given set of vertices.

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 instance of the same problem, 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.

We implement a prototype of vulcan and demonstrate its efficacy and efficiency with extensive experiments using real-world and synthetic datasets.

Authors

Haizhou Du, Zong Yan, Qiao Xiang, Qinqing Zhan

◐ Recommended Follows

◐ Latest Activity