Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search

• URL: http://arxiv.org/abs/2305.00535v1
• Date: Sun, 30 Apr 2023 17:15:38 GMT
• Title: Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search
• Authors: Reyan Ahmed, Mithun Ghosh, Kwang-Sung Jun, Stephen Kobourov
• Abstract summary: We describe an approach for computing Steiner Trees by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a Steiner tree.
• Score: 9.061356032792952
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks are useful for learning problems, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing Steiner Trees by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a Steiner tree. The proposed method consistently outperforms the standard 2-approximation algorithm on many different types of graphs and often finds the optimal solution.

Related papers

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• Solving the Tree Containment Problem Using Graph Neural Networks [0.6081917632687639]
  Tree Containment is a problem in phylogenetics useful for verifying a proposed phylogenetic network. We propose to solve it approximately using Graph Neural Networks. Our algorithm demonstrates an accuracy of over $95%$ in solving the tree containment problem on instances with up to 100 leaves.
  arXiv  Detail & Related papers  (2024-04-15T14:10:06Z)
• GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection [51.608147732998994]
  Graph neural networks are increasingly becoming the framework of choice for graph-based machine learning. We propose a new graph neural network architecture that substitutes classical message passing with an analysis of the local distribution of node features.
  arXiv  Detail & Related papers  (2024-01-17T13:04:23Z)
• Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search [9.128418945452088]
  We describe an approach for computing graph sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a sparsifier.
  arXiv  Detail & Related papers  (2023-11-17T03:59:50Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
  We consider the Steiner tree problem on graphs where we are given a set of nodes. The goal is to find a tree sub-graph that contains all nodes in the given set, potentially including additional nodes.
  arXiv  Detail & Related papers  (2022-08-25T10:31:00Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  Subgraph Matching is a core operation in graph database search, biomedical analysis, social group finding, etc. In this paper, we propose a novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs. Experiments on five large real-world target graphs show that N-BLS can significantly improve the subgraph matching performance.
  arXiv  Detail & Related papers  (2022-07-21T04:47:21Z)
• Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
  In this paper, we tackle the Steiner Tree Problem. We employ four learning frameworks to compute low cost Steiner trees. Our finding suggests that the out-of-the-box application of GNN methods does worse than the classic 2-approximation algorithm.
  arXiv  Detail & Related papers  (2021-08-18T19:55:16Z)
• Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks [74.26734952400925]
  We propose a novel Minimum Graph Entropy (MinGE) algorithm for Node Embedding Dimension Selection (NEDS) MinGE considers both feature entropy and structure entropy on graphs, which are carefully designed according to the characteristics of the rich information in them. Experiments with popular Graph Neural Networks (GNNs) on benchmark datasets demonstrate the effectiveness and generalizability of our proposed MinGE.
  arXiv  Detail & Related papers  (2021-05-07T11:40:29Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Neural Subgraph Matching [57.05893848555512]
  NeuroMatch is an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch is 100x faster than existing geometric approaches and 18% more accurate than existing subgraph matching methods.
  arXiv  Detail & Related papers  (2020-07-06T22:06:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.