Research map / Graph learning / Graph algorithms and clustering
Limited Query Graph Connectivity Test
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the Limited Query Graph Connectivity Test model with a scalable exact algorithm (iterative path/cut set and tree-structure growth with integer programming), plus heuristics (horizon-limited exact "Tree", RL, MCTS) that beat eight ported SBFE/sequential-testing heuristics.
Problem
Adaptively querying hidden On/Off edges in a graph to establish s-t connectivity (find a path of On edges or a cut of Off edges) with a query budget B, minimizing expected number of queries; motivated by attack-path analysis in Active Directory networks where each query requires manual IT admin effo
Approach
Iteratively grows a path set, cut set and policy-tree structure, solving each subproblem exactly with an integer program, so the exact optimum converges; the query limit makes this scalable, and limiting the planning horizon of this exact solver yields the best heuristic.
Key results
- With B=5 the exact algorithm solves all 25 graphs, and H1 is optimal in all but one graph (bcspwr07).
- With B=10 the Tree heuristic beats the best of 8 existing heuristics on 11 graphs, loses on 2, and ties on 12.
- The exact algorithm converges to the optimal policy without query limit on r2000 (18795 edges), versus prior exact methods limited to about 20 edges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the limited-horizon exact-algorithm heuristic instead of the best existing heuristic | Limited Query Graph Connectivity Test · 25 graphs, B=10 | expected query count: wins for 11 graphs, loses for 2 graphs, and ties for 12 graphs | Mixed |
| Use the limited-horizon exact-algorithm heuristic instead of RL or MCTS | Limited Query Graph Connectivity Test · 25 graphs, B=10 | expected query count | Helped |
| Use the exact algorithm instead of existing heuristics | Limited Query Graph Connectivity Test · 25 graphs, B=5 | expected query count: optimal results in all but one graph (bcspwr07) | Mixed |
Surprising findings
- PPO collapsed to cloning the H1 default action, so entropy-maximising SAC was used instead.
- Query count distributions are heavy-tailed, so the query limit rarely binds in practice.
Limitations
- Exact algorithm is not fixed-parameter tractable and convergence is not guaranteed in practice; large-B cases give only lower bounds (e.g., r4000 at B=10).
- Query-count minimisation is #P-hard, so exact solving is inherently expensive.
- Experiments assume unit query cost and independent edges with p=0.5.
Experimental setup
Datasets: euroroad minnesota USAir97 power bcspwr01-10 bugfix football chesapeake cattle networkx numpy matplotlib
Benchmarks: euroroad minnesota USAir97 power bcspwr01-10 bugfix football chesapeake cattle networkx numpy matplotlib
Metrics: expected query count optimality gap of lower bound
Baselines: H1 H2-Both H2-Path H2-Cut MinSC MinSC-Path MinSC-Cut Adaptive Submodular RL (discrete SAC) MCTS
Builds on: Stochastic Boolean Function Evaluation optimal decision trees via integer programming H1 heuristic (sequential testing) Soft Actor-Critic for discrete actions
Closest papers by meaning
- Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing (NeurIPS 2025 · similarity 0.85)
- Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks (AAAI 2025 · similarity 0.85)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.84)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.84)
- The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.84)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.