# Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 72 references that are in the map.
- First posted on arXiv 27 May 2025.

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

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Practical Calculation of Gittins Indices for Multi-armed Bandits](https://mlsanity.com/paper/1909.05075/) (2019)

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

- [Policy-Embedded Graph Expansion: Networked HIV Testing with Diffusion-Driven Network Samples](https://mlsanity.com/paper/2601.16233/) (2026)
- [Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions](https://mlsanity.com/paper/2601.22211/) (2026)

## Abstract (arXiv)

We study a sequential decision-making problem on a n-node graph G where each node has an unknown label from a finite set Omega, drawn from a joint distribution P that is Markov with respect to G. At each step, selecting a node reveals its label and yields a label-dependent reward. The goal is to adaptively choose nodes to maximize expected accumulated discounted rewards. We impose a frontier exploration constraint, where actions are limited to neighbors of previously selected nodes, reflecting practical constraints in settings such as contact tracing and robotic exploration. We design a Gittins index-based policy that applies to general graphs and is provably optimal when G is a forest. Our implementation runs in O(n2 · |Omega|2) time while using O(n · |Omega|2) oracle calls to P and O(n2 · |Omega|) space. Experiments on synthetic and real-world graphs show that our method consistently outperforms natural baselines, including in non-tree, budget-limited, and undiscounted settings. For example, in HIV testing simulations on real-world sexual interaction networks, our policy detects nearly all positive cases with only half the population tested, substantially outperforming other baselines.