Title: Adaptive Inferential Method for Monotone Graph Invariants,
Abstract: We consider the problem of undirected graphical model inference. In many
applications, instead of perfectly recovering the unknown graph structure, a
more realistic goal is to infer some graph invariants (e.g., the maximum
degree, the number of connected subgraphs, the number of isolated nodes). In
this paper, we propose a new inferential framework for testing nested multiple
hypotheses and constructing confidence intervals of the unknown graph
invariants under undirected graphical models. Compared to perfect graph
recovery, our methods require significantly weaker conditions. This paper makes
two major contributions: (i) Methodologically, for testing nested multiple
hypotheses, we propose a skip-down algorithm on the whole family of monotone
graph invariants (The invariants which are non-decreasing under addition of
edges). We further show that the same skip-down algorithm also provides valid
confidence intervals for the targeted graph invariants. (ii) Theoretically, we
prove that the length of the obtained confidence intervals are optimal and
adaptive to the unknown signal strength. We also prove generic lower bounds for
the confidence interval length for various invariants. Numerical results on
both synthetic simulations and a brain imaging dataset are provided to
illustrate the usefulness of the proposed method.