Research map / Graph learning / Graph algorithms and clustering
Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing
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.
Formulates adaptive frontier exploration on graphs (AFEG) as a discounted sequential testing problem and proposes a Gittins-index policy that is provably optimal on forests, with an efficient piecewise-linear implementation and strong empirical results on synthetic and real sexual-contact networks for disease testing.
Problem
Sequentially choosing nodes on a graph with unknown Markov-correlated discrete labels to maximize discounted label-dependent rewards, when actions are restricted to the frontier of previously selected nodes (e.g., network-based disease testing).
Approach
Reduce frontier-constrained AFEG on forests to a discrete branching bandit with history-dependent rewards and compute Gittins indices efficiently via piecewise-linear representations of the recursive phi and Phi functions; on general graphs, apply the same policy to a BFS spanning tree heuristically.
Key results
- On HIV sexual interaction networks with only half the population testable, Gittins detects nearly all positive cases while other baselines detect about 80%.
- On n=10 trees, Gittins matches the brute-force Optimal policy exactly, as predicted by the forest optimality result.
- Gittins index computation runs in O(n^2 |Omega|^2) time with O(n |Omega|^2) oracle calls to P.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Gittins instead of Random, Greedy, or DQN | AFEG policies on synthetic tree graphs · Synthetic trees | expected accumulated discounted reward | Helped |
| use Gittins instead of Greedy or DQN | AFEG policies on synthetic non-tree graphs · Synthetic 50-node graphs with added edges | expected accumulated discounted reward | Mixed |
| use Gittins instead of other baselines | AFEG policies on real-world sexual interaction graphs · Gonorrhea, Chlamydia, Syphilis, HIV, and Hepatitis | fraction of positive cases detected | Helped |
| use Gittins instead of other baselines | AFEG policies on the HIV interaction graph · HIV, half the population tested | fraction of positive cases detected: nearly all vs about 80% | Helped |
| increase noise in the available distribution from Qε | AFEG policies evaluated using the HIV distribution · HIV | fraction of positive cases detected | Hurt |
Surprising findings
- Gittins' advantage over Greedy and DQN diminishes as edges are added to trees, but it remains competitive on non-tree graphs.
Limitations
- Optimality guarantee only holds for tree/forest-structured graphs; general graphs use a heuristic BFS spanning tree.
- Assumes the interaction graph is known and fixed.
- Requires exact inference oracle for P, tractable only on sparse or low-treewidth graphs.
Experimental setup
Datasets: ICPSR 22140 sexual interaction network data (Gonorrhea, Chlamydia, Syphilis, HIV, Hepatitis) synthetic random trees
Benchmarks: synthetic trees n=10,50,100 synthetic non-tree graphs ICPSR sexual interaction graphs subsampled to 300 nodes
Metrics: expected accumulated discounted reward fraction of positive cases detected
Baselines: Random Greedy DQN Optimal
Builds on: Gittins index branching bandits adaptive submodularity deep Q-network
Closest papers by meaning
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.87)
- Limited Query Graph Connectivity Test (AAAI 2024 · similarity 0.85)
- Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.85)
- Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency (ICML 2024 · similarity 0.84)
- Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs (ICML 2025 · similarity 0.84)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.84)
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.