Query-decision Regression between Shortest Path and Minimum Steiner Tree
- URL: http://arxiv.org/abs/2402.02211v1
- Date: Sat, 3 Feb 2024 17:05:01 GMT
- Title: Query-decision Regression between Shortest Path and Minimum Steiner Tree
- Authors: Guangmo Tong, Peng Zhao, Mina Samizadeh
- Abstract summary: This paper focuses on the shortest path problem and the minimum Steiner tree problem.
We provide theoretical insights regarding the design of realizable hypothesis spaces for building scoring models.
Our experimental studies show that such problems can be solved to a decent extent with statistical significance.
- Score: 20.092639310758145
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Considering a graph with unknown weights, can we find the shortest path for a
pair of nodes if we know the minimal Steiner trees associated with some subset
of nodes? That is, with respect to a fixed latent decision-making system (e.g.,
a weighted graph), we seek to solve one optimization problem (e.g., the
shortest path problem) by leveraging information associated with another
optimization problem (e.g., the minimal Steiner tree problem). In this paper,
we study such a prototype problem called \textit{query-decision regression with
task shifts}, focusing on the shortest path problem and the minimum Steiner
tree problem. We provide theoretical insights regarding the design of
realizable hypothesis spaces for building scoring models, and present two
principled learning frameworks. Our experimental studies show that such
problems can be solved to a decent extent with statistical significance.
Related papers
- Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs [0.0]
In this paper, we solve the Minimum Spanning Tree Problem with Conflicts using a tailored Kernel Search method.
The main novelty of the approach consists in using an independent set of the conflict graph within the algorithm.
arXiv Detail & Related papers (2024-01-04T12:10:39Z) - 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) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
The minimax algorithms for neural networks have been developed to solve many problems.
In this paper, we propose two types of minimax algorithms.
For the setting, we propose DRSGDA and prove that our method achieves a gradient.
arXiv Detail & Related papers (2023-02-08T01:42:45Z) - NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree
Problems [0.0]
We propose NeuroPrim, a novel framework for solving various spanning tree problems by defining a Decision Process (MDP) for general optimization problems on graphs.
We apply our framework to three difficult problems on Euclidean space: the Degree-constrained Minimum Spanning Tree (DCMST) problem, the Minimum Cost Spanning Tree (MRCST) problem, and the Steiner Tree Problem in Routing graphs (STP)
arXiv Detail & Related papers (2022-10-22T13:49:29Z) - 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) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
We design and analyze an algorithm that boosts the error exponent by at least 40% when $rho$ is at least $0.8$.
Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph.
arXiv Detail & Related papers (2021-10-27T10:45: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) - Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
Previous neural solvers of math word problems (MWPs) are learned with full supervision and fail to generate diverse solutions.
We introduce a textitweakly-supervised paradigm for learning MWPs.
Our method only requires the annotations of the final answers and can generate various solutions for a single problem.
arXiv Detail & Related papers (2020-12-19T03:10:21Z) - Solving the Steiner Tree Problem with few Terminals [8.024778381207128]
A state-of-the-art algorithm to solve the Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner algorithm.
We enhance the Dijkstra-Steiner algorithm and establish a revisited algorithm, called DS*.
We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible function.
arXiv Detail & Related papers (2020-11-09T17:46:02Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
We introduce a novel learning problem for dense subgraph discovery.
We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability.
We then design a more scalable algorithm with a theoretical guarantee.
arXiv Detail & Related papers (2020-06-24T11:37:33Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data.
In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem.
We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z)
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.