Limited Query Graph Connectivity Test
- URL: http://arxiv.org/abs/2302.13036v3
- Date: Mon, 18 Dec 2023 13:29:00 GMT
- Title: Limited Query Graph Connectivity Test
- Authors: Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen
- Abstract summary: We consider a graph whose edges have two possible states (On/Off)
We aim to test s-t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges)
Our model is mainly motivated by a cyber security use case where we need to establish whether an attack path exists in a network.
- Score: 14.108454811023465
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a combinatorial optimisation model called Limited Query Graph
Connectivity Test. We consider a graph whose edges have two possible states
(On/Off). The edges' states are hidden initially. We could query an edge to
reveal its state. Given a source s and a destination t, we aim to test s-t
connectivity by identifying either a path (consisting of only On edges) or a
cut (consisting of only Off edges). We are limited to B queries, after which we
stop regardless of whether graph connectivity is established. We aim to design
a query policy that minimizes the expected number of queries.
Our model is mainly motivated by a cyber security use case where we need to
establish whether an attack path exists in a network, between a source and a
destination. Edge query is resolved by manual effort from the IT admin, which
is the motivation behind query minimization.
Our model is highly related to monotone Stochastic Boolean Function
Evaluation (SBFE). There are two existing exact algorithms for SBFE that are
prohibitively expensive. We propose a significantly more scalable exact
algorithm. While previous exact algorithms only scale for trivial graphs (i.e.,
past works experimented on at most 20 edges), we empirically demonstrate that
our algorithm is scalable for a wide range of much larger practical graphs
(i.e., Windows domain network graphs with tens of thousands of edges).
We propose three heuristics. Our best-performing heuristic is via reducing
the search horizon of the exact algorithm. The other two are via reinforcement
learning (RL) and Monte Carlo tree search (MCTS). We also derive an anytime
algorithm for computing the performance lower bound. Experimentally, we show
that all our heuristics are near optimal. The exact algorithm based heuristic
outperforms all, surpassing RL, MCTS and 8 existing heuristics ported from SBFE
and related literature.
Related papers
- Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference [18.101059380671582]
We study multi-armed bandits under network interference.<n>This induces an exponentially large action space.<n>We propose a novel algorithm that uses the local graph structure to minimize regret.
arXiv Detail & Related papers (2025-03-10T17:25:24Z) - Graph Inference with Effective Resistance Queries [2.2349172369559156]
We study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices.
Although it is known that an $n$-vertex graph can be uniquely reconstructed from all possible ER queries, little else is known.
arXiv Detail & Related papers (2025-02-25T16:37:25Z) - Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
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.
arXiv Detail & Related papers (2024-02-27T18:12:58Z) - Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
We propose a general learnable graph matching method to address these issues.
Our method achieves state-of-the-art performance on several MOT datasets.
For image matching, our method outperforms state-of-the-art methods on a popular indoor dataset, ScanNet.
arXiv Detail & Related papers (2023-03-27T17:39:00Z) - 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) - Arch-Graph: Acyclic Architecture Relation Predictor for
Task-Transferable Neural Architecture Search [96.31315520244605]
Arch-Graph is a transferable NAS method that predicts task-specific optimal architectures.
We show Arch-Graph's transferability and high sample efficiency across numerous tasks.
It is able to find top 0.16% and 0.29% architectures on average on two search spaces under the budget of only 50 models.
arXiv Detail & Related papers (2022-04-12T16:46:06Z) - 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) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
We show that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of $> 5$ a maximum cut of at most $1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$.
We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$, where
arXiv Detail & Related papers (2021-06-10T16:28:23Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
Data association across frames is at the core of Multiple Object Tracking (MOT) task.
Existing methods mostly ignore the context information among tracklets and intra-frame detections.
We propose a novel learnable graph matching method to address these issues.
arXiv Detail & Related papers (2021-03-30T08:58:45Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models.
Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
arXiv Detail & Related papers (2020-08-29T14:58:26Z) - 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) - Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis [7.99536002595393]
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph.
We show that learning an optimal network with at most $k$ edges in the moralized graph presumably has no $f(k)cdot |I|O(1)$-time algorithm.
arXiv Detail & Related papers (2020-04-30T12:31:13Z)
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.