Adaptive Inferential Method for Monotone
Graph Invariants
arXiv:1707.09114v1 [] 28 Jul 2017

Junwei Lu∗

Matey Neykov∗

Han Liu∗†

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.

Keyword: Monotone graph invariant; Skip-Down method; Double adaptivity; Gaussian
multiplier bootstrap; Hollow graphs.

1

Introduction

Graphical models are widely used for modeling complex networks such as gene regulatory
networks and brain connectivity networks (Luscombe et al., 2004; Rubinov and Sporns, 2010).
We use an undirected graph G = (V, E) to represent the conditional dependency structure
of a d-dimensional random vector X = (X1 , . . . , Xd )T , where each vertex in V = {1, . . . , d}
∗

Department of Operations Research and Financial Engineering, Princeton University, Princeton NJ
08544, USA; e-mail: {junweil,mneykov,hanliu}@princeton.edu
†
Research supported by NSF DMS1454377-CAREER; NSF IIS 1546482-BIGDATA; NIH R01MH102339;
NSF IIS1408910; NIH R01GM083084.

1

corresponds to a component of the random vector X. Specifically, two nodes j and k are
connected if and only if Xj and Xk are conditionally dependent given the other variables.
Learning the structure of the graph in a graphical model has been widely studied in
the literature. Many theoretical studies focus on achieving a perfect recovery of the true
b satisfying P(G
b = G) → 1 as the
graph, i.e., they aim to find a consistent graph estimator G
sample size goes to infinity. For the Gaussian graphical model, many works estimate the
graph through the precision matrix Θ satisfying Θjk 6= 0 if and only if the edge (j, k) ∈ E
(Meinshausen and Bühlmann, 2006; Yuan and Lin, 2007; Friedman et al., 2008; Peng et al.,
2009; Lam and Fan, 2009; Ravikumar et al., 2011; Cai et al., 2011; Shen et al., 2012). For
the Ising model, the true graph is determined by the sparsity pattern of the interaction
parameters and we can estimate the parameters by sparse logistic regression (Ravikumar
et al., 2010). A number of authors relax the Gaussian or Ising assumption by allowing the
node-conditional distribution to belong to a univariate exponential family (see, e.g., Lee et al.,
2006; Höfling and Tibshirani, 2009; Jalali et al., 2011; Anandkumar et al., 2012; Yang et al.,
2012; Allen and Liu, 2012; Yang et al., 2013). This line of research extents to the mixed
graphical model framework in which the conditional distributions of two nodes can belong to
two different distributions from a univariate exponential family (see, e.g., Fellinghauer et al.,
2013; Lee and Hastie, 2015; Yang et al., 2014a; Chen et al., 2015). Semiparametric extensions
using copulas are also developed in Liu and Wasserman (2009), Liu et al. (2012a), Xue and
Zou (2012), and Liu et al. (2012b), and extended for mixed data in Fan et al. (2014). Danaher
et al. (2014), Qiu et al. (2013), Mohan et al. (2014) consider joint estimation of multiple
graphical models. However, in order to achieve the perfect graph recovery in these works,
some strong conditions especially the minimal signal strength assumption are usually needed
for the CLIME (Cai et al., 2011), the neighborhood selection (Meinshausen and Bühlmann,
2006; Zhou et al., 2009), the graphical Lasso (Lam and Fan, 2009) and the transellipitical
graphical model (Liu et al., 2012b). The minimal signal strength assumption imposes that
every edge has strong enough signal which is unlikely to hold in reality.
In this paper, we consider a statistical problem which imposes weaker assumptions
compared to minimal signal strength type of conditions. In particular, we aim to infer
the topological structure of the graph without imposing strong conditions required for
perfect recovery. The topological structure of a graph is an important feature in many real
applications. For instance, in a gene regulatory network, it is scientifically interesting to infer
the number of metabolic cycles where cells move through in the genomic network (Luscombe
et al., 2004). In neuroscience applications, one critical problem is to infer the degrees of
various cerebral areas in the brain network during certain cognitive processes (Hagmann
et al., 2008). In this paper, we propose a unified inferential framework on the topological
quantities related to graphical models. In particular, we focus on topological quantities which
are invariant under graph isomorphism. We call such quantities graph invariants, denoted as
I. Examples of graph invariants we consider include: maximum degree, maximum clique
size, chromatic number, girth, the number of connected subgraphs, etc. We are interested in
testing hypotheses with a nested structure:
H0k : I ≤ k, for k being all possible values of I.
2

(1.1)

Our goal is to propose a test with family-wise error control and power optimality. Moreover,
we aim to derive a confidence interval for I utilizing the method for nested multiple hypotheses.
Our paper will focus on the Gaussian graphical models whose graph structure is encoded by
the sparsity of precision matrices, but we will also discuss how the proposed method applies
to other more flexible graphical models.
A related research area on graphical models are concerned with inferential methods on
a single edge in the graphical model (Yang et al., 2014b; Gu et al., 2015; Ren et al., 2015;
Janková and van de Geer, 2016)). A few authors have also proposed to test multiple edges
simultaneously (among others, Liu, 2013; Cai et al., 2014; Lu et al., 2015). However, their
proposals require a user-specified set of edges to be tested simultaneously, and thus cannot
be directly applied to infer the topological structure of a graph. In another related research
direction, several authors (Arias-Castro et al., 2012, 2015, 2011; Addario-Berry et al., 2010)
have considered testing whether a graph is empty or it has certain topological structure and
discussed lower bounds. One of the drawbacks of these approaches is that the null hypothesis
is constrained to be an empty graph. The most related work to our paper is Neykov et al.
(2016). They propose a general theoretical framework for analyzing lower bounds for testing
hypothesis of whether a graph satisfies a certain graph property. To match the lower bound, a
data splitting procedure is required. However, our method does not need to split the dataset.
Our contributions to the inference of graph invariants for graphical models are three-fold
in methodology, theory of inference and fundamental limits.
• Methodology. We propose a fully data-driven method for the nested hypotheses on a
wide family of graph invariants I, which also derives confidence intervals for invariants. Unlike
Neykov et al. (2016)’s data splitting method, which tests a single hypothesis H0 : I ≤ k with a
specified k, our method does not need to pre-determine the value of k. In practice, it is usually
hard to decide which k to test. On the other hand, the nested hypotheses in (1.1) initiate a
fully data-driven approach to choosing the value of k. Nested multiple hypotheses problem
is considered by Bauer and Hackl (1987) for continuous parameters test. We propose a
skip-down algorithm for the nested hypotheses on combinatorial quantities, which iteratively
screens critical edge sets for the graph invariant of interest. We also derive confidence
intervals from the skip-down algorithm. Constructing confidence intervals for combinatorial
quantities is challenging as the standard confidence interval theory on continuous and smooth
parameters does not directly apply. We show that our proposed confidence interval [IbL , IbU ]
is asymptotically honest for all monotone graph invariants.
• Theory of Inference. For the Gaussian graphical model, we demonstrate that
the length of our proposed confidence interval [IbL , IbU ] is adaptive to the signal strength
of the precision
matrix Θ. To
p elaborate in detail, we define the significant edge set as

ESig (Θ) := (j, k) | |Θjk | ≥ C log d/n , which only keeps edges with signal strength larger
p
than C log d/n for some sufficiently large constant C. We show that the expected length
of confidence interval [IbL , IbU ] is adaptive to the value of the invariant I(ESig (Θ)), which
denotes the value of the graph invariant based on edge set ESig (Θ). Specifically, under some
regularity and scaling conditions, we show that for any monotone invariant I, EΘ [IbU − IbL ] is
decreasing when I(ESig (Θ))) becomes larger. More details regarding the adaptivity will be
3

shown in Theorem 4.5.
• Fundamental Limits. We provide a general theoretical result for the lower bound of
the confidence interval length for graph invariants. We provide a sufficient condition under
which the confidence interval length is optimal for a large family of invariants. Our sufficient
condition is uniquely characterized by the geometry of the graph invariant. This makes it
easier to show the lower bound of confidence interval length for many graph invariants. In
comparison, the lower bound results in Neykov et al. (2016) for graph properties hypothesis
test rely on probabilistic type conditions such as negative association (Joag-Dev and Proschan,
1983), which are difficult to verify in practice. Our result also bares similarity to results in
Cai and Guo (2015), who show a lower bound on the confidence interval length for the high
dimensional linear model. However, our confidence interval is for combinatorial quantities
where classical parametric and continuous statistical theory cannot be directly applied.

1.1

Notation

We denote the graph induced by a matrix Θ as G(Θ) = (V, E(Θ)), where (j, k) ∈ E(Θ) if
and only if Θjk 6= 0. Given any edge set E, we let V (E) = {v | ∃ u ∈ V, s.t. (u, v) ∈ E} be
the set of vertices in E. We denote the cardinality of a set V as |V |. Given two sequences
∞
{an }∞
n=1 and {bn }n=1 , if an ≤ Cbn for some finite positive constant C for all n large enough,
we denote it as an = O(bn ) or bn = Ω(an ). We use the notation an  bn if an = O(bn )
and bn = O(an ). We also write an = o(bn ) if an /bn → 0 as n goes infinity. We denote
a ∨ b = max(a, b) and a ∧ b = min(a, b) for any two scalars a and b. Given a scalar x, bxc
denotes the largest integer which is smaller than x. Let [n] denote the set {1, . . . , n}. For
×d2
a matrix A ∈ Rd1P
, we denote the max-norm kAkmax = maxi∈[d1 ],j∈[d2 ] |Aij |, the `1 -norm
kAk1 = maxj∈[d2 ] i∈[d1 ] |Aij |, and the operator norm kAk2 = supkvk2 =1 kAvk2 . Throughout
the paper, we let C, C1 , C2 , . . . be generic constants whose values may change in different
places.

1.2

Paper Organization

The rest of our paper is organized as follows. In Section 2, we introduce preliminary concepts
of graph theory including graph invariants and graph properties. In Section 3, we provide the
skip-down algorithm for graph invariant confidence intervals and tests on graph properties.
In Section 4, we show theoretical results on the optimality for our confidence intervals and
tests. In Section 5, we generalize our method to more flexible graphical models. We provide
numerical results on both synthetic simulations and brain imaging applications in Section 7.

2

Preliminaries on Graph Theory

Let V = {1, . . . , d} be the set of nodes and the edge set E be a subset of V × V . G = (V, E)
denotes an undirected graph with vertices in V and edges in E. We say G = (V, E) is
isomorphic to G0 = (V 0 , E 0 ) if there exists a one-to-one mapping σ : V → V 0 , such that
4

(j, k) ∈ E if and only if (σ(j), σ(k)) ∈ E 0 . We also write G  G0 if V ⊆ V 0 and E ⊆ E 0 . Let
Gd be the set of all graphs with d vertices. A graph invariant is a function I : Gd → Z such
that I(G) = I(G0 ) if G is isomorphic to G0 . In other words, a graph invariant is a geometric
characterization of the graph, which is invariant to vertex permutations. In this paper, we
are interested in a special family of graph invariants called monotone invariants defined as
follows.
Definition 2.1. A graph invariant I is monotone whenever I(G) ≤ I(G0 ) for all G  G0 .
Specifically, if a graph invariant takes binary values, i.e., P : Gd → {0, 1} such that
P(G) = P(G0 ) if G is isomorphic to G0 , we call this invariant P a graph property. We also
say a graph G satisfies a property P if P(G) = 1. Similarly to Definition 2.1, we define the
monotone graph property as follows.
Definition 2.2. A graph property P is monotone whenever P(G) ≤ P(G0 ) for all G  G0 .
In this paper, we will always take the vertex set V = {1, . . . , d}. Therefore, for simplicity
of notation, given a graph G = (V, E), we also write an invariant or a property as a function
of edge set, i.e., I(E) = I(G) and P(E) = P(G). From the definitions above, we can see that
a monotone graph invariant is non-decreasing under addition of edges. Similarly, if a graph
G satisfies a monotone property, the property is preserved under addition of edges to G.
Many extensively used graph invariants are monotone. For example, we can easily check
that the following invariants are monotone:
• The maximum degree of G, which is the largest number of vertices connected to a single
vertex in the graph (see Figure 1(a) for an example of a graph with maximum degree
5);
• The size of the longest chain in G, where a chain is a set of edges connecting a sequence
of distinct vertices consecutively, and the size of a chain is the number of edges it
contains (see Figure 1(b) for an example of a graph with longest chain of size 5);
• The size of the largest clique in G, where a clique is a subgraph such that any pair of
its vertices are connected and the size of a clique is the number of vertices it contains
(see Figure 1(c) for an example of a graph with largest clique size 5);
• The chromatic number of G, which is the smallest number of colors needed to color all
vertices, so that no vertices sharing the same color are adjacent (see Figure 1 (d) for an
example of a graph with chromatic number 3);
• The negative number of isolated nodes of G, where a isolated node is a vertex with no
neighbor. Here we take the negative number because the number of isolated nodes is
non-decreasing under the addition of edges (see Figure 1 (e) for an example of a graph
with 5 isolated nodes);

5

(a) 5-star

(b) 5-chain

(c) 5-clique

(d) 3-colorable

(e) 5 isolated nodes

(f) girth 5

(g) 2-connected

(h) matching

(i) planar

(j) bipartite

Figure 1: Examples of graph invariants and properties.
• The negative girth of G, where the girth of a graph is the length of the shortest cycle
and the girth equals infinity when G has no cycle. We take the negative girth also
because the girth itself is non-increasing when adding edges (see Figure 1 (f) for an
example of a graph with girth 5);
• The negative number of connected subgraphs of G, where a subgraph is connected if
any pair of its vertices are connected by a chain (see Figure 1 (g) for an example of
a graph with connected subgraphs). Notice that the number of connected subgraphs
is again non-increasing under the addition of edges and thus the negative number of
connected subgraphs is monotone.
In the last three examples of monotone invariants listed above, we consider the negative
values as more natural quantities. The negative sign is introduced since the invariants –
number of isolated nodes, girth and number of connected subgraphs are non-increasing under
the addition of edges, i.e., they are “monotone decreasing” instead of monotone increasing.
In order to unify our methodology, we focus only on monotone increasing invariants in this
paper. Any monotone decreasing invariant, can be simply converted to a monotone increasing
one by taking its negative value.
Any graph invariant I, induces a graph property PI,k defined as PI,k (G) = 0 if I(G) ≤ k
and PI,k (G) = 1 if I(G) > k. It is easy to see that PI,k is a monotone graph property if I is
monotone. For example, when I is the chromatic number, the induced property PI,k (G) = 0
if and only if G is k-colorable, which means we can assign each vertex a color from k colors
such that no two adjacent vertices share the same color, and in particular, PI,2 (G) = 0 if
and only if G is bipartite1 . See Figure 1(e) for an example of a 3-colorable graph and Figure
1(j) for an example of a bipartite graph. Another example is when I is the negative girth.
1

Recall that a bipartite graph is a graph whose vertices can be separated into two disjoint sets so that
every edge connects vertices from one set to another.

6

The induced property PI,−∞ (G) = 0 if and only if G is a forest and the induced property
PI,−4 (G) = 0 if and only if G is triangle-free.
Therefore, the above examples of monotone invariants naturally imply corresponding
examples of monotone properties. In addition to these natural examples, we also have the
following examples of monotone properties:
• G has a perfect matching, i.e. G has a subset of edges without common vertices such
that each vertex of G is an endpoint of one of these edges (see Figure 1(h) for an
example of a graph having perfect matching);
• G is not planar, where a graph is planar if it can be drawn on the plane in such a
way so that its edges only intersect at the vertices of the graph (see Figure 1(i) for an
example of a planar graph);
• G has a subgraph which is isomorphic to a given graph H.
The last property can actually derive a family of monotone graph properties given different
subgraph pattern H. If the given graph H is a k-star, the last property becomes the property
that G contains a star of size equal to or larger than k, which is equivalent to the induced
property PI,k when I is the maximum degree. Similarly, we can also set H to be a chain of
size k or a clique of size k which corresponds to the induced property PI,k for I to be the size
of the longest chain or the size of the largest clique. Another example is when H is a graph
with d/2 disjoint edges, which is equivalent to the existence of perfect matching. We visualize
the aforementioned examples of H’s with the red edges in Figures 1(a) - 1(d) and 1(h).

3

Inferential Methods for Graph Invariants

In this section, we introduce the general framework for testing nested hypotheses for monotone
graph invariants and then derive confidence intervals from the tests. Theoretical results on
the validity of the tests and confidence intervals are also provided.
We begin with formulating our inferential problems on graph invariants. In order to
illustrate the main idea of our testing procedure, we focus on the Gaussian graphical model
first and discuss further extensions to other models in Section 5. Let X = (X1 , . . . , Xn )
be i.i.d. observations of the random vector X ∼ N (0, Σ). The precision matrix Θ = Σ−1
encodes the underlying conditional independence graph G = (V, E). In particular, the edge
(j, k) ∈ E if and only if Θjk 6= 0. We consider the parameter space of precision matrices
n
o
Us = Θ ∈ Rd×d λmin (Θ) ≥ 1/ρ, max kΘj k0 ≤ s, kΘk1 ≤ M .
(3.1)
j∈[d]

The above class requires the precision matrix to have at most s nonzero entries for each
column and therefore the graphs induced by such matrices have maximum degrees at most s.
We denote the range of a graph invariant I as [IL∗ , IU∗ ]. Throughout the paper, [IL∗ , IU∗ ]
usually represents the default range of a graph invariant. For example, for any graph property
7

P, the default range is [0, 1]. If I is the negative number of isolated nodes, the default range
is [−d, 0] and for I being the negative number of connected subgraphs, the range is [−d, −1].
Sometimes we may have prior knowledge on the precision matrix which can make the default
range smaller. For example, if we know that Θ ∈ Us , the range of maximum degree can be
set to [0, s]. In this paper, we mainly focus on two inferential problems on graphical models.
Let G be the graph which the graphical model is Markov with respect to. The first problem
is testing multiple hypotheses with a nested structure
H0k : I(G) ≤ k versus H1k : I(G) > k, for k ∈ [IL∗ , IU∗ ).

(3.2)

If I(G) = k ∗ , we have H0k is true for k ≥ k ∗ and H1k is true for k < k ∗ . For each k ∈ [IL∗ , IU∗ ),
we aim to propose a test ψk ∈ {0, 1} for H0k , such that the family-wise type-I error is
controlled, i.e.,


lim PI(G)=k∗ There exists a type-I error = lim PI(G)=k∗ ∃k ≥ k ∗ s.t. ψk = 1 ≤ α.
n→∞

n→∞

When an invariant is a property, since it only takes binary values, we have a special single
hypothesis on graph property
H0 : P(G) = 0 versus H1 : P(G) = 1,

where P is a monotone property of interest. We aim to propose a test ψ ∈ {0, 1} at significance
level α such that

lim PH0 ψ = 1 ≤ α.
n→∞

The second problem is constructing a confidence interval of a monotone invariant I. We aim
to construct a confidence interval [IbL , IbU ] at significance level α such that

lim P I(G) ∈ [IbL , IbU ] ≥ 1 − α.
n→∞

3.1

A Generic Skip-Down Algorithmic Framework

In this subsection, we first describe the proposed skip-down algorithm (See Algorithm 1) for
testing the hypothesis in (3.2). We then show that the same algorithm can also deliver a
valid confidence interval for the graph invariant being tested.
To describe the algorithm, we first introduce a concept called “the critical edge set”.
Intuitively, for any graph invariant I to be tested, we need to find a set of critical edges
which may potentially change the value of I. A formal definition is as follows.
Definition 3.1 (Critical edge set). For any monotone graph invariant I and an edge set
E0 ⊆ V × V , we define the critical edge set of I with respect to E0 as

CI (E0 ) := e ∈ E0c | ∃E 0 ⊇ E0 s.t. I(E 0 ) > I(E 0 \{e}) .
(3.3)
The definition of CI (E0 ) is quite abstract. To understand its intuition, we first consider a
8

Examples of E0

(a) Connectivity

(b) Max degree

(c) Singletons

(d) Acyclic

(1)

E0

(2)

E0

Figure 2: Two examples of the critical edge sets CI (E0 ) (in red edges) for (a) I is the negative
number of connected subgraphs, (b) I is the maximum degree, (c) I is the negative number
of isolated nodes, and (d) I = 0 when the graph is a forest and I = 1 otherwise. The first
(1)
(2)
row is for E0 = E0 and the second row is for the second example when E0 = E0 .
special case when I is a monotone graph property (denoted by P). As P only takes binary
values, CP (E0 ) can be equivalently written as

CP (E0 ) := e ∈ E0c | ∃E 0 ⊇ E0 s.t. P(E 0 ) = 1 and P(E 0 \{e}) = 0 .
(3.4)

An edge e is critical for P with respect to E0 , if there exits a set of edges {e1 , . . . , ek }
that do not belong to E0 ∪ {e} such that adding them to E0 makes (V, E0 ∪ {e1 , . . . , ek , e})
satisfies P but (V, {e1 , . . . , ek }) does not. This implies that e has the “potential” to change
the property of E0 through edge addition. In Figure 2, we provide examples of critical edge
sets for various invariants. From Figure 2, we see that CI (E0 ) can be strictly smaller than E0c
for some invariants. This implies that we can ignore some edges and leads to a more powerful
test. For a more detailed discussion of critical edges, see Section 3.2.
We begin by introducing the high level idea of testing the nested hypotheses in (3.2). At
first, we do not have any information on the true graph. Therefore, we test the existence
of edges in CI (∅). Suppose we have rejected edges in some edge set E0 ⊆ CI (∅), then we
can update our knowledge that E0 is a subgraph of the true graph. Since I is a monotone
invariant, we also know that I(G) ≥ I(E0 ). In the next step, we can further update our
knowledge of the true graph by testing the existence of edges in CI (E0 ). We can repeat this
procedure for multiple times and iteratively refine our knowledge on I(G).
An essential component step of the above idea is to test the existence of a certain edge set
b d and a (1 − α) quantile
E. This can be achieved by a generic precision matrix estimator Θ
√ bd
estimator c(α, E) for the statistic TE = maxe∈E n(Θe − Θe ) given any edge set E ⊆ V × V
satisfying


√
b d − Θe ) > c(α, E) − α = 0.
lim sup P max n(Θ
(3.5)
n→∞ Θ∈Us

e∈E

e

b d and c(α, E) satisfying (3.5) in Section 5.
We will provide concrete examples of Θ
9

Algorithm 1 Skip-Down Method for Inferring Graph Invariant I
b d }e∈V ×V and the range [I ∗ , I ∗ ].
Input: {Θ
e
L U
Initialize t = 0, E0 = ∅ and the interval [IbL , IbU ] = [IL∗ , IU∗ ].
repeat
t ← t + 1;
Select the screening set: A ← CI (Et−1 );

√
b d | > c(α, A) ;
Update the rejected set: Et ← Et−1 ∪ e ∈ A | n · |Θ
e
∗
b
b
Update the interval [IL , IU ] ← [I(Et ), IU ];
until I(Et ) ≥ IU∗ or Et = Et−1
Output:
• Nested hypotheses: Let IbL = min(max(I(Et ), IL∗ ), IU∗ ). At the significance level α, we
reject H0k for k < IbL and not reject H0k for k ∈ [IbL , IU∗ ].
• Confidence interval: The 1 − α confidence interval [IbL , IU∗ ].

Algorithm 1 implements the high level idea above to test hypotheses in (3.2) and construct
a confidence interval for the monotone invariant I. We call this algorithm the skip-down
method. The skip-down method is motivated by the step-down method (Romano and Wolf,
2005), which is designed for controlling the family-wise error of general multiple hypothesis
tests. Our skip-down method explicitly exploits the nested structure of multiple hypotheses
and has stronger power. Particularly, in each step, the step-down method tests all hypotheses
which have not been previously rejected, while the skip-down method “skips” edges not
belonging to the critical edge set, and hence improves the power of the test.
To construct confidence intervals, we choose the lower side as IbL in Algorithm 1 while the
upper side is simply chosen to be IU∗ . This asymmetry is due to the monotonicity of graph
invariants. In fact, we cannot construct a better upper bound for maximum degree according
to the following theorem.

Theorem 3.1. Denote IDeg (G) as the maximum degree of G. Define the family of confidence
upper bound of IDeg as

b (·) : Rd×n → [0, s]
U (IDeg , α) = U


b (X) ≥ 1 − α .
inf PΘ I(Θ) ≤ U

Θ∈Us

(3.6)

p

Let Us (θ) = Θ ∈ Us mine∈E(Θ) |Θe | ≥ θ . If s = o(d1/2 ) and θ ≤ C log d/n for some
sufficiently small positive constant C, we have


b − IDeg (Θ) ≥ s(1 − α).
lim inf
inf
sup EΘ U
(3.7)
n→∞ U
b ∈U (IDeg ,α) Θ∈Us (θ)

b = s with probability 1−α
We can achieve the lower bound (3.7) by a naive upper bound U
b = 0 with probability α. Theorem 3.1 explains why we simply choose the confidence
and U
upper bound to be IU∗ for maximum degree. Similar results hold for many other invariant, we
refer to Theorems 4.3 for details.
10

Since graph properties are a special type of graph invariants with range [0, 1], Algorithm 1
b d }e∈V ×V and
induces a test for H0 : P(G) = 0 versus H1 : P(G) = 1. Using the input {Θ
e
the range [0, 1] for Algorithm 1, we construct the test at a significance level α as ψα = 0 if
the output IbL = 0 and ψα = 1 otherwise. Following this idea, Algorithm 2 summarizes the
procedure for testing graph properties.
An important step in the implementation of Algorithms 1 and 2 is scanning through
the critical edge set CI (E0 ) for any given E0 . One general procedure for doing this is to
exhaustively search all edges in CI (E0 ). Specifically, for all edge set E 0 ⊇ E0 , we search for
every edge e ∈ E 0 \E0 and if I(E 0 ) > I(E 0 \{e}), we add the edge e into CI (E0 ). Although this
is a valid procedure for any monotone invariant or property, the computational complexity is
exponential to the dimension. On the other hand, for many specific invariants and properties,
the structure of CI (E0 ) is simple and fast algorithms finding CI (E0 ) exist. In Section 3.2,
we will give specific algorithms for finding the critical edge sets for three invariants and one
property: the maximum degree, the negative number of isolated nodes, the negative number
of connected subgraphs and the property that a graph is not a forest.
Algorithm 2 Skip-Down Method for Testing a Graph Property P
b d }e∈V ×V
Input: {Θ
e
Initialize t = 0, E0 = ∅.
repeat
t ← t + 1;
Select the screening set: A ← CP (Et−1 );
√
b d | > c(α, A)};
Update the rejected set: Et ← Et−1 ∪ {e ∈ A | n · |Θ
e
until P(Et ) = 1 or Et = Et−1
Output: ψα = 0 if P(Et ) = 0 and ψα = 1 otherwise.

3.2

Case Study for Skip-Down Algorithm

In this section, we provide examples of graph invariants and show how to implement the
skip-down algorithm for testing nested hypotheses and constructing confidence intervals of
the following graph invariants:
• IConn (G) = the negative number of connected subgraphs of G;
• IDeg (G) = the maximum degree of G;
• IIso (G) = the negative number of isolated nodes of G.
Recall that the induced graph property PI,k (G) = 0 if I(G) ≤ k and PI,k (G) = 1 if I(G) > k.
The above four invariants therefore naturally induce the following properties:
• PConn,−k (G) = 1 if and only if G has less than k connected subgraphs;
11

• PDeg,k (G) = 1 if and only if G has maximum degree larger than k;
• PSig,−k (G) = 1 if and only if G has less than k isolated nodes.
We also consider a fourth example of graph property:
• PCycle (G) = 0 if and only if G is a forest.
In order to apply Algorithms 1 and 2 for the above invariants and properties, there are
two important steps; we need to first specify critical edge set CI (E0 ) given any edge set E0 ,
and second to calculate the invariant for any given graph. The second step can directly
utilize existing algorithms for deterministic graphs. As mentioned previously, the critical
edge set can be found via exhaustive search but the computation is not efficient in general.
However, for the examples we give above, the critical edge sets can be selected explicitly. In
the following proposition, we show the explicit forms of the critical edge sets for the above
four properties.
Proposition 3.2 (Critical edge sets for induced properties). Given any graph G0 = (V, E0 ),
we have the following concrete forms of the critical edge sets.
0

• Connected subgraphs. Denote all connected subgraphs of G0 by {G0` = (V0` , E0` )}k`=1 .
If PConn,−k (G0 ) = 1, i.e., k 0 < k, we have CPConn,−k (E0 ) = ∅, otherwise

CPConn,−k (E0 ) = (u, v) ∈ E0c u ∈ V0` , v ∈ V0`0 , ` 6= `0 .
(3.8)
Thus the critical edge set consists of all edges that link the connected subgraphs of G0 .

• Maximum degree. If PDeg,k (G0 ) = 1, i.e., the maximum degree of G0 is larger than
k, we have CPDeg,k (E0 ) = ∅, otherwise CPDeg,k (E0 ) = E0c .
• Singletons. Denote the set of all isolated nodes of G0 by VSig . If PSig,−k (G0 ) = 1, i.e.,
|VSig | < k, we have CPSig,−k (E0 ) = ∅, otherwise
CPSig,−k (E0 ) = {(u, v) ∈ E0c | u ∈ VSig or v ∈ VSig }.

(3.9)

Therefore, the critical edge set contains the edges that connect the isolated nodes.
• Acyclic. If PCycle (G) = 1, we have CPCycle (E0 ) = ∅, otherwise when G0 is a forest,
CPCycle (E0 ) = E0c .
The critical edge set for an invariant can be obtained from the one of its induced property.
In fact, there exists a direct connection between the critical edge set of an invariant and its
induced property:
∗
IU
[
CI (E0 ) =
CPI,k (E0 ).
(3.10)
∗
k=IL

12

V
Ct
Et−1
t=1

t=2

t=3

t=4

Figure 3: An example of Algorithm 3 for IConn from the 1st to 4th iteration. The blue dashed
circles are the connected node sets V, the red edges are the critical edge set Ct and the black
edges are Et−1 . In the 4th iteration, since |V| = 1, we stop the algorithm.
This can be directly derived from Definition 3.1. On the one hand, for any e ∈ CI (E0 ),
there exists E 0 ⊇ E0 such that I(E 0 ) > I(E 0 \{e}), therefore e ∈ CPI,I(E0 \{e}) (E0 ) by (3.4).
On the other hand, if e ∈ CPI,k0 (E0 ) for some k0 ∈ [IL∗ , IU∗ ], by (3.4) and the definition of
induced property, there exists E 0 ⊇ E0 such that I(E 0 ) > k0 ≥ I(E 0 \{e}), which implies
that e ∈ CI (E0 ). Therefore, by (3.10), we have a corollary of Proposition 3.2 on the critical
edge set of invariants.
Corollary 3.3 (Critical edge sets for invariants). Given a graph G0 = (V, E0 ), as in Proposi0
tion 3.2, we denote all the connected subgraphs of G0 as {G0` = (V0` , E0` )}k`=1 and all the set
of isolated nodes of G0 as VSig . The critical edge sets for the four invariants are as follows.

• Connected subgraphs: CIConn (E0 ) = (u, v) ∈ E0c u ∈ V0` , v ∈ V0`0 , ` 6= `0 ;
• Maximum degree: CIDeg (E0 ) = E0c ;

• Singletons: CIIso (E0 ) = {(u, v) ∈ E0c | u ∈ VSig or v ∈ VSig }.
The examples of the critical edges for invariants are visualized in Figure 2. Having the
explicit forms of critical edge sets, we are now ready to implement Algorithms 1 and 2 for
the above examples.
Example 3.1 (Number of connected subgraphs). By Corollary 3.3, we need to partition the
node set V into disjoint connected node sets V = {V1 , V2 , . . . , Vk0 } representing connected
subgraphs in each iteration. We update the connected node sets V1 , V2 , . . . , Vk0 in each iteration
of skip-down algorithm as follows. If an edge (u, v) is rejected and u ∈ V1 and v ∈ V2 , we
take the union of V1 and V2 and update the connected node sets as V = {V1 ∪ V2 , V3 , . . . , Vk0 }.
A detailed description of the algorithm for the confidence interval of IConn with a default
range [−d, −1] is shown in Algorithm 3. We visualize the algorithm in Figure 3. Similarly,
we can also test PConn,−k by modifying Algorithm 3.
Example 3.2 (Maximum degree). According to Corollary 3.3, the critical edge set is
simply the complement of the rejected edge set. Therefore, for IDeg , in the t-th iteration
c
of Algorithm 1, we select the screening set A = Et−1
. In order to obtain I(Et ), we can
directly count the maximal number of neighbors for each node. Therefore, the algorithm
for maximum degree confidence interval can directly implement Algorithm 1 by plugging in
13

Algorithm 3 Skip-Down Method for IConn
b d }e∈V ×V .
Input: {Θ
e
Initialize t = 0, E0 = ∅ and connected node sets V = {{1}, . . . , {d}}.
repeat
t ← t + 1;

c
Find the critical edge set Ct = (u, v) ∈ Et−1
u ∈ S, v ∈ T, S 6= T and S, T ∈ V .
√
b d | > c(α, Ct )};
Update the rejected set: Rt = {e ∈ Ct | n · |Θ
e
Et ← Et−1 ∪ Rt ;
Update the connected node sets V:
for (u, v) ∈ Rt do
if u, v belong to different node sets S, T in V, i.e., u ∈ S, v ∈ T and S 6= T then
V ← (V\{S, T }) ∪ {S ∪ T }
end if
end for
until |V| = 1 or Rt = ∅
Output:
• Nested hypotheses: We reject H0k for k < −|V| and not reject H0k for k ∈ [−|V|, −1].
• Confidence interval: The 1 − 2α confidence interval [IbL , IbU ], where IbL = −|V| and
IbU = −1 with probability 1 − α and IbU = −|V| with probability α.
c
the explicit forms of A = Et−1
and I(Et ). Similar methods can be applied to test PDeg,k by
plugging in the set CPDeg,k (E0 ) defined in Proposition 3.2 into Algorithm 2.

Example 3.3 (Singletons). The critical edge set for CISig,−k (E0 ) is shown in (3.9). It is
apparent from this explicit form that we need to keep the track of the set of isolated nodes
for each iteration. If an edge (u, v) is rejected, we simply delete u and v from the set of
isolated nodes if they belong to the set. A detailed description of step-down algorithm for
ISig,−k with a default range [−d, 0] is shown in Algorithm 4.
Example 3.4 (Acyclic graph). The critical edge set is also the complement of the rejected
edge set for the cyclicity property. Similarly to the maximum degree test, in the tth iteration,
c
we also select the screening set A = Et−1
. The procedure for checking whether Et ∈ PCycle ,
i.e., Et is contains a cycle is similar the one of detecting connectivity in Example 3.1. A
detailed implementation of the test is shown in Algorithm 5.

4

Theory of Skip-down Method

In this section, we first prove the validity of obtained tests and confidence intervals described
in Algorithm 1. We then show the optimality of the length of the confidence intervals for a
family of monotone invariants. We show that the length of the confidence interval is adaptive
to the signal strength.
14

Algorithm 4 Skip-Down Method for IIso
b d }e∈V ×V .
Input: {Θ
e
Initialize t = 0, E0 = ∅ and isolated node set VSig = {1, . . . , d}.
repeat
t ← t + 1;

c
Find the critical edge set Ct = (u, v) ∈ Et−1
u ∈ VSig or v ∈ VSig .
√
b d | > c(α, Ct )};
Update the rejected set: Rt = {e ∈ Ct | n · |Θ
e
Et ← Et−1 ∪ Rt ;
Update the connected node sets VSig :
for (u, v) ∈ Rt do
VSig ← VSig \{u, v};
end for
until |VSig | = 0 or Rt = ∅
Output:
• Nested hypotheses: We reject H0k for k < −|VSig | and not reject H0k for k ∈ [−|V|, 0].
• Confidence interval: The 1 − 2α confidence interval [IbL , IbU ], where IbL = −|VSig | and
IbU = 0 with probability 1 − α and IbU = −|VSig | with probability α.

4.1

Validity of Tests and Confidence Intervals

Given the precision matrix Θ, recall that G(Θ) is the graph induced by the support of Θ.
We also use the shorthand I(Θ) = I(G(Θ)) for the corresponding invariant for G(Θ) and
similarly put P(Θ) = P(G(Θ)) for the corresponding property. Given a graph invariant I,
we define the parameter space

Us (IL∗ , IU∗ ) = Θ ∈ Us | I(Θ) ∈ [IL∗ , IU∗ ] .
Here we assume IL∗ and IU∗ are known.
The following theorem shows the family-wise error of nested hypotheses and the asymptotic
coverage probability of the confidence interval given by the skip-down method in Algorithm 1.

Theorem 4.1 (Asymptotic coverage probability). Suppose Θ ∈ Us and (3.5) is satisfied.
Given any monotone invariant I, the multiple test given by Algorithm 1 has

lim sup
sup
PΘ ∃k ≥ I(Θ) such that H0k is rejected ≤ α,
(4.1)
n→∞

∗ ,I ∗ )
Θ∈Us (IL
U

and the confidence interval [IbL , IU∗ ] satisfies
lim inf
n→∞

inf∗

∗)
Θ∈Us (IL ,IU


PΘ I(Θ) ∈ [IbL , IU∗ ] ≥ 1 − α.

(4.2)

Since graph properties are a special types of graph invariants, Theorem 4.1 actually
implies the validity of the test ψα in Algorithm 2.
15

Algorithm 5 Skip-Down Method for PCycle
b d }e∈V ×V .
Input: {Θ
e
Initialize t = 0, E0 = ∅ and path node sets VPaths = {{1}, . . . , {d}}.
repeat
t ← t + 1;
√
b d | > c(α, E c )};
Update the rejected set: Rt = {e ∈ Etc | n · |Θ
e
t
Et ← Et−1 ∪ Rt ;
Detect the cycles in the graph:
for (u, v) ∈ Rt do
if u, v belong to different node sets S, T in VPaths , i.e., u ∈ S, v ∈ T and S 6= T then
VPaths ← (VPaths \{S, T }) ∪ {S ∪ T }
else
VPaths ← ∅, Break;
end if
end for
until Rt = ∅
Output: ψα = 0 if VPaths 6= ∅ and ψα = 1 otherwise.
Corollary 4.2 (Uniform asymptotic validitiy). Given any monotone property P, we define
the parameter space

(4.3)
G0 := Θ ∈ Us P(Θ) = 0 .
Under the same conditions of Theorem 4.1, the test ψα given by Algorithm 2 has
lim inf inf PΘ (ψα = 0) ≥ 1 − α.
n→∞ Θ∈G0

(4.4)

Both results of Theorem 4.1 and Corollary 4.2 are uniform over the parameter space
Us (IL∗ , IU∗ ). Besides, the parameter space Us (IL∗ , IU∗ ) does not impose any restriction on the
signal strength. The signal strength assumption is usually required to obtain a consistent
b
graph estimator (Ravikumar et al., 2011; Cai et al., 2011; Liu et al., 2012b), such that G
b = G) → 1 as n → ∞. The consistency of graph recovery has been shown for
satisfies P(G
many graphical model estimators including CLIME (Cai et al., 2011), neighborhood selection
(Meinshausen and Bühlmann, 2006; Zhou et al., 2009), graphical Lasso (Lam and Fan, 2009)
and transellipitical graphical model (Liu et al., 2012b) and all these results need the minimal
b there is a plug-in invariant
signal strength condition. Given any consistent graph estimator G,
b
b
estimator I(G) such that P(I(G) = I(G)) → 1. Similarly, to test the properties, one can also
b In comparison with the plug-in methods, the confidence
construct a plug-in test ψ := P(G).
intervals and tests obtained by Algorithms 1 and 2 have two major advantages: (1) they do
not require any signal strength conditions and (2) one can choose different significance levels
and thus have controllable uncertainty assessment for our inferential procedures.
Neykov et al. (2016) propose a data-splitting method to test the graph properties. Their
method splits the data into two disjoint parts D1 and D2 . The method uses the first data
16

b 1 ) and order the estimators |Θ
b [1] | ≥ . . . ≥
split D1 to estimate the inverse covariance Θ(D
b [d(d−1)/2] |. It adds the edges from the largest to the smallest until they detect witness
|Θ
b for the property. For example, for the property that a graph has maximum degree
pattern E
b is the first star of size k + 1. The method then applies the
larger than k, the pattern E
b If
step-down algorithm on the second data split D2 to test on the existence of edges in E.
b are rejected, the method rejects the hypothesis and does not reject otherwise.
all edges in E
Compared to the data splitting test proposed in Neykov et al. (2016), the skip-down algorithm
has three advantages. First, it is a data-driven procedure without any pre-specified value of
a graph invariant to be tested. Second, it is a unified procedure valid for all monotone graph
invariants, which are non-decreasing under edge addition, while the data splitting method
needs to consider different invariants case by case. Third, the data splitting method needs
the first split to screen the critical edge set and conducts the tests on the critical edge set by
the second split. In comparison, the skip-down algorithm avoids data splitting and conducts
both screening and inference using the entire dataset.

4.2

Optimality and Adaptivity of the Confidence Intervals

Theorem 4.1 proves that the confidence intervals [IbL , IU∗ ] constructed by Algorithm 1 is
asymptotically honest uniformly over the parameter space Us (IL∗ , IU∗ ). In this subsection, we
show that the averaged length of confidence interval obtained in Algorithm 1 is optimal in
the minimax sense.
Define a parameter space with minimal signal strength θ as
n
o
UI (IL∗ , IU∗ ; θ) = Θ ∈ Us I(Θ) ∈ [IL∗ , IU∗ ], min |Θe | ≥ θ .
(4.5)
e∈E(Θ)

Let the family of confidence upper bound of I be
n
b (·) : Rd×n → [I ∗ , I ∗ ]
inf∗
U (I, α) = U
L U

∗)
Θ∈Us (IL ,IU

PΘ

o

b
I(Θ) ≤ U (X) ≥ 1 − α .

Theorem 3.1 shows we cannot construct non-trivial confidence upper bound for maximum
degree. The following theorem shows that a similar result holds for IConn and IIIso as well.

Theorem 4.3 (Lower
bound of confidence upper bounds). Suppose IL∗ ≥ d/2 and IU∗ − IL∗ =
p
o(d1/2 ). If θ ≤ C log d/n for some sufficiently small positive constant C, we have
lim inf

inf

sup

n→∞ U
b ∈U (I,α) Θ∈UI (I ∗ ,I ∗ ;θ)
L U

for I = IConn or I = IIso .



b − I(Θ) ≥ (I ∗ − I ∗ )(1 − α),
EΘ U
U
L

(4.6)

Similar to Theorem 3.1, the lower bound in (4.6) can be achieved by a naive upper
b = I ∗ with probability 1 − α and U
b = I ∗ with probability α. This explains why in
side U
U
L
Algorithm 1, we only simply choose the upper bound as IU∗ . For the result of generic invariant
confidence upper bound, we refer to Theorem 6.2.
17

Although we cannot construct a non-trivial confidence upper bound for many invariants,
we can still construct good enough confidence intervals. Define the family of honest confidence
intervals as
n
o

b U
b ] L(X)
b
b (X) a.s.,
b
b (X)] ≥ 1−α . (4.7)
I(I, α) = [L,
≤U
inf∗ ∗ PΘ I(Θ) ∈ [L(X),
U
Θ∈Us (IL ,IU )

The following theorem gives the lower bounds of confidence interval length for I = IDeg ,
IConn and IIso .
Theorem 4.4 (Lower bound of confidence intervals). Given a precision matrix Θ ∈
UI (IL∗ , IU∗ ; θ), we define its significant edge set as
p

ESig (Θ) := (j, k) | |Θjk | ≥ C log d/n ,
where C is some sufficiently large constant. We then define the oracle length as

For I = IDeg , IConn
C 0 , we have

Oracle Length(Θ) = IU∗ − I(ESig (Θ)).
(4.8)
p
or IIso , if θ ≤ C 0 log d/n for some sufficiently small positive constant



b −L
b
EΘ U
≥ 1 − 2α.
lim inf
inf
sup
n→∞ [L,
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ) Oracle Length(Θ)
L U

(4.9)

By the definition in (4.8), Oracle Length(Θ)
becomes smaller, if there are more entries in
p
Θ with signal strength larger than C log d/n. Namely, the oracle length is adaptive to the
number of edges to strong signal strength. Therefore, (4.9) implies that the lower bound of
the confidence interval length is adaptive to the significant edge set ESig (Θ). For the lower
bound of generic invariants, we refer to Theorem 6.1 in Section 6.
From (4.9), it is straightforward to derive that


b −L
b ≥ (1 − 2α)(IU∗ − IL∗ ).
lim inf
inf
sup
EΘ U
n→∞ [L,
bU
b ]∈I(I,α) Θ∈UI (I ∗ ,I ∗ ;θ)
L U

This implies that if there is no edge with strong enough signal strength, we only have a trivial
rate O(IU∗ − IL∗ ) for the confidence interval length.
Now we discuss the upper bound the confidence interval length from Algorithm 1. The
following theorem shows that it achieves the lower bound in Theorem 4.4.

Theorem 4.5 (Size of confidence interval). Suppose Θ ∈ Us and (3.5) is satisfied. For any
monotone invariant I with range [IL∗ , IU∗ ], if IU∗ − IL∗ = O(d2 ), for any α ∈ (0, 1) and θ > 0,


EΘ IbU − IbL
lim
sup
≤ 1.
n→∞ Θ∈U (I ∗ ,I ∗ ;θ) Oracle Length(Θ) + 1
I L U

(4.10)

We add one in the denominator Oracle Length(Θ) + 1 of (4.10) just to avoid singularity
18

when IU∗ = I(ESig (Θ)). We can see that the length is adaptive to the value I(ESig (Θ)).
As we argued above, the oracle length in (4.10) shows the first level of adaptivity for the
skip-down algorithm: the length of our confidence interval is smaller if there are more edges
with strong enough signal strength. The assumption that IU∗ − IL∗ = O(d2 ) is satisfied for all
examples in Section 2. In fact, this assumption is mild in the sense that for monotone I, there
are at most d(d − 1)/2 possible values and we can easily rescale I such that IU∗ − IL∗ = O(d2 ).
Theorem 4.3 shows that it is impossible to construct an adaptive upper side of confidence
interval. In fact, the following theorem shows that the oracle length in (4.10) mainly comes
from the lower side.
Theorem 4.6 (Size of confidence lower bound). Suppose Θ ∈ Us . If (3.5) is satisfied, for
any monotone invariant I with range [IL∗ , IU∗ ], if IU∗ − IL∗ = O(d2 ), for any α ∈ (0, 1) and
θ > 0, we have


EΘ I(Θ) − IbL
lim
sup
≤ 1.
(4.11)
n→∞ Θ∈U (I ∗ ,I ∗ ;θ) I(Θ) − I(ESig (Θ)) + 1
I L U
Similar to (4.10), we add one in the denominator IU∗ − I(ESig (Θ)) + 1 of (4.11) just to
avoid singularity. We remark that (4.11) also gives the type II error analysis for nested
hypotheses in (3.2). In Algorithm 1, we do not reject H0k for k ∈ [IbL , IU∗ ], thus the number
of type II errors is max{I(Θ) − IbL , 0}. In fact, the proof of Theorem 4.6 shows that the
expected number of type II errors has


lim EΘ I(Θ) − IbL ≤ I(Θ) − I(ESig (Θ)).
n→∞

Therefore, when the minimal signal strength satisfies min(j,k)∈E |Θjk | ≥ C
sufficiently large C, there is asymptotically no type II error.

5

p
log d/n for

Extension to Non-Gaussian Graphical Models

In this section, we show that the skip-down method for nested hypotheses and confidence
intervals can be applied to a general family of graphical models and estimators.
We first introduce a few notations for general graphical models. We say a symmetric
matrix Ω is an interaction matrix for a graphical model Markov to graph G∗ = (V, E ∗ ), if
for any two different j, k ∈ V , Ωjk = 0 if and only if (j, k) 6∈ E ∗ . For the Gaussian graphical
model, the precision matrix Θ is an interaction matrix by definition. For Gaussian copula
graphical model (Liu et al., 2012a; Xue and Zou, 2012) and the transelliptical graphical
model (Liu et al., 2012b), the interaction matrix can be the latent correlation matrix. For
the semiparametric exponential family graphical model (Yang et al., 2014b), the interaction
matrix can be the interactive parameters in the canonical form.
In the skip-down algorithm for Gaussian graphical model in Algorithm 1, we only use
b d in the step of updating the rejected edge
the debiased precision matrix estimators Θ
19

set. In fact, for general graphical models, it suffices to validate Algorithm 1 if we can
b d for the interaction matrix such that the quantile of statistic
construct some
Ω
√ bestimator
max(j,k)∈E n(Ωdjk − Ωjk ) can be well estimated for any edge set E ⊆ V × V . In specific, we
have the following theorem for general graphical models.

Theorem 5.1. Let Ω be an interaction matrix for a graphical model. Suppose there
b d and a quantile estimator c(α, E) for the statistic
exist an interaction matrix estimator Ω
√ bd
max(j,k)∈E n(Ωjk − Ωjk ) given any edge set E ⊆ V × V satisfying


√
b d − Ωe ) > c(α, E) − α = 0.
lim sup PΩ max n(Ω
e

n→∞ Ω∈Us

e∈E

b d and c(α, E) into Algorithm 1,
For any monotone invariant I, if we plug such estimators Ω
the output test is honest, i.e.,

lim sup
sup
PΩ ∃k ≥ I(Ω) such that H0k is rejected ≤ α,
(5.1)
n→∞

∗ ,I ∗ )
Ω∈Us (IL
U

and the output confidence interval [IbL , IU∗ ] satisfies
lim inf
n→∞

inf∗

∗)
Ω∈Us (IL ,IU


PΩ I(Ω) ∈ [IbL , IU∗ ] ≥ 1 − α.

(5.2)

The above theorem generalizes Theorem 4.1 to non-Gaussian graphical models. In fact,
it provides a sufficient condition (3.5) to guarantee that the test and confidence interval
achieved from Algorithm 1. In fact, after applying a debiasing step, (3.5) is satisfied for many
estimators for Gaussian graphical model as long as non-Gaussian graphical models including
Gaussian copula graphical model, transelliptical graphical model, semiparametric exponential
family graphical model and so on. For the details of debiasing step and approaching (3.5),
we refer Section S.5 in the appendix.

6

A Generic Framework of Lower Bounds

In this section, we show the lower bound of the confidence interval length for a generic family
of invariants characterized by a concept called “hollow graphs”, whose formal definition is
given below.
Definition 6.1 (Hollow graph). A graph G = (V, E) is called R-hollow, if
max

∅6=F ⊆E

|F |
≤ R.
|V (F )| − 1

(6.1)

The quantity R in (6.1) measures the maximal “density” of edges. A k-clique is k-hollow
as the edges are fully connected and a k-chain is (1 − 1/k)-hollow as it is relatively sparse.
Therefore, we can see that any graph with maximal degree s is at most s-hollow. Definition
20

6.1 is a classical definition proposed by Nash-Williams (1964). If a graph is R-hollow for
some constant R independent of the graph size, we say the graph is hollow.
Before presenting the theorem on the lower bound, we introduce a few notations on the
graph. The maximum degree of a graph G = (V, E) is denoted by dmax (G). The union of two
graphs G1 = (V, E1 ) and G2 = (V, E2 ) is G1 ∪ G2 := (V, E1 ∪ E2 ). We say G0 = (V, E 0 ) is an
isomorphic copy of G = (V, E) if G0 is isomorphic to G and V (E 0 ) ∩ V (E) = ∅. Furthermore,
we say G1 , . . . , GN are different isomorphic copies of G if each Gj is an isomorphic copy of G
and V (Ej ) ∩ V (Ej 0 ) = ∅ for any 1 ≤ j 6= j 0 ≤ N .
Now we briefly explain the intuition behind the proof of the lower bound of confidence
interval length. Given an invariant I, the idea of the proof is to reduce the problem to a lower
bound in a certain hypothesis test (Cai and Guo, 2015). In order to obtain sharp bounds,
we compare a graph with invariant equal to IL∗ with multiple graphs with invariant equal to
IU∗ . The construction of the alternative graphs with invariant IU∗ relies on the existence of
isomorphic copies of a certain graph.
Theorem 6.1 (Lower bound of confidence interval length). Given any monotone invariant
I in the range [IL∗ , IU∗ ], suppose there exist two graphs GL = (V, EL ) and GU = (V, EU ) with
GL  GU and they satisfy |V (EL )| = O(1), |V (EU )| = o(d1/2 ) and GU is hollow. Given some
N satisfying d1/2 ≤ N ≤ d/(2|V (EL )|), we assume there exist N different isomorphic copies
of GL denoted as GL,1 , . . . , GL,N such that
∗
N
∗
I(∪N
j=1 GL,j ∪ GL ) = IL and I(∪j=1 GL,j ∪ GU ) = IU .

If there exist constants C1 and C2 such that
p
p
θ ≤ C1 log d/n and dmax (GU ) log d/n ≤ C2 ,

we have the following lower bound on the confidence interval length


b −L
b
EΘ U
lim inf
inf
sup
≥ 1 − 2α,
n→∞ [L,
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ) Oracle Length(Θ)
L U

(6.2)

(6.3)

(6.4)

where Oracle Length(Θ) is defined in (4.8).

We now sketch the high level idea behind the proof of Theorem 6.1. The first step reduces
the minimax result in (6.4) to a lower bound of testing H0 : I(Θ) = IL∗ versus H1 : I(Θ) = IU∗ .
Next we further reduce the above test to the test H0 : Θ = Θ0 versus H1 : Θ ∈ {Θ1 , . . . , ΘM },
where I(Θ0 ) = IL∗ and I(Θj ) = IL∗ for 1 ≤ j ≤ M . In order to obtain sharp bounds one
needs to construct a maximally challenging set of matrices {Θ0 , Θ1 , . . . , ΘM } for hypothesis
test. Condition (6.2) enables our construction. We choose a Θ0 with G(Θ0 ) = ∪N
j=1 GL,j ∪ GL
and select Θ1 , . . . , ΘM so that each G(Θj ) for 1 ≤ j ≤ M is isomorphic to ∪N
j=1 GL,j ∪ GU .
N
The reason the graph ∪j=1 GL,j ∪ GU is used is to reproduce multiple isomorphic G(Θj )’s in
the alternative which makes it challenging to tell them from the graph G(Θ0 ) under the null.
Assumptions on the sizes of GL and GU , as well as the range of N are imposed to ensure
21

!!!!!!!!!!"#!!!!!!!!!$

!!! ! ! ! "#!! ! ! ! $
EU

IU

IL

···

EU

!!! ! !"#!! ! !$ !!!!!!!!!!"#!!!!!!!!!$

IU

IL

IU

IU

IL

EU
EL

EL

G1

···

EL

G1

GN

(a) IDeg

···

GN

(b) IConn

G1

···

GN

(c) IIso

Figure 4: A visualization of a construction satisfying the conditions of Theorem 6.1 for the
invariants I: (a) the maximum degree, (b) the negative number of connected subgraphs and
(c) the negative number of isolated nodes.
the existence of sufficiently many graphs in the alternative. The second condition of (6.3)
guarantees
the positive definiteness of the precision matrix. It is satisfied when the condition
p
s log d/n = o(1) holds.
The following theorem gives a generic lower bound of confidence upper bound, i.e., the
right endpoint of the confidence interval.
Theorem 6.2 (Negative result of confidence upper bound). Given any monotone invariant I
in the range [IL∗ , IU∗ ]. Under the same conditions as Theorem 6.1, if (6.3) is satisfied, we have
lim inf

inf

sup

n→∞ U
b ∈U (I,α) Θ∈UI (I ∗ ,I ∗ ;θ)
L U



b − I(Θ) ≥ (I ∗ − I ∗ )(1 − α).
EΘ U
U
L

(6.5)

In the final part of this section, we give concrete examples of invariants satisfying the
conditions of Theorem 6.1. Specifically, the following examples show how to derive Theorems
4.3 and 4.4 from Theorems 6.1 and 6.2.
Example 6.1. The maximum degree IDeg satisfies the conditions of Theorem 6.1 for IL∗ =
O(1) and IU∗ = o(d1/2 ). We visualize the construction in Figure 4(a). We let GL be an
IL∗ -star and GU be an IU∗ -star. By definition we immediately have that GU is hollow. Since
IU∗ = o(d1/2 ) and IL∗ = O(1), we have |V (EL )| = O(1) and |V (EU )| = o(d1/2 ). We let
N = d/(2(IL∗ + 1)) = Ω(d1/2 ) and reproduce N different isomorphic copies of the IL∗ -star, as
GL,1 , . . . , GL,N shown in Figure 4(a). One can easily verify that this construction satisfies
(6.2).
Example 6.2. The negative number of connected subgraphs IConn satisfies the conditions
of Theorem 6.1 for any pair of IL∗ and IU∗ such that IL∗ = −bγdc for some γ ∈ (1/2, 1]
and IU∗ − IL∗ = o(d1/2 ). We let GL be a 1/(2γ − 1)-loop2 and GU be a graph connecting
an (IU∗ − IL∗ )-chain to GL , as is shown in Figure 4(b). It is easy to see that GU is hollow,
|V (EL )| = O(1) and |V (EU )| = o(d1/2 ). Choose N = (2k − 1)d/2 and reproduce N different
isomorphic copies of the 1/(2γ − 1)-loop. It can be checked that (6.2) is satisfied.
2

Without loss of generality, we assume 1/(2γ − 1) is an integer and same for N .

22

Example 6.3. The negative number of isolated nodes IIso satisfies the conditions of Theorem
6.1 for any pair of IL∗ and IU∗ satisfying IL∗ = −bγdc for some γ ∈ (0, 1) and IU∗ − IL∗ = o(d1/2 ).
We let GL be a 2-chain and GU be a graph connecting an (IU∗ − IL∗ )-chain to GL , as is shown
in Figure 4(c). By construction GU is hollow, |V (EL )| = O(1) and |V (EU )| = o(d1/2 ). Choose
N = (d − IL∗ )/2 and reproduce N different isomorphic copies of the 2-chain. One can easily
check that (6.2) is satisfied.

7

Numerical Results

In this section we show the numerical performance for the proposed confidence interval to
three graph invariants: the negative number of connected subgraphs, the maximum degree and
the negative number of isolated nodes. In addition we apply our method to a neuroimaging
dataset.

7.1

Synthetic Data

We first implement Algorithm 1 for synthetic simulations. Here we use the confidence interval
to illustrate the performance of the skip-down algorithm. We consider three invariants: IConn ,
IDeg and IIso . Let X1 , . . . , Xn be i.i.d. n samples generated from N (0, Θ−1 ), where the
precision matrix Θ ∈ Rd×d . In order to illustrate Theorem 4.5 and show how the confidence
interval length changes adaptively with the value of I(ESig (Θ)), we choose two parameters
k ≥ kµ and generate the precision matrix Θ satisfying I(Θ) = k and I(Ep
Sig (Θ)) = kµ . To
generate such a precision matrix, we set the minimal signal strength θ = 0.01 log d/n and we
set part of the non-zero entries of Θ as µ > θ. To calculate the average coverage probability
and average confidence interval length, we repeat the simulation 500 times. We allow the
precision matrix to change in different repetitions to show that our confidence interval is
honest.
Specifically, we construct the precision matrices following different scenarios for three
different invariants as follows.
• IConn : Denote the adjacency matrix of a d-chain with Achain(d) ∈ Rd×d . Formally,
[Achain(d) ]s,t = 1 for any 1 ≤ s 6= t ≤ d satisfying |s − t| = 1 and [Achain(d) ]s,t = 0
otherwise. Recall that IConn denotes the negative number of connected subgraphs, and
hence the parameter k takes negative values. We construct our graph with −k connected
subgraphs by removing −k − 1 edges from the d-chain. Given any k ∈ [−d, −1], let the
adjacency matrix for the edges to cut be Acut(k) such that [Acut(k) ]s,t = 1 if and only
if |s − t| = 1 and s = jb−d/kc for j = 1, 2, . . . , −k − 1 and otherwise [Acut(k) ]s,t = 0.
We construct the precision matrix as Θµ,k = Id + µ(Achain(d) − Acut(k) ). Given k and
kµ to be the values of IConn (Θ) and IConn (ESig (Θ)) respectively, for each repetition,
we uniformly sample k − kµ edges from E(Θµ,k ) and change the values of entries on
e
Θµ,k corresponding to these edges from µ to θ. Denote this new precision matrix as Θ
e = k and IConn (ESig (Θ))
e = kµ . We generate X1 , . . . , Xn
and we can see that IConn (Θ)
23

Table 1: The estimated coverage probability (the column Prob.) and averaged confidence
interval length (the column Length) for IConn . We set the dimension d = 100, the sample
size n ∈ {400, 600}, the values of the invariant k = −25, kµ ∈ {−25, −26, −27, −28} and the
signal strength µ ∈ {0.2, 0.4, 0.6, 0.8}. The results are calculated based on 500 repetitions.
µ = 0.2
n

kµ Prob.
-25 0.978
-26 0.984
400
-27 0.970
-28 0.976
-25 0.976
-26 0.974
600
-27 0.976
-28 0.986

µ = 0.4

Length Prob.
43.81 0.848
44.63 0.962
45.13 0.970
46.25 0.976
35.91 0.756
36.72 0.940
37.69 0.970
38.88 0.984

Length
23.86
24.97
25.65
26.74
23.16
24.08
25.13
26.39

µ = 0.6
Prob.
0.802
0.970
0.968
0.976
0.826
0.972
0.976
0.986

Length
23.26
24.39
25.01
26.09
23.25
24.15
25.20
26.41

µ = 0.8
Prob.
0.920
0.976
0.970
0.976
0.896
0.966
0.976
0.986

Length
23.39
24.47
25.08
26.25
23.33
24.25
25.25
26.50

e −1 ) and construct [IbL , I ∗ ] from Algorithm 3. For IConn , we consider
i.i.d. from N (0, Θ
U
k = −25, kµ = −25, −26, −27 and −28 and set [IL∗ , IU∗ ] = [−d, −1].

• IDeg : Let the adjacency matrix of a k-star graph be Astar(k) ∈ R(k+1)×(k+1) such that
[Astar(k) ]1t = 1 for 1 ≤ t ≤ k + 1 and [Astar(k) ]st = 0 if s 6= 1. We construct the precision
matrix with signal strength µ for the graph assembling bd/(k + 1)c number of k-stars
as Θµ,k = Id + µ · diag(Astar(k) , . . . , Astar(k) , Id−kbd/(k+1)c ). Given k and kµ , for each
e = diag(Astar(k−kµ ) , Ik−kµ ) and we construct the precision matrix as
repetition, denote A
e = Id + µdiag(Astar(k) , . . . , Astar(k) , Id−kbd/(k+1)c ) + (θ − µ)diag(A,
e . . . , A,
e Id−kbd/(k+1)c ).
Θ

e = k and IDeg (ESig (Θ))
e = kµ . We generate X1 , . . . , Xn i.i.d.
We can see that IDeg (Θ)
e −1 ) and construct [IbL , I ∗ ] from Algorithm 1 for I = IDeg . For IDeg , we
from N (0, Θ
U
consider k = 5, kµ = 5, 4, 3 and 2 and set [IL∗ , IU∗ ] = [0, 20].
• IIso : Since IIso is the negative number of isolated nodes, the parameters k and kµ are
negative. If d + k is even, we construct the precision matrix with −k isolated nodes as
Θµ,k = µdiag(I−k , Achain(1) , . . . , Achain(1) ). The precision matrix represents the graph
containing −k isolated nodes and (d + k)/2 disconnected single edges. If d + k is even we
construct the precision matrix as Θµ,k = Id +µdiag(I−k , Achain(1) , . . . , Achain(1) , Achain(2) ).
Since d + k is odd, we let the last chain in the graph contain 2 edges. Given k and kµ
such that k − kµ is even, for each repetition, we uniformly sample (k − kµ )/2 edges
from the single edge chain in E(Θµ,k ) and change the weights on these edges from µ
e and we can see that IIso (Θ)
e = −k and
to θ. Denote this new precision matrix as Θ
e = −kµ . We generate X1 , . . . , Xn i.i.d. from N (0, Θ
e −1 ) and construct
IIso (ESig (Θ))
24

Table 2: The estimated coverage probability (the column Prob.) and averaged confidence
interval length (the column Length) for IDeg . We set the dimension d = 100, the sample size
n ∈ {400, 600}, the values of the invariant k = 5, kµ ∈ {5, 4, 3, 2} and the signal strength
µ ∈ {0.2, 0.4, 0.6, 0.8}. The results are calculated based on 500 repetitions.
µ = 0.2
n

kµ
5
4
400
3
2
5
4
600
3
2

Prob.
0.962
0.962
0.962
0.962
0.978
0.980
0.978
0.978

µ = 0.4

Length Prob.
15.68 0.964
15.68 0.964
16.44 0.962
17.31 0.962
15.63 0.978
15.63 0.978
16.60 0.978
17.57 0.978

µ = 0.6

Length
15.38
15.38
16.31
17.28
15.63
15.64
16.59
17.55

Prob. Length
0.962 15.39
0.962 15.39
0.962 16.34
0.962 17.29
0.978 15.65
0.978 15.65
0.978 16.62
0.978 17.56

µ = 0.8
Prob.
0.962
0.962
0.962
0.962
0.978
0.978
0.978
0.978

Length
15.39
15.39
16.35
17.31
15.65
15.65
16.62
17.59

[IbL , IU∗ ] from Algorithm 4. For IIso , we consider k = −3, kµ = −3, −5, −7 and −9 and
set [IL∗ , IU∗ ] = [−d, 0].
Given the data X1 , . . . , Xn , we estimate the precision matrix by the CLIME estimator
b j = arg min kβk1 s.t. kΣβ
b − ej k∞ ≤ λ
Θ

(7.1)

β∈Rd

where ej is the j-th canonical basis in Rd for any j = 1, . . . , d. The tuning parameter λ in
(7.1) is chosen through minimizing a 3-fold cross validation
CV(λ) =

3
X
k=1

b (k) Θ
b
kΣ
λ

(−k)

− Id k2F ,

(7.2)

b (k) is the sample covariance matrix only using the k-th fold of the dataset and Θ
b (−k)
where Σ
λ
is the CLIME estimator using the remaining data. In the simulations for all three invariants,
we set the dimension d = 100 and sample size n = 400 and 600. We set µ = 0.2, 0.4, 0.6 and
0.8. We choose the significance level of confidence intervals as 5%.
The estimated coverage probability and the averaged confidence interval length calculated
through 500 repetitions are reported in Tables 1, 2 and 3 for IConn , IDeg and IIso respectively.
From these results, we can see that when the value µ is relatively small, the confidence interval
lengths are larger in order to guarantee the confidence interval cover the true invariant under
small signal strength. When µ becomes larger, the confidence interval lengths converge to
the optimal rate O(IU∗ − I(ESig (Θ))) shown in (4.10). This illustrates that the proposed
confidence interval is adaptive to kµ .

25

Table 3: The estimated coverage probability (the column Prob.) and averaged confidence
interval length (the column Length) for IIso . We set the dimension d = 100, the sample size
n ∈ {400, 600}, the values of the invariant k = −3, kµ ∈ {−3, −5, −7, −9} and the signal
strength µ ∈ {0.2, 0.4, 0.6, 0.8}. The results are calculated based on 500 repetitions.
µ = 0.2
n

kµ
-3
-5
400
-7
-9
-3
-5
600
-7
-9

7.2

Prob.
0.962
0.972
0.970
0.964
0.978
0.974
0.968
0.974

µ = 0.4

Length Prob.
32.97 0.964
33.49 0.972
51.42 0.970
36.63 0.964
21.16 0.976
22.63 0.974
24.15 0.968
26.19 0.974

Length
4.32
6.25
8.28
10.15
2.93
4.87
6.74
8.70

µ = 0.6
Prob. Length
0.958
2.84
0.972
4.78
0.970
6.70
0.964
8.58
0.972
2.91
0.974
4.83
0.968
6.71
0.974
8.68

µ = 0.8
Prob.
0.938
0.972
0.970
0.964
0.962
0.974
0.968
0.974

Length
2.82
4.77
6.66
8.51
2.89
4.81
6.69
8.66

Neuroscience Application

We apply our inferential method to the brain imaging dataset studied in Simony et al. (2016).
The dataset contains fMRI scans from 36 subjects taken while the subjects were listening
to the stimuli generated from a seven-minute story Pieman (told by Jim O’Grady at the
“The Moth” storytelling event). The 36 subjects also listened to a word-scrambled version of
the story. In particular, the story was segmented into 608 short words and their order was
scrambled randomly. The raw functional data was preprocessed to correct head motion, time
slicing, spatial smoothing and temporal filtering in Simony et al. (2016). For both the intact
story and the word scrambled settings, each subject had 300 fMRI measurements and the
measurements were taken every 1.4 seconds.
The original fMRI dataset has the dimensional 271,633 representing 271,633 3-mm isotropic
voxels. We reduce the dimension to 172 regions of interest (ROIs) introduced by Baldassano
et al. (2015) through averaging the voxels in the same ROI. Therefore, for each subject,
we have the data with dimension d = 172 and sample size n = 300. We average the data
across the 36 subject to obtain a single 300 × 172 dataset and standardize each ROI such
that they have mean zero and standard deviation one. We apply the Gaussian graphical
model to the dataset so that the brain network is induced by the precision matrix Θ and
each ROI corresponds to a node in the network. Our goal is to infer two combinatorial
quantities of the brain network: the number of connected subgraphs and the maximum
degree. In fact, to grasp more detailed structural information of the network, we aim to infer
the above two invariants for the precision matrix at different filtration levels. In specific,
given a precision matrix Θ and a filtration level µ > 0, we define the thresholded matrix
[Tµ (Θ)]jk = Θjk 1{|Θjk | ≥ µ} for all 1 ≤ j, k ≤ d. We want to construct confidence intervals
for invariants IConn (Tµ (Θ)) and IDeg (Tµ (Θ)) for different levels of µ under both the intact
story and word scrambled settings. It is easy to check that IConn (Tµ (Θ)) and IDeg (Tµ (Θ))
26

µ = 0.5

µ = 0.6

µ = 0.7

# of Connected Subgraphs

Word

Intact

µ = 0.4

150
●

● ●

● ●

●

● ● ●

●
● ●
● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ●
● ● ● ● ●
● ●
● ●

● ●

100

●

● ●

●
●
●

●

●

●

●

50

Type

●
●

●

●

●

0

● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

0.0

0.1

0.2

0.3

● ●

●

0.4

0.5

Filtration Level

0.6

0.7

0.8

0.9

Intact
Word
1.0

Figure 5: The connected subgraphs in brain networks changing with the filtration level µ.
The upper panel illustrates the connected regions of interest by same colors. The lower panel
shows how the number of connected subgraphs change with the filtration level µ for both
intact story (in red) and word scrambled (in blue).
are also monotone invariants, therefore the skip-down algorithm can be applied.
As before, the tuning parameter of the CLIME estimator is chosen via 3-fold cross
validation using the risk in (7.2). The significance level of the confidence interval is set to
α = 5% and since there is no prior information on how large the maximum degree of the
network is, or how many connected subgraphs the network contains, we consider the largest
possible range for both invariants.
We implement Algorithm 1 to construct the confidence intervals. Figures 5 and 6 visualize
how the lower endpoints of the confidence intervals, of the number of connected subgraphs and
the maximum degree respectively, change with the filtration level µ. In addition, we visualize
the structural information of the output edge set Et∗ generated from the skip-down algorithm,
where t∗ is the number of iterations needed for Algorithm 1 to conclude. Figures 5 illustrates
the different connected ROIs in Gt∗ = (V, Et∗ ) by different colors and Figure 6 illustrates the
degree of each ROI in Gt∗ . For the number of connected subgraphs, Figure 5 shows that
the brain network has fewer connected subgraphs when the subject is listening to the intact
story compared to when the subject is listening to the scrambled word version. In particular,
we can see in Figure 7(a) that compared to the word scrambled setting, the dorsolateral
prefrontal cortex (DL-PFC) is connected to the inferior frontal gyrus (IFG) under the intact
27

µ=0

µ = 0.1

µ = 0.2

120

µ = 0.4

45

Intact

100

40

35
80

30

60

25

20
40

Word

15

20

10

5
0

5

●

●

●

Max Degree

100

●

●

●
●

50

●
●

● ●
●

Type
●
● ●
● ●

0
0.0

0.1

●

Intact
Word

● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ●

0.2

0.3

0.4

0.5

Filtration Level

0.6

0.7

0.8

0.9

1.0

Figure 6: The degree of region of interest in brain networks changing with filtration level µ.
The upper panel illustrates the degree of each region of interest. The lower panel shows how
the maximum degree changes with the filtration level µ for both intact story (in red) and
word scrambled (in blue).
story setting. The inferior frontal gyrus is the brain area responsible for language processing
and comprehension (Grewe et al., 2005; Caplan, 2006) and the dorsolateral prefrontal cortex
is responsible for working memory tasks (Barbey et al., 2013). The fact that these two areas
are connected in the intact story setting suggests that both language processing and memory
are working together in the procedure of understanding the intact Pieman story.
Regarding maximum degree, Figure 6 shows that the brain network has higher maximum
degree when the subject is listening to the intact story compared to when the subject is
listening to scrambled words. In Figure 7(b) we also observe that the precuneus area, which
is known to be involved with understanding high-level concepts in stories (Lerner et al., 2011;
Ames et al., 2015), has a higher degree under the intact story setting compared to the word
scrambled setting.

8

Discussion

In this manuscript we propose generic inferential methods for monotone invariants and
monotone properties under graphical models. Our skip-down algorithm is based on screening
28

10

15

20

(a) Connectivity

(b) Maximum Degree

Dorsolateral

Precuneus

120

45
100

40

35
80

30

60

25

20
40

15

20

5

IFG

Intact story

10

0

5

Word scrambled

Intact story

Word scrambled

Figure 7: Structural differences in cerebral cortices between the intact story and word
scrambled settings. (a) shows the connected regions of interest in brain networks under the
filtration level µ = 0.4. (b) shows the degree of regions of interest in brain networks under
the filtration level µ = 0.
critical edge sets specific to the invariant of interest. We provide fast algorithms critical edge
set search for several graph invariants. An interesting research direction is to provide an
efficient critical edge set searching algorithm for a general family of invariants. Moreover, we
can explore the inferential methods for the combinatorial structures beyond graphs in the
future researches, including ranking, hypergraph and partitions.
For the
p lower bound on the confidence interval length, we show that the signal strength at
the rate log d/n is critical for a large family of invariants. A standing question is to find out
whether invariants whose confidence interval length has lower bounds depending on smaller
signal strength exist, and to construct optimal confidence intervals for such invariants.

References
Addario-Berry, L., Broutin, N., Devroye, L. and Lugosi, G. (2010). On combinatorial
testing problems. The Annals of Statistics 38 3063–3092.
Allen, G. I. and Liu, Z. (2012). A log-linear graphical model for inferring genetic networks
from high-throughput sequencing data. In Bioinformatics and Biomedicine (BIBM), 2012 IEEE
International Conference on. IEEE.
Ames, D. L., Honey, C. J., Chow, M. A., Todorov, A. and Hasson, U. (2015). Contextual
alignment of cognitive and neural dynamics. Journal of Cognitive Neuroscience 27 655–664.
Anandkumar, A., Tan, V. Y., Huang, F., Willsky, A. S. et al. (2012). High-dimensional
structure estimation in Ising models: Local separation criterion. The Annals of Statistics 40
1346–1375.
Arias-Castro, E., Bubeck, S. and Lugosi, G. (2012). Detection of correlations. The Annals of
Statistics 40 412–435.
Arias-Castro, E., Bubeck, S., Lugosi, G. and Verzelen, N. (2015). Detecting Markov
random fields hidden in white noise. arXiv preprint arXiv:1504.06984 .
Arias-Castro, E., Candès, E. J. and Durand, A. (2011). Detection of an anomalous cluster in
a network. The Annals of Statistics 39 278–304.

29

10

15

20

25

30

35

40

Baldassano, C., Beck, D. M. and Fei-Fei, L. (2015). Parcellating connectivity in spatial maps.
PeerJ 3 e784.
Barbey, A. K., Koenigs, M. and Grafman, J. (2013). Dorsolateral prefrontal contributions to
human working memory. Cortex 49 1195–1205.
Bauer, P. and Hackl, P. (1987). Multiple testing in a set of nested hypotheses. Statistics: A
Journal of Theoretical and Applied Statistics 18 345–349.
Cai, T., Liu, W. and Luo, X. (2011). A constrained `1 minimization approach to sparse precision
matrix estimation. Journal of the American Statistical Association 106 594–607.
Cai, T. T. and Guo, Z. (2015). Confidence intervals for high-dimensional linear regression:
Minimax rates and adaptivity. arXiv preprint arXiv:1506.05539 .
Cai, T. T., Liu, W. and Xia, Y. (2013). Two-sample covariance matrix testing and support
recovery in high-dimensional and sparse settings. Journal of the American Statistical Association
108 265–277.
Cai, T. T., Liu, W. and Xia, Y. (2014). Two-sample test of high dimensional means under
dependence. Journal of the Royal Statistical Society. Series B. Statistical Methodology 76 349–372.
Caplan, D. (2006). Why is broca’s area involved in syntax? Cortex 42 469–471.
Chen, S., Witten, D. M. and Shojaie, A. (2015). Selection and estimation for mixed graphical
models. Biometrika 102 47–64.
Chernozhukov, V., Chetverikov, D. and Kato, K. (2013). Gaussian approximations and
multiplier bootstrap for maxima of sums of high-dimensional random vectors. The Annals of
Statistics 41 2786–2819.
Danaher, P., Wang, P. and Witten, D. M. (2014). The joint graphical Lasso for inverse
covariance estimation across multiple classes. Journal of the Royal Statistical Society. Series B.
Statistical Methodology 76 373–397.
Fan, J., Liu, H., Ning, Y. and Zou, H. (2014). High dimensional semiparametric latent graphical
model for mixed data. ArXiv e-prints, arXiv:1404.7236 .
Fellinghauer, B., Bühlmann, P., Ryffel, M., von Rhein, M. and Reinhardt, J. D. (2013).
Stable graphical model estimation with random forests for discrete, continuous, and mixed
variables. Comput. Stat. Data Anal. 64 132–152.
Friedman, J. H., Hastie, T. J. and Tibshirani, R. J. (2008). Sparse inverse covariance
estimation with the graphical Lasso. Biostatistics 9 432–441.
Grewe, T., Bornkessel, I., Zysset, S., Wiese, R., von Cramon, D. Y. and Schlesewsky,
M. (2005). The emergence of the unmarked: A new perspective on the language-specific function
of broca’s area. Human brain mapping 26 178–190.
Gu, Q., Cao, Y., Ning, Y. and Liu, H. (2015). Local and global inference for high dimensional
gaussian copula graphical models. arXiv preprint arXiv:1502.02347 .
Hagmann, P., Cammoun, L., Gigandet, X., Meuli, R., Honey, C. J., Wedeen, V. J. and
Sporns, O. (2008). Mapping the structural core of human cerebral cortex. PLoS Biol 6 e159.
Han, F. and Liu, H. (2014). Distribution-free tests of independence with applications to testing
more structures. arXiv preprint arXiv:1410.4179 .
Höfling, H. and Tibshirani, R. J. (2009). Estimation of sparse binary pairwise Markov networks
using pseudo-likelihoods. J. Mach. Learn. Res. 10 883–906.
Jalali, A., Ravikumar, P. D., Vasuki, V. and Sanghavi, S. (2011). On learning discrete
graphical models using group-sparse regularization. In International Conference on Artificial

30

Intelligence and Statistics.
Janková, J. and van de Geer, S. (2016). Honest confidence regions and optimality in highdimensional precision matrix estimation. TEST 1–20.
Javanmard, A. and Montanari, A. (2014). Confidence intervals and hypothesis testing for
high-dimensional regression. J. Mach. Learn. Res. 15 2869–2909.
Joag-Dev, K. and Proschan, F. (1983). Negative association of random variables with applications. The Annals of Statistics 286–295.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman
problem. Proceedings of the American Mathematical society 7 48–50.
Lam, C. and Fan, J. (2009). Sparsistency and rates of convergence in large covariance matrix
estimation. The Annals of Statistics 37 4254–4278.
LeCam, L. (1973). Convergence of estimates under dimensionality restrictions. The Annals of
Statistics 1 38–53.
Lee, J. D. and Hastie, T. J. (2015). Learning the structure of mixed graphical models. Journal
of Computational and Graphical Statistics 25 230–253.
Lee, S.-I., Ganapathi, V. and Koller, D. (2006). Efficient structure learning of Markov networks
using `1 -regularization. In Advances in Neural Information Processing Systems.
Lerner, Y., Honey, C. J., Silbert, L. J. and Hasson, U. (2011). Topographic mapping of a
hierarchy of temporal receptive windows using a narrated story. The Journal of Neuroscience 31
2906–2915.
Liu, H., Han, F., Yuan, M., Lafferty, J. D. and Wasserman, L. A. (2012a). High-dimensional
semiparametric Gaussian copula graphical models. The Annals of Statistics 40 2293–2326.
Liu, H., Han, F. and Zhang, C.-H. (2012b). Transelliptical graphical models. In Proc. of NIPS
(P. Bartlett, F. Pereira, C. Burges, L. Bottou and K. Weinberger, eds.). 809–817.
Liu, H. and Wasserman, J. D. L. L. A. (2009). The nonparanormal: Semiparametric estimation
of high dimensional undirected graphs. J. Mach. Learn. Res. 10 2295–2328.
Liu, W. (2013). Gaussian graphical model estimation with false discovery rate control. The Annals
of Statistics 41 2948–2978.
Lu, J., Kolar, M. and Liu, H. (2015). Post-regularization inference for dynamic nonparanormal
graphical models. arXiv preprint arXiv:1512.08298 .
Luscombe, N. M., Babu, M. M., Yu, H., Snyder, M., Teichmann, S. A. and Gerstein,
M. (2004). Genomic analysis of regulatory network dynamics reveals large topological changes.
Nature 431 308–312.
Meinshausen, N. and Bühlmann, P. (2006). High dimensional graphs and variable selection with
the Lasso. The Annals of Statistics 34 1436–1462.
Mohan, K., London, P., Fazel, M., Witten, D. M. and Lee, S.-I. (2014). Node-based learning
of multiple gaussian graphical models. J. Mach. Learn. Res. 15 445–488.
Nash-Williams, C. S. J. (1961). Edge-disjoint spanning trees of finite graphs. Journal of the
London Mathematical Society 1 445–450.
Nash-Williams, C. S. J. (1964). Decomposition of finite graphs into forests. Journal of the
London Mathematical Society 1 12–12.
Neykov, M., Lu, J. and Liu, H. (2016). Combinatorial inference for graphical models. arXiv
preprint arXiv:1608.03045 .
Neykov, M., Ning, Y., Liu, J. S. and Liu, H. (2015). A unified theory of confidence regions and

31

testing for high dimensional estimating equations. arXiv preprint arXiv:1510.08986 .
Ning, Y. and Liu, H. (2014). A general theory of hypothesis tests and confidence regions for sparse
high dimensional models. arXiv preprint arXiv:1412.8765 .
Peng, J., Wang, P., Zhou, N. and Zhu, J. (2009). Partial correlation estimation by joint sparse
regression models. J. Am. Stat. Assoc. 104 735–746.
Qiu, H., Han, F., Liu, H. and Caffo, B. S. (2013). Joint estimation of multiple graphical models
from high dimensional time series. ArXiv e-prints, arXiv:1311.0219 .
Ravikumar, P., Wainwright, M. J. and Lafferty, J. D. (2010). High-dimensional Ising model
selection using `1 -regularized logistic regression. The Annals of Statistics 38 1287–1319.
Ravikumar, P., Wainwright, M. J., Raskutti, G. and Yu, B. (2011). High-dimensional
covariance estimation by minimizing `1 -penalized log-determinant divergence. Electron. J. Stat. 5
935–980.
Ren, Z., Sun, T., Zhang, C.-H. and Zhou, H. H. (2015). Asymptotic normality and optimalities
in estimation of large gaussian graphical models. Ann. Statist. 43 991–1026.
Romano, J. and Wolf, M. (2005). Exact and approximate stepdown methods for multiple
hypothesis testing. Journal of the American Statistical Association 100 94–108.
Rubinov, M. and Sporns, O. (2010). Complex network measures of brain connectivity: uses and
interpretations. Neuroimage 52 1059–1069.
Shen, X., Pan, W. and Zhu, Y. (2012). Likelihood-based selection and sharp parameter estimation.
J. Am. Stat. Assoc. 107 223–232.
Simony, E., Honey, C. J., Chen, J., Lositsky, O., Yeshurun, Y., Wiesel, A. and Hasson,
U. (2016). Dynamic reconfiguration of the default mode network during narrative comprehension.
Nature Communications 7 12141.
van de Geer, S. A., Bühlmann, P., Ritov, Y. and Dezeure, R. (2014). On asymptotically
optimal confidence regions and tests for high-dimensional models. The Annals of Statistics 42
1166–1202.
van der Vaart, A. W. and Wellner, J. A. (1996). Weak Convergence and Empirical Processes:
With Applications to Statistics. Springer.
Xue, L. and Zou, H. (2012). Regularized rank-based estimation of high-dimensional nonparanormal
graphical models. The Annals of Statistics 40 2541–2571.
Yang, E., Allen, G. I., Liu, Z. and Ravikumar, P. (2012). Graphical models via generalized
linear models. In Advances in Neural Information Processing Systems 25. 1358–1366.
Yang, E., Ravikumar, P., Allen, G. I., Baker, Y., Wan, Y.-W. and Liu, Z. (2014a). A
general framework for mixed graphical models. arXiv preprint arXiv:1411.0288 .
Yang, E., Ravikumar, P., Allen, G. I. and Liu, Z. (2013). On poisson graphical models. In
Advances in Neural Information Processing Systems 26. 1718–1726.
Yang, Z., Ning, Y. and Liu, H. (2014b). On semiparametric exponential family graphical models.
arXiv preprint arXiv:1412.8697 .
Yuan, M. and Lin, Y. (2007). Model selection and estimation in the gaussian graphical model.
Biometrika 94 19–35.
Zhang, C.-H. and Zhang, S. S. (2013). Confidence intervals for low dimensional parameters in
high dimensional linear models. J. R. Stat. Soc. B 76 217–242.
Zhou, S., van de Geer, S. and Bühlmann, P. (2009). Adaptive Lasso for high dimensional
regression and Gaussian graphical modeling. arXiv preprint arXiv:0903.2515 .

32

Technical supplementary material to

Adaptive Inferential Method for Monotone Graph
Invariants
Junwei Lu, Matey Neykov and Han Liu
This document contains the supplementary material to the paper “Adaptive Inferential
Method for Monotone Graph Invariants”. We mainly provide technical details of proving
confidence interval lower bound here.

S.1

Proofs of Results on the Skip-Down Method

In this section, we prove theoretical results on skip-down algorithm. We will prove Theorems
4.1, 4.5 and 4.6 and Proposition 3.2.

S.1.1

Proof of Theorem 4.1

Under (3.5), it suffices to prove (4.1) and (4.2) by showing that

lim inf inf∗ ∗ PΘ I(Θ) ≤ IbL ≥ 1 − α.
n→∞ Θ∈Us (IL ,IU )

(S.1)

We denote the true edge set as E ∗ = E(Θ). We aim to bound the probability of the
event {I(Θ) < IbL }. Assume that the output of Algorithm 1 satisfies I(Θ) < IbL and that
the algorithm has stopped at the t = K-th step. Under these assumptions the final rejected
edge set EK satisfies I(EK ) > I(Θ). Our high-level outline to prove this theorem is to show
the following two facts:
(1) At least one rejected edge belongs to CI (E ∗ );
(2) If the `-th iteration is the step before which no edge in CI (E ∗ ) is rejected, then
CI (E ∗ ) ⊆ CI (E`−1 ).
Suppose the above two claims have been proved. We denote the first edge rejected in
CI (E ∗ ) as ē. According to the steps in Algorithm 1, we have
max∗

e∈CI (E )

√ d √ d
b ≥ nΘ
b ≥ c(α, CI (E`−1 )) ≥ c(α, CI (E ∗ )),
nΘ
e
ē

(S.2)

where the first inequality is by ē ∈ CI (E ∗ ), the second inequality is by the mechanism of
updating the rejected set and the third inequality is by CI (E ∗ ) ⊆ CI (E`−1 ). Therefore, by
(3.5) and the fact that Θe = 0 for any e ∈ CI (E ∗ ) ⊆ (E ∗ )c , we have


√ d
b ≥ c(α, CI (E ∗ )) ≤ α + o(1).
sup PΘ (I(Θ) < IbL ) ≤
sup PΘ max∗ nΘ
e
∗ ,I ∗ )
Θ∈Us (IL
U

∗ ,I ∗ )
Θ∈Us (IL
U

e∈CI (E )

33

So in the rest part of the proof, we only need to show the above two facts.
We first prove that at least one rejected edge belongs to CI (E ∗ ). To begin with, there
must exist at least one edge in (E ∗ )c which is rejected, otherwise EK ⊆ E ∗ which implies
a contradictory result that IbL = I(EK ) ≤ I(E ∗ ) = I(Θ). To show the stronger result
that EK ∩ CI (E ∗ ) 6= ∅, we consider the edge set EK ∪ E ∗ . Since I(EK ) > I(E ∗ ) and I is
monotone, we have I(EK ∪ E ∗ ) > I(E ∗ ) as well. As we have shown that EK \E ∗ 6= ∅, we
denote the edges in this set as EK \E ∗ = {e1 , . . . , em }. Here the order of the edges’ indices is
arbitrary. Consider the nested sequence
E ∗ ⊆ E ∗ ∪ {e1 } ⊆ E ∗ ∪ {e1 , e2 } ⊆ · · · ⊆ E ∗ ∪ {e1 , . . . , em } = EK ∪ E ∗ ,
where I(EK ∪ E ∗ ) > I(E ∗ ).
Notice that the invariant of the first edge set in the above sequence is strictly smaller
than the one of the last one. The fact that I is monotone implies that there exists an integer
m0 ∈ [0, m] such that I(E ∗ ∪ {e1 , . . . , em0 }) < I(E ∗ ∪ {e1 , . . . , em0 +1 }), where for m0 = 0, we
denote E ∗ ∪ {e1 , . . . , em0 } = E ∗ . In particular, we have the sequence
E ∗ ⊆ · · · ⊆ E ∗ ∪ {e1 , . . . , em0 } ⊆ E ∗ ∪ {e1 , . . . , em0 +1 } ⊆ · · · ⊆ EK ∪ E ∗ .
|
{z
} |
{z
}
I(•)≤I(E ∗ ∪{e1 ,...,em0 })

(S.3)

I(E ∗ ∪{e1 ,...,em0 +1 })≤I(•)

Comparing to (3.3), we have em0 +1 ∈ CI (E ∗ ) and by the construction, em0 +1 ∈ EK . Therefore,
we prove that EK ∩ CI (E ∗ ) 6= ∅.
Recall ` denotes the first iteration of Algorithm 1 in which and edge from CI (E ∗ ) has been
rejected. Now, we are going to show that CI (E ∗ ) ⊆ CI (E`−1 ). We have E`−1 ∩ CI (E ∗ ) = ∅
and I(E`−1 ) ≤ I(E ∗ ). For any e0 ∈ CI (E ∗ ), denote E 0 is the set satisfying (3.3) for
CI (E ∗ ) such that E 0 ⊇ E ∗ and I(E 0 ) > I(E 0 \{e0 }). The monotone invariant implies that
I(E 0 ∪ E`−1 ) ≥ I(E 0 ). To prove e0 ∈ CI (E`−1 ), it suffices to show that

I(E 0 ∪ E`−1 ) > I (E 0 ∪ E`−1 )\{e0 } .
Combining E`−1 ∩ CI (E ∗ ) = ∅ with e0 ∈ CI (E ∗ ), it is equivalent to show
I(E 0 ∪ E`−1 ) > I((E 0 \{e0 }) ∪ (E`−1 \E 0 )).
This is obviously true if E`−1 \E 0 = ∅ as I(E 0 ) > I(E 0 \{e0 }). For the case E`−1 \E 0 6= ∅, we
prove by contradiction. If I((E 0 \{e0 }) ∪ (E`−1 \E 0 )) ≥ I(E 0 ∪ E`−1 ), we have
E 0 \{e0 } ⊆ (E 0 \{e0 }) ∪ E`−1 and I(E 0 \{e0 }) < I(E 0 ∪ E`−1 ) ≤ I((E 0 \{e0 }) ∪ E`−1 ).
Similar to (S.3), we denote E`−1 \E 0 = {e01 , . . . , e0m0 } and there exists an integer m00 ∈ [0, m0 ]
such that
(E 0 \{e0 }) ∪ {e01 , . . . , e0m00 } ⊆ (E 0 \{e0 }) ∪ {e01 , . . . , e0m00 +1 } .
(S.4)
|
{z
} |
{z
}
I(•)≥I(E 0 \{e0 })

I((E 0 \{e0 })∪E`−1 )≤I(•)

34

Since e0m0 +1 ∈ E`−1 \E 0 and E ∗ ⊆ E 0 \{e0 }, we have e0m0 +1 6∈ E ∗ . Combining with (S.4), the
0
0
definition in (3.3) is satisfied for e0m0 +1 and thus e0m0 +1 ∈ CI (E ∗ ). This contradicts the fact
0
0

that E`−1 ∩ CI (E ∗ ) = ∅. In summary, we show that I(E 0 ∪ E`−1 ) > I (E 0 ∪ E`−1 )\{e0 } and
therefore, due to the previous discussion, prove that CI (E ∗ ) ⊆ CI (E`−1 ).

S.1.2

Proof of Theorems 4.5 and 4.6

We first define a few notations before presenting the proof. For a positive number µ > 0,
recall that the thresholded matrix [Tµ (Θ)]jk = Θjk 1{|Θjk | ≥ µ} for all 1 ≤ j, k ≤ d.
We define Tµ (Θ) in order to show the
p adaptivity of our confidence interval. We can see
I(Tµ (Θ)) = I(ESig (Θ)) when µ = C log d/n.
We also define the parameter space
n
o
∗
∗
∗
∗
(S.5)
Us (IL , IU ; θ, µ) = Θ ∈ Us I(Θ) ≤ IU , min |Θe | ≥ θ, I(Tµ (Θ)) ≥ IL .
e∈E(Θ)

The proof of both Theorems 4.5 and S.7 can be directly derived from the following lemma.
Lemma S.1. Suppose Θ ∈ Us and (log(dn))6 /n + s2 (log dn)4 /n = o(1). For any monotone
p
invariant I with range [IL∗ , IU∗ ], there exists a positive constant C such that if µ ≥ C log d/n,
for any α ∈ (0, 1) and θ > 0,
sup

∗ ,I ∗ ;θ)
Θ∈UI (IL
U

PΘ (I(Tµ (Θ)) ≤ IbL ) = 1 − O(1/d3 ).

(S.6)

We defer the proof of Lemma S.1 to Section S.4 in the technical supplementary. We first
give the proof of Theorem 4.5. By the construction of [IbL , IU∗ ] in Algorithm 1, we have
EΘ [IU∗ − IbL ] ≤ EΘ [IU∗ − I(Tµ (Θ)) ∨ IL∗ | I(Tµ (Θ)) ≤ IbL ]P(I(Tµ (Θ)) ≤ IbL )
+ (I ∗ − I ∗ )P(I(Tµ (Θ)) > IbL )
U

≤

L

− I(Tµ (Θ)) ∨ IL∗ + 1]P(I(Tµ (Θ)) ≤ IbL )
+ (I ∗ − I ∗ )P(I(Tµ (Θ)) > IbL ).

[IU∗

U

L

Therefore, by (S.6), we have


EΘ IbU − IbL
IU∗ − IL∗
sup
≤
1
+
o(1)
+
· O(1/d3 ).
∗
∗
∗
∗
I
−
I(T
(Θ))
+
1
I
−
I(T
(Θ))
+
1
µ
µ
Θ∈UI (IL ,IU ;θ) U
U
Since IU∗ − IL∗ = O(d2 ), we have the second term on the right hand side above to be o(1).
Therefore, we finish the proof of (4.10).
Similarly, we can also have
EΘ [I(Θ) − IbL ] ≤ [I(Θ) − I(Tµ (Θ)) ∨ IL∗ ]P(I(Tµ (Θ)) ≤ IbL ) + [I(Θ) − IL∗ ]P(IbL > I(Tµ (Θ))).
35

By (S.6), following the same argument as the proof of (4.10) above, we prove (4.11).
Theorem S.7 is a direct corollary of (S.6). For a monotone property P, we have the range
∗
IL = 0 and IU∗ = 1. Moreover, if Θ ∈ G1 (µ; P) defined in (S.20), we have Tµ (Θ) = Θ. Since
Algorithm 2 is derived from Algorithm 1 in the sense that the test ψα = 1 is equivalent to a
1 − 2α confidence lower side IbL = 1. Thus, under the alternative that P(Θ) = 1, we have
{ψα = 1} = {P(Θ) ≤ IbL } = {P(Tµ (Θ)) ≤ IbL }.

Therefore, (S.21) can be directly derived from (S.6).

S.1.3

Proof of Proposition 3.2

We first prove a general result on when the critical edge set is empty. We claim that given
any monotone property P, if P(G0 ) = 1 then CP (E0 ) = ∅. This is straightforward from
Definition 3.1. If P(G0 ) = 1, by the monotonicity of P, for any E 0 ⊇ E0 , we have P(E 0 ) = 1.
Therefore, there is no edge e ∈ E0c such that P(E 0 \{e}) = 0. This implies that CP (E0 ) = ∅.
Therefore, we prove the four results in Proposition 3.2 when the critical edge sets are empty.
In the following part of the proof, we will discuss four properties case by case. An illustration
of the proof are shown in Figure 8.
• Connected subgraphs. Now we prove the results on the connected subgraphs. We can
consider the case PConn,−k (G0 ) = 0. We choose the k 0 nodes, each of which from one of
0
the connected subgraphs {G0` = (V0` , E0` )}k`=1 . Namely, we choose arbitrary v` ∈ V0` for
1 ≤ ` ≤ k 0 . For any edge (u, v) ∈ E0 such that j ∈ V0` , k ∈ V0`0 , ` 6= `0 . We arbitrarily select
k 0 − k − 1 edges from the set {(vs , vs0 )|(s, s0 ) 6= (`, `0 ) or (s, s0 ) 6= (`0 , `)} and denote this set
e We construct the set
E.
e
E 0 = E0 ∪ {e} ∪ E.
We can find an illustration of the construction in Figure 8(a). Notice that G0 = (V, E 0 ) has
e
k−1 connected subgraphs and thus PConn,−k (E 0 ) = 1. We can also check that E 0 \{e} = E0 ∪ E
with has k connected subgraphs. By (3.3), we have (u, v) ∈ CPConn,−k (E0 ) and thus

CPConn,−k (E0 ) ⊇ (u, v) ∈ E0 j ∈ V0` , k ∈ V0`0 , ` 6= `0 .
v1

e

u

Ẽ
v2
v3 E0
(a) PConn,−k

Ẽ

u

Ẽ

u

E0

u

v

v

v
v

E0
(b) PDeg,k

E0
(c) PCycle

v

u
Ẽ
(d) PSig,−k

Figure 8: Visualization of the proof of Proposition 3.2.

36

To prove the other direction, if e 6∈ {(u, v) ∈ E0 u ∈ V0` , v ∈ V0`0 }, we must have e ∈ E0`
for some `. For any E 0 ⊇ E such that PConn,−k (E 0 ) = 1, since e ∈ E0` , E 0 \{e} has the same
number of connected subgraphs, therefore e 6∈ CPConn,−k (E0 ). In summary, we prove (3.8).
• Maximum degree. We next move to the critical edge set of maximum degree. By (3.3),
we have CPDeg,k (E0 ) ⊆ E0c . It suffices to prove another direction. Denote the maximum degree
of G0 as k 0 . For any (u, v) ∈ E0c , since the maximum degree k 0 ≤ k, we can select arbitrary
e See
k 0 − k edges from {(u, u0 ) ∈ E0c |u0 6= v} and denote the set containing these edges as E.
0
e has
an illustration of the proof in Figure 8(b). It is easy to check that E = E0 ∪ {(u, v)} ∪ E
0
0
c
PDeg,k (E ) = 1 and PDeg,k (E \{(u, v)}) = 0. Therefore, we have CPDeg,k (E0 ) = E0 .
• Acyclic. Now we turn to show the critical edge set for the cyclic property when
G0 = (V, E0 ) is a forest. Similar to the preceding part, it suffices to show E0c ⊆ CPCycle (E0 ).
For any (u, v) ∈ E0c , if E0 ∪ {(u, v)} forms a cycle, then (u, v) ∈ CPCycle (E0 ) by the definition in
(3.3). If E0 ∪ {(u, v)} is still a forest, we apply the Kruskal’s algorithm (Kruskal, 1956) with
the initial input E0 ∪ {(u, v)} and the weights of all edges are 1. Specifically, the procedure in
described in Algorithm 6 and in the algorithm we can choose arbitrary order of adding edges
in (E0 ∪ {(u, v)})c in the for loop since the edge weights are the same. We denote the output
e and (V, E)
e is a tree by the property of Kruskal’s algorithm.
edge set of Algorithm 6 as E
We illustrate the graph and the following of the construction in Figure 8(c). We start to
construct E 0 to satisfy (3.3). Since (V, E 0 ) is a tree, there are only two cases: (1) neither of
u, v is a leaf; and (2) only one of u, v is a leaf. We first consider the case that neither of u, v
e Then, in the graph (V, E),
e we can choose u0 as any neighbor of u but v and
is a leaf in E.
0
choose v as any neighbor of v but u. This is feasible since neither of u, v is a leaf. We can see
e ∪ {(u0 , v 0 )}
that u0 6= v 0 , otherwise the triangle u → v → u0 → u forms a loop. Let E 0 = E
e is a tree and adding
and it has a loop u → v → v 0 → u0 → u and has only this loop (as E
one edge to it will only form one loop). Therefore, if we delete the edge (u, v) from the loop,
e ∪ {(u, u0 )} has
the graph (V, E 0 \{(u, v)}) has no loop. Therefore, we check (3.3) that E 0 = E
∈ PCycle (E 0 ) = 1 and PCycle (E 0 \{(u, u0 )}) = 0. For the second case that only one of u, v is a
e we
leaf (we assume the leaf is u), the proof is similar to the first one. In the graph (V, E),
e ∪ {(u, v 0 )} has
find v 0 as any neighbor of v but u. We can check as the first case that E 0 = E
PCycle (E 0 ) = 1 and PCycle (E 0 \{(u, v 0 )}) = 0. We can now conclude that E0c = CPCycle (E0 ).
Algorithm 6 Kruskal’s algorithm for the proof of Proposition 3.2
Input: E (0) = E0 ∪ {(u, v)}, t = 0.
for e ∈ (E0 ∪ {(u, v)})c do
t ← t + 1;
if {e} ∪ E (t) does not contain a cycle then
E (t) ← E (t−1) ∪ {e}
end if
end for
Output: E (t) .
• Singletons. We finally discuss the critical edge set for isolated nodes. Denote the number
37

of isolated nodes |VSig | = k 0 ≥ k. For any (u, v) ∈ E0c such that u ∈ VSig or v ∈ VSig , we can
check that at least one of u and v is an isolated node. If both u, v are isolated nodes, this
implies that k 0 > k + 1 and we can select arbitrary k 0 − k − 1 nodes from VSig \{u, v} if only
one of u, v is a isolated node, we select arbitrary k 0 − k − 2 nodes from VSig \{u, v}. Denote
e = {(u0 , v 0 ) ∈ E c |u0 , v 0 ∈ Ve }. We can check that
the set of nodes selected as Ve and define E
0
e has PSig,−k (E 0 ) = 1 and PSig,−k (E 0 \{(u, v)}) = 0. Therefore, we have
E 0 = E0 ∪ {(u, v)} ∪ E
CPSig,−k (E0 ) ⊇ {(u, v) ∈ E0c | u ∈ VSig or v ∈ VSig }. The construction is illustrated in Figure
8(d). On the other hand, let the edge (u, v) satisfy u 6∈ VSig and v 6∈ VSig . For any E 0 ⊇ E0 and
PSig,−k (E 0 ) = 1, as E 0 \{(u, v)} does not include new isolated nodes, PSig,−k (E 0 \{(u, v)}) = 1.
This implies that CPSig,−k (E0 ) = {(u, v) ∈ E0c | u ∈ VSig or v ∈ VSig }.

S.2

Proofs for Lower Bound of confidence interval length

In this section, we give a general framework of the lower bound of confidence interval length.

S.2.1

Proof of Theorem 6.1

We define the pre-distance on a graph G = (V, E) between two vertex sets V1 and V2 as
dG (V1 , V2 ) = the length of the shortest path on G connecting one of v1 ∈ V1 and one of
v2 ∈ V2 , and if there is no such path, we let dG (V1 , V2 ) = ∞. In order to prove Theorem 6.1,
we need the following lemma.
Lemma S.2. Given an invariant, if there exists a construction as follows:
(1) There exists GL = (V, E L ) satisfying V L := V (E L ) ⊂ V = {1, . . . , d} and I(GL ) = IL∗ .
N
(2) There exist N disjoint anchor vertex sets {Aj }N
j=1 such that ∪j=1 Aj ⊆ V L .

(3) There exists V U ⊆ V \V L such that for each vertex set Aj , we can find an edge set Ej
with V (Ej ) ⊆ Aj ∪ V U and the graph Gj = (V, E L ∪ Ej ) has I(Gj ) = IU∗ .
(4) There exists a universal constant R independent to the such that for any 1 ≤ j ≤ N ,
Gj is R-hollow and |Aj | ≤ R. Moreover, the number of anchor vertex sets has N ≥ dγ
with some γ > 0.
Suppose ∀1 ≤ j =
6 k ≤ N , dGL (Aj , Ak ) = ∞, |V U | = o(d1/2 ) and |V L |/d < 1. there exist
constants C1 and C2 such that if
p
p
θ ≤ C1 log d/n and max dmax (Gj ) log d/n ≤ C2 ,
(S.7)
j

we have the following lower bound on the confidence interval length


b −L
b
EΘ U
≥ 1 − 2α.
lim inf
inf
sup
n→∞ [L,
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ) Oracle Length(Θ)
L U
38

We now prove Theorem 6.1 using Lemma S.2. Let
N
GL = ∪N
j=1 GL,j ∪ GL and GU = ∪j=1 GL,j ∪ GU .

We choose anchor vertex sets Aj = V (GL,j ) for 1 ≤ j ≤ N . Since |V (EL )| = O(1) and GL,j ’s
are isomorphic copies of GL , we have |Aj | = O(1) as well. It is easy to check ∪N
j=1 Aj ⊆ V L .
We now construct Gj ’s as isomorphic copies of GU . In order to obtain these copies, we denote
the isomorphic map between GL and GL,j as σj : V (GL ) → V (GL,j ). We extend the domain
of σj to V by letting σ̄j (u) = σj (u) if u ∈ V (GL ) and σ̄j (u) = u otherwise. We construct
Ej := {(σj (u), σj (v)) | (u, v) ∈ (EU \EL ))} and we can see the graph Gj = (V, E L ∪ Ej ) is
isomorphic to GU . Therefore, I(Gj ) = IU∗ for any 1 ≤ j ≤ N . Therefore, by Lemma S.2, we
complete the proof.

S.2.2

Proof of Lemma S.2

The high level idea of the proof is to reduce the length of confidence interval to the bound of
χ2 -divergence of two distributions.
In fact, we will prove a stronger lower bound in a smaller parameter space Us (IL∗ , IU∗ ; θ, µ)
defined in (S.5). We consider this parameter
space because it contains precision matrices Θ
p
∗
such that I(Tµ (Θ)) ≥ IL , for µ = C log d/n. Namely, part of entries of precision matrix
has strong enough signal strenght.
We can lower bound the length of confidence interval as




b −L
b
b −L
b
EΘ U
EΘ U
≥
inf
sup
inf
sup
∗
∗
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ,µ) IU
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ) IU
− I(Tµ (Θ)) [L,
− I(Tµ (Θ))
[L,
L U
L U


b −L
b
EΘ U
.
(S.8)
≥
inf
sup
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ,µ)
IU∗ − IL∗
[L,
L U
The following lemma proved in Cai and Guo (2015) reduces the length of confidence
interval to the χ2 -divergence. Given two distributions P and Q, the χ2 -divergence between P
and Q is defined as
Z  2
dP
Dχ2 (P, Q) =
dQ − 1.
dQ

Lemma S.3 (Lemma 1, Cai and Guo (2015)). Given any monotone invariant I, suppose
there exist Θ0 , Θ1 , . . . , ΘN ∈ Us (IL∗ , IU∗ ; θ, µ) satisfying I(Θ0 ) = IL∗ and I(Θj ) = IU∗ for all
P
1 ≤ j ≤ N . If PL = PΘ0 and PU = N1 N
j=1 PΘj , we have
q


∗
∗
b
b
inf
sup
EΘ [U − L] ≥ (IU − IL ) 1 − 2α − Dχ2 (PU , PL ) .
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ,µ)
[L,
L U

Given two edge sets E1 , E2 , we denote the pre-distance on the graph G between E1 and
E2 as dG (V1 , V2 ) = dG (V (E1 ), V (E2 )). Combining (S.8) with Lemma S.3, the proof of Lemma
S.2 can be deduced from the following theorem.
39

Theorem S.4. Given graphs G0 = (V, E0 ) and G1 , . . . , GN , we denote the difference edge
set as C = {E(Gj )\E(G0 )}N
j=1 . Given an edge set S ∈ C, we denote AS as the adjacency
matrix of S. We also define A0 as the adjacency matrix of G0 and AS,S 0 = A0 + AS + AS 0 .
Let VS,S 0 = {V (E0 ∪ S) ∩ V (S 0 )} ∪ {V (E0 ∪ S 0 ) ∩ V (S)}. Suppose the following assumption
holds:
A1: Denote the uniform maximum degree as Γ = maxS,S 0 ∈C kAS,S 0 k1 and uniform spectral
norm as Λ = maxS,S 0 ∈C kAS,S 0 k2 . We further define
R = max
0

S,S ∈C

|S ∩ S 0 |
|VS,S 0 |

and B = max
0

S,S ∈C




(Γ2 |VS,S 0 |) ∧ Λ4 .

Suppose S 0 is uniformly sampled from C. If for any fixed S 
∈ C, V (S) can be split into
`
` groups: V (S) = ∪j=1 Vj (S), so that the random variables 1(VS,S 0 ∩ Vj (S) 6= ∅) j∈[`]
with respect to a uniformly sampled S 0 from C are negatively associated. In other words,
for any pair of disjoint sets I, J ⊆ [`] and any pair of coordinate-wise nondecreasing
functions f, g we have:
 
 

0
0
Cov f 1(VS,S ∩ Vj (S) 6= ∅) j∈I , g 1(VS,S ∩ Vj (S) 6= ∅) j∈J
≤ 0.
Denote the largest cardinality of vertices as Vmax = maxS∈C maxj |Vj (S)|. Assume the

−1
following holds: maxS∈C ES 0 |VS,S 0 |
→ ∞,
µ≤

r

v


u
u log  maxS∈C ES 0 |VS,S 0 |−1
−1
t
R 1−C
∧ √
and θ ≤
∧ µ.
B
4nVmax R
2 2Γ

Under either Setting A or B, for the parameters Θ0P= µA0 , ΘS = µA0 + θAS for all S ∈ C,
the χ2 -divergence between PL = PΘ0 and PU = N1 S∈C PΘS satisfies
lim Dχ2 (PU , PL ) = 0.

n→∞

We defer the proof of Theorem S.4 to Section S.2.4 and continue the proof of Lemma S.2.
Our strategy is to show that the conditions in Lemma S.2 satisfy the ones in Theorem S.4
correspondingly. We first bound the norms of the adjacency matrices in Theorem S.4. Let
GL and {Ej }N
j=1 be the construction in Lemma S.2. We have Γ = max1≤j,k≤N kAEj ,Ek k1 ≤
2 maxj dmax (Gj ). Moreover, since {Gj }N
j=1 are R-hollow, by Definition 6.1, we also have the
graphs (V, Ej ) and (V, Ej ∪ Ek ) are 2R-hollow for any 1 ≤ j =
6 k ≤ N . According to Lemma
S.6, we have
q
q
max kAEj k2 ≤ 4R max dmax (Gj ) and max kAEj ,Ek k2 ≤ 4R 2 max dmax (Gj ). (S.9)
1≤j≤N

j

1≤j,k≤N

j

Moreover, as |Aj | ≤ R, since Gj is hollow, we also have |Ej | ≤ R|Aj | ≤ R2 . Now we verify
40

A1. First we describe how to construct G0 , G1 , . . . , GN . We begin by splitting the vertices
into two parts V L and V \V L . Let G0 = GL = (V, E L ). Next, we randomly sample |V U |
vertices from the vertex set V \V L . Denote as Ve the random vertex set we have sampled.
We also sample one anchor set Aej where e
j follows uniform distribution from {1, . . . , N }. We
e
aim to connect V to V L using the pattern of Gej . In specific, since |Ve | = |V U |, there exists
a unique one-to-one mapping π : Aej ∪ V U → Aej ∪ Ve such that π(u) = u if u ∈ Aej and if
u ∈ V L , π(u) ∈ Ve with π(u) < π(v) if and only if u < v for any u, v ∈ V U . Given Ve and Aej ,
we construct the edge set
e = {(π(u), π(v)) | (u, v) ∈ E L ∪ Ee}.
E
j

e ∪ E L ) is isomorphic to Ge. We construct G1 , . . . , GN for all
e = (V, E
Then the graph G
j
e
e
e for
possible such G by enumerating V and Aej . The edge set C then contains the edge set E
all possible vertex set Ve ⊆ V \V L and anchor set Aej .
We will now prove that the quantity R in (6.1) is bounded. Due to the construction of
C for all S, S 0 ∈ C and the fact that dG0 (Ej , Ek ) = ∞ for all ∀1 ≤ j 6= k ≤ N , we have
VS,S 0 = V (S) ∩ V (S 0 ). Therefore, we obtain that
|S|
1
|S ∩ S 0 |
|S ∩ S 0 |
≤ max
≤ max
= max
≤ R,
S∈C |V (S)|
S,S 0 ∈C |VS,S 0 |
S,S 0 ∈C |V (S) ∩ V (S 0 )|
2

(S.10)

where we used the fact that the graph (V (S) ∩ V (S 0 ), S ∩ S 0 ) is isomorphic to a subset of the
R-hollow graph Gj for some 1 ≤ j ≤ N . Therefore, 1/2 ≤ R ≤ R.
Next we show that there exists a division of V (S) satisfying the negative association.
c
Given any fixed S ∈ C, we split V (S) into V (S) ∩ V L and V (S) ∩ V L . Let S 0 be uniformly
sampled from C. Since VS,S 0 = V (S) ∩ V (S 0 ), by the construction above, it is simple to see
that, the variables
c

{1(VS,S 0 ∩ V 0 6= ∅) | V 0 = V (S) ∩ V L or V 0 = {v} for v ∈ V (S) ∩ V L }
c

= {1(V (S) ∩ V (S 0 ) ∩ V L = ∅)} ∪ {1(v ∈ V (S)) | v ∈ V (S 0 ) ∩ V L }.

The above variables are negatively associated, since by our construction, 1(V (S)∩V (S 0 )∩V L =
∅) is independent of the remaining random variables, and the others are induced by a
hypergeometric distribution (Joag-Dev and Proschan, 1983). It is further simple to evaluate
the expectation:
ES 0 |VS,S 0 | = ES 0 |V (S) ∩ V (S 0 )|
= ES 0 |V (S) ∩ V (S 0 ) ∩ V L | +

X

c

v∈V (S 0 )∩V L

41

ES 0 [1(v ∈ V (S))] ≤

|V U |2
maxj |Aj |
+
.
N
d − |V L |

Since we assume maxj |Aj | ≤ R, N ≥ dγ , |V U | = o(d1/2 ) and |V L |/d < 1, we have

−1
log max ES 0 |VS,S 0 |
≥ C log d → ∞.
S∈C

By (S.9) and Γ ≤ 2 maxj dmax (Gj ), we have

B ≤ Λ4 ≤ CR4 max d2max (Gj ).
j

Combining with Vmax ≤ maxj |Aj | ≤ R and 1/2 ≤ R ≤ R by (S.10), we can reduce the rate
in A1 to
r
R 1 − C −1
CR−3/2
∧ √
≥
B
maxj dmax (Gj )
2 2Γ
v


u
r
u log  maxS∈C ES 0 |VS,S 0 |−1
t
log d
∧µ≥C
∧ µ.
4nVmax R
n

Therefore, the construction in Lemma S.2 can be reduced to A1 in Theorem S.4, and therefore
for Θ0 = µA0 , Θj = µA0 + θAEj for 1 ≤ j ≤ N we have
lim Dχ2 (PU , PL ) = 0, where PL = PΘ0

n→∞

N
1 X
P Θj .
and PU =
N j=1

Combining (S.8) with Lemma S.3 again, we prove Lemma S.2.

S.2.3

Proofs of Theorem 6.2

The proof of Theorem 6.2 is same as the one of Lemma S.2. We just set θ in the proof of Lemma
S.2 as µ = θ. We change the parameters in Theorem S.4 into Θ0 =P
θA0 , ΘS = θA0 + θAS
for all S ∈ C. Considering two distributions PL = PΘ0 and PU = N1 N
j=1 PΘj , Theorem S.4
gives us limn→∞ Dχ2 (PU , PL ) = 0. Applying Lemma S.3, we have
q


b − L]
b ≥ (IU∗ − IL∗ ) 1 − 2α − Dχ2 (PU , PL ) → (IU∗ − IL∗ )(1 − 2α).
inf
sup
EΘ [U
bU
b ]∈I(I,α) Θ∈Us (I ∗ ,I ∗ ;θ)
[L,
L U

42

We now start to prove Theorem 6.2.


b − I(Θ) ≥
inf
sup
EΘ U
b ∈U (I,α) Θ∈Us (I ∗ ,I ∗ ;θ,µ)
U
L U

≥

≥

inf

inf

b ∈U (I,α) I(Θ)=I ∗
U
L



b < IU∗ ]) − IL∗
b = IU∗ ] + IL∗ PΘ U
sup (IU∗ PΘ U

b ∈U (I,α) I(Θ)=I ∗
U
L

inf


b] − I∗
sup EΘ U
L


b = I ∗ ].
sup (IU∗ − IL∗ )PΘ U
U

b ∈U (I,α) I(Θ)=I ∗
U
L

(S.11)


b = I ∗ ] by Theorem S.4. Since I is hollow, similarly to the proof
We aim to bound PΘ U
U
of Lemma S.2, we can construct Θ0 , Θ1 , . . . , ΘN ∈ Us (IL∗ , IU∗ ; θ, µ) satisfying I(Θ0 ) = IL∗
∗
2
and
PI(Θj ) = IU for all 1 ≤ j ≤ N and the χ -divergence between PL = PΘ0 and PU =
1
S∈C PΘS satisfies
N
lim Dχ2 (PU , PL ) = 0.
(S.12)
n→∞

Next notice that
b < I ∗ )| ≤ TV(PL , PU ) ≤
b < I ∗ ) − PU (U
|PL (U
U
U

q
Dχ2 (PL , PU ),

where the next to last inequality simply follows by the definition of total variation norm and
the last inequality is due to Cauchy-Schwartz. Hence we have:

b = IU∗ ] ≥ 1 − PL (U
b < IU∗ )
sup PΘ U
∗
I(Θ)=IL

q
b < I∗ )
≥ 1 − Dχ2 (PL , PU ), −PU (U
U
q
q
∗
b
≥ 1 − sup PΘ (U < IU ) − Dχ2 (PL , PU ) ≥ 1 − α − Dχ2 (PL , PU ).
∗
I(Θ)=IL

Combining the above inequality with (S.12) and (S.11), we prove Theorem 6.2.

S.2.4

Proof of Theorem S.4

The proof of the theorem mainly relies on the following proposition.
Proposition S.5. Let G0 , G1 , . . . , GN and C be the same as Theorem S.4. Define the
e 0 = (µ/θ)A0 , and A
e S,S 0 = A
e 0 + AS + AS 0 . For all S, S 0 ∈ C we denote:
matrices A
VS,S 0 |S := V (E0 ∪ S 0 ) ∩ V (S) = VS,S 0 ∩ V (S).

Then for any collection of vertex buffers V = {VS,S 0 }S,S 0 ∈C and any of the following two

43

choices:
Setting 1: HS,S 0 =
Setting 2: HS,S 0 =

(|VS,S 0 |S | ∧ |VS,S 0 |S 0 |)kAS k2 kAS 0 k2
e S,S 0 k2 ;
and KS,S 0 = 2kA
2
e
kAS,S 0 k
2

|VS,S 0 |S ||VS,S 0 |S 0 |
e S,S 0 k2
kA

and

1

when the signal strengths satisfies

θ ≤ µ,

e S,S 0 k1 .
KS,S 0 = 2kA

1 − C −1
µ≤ √
,
2 2kAS,S 0 k1

(S.13)

2
we have for ΘP
0 = µA0 , ΘS = µA0 + θAS for all S ∈ C, the χ -divergence between PL = PΘ0
1
and PU = N S∈C PΘS satisfies

 

0
1 X
HS,S 0 (θKS,S 0 )2(dG0 (S,S )∨1+1)
0 2
Dχ2 (PL , PU ) ≤
exp n |S ∩ S |θ +
− 1.
|C|2 S,S 0 ∈C
2(dG0 (S, S 0 ) ∨ 1 + 1)

We defer the proof of proposition to Section S.2.4.1 and first present the proof of Theorem S.4.
Proof of Theorem S.4. Using Proposition S.5 it suffices to control the expression:
 

0
1 X
HS,S 0 (θKS,S 0 )2(dG0 (S,S )∨1+1)
0 2
exp n |S ∩ S |θ +
− 1,
|C|2 S,S 0 ∈C
2(dG0 (S, S 0 ) ∨ 1 + 1)
Note that by the definition of B we have:


2
2
0
0
0
0
max
(kA
k
kA
k
kA
k
)
∧
(|V
|kA
k
)
≤ B.
S 2
S 2
S,S 2
S,S
S,S 1
0
S,S ∈C

Therefore using Proposition S.5 it suffices to control:



1 X
2
2
.
exp |VS,S 0 |S |nθ R + Bµ
Dχ2 (PL , PU ) =
|C|2 S,S 0 ∈C
First note that by |VS,S 0 |S | =

P

j∈[`]

|Vj (S) ∩ VS,S 0 |S |, we have:

 
X

1 X
2
2
Dχ2 (PL , PU ) ≤
exp nθ R + Bµ
|Vj (S) ∩ VS,S 0 |S | .
|C|2 S,S 0 ∈C
j∈[`]

Denotep
by PS 0 the measure induced by drawing S 0 uniformly from C. Under the assumption: µ < R/B, and using the fact that the random variables {1(VS,S 0 ∩ Vj (S) 6= ∅)}j∈[`]
44

are negatively associated for every fixed S ∈ C, we obtain:
hX
h
ii
2
log Dχ2 (PL , PU ) ≤ max
log ES 0 exp(2|Vj (S) ∩ VS,S 0 |S |Rnθ )
S∈C

j∈[`]

hX
h
ii
2
0
0
0
0
≤ max
log exp(2|Vj (S)|Rnθ )PS (Vj (S) ∩ VS,S |S 6= ∅) + (1 − PS (Vj (S) ∩ VS,S |S 6= ∅)
S∈C

j∈[`]

≤ exp(2RVmax nθ2 ) max ES 0
S∈C

X

j∈[`]

1(Vj (S) ∩ VS,S 0 |S 6= ∅) ≤ exp(2RVmax nθ2 ) max ES 0 |VS,S 0 |,
S∈C

where the expectation ES 0 is taken with respect to a uniform draw of S 0 ∈ C. The first
inequality above is due to negative association, the second inequality is due to log(1 + x) ≤ x.
Recalling that Vmax = maxS∈C maxj |Vj (S)|, we have for values of θ
v

 v


u
u
u log [maxS∈C ES 0 |VS,S 0 |]1/2 [maxS∈C ES 0 |VS,S 0 |]−1
u log [maxS∈C ES 0 |VS,S 0 |]−1
t
t
θ≤
=
,
2nVmax R
4nVmax R
we have Dχ2 (PL , PU ) ≤ exp([maxS∈C ES 0 |VS,S 0 |]1/2 ). The proof is now completed by an
application of Lemma S.3.
S.2.4.1

Proof of Proposition S.5

The proof of Proposition S.5 follows the same strategy of the proof of Proposition C.1 in Neykov
e 0 = (µ/θ)A0 ,
et al. (2016). However, the main difference is that our adjacency matrices A
e S,S 0 = A
e 0 + AS + AS 0 have weights on edges while Proposition C.1 in Neykov et al.
and A
(2016) handles the adjacency matrices all have the same weight one. This makes our proof
different in a few places and to make our proof self-contained, we give a complete proof with
both the same and different parts comparing to the proof of Proposition C.1 in Neykov et al.
(2016).
In the first step we construct a set of parameters. Define Θ0 = I+µA0 , ΘS = I+µA0 +θAS ,
ΘS,S 0 = I + µA0 + θ(AS + AS 0 ), for S, S 0 ∈ C and some θ > 0. For any S, S 0 ∈ C we have:
e 0 k2 , kA
e 0 + AS k2 , kA
e S,S 0 k2 ) ≤ kA
e S,S 0 k1
max(kA
e 0 k1 , kA
e 0 + AS k1 , kA
e S,S 0 k1 ) ≤ kA
e S,S 0 k1 ,
max(kA

e 0, A
e 0 + AS and A
e S,S 0 are symmetric and by Hölder’s inequality for any symmetric
since A
p
matrix A we have kAk2 ≤ kAk1 kAk∞ = kAk1 .
We can make sure that the matrices Θ0 and ΘS fall into the sets Us (IL∗ , IU∗ ; θ, µ) and
Us (IL∗ , IU∗ ; θ, µ) respectively, and in addition the matrix ΘS,S 0 is strictly positive definite if θ ≤
1−C −1
µ < kA
. Thus by assumption the graphs Θ0 ∈ Us (IL∗ , IL∗ ; θ, µ) and ΘS ∈ Us (IL∗ , IU∗ ; θ, µ)
S,S 0 k1
for all S ∈ C. In addition this implies that the matrices Θ0 , ΘS , ΘS,S 0 are strictly positive
definite for any S, S 0 ∈ C.
45

In the second step we bound the χ2 -divergence from below. It suffices to bound:


n/2 
n/2
det(ΘS )
det(ΘS 0 )
det(Θ0 )
det(ΘS,S 0 )
 X
∞

n
(−θ)k  e k
k
k
k
e
e
e
,
= exp
Tr AS,S 0 + A0 − (A0 + AS ) − (A0 + AS 0 )
2 k=1 k

For any k ∈ N we have the following bound:

e 0 + AS )k − (A
e 0 + AS 0 )k ) ≥ 0.
e k − (A
ek 0 + A
Tr(A
0
S,S

Same as the proof of Proposition C.1 in Neykov et al. (2016), we still consider three cases:
(1) k < 2(dG0 (S, S 0 ) + 1), (2) k < 4 and k ≥ 2(dG0 (S, S 0 ) + 1) and (3) k ≥ 4 and k ≥
2(dG0 (S, S 0 ) + 1). For k < 2(dG0 (S, S 0 ) + 1), the above is in fact an equality since if the
e 0 , AS , AS 0 or A
e S,S 0 with length smaller than
length of any weighted walk contained in A
0
0
2(dG0 (S, S ) + 1) cannot contain two edges in S and S , and hence will cancel out in the
expression. On the other hand, when k < 4 and k ≥ 2(dG0 (S, S 0 ) + 1), we have
e2 + A
e 2 0 − (A
e 0 + AS )2 − (A
e 0 + AS 0 )2 ) ≤ 4|S ∩ S 0 |,
Tr(A
0
S,S

(S.14)

e 2 0 − (A
e 0 + AS )2 − (A
e 0 + AS 0 )2 ) ≤ HS,S 0 Kk 0 ,
e2 + A
Tr(A
0
S,S
S,S

(S.15)

This is because every length 2 closed walk in (S.14), must have one edge in S and one
edge in S 0 .
In the third step we check that:

for any of the two settings below

Setting 1: HS,S 0 =
Setting 2: HS,S 0 =

(|VS,S 0 |S | ∧ |VS,S 0 |S 0 |)kAS k2 kAS 0 k2
e S,S 0 k2 ;
and KS,S 0 = 2kA
2
e
0
kAS,S k
2

|VS,S 0 |S ||VS,S 0 |S 0 |
e S,S 0 k2
kA

and

1

e S,S 0 k1 .
KS,S 0 = 2kA

We begin with showing a similar result as Eq.(C.6), Neykov et al. (2016) but for weighted
graphs. Given weighted adjacency matrices A1 , . . . Aj and let wii as the number of weighted
closed walks starting and ending at i and the `-th edge belongs to the `-th adjacency matrix
for ` ∈ [j]. We have
Y
wii = Aii ≤ kAk2 ≤
kA` k2 .
(S.16)
`∈[j]

46

We aim to prove that
ek + A
e k 0 − (A
e 0 + AS )k − (A
e 0 + AS 0 ) k )
Tr(A
0
S,S

h 2 k (|V 0 | ∧ |V 0 0 |)kA k kA 0 k i
S 2
S 2
S,S |S
S,S |S
2
e S,S 0 kk .
kA
≤
2
2
e
kAS,S 0 k2

(S.17)

Since the trace of a weighted adjacency matrix, sums all weighted closed walks of length
k in the graph. It suffices to bound the number of closed walks containing both edges in S
and S 0 since a walk is counted on the LHS of (S.17) if and only if it contains both edges in S
and S 0 . Recall that GS = (V, E0 ∪ S), GS 0 = (V, E0 ∪ S 0 ).
(k)
e S,S 0 )}. Given any length k closed walk
Denote CS,S 0 = {closed walks C of length k on G(A
C = v1 → v2 → . . . → vk , let vt be its t-th vertex and let (vt , vt+1 ) be its t-th edge. In the
special case of t = 0, (vk−1 , vk ) is the 0-th edge.
For any vertex v ∈ VS,S 0 and any 1 ≤ t1 6= t2 ≤ k, we first count the number of closed

(k)
walks in the set Ck (v, t1 , t2 ) = C ∈ CS,S 0 v is the t1 -th vertex on C, the t1 -th edge on C
belongs to S Q
and the t2 -th edge on C belongs to S 0 . For a closed walk C ∈ G(AS,S 0 ) denote
with |C|W = e∈C {AS,S 0 }e the weighted length of the closed walk. Following (S.16), we have
X

C∈Ck (v,t1 ,t2 )

e S,S 0 kk−2 .
|C|W ≤ kAS k2 kAS 0 k2 kA
2

(S.18)


(k)
Similarly, we define Ck0 (v, t1 , t2 ) = C ∈ CS,S 0 v is the t1 -th vertex on C, the (t1 − 1)-th edge
on C belongs to S and the t2 -th edge on C belongs to S 0 . We also have
X

C∈Ck0 (v,t1 ,t2 )

e S,S 0 kk−2 .
|C|W ≤ kAS k2 kAS 0 k2 kA
2

We notice that the set comprised of closed walks containing v and edges from both S and S 0
satisfies
[


(k)
Ck (v) = C ∈ CS,S 0 v ∈ C, C ∩ S 6= ∅ and C ∩ S 0 6= ∅ ⊆
Ck (v, t1 , t2 ) ∪ Ck0 (v, t1 , t2 ) .
1≤t1 6=t2 ≤k

Therefore, we can control the number of such closed walks by
 
X
k
e S,S 0 kk−2 .
|C|W ≤ 2
kAS k2 kAS 0 k2 kA
2
2
0
C∈Ck (v,t1 ,t2 )∪Ck (v,t1 ,t2 )

(k)

By the definition of VS,S 0 , each closed walk C in CS,S 0 containing edges from both S and
S 0 , has a vertex v ∈ C belonging to VS,S 0 |S , which is also a vertex of an edge in S. Therefore,
we have the set of closed walks contains edges both from S and S 0 .

47


(k)
Ck = C ∈ CS,S 0 C ∩ S 6= ∅ and C ∩ S 0 6= ∅ ⊆
P

This implies that C∈Ck |C|W ≤ |VS,S 0
we immediately obtain:
X

C∈Ck

[

v∈VS,S 0 |S

Ck (v).

(S.19)


e S,S 0 kk−2 . By symmetry
∩ V (S)| · 2 k2 kAS k2 kAS 0 k2 kA
2

|C|W ≤ (|VS,S 0 ∩ V (S)| ∧ |VS,S 0

 
k
e S,S 0 kk−2 ,
∩ V (S )|) · 2
kAS k2 kAS 0 k2 kA
2
2
0

which completes the proof of (S.17).
For Setting 2, the proof is similar to Setting 1. We have two vertices in VS,S 0 and each
e S,S 0 k1 weighted vertices, where the weight corresponds to the type of
vertex can go into kA
edge we can go on — µ or θ. Since two of the vertices are on fixed positions we are left with
e S,S 0 kk−2 vertices to complete the path. Since there are at most k(k − 1) ≤ 2k possibilities
kA
1
for the positions of two vertices, and there are at least the 2 edges which are coming out of
the two fixed vertices have weight θ, we complete the proof for Setting 2.
Finally we complete the proof by showing that if {HS,S 0 , KS,S 0 }S,S 0 ∈C satisfies either
Setting 1 or 2, we can bound the χ2 -divergence as the proposition. In particular, we have
∞
X
k=1



ek 0 + A
e k − (A
e 0 + AS )k − (A
e 0 + AS 0 )k /k
θk Tr A
S,S
0

≤ 2|S ∩ S 0 |θ2 +
≤ 2|S ∩ S 0 |θ2 +

X

HS,S 0 k −1 (KS,S 0 )k

2|k, k≥2(dG0 (S,S 0 )∨1+1)

0

2HS,S 0 (KS,S 0 θ)2(dG0 (S,S )∨1+1)
.
2(dG0 (S, S 0 ) ∨ 1 + 1)

We therefore complete the proof.

S.2.5

Auxiliary Results on Graph Spectral

In this section, we prove the following lemma of the operator norm of hollow graph.
Lemma S.6 (Sparse Graph Lemma). If we have an R-hollow graph G with maximum degree
dmax (G) and adjacency matrix A we have:
p
kAk2 ≤ 2R dmax (G).

Proof. Using a result of Nash-Williams (1964) which follows by earlier results of NashWilliams (1961), we know that there exists a decomposition of any sparse graph in at most
R forests. Since the graph is of degree at most dmax (G) each of the forests is also of at
most dmax (G) degree. We will now argue that for any forest graph F with bounded
by
p
dmax (F ) degree the largest eigenvalue of its adjacency matrix is bounded by 2 dmax (F ).
48

First recall that for two non-intersecting graphs on the same vertex set G0 and G00 we have
kAG0 ∪G00 k2 ≤ kAG0 k + kAG00 k2
To show the bound we proceed by decomposing the graph F , by greedily constructing
star graphs. To describe the procedure it suffices to consider the case where F is a tree since
it can be applied to all sub-trees of a forest F in parallel. Starting from a root of F split
out the root and all of its children. Recursively moving in a breadth first search manner
add edges by the following procedure: do not take any vertex who has already been taken
into account, and for any vertex who has not been taken into account take all edges from
him to his children. Clearly two passes are enough to partition the forest into two graphs of
non-intersecting
star-graphs. It is simple to check that a star graph of maximum degree dmax
√
has dmax as the operator norm of its adjacency matrix. This implies that
p
kAF k2 ≤ 2 dmax (F ),
as claimed. Putting everything together we have:
p
kAk2 ≤ 2R dmax (G).

p
Remark S.2.1. Lemma S.6 is developed with the regime R = o( dmax (G)) in mind.
Otherwise it is clear that always:
kAk2 ≤ dmax (G).

S.3

Power Analysis of the Tests

In this section, we discuss the power analysis for the test ψα obtained from Algorithm 2.
Under the alternative H1 : P(Θ) = 1, we define the parameter space
n
o
G1 (θ; P) = Θ ∈ Us P(G(Θ)) = 1 and 0 max 0 min0 |Θe | ≥ θ .
(S.20)
E ⊆E(Θ),P(E )=1 e∈E

If Θ ∈ G1 (θ; P), by (S.20), its induced graph G(Θ) = (V, E(Θ)) must has a sub-edge set
E0 ⊆ E(Θ) such that P(E0 ) = 1 and the minimal signal strength on E0 is larger than θ.
Theorem S.7 (Power analysis). Suppose Θ ∈ Us and (3.5) is satisfied. Under the alternative
hypothesis H1 : P(G) = 1, there exists a positive constant C such that for any α ∈ (0, 1)
with 1/(α(d ∨ n)) = o(1),
lim

inf

n→∞ Θ∈G1 (Cτn ;P)

where τn =

PΘ (ψα = 1) = 1,

p
log d/n.
49

(S.21)

Notice that the parameter space G1 (θ; P) defined in (S.20) is larger than the parameter
space such that Θ has the minimal signal strengths θ on its support E(Θ). Namely, we have
n
o
G1 (θ; P) ⊇ G10 (θ; P) = Θ ∈ Us | P(G(Θ)) = 1 and min |Θe | ≥ θ .
(S.22)
e∈E(Θ)

The parameter space G10 (θ) is usually considered for the power analysis of the global hypothesis
tests (Han and Liu, 2014) or high dimensional two sample tests (Cai et al., 2013, 2014). For
example, Han and Liu (2014)pconsider the null hypothesis H0 : Σ = Id and show their test is
powerful if minj6=k |Σjk | > C log d/n for some constant C > 0. Theorem S.7 demonstrates
that for the power analysis of graph property test, it suffices to impose the minimal signal
strength condition on a subgraph E 0 of the true support E(Θ) if P(E 0 ) = 1. The following
proposition gives a concrete characterization of G1 (θ).
Proposition S.8. Given the graph G(Θ) = (V, E(Θ)), we set the weights on the edge (j, k)
as |Θjk | for any j, k ∈ V . We order the weights |Θe | for e ∈ V × V as |Θe[1] | ≥ . . . ≥

|Θe[d(d−1)/2] |. Let t∗ = arg min t | P(E[t] ) = P({e[1] , . . . , e[t] }) = 1 . If the property P is
monotone, we have

G1 (θ; P) = Θ ∈ Us |Θe[t∗ ] | ≥ θ .
Proof. By the definition in (S.20), since P(E[t∗ ] ) = 1, we have

G1 (θ; P) ⊇ Θ ∈ Us |Θe[t∗ ] | ≥ θ .

It suffices to prove the other direction. If Θ ∈ G1 (θ; P), there exists E 0 ⊆ E(Θ) with
P(E 0 ) = 1 such that mine∈E 0 |Θe | ≥ θ. Since P is monotone, we have P(E[t∗ ] ∪ E 0 ) = 1. As
mine∈E 0 |Θe | ≥ θ and E[t∗ ] contains the top t∗ largest weight edges, we have |Θe[t∗ ] | ≥ θ. This
completes the proof of the proposition.
Remark S.3.1. Proposition S.8 implies that we can add the edges in E(Θ) from the largest
to the smallest until we stop at the t∗ -th step when P(E[t∗ ] ) = 1. For example, for the
connectivity property PConn(1) , we greedily add edges in order until the graph is connected.
Comparing to the procedure of Kruskal’s algorithm (Kruskal, 1956), let EMSF be the edge set
of the maximum spanning tree of G(Θ) with Θ as the weights, we can have
n
o
G1 (θ; PConn,−1 ) = Θ ∈ Us min |Θe | ≥ θ .
e∈EMSF

This coincides with the alternative set for the connectivity test in Neykov et al. (2016). For
the maximum degree property PDeg,k , Neykov et al. (2016) consider the alternative set G10 (θ) in
(S.22). Proposition S.8 implies that our test is asymptotically powerful in a larger parameter
space. In specific, we order the weights of the neighbor of node j as |Θj(1) | ≥ . . . ≥ |Θj(d) |.
For for any k ∈ [1, d), we have
n
o
G1 (θ; PDeg,k ) = Θ ∈ Us PDeg,k (G(Θ)) = 1 and max |Θj(k) | ≥ θ .
j∈V

50

From Theorems 4.1 and S.7, we show that the test ψα obtained from Algorithm 1 is
optimal for the four examples we discuss in Section 3.2: PConn,−k , PDeg,k and PSig,−k . To
achieve this goal, we define the risk of a test ψ as
Rθ (ψ, P) = sup PΘ (ψ = 1) +
Θ∈G0

sup
Θ∈G1 (θ;P)

PΘ (ψ = 0),

(S.23)

where the parameter spaces G0 and G1 (θ; P) are defined in (4.3) and (S.20) respectively. We
say that the hypotheses H0 : Θ ∈ G0 v.s. H1,θ : Θ ∈ G1 (θ; P) are asymptotically separated
by a test ψ if limn→∞ Rθ (ψ, P) = 0. On the other hand, H0 and H1,θ are asymptotically
inseparable if
lim inf inf Rθ (ψ, P) = 1.
n→∞

ψ

From Theorems 4.1 and S.7, the test ψα obtained from Algorithm 1 can asymptotically
separate H0 and H1,θ for any monotone property P if the signal strength is strong enough.
In specific, we have the following corollary directly from (4.2) and (S.21).
Corollary S.9. Under the same conditions as Theorem S.7, for any monotone property P,
we choose the level of significance αn ∈ (0, 1) such that 1/(αn (d ∨ n)) = o(1) and αn = o(1).
The hypotheses H0 : Θp∈ G0 v.s. H1,θ : Θ ∈ G1 (θ; P) can be asymptotically separated by the
test ψαn when θ ≥ C1 log d/n for some universal constant C1 > 0.

On the other hand, the lower bound on the signal strength developed in Neykov et al.
(2016) shows that the signal strength in Corollary S.9 is optimal for the properties including
connectivity, maximum degrees and
pcyclic graph. In specific, they show that there exists a
constant C2 > 0 such that if θ ≤ C2 log d/n, and log d/n = o(1),
√ for the following properties:
(1) PConn,−k for k ∈ [1, d); (2) PCycle ; (3) PDeg,k for k ∈ [1, d) and k log d/n = o(1), the
hypotheses H0 : Θ ∈ G0 v.s. H1,θ : Θ ∈ G1 (θ; P) are asymptotically inseparable. For PSig,−k
for k ∈ [0, d), we can establish the same lower bound. See Section S.3.1.1 in the appendix for
details.

S.3.1

Proofs of Lower Bound of Tests

The lower bounds for the three properties: PConn,−k , PCycle and PDeg,−k are proved in Neykov
et al. (2016). Following a similar procedure, we will prove the lower bound for PSig,−k .
For the self-consistency of the paper, we introduce the Le Cam’s lemma (LeCam, 1973)
first. A standard application of Le Cam’s lemma is for the lower bound on when a null
hypothesis with a single parameter can be separated from the alternative. Under that case,
the Le Cam’s lemma selects a set of parameters in the alternatives such that they deviate
from the null parameter far away enough. In specific, let Θ0 ∈ G0 and Θ(1) , . . . , Θ(K) ∈ G1 (θ).
Let PnΘ be the product measureP
of the i.i.d. samples {X1 , . . . , Xn } ∼ N (0, Θ−1 ). We denote
n
K
−1
the mixture measure P = K
j=1 PΘ(j) . Le Cam’s lemma gives the following lower bound
of the risk (after adapting our notations).
51

Lemma S.10. Let Rθ (ψ, P) be the risk defined in (S.23), we have
inf Rθ (ψ, P) ≥
ψ

PnΘ0 (ψ

1
= 1) + P (ψ = 0) ≥ 1 −
2
n

Z  n 2
1/2
dP
n
dP
−
1
.
Θ0
dPnΘ0

(S.24)

However, under the property testing problems, we have both composite null hypothesis
and composite alternatives. When the null hypothesis contains richer parameter space that
the alternative, we should instead choose a parameter from alternatives ΘA ∈ G1 (θ). On the
other hand, we collate Θ(1) , . . . , Θ(K) ∈ G0 . Le Cam’s lemma also gives the following lower
bound of the risk:

inf Rθ (ψ, P) ≥
ψ

S.3.1.1

PnΘA (ψ

1
= 1) + P (ψ = 0) ≥ 1 −
2
n

Z 
n
1/2
dP 2 n
dPΘA − 1
.
dPnΘA

(S.25)

Proof of Lower Bound on Singletons

For the property of isolated nodes, we consider two cases: (1) k ∈ [0, d/2) and (2) k ∈ (d/2, d).
As an atom to construct the matrices in (S.25), we consider the precision matrix

ΘChain(d)




1 θ
0
θ 1 θ



.. ..


.
.
= θ
.


.. ..

.
. θ
0
θ 1

(S.26)

The precision matrix above induces a chain with d nodes and d − 1 edges.
Case 1: k ∈ [0, d/2). For this case, we apply Le Cam’s Lemma in (S.25) by selecting a
ΘA ∈ G1 (θ) and {Θ(1) , . . . , Θ(K) } ∈ G0 . We set


ΘA = diag ΘChain(2) , . . . , ΘChain(2) , ΘChain(d−k−2b(d−k)/2c) , Ik ∈ Rd×d ,
|
{z
}
b(d−k)/2c matrices

where d − k − 2b(d − k)/2c) = 2 if d − k is even and 3 otherwise. We also denote Θ(j) =
Θ0 − θE2j,2j+1 for 1 ≤ j ≤ b(d − k)/2c − 1.
Denote fj for 1 ≤ j ≤ b(d − k)/2c − 1 as the density of PnΘ(j) and f0 for PnΘ0 . Similar to
the previous proofs, we first bound the square term
Z

fj2
dµ =
f0



det(Θ(j) )2
det(ΘA ) det(2Θ(j) − ΘA )

n/2

52

=



(1 − θ2 )2b(d−k)/2c−4
(1 − θ2 )2b(d−k)/2c−2

n/2

=

1
,
(1 − θ2 )n

and the summation
1
b(d − k)/2c2

b(d−k)/2c Z

X

fj2
dµ ≤ (b(d − k)/2c)−1 exp(1 + nθ2 ) ≤ exp(− log d + nθ2 ),
f0

j=1

p
where the last inequality is due to k ≤ d/2. Therefore, if θ ≤ C2 log d/n for some sufficiently
small C2 > 0,
b(d−k)/2c Z
X
fj2
1
dµ → 0.
b(d − k)/2c2 j=1
f0
For the cross term, we have
Z

fj fk
dµ =
f0




det(Θ(j) ) det(Θ(k) )
det(ΘA ) det(Θ(j) + Θ(k) − ΘA )

n/2

(1 − θ2 )b(d−k)/2c−2 (1 − θ2 )b(d−k)/2c−2
=
(1 − θ2 )b(d−k)/2c−1 (1 − θ2 )b(d−k)/2c−3

n/2

= 1.

Therefore, we conclude that
1
∆=
b(d − k)/2c2

b(d−k)/2c Z

X
j=1

fj2
2
dµ +
f0
b(d − k)/2c2

X

1≤j<k≤b(d−k)/2c2

Z


fj fk
dµ − 1 → 0.
f0

Case 2: k ∈ [d/2, d) We apply the Le Cam’s Lemma in(S.24) by choosing a Θ0 ∈ G0 and
{Θ(1) , . . . , Θ(K) } ∈ G1 (θ).
We set


Θ0 = diag Ik+1 , ΘChain(2) , . . . , ΘChain(2) , ΘChain(d−k−1−2b(d−k−1)/2c) ∈ Rd×d ,
|
{z
}
b(d−k−1)/2c matrices

and Θ(j) = Θ0 + θE2j,2j+1 for 1 ≤ j ≤ b(k + 1)/2c.
Using the same notations, we again first bound the square term
Z

fj2
dµ =
f0
=





det(Θ(j) )2
det(Θ0 ) det(2Θ(j) − Θ0 )

n/2

(1 − θ2 )2b(d−k−1)/2c+2
(1 − θ2 )b(d−k−1)/2c (1 − θ2 )b(d−k−1)/2c+1

53

n/2

=

1
,
(1 − θ2 )n/2

and since k ∈ (d/2, d), we have
1
b(k + 1)/2c2
If θ ≤ C2

b(k+1)/2c Z

X
j=1

fj2
dµ ≤ (b(k + 1)/2c)−1 exp(1 + nθ2 /2) ≤ exp(− log d + nθ2 /2).
f0

p
log d/n for some sufficiently small C2 > 0,
1
b(k + 1)/2c2

b(k+1)/2c Z

X
j=1

fj2
dµ → 0.
f0

We can calculate the cross term
n/2

Z
det(Θ(j) ) det(Θ(k) )
fj fk
dµ =
f0
det(ΘA ) det(Θ(j) + Θ(k) − ΘA )

n/2
(1 − θ2 )b(d−k−1)/2c+1 (1 − θ2 )b(d−k−1)/2c+1
=
= 1.
(1 − θ2 )b(d−k−1)/2c (1 − θ2 )b(d−k−1)/2c+2
Therefore, we have
1
∆=
b(d − k)/2c2
S.3.1.2

b(d−k)/2c Z

X
j=1

fj2
2
dµ +
f0
b(d − k)/2c2

X

1≤j<k≤b(d−k)/2c2

Z


fj fk
dµ − 1 → 0.
f0

Auxiliary Results on Matrix Determinant

Lemma S.11. Let

√
√
1 − 1 − 4θ2
1 − 4θ2
and r2 =
.
(S.27)
r1 =
2
2
For the matrices ΘChain(d) defined in (S.26) and Ej,j+1 = ej eTj+1 + ej+1 eTj , we have for all
1 ≤ j ≤ d − 1,
1+

det(ΘChain(d) ) = det(ΘChain(d) − 2θEj,j+1 ) =
Proof. For a tridiagonal matrix Mk :


r1d+1 − r2d+1
.
r1 − r2


a1 b 1
0
 c 1 a2 b 2



.
...


c2 . .
Mk := 
,


..
..

.
. bk−1 
0
ck−1 ak
54

we expand the determinant on the first row:
det(Mk ) = ak det(Mk−1 ) − ck−1 bk−1 det(Mk−2 ).
Plugging in ci = bi = θ, i ∈ [k − 1] and ai = 1, i ∈ [k] we obtain:
det(ΘChain(i) ) = det(ΘChain(i−1) ) − θ2 det(ΘChain(i−2) ).

(S.28)

Writing out the characteristic polynomial of this recursive relationship, it is easy to check
that it has two roots: r1 and r2 . Finally checking the initial conditions det ΘChain(1) = 1,
det ΘChain(2) = 1 − θ2 yields the desired formula.
For det(ΘChain(d) −2θEj,j+1 ) observe that cj = bj = −θ, which doesn’t change the recursive
relationship (S.28), and hence the determinant is the same.

S.4

Proof of Lemma S.1

We first consider a special case that I(Tµ (Θ)) = I(∅). Since I is monotone, according to
Algorithm 1, IbL ≥ I(Tµ (Θ)) = I(∅) almost surely and (S.6) is trivially true.
Therefore, in the following of the proof, we consider the case I(Tµ (Θ)) > I(∅). This
implies that there exists a non-empty edge set E00 such that
p
E00 ⊆ E(Tµ (Θ)), I(E00 ) = I(Tµ (Θ)) and min0 |Θe | > C log d/n,
(S.29)
e∈E0

where the constant C is determined later. By I(E00 ) > I(∅), similar to (S.4), we claim
that I(E00 ∩ CI (∅)) = I(E00 ). To prove this claim, we find a subgraph E000 ⊂ E00 such that
e ⊂ E000 , we have I(E)
e < I(E000 ). Such graph E000 can be
I(E000 ) = I(E00 ) and for any E
constructed by deleting edges from E00 and making the invariant equal to I(E00 ) until it is
impossible to further delete edges without reducing the value of the invariant. By Definition
3.1, we have E000 ⊆ CI (∅) which implies E000 ⊆ E00 ∩ CI (∅). As I(E000 ) = I(E00 ), by monotone
property, we prove the claim that I(E00 ∩ CI (∅)) = I(E00 ). Consider the following event
n
o
√
b d | > c(α, CI (∅)) .
E1 =
min
n|
Θ
e
0
e∈E0 ∩CI (∅)

According to Algorithm 1, the rejected set in the first iteration is
√
b d | > c(α, CI (∅))}.
E1 = {e ∈ CI (∅) : n|Θ
e

Under the event E1 , we have E00 ∩ CI (∅) ⊆ E1 and since I(E00 ∩ CI (∅)) = I(E00 ), we have
I(E1 ) = I(E00 ), which makes IbL ≥ I(E00 ) = I(Tµ (Θ)). Therefore, we have
P(I(Tµ (Θ)) ≤ IbL ) ≥ P(E1 ).
55

(S.30)

We will bound P(E1 ) next. We have


b d − Θe | ≤ c(α, CI (∅)) .
P(E1 ) ≥ P min0 |Θe | > 2c(α, CI (∅)) and max |Θ
e
e∈V ×V

e∈E0

(S.31)

We next estimate the rate of c(α, CI (∅)). By Lemma E.4. of Neykov et al. (2016), we
have with probability 1 − 1/d3 , there exists a constant C1 ,

b d − Θjk + ΘT ΣΘ
b k − ek | ≤ C1 s log d .
max |Θ
jk
j
j,k∈[d]
n

(S.32)

Notice here we change the tail probability to 1 − 1/d3 from 1 − 1/d in Lemma E.4. of
Neykov et al. (2016), which can be easily done by changing the value of C1 because the
dimension d only appears in the logarithmic term in (S.32). Similar trick also apply to the
tail probabilities below. Since Θ ∈ Us and kΘk2 ≤ ρ, we have kΘTj XX T Θk kψ1 ≤ C2 ρ2 . By
the maximal inequality (see Lemma 2.2.2 in van der Vaart and Wellner (1996)), we have for
some constant C3 > 0
r



b k − ek | > C3 ρ2 log d
P max |ΘTj ΣΘ
j,k∈[d]
n
r
n

1X T
log d 
= P max
≤ 1/d3 .
(Θj Xi XiT Θk − E[ΘTj Xi XiT Θk ]) > C3 ρ2
j,k∈[d] n
n
i=1
Let C0 = C1 + C3 and we have


b d − Θjk | > C0
P max |Θ
jk
j,k∈[d]

r

log d 
2
< 3.
n
d

(S.33)

Applying (3.5) and (S.33), for any fixed α ∈ (0, 1) and sufficiently large d, n such that
P(TV ×V > c(α, V × V )) > α and 2/d3 ≤ α, we have
r
log d
.
c(α, CI (∅)) ≤ c(α, V × V ) ≤ C0
n
p
We set the constant C = 2C0 in µ ≥ C log d/n and it follows from (S.29) and (S.33) that
r


log d
d
b
min
|Θ
|
>
2C
>
2c(α,
C
(∅))
and
P
max
|
Θ
−Θ
|
≤
c(α,
C
(∅))
> 1−2/d3 .
e
0
I
e
I
e
e∈V ×V
e∈E00 ∩CI (∅)
n
Combining the above inequalities with (S.30) and (S.31), we have
P(I(Tµ (Θ)) ≤ IbL ) ≥ P(E1 ) > 1 − 2/d3 .

Since the right hand side of the above inequality is universal for any Θ ∈ UI (IL∗ , IU∗ ; θ), we
56

complete the proof of the lemma.

S.5

Quantile Estimation for Graphical Models

In this section, we first provide concrete examples satisfying (3.5) under Gaussian graphical
model. We then generalize our method to non-Gaussian
graphical models.
b = n−1 Pn Xi X T . We use the CLIME estimator
Let the sample covariance be Σ
i
i=1
proposed by Cai et al. (2011) to estimate Θ. It can in fact be generalized to other estimators
and we will discuss the extension in Section 5. In order to achieve asymptotic normality from
b Neykov et al. (2015) propose the following debiased estimator
Θ,
bd = Θ
b jk − Θ
b T (Σ
bΘ
b k − ek )/(Θ
bTΣ
b j)
Θ
jk
j
j

(S.34)

√ bd
and show that n(Θ
N (0, Var(ΘTj XX T Θk )) under certain regularity conditions.
jk − Θjk )
Based on the debiased estimator, we are able to test
edges. For any edge set
√ onbmultiple
d
E ⊆ V × V , we consider the statistic TE = max(j,k)∈E n(Θ
−
Θ
).
jk We apply the Gaussian
jk
multiplier bootstrap (Chernozhukov et al., 2013) by constructing the random variable
n

T

B

1 X bT
b k − ek )ξi .
= sup √
Θj (Xi XiT Θ
n
(j,k)∈E
i=1

B
and we estimate the conditional quantile by c(α, E) = inf{t ∈ R | P(|Tjk
| > t | {Xi }ni=1 ) ≤ α)}.
Applying the theory developed by Chernozhukov et al. (2013), it can be shown that c(α, E)
is a valid quantile estimator. For the CLIME estimator, Neykov et al. (2016) prove that it
is true if Θ ∈ Us and (log(dn))6 /n + s2 (log dn)4 /n = o(1). The scaling condition is to show
that c(α, E) obtained from the Gaussian multiplier bootstrap is a good quantile estimator of
√ bd
maxe∈E n(Θ
e − Θe ). Similar condition is also considered in Equation (23) in Chernozhukov
et al. (2013) for multiple hypothesis testing. The first scaling term (log(dn))6 /n = o(1)
comes from the Berry-Essen bound of the Gaussian approximation for the maximum of a
sum of high dimensional random vectors. The second term s2 (log dn)4 /n = o(1) comes from
√ bd
approximating the statistic n(Θ
e − Θe ) by a summation of i.i.d. random vectors. Similar
condition can be found in Condition (M) of Chernozhukov et al. (2013).
For the CLIME estimator in Gaussian graphical model, Neykov et al. (2016) prove that
the quantile estimator in Section 3 satisfies (3.5).
In fact, if we apply the theory of Gaussian multiplier bootstrap developed in Chernozhukov
et al. (2013), (3.5) is satisfied for many other estimators for Gaussian graphical model. The
proof in Neykov et al. (2016) essentially shows that (3.5) holds if we use a precision
matrix
p
b
b
estimator Θ in (S.34) satisfying the three conditions: (1) kΣ − Σkmax = OP ( log d/n); (2)
p
p
b
b Θ−I
b d kmax = OP ( log d/n). These conditions (1)-(3)
kΘ−Θk
log d/n) and (3) kΣ
1 = OP (s
can also be established under the irrepresentability condition for the graphical Lasso estimator
(Yuan and Lin, 2007; Ravikumar et al., 2011) and neighborhood selection (Meinshausen and
Bühlmann, 2006).

57

For non-Gaussian graphical models, (3.5) can also established. For example, for the
Gaussian copula graphical model, Gu et al. (2015) propose a pseudo maximal log-likelihood
estimator based on Kendall’s tau statistics and show (3.5). For the semiparametric exponential
family graphical model, Yang et al. (2014b) also show (3.5) based on a semi-paramtric
estimator. Applying the high dimensional debiasing methods (Zhang and Zhang, 2013;
van de Geer et al., 2014; Javanmard and Montanari, 2014; Ning and Liu, 2014) and Gaussian
multiplier bootstrap (Chernozhukov et al., 2013), (3.5) can also potentially be shown for
many other graphical models, thus Theorem 5.1 shows the proposed skip-down method can
also be directly applied.

58

