Abstract:

We propose a systematic inferential toolkit for multiple hypotheses and confidence intervals of structural quantities in graphical models such as the maximum degree, the number of connected subgraphs, the number of singletons, etc. We propose a general skipdown algorithm for testing nested multiple hypotheses on graph invariants. Its validity is shown for any graph invariant which is nondecreasing under addition of edges. We also derive confidence intervals for graph invariants from the skipdown algorithm. We prove that the length of our confidence intervals are optimal and doubly adaptive to the signal strength. The first level of adaptivity implies that when the signal strength is strong enough, the interval length is decreasing if there are more parameters with large magnitude. The second level of adaptivity shows that when no signal strength is guaranteed, the length reduces to the optimal rate. Moreover, we provide general theoretical lower bounds for the confidence interval length for various invariants. Numerical results on both synthetic simulations and a brain imaging dataset illustrate the usefulness of our method.
