Learning-Based Algorithms for Graph Searching Problems

• URL: http://arxiv.org/abs/2402.17736v2
• Date: Sat, 16 Mar 2024 21:56:58 GMT
• Title: Learning-Based Algorithms for Graph Searching Problems
• Authors: Adela Frances DePavia, Erasmo Tani, Ali Vakilian,
• Abstract summary: We consider the problem of graph searching with prediction recently introduced by Banerjee et al. In this problem, an agent, starting at some $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$. We design algorithms for this search task on unknown graphs.
• Score: 6.923787372512553
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$ while minimizing the total distance travelled. We study a setting in which at any node $v$, the agent receives a noisy estimate of the distance from $v$ to $g$. We design algorithms for this search task on unknown graphs. We establish the first formal guarantees on unknown weighted graphs and provide lower bounds showing that the algorithms we propose have optimal or nearly-optimal dependence on the prediction error. Further, we perform numerical experiments demonstrating that in addition to being robust to adversarial error, our algorithms perform well in typical instances in which the error is stochastic. Finally, we provide alternative simpler performance bounds on the algorithms of Banerjee et al. (2022) for the case of searching on a known graph, and establish new lower bounds for this setting.

Related papers

• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Causal Bandits without Graph Learning [28.021500949026766]
  We develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We extend our algorithm to the case when the reward node has multiple parents.
  arXiv  Detail & Related papers  (2023-01-26T20:27:14Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  Causal effect estimation from observational data is a fundamental task in empirical sciences. This paper focuses on front-door adjustment -- a classic technique which, using observed mediators, allows to identify causal effects even in the presence of unobserved confounders.
  arXiv  Detail & Related papers  (2022-11-29T18:44:03Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  We give a characterization of a minimal sized set of atomic interventions to check the correctness of a claimed causal graph. We generalize our results to the settings of bounded size interventions and node-dependent interventional costs. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs.
  arXiv  Detail & Related papers  (2022-06-30T15:52:30Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• 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)
• 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)

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.