Bayesian Probing on Graphs
Abstract
We introduce a stochastic probing problem with correlated items. In our model, which we call Bayesian Probing, the correlations are modeled by an underlying graph G. Each vertex is independently active with a known probability. Each item corresponds to an edge in the graph. Probing an edge has some cost, gives some reward if both endpoints are active, and also reveals the state of its endpoints. Hence a probe induces a Bayesian update on the remaining edges. The goal is to adaptively probe items/edges subject to a knapsack constraint to maximize the expected total reward obtained from the probed edges. Bayesian Probing generalizes stochastic knapsack and stochastic probing by allowing correlations between items. Moreover, it gives a tractable model for the Bayesian Active Search problem, a popular problem considered in the machine learning community. In Bayesian Active Search, the goal is to find items in a particular class by adaptively probing at most, say k, items. Given a prior distribution over items, we want to compute a Bayesian policy to maximize the number of such items found. For this general problem with arbitrary priors, there are strong lower bounds on efficiently computing good policies. In this paper, we design efficient approximation algorithms for Bayesian Probing. These results give the first efficient approximation algorithms for Bayesian Active Search, for a class of practically-relevant prior distributions.
Related
- Bayesian Matrix-Valued Graphs for Context-Dependent Multivariate Relationships
- Semiparametric Bayesian structure learning of nonparanormal directed acyclic graphs with local--global shrinkage
- Bayesian Semiparametric Hidden Markov Random Partition Fields for Factor Collapse on Graphs: A Study of Cortical Mapping of Fingertips
- Amortized Bayesian Disease Mapping and Boundary Detection on Heterogeneous Spatial Graphs
- Online Bayesian Node Classification on Inductive Graphs under Distribution Shift
BibTeX
@misc{gupta2026bayesian,
title = {{Bayesian Probing on Graphs}},
author = {Anupam Gupta and Benjamin Moseley and Rudy Zhou},
howpublished = {arXiv},
year = {2026},
month = jun,
doi = {10.48550/arxiv.2606.09729},
eprint = {2606.09729},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.09729},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Bayesian Probing on Graphs
AU - Anupam Gupta
AU - Benjamin Moseley
AU - Rudy Zhou
PY - 2026
DA - 2026/06/08
PB - arXiv
DO - 10.48550/arxiv.2606.09729
UR - https://arxiv.org/abs/2606.09729
AB - We introduce a stochastic probing problem with correlated items. In our model, which we call Bayesian Probing, the correlations are modeled by an underlying graph G. Each vertex is independently active with a known probability. Each item corresponds to an edge in the graph. Probing an edge has some cost, gives some reward if both endpoints are active, and also reveals the state of its endpoints. Hence a probe induces a Bayesian update on the remaining edges. The goal is to adaptively probe items/edges subject to a knapsack constraint to maximize the expected total reward obtained from the probed edges. Bayesian Probing generalizes stochastic knapsack and stochastic probing by allowing correlations between items. Moreover, it gives a tractable model for the Bayesian Active Search problem, a popular problem considered in the machine learning community. In Bayesian Active Search, the goal is to find items in a particular class by adaptively probing at most, say k, items. Given a prior distribution over items, we want to compute a Bayesian policy to maximize the number of such items found. For this general problem with arbitrary priors, there are strong lower bounds on efficiently computing good policies. In this paper, we design efficient approximation algorithms for Bayesian Probing. These results give the first efficient approximation algorithms for Bayesian Active Search, for a class of practically-relevant prior distributions.
ER -