Adaptive Hypothesis Testing for Dependent Graph-Valued Structures via Topological Value of Information

Modern ML systems increasingly output uncertain graph-valued structures, including causal graphs, mechanistic graphs, interaction networks, and graph-based explanations. In these settings, reliability depends on deciding which dependent structural hypotheses to test next under a limited budget. We formulate this as \emph{adaptive structural hypothesis testing}, where candidate edges are binary hypotheses, tests produce noisy evidence, and test value depends on the global graph-valued hypothesis state. We introduce Topological Complexity Minimization (TCM), a cost-aware adaptive testing policy that scores a probabilistic belief graph using connected components $(\beta_0)$ and independent cycles $(\beta_1)$, and selects tests that maximize expected topological simplification per unit cost. We evaluate TCM on standard Bayesian network DAGs from bnlearn Child, Insurance and 200 atom-level mechanistic graphs from mech-USPTO-31k. Across cycle-dominated, fragmentation-dominated, and mixed corruption regimes, TCM achieves the highest structural efficiency in both benchmark families while preserving competitive edge-level F1. On mechanistic graphs, TCM improves over CycleRank from 0.452 to 0.576 in fragmentation regimes and from 0.715 to 0.830 in mixed regimes; on the Bayesian network DAGs, the corresponding gains are 1.062 to 1.471 and 1.406 to 2.049. These results show that local edge uncertainty is not always aligned with graph-level disambiguation, and that lightweight topological utilities can support adaptive hypothesis testing under structural dependence.