# Limited Query Graph Connectivity Test

arXiv: https://arxiv.org/abs/2302.13036 · HTML: https://mlsanity.com/paper/2302.13036/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 25 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic for Discrete Action Settings](https://mlsanity.com/paper/1910.07207/) (2019)
- [Deep Reinforcement Learning for Cost-Effective Medical Diagnosis](https://mlsanity.com/paper/2302.10261/) (2023)
- [Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover](https://mlsanity.com/paper/1303.0726/) (2013)
- [Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs](https://mlsanity.com/paper/2112.13175/) (2021)
- [Defending Active Directory by Combining Neural Network based Dynamic Program and Evolutionary Diversity Optimisation](https://mlsanity.com/paper/2204.03397/) (2022)
- [Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs](https://mlsanity.com/paper/2212.04326/) (2022)
- [Graph Connectivity with Noisy Queries](https://mlsanity.com/paper/2208.10423/) (2022)

## Built on by (most cited first, 2 of 2)

- [Optimizing Cyber Defense in Dynamic Active Directories through Reinforcement Learning](https://mlsanity.com/paper/2406.19596/) (2024)
- [Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory](https://mlsanity.com/paper/2505.01028/) (2025)

## Abstract (arXiv)

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.