Partial correlation graphs and the neighborhood lattice∗

arXiv:1711.00991v1 [] 3 Nov 2017

Arash A. Amini, Bryon Aragam, Qing Zhou
November 6, 2017

Abstract
We define and study partial correlation graphs (PCGs) with variables in a general
Hilbert space and their connections to generalized neighborhood regression, without making any distributional assumptions. Using operator-theoretic arguments, and especially
the properties of projection operators on Hilbert spaces, we show that these neighborhood
regressions have the algebraic structure of a lattice, which we call a neighborhood lattice.
This lattice property significantly reduces the number of conditions one has to check when
testing all partial correlation relations among a collection of variables. In addition, we
generalize the notion of perfectness in graphical models for a general PCG to this Hilbert
space setting, and establish that almost all Gram matrices are perfect. Under this perfectness assumption, we show how these neighborhood lattices may be “graphically” computed
using separation properties of PCGs. We also discuss extensions of these ideas to directed
models, which present unique challenges compared to their undirected counterparts. Our
results have implications for multivariate statistical learning in general, including structural
equation models, subspace clustering, and dimension reduction. For example, we discuss
how to compute neighborhood lattices efficiently and furthermore how they can be used to
reduce the sample complexity of learning directed acyclic graphs. Our work demonstrates
that this abstract viewpoint via projection operators significantly simplifies existing ideas
and arguments from the graphical modeling literature, and furthermore can be used to
extend these ideas to more general nonparametric settings.

1

Introduction

Graphical models are a popular tool for representing complex joint distributions and have
found numerous applications in computational biology, computer vision, signal processing, and
natural language processing, just to name a few [KF09; WJ08; Fri04; LMP01]. Undirected
graphical models, also known as Markov networks, encode conditional independence statements satisfied by a joint distribution, via separation in an undirected graph [Lau96]. In this
sense, we can refer to the corresponding graphs as conditional independence graphs, or CIGs.
In general, it is difficult to estimate conditional independence without specific distributional
assumptions. Common assumptions include Gaussianity and various closely related extensions
(e.g. nonparanormal and elliptical distributions, Gaussian copulas [HD12; HD13; LLW09]). On
the other hand, it is fairly straightforward to estimate second-order information, for example
covariances and partial correlations among variables, even if the data is non-Gaussian. In fact,
∗

This work was supported by NSF grant IIS-1546098

1

sample covariances and estimated partial correlations, via node-wise regression, are among the
most common practical tools for measuring dependence among variables. In the absence of
any distributional assumptions, these quantities are what we can reliably estimate.
In this paper, we study partial correlation graphs, or PCGs, as the minimal-assumption
counterparts of CIGs. In the context of PCGs, independence is replaced with orthogonality,
and conditional independence is replaced with a corresponding notion of partial (or conditional )
orthogonality. We show that the theory for PCGs can be developed in parallel with that of
CIGs, by interpreting PCGs as describing partial orthogonality statements among families of
projection operators associated with the underlying variables. This algebraic viewpoint allows
us to define generalized versions of the Markov property—which we call L2 Markov properties—
and derive many of the related properties via independent arguments not relying on properties
of CIGs. In doing so, we extend the “classical” theory of conditional independence in graphical
models to the weaker notion of partial orthogonality in an abstract Hilbert space, which as we
will show applies to problems of general interest to statisticians. It is worth noting that while
partial correlation coefficients are well-known from regression analysis, even the “usual” notion
of a PCG, as a stand-alone concept, is little known, despite having appeared in the literature
before (e.g., [WKR13]).
Studying partial orthogonality is naturally related to the so-called neighborhood regression
problem, which has been leveraged with great success in the context of graphical models. More
specifically, given a random vector X = (X1 , . . . , Xd ), one can often reconstruct a Markov
network for X by regressing each node Xj onto the rest of the nodes X−j = {X1 , . . . , Xd } \
{Xj }. This procedure is valid for several classes of distributions including joint Gaussian
models [MB06], Ising models [RWLO10], and exponential random families [YRAL15], as well
as semiparametric families [LLW09]. We note that each of these examples requires strong
distributional assumptions.
In this paper, we extend the notion of neighborhood regression (Section 4) in two important
aspects. First, we do not restrict our analysis to any specific family of distributions; in fact,
our analysis extends well beyond to the traditional setting of random variables to include
vectors in any separable Hilbert space, where there may be no concept of a distribution.
Second, we study regression of a single variable Xj onto an arbitrary subset of the rest of
the variables: S ⊂ {X1 , . . . , Xd } \ {Xj }. This generality is needed to verify general partial
orthogonality statements involving a pair of variables, as discussed in Section 4. One of the
main contributions of this paper is to show that these neighborhood regression problems have
a rich algebraic structure, namely that they have the structure of a complete, convex lattice
(Theorem 1). This is developed in Section 4.2 and is linked to the separation properties of
the PCG in Section 5.2. The lattice property could potentially lead to substantial savings
when evaluating all possible conditional statements implied by a PCG for a particular node
(Section 4.2). In addition, neighborhood regression onto a general neighborhood S has a
natural connection to directed graphical models and structural equation modeling, as discussed
in Section 6. Our results have direct implications for the computational and sample complexity
of learning directed acyclic graphs (Section 6.2).
We also develop the notion of L2 (Markov) perfectness, the counterpart of the more familiar notion of perfectness (or faithfulness) in the context of CIGs. Under L2 perfectness,
there is a one-to-one correspondence between separation in the PCG and partial orthogonality
statements implied by the variables. As a result of independent interest, we establish a substantial generalization of a result due to [LM07] that implies the existence of an L2 perfect
2

covariance matrix (or Gram matrix in general) for every possible graph structure (Theorem 2).
We strengthen this result, in Section 5, to show that almost all covariance matrices respecting
a graph structure are L2 perfect for it. Similar results are already known for other classes of
graphical models [SGS00; Peñ11] and our result thus provides a corresponding extension to the
case of undirected graphical models and their L2 extensions described herein.
As far as we know, the lattice property of neighborhood regression has not been noted before
in the literature. This useful property has far-reaching implications in terms of the sample
complexity needed in recovering “independence” structures from high-dimensional data; see the
discussion in Section 6.2. In order to derive this property, we also develop the theory of PCGs
in maximum generality, by assuming the variables to be elements of a separable Hilbert space.
This includes the special case of random variables with finite second moments, but also covers
other objects such as random (or deterministic) vectors, functions and data matrices, once an
appropriate inner product, i.e., a similarity measure, is defined; see examples in Section 3.1.
We give largely self-contained proofs of all the results in this theory using operator-theoretic
arguments. The perfectness result of Section 5 uses a fairly technical extension of the arguments
in [LM07] that invokes ideas from geometric measure theory, and could be of independent
interest.

2

Preliminaries

In this section, we review some preliminaries and background material that is useful for setting
the stage of our general theory. The material on projections in Section 2.3 in particular is
essential for the definitions and results in the sequel.

2.1

Notation

Graph notation. In an undirected graphical model for a random vector X = (X1 , . . . , Xd ),
we identify each random variable Xj , j = 1, . . . , d, with a node in an undirected graph G =
([d], E), where [d] = {1, . . . , d}. Two nodes i and j are adjacent, or neighbors, if (i, j) ∈
E, in which case we write i ∼ j, otherwise i  j. A path from i to j is a sequence i =
k1 , k2 , . . . , kn−1 , kn = j ∈ [d] of distinct elements with (kl , kl+1 ) ∈ E for each l = 1, . . . , n − 1.
Given two subsets A, B ⊂ [d], a path connecting A to B is any path with k1 ∈ A and
kn ∈ B. A subset C ⊂ [d] separates A from B, denoted by A − C − B, if all paths connecting
A to B intersect C (i.e. kl ∈ C for some 1 < l < n), otherwise we write ¬(A − C − B). Implicit
in this definition is that A, B and C are disjoint.
Subset notation. For any A ⊂ [d], we denote XA = {Xi : i ∈ A}. We also use the shorthand
notations: {i} = i and {i, j} = ij, A ∪ {i} = Ai, A ∪ B = AB and so on. In addition, we let
[d]S = [d]\S = {1, . . . , d}\S. Common uses of these notational conventions are: [d]j = [d]\{j}
and [d]ij = [d] \ ij = [d] \ {i, j}. For a matrix Σ ∈ Rd×d , and subsets A, B ⊂ [d], we use ΣA,B for
the submatrix on rows and columns indexed by A and B, respectively. Single index notation
is used for principal submatrices, so that ΣA = ΣA, A . For example, Σi,j is the (i, j)th element
of Σ (using the singleton notation), whereas Σij = Σij, ij is the 2 × 2 submatrix on {i, j} and
{i, j}. Similarly, ΣAi,Bj is the submatrix indexed by rows A ∪ {i} and columns B ∪ {j}.

3

2.2

Graphical models

For completeness, we recall here some of the traditional definitions from the graphical modeling
literature. This is mainly to provide a basis for comparison, and is not needed for most of the
results we prove. A more thorough treatment can be found in [KF09; Lau96].
In the context of undirected graphs, there are three so-called Markov properties of interest:
G satisfies the
• pairwise Markov property if (i, j) ∈
/ E implies that Xi ⊥
⊥ Xj | X[d]ij ,
• local Markov property if each node is conditionally independent of all other variables
given its neighbours,
• global Markov property if A − C − B implies that XA ⊥
⊥ XB | XC .
The notation X1 ⊥
⊥ X2 | X3 means X1 is (probabilistically) independent of X2 conditioned on
X3 . In general, these conditions are not equivalent and we have global =⇒ local =⇒ pairwise,
however, for positive distributions, these conditions are in fact equivalent [KF09]. A graph G
satisfying the pairwise Markov property is sometimes called a conditional independence graph
(CIG) for the distribution of X.
The Markov properties go in one direction: The graphical criterion (i.e. separation) implies
a probabilistic conclusion (i.e. conditional independence). The converse is not true in general;
when it is, the graph G is called perfect with respect to the joint distribution of X. Specifically,
G is called perfect if
A − C − B ⇐⇒ XA ⊥
⊥ XB | XC .
Remark 1. In the literature on graphical models, there are two related notions of perfectness (as defined above) and faithfulness. Conceptually, these terms mean the same thing—
namely that there is a one-to-one correspondence between properties of a graph and conditional
independence—and the only distinction regards what kind of graphical model is being used.
The term “perfect” is more commonly used in reference to undirected graphs, whereas “faithful” is more common with directed acyclic graphs (DAGs). To add to the confusion, faithfulness
is sometimes called DAG perfectness. The key difference to remember is that in undirected
graphical models, graph separation corresponds to conditional independence, whereas in directed graphical models, the more complicated notion of d-separation corresponds to conditional independence. Indeed, the graphical modeling literature distinguishes even more general
types of graphs—each with their own Markov properties—such as chain graphs [Fry90; CW93],
ancestral graphs [RS02], and other mixed graphs [LS16]. For more details on the relationship
between directed and undirected graphs, see [KF09].

2.3

The lattice of projections

We will assume the reader is familiar with the basic theory of Hilbert spaces and their projections; a detailed introduction to these topics can be found in [FW10; Bla06]. For a (separable)
Hilbert space H, let B(H) be the space of bounded linear operators on H. For an operator
P ∈ B(H), let ran(P ) := P H := {P x : x ∈ H} denote its range and P ∗ its adjoint, defined
via the relation hx, P ∗ yi = hP x, yi for all x, y ∈ H. Here and in the sequel, we use h·, ·iH or
the shorthand h·, ·i to denote the inner product of H.
4

We recall that P ∈ B(H) is an orthogonal projection iff it is self-adjoint and idempotent:
P ∗ = P = P 2 . The set of orthogonal projections in B(H), denoted as P(H), is of particular
importance in this paper. P(H) can be partially ordered as follows:
Lemma 1. For P, Q ∈ P(H), the following are equivalent:
(a) P = P Q,

(b) P = QP,

(c) ran(P ) ⊂ ran(Q).

When any of these conditions hold we write P ≤ Q.
The equivalence of (a) and (b) follows from self-adjointness of orthogonal projections. Note
that when P and Q are both projections, P Q is not necessarily a projection (unless P and Q
commute). The above ordering makes P(H) into a complete lattice, that is, a partially ordered
set S in which each subset has both a supremum (join) and an infimum (meet) in S. For
P, Q ∈ P(H), we denote the supremum with P ∨ Q and the infimum with P ∧ Q. We have
P ∧ Q = the projection onto ran(P ) ∩ ran(Q)
P ∨ Q = the projection onto the closed linear span of ran(P ) ∪ ran(Q).
We also let P ⊥ := I − P , the orthogonal complement of P . Note that P ∨ P ⊥ = I (the identity
operator) and P ∧ P ⊥ = {0}. Also, P ≤ Q iff P ⊥ ≥ Q⊥ . See for example [FW10, Section 5,
p. 24] and [Bla06, Section II.3.2, p. 78] and the references therein.
We often consider the concrete example where H = L2 (P), the space of random variables
(on a probability space with measure P) with finite second moments. When applied to a
random variable X, P ⊥ X = X − P X may be interpreted as the residual between X and its
projection P X. For this reason, when x is a vector in an arbitrary Hilbert space H we will
refer to P ⊥ x as the residual of the projection P x in the sequel. We will also need the following
notion of orthogonality of operators:
Lemma 2. For P, Q ∈ B(H), the following are equivalent:
(a) hP x, Qyi = 0, ∀x, y ∈ H,

(b) P ∗ Q = Q∗ P = 0,

(c) ran(P ) ⊥ ran(Q).

When any of the conditions above hold, we call P and Q orthogonal and denote this by P ⊥ Q.

3

Partial orthogonality

In contrast to the classical theory of graphical models which works with random variables,
we will develop our theory in the abstract setting of a general Hilbert space H. We begin by
generalizing the usual notion of a PCG to this setting, and then extend the Markov properties
defined in Section 2.2 based on this extension. The notion of partial orthogonality (cf. (5))—
which is well-defined in any Hilbert space—will play a prominent role here and in the rest of
the paper.

3.1

Abstract partial correlation graphs

We start with an abstract generalized definition of PCGs which applies to vectors with elements
in a general Hilbert space H, and can be considered a minimal-assumption version of conditional
independence graphs (CIGs). We then discuss how by specializing to the L2 space of random
5

variables (as a concrete Hilbert space), we can recover the usual definition of PCGs familiar
from regression analysis. Throughout, we write Hd = {(x1 , . . . , xd ) : xi ∈ H, i ∈ [d]} for some
positive integer1 d, and a separable Hilbert space H. We recall that [d]ij = {1, . . . , d} \ {i, j}.
Fix a vector x = (x1 , . . . , xd ) ∈ Hd , and for any S ⊂ [d], let PS ∈ P(H) denote the
projection onto the span of xS = {xi , i ∈ S}.
Definition 1 (Pairwise L2 Markov, PCG). We say that x satisfies the pairwise L2 Markov
property w.r.t. G if
i  j in G ⇐⇒ Pi PS⊥ Pj = 0, for S = [d]ij ,

(1)

in which case G is called a partial correlation graph (PCG) of x.
For H = L2 (P), we recover the usual notion of PCG for random variables:
Example 1. For a probability measure P, let H = L2 (P), the space of square-integrable random
variables: Xi ∈ L2 (P) iff EXi2 < ∞. The inner product is hX, Y iL2 = EXY . Consider zeromean random variables X1 , . . . , Xd ∈ L2 (P). In this case, PS corresponds to the L2 projection
on the span of XS , or regressing on (covariates) Xi , i ∈ S in statistical terms. Similarly, PS⊥ Xi
is the residual after regressing Xi on XS .
Now, fix some S ⊂ [d]. The usual partial correlation between Xi and Xj given XS is the
correlation between the residuals PS⊥ Xi and PS⊥ Xj , that is, hPS⊥ Xi , PS⊥ Xj iL2 . Thus, the partial
correlation is zero iff PS⊥ Xi ⊥ PS⊥ Xj (orthogonality in the L2 sense). Since span{PS⊥ Xj } =
ran(PS⊥ Pj ), using Lemma 2(c), the partial correlation is zero iff PS⊥ Pi ⊥ PS⊥ Pj . This in turn
is equivalent to Pi PS⊥ Pj = 0, by Lemma 2(b). Thus, in this case Definition 1 defines the PCG
as the graph where the missing edges between a pair of nodes (i, j) correspond to zero partial
correlation between Xi and Xj given the rest of the variables Xk , k ∈ [d]ij . This is the usual
notion of the PCG for a collection of random variables.
In Example 1, it is well-known that if X = (X1 , . . . , Xd ) has a Gaussian distribution, then
the PCG defined above is in fact a CIG. However, the PCG is defined for any (joint) distribution
on X whose marginals have finite second moments, and in general it may not correspond to a
CIG. (It is usually sparser than a CIG.).
Going back to the general setup of Definition 1, let Σ = (hxi , xj iH ) ∈ Rd×d be the Gram
matrix of the underlying variables x = (xj , j ∈ [d]). Although the PCG is defined using
projection operators, we now show that it is completely determined by the Gram matrix.
Unless otherwise stated, we will assume the following from now on:
Σ := (hxi , xj iH )  0.

(A1)

The following result is proved in Appendix A.2:
Lemma 3. |ΣSi,Sj | = 0 is equivalent to Pi PS⊥ Pj = 0, for all i, j and S ⊂ [d]ij .
It is worth noting that the lemma is not restricted to random variables and holds in the general
Hilbert space setup of Definition 1. Since PCGs are preserved under Hilbert space isometries
(Appendix A.5), by passing to the case where x is a zero-mean Gaussian random vector with
covariance Σ (i.e., a special case of Example 1), and using the known results on Gaussian
1

We assume d < ∞ for simplicity, though most of our results hold also for d = ∞.

6

Figure 1: Examples of functions in H 1 ([0, 1]) that form a 6-nodes star-shaped PCG. Each row corresponds to one star-shaped graph, and in each case the function that acts as the central node is shown
with dashed red line. See Example 2 for the details of the constructions.

pairwise conditional independence [Lau96, Prop. 5.2], we conclude that (1) in Definition 1 is
in fact equivalent to
i  j in G ⇐⇒ [Σ−1 ]i,j = 0

(2)

or equivalently |ΣSi,Sj | = 0 where S = [d]ij . That is, Lemma 3, applied with with S = [d]ij ,
recovers this well-known result. Note, however, that Lemma 3 is stronger than (2), since it
establishes the equivalence for any S ⊂ [d]ij . Let us now give more concrete examples of the
abstract PCG of Definition 1, which go beyond the familiar case of Example 1, and also show
the utility of Lemma 3.
Example 2 (PCG for deterministic objects). The general setup of Definition 1 allows us to
define PCGs for purely deterministic objects. For example, let us take H = Rn with the
usual Euclidean inner product and take {xj , j ∈ [d]} to be a collection of vectors in Rn . The
resulting PCG encodes a form of partial orthogonality among these vectors. For example, let
{e1 , . . . , en } be an orthonormal basis of Rn and let xj = e1 + ej for j ∈ [d], assuming n ≥ d.
It is clear that for j 6= 1 and any subset A ⊂ [d]j containing 1, PA xj = P1 xj and P1⊥ xj = ej .
Hence, for distinct i, j 6= 1 and 1 ∈ A ⊂ [d]ij , we have xTi PA⊥ xj = xTi P1⊥ xj = 0. In other words,
“conditional” on any subset [d]ij containing 1, i and j are orthogonal, i.e., there is no edge
between them in the PCG. One can argue with some more work that all the other edges (i.e.,
between 1 and any other node) are present. Hence the PCG is star-shaped with node 1 at the
center. The corresponding Gram matrix and its inverse are




1
1
u
γ −uT
−1
Σ=
, Σ =
,
(3)
−u
I
γ − kuk2 u (γ − kuk2 )I + uuT
where γ = d/4 and u = 12 1d−1 . Here, 1d−1 is the all ones vector in Rd−1 , and we have
γ − kuk2 = 1/4. The star shape of the PCG is immediately clear from (3) in view of (2), or
equivalently Lemma 3.
Similarly, one can take H = F for a Hilbert space of functions and let {xj } be functions
in F. For example, take H = H 1 ([0, 1]), the Sobolev space of order 1, defined as the space of
absolutely continuous functions f : [0, 1] → R with
f 0 ∈ L2 ([0, 1]), and f (0) = 0.
R 1 derivative
0
0
0
0
The inner product is hf, giH := hf , g iL2 ([0,1]) = 0 f (t)g (t)dt, and the corresponding norm
is a measure of smoothness of the functions. An orthonormal basis for this space is ek (t) =
µk sin(t/µk ) for k = 1, 2, . . . , where µk = 2/((2k − 1)π). The exact same construction used
earlier, namely xj (t) = e1 (t) + ej (t), t ∈ [0, 1], j ∈ [d], can be used to obtain a star PCG for
7

the underlying functions, since one gets the exact same Gram matrix as in (3). In this case, in
contrast to the finite-dimensional setting, we can even take d = ∞ to have a star PCG with
infinitely many leaves. The top row in Figure 1 shows the functions in this construction for
d = 6. Also shown as the second row is the collection xj (t) = e6 (t) + ej (t), j = 1, . . . , 6 which
has the same star-shaped PCG with e6 as the central node.
Example 3 (PCG for random vectors). For a probability measure P, and n ∈ N, let H =
2
(L2 (P))n , the L2 space of random vectors X ∈ Rn with bounded
Pnsecond moments: EkXk2 < ∞.
The inner product here is given by hX, Y iH = EhX, Y iRn = i=1 E(Xi Yi ) where h·, ·iRn is the
usual Euclidean inner product in Rn . Fix integers d and m, and take a sequence {ukj , k ∈
kj , k ∈ [m], j ∈ [d]} ⊂ L2 (P) of
[m], j ∈ [d]} ⊂ Rn of deterministic vectors, a sequence
Pm {Z
kj
zero-mean (scalar) random variables, and let Xj = k=1 Z ukj ∈ Rn for j = 1, . . . , d. Clearly
each Xj ∈ (L2 (P))n and we have
hXi , Xj iH =

m X
m
X

0

E[Z ki Z k j ]huki , uk0 j iRn ,

i, j ∈ [d]

k=1 k0 =1
0

which can model complex correlations both via the covariance matrices Sk,k0 = (E[Z ki Z k j ]) ∈
Rd×d and the relative positions of {ukj } in Rn . Letting Vj = span{u1j , . . . , umj }, we observe
that Xj ∈ Vj , that is Xj is a random element of Vj . Thus, we can use this setup to simultaneously model subspace clustering and dimension reduction, especially when assuming m  n
so that Vj s are of much lower dimension than the ambient space, and when some pairs of
subspaces are either identical or have large intersections. For example, to see the application
to clustering, consider the case where Vj = V (1) for some js and Vj = V (2) for others, with
V (1) 6= V (2) . Then, the vectors {Xj } are naturally divided into two clusters, and their PCG
will contain information about the two clusters.
The PCG of Definition 1 for X = (X1 , . . . , Xd ) has a random vector, Xj , on each node. The
geometry of the subspaces V1 , . . . , Vd affects this PCG of X. For example, when the subspaces
are mostly orthogonal, there will be a lot of missing edges in the PCG: If Vi ⊥ Vj for i ∈ A
and j ∈ B, then, hXi , Xj iH = 0 for all i ∈ A, j ∈ B, irrespective of the correlation structure
of Z. Lemma 3 (with S = [d]ij ), then, implies that there is no edge between A and B in the
PCG (since the inverse Gram matrix has a zero block on indices A × B).
Example 4 (PCG for random functions). In the setup of Example 3, we can replace Rn with
a Hilbert space F of real-valued functions on domain X , that is, RX . We take H = (L2 (P))X ,
a space of random functions (or random processes) on domain X , with hF, GiH = EhF, GiF .
Similar to Example 3, take a deterministic sequence {fkj ∈ F, k ∈ [m], P
j ∈ [d]}, (with m = ∞
m
kj
a possibility when F is an infinite-dimensional space) and let Fj =
k=1 Z fkj . All the
discussions of the Example 3 go through. The PCG in this case has random functions {Fj } as
its nodes. Depending on what the inner product of F measures, the absence of an edge could
have different meanings. For example, if F is a Sobolev space where the norm measures some
form of smoothness of the function, an absence of an edge between Fi and Fj includes some
information about the relative smoothness of the pair of functions.
For example, let F be the Sobolev space of Example 2 with basis functions e1 , e2 , . . .
given there. Consider the star construction with e1 at the center but with random weights:
0
xj = Z 1j e1 + Z 2j ej for j ∈ [d]. Let Sk,k0 = (E[Z ki Z k j ]) ∈ Rd×d for k, k 0 = 1, 2. Note that

8

T . Let δ
S2,1 = S1,2
i,j = 1{i 6= j} be the Kronecker delta function. It is not hard to see that



T
Σi,j := hxi , xj i = S1,1 + S1,2
δi,1 + S1,2 δ1,j + S2,2 δi,j i,j ,

i, j ∈ [d].

Thus, the off-diagonal elements of the first row of Σ (Σ1,i , i 6= 1) are determined by the
T , while the off-diagonal elements of Σ outside the first row
corresponding elements of S1,1 + S1,2
and column are determined by those of S1,1 alone. It is clear for example, that elements of
S2,2 besides [S2,2 ]1,1 have no effect on the Gram matrix. The deterministic case of Example 2
corresponds to S1,1 = S1,2 = all-ones d × d matrix. The other extreme S1,1 = S1,2 = Id leads
to the empty PCG. Many other possibilities exist between these two extremes.
We note that Examples 3 and 4 provide useful statistical frameworks for modeling multivariate dependencies among random functions or other high-dimensional objects, while retaining
some familiar aspects of regression analysis and PCGs. In this sense, they provide avenues
for extending classical multivariate statistical analysis to collections of higher-order objects
(vectors, matrices, functions, etc.).

3.2

Global Markov property

Let us now extend Definition 1. In analogy with the global Markov property in the context of
CIGs, we can define a global notion of the L2 Markov property with respect to a graph:
Definition 2 (Global L2 Markov). Given the setup of Definition 1, we say that x ∈ H satisfies
global L2 Markov property w.r.t. G if
S separates A and B in G =⇒ PA PS⊥ PB = 0.

(4)

In the special case H = L2 (P), this reduces to the global Markov property for an undirected
graphical model, and hence Definition 2 provides a natural generalization of this property to
general Hilbert spaces.
Remark 2. In contrast to Definition 1, the one-sided implication in (4) is in line with the
usual definition for CIGs in the literature. This way, in the Gaussian case, the usual global
Markov property matches the L2 version defined here. The two-sided version of this property
then corresponds to the notion of “perfectness” which will be discussed in detail in Section 5.
Comparing with Definition 1, we could have used a one-sided implication in defining the pairwise property as well, however, this would introduce some unnecessary technicalities involved
with nonuniqueness of the PCG. Our choice of the two-sided implication in the pairwise case
leads to a well-defined PCG (i.e. a unique PCG for any given vector x), which simplifies the
arguments in the sequel.
Since PA PS⊥ PB = PB PS⊥ PA due to self-adjointness of projections, Definition 2 is symmetric
in A and B. We will use the following notational convention
PA ⊥ PB | PS

means

PA PS⊥ PB = 0.

(partial orthogonality)

(5)

Note the use of ⊥ here to denote orthogonality in H, as opposed to ⊥
⊥ which is reserved for
probabilistic independence as usual. This ternary relation among projections is also completely
characterized by the Gram matrix Σ:
9

⊥
Lemma 4. ΣB,A − ΣB,S Σ−1
S ΣS,A = 0 is equivalent to PA PS PB = 0, for disjoint A, S, B ⊂ [d].

This lemma will be proved as part of Proposition 1 (Section 4). We refer to (5) as partial
orthogonality, or conditional orthogonality, a generalization of the notion of partial uncorrelatedness of random variables. Clearly the global L2 Markov property implies the pairwise version
as a special case. The following result, proved in Appendix A.5, establishes the equivalence of
the pairwise and global L2 Markov properties when the covariance matrix is non-degenerate.
Note that this is the L2 analogue of a similar well-known result for CIGs [Lau96, Thm. 3.9,
p. 35].
Lemma 5. Assuming Σ  0, the pairwise L2 Markov property implies the global L2 Markov
property.
The PCG, as well as the pairwise and global L2 Markov properties, can be thought of
as being defined based on (1) a vector x ∈ Hd with a particular Gram matrix Σ, or more
abstractly based on (2) a family of projection operators on the subspaces generated by x. We
have implicitly taken the first viewpoint, in which case we can characterize the PCG in terms
of Σ. There are however subtle differences between (1) and (2). A vector x uniquely identifies
both a Gram matrix Σ and a collection of subspaces, or equivalently a collection of projection
operators {PA }. However, neither Σ nor {PA } uniquely identifies the other. Nevertheless both
are useful in encoding L2 Markov properties as illustrated in Lemma 3. For example, it is clear
from the projection viewpoint, that rescaling any of the components of x does not change the
subspaces and hence the L2 Markov properties. This implies the following:
Lemma 6. DΣD has the same L2 Markov properties as Σ for any diagonal matrix D, with
nonzero diagonal entries.
Although this can be verified directly in terms of Σ, using the characterization of Lemma 4,
the projection viewpoint makes this immediately clear. A major theme of this paper is showing
the usefulness of the projection interpretation in understanding the algebraic features of the
L2 Markov property.
Remark 3. Let us say a few words about the terminology. Throughout, we have used the
term L2 Markov property, while the results hold for any (separable) Hilbert space. Perhaps
a more appropriate name would have been “H Markov”. However, since all separable Hilbert
spaces are isomorphic2 to an L2 space of some probability measure, we have elected to use the
L2 terminology due to its familiarity and ease of recognition.

4

Neighborhood regression

The well-known concept of neighborhood regression provides an alternative characterization
of the partial orthogonality relation (5). As will be shown in this section, we can verify the
relation Pi ⊥ Pj | PS , by looking at the coefficients of the regression of xj onto {xk , k ∈ Si},
as opposed to the residuals.
2
n
In fact, all n-dimensional Hilbert spaces are isomorphic to `n
2 = (R , k · k2 ) and all infinite-dimensional
separable Hilbert spaces are isomorphic to `2 = `∞
,
the
space
of
square-integrable
sequences. Both correspond
2
to L2 spaces associated with counting measures on [n] and N, respectively.

10

4.1

SEM coefficients

In the literature on undirected graphical models, the neighborhood of a fixed node xj is implicitly understood to be the set of all other variables, namely the collection x−j . Here, we extend
the notion of neighborhood to any subset S ⊂ [d]j , which is necessary for evaluating general
conditional orthogonality statements, such as xi ⊥ xj | xS . (See Section 6 for a discussion of
how this general setup is needed for learning directed extensions of the PCG.) At a high-level,
the neighborhood regression problem for the node xj and a subset S ⊂ [d]j is the problem of
finding the linear projection of xj onto xS :
Definition 3. For any S ⊂ [d]j , let
βj (S) :=

argmin
β

∈ Rd ,

kxj − β T xk2H .

(6)

supp(β) ⊂ S

We call βj (S) the structural equation model (SEM) coefficients for variable j regressed on the
variables S.
P
Here, β T x = dj=1 βj xj for any β ∈ Rd and x ∈ Hd . It is not hard to see that [βj (S)]S =
⊥
Σ−1
S ΣS,j (Appendix A.3). In addition, it is possible to write the condition PA PS PB = 0
directly in terms of the SEM coefficients, and also in terms of the Gram matrix Σ. We have
the following generalization of Lemma 3 (proved in Appendix A.3):
Proposition 1. Under (A1), the following are equivalent:
(a) PA PS⊥ PB = 0,
P
(b) [βj (A)]i = k∈S [βj (S)]k [βk (A)]i ,

∀i ∈ A, j ∈ B,

(c) ΣB,A − ΣB,S Σ−1
S ΣS,A = 0 (replaced with ΣB,A = 0 if S = ∅),
(d) [βj (Si)]i = 0, ∀i ∈ A, j ∈ B.
Moreover, for any i, j ∈ [d] and S ⊂ [d]ij , we have
[βj (Si)]i =

hxi , PS⊥ xj iH
.
hxi , PS⊥ xi iH

(7)

We note that (d) can be equivalently written as [βj (Si)]i = [βi (Sj)]j = 0, ∀i ∈ A, j ∈ B,
due to symmetry. Most assertions in Proposition 1 are colloquially known (perhaps except
part (b)). For example, expressions similar to (7) have appeared before [Tia12], going back to
the work of [Cra46] and [Dem69]. Recalling our definition of partial orthogonality in (5), the
equivalence (a) ⇐⇒ (d) established in Proposition 1 shows that to study partial orthogonality
relations it is enough to study neighborhood regression problems:
Corollary 1. To test Pi ⊥ Pj | PS for all S ⊂ [d]ij , it is enough to have {βj (T ) : T ⊂ [d]j }.
Corollary 1 motivates studying the collections {βj (T ) : T ⊂ [d]j }, and it turns out that these
neighborhood regression problems have rich algebraic properties which will be explored in the
next section.

11

4.2

Neighborhood lattice

We now introduce the main object of study in the rest of the paper.
Definition 4 (Neighborhood lattice). For any S ⊂ [d]j , define a collection of subsets by
Tj (S) = {T ⊂ [d]j : PT Pj = PS Pj }.

(8)

In other words, for any j, Tj (S) is the collection of candidate sets T ⊂ [d]j such that the
projection of xj onto {xi , i ∈ T } is invariant. Definition 4 is somewhat abstract, though it
highlights the algebraic nature of the collection Tj (S) and the sufficiency of the projection
operators {PS , S ⊂ [d]} in defining it. Note that Tj (S) as given in (8) is well-defined even
when the Gram matrix Σ is rank deficient. In order to see the usefulness of this definition,
assume in addition that Σ is (strictly) positive definite. Then we have the following alternative
representations of Tj (S):
Tj (S) = {T ⊂ [d]j : βj (T ) = βj (S)}

= T ⊂ [d]j : supp(βj (T )) = supp(βj (S)) .

(9)

To see the first equality in (9), note that βj (S)T x = PS xj . Since the Gram matrix of x is
positive definite, βj (S) = βj (T ) is equivalent to βj (S)T x = βj (T )T x, and hence to PS xj =
PT xj . The result follows since for any operator L, Lxj = 0 is equivalent to LPj = 0. (We
have LPj y = hxj , yiLxj for all y, assuming kxj kH = 1.) The second equality in (9) follows
from the first equality, and positive definiteness of Gram matrix. Note that by definition
supp(βj (S)) ⊂ S. We are primarily interested in cases where supp(βj (S)) is much smaller than
S, and all the other sets T for which supp(βj (T )) is the same as this small set.
Our goal in this paper is to study the algebraic properties of Tj (S), for which representation (8) is very helpful. Throughout, we fix j ∈ [d] and S ⊂ [d]j . Our next result shows
that, Tj (S) is indeed a lattice, as suggested by the name. Recall that a complete lattice is a
partially ordered set, or poset for short, in which all subsets have both a supremum (join) and
an infimum (meet) [Sta97, Section 3.3]. We also need the following definition: Let (P, ≤) be
a poset and C a subposet of P. We say that C is convex (in P) if z ∈ C whenever x < z < y
and x, y ∈ C. A closed interval [x, y] := {z ∈ P : x ≤ z ≤ y} is an example of a convex
subposet [Sta97, Section 3.1].
Theorem 1. Under (A1), Tj (S), ordered by inclusion, is a complete lattice. In particular,
Tj (S) has unique minimal and maximal elements, which we denote by mj (S) and Mj (S),
respectively. Moreover, Tj (S) is convex as a subposet of 2[d]j .
Any finite nonempty lattice is in fact complete. However, the proof we give in Section 8.1
also establishes the result for an infinite collection of variables {xi }. Tj (S) being convex in 2[d]j
means the following: for every two subsets S1 , S2 ∈ Tj (S), and any S 0 ⊂ [d]j , if S1 ⊂ S 0 ⊂ S2 ,
then S 0 ∈ Tj (S). Thus, using the interval notation, we can represent the neighborhood lattice as
Tj (S) = [mj (S), Mj (S)] = {A ∈ 2[d]j : mj (S) ⊂ A ⊂ Mj (S)}.

(10)

In other words, to specify Tj (S), it is enough to specify its minimum and maximum elements. In
Section 5.2, we describe the abstract sets mj (S) and Mj (S) in terms of the PCG G (Theorems 3
and 4), which gives a useful semantic interpretation in terms of separation properties of a graph.
Theorem 1 is in fact a special case of a much more abstract result discussed in Appendix B.
12

11

5
2.0

5

1.0

0.8

0.5
0.0

0.2
0.0

10

−1.0
5

10

−0.4
−0.6
15

15

(a)

5

10

(b)

15

13
9

3

6

2

−0.2

−0.5
15

12

8

0.6

5

0.4

10

4

1.0

1.5

1
10

14

7

15

(c)

Figure 2: A Markov perfect example, with inverse covariance generated randomly: (a) covariance matrix,
(b) inverse covariance matrix, and (c) PCG. In (a) nodes are colored to help graphical computation of
Tj (S) for j = 3 and S = {9, 8, 11, 12, 14}. See Examples 5 and 6.

An alternative way to view Tj (S) is as a collection of subsets of {xi : i ∈ [d]j } that have
the same explaining power as S for xj . This view can be further advanced by removing the
reference to the set S. A node j defines an equivalence relation among subsets of [d]j , where
S, T ⊂ [d]j are equivalent iff PS Pj = PT Pj . We then say that S and T have the same explaining
power for {j}. This relation partitions 2[d]j into equivalence classes, each of which is a complete
lattice according to Theorem 1.
Example 5. Consider the covariance matrix Σ shown in Figure 2(a), with dimension d = 15.
The corresponding PCG is plotted in Figure 2(c). For j = 3 and S = {9, 8, 11, 12, 14}, the minimal set is mj (S) = {9, 12, 14}, and maximal set is Mj (S) = {4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15}.
These can be easily read from the graph as will be described in Section 5.2. Since the lattice can be represented as Tj (S) = [mj (S), Mj (S)], we know for example that {9, 12, 14, 5}
and {9, 12, 14, 10, 13} both belong to Tj (S). Note that these two sets are not comparable in
2[d]j , i.e., Tj (S) is not a chain (or totally ordered set) in 2[d]j . In this case, Tj (S) contains
2|Mj |−|mj | = 28 = 256 subsets, out of a total possible |2[15]3 | = 214 . Regressing j = 3 onto any
of these 256 subsets results in the same SEM coefficients.
Remark 4. It is not hard to see that mj (S) = supp(βj (S)), that is, mj (S) represents the
so-called active set when regressing xj onto xS , which is of course of interest in regression and
graphical models. Thus, there is a one-to-one correspondence between the neighourbohood
lattices Tj (S), the equivalence classes defined above, and the possible active sets for predicting
xj . Furthermore, a consequence of Theorem 1 is that there will be a largest set Mj (S) possibly
larger than the S we started with, regressing onto which has the same active set. Regressing
onto any set strictly larger than Mj (S) will change the active set.

4.3

Computational complexity

Theorem 1, combined with the observations in Remark 4, suggests an intuitive algorithm for
efficiently computing the entire neighborhood lattice Tj (S). Once we have the active set mj (S),
it is enough to compute Mj (S), by sequentially adding the rest of the nodes and either include or
reject them based on whether the active set is changed. Once mj (S) and Mj (S) are computed,
the entire lattice is given by (10). This procedure is outlined formally in Algorithm 1. Since
this algorithm only requires d − 1 − |mj (S)| = O(d) projections, we have the following perhaps
surprising result:
13

Algorithm 1 Compute the lattice Tj (S) for a given j and S ⊂ [d]j .
1: function computeLattice(j, S, Σ)
2:
βj (S) ← computeSEMcoeff(j, S, Σ)
3:
m ← supp(βj (S)).
4:
M ←S
5:
A ← [d] \ (S ∪ {j})
6:
while A 6= ∅ do
7:
k ← (pop first element off A)
8:
P ← M ∪ {k}
9:
c ← computeSEMcoeff(j, P , Σ)
10:
if supp(c) = m then M ← P
11:
end while
12:
return [m, M ]
13: end function
14: function computeSEMcoeff(j,S,Σ)
15:
return βj (S) which is = Σ−1
S ΣS,j on S and 0 otherwise.
16: end function

. This is mj (S).

. Proposal set

Proposition 2. For any j and S ⊂ [d]j , it is possible to compute Tj (S) with O(d) projections.
Since each projection can be computed in polynomial time (in d), a consequence of Proposition 2 is that Tj (S) can be computed in polynomial time. In graphical modeling, it is
of significant interest to learn all possible conditional independence statements of the form
Xi ⊥
⊥ Xj | XS . Likewise, in our more general setting, it is of interest to learn all partial orthogonality statements of the form Pj ⊥ Pi | PS for any i ∈ [d]j and S ⊂ [d]j . By Corollary 1,
for this it is enough to compute the collection {Tj (S) : j ∈ [d], S ⊂ [d]j }. Let T(1) , T(2) , . . . , T(N )
be an enumeration of these lattices. Starting from an arbitrary subset S ⊂ [d]j , say [d]j itself,
we can compute Tj (S) in O(d − |S| − 1) = O(d) projections, using for example Algorithm 1.
This gives us T(1) . Then, we pick another S ∈
/ T(1) , and repeat the process to obtain T(2) . Thus,
we can compute the entire partition into lattice equivalence classes in O(N d) projections. This
provides answers to all partial orthogonality statements of the form Pj ⊥ Pi | PS for any i ∈ [d]j
and S ⊂ [d]j .
Since N could potentially be much smaller than 2d−1 , this procedure could result in substantial savings relative to the naive approach of checking all the 2d−1 possible subsets. For
example, we have the following special case:
Lemma 7. If |mj (S)| ≤ k for all S ⊂ [d]j , then all partial orthogonality statements for the jth
node can be computed in polynomial time, with at most O(dk ) projections.
In other words, as long as no active set for xj has more than k elements, this computation is
polynomial in d. The proof of this lemma follows from the fact that under the assumptions
we have N ≤ kd ≤ dk . Whether there are other assumptions, besides that of Lemma 7, that
could guarantee a polynomial number N of lattice equivalence classes is an interesting open
question.
In addition to providing direct answers to arbitrary partial orthogonality queries, these
computational results also have important implications for the sample complexity of learn-

14

ing directed graphical models. See Section 6 for more details. Finally, R code implementing
Algorithm 1 and more, including the graphical computation of Section 5.2, is available at [Reg].

5

PCGs under Markov perfectness

We now introduce the notion of L2 Markov perfectness, which is the PCG counterpart of the
notion of Markov perfectness in undirected graphical models (or faithfulness in the directed
case). Recall from Definition (4), that under global L2 Markov property, graph separation
implies partial orthogonality. Perfectness upgrades this implication to hold both ways.
Definition 5. We say that x is L2 globally Markov perfect w.r.t. G if
S separates A and B in G ⇐⇒ PA PS⊥ PB = 0.
This notion of perfectness is closely related to the notion of faithfulness in DAGs; see Remark 1.
We often abbreviate “L2 globally Markov perfect w.r.t. G” and just refer to x as perfect or
imperfect. Note that there is no need to specify G either, since it is implied by x, due to
the uniqueness of PCGs according to Definition 1 (see also Remark 2). Since PCGs and L2
Markov properties can be equivalently characterized by the Gram matrix Σ = (hxi , xj iH ) as
discussed in Section 3, we can equivalently talk about perfectness of a Gram matrix Σ. The
corresponding graph is also (uniquely) implied in this case, given by the sparsity pattern of
Σ−1 ; see (2) and Lemma 3. In this section, we will focus on the Gram matrix interpretation
and ask whether a given Σ is perfect or not.

5.1

Prevalence of perfectness

One could ask how prevalent L2 Markov perfectness is. This boils down to the prevalence of the
(usual) Markov perfectness among Gaussian distributions (see the discussion after Lemma 3).
[LM07] shows that for any graph G, there is a regular Gaussian distribution which is Markov
perfect w.r.t. G; this implies that for any potential PCG, there is at least one Gram matrix
Σ and a corresponding random vector which is perfect w.r.t. that PCG. Here, we extend the
argument in [LM07] to show that almost all covariance matrices are L2 Markov perfect. As
discussed earlier, given any positive definite matrix Σ, we can ask whether it is perfect or
not, with the graph G being implicit from the support of Σ−1 . This is the language we use
throughout this section. Our main result on L2 perfectness is the following:
Theorem 2. Let G be an undirected graph on [d], and let A ∈ Rd×d be drawn from a continuous
distribution (w.r.t. the Lebesgue measure) on positive definite matrices with support G. Then,
Σ = A−1 , as a Gram matrix, is perfect w.r.t to G, with probability one.
Theorem 2 is proved in Section 8.4. The theorem shows that almost all Gram matrices
are L2 Markov perfect, justifying making that assumption in some of the results to follow.
Compared with [LM07], this is a significant strengthening. Theorem 2 is a consequence of a
more technical result, namely, Theorem 5 discussed in Section 8.4, a result which could be of
independent interest. One needs a fair amount of technical work to make the notion of “almost
all” precise. This is done in Section 8.4 by constructing appropriate measures on a suitable
parametrization of the set of Gram matrices that are L2 Markov w.r.t. a given graph G. Once
done, the same techniques in [LM07] can be extended to show the stronger result as illustrated
15

in the proof of Theorem 5. In addition, Theorem 2 further strengthens this result by showing
that the notion of “almost all” is independent of the particular parametrization of Theorem 5.
Remark 5. A corresponding result for linear DAG models appears as Theorem 3.2 in [SGS00],
and similarly for chain graphs in [Peñ11]. Although undirected graphs can be viewed as special
cases of chain graphs, our results are much stronger compared to the one found in [Peñ11].
The latter result only applies to a very particular parametrization of chain graphs, whereas our
results apply to essentially any parametrization of undirected graphs via Theorem 2. Moreover,
our proof technique is somewhat more intuitive and applies to PCGs defined over general
Hilbert spaces, i.e. not just collections of random variables.
Markov perfectness is useful when making statements regarding the separation of nodes in
the PCG, in which case there is a one-to-one correspondence between separation on the graph
and the relation PA ⊥ PB | PS among projections. This will be helpful in the next section,
where we discuss how the neighborhood lattice Tj (S) can be read off from the separation
properties of the PCG.

5.2

Graphical computation of the lattice

Under the perfectness assumption, let us now characterize the elements of Tj (S) in terms of
the separation in the underlying PCG. For any set S ⊂ [d]j , define a new set by
\
S ∗ := {T ⊂ S : T separates j and S \ T }.
(11)
Thus, S ∗ is the smallest subset of S that separates j and S \ S ∗ . Our next result gives the
following characterization of the minimal set mj (S), the maximal set Mj (S), and the entire
lattice, via graph separation:
Theorem 3. Assume L2 Markov perfectness. Fix j ∈ [d], S ⊂ [d]j , and define S ∗ by (11). Let
Ej (S ∗ ) = {k : S ∗ separates k and j}. Then,
(a) mj (S) = S ∗ .
(b) Mj (S) = S ∗ ∪ Ej (S ∗ ).
(c) Tj (S) = {S ∗ ∪ T : T ⊂ Ej (S ∗ )}.
We next provide a characterization of the minimal and maximal sets of the neighborhood
lattice of j via connected components of the graph resulting from the removal of j:
Theorem 4. Under L2 Markov perfectness, suppose that removing node j and the edges
connected to it breaks the PCG into K connected components defined by the vertex subsets
G1 , G2 , . . . , GK ⊂ [d]j . Let Sk = S ∩ Gk . Then,
U
(a) mj (S) = k mj (Sk ),
S
U
(b) Mj (S) = k Mj (Sk ) = k Mj (Sk ; Gk ), where Mj (Sk ; Gk ) is the largest element of
Tj (Sk ; Gk ) := {T ⊂ Gk : PT Pj = PSk Pj }.

16

11

5
12

8

15

13

11

5

4
8

12

9

3

4
15

13

9

3

6

2
1
10

14

6

2
1

7

10

(a)

14

7

(b)

Figure 3: The graphical computation in Example 6 of the neighborhood lattice Tj (S) for j = 3 and
S = {9, 8, 11, 12, 14}. (a) Original PCG with j and S specified with different colors. From this figure,
it is easy to see that S ∗ = {9, 12, 14} is the smallest subset of S that separates j from S \ S ∗ , hence
mj (S) = S ∗ . (b) Illustration of the three connected components which result after removing node j = 3.
As a result of Theorem 4, we can work in each component separately. For example, restricted to the left
component G1 = {1, 2, 8, 9, 13}, the minimal subset of S ∩ Gk = {8, 9} that separates j = 3 from the
rest of S ∩ Gk is Sk∗ = {9}. Within G1 , Sk∗ separates {8, 13} from j = 3. Hence, the restricted lattice
Tj (S ∩ G1 ; G1 ) = [{9}, {9, 8, 13}].

U
In these statements
denotes the disjoint union. Note that Tj (Sk ; Gk ) is the lattice restricted to the ground set Gk ∪{j} (i.e. instead of [d]). The original lattice given in Definition 4
can be thought of as Tj (Sk ; [d]j ). For illustrative purposes, some simple consequences of Theorems 3 and 4 are as follows:
(i) mj (S) = ∅ iff there is no path between j and S. (Separation by the empty set.)
(ii) If the PCG decomposes into two disjoint components, say G and H, then Mj (S) contains
H for any j ∈ G and any S.
Both (i) and (ii) hold without the prefectness assumption, and can be shown directly. However,
the graphical view of Theorems 3 and 4 makes them immediately clear.
Example 6. Continuing with Example 5, let j = 3 and S = {9, 8, 11, 12, 14}. It is clear from
Figure 3(a) that the smallest subset S ∗ of S, separating j from S \ S ∗ is {9, 12, 14}. Hence,
mj (S) = S ∗ according to Theorem 3. Similarly, Ej (S ∗ ) = {4, 5, 7, 8, 10, 11, 13, 15} and Mj (S) =
S ∗ ∪ Ej (S ∗ ). To verify Theorem 4, note that removing j breaks the PCG into three connected
components G1 = {1, 2, 8, 9, 13}, G2 = {7, 10} and G3 = {4, 5, 6, 11, 12, 14, 15}, as illustrated in
Figure 3(b). Applying Theorem 3, we can compute the restricted lattices Tj (S ∩ Gk ; Gk ), k =
1, 2, 3. Using the notation [m, M ] to represent a lattice with minimum and maximum elements
m and M , respectively, the three lattices are: [{9}, {8, 9, 13}], [{12, 14}, {4, 5, 11, 12, 14, 15}]
and [∅, {7, 10}]. It is clear that the minimal and maximal elements of the original lattice are
the disjoint union of the corresponding elements of these three lattices.
As can be seen from Example 6, graphical computation (assuming perfectness holds) is
much more computationally efficient than direct computation. The PCG can be constructed
from the sparsity pattern of the inverse Gram matrix, Σ−1 , after which all the lattice computations reduce to establishing certain connectivity criteria on the graph. In contrast, direct
computation requires evaluating at least some of the SEM coefficients, βj (S), which requires
17

calculating inverses Σ−1
S for different S. This task becomes computationally intensive when
the model is high-dimensional (and |S| is large) and when ΣS is relatively dense.

6

Directed models

Just as the undirected PCG defined in Definition 1 is the L2 analogue of undirected conditional
independence graphs, it is possible to extend the general L2 concepts to directed graphs in a
way that mirrors the theory of Bayesian networks (BNs) and structural equation models. In
this section, we discuss such extensions and illustrate how these ideas are closely related to
neighborhood regression and the neighborhood lattice introduced in Section 4.

6.1

Directed PCGs

There are several equivalent ways to define the notion of a directed PCG, which we describe
here. Let G be a directed acyclic graph (DAG) on [d], and let Πj denote the parent set of node
j in G. Similarly, let Nj be the set of non-descendants of j in G (i.e., i ∈ Nj if no directed
path exists from j to i), which is a well-defined notion due to the acyclicity assumption.
Definition 6. We say that x = (x1 , . . . , xd ) ∈ Hd satisfies a directed PCG w.r.t. G if
Pi PΠ⊥j Pj = 0,

∀j ∈ [d], i ∈ Nj .

(12)

This condition is modeled after the local Markov properties of BNs. Intuitively, (12) says that
the residual after projecting xj onto its parents is orthogonal to any of xj ’s non-descendants.
Alternatively, we could require that the residuals after projecting xi and xj onto their respective
parent sets are orthogonal, which gives a condition which is symmetric in i and j:
Pi PΠ⊥i PΠ⊥j Pj = 0,

for all distinct i, j ∈ [d].

(13)

A common way to rewrite these conditions is to require that there exists a vector e ∈ Hd ,
and a matrix B ∈ Rd×d with zero diagonal entries, whose associated graph is G (that is,
{(k, j) : Bkj 6= 0} is the edge set of G) such that
(a) x = B T x + e,

(b) (B T x)i ⊥ ei ,

(c) ei ⊥ ej ,

∀i, j ∈ [d].

(14)

P
Here, B T x is interpreted as an element of Hd with entries (B T x)j = k Bkj xk . The model
(14) is often called a (recursive) structural equation model (SEM) for x.
We have opted to define a directed PCG via (12) owing to its familiarity from the literature
on directed graphical models. The following lemma, however, establishes the equivalence of
conditions (12-14):
Lemma 8. Let x = (x1 , . . . , xd ) ∈ Hd be a vector satisfying (A1) and G a directed acyclic
graph. Then conditions (12), (13), and (14) are equivalent.
The equivalence of (12) and (13) is proved in Appendix A.6. The equivalence of (13) and (14)
is established via the following correspondences: (B T x)j = PΠj xj and ej = PΠ⊥j xj . We note
that B will not be unique unless the Gram matrix Σ = (hxi , xj i) is nonsingular. Assuming
that Σ is nonsingular, the jth column of B is βj (Πj ) as given by Definition 3.
18

It is always possible to obtain a directed PCG for a given x ∈ Hd by fixing an ordering
of the elements of x and performing recursive projection, i.e., projecting each element onto
those that come before it in the ordering. More precisely, fix a d × d permutation matrix P ,
and let x
e = P x. Then, we set e1 = x
e1 and proceed by projecting x
ej onto x
e1 , . . . , x
ej−1 for
j ≥ 2, and calling the residual ej . It is easy to see that this procedure leads to an SEM of
eT x
e T is upper triangular. In terms of the original vector x, we
the form x
e= B
e + e where B
e , hence a directed PCG as defined
obtain an SEM of the form (14) with B = B(P ) = P T BP
above. In the other direction any directed PCG is obtained in this way, i.e. if (14) holds,
one can obtain a permutation matrix P such that P BP T is lower triangular (due to acyclicity
assumption). Furthermore, letting πP : [d] → [d] be the permutation associated with P and
defining Sj = Sj (P ) = πP−1 ({1, . . . , j}), the jth column of the matrix B obtained in this way
corresponds to the coefficients βj (Sj ) as given by Definition 3. More interestingly, the support
of βj (Sj ) could be smaller than Sj (the original candidate parent set used in the recursive
projection). This support will be the minimal element of the corresponding neighborhood
lattice, Tj (Sj ), and will act as the (actual) parent set of j in the constructed PCG: that is,
Πj = mj (Sj ) and βj (Sj ) = βj (Πj ). The recursive projection procedure thus establishes an
interesting connection between undirected PCGs, directed PCGs, SEM coefficients, and the
neighborhood lattice which can be exploited when learning graphs from data (Section 6.2).
From the above discussion, it is clear that for any x ∈ Hd , there are in fact many potential
directed PCGs: One for each possible ordering of its elements (note that some orderings might
lead to the same directed PCG). The corresponding SEM coefficients B can be related to the
Cholesky factors of the inverse Gram matrix, after proper permutation: Assume that (14)
holds, P is a permuation matrix that makes P BP T lower triangular (always possible for a
DAG), and D is the diagonal Gram matrix of e. Letting Σ be the Gram matrix of x, it is not
hard to see that Σ−1 = (I − B)D−1 (I − B)T and P (I − B)D−1/2 P T = L for the Cholesky
decomposition P Σ−1 P T = LLT . From this interpretation, it is clear that the SEM in (14)—
alternatively a directed PCG—is not unique, i.e., for every permutation P of the elements of
x, there is a corresponding SEM obtained from the Cholesky decomposition of P Σ−1 P T . This
distinguishes directed PCGs from undirected PCGs, which are always unique.

6.2

Learning directed PCGs

The SEM model (14) provides a useful, interpretable way to describe how the variables in
x = (x1 , . . . , xd ) relate to one another that is commonly used in applications such as biology,
social science, and machine learning. Given its apparent utility in practice, it is of significant
interest to learn the coefficient matrix B from data. Furthermore, since the matrix B can be
interpreted as a weighted adjacency matrix for the underlying DAG G, learning B also implies
learning the structural relations encoded by the graph G.
Unfortunately, since directed PCGs are not unique these models are unidentifiable. In
the previous subsection we illustrated how the notion of a directed PCG is naturally related
to an implicit ordering on the variables, represented by a permutation P . To circumvent
identifiability issues, one often seeks permutations that result in the sparsest DAGs, as these
represent parsimonious explanations of the variables that are simple to interpret in practice.
If we know the order of the variables that leads to the sparsest possible directed graph G,
then we can use the recursive projection procedure outlined in Section 6.1 to estimate G.
More specifically, we can use (6) with the neighborhoods Sj defined previously to estimate the

19

support of each βj (Sj ) and hence the graph G.
In practice, of course, we do not know this ordering. Thus, we must consider all possible d!
orderings of the variables. A naive algorithm would compute βj (S) for all possible neighborhoods S ⊂ [d]j and all j ∈ [d], and check all possible permutations to find the sparsest graph
G. This is clearly computationally infeasible. In considering all possible neighborhoods, however, one implicitly encounters the neighborhood lattices Tj (S) (Definition 4) for every possible
S ⊂ [d]j and j ∈ [d]. These lattices encode how much “redundancy” exists in the different
neighborhoods, and suggests that we can reduce the total number of neighborhoods one must
consider by exploiting the algebraic structure of these lattices. This leads one to wonder: Is it
possible to exploit this redundancy in order to learn directed PCGs more efficiently?
Without sparsity or other simplifying assumptions, there are 2d−1 d neighborhood problems
to consider, which is intractable when d is large. By imposing a natural sparsity assumption
on the neighborhood lattices, however, the total number of neighborhood problems reduces
substantially owing to the redundancies encoded by the neighborhood lattices. For example, if
we assume that |mj (S)| ≤ k  d, for all S ⊂ [d]j and j ∈ [d], the total number of neighborhood

problems reduces to at most kd d ≤ dk+1  2d−1 d. This is an immediate consequence of the
lattice construction in Section 4.2. By Remark 4, we have mj (S) = supp(βj (S)), so that this
assumption amounts to assuming that the parent sets are sparse, which is a natural assumption
to make in practice. This suggests that one can learn all possible SEM representations of
the variables using a much smaller sample size, relative to the naive approach of solving all
possible regressions. This has been successfully exploited for Gaussian models [AAZ16] to
achieve optimal sample complexity n = Ω(k log d) in learning recursive structural equation
models [GH17]. The results presented in the current work suggest that these ideas can be
extended much further to non-Gaussian models, a direction we intend to pursue in the future.

7

Discussion

In this paper, we explored PCGs as counterparts to conditional independence graphs (CIGs),
when no assumptions are made about the distribution beyond the knowledge of the second
moments. We investigated the notion of partial orthogonality as the counterpart of conditional
independence and its natural relation to the general neighborhood regression problem. We
also investigated the algebraic structure of neighborhood regressions, motivated by the problem of enumerating all partial orthogonality relations efficiently. Finally, we also discussed
some subtleties and complications in extending these ideas to directed models. Studying these
extensions in more depth is left for future work. Below, we discuss an additional avenue for
future work regarding the estimation of partial orthogonality relations from a finite sample.
From a statistical perspective, all the discussions in this paper have been at the population
level. In practical statistical applications, one has to estimate partial orthogonality relations
from a sample of size n. To be precise, consider the cases where the underlying Hilbert space
H has a stochastic component, that is, its inner product is defined as hx1 , y1 iH = Ehx1 , y1 iH0
for x1 , y1 random elements from a base Hilbert space H0 , e.g, H0 = R or H0 = H 1 ([0, 1]);
see examples in Section 3.1. Now, assume that we observe independent copies x(1) , . . . , x(n) of
x ∈ Hd , a stochastic vector in H0d . Based on this sample, we wish to estimate some or all of
the partial orthogonality relations (5).
Under the perfectness assumption, according to the theorems of Section 5.2, the problem
reduces to estimating the support of Σ−1 . If d is fixed and n → ∞, thresholding the inverse of
20

the sample Gram matrix, given by
n

b = (Σ
b i,j ) ∈ Rd×d ,
Σ

X (k) (k)
b i,j = 1
hxi , xj iH0 ,
Σ
n
k=1

may be sufficient without many assumptions on the distribution. For high-dimensional data
(d  n), however, it would be interesting to see if some of the well-known penalized estimators
such as the graphical lasso [FHT08] can be used to estimate the PCG without the Gaussian assumptions. Much of the previous work in this area has been focused on the Gaussian
case [MB06; YL07; BEGd08; Uhl12]. Note that to recover the PCG, we need to have consistent
support recovery, perhaps the strongest form of consistency in high-dimensional problems.
Without the perfectness assumption, we have to consistently estimate the support of βj (S)
for all j and S ⊂ [d]j , simultaneously (Corollary 1). This can be done, at least in theory, by
solving all the neighborhood regression problems:
n

βbj (S) :=

argmin
β ∈ Rd , supp(β) ⊂ S

1 X (k)
kxj − β T x(k) k2H0 ,
n
k=1

and asking whether the support of βbj (S), after thresholding or adding regularization, is consistent for that of βj (S) for all j and S. This is a very challenging problem, as there are a
priori a super-exponential number of these neighborhood regressions. Here is where the lattice
property from Section 4.2 comes into play: By exploiting the lattice property, we can reduce
the total number of neighborhood regression problems that we need to look at, as detailed in
Section 6.2.
Finally, we note that the results presented here offer an interesting connection between
undirected and directed graphs via the well-understood and intuitive notion of neighborhood
regression. While such connections have appeared in passing in previous work, our results
confirm and extend these ideas in the very general setting of an abstract Hilbert space. While
there is much interest in using undirected graphs to simplify learning directed graphs, we
emphasize that these results also offer a way to go in the opposite direction. Namely, given
a DAG, how can we interpret the relationships encoded in the model in terms of the perhaps
more familiar undirected PCG? Theorems 3 and 4 provide an explicit description of how the
connections in B—given by mj (S)—can be characterized in terms of the underlying PCG.
Thus, our results provide an intuitive bridge between SEM and PCGs in a very general setting.

8

Proofs of the main results

Let us start with some preliminary lemmas. Recall the lattice of projections, P(H), introduced
in Section 2.3 and its meet and join operations. We have:
Lemma 9. For P, Q ∈ P(H), P y = 0 and Qy = 0 ⇐⇒ (P ∨ Q)y = 0.
In addition, for the collection of projection operators {PS , S ⊂ [d]} introduced in Definition 1, we have: For any T1 , T2 ⊂ [d], PT1 ∨PT2 = PT1 ∪T2 and PT1 ∧PT 2 = PT1 ∩T2 . In particular,
S ⊂ T implies PS ≤ PT . All these statements extend to any number of operators and can be
argued by considering bases for the underlying subspaces. For example, for the statement in
Lemma 9, a basis for the range of P ∨ Q can be built in such a way that it consists of the
21

union of bases for the range of P and the range of Q, from which the statement follows. The
following lemma is also key in the proofs:
Lemma 10. For S ⊂ T , R = T \ S and any L ∈ B(H),
PT L = PS L ⇐⇒ PR PS⊥ L = 0.
Proof. Since PS ≤ PT , we have PT PS = PS , hence (PT −PS )L = PT (I −PS )L = PT PS⊥ L. That
is, the LHS is equivalent to PT PS⊥ L = 0. Multiplying by PR and using PR ≤ PT gives the RHS,
i.e., PR PS⊥ L = 0. Now assume that the RHS is true; since in addition we have PS PS⊥ L = 0,
it follows that (PR ∨ PS )PS⊥ L = 0 by Lemma 9, from which we get the LHS by noting that
PR ∨ PS = PS∪R .

8.1

Proof of Theorem 1

Closure under intersections: Let Q be the projection T
onto the range of PS Pj , so that we have
Q ≤ PS . Assume that T1 , T2 , · · · ∈ Tj (S) and let R = k Tk . Note that Q is also the projection
onto the
V range of PTk Pj = PS Pj for all k. Hence, Q ≤ PTk (and also QPTk Pj = PTk Pj ). Since
PR = k PTk , it follows that Q ≤ PR ≤ PTk for all k. This last statement is equivalent to
PR Q = Q and PR PTk = PR for all k. Now, we have
PR Pj = PR PTk Pj = PR (QPTk Pj ) = QPTk Pj = PTk Pj = PS Pj ,

(15)

hence R ∈ Tj (S). The first equality follows from PR ≤ PTk , the second and fourth since Q
projects onto range PTk Pj , and the third since Q ≤ PR . Thus, we have shown that Tj (S) is
closed under intersections.
Closure under unions: Let S ∗ be the minimal element of Tj (S) which exists by the previous
argument. Note that
T ∈ Tj (S) ⇐⇒ T ⊃ S ∗ and PT PS⊥∗ Pj = 0.

(16)

To see this, it is enough to note that for T ⊃ S ∗ , we have (PT − PS ∗ )Pj = PT (I − PS ∗ )Pj =
PT PS⊥∗ Pj S
, where the first equality is by PS ∗ ≤ PT . Now, assume that T1 , T2 , · · · ∈ Tj (S) and
∗
⊥
let
M
=
k Tk . Since Tk ∈ Tj (S), we have TkW⊃ S and PTk PS ∗ Pj = 0 for all k. It follows that
W
( k PTk )PS⊥∗ Pj = 0 (Lemma 9). But PM = k PTk , that is, PM PS⊥∗ Pj = 0, hence M ∈ Tj (S)
by (16).
Convexity: Let S1 , S2 ∈ Tj (S) and S 0 ⊂ [d]j . Assume that S1 ⊂ S 0 ⊂ S2 , so that PS1 ≤
PS 0 ≤ PS2 . We have PS1 Pj = PS2 Pj . Multiply on the left by PS 0 and note that PS 0 PS1 = PS1 ,
and PS 0 PS2 = PS 0 . Thus, PS1 Pj = PS 0 Pj showing that S 0 ∈ Tj (S). The proof is complete.

8.2

Proof of Theorem 3

Throughout the proof of this theorem, we work under the assumption of L2 Markov perfectness,
i.e., all the lemmas in this subsection are stated under that assumption. We note that
S 0 ∈ Tj (S) ⇐⇒ Tj (S) = Tj (S 0 ) ⇐⇒ S ∈ Tj (S 0 ).
Lemma 11. Let A ⊂ S ⊂ [d]j . Then, A ∈ Tj (S) iff A separates j from S \ A.
22

(17)

C1
A

C1
B

A

B

C2

C2

(a)

(b)

Figure 4: Illustration of the reduction property. We break the cases respecting A − C1 ] C2 − B into two
groups, depending on whether there is a path between C1 and C2 (a), or not (b). The dashed lines are
possible paths. In none of the cases there could be a path between C2 and B because of the assumption
C2 − A − B. The same assumption precludes a path between C1 and B in cases in (a), because of the
existence of a path from C2 to C1 . As seen from this figure, in all possible cases, A and B are separated
by C1 .

Proof. Let R = S \ A. Then, by L2 Markov perfectness, A separates j from S \ A iff PR ⊥ Pj |
PA . This means PR PA⊥ Pj = 0 which is equivalent to PA Pj = PS Pj , by Lemma 10.
We can now write mj (S), the minimum element of Tj (S), as
\
\
mj (S) = {A ⊂ S : A ∈ Tj (S)} =
A ⊂ S : A separates j and S \ A.
the first equality is because we can restrict to subsets of S when finding the minimum, due
to Tj (S) being closed under intersections (lattice property), and the second is by Lemma 11.
This proves part (a) of Theorem 3.
Lemma 12. Let B ⊂ [d]j and A ∈ Tj (S) be disjoint. Then A separates B and j if and only if
A ∪ B ∈ Tj (S).
Proof. Since A ∈ Tj (S), we have Tj (A) = Tj (S). Hence, A ∪ B ∈ Tj (S) is equivalent to
A ∪ B ∈ Tj (A) which is equivalent to A ∈ Tj (A ∪ B) by (17). By Lemma 11, this latter
statement is equivalent to A separates j and B.
Since mj (S) is the smallest element of Tj (S), we get the following characterization:
Tj (S) = {T ⊂ [d]j : mj (S) separates j and T \ mj (S)}.

(18)

To see this, fix S and let S ∗ = mj (S). Then T ∈ Tj (S) iff S ∗ ⊂ T by minimality and S ∗
separates j and T \ S ∗ by Lemma 12. From (18), it follows that Mj (S) = mj (S) ∪ B where B
is the largest set that can be separated from j by mj (S). This proves part (b). Part (c) also
follows from (18).

8.3

Proof of Theorem 4

Let us introduce some new notations. Recall that we write A − C − B for disjoint sets A, B
and C when C separates A and B. This means that any path from a node i ∈ A to node j ∈ B
should pass through a node k ∈ C. This includes the case where there is no path from A to B.
Lemma 13. Separation has these properties:
• Additive property: A − C1 − B1 and A − C2 − B2 implies A − (C1 ∪ C2 ) − (B1 ∪ B2 ).
23

• Reduction property: A − C1 ] C2 − B and C2 − A − B implies A − C1 − B.
Proof. We only show the reduction property, for which it is enough to show that there is no
path from A to B that passes through C2 and not C1 . If so, a portion of it gives a path from
C2 to B that does not pass through C1 , and clearly not A since the paths do not self-cross. But
then A does not separate C2 and B, a contradiction. Figure 4 illustrates the argument.
Proof of Theorem 4. By induction we can reduce to the case where the nodes are partitioned
into two disjoint components G1 and G2 , after the removal of j. This implies G1 − j − G2 . For
any set A, let Ak := A ∩ Gk , k = 1, 2. We have
j − A − (S \ A)

⇐⇒

j − A1 − (S1 \ A1 )

and j − A2 − (S2 \ A2 )

(19)

To see this, note that the RHS implies j − A − (S1 \ A1 ) ∪ (S2 \ A2 ) by the additive property.
But (S1 \ A1 ) ∪ (S2 \ A2 ) = S \ A since G1 and G2 are disjoint.
Now assume the LHS. Then, clearly j − A − (S1 \ A1 ). But we also have A2 − j − (S1 \ A1 ).
Applying the reduction property, we get j − A1 − (S1 \ A1 ). The other implication is similar,
hence we get the RHS.
Equipped with (19), we can prove part (a). Let S ∗ be the smallest subset of S separating j
and S \ S ∗ (see (11)), and let S1∗ and S2∗ be its components (i.e, Sk∗ = S ∗ ∩ Gk , k = 1, 2). Then,
by (19) Sk∗ separates j and Sk \ Sk∗ , for k = 1, 2. It remains to show that Sk∗ is the smallest such
set (for each k). Suppose that there is a proper subset S10 of Sk∗ that separates j and S \ S10 .
Then, applying (19) with A1 = S10 and A2 = S2∗ and A = S 0 := S10 ∪ S2∗ , we conclude that S 0
separates j and S \ S 0 . But S 0 is a proper subset of S ∗ , violating the assumption that S ∗ is the
minimal set with such property. It follows that we should have mj (S1 ) = S1∗ and mj (S2 ) = S2∗
which proves part (a).
For part (b), let Sk∗ = mj (Sk ), k = 1, 2 and S ∗ = mj (S). From part (a), we have S ∗ =
∗
S1 ∪ S2∗ . Fix r ∈ [d]j . We claim that
r − S∗ − j

⇐⇒

r − S1∗ − j or r − S2∗ − j.

(20)

The ⇐ implication is clear. For the other direction, assume that r is separated from j by S ∗ ,
i.e., all the paths from r to j pass through S ∗ . WLOG, assume that r ∈ G1 (the case r ∈ G2
is similar). Suppose that there is a path from r to j that passes through S2∗ . A portion of
this path gives a path from r to S2∗ , hence to G2 , that does not pass through j, contradicting
G1 −j −G2 . Hence all the paths from r to j should pass through S1∗ , i.e., r−S1∗ −j, proving (20).
From (20), we conclude that Ej (S ∗ ) = Ej (S1∗ ) ∪ Ej (S2∗ ). Combined with characterization of
Mj (S) in Theorem 3(b), this proves the first equality in part(b).
To see the second equality in (b), recall that Tj (Sk ; Gk ) is the lattice with ground set
restricted to Gk ∪ {j}. First, the minimal element of Tj (Sk ; Gk ) is the same as that of Tj (Sk ).
This is true since a subset A of Sk separates j and Sk \ A in Gk ∪ {j} iff it does so in G.
(If the separation happens in Gk ∪ {j} but not in G, there will be a path from Sk \ A to j
passing through some Gr , r 6= k contradicting disjointness of Gk and Gr .) Even more directly,
a minimal subset of Tj (Sk ) is a subset of Sk , hence Gk , and the restriction in Tj (Sk ; Gk ) is
automatically satisfied. Knowing that the minimal element of Tj (Sk ; Gk ) is Sk∗ , we invoke
Theorem 3(b) restricted to Gk ∪ {j} to conclude that Mj (Sk ; Gk ) = Sk∗ ∪ Ej (Sk∗ ; Gk ) where
Ej (Sk∗ ; Gk ) = {i ∈ Gk : Sk∗ separates i and j}. Going through the argument leading to (20),
it is clear that we can replace (20) with
r − S∗ − j

⇐⇒

[r − S1∗ − j and r ∈ G1 ] or [r − S2∗ − j and r ∈ G2 ]
24

(21)

showing that Ej (S ∗ ) = Ej (S1∗ ; G1 ) ∪ Ej (S2∗ ; G2 ). Combined with the expression for Mj (Sk ; Gk ),
the desired result follows.

8.4

Proof of Theorem 2

For simplicity, let us introduce some notation and terminology. Let Sd be the set of symmetric
d × d matrices, Sd++ the set of d × d positive definite matrices, and Sd++,1 = {Γ ∈ Sd++ : Γi,i =
1, i ∈ [d]}. Matrices in Sd++,1 are often called correlation matrices. To avoid confusion, we
will call them Cor matrices. According to Lemma 6, L2 Markov properties are invariant to
arbitrary rescaling of the Gram matrix Σ. Thus, it is enough to focus on the case where
(Σ−1 )i,i = 1 for all i ∈ [d]. We will call a matrix Σ such that Σ−1 ∈ Sd++,1 , an inverse-Cor
matrix.
Given any graph G on nodes [d], our goal is to construct a collection of random inverse-Cor
matrices that are L2 Markov w.r.t. G. We then show that with probability one, such inverseCor matrices are perfect. The class of inverse-Cor matrices that are L2 Markov w.r.t. G can
be written as
−1
: Γ ∈ ΨG },
Ψ−1
G := {Γ

where

ΨG := {Γ ∈ Sd++,1 : Γi,j 6= 0 iff ij ∈ G}.

Note that ΨG is the set of Cor matrices with support G. The first step in our approach is to
put a distribution on Ψ−1
G as the push-forward of a distribution on ΨG which we construct. Our
construction is not uniform w.r.t. the Lebesgue measure, however, in Theorem 2, we extend the
result to any distribution on ΨG which is absolutely continuous w.r.t. the Lebesgue measure.
Before describing our construction of a random inverse-Cor matrix, let us set up some more
notation. We let Ln and Hs (s > 0) denote, respectively, the Lebesgue measure and the sdimensional Hausdorff measure on Rn . The dimension of the ambient space of Hs will be clear
from the context. For the graph G, let g = |G| be the number of edges. We often identify ΨG
with a subset of RG , and often identify RG with Rg , after ordering the edges, the particular
order being unimportant. For example, if G is 1 − 2 − 3, with g = |G| = 2, and Γ ∈ ΨG is


1 δ12 0
Γ = δ12 1 δ23  ,
0 δ23 1
we either view Γ as {δ12 , δ23 } = (δij , ij ∈ G), as an element of RG , or as the ordered pair
(δ12 , δ23 ) as an element of Rg = R2 .
For δ = (δij , ij ∈ G) ∈ RG and ε > 0, define AG,δ,ε = (aG,δ,ε
) ∈ Rd×d by setting
ij
aG,δ,ε
= 1, ∀i and aG,δ,ε
= δij ε 1{ij ∈ G}, ∀i 6= j.
ii
ij

(22)

For a fixed δ ∈ RG , let εG (δ) be the largest ε > 0 such that AG,δ,ε is positive definite, that is,
εG (δ) := sup{ε > 0 : AG,δ,ε ∈ Sd++ }. Let [−1, 1]∗ := [−1, 1] \ {0} and consider

MG := (δ, ε) : δ ∈ [−1, 1]G
∗ , ε ∈ (0, εG (δ)) .
The set {(AG,δ,ε )−1 : (δ, ε) ∈ MG } is (a parametrization of) the set of all inverse-Cor matrices
that are L2 Markov w.r.t. G. In other words, with the map ζ given by
ζ : RG × R → Sd ,

ζ(δ, ε) = (AG,δ,ε )−1 ,
25

(23)

1
0.8
0.6
0.4

0.8

0.2

0

0.6
0

0.4
0.2

-0.2

1

1

-0.4

0.5

0.5

-0.6

0

0

-0.8

-0.5

-0.5

/ 23

-1

-1

/ 12

-1
-1

-0.5

0

0.5

1

G
Figure 5: (Left) The plot of the samples from the uniform
p distribution on M∞ , called µG in the text,
2
for the graph G = 1 − 2 − 3. We have εG ((δ12 , ±1)) = 1/ 1 + δ12 and similarly for εG ((±1, δ23 )). Note
that the distribution is supported on S2∞ × [0, 1], it is singular w.r.t. L3 but absolutely continuous w.r.t.
H2 . (Right) Pushforward of µG by the map F defined in Step 1 in the proof of Theorem 2.

G
G
G
g+1 .
we have ζ(MG ) = Ψ−1
G . We note that M is a subset of [−1, 1] × (0, ∞) ⊂ R × R ' R
G
g+1
We will equip M with the Lebesgue measure (i.e., L ).
Alternatively, we can work with the normalized Lebesgue measure to obtain a uniform
probability distribution. For technical reasons, we will work with the subset of MG for which
G
G
G
G
δ has unit `∞ norm. Let SG
∞ := {δ ∈ R : kδk∞ = 1}, S∞,∗ = [−1, 1]∗ ∩ S∞ , and
G
G
MG
∞ := M ∩ (S∞ × R) =



(δ, ε) : δ ∈ SG
∞,∗ , ε ∈ (0, εG (δ)) .

G
The function εG , restricted to SG
∞,∗ , is continuous and bounded. In fact, sup εG (S∞,∗ ) = 1
G
G
g
g+1 ),
so that MG
∞ ⊂ [−1, 1] × (0, 1]. Hence M∞ has finite and positive H -measure (on R
G
g
where g := |G|. We equip M∞ with the normalized H -measure, to get a uniform probability
0
distribution. The uniform distribution on MG
∞ can also be described as follows: Pick δ by
0
0
0
drawing each entry uniformly from [−1, 1]∗ , and given δ , set δ = δ /kδ k∞ and draw ε uniformly
from [0, εG (δ)]; the vector (δ, ε) has the desired distribution. We will use µG to refer to the
uniform distribution on MG
∞ . See Figure 5. The map ζ defined earlier is also well-behaved
−1
G
over MG
:
It
is
one-to-one,
and onto Ψ−1
∞
G , that is, ζ : M∞ → ΨG is a bijection. We can now
−1
put a distribution on inverse-Cor matrices, ΨG , as the push-forward of µG by ζ.
Let us now consider the subclass of Ψ−1
G which is non-perfect. It is enough to work with
the corresponding subsets in MG and MG
∞:

N G = {(δ, ε) ∈ MG : (AG,δ,ε )−1 is not perfect},
G
G,δ,ε −1
N∞
= {(δ, ε) ∈ MG
) is not perfect} = N G ∩ (SG
∞ : (A
∞ × R)

The following result is the key component on which Theorem 2 is based:
G
Theorem 5. For δ ∈ [−1, 1]G
∗ , let Bδ := {ε : (δ, ε) ∈ N }, and let g := |G| ≥ 2. There exists
G
a set D ⊂ [−1, 1]∗ such that

(a) Dc is an Lg -null set,
c
g−1 -null set, and
(b) SG
∞ ∩ D is an H

(c) for every δ ∈ D, Bδ is finite, that is, H0 (Bδ ) < ∞.
26

G is Hg -null set.
In particular, (d) the set N G is Hg+1 -null set, and N∞

Since Hg+1 = Lg+1 on Rg+1 , we can equivalently say that N G has Lebesgue measure
zero. Theorem 5 is proved in Section 8.5. To get an intuition for this result, consider the
example G = 1 − 2 − 3 illustrated in Figure 5. Theorem 5 says that there is a “good” set
D of (δ12 , δ23 ) ∈ [−1, 1]2∗ which has full 2-dimensional measure, and its boundary (i.e., the
intersection with the perimeter of the square [−1, 1]2∗ ) has full 1-dimensional measure, and such
that for any (δ12 , δ23 ) ∈ D at most finitely many ε are problematic, i.e. lead to a nonperfect
Gram matrix. Equipped with this result, we can finish the proof of Theorem 2:
Proof of Theorem 2. Recall the identification of ΨG with a subset of RG ' Rg . The cases g = 0
and g = 1 are trivial, so we will assume g ≥ 2. We proceed in two steps:
Step 1. We first show that for any distribution on Cor matrices, ΨG , that is absolutely
continuous w.r.t Hg = Lg on ΨG , the result holds. Consider the map F : RG × R → RG
given by F (δ, ε) = (δij ε, ij ∈ G). Since F is a C 1 map, it is locally Lipschitz. In fact, F is
Lipschitz over MG
∞ . It is well-known that a Lipschitz map (between two metric spaces) maps
s
H -null sets to Hs -null sets, for any s > 0; see for example [KP08, Proposition 2.4.7]. Since
G ) = 0 according to Theorem 5, it follows that Hg (F (N G )) = 0. Let
Hg (N∞
∞
N = {Γ ∈ ΨG : Γ−1 is not perfect}.

(24)

Recalling the identification of ΨG with a subset of RG , and that F : MG
∞ → ΨG is a bijection,
g
G
we have F (N∞ ) ' N , that is, H (N ) = 0.
Step 2. Now consider the map ξ on Rd++ × RG → RG given by
 y


ij
ξ : xk , k ∈ [d]; yij , ij ∈ G 7→ √
, ij ∈ G ,
xi xj

(25)

which should be thought of as mapping a general PD matrix, with support G, to its corresponding Cor matrix (ignoring the diagonal of all ones). We claim that the push-forward of
Lg+d by ξ is absolutely continuous w.r.t. to Hg = Lg on RG ' Rg . This follows since ξ is
C 1 , hence locally Lipschitz on Ω := Rd++ × Rg ; see Lemma 16 in Appendix A.4 for details.
Combined with the result of Step 1, this implies Lg+d (ξ −1 (N )) = 0. But ξ −1 (N ) is the set of
all PD matrices with support G that are not perfect. The proof is complete.
It is worth noting that the measure µG , constructed in this section, is itself interesting. It
gives a practical device to generate a random sample (albeit with non-uniform distribution)
from the set of all (properly normalized) Gram matrcies that are L2 Markov w.r.t. to any
given graph G. The only computational burden is computing εG (δ), which can be obtained by
solving a convex optimization problem. We expect this approach to be much more efficient in
practice than, say, rejection sampling.

8.5

Proof of Theorem 5

Let us introduce some notation, most of which are borrowed from [LM07] with minor modifications. We assume familiarity with the arguments in [LM07] and keep the discussion of the
notation to a minimum. An ij-path on [d] is an ordered sequence i0 → i1 → i2 · · · → it → it+1 ,
27

where ij , j = 0, . . . , t + 1 are distinct elements of [d], i0 = i and it+1 = j. We represent such a
path as an ordered subset Π = {i0 , i1 . . . , it+1 } of [d]. An i0 -cycle on [d] is a i0 i0 -path; that is,
an ordered sequence of the form i0 → i1 → i2 · · · → it → i0 , where ij , j = 0, . . . , t are distinct
elements of [d]. We will represent such a cycle as an ordered subset C = {i0 , i1 . . . , it } of [d].
Ultimately, the ij-paths and i0 -cycles will be used to represent non-intersecting paths and
cycles on a graph G on nodes [d]. The graph G will be viewed as set of unordered pairs from
[d] representing the edges of G. We say that an ij-path Π = {i = i0 , i1 . . . , it+1 = j} belongs
to G, denoted as Π ∈ G, if all the edges in the path belong to G, that is, ij ij+1 ∈ G for all
j = 0, . . . , t. The set of ij-paths that belong to G is denoted as P ij (G). With some abuse
of notation, we let P ij = P ij ([d]) denote the set of all ij-path on [d] (corresponding to the
complete graph). The set of all ij-paths of G of length t + 1 is denoted as Ptij (G), that is
Ptij (G) := {Π ∈ P ij : Π ∈ G, |Π| = t + 1}.
S
We let Pt (G) := i,j∈[d] Ptij (G), the set of all paths of length t + 1 in G. The parallel notations
for i-cycles, namely
C i (G), C i = C i ([d]), Cti (G), and Ct (G)

(26)

are defined similarly (by setting i = j in the corresponding definitions for paths).
For an ij-path Π = {i0 = i, i1 , . . . , it , j = it+1 } ∈ P ij and a matrix B = (bi,j ) ∈ Rd×d , let
bΠ =

t
Y

bij ,ij+1 .

(27)

j=0

Note that if, instead, b ∈ RG and Π is a path that belongs to G, then bΠ as above is still
well-defined (i.e., we do not need b to be defined outside G.) A similar notation, namely bC , is
well-defined when C is an i0 -cycle. (In this case, it+1 = i0 in (27).)
The proof of Theorem 5 relies on the following key technical lemma, which is as an extension
of Lemma 4 in [LM07] and is proven in Appendix A.1. Here, we treat node 1 specially, hence
the emphasis on the collection of 1-cycles (cycles which begin and end on node 1) of a given
length t, namely Ct1 (G). The special role given to 1 becomes clear in the proof of Theorem 6
below, where in dealing with an ij-path of G, we identify the endpoints with node 1 of a new
graph H, hence obtaining a 1-cycle of H. Let C[x] be the set of polynomials in indeterminate
variable x, with complex coefficients. For p ∈ C[x], we say that p = 0 in C[x], or p(x) = 0 in
C[x], if p is the zero polynomial (i.e., all its coefficients are zero). For a square matrix B, |B|
denotes its determinant.
Lemma 14. Consider a graph H on [r] with no self-loops on any node except possibly node 1.
Let δij 6= 0, for ij ∈ H with i 6= j, and δ11 6= 0 . Define a matrix B(x) = (bij (x)) ∈ Rr×r by
bii = 1, ∀i > 1,

and

bij (x) = δij x 1{ij ∈ H}, for i 6= j and i = j = 1,

treating bij (x) as a polynomial in C[x]. Assume that |B(x)| = 0 in C[x], that is, |B(x)| is the
zero polynomial. Then, either Ct1 (H) = ∅ for all t ≥ 0 or
X
∃t ∈ [d] such that Ct1 (H) 6= ∅,
δC = 0.
(28)
C ∈ Ct1 (H)

28

Note that in the case t = 0, Ct1 (H) is nonempty only if H has a self-loop on node 1.
Following [LM07], let N = [d] and R(N ) the set of all couples (ij|K) such that i and j are
distinct singletons of N and K ⊂ N \ ij. Subsets of R(N ) are called relations. To simplify
notation, unless otherwise stated, couples of the form (ij|K) are always assumed to belong to
R(N ). The dual couple of (ij|K) is (ij|N \ ijK). For a relation L ⊂ R(N ), the dual relation
Le is defined as the relation containing all the dual couples of the elements of L. For any
matrix A ∈ Rd×d , let

hhAii := (ij|K) : |AiK,jK | = 0 .
By Lemma 1 in [LM07], for an invertible matrix A, we have hhAiie = hhA−1 ii. For a simple
undirected graph G with vertex set N , let

hGi := (ij|K) : K separates i and j in G .
Recalling the notation Ptij (G), let us write Ptij (G; K) := {Π ∈ Ptij (G) : Π ⊂ ijK} to denote
the set of ij-paths in G of length t + 1 that pass entirely through K. Also recall that for δ ∈ RG
and any path Π ∈ Pt (G) (of length t) in G, the quantity δΠ is well-defined using (27). We
define:
n
o
X
D = DG := δ ∈ [−1, 1]G
:
δ
=
6
0,
for
all
nonempty
P
⊂
P
(G),
t
∈
[d]
.
(29)
t
Π
∗
Π∈P

Theorem 6. Let G be a simple graph with vertex set N . Then,for any δ ∈ D, there are finitely
many ε ∈ C for which hGie = hhAG,δ,ε ii fails, where AG,δ,ε is defined in (22).
Proof. Let AG,δ,x be the matrix with elements in C[x] obtained by replacing ε in AG,δ,ε by
indeterminate x. Consider
hhAG,δ,x iiC[x] := {(ij|K) : |AG,δ,x
iK,jK | = 0 in C[x]}.
Step 1. Fix δ ∈ D. We show that hGie = hhAG,δ,x iiC[x] . Consider AG,δ,x
iK,jK and transpose
rows 1 and i, and columns 1 and j. This operation does not change the determinant, and
from now on, we can identify (i, j) with element (1, 1) in Lemma 14. In particular, let H be
the subgraph of G induced on nodes ijK, with nodes i and j identified together and renamed
node 1. Thus, a path from i to j in G that lies entirely in ijK corresponds to a cycle in H
starting at node 1. In other words, we can identify Ptij (G; K) with Ct1 (H). Also note that a
possible edge between i and j in G will be a self-loop on node 1 in H, i.e., δij x plays the role
of δ11 x in Lemma 14. Assumption (29) then implies that (28) of Lemma 14 cannot hold for
1
H derived from any (ij|K) ∈ R(N ). It follows from Lemma 14 that |AG,δ,x
iK,jK | = 0 iff Ct (H) or
equivalently Ptij (G; K) is empty for all t ≥ 0 That is, there is no ij-path in G of any length
that passes entirely through K. In other words, every ij path in G should intersect N \ ijK,
i.e., i and j are separated in G by N \ ijK, or in symbols (ij|K) ∈ hGie .
G,δ,ε
Step 2. Fix δ ∈ RG . For any ε ∈ C, |AG,δ,x
iK,jK | = 0 in C[x] implies |AiK,jK | = 0. (A zero
polynomial evaluates to zero at every point.) That is,

hhAG,δ,x iiC[x] ⊂ hhAG,δ,ε ii,

29

∀ε ∈ C.

(30)

The inclusion is strict iff there is (ij|K) such that pijK (x, δ) := |AG,δ,x
iK,jK | is a nonzero polynomial (in C[x]) with root ε. Since any such polynomial has a finite number of roots, we have
hhAG,δ,x iiC[x] = hhAG,δ,ε ii, for all but finitely many ε ∈ C. Combined with Step 1, the assertion
follows.
Lemma 15. Let Σ be a covariance matrix such that hGie = hhΣ−1 ii. Then, Σ is L2 Markov
perfect w.r.t. G.
Proof. First we note that by Lemma 1 in [LM07], hGi = hGiee = hhΣ−1 iie = hhΣii. Recall
N := [d]. Assume that Σ is not perfect. Then, there exist nonempty disjoint sets A, B ⊂ N and
⊥ P = 0 and K does not separate A and B. Then, ∃i ∈ A, j ∈ B
K ⊂ N \ AB such that PA PK
B
such that ¬(i − K − j) and clearly K ⊂ N \ ij. That is, (ij|K) ∈ R(N ). We also have
⊥ P = P P P ⊥ P P = 0 since P ≤ P and P ≤ P , hence |Σ
Pi PK
j
i A K B j
i
j
A
B
Ki,Kj | = 0 by Lemma 3.
That is, (ij|K) ∈ hhΣii, hence we should have (ij|K) ∈ hGi, contradicting ¬(i − K − j). The
proof is complete.
Proof of Theorem 5. Part (c) of Theorem 5, with D given by (29), follows from Theorem 6 and
Lemma 15 and the relation Σ−1 = AG,δ,ε . For part (a), we note that Dc := {δ ∈ [−1, 1]G
/
∗ :δ ∈
g -measure zero in
D} is the finite union of the zero sets of nontrivial polynomials,
hence
of
L
S
+
−
G
g
G
[−1, 1]G
∗ (as a subset of R ' R ). For part (b), let S∞ =
ij (Fij ∪ Fij ) be the decomposition
±
of SG
∞ into its (g − 1)-dimensional faces: Fij = {δ : δij = ±1}. It is enough to show, for
example, that Fij+ ∩ Dc has Hg−1 -measure zero. Let G0 be G with edge ij removed. By fixing
0
δij = 1, we can view Fij+ ∩ Dc as a subset of Fij+ ⊂ RG ' Rg−1 . Recalling the definition of
D, (29), we observe, as before, that Fij+ ∩ Dc as a subset of Rg−1 has Lg−1 -measure zero as a
finite union of the zero sets of nontrivial polynomials in g − 1 variables δG0 = (δrs , rs ∈ G0 ).
Since Lg−1 = Hg−1 on Rg−1 , the assertion follows.
G ) = 0 follow from the Fubini theorem for the
For part (d), both Lg+1 (N G ) = 0 and Hg (N∞
Lebesgue measure. For example, consider the latter assertion. It is enough to show Hg (N G ∩
(Fij+ × R)) = 0. Viewing N G ∩ (Fij+ × R) as a subset of Rg−1 × R, as above, and using the
decomposition of the Lebesgue measure Lg = Lg−1 × L1 , Fubini theorem gives
Z

+
g
G
H N ∩ (Fij × R) =
L1 (Bδ ) dHg−1 (δ)
+
Fij

Z

1

L (Bδ ) dH

=
+
Fij

∩ Dc

g−1

Z

L1 (Bδ ) dHg−1 (δ).

(δ) +
+
Fij

∩D

Both integrals are zero, the first since Hg−1 (Fij+ ∩ Dc ) = 0 by part (b), and the second since
Bδ has finitely many elements hence L1 (Bδ ) = 0, by part (c). The proof is complete.

References
[AAZ16]

B. Aragam, A. Amini, and Q. Zhou. Learning directed acyclic graphs with penalized neighbourhood regression. Submitted arXiv:1511.08963 (2016).

[BEGd08]

O. Banerjee, L. El Ghaoui, and A. d’Aspremont. Model selection through sparse
maximum likelihood estimation for multivariate Gaussian or binary data. The
Journal of Machine Learning Research 9 (2008), pp. 485–516.
30

[Bic]

T. Bice. Collection of projection operators in finite dimension and algebraic techinques. MathOverflow.

[Bla06]

B. Blackadar. Operator Algebras. Vol. 122. Encyclopaedia of Mathematical Sciences. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.

[Cra46]

H. Cramér. Mathematical Methods of Statistics. Vol. 9. Princeton university press,
1946.

[CW93]

D. R. Cox and N. Wermuth. Linear dependencies represented by chain graphs.
Statistical science (1993), pp. 204–218.

[Dem69]

A. P. Dempster. Elements of continuous multivariate analysis. Vol. 388. AddisonWesley Reading, Mass., 1969.

[FHT08]

J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation
with the Graphical Lasso. Biostatistics 9.3 (2008), pp. 432–441.

[Fri04]

N. Friedman. Inferring cellular networks using probabilistic graphical models. Science 303.5659 (2004), pp. 799–805.

[Fry90]

M. Frydenberg. The chain graph Markov property. Scandinavian Journal of Statistics (1990), pp. 333–353.

[FW10]

I. Farah and E. Wofsey. Set theory and operator algebras. Appalachian Set Theory:
2006-2012 (2010), pp. 1–51.

[GH17]

A. Ghoshal and J. Honorio. Information-theoretic limits of Bayesian network structure learning. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Ed. by A. Singh and J. Zhu. Vol. 54. Proceedings of Machine
Learning Research. Fort Lauderdale, FL, USA: PMLR, 2017, pp. 767–775.

[HD12]

N. Harris and M. Drton. PC algorithm for Gaussian copula graphical models.
arXiv preprint arXiv:1207.0242 ii (2012), pp. 1–17. arXiv: arXiv:1207.0242v1.

[HD13]

N. Harris and M. Drton. PC algorithm for nonparanormal graphical models. Journal of Machine Learning Research 14.1 (2013), pp. 3365–3383.

[KF09]

D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. Vol. 2009. 4. 2009, p. 1231.

[KP08]

S. G. Krantz and H. R. Parks. Geometric integration theory. Springer Science &
Business Media, 2008.

[Lau96]

S. L. Lauritzen. Graphical Models (Oxford Statistical Science Series). Oxford University Press, USA, 1996, p. 312.

[LLW09]

H. Liu, J. Lafferty, and L. Wasserman. The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs. Journal of Machine Learning
Research 10 (2009), pp. 2295–2328.

[LM07]

R Lněnička and F Matúš. On Gaussian condititional independence structures.
Kybernetika 43.3 (2007), pp. 327–342.

[LMP01]

J. Lafferty, A. McCallum, and F. C. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data (2001).

[LS16]

S. Lauritzen and K. Sadeghi. Unifying Markov Properties for Graphical Models.
arXiv preprint arXiv:1608.05810 (2016).
31

[MB06]

N. Meinshausen and P. Bühlmann. High-dimensional graphs and variable selection
with the {L}asso. The Annals of Statistics 34.3 (2006), pp. 1436–1462.

[Peñ11]

J. M. Peña. Faithfulness in chain graphs: the Gaussian case. International Conference on Artificial Intelligence and Statistics. 2011, pp. 588–599.

[Reg]

Neighborhood regression: lattice computation. https :/ /github .com / aaamini/
reg_lattice_comp. 2017.

[RS02]

T. Richardson and P. Spirtes. Ancestral graph Markov models. Annals of Statistics
(2002), pp. 962–1030.

[RWLO10]

P. Ravikumar, M. J. Wainwright, J. D. Lafferty, and Others. High-dimensional
Ising model selection using `1 -regularized logistic regression. The Annals of Statistics 38.3 (2010), pp. 1287–1319.

[SGS00]

P. Spirtes, C. Glymour, and R. Scheines. Causation, prediction, and search. Vol. 81.
The MIT Press, 2000.

[Sta97]

R. P. Stanley. Enumerative Combinatorics (Volume 1). Cambridge studies in advanced mathematics (1997).

[Tia12]

J. Tian. A Criterion for Parameter Identification in Structural Equation Models. Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI).
June 20, 2012. arXiv: 1206.5289v1 [stat.ME].

[Uhl12]

C. Uhler. Geometry of maximum likelihood estimation in Gaussian graphical models. The Annals of Statistics 40.1 (2012), pp. 238–261.

[WJ08]

M. J. Wainwright and M. I. Jordan. Graphical models, exponential families,
and variational inference. Foundations and Trends R in Machine Learning 1.1–
2 (2008), pp. 1–305.

[WKR13]

L. Wasserman, M. Kolar, and A. Rinaldo. Estimating undirected graphs under
weak assumptions. arXiv preprint arXiv:1309.6933 (2013).

[YL07]

M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphical
model. Biometrika 94.1 (2007), pp. 19–35.

[YRAL15]

E. Yang, P. Ravikumar, G. I. Allen, and Z. Liu. Graphical models via univariate
exponential family distributions. Journal of Machine Learning Research 16 (2015),
pp. 3813–3847.

A

Proofs of auxiliary results

We recall the following notational conventions: For a matrix Σ ∈ Rd×d , and subsets A, B ⊂ [d],
we use ΣA,B for the submatrix on rows and columns indexed by A and B, respectively. Single
index notation is used for principal submatrices, so that ΣA = ΣA, A . For example, Σi,j is the
(i, j)th element of Σ (using the singleton notation), whereas Σij = Σij, ij is the 2 × 2 submatrix
on {i, j} and {i, j}.

A.1

Proof of Lemma 14

Recall the definition of the i0 -cycle (of [d] or a graph G) from Section 8.5. In proving Lemma 14,
we will use the term cycle to also refer to cycles of a permutation. The necessary background
32

on cycle decomposition is briefly reviewed below. The two notions of cycle (graph versus
permutation) are related in our arguments, and the distinction in each occurrence should be
clear from the context.
Recall that every permutation π on [d], that is, a bijective map π : [d] → [d], has a
unique cycle decomposition, once we agree on a particular order within cycles and among
them [Sta97, Section 1.3]. For example, representing π = (142)(35) means that π has two
cycles C1 = {1, 4, 2} and C2 = {3, 5}. C1 being a cycle means that π maps 1 to 4, 4 to 2, and
2 back to 1, and similarly for C2 . We treat the cycles of π as ordered sets with the smallest
element written first, and the rest of the order determined by the action of π. (That is, if
C = {i0 , i1 , . . . , it } is a cycle of π, we have i0 < ij and π(ij−1 ) = ij for j = 1, . . . , t.) Thus,
permutation cycles are also graph cycles in the sense of Section 8.5. The (unordered) collection
of cycles of π will be denoted as Sπ , in this case, Sπ = {C1 , C2 }. The ordering among the
cycles is unimportant. We also follow the convention of disregarding trivial cycles, that is,
those containing a singles element. In this sense, the identity permutation has no cycles. We
often talk about “single cycle” permutations: for example, π 0 = (142)(3)(5) has a single cycle
C1 = {1, 4, 2} in our convention.
For matrix B = (bi,j ) ∈ Rd×d and permutation π on [d], we write
Y
Y
bπ :=
bi,π(i) =
bC ,
C ∈ Sπ

i∈[d]

where bC is as defined3 in (27). For the example above the two expressions are
bπ = b1,4 b2,1 b3,5 b4,2 b5,3 = (b1,4 b4,2 b2,1 )(b3,5 b5,3 ).
For any permutation, π, let Cπ be its 1-cycle, i.e., its cycle that contains Q
1 and let tπ =
|Cπ \ {1}| = |Cπ | − 1. We will call Cπ the first cycle of π. Note that bCπ = i∈Cπ bi,π(i) is a
factor of bπ . Note that for every permutation π, there is a “single cycle” permutation π 0 (as in
the example above) such that Cπ = Cπ0 , hence bCπ = bCπ0 .
Proof of Lemma 14. For simplicity, we will
Pdrop the explicit dependence on x and write B =
(bij ). By assumption, we have 0 = |B| = π sign(π)bπ . Note that bπ has bCπ as a factor. We
will show that bCπ = 0 for all π, form which the claim follows. (See the last paragraph of the
proof.) We proceed by induction on tπ = |Cπ | − 1 ∈ {0, . . . , r}, proving the induction step and
the case tπ = 0 simultaneously. Assume that 0 ≤ t ≤ r and that bCπ = 0 for all π with tπ < t.
We would like to show that bCπ = 0 for all π with tπ = t. It is enough to restrict to single
1-cycle permutations, that is, permutations with a single cycle C, containing 1 (C ∈ C 1 ). In
fact, it is enough to show
bC = 0,

∀C ∈ C 1 : |C| = t + 1.

(31)

We note that for any cycle C,
bC = δC x|C| 1{C ∈ H},

(32)

that is, bC is equal to 0 or δC x|C| , the latter iff C ∈ H. Here, δC is defined similar to bC . (δC
is well-defined when C ∈ H, otherwise define it arbitrarily.)
3

The notation bπ is also consistent with the definition of bC in Section 8.5 due to the following connection:
Every (graph) cycle C can be viewed as a permutation that leaves elements outside C intact.

33

P
By the induction assumption, bπ = 0 when tπ < t, hence 0 = |B| = π: |tπ | ≥ t sign(π)bπ .
There are three categories of terms in this expansion: (Sπ is the cycle decomposition of π.)
• |Sπ | = 1, tπ = t: These are the single 1-cycle permutations of cycle length t + 1. All of
these permutations have the same sign, and we have
bπ = bCπ = δCπ xt+1 1{Cπ ∈ H}
The first equality is since bii = 1 for all i 6= 1. Recall
tπ + 1 = t + 1. Thus, the
P that |Cπ | =t+1
overall contribution of these terms to |B| is ±
δ
x
, with the convention
1
C ∈ Ct (H) C
1
that the sum is zero if Ct (H) = ∅.
• |Sπ | ≥ 2, tπ = t: Any such permutation has at least a cycle C of size r ≥ 1 in [r] \ Cπ .
Hence, bπ has a factor of the form
bCπ bC = δCπ δC xt+r+1 1{Cπ , C ∈ G}
Thus, any such bπ if nonzero contributes a polynomial of degree at least t + 2.
• tπ ≥ t + 1: In this case, bπ has a factor of bCπ = δCπ xtπ +1 1{Cπ ∈ G} and as the previous
case contributes a polynomial of degree at least t + 2, if nonzero.
t+1 in the expansion of |B| equal to zero, we conclude
Thus,
P setting the coefficient of the x
that C ∈ C 1 (H) δC = 0. which proves the desired claim. (Note in addition that this implies (31)
t
in view of (32). In particular, with t = 0, it means that H cannot have a self-loop on node 1
if |B| = 0.)

A.2

Proof of Lemma 3

Let H be the underlying Hilbert space and
P xi ∈ H such that Σ = (hxi , xj i)  0. Define
the operator LS : R|S| → H by LS a = i∈S ai xi . The adjoint operator L∗S : H → R|S| is
given by L∗S y = (hy, xi i)i∈S . Since Σ  0, we have ΣS = (hxi , xj i)i,j∈S  0 for all S ⊂ [d].
By considering ΣS : R|S| → R|S| as an operator, we have the identification ΣS = L∗S LS . To
simplify notation, let Li = L{i} , so that Li a = axi for any a ∈ R and L∗i y = hy, xi i for any
y ∈ H. Then,
∗
PS = LS (L∗S LS )−1 L∗S = LS Σ−1
S LS .

(33)

(To see (33), note that the projection PS is characterized by the residual x − PS x, for any
x ∈ H, being orthogonal to ran(PS ) = ran(LS ), that is, x − PS x ∈ [ran(LS )]⊥ = ker(L∗S ).
Thus, PS is characterized by L∗S (I − PS ) = 0 which is satisfied by (33). Alternatively, write
PS x = LS a so that L∗S (x − LS a) = 0 and solve for a.)
−1 ∗
∗ ⊥
It follows that Pi PS⊥ Pj = 0 is equivalent to Li Σ−1
i Li PS Lj Σj Lj = 0. Note that Σi and
Σj are both positive scalars (ith and jth diagonal entries of Σ). Hence we can take them
out and get the equivalent statement Li L∗i PS⊥ Lj L∗j = 0. We also note that Li (L∗i PS⊥ Lj )L∗j =
(L∗i PS⊥ Lj )Li L∗j since the expression in parentheses is a scalar. Li L∗j is not the identically zero
operator, hence we get the equivalent statement
∗
0 = L∗i PS⊥ Lj = L∗i (I − PS )Lj = L∗i Lj − L∗i LS Σ−1
S LS Lj

= Σij − ΣTS,i Σ−1
S ΣS,j
34

(34)

where ΣS,i ∈ R|S| is the vector obtained from rows indexed by S in column i of Σ. By a Schur
Σ ΣT 
complement argument, (34) in turn is equivalent to the determinant of Σ ij ΣS,i = ΣSi,Sj
S,j
S
being zero, as desired.

A.3

Proof of Proposition 1

Let us start by computing PS xi using the notation used in the proof of Lemma 3. Since
−1
∗
xj = Lj 1, it is enough to write PS Li = LS Σ−1
S LS Lj = LS (ΣS ΣS,j ) (cf. (33)). This means
−1
that ΣS ΣS,j is the coefficient of expansion of PA xj in the basis of {xi : i ∈ S}. That is,
[βj (S)]S = Σ−1
S ΣS,j in the notation of Definition 3.
We can now obtain an equivalent statement to PA PS⊥ PB = 0 in terms of the Gram matrix
Σ. The condition is equivalent P
to PA PS⊥ xj = 0 for all j ∈ B. This in turn is equivalent to
PA xj = PA PS xj . Since PS xj = i∈S [βj (S)]i xi , we have
X

X
X
PA PS xj =
[βj (S)]i
[βi (A)]k xk .
[βj (S)]i (PA xi ) =
i∈S

i∈S

k∈A

P
Using PA xj = k∈A [βj (A)]k xk and equating the coefficients of xk , we obtain the system of
equations given in (b).
To see the equivalence of (b) and (c), let IS,i be the subvector of the identity matrix I ∈ Rd×d
−1
T Σ−1 Σ
on S × {i}. Note that we have [βj (S)]i = IS,i
S,j = Σj,S ΣS IS,i , for all i ∈ S (in fact true
S
for all i ∈ [d]), where the second equality is by symmetry of Σ. The RHS of ((b)) is equal to
X
X



−1
−1
IS,i Σi,A Σ−1
I
=
Σ
Σ
I
Σ
Σ
Σj,S Σ−1
j,S
S,i
i,A
A,k
A IA,k ,
S
A
S
i∈S

i∈S

the latter summation being equal to IS,S ΣS,A = ΣS,A . Similarly, the LHS of (b) is equal to
Σj,A Σ−1
A IA,k . Hence, (b) is equivalent to
−1
−1
Σj,A Σ−1
A IA,k = Σj,S ΣS ΣS,A ΣA IA,k ,

∀k ∈ A, j ∈ B,

−1
−1
or in matrix form ΣB,A Σ−1
A IA,A = ΣB,S ΣS ΣS,A ΣA IA,A . Dropping the identity IA,A and
rearranging we have (ΣB,A − ΣB,S ΣS−1 ΣS,A )Σ−1
A = 0 which is equivalent to (c).
Let us now show the equivalence of (a) and (d). First we note that (a) is equivalent to
Pi PS⊥ Pj = 0 for all i ∈ A and j ∈ B. Alternatively, it is equivalent to hxi , PS⊥ xj iH = 0 for all
i ∈ A and j ∈ B. Let us fix i ∈ A and j ∈ B, and show that

hxi , PS⊥ xj iH = 0 ⇐⇒ [βj (Si)]i = 0
which
establishes (a) ⇐⇒ (d). By definition of SEM coefficients in (3), we have PSi xj =
P
k∈Si [βj (Si)]k xk . To simplify notation, let us write α = βj (Si) and u = PSi xj . We have
u=

X

αk xk ,

⊥
xj = PSi
xj + u.

(35)

k∈Si

Applying PS⊥ to both sides of the first equation, we get PS⊥ u = αi PS⊥ xi . (Since, PS⊥ xk =

35

0, ∀k ∈ S.) Taking the inner product with xi (dropping H subscript for simplicity), we obtain
αi hxi , PS⊥ xi i = hxi , PS⊥ ui
⊥
= hxi , PS⊥ (xj − PSi
xj )i
⊥
= hxi , PS⊥ xj i − hxi , PSi
xj i

⊥
⊥ ⊥
⊥
(Since PSi
≤ PS⊥ , i.e. PSi
PS = PSi
)

⊥
= hxi , PS⊥ xj i − hPSi
xi , xj i

(Projections are self-adjoint.)

= hxi , PS⊥ xj i

⊥
(Since PSi
xi = 0.)

⊥ ≤ P ⊥ is equivalent to P ≤ P
Note that PSi
S
Si which is perhaps easier to see. Since assumption
S
⊥
Σ  0 implies hxi , PS xi i > 0, we have the equivalence of αi = 0 and hxi , PS⊥ xj i = 0 which is
the desired result. Note that we have also established (7). The proof is complete.

A.4

Auxiliary lemmas

The following lemma is used in the proof of Theorem 2. The notation ξ∗ µ denotes the pushforward of measure µ by map ξ.
Lemma 16. With ξ : Rd++ × Rg → Rg defined as in (25), we have ξ∗ Ld+g  Lg , that is,
Lg (A) = 0 implies Lg+d (ξ −1 (A)) = 0.
Proof. Let Ω := Rd++ × Rg be a subset of Rd+g . Let x = (xk , k ∈ [d]) and y = (yij , ij ∈ G).
Consider the function F1 : Ω → Ω defined by


yij
, ij ∈ G .
F1 (x, y) = x, √
xi xj
F1 is a C ∞ diffiomorphism of Ω onto itself, that is, F1 : Ω → Ω is a bijection and both F1 and
its inverse F2 := F1−1 belong to class C ∞ . This implies that F1 and F2 are locally Lipschitz
(i.e., Lipschitz when restricted to any compact subset of Ω), hence they both preserve Lg+d -null
sets (i.e., map null sets to null sets).
Let π : Rd+g → Rg be the projection π(x, y) = y. We can write ξ = π ◦ F1 . Below we will
show that π∗ Ld+g  Lg . Assuming that Lg (A) = 0, we thus have Lg+d (π −1 (A)) = 0. But then
Lg+d (F2 ◦ π −1 (A)) = 0, due to the diffiomorphic nature of F2 . Noting that ξ −1 = (π ◦ F1 )−1 =
F1−1 ◦ π −1 = F2 ◦ π −1 , we have the desired result.
It remains to prove the claim about the projection π. But this follows from Fubini theorem:
Let A ⊂ Rg be such that Lg (A) = 0. We have π −1 (A) = Rd × A. Hence, Ld+g (π −1 (A)) =
Ld (Rd ) · Lg (A) = 0 since Lebesgue measure is σ-finite. The proof is complete.

A.5

Proof of Lemma 5

The idea is to reduce the general case to the case where the underlying random variables are
Gaussian, in which case PCG is the same as CIG. The result the follows that for CIGs.
The first step is to show that PCGs are preserved under isometries between Hilbert spaces.
Let us recall some facts about isometries: An operator L ∈ B(H1 , H2 ) between two Hilbert
spaces is called an isometry if kLξkH2 = kξkH1 for all ξ ∈ H1 , i.e. it preserves norms. Equivalently (using polarization identity), it is an isometry if hLξ, LηiH2 = hξ, ηiH1 , ∀ξ, η ∈ H1 , i.e.,
it preserves inner products. One has that L is an isometry iff L∗ L = IH1 .
36

Step 1 (PCGs are preserved by isometries): Let H0 := span{x1 , . . . , xd } ⊂ L2 (P). Let K
be a d-dimensional Hilbert space and let us define the linear operator V : K → H0 by taking a
linearly independent set {y1 , . . . , yd } ⊂ K with and letting V yi = xi , ∀i ∈ [d]. We can further
assume that {yi } are chosen such that hyi , yj iK = Σij = hxi , xj iH . It then follows that V is an
isometry, hence V ∗ V = IK . On the other hand, V is also surjective, hence a unitary operator,
hence V V ∗ = IH0 .
Let QA = V ∗ PA V . We claim that this is the (orthogonal) projection operator onto the span
of yA := {yi : i ∈ A}. We have, for i ∈ A, QA yi = V ∗ PA xi = V ∗ xi = V ∗ V yi = yi . On the other
hand, assume z ⊥K yi , ∀i ∈ A. Then, for all i ∈ A, 0 = hz, yi iK = hV z, V yi iH0 = hV z, xi iH0 . It
follows that PA V z = 0, hence QA z = 0.
This shows that any of the pairwise or global L2 Markov properties are preserved under
∗
∗ ⊥
isometries: Note that Q⊥
A := IK − QA = V (IH0 − PA )V = V PA V . We conclude that
⊥
∗
⊥
⊥
⊥
∗
QA QS QB = V (PA PS PB )V and PA PS PB = V (QA QS QB )V . Hence,
PA PS⊥ PB = 0 ⇐⇒ QA Q⊥
S QB = 0.

(36)

Step 2 (Reduction to Gaussian case): Now take y = (y1 , . . . , yd ) ∼ N (0, Σ), say on the
same probability space, and let K = span{y1 , . . . , yd }. By (36), and using the assumption
that x satisfies pairwise L2 property w.r.t. some G, we conclude that y also satisfies pairwise
L2 property w.r.t. G. Then, due to the equivalence of orthogonality and independence for
Gaussian random variables, y satisfies usual pairwise Markov property (defined via conditional
independence) w.r.t. G. That is, G is a CIG for y.
Invoking (36) again, it is enough to show that if A and B are separated by S, then
⊥
QA Q⊥
S QB = 0, which is equivalent to hu, QS viK = 0, ∀u ∈ span{yA }, v ∈ span{yB }. Since S
separates A and B, we know that u and v are independent given yS . This follows from [Lau96,
Thm. 3.9, p. 35] for CIGs, since N (0, Σ) has a.e. positive density w.r.t. Lebesgue measure,
assuming Σ  0. In particular,
E[uv|yS ] = E[u|yS ] E[v|yS ] = (QS u)(QS v)

(37)

where the second equality uses Gaussianty again to write E[u|yS ] as the L2 projection to the
linear span of yS . Taking expectation on both sides of (37), we have hu, viK = hQS u, QS viK
⊥
⊥
from which it follows that hQ⊥
S u, QS viK = 0, which in turn is equivalent to hu, QS viK = 0
⊥
since QS is self-adjoint and idempotent.

A.6

Equivalence of the two directed PCG definitions

In this appendix, we show that the two definitions of a directed PCG given in (12) and (13)
are equivalent (under the acyclicity assumption). Recall that Πj and Nj denote, respectively,
the sets of parents and non-descendants of node j in the underlying graph G.
Assume first that (12) holds and take i, j ∈ [d]. Since G is a DAG, one of i and j is a
non-descendant of the other, say i ∈ Nj . (If i and j are adjacent, this means that i is a
parent of j.) Then, any parent of i will be a non-descendant of j, that is, Πi ⊂ W
Nj . It follows
that Pk PΠ⊥j Pj = 0 for k ∈ {i} ∪ Πi . In particular, PΠi PΠ⊥j Pj = 0 since PΠi = k∈Πi Pk (see

37

Lemma 9), and Pi PΠ⊥j Pj = 0. Since we have
Pi PΠ⊥j Pj = Pi (PΠi + PΠ⊥i )PΠ⊥j Pj
= Pi PΠi PΠ⊥j Pj + Pi PΠ⊥i PΠ⊥j Pj

(38)

(c)

= Pi PΠ⊥i PΠ⊥j Pj ,

we obtain Pi PΠ⊥i PΠ⊥j Pj = 0, that is (13) holds for i and j.
Now assume that (13) holds and take j ∈ [d] and i ∈ Nj . Note that it is enough to establish
identity (38). An ancestor of i is any node that has a directed path to i; let us call such a
path, a path from the top to i. Let the depth of a node i be the length of the longest path
from the top to it. We proceed by the induction on the depth of node i. For depth zero, we
have Πi = ∅, hence PΠi = 0 and (38) holds trivially. Now assume that we have the result for
all non-descendants of j at depth at most r − 1, and let i ∈ Nj have depth r. Any k ∈ Πi is
at depth at most r − 1 and belongs to Nj , hence by the induction hypothesis Pk PΠ⊥j Pj = 0 for
k ∈ Πj . It follows that PΠi PΠ⊥j Pj = 0, hence (38)(c) holds which then means that (38) holds
as a whole. The proof is complete.

B

Abstract lattice theorem

In this appendix, we present an interesting generalization of the lattice Theorem 1. The result
and its argument are due to Tristan Bice [Bic]. Let A be a von Neumann algebra and P be
its projection lattice, ordered by p ≤ q ⇐⇒ p = pq ⇐⇒ p = qp, the latter equivalence
being a result of the self-adjointness of p and q. The convention is to use lower case letters
for elements of A and P . Note that a general element b ∈ A is a bounded operator on the
underlying Hilbert space, i.e., b ∈ B(H). Similarly p ∈ P is a projection operator in B(H).
Theorem 7. Q = {q ∈ P : pa = qa} is a complete sublattice of P , ∀a ∈ A and p ∈ P .
Proof. Let [b] be the range projection of any b ∈ A, i.e., projection onto the closure of the
range of b. For any q ∈ P and a ∈ A, we have [qa] ≤ q (since the range of qa is included in the
range of q). Also note the identity (2) b = [b]b, ∀b ∈ A.
If R ⊂ Q,Vthen for all q ∈ R, we have (1) [pa] = [qa] ≤ q, hence [pa] is lower bound on R.
Letting r := R, by definition of infimum, [pa] ≤ r ≤ q, ∀q ∈ R, hence [qa] ≤ r ≤ q, ∀q ∈ R
by (1). Hence,
(By r ≤ q ⇐⇒ r = rq)

ra = rqa
= r[qa]qa
= [qa]qa

(By (2) with b = qa)
(By [qa] ≤ r ⇐⇒ [qa] = r[qa])

= qa

(By (2) with b = qa)

= pa,
showing that r ∈ Q. So, Q is closed under infima.
Since pa = qa ⇐⇒ p⊥ a = q ⊥ a (recall p⊥ = 1 − p), it follows that Q⊥ := {q ⊥ : q ∈ Q}
is also closed under infima. But since q ⊥ ≤ p⊥ ⇐⇒ p ≤ q, it follows that Q is closed under
suprema, finishing the proof.

38

