arXiv:1612.05994v1 [] 18 Dec 2016

ALGEBRAIC PROBLEMS IN STRUCTURAL EQUATION
MODELING
MATHIAS DRTON
Abstract. The paper gives an overview of recent advances in structural equation modeling. A structural equation model is a multivariate statistical model
that is determined by a mixed graph, also known as a path diagram. Our
focus is on the covariance matrices of linear structural equation models. In
the linear case, each covariance is a rational function of parameters that are
associated to the edges and nodes of the graph. We statistically motivate
algebraic problems concerning the rational map that parametrizes the covariance matrix. We review combinatorial tools such as the trek rule, projection
to ancestral sets, and a graph decomposition due to Jin Tian. Building on
these tools, we discuss advances in parameter identification, i.e., the study of
(generic) injectivity of the parametrization, and explain recent results on determinantal relations among the covariances. The paper is based on lectures
given at the 8th Mathematical Society of Japan Seasonal Institute.

Contents
Part
1.
2.
3.

I. Structural Equation Models and Questions of Interest
Motivation
Linear Structural Equation Models
Questions of Interest

Part
4.
5.
6.

II. Treks, Subgraphs and Decomposition
Trek Rule
Induced Subgraphs and Principal Submatrices
Graph Decomposition

2
2
4
7
13
13
15
17

Part III. Parameter Identification
7. Global Identifiability
8. Generic Identifiability

21
21
23

Part IV. Relations Among Covariances
9. Implicitization
10. Conditional Independence
11. Trek Separation
12. Verma Constraints

29
29
31
32
34

13. Conclusion
References

35
36

Date: September 21, 2016.
Key words and phrases. Algebraic statistics, covariance matrix, Gaussian distribution, graphical model, Gröbner basis, structural equation model.
1

2

MATHIAS DRTON

Part I. Structural Equation Models and Questions of Interest
1. Motivation
The following example serves well to introduce the statistical models we will
consider. It features the simplest instance of what is known as an instrumental
variable model. An empirical study that shows this type of model ‘in action’ can
be found in [29].
Example 1.1. Does a mother’s smoking during pregnancy harm the baby? To
answer this question researchers conduct a study in which they record, for a sample
of pregnancies, the baby’s birth weight and the average number of cigarettes the
mom smoked per day during the first trimester. The researchers observe a significant negative correlation between the birth weight and smoking and are tempted to
conclude that smoking has a negative effect on the baby’s health, with an increase
in the number of cigarettes smoked leading to lower birth weight.
The cigarette companies are not suprised by this finding. They argue, however,
that smoking does not harm baby. Instead, heavier smoking is merely a reflection of
underlying factors that are the true causes of low birth weight. Such confounding
variables could, for instance, be of socio-economic nature. In the context of the
smoking-lung cancer debate, prominent Statistician Ronald Fisher liked to argue
that correlations can be attributed to unobserved variables of genetic nature [59].
Familiar with this type of counter-argument, the researchers cleverly recorded a
third variable: The tax rate on tobacco products in the local jurisdictions of the
mothers in the sample. It is not unreasonable to assume that the tax rate does
not have a direct effect on the baby’s health. If there is then variation in the tax
rate and higher taxes have an effect on the amount of smoking, then the effect
that smoking has on birth weight can be estimated in a model that allows for the
presence of unobserved confounders, as we will see shortly.
The above narrative suggests a number of cause-effect relations, as well as the
absence thereof. Qualitatively these are summarized in the graph in Figure 1.1.
The variables in play are the nodes of the graph and cause-effect relationships are
indicated as directed edges. The variable U represents a confounding variable and
is unobserved, which we emphasize by coloring its edges in red.
Structural equation models turn the qualitative descriptions of causes and effects
into quantified functional relationships. In this article, the functional relationships
will always be linear. The linear structural equation model for the present example
is based on the following system of structural equations:
(1.1)

X1 = λ01

(1.2)

X2 = λ02 + λ12 X1 + λu2 U + ε2 ,

(1.3)

X3 = λ03 + λ23 X2 + λu3 U + ε3 ,

(1.4)

U = λ0u

+ ε1 ,

+ εu .

Here, the error terms ε1 , ε2 , ε3 , εu are independent random variables with zero
mean. The eight coefficients λ01 , λ02 , λ03 , λ0u , λ12 , λ23 , λu2 , and λu3 are unknown
parameters. Equation (1.1) indicates that variable X1 , the tax rate, has expectation
λ01 , from which it deviates according to the distribution assumed for ε1 . The
analogous statement for the unobserved confounder U is made in (1.4). In (1.2),
the amount of smoking, denoted X2 , is modeled to be a linear function of the tax

STRUCTURAL EQUATION MODELS

3

U : Confounder

X1 : Tax Rate

X2 : Mom’s Smoking

X3 : Baby’s Weight

Figure 1.1. Directed graph representing an instrumental variable model.
rate and independent noise. Similarly, (1.3) introduces birth weight, denoted X3 ,
as a noisy linear function of smoking.
The quantity of primary interest is the coefficient λ23 that quantifies the relationship between smoking and birth weight. Using data, we can estimate the joint
distribution and, in particular, the covariance matrix of the three observed variables
X1 , X2 and X3 . Because the error terms are independent and have zero means,
the covariance between X3 and X1 is
(1.5)

Cov[X1 , X3 ] = λ23 Cov[X1 , X2 ].

Hence, as long as Cov[X1 , X2 ] 6= 0, statistical inference about λ23 may be based on
the ratio of the two covariances in (1.5).
In some applications of structural equation models latent (that is, unobserved)
variables are of direct interest. For instance, concepts such as intelligence or depression in psychology are of this nature and measured only indirectly through
other variables such as exam results or answers in questionnaires. While problems
with explicit latent variables are ubiquitous [5], we will focus on models in which
the effects of latent variables are summarized and represented merely in terms of
correlations among the error terms in structural equations. This representation of
dependence induced by latent variables is discussed in detail in [33, 44, 49, 50, 71].
Example 1.2. We take up the instrumental variable model from Example 1.1.
The effects of the confounding variable U can be summarized by absorbing U into
the error terms for equations (1.2) and (1.3). Define
(1.6)

ε̃2 = λu2 U + ε2 ,

ε̃3 = λu3 U + ε3 .

Retaining only the equations for the observed variables X1 , X2 , and X3 , we are left
with the equation system:
(1.7)

X1 = λ01

+ ε1 ,

(1.8)

X2 = λ02 + λ12 X1 + ε̃2 ,

(1.9)

X3 = λ03 + λ23 X2 + ε̃3 .

However, and this is the significance of the unobserved variable U , we have now
correlated error terms because
(1.10) ω23 := Cov[ε̃2 , ε̃3 ] = Cov[λu2 U + ε2 , λu3 U + ε3 ] = λu2 λu3 Var[U ] 6= 0.
In the sequel, we will focus on models that are given by equations such as (1.7)(1.9), with one equation for each observed variable but error terms that may be
correlated. Graphically, such models may be represented by a mixed graph that
features directed edges to encode which variables appear in each structural equation and bidirected edges that indicate possibly nonzero correlations between error
terms. The mixed graph for the model given by (1.7)-(1.9) is depicted in Figure 1.2,
which shows the unknown parameters as weights for the edges. At the nodes, we

4

MATHIAS DRTON

ω23

ω11
X1 : Tax rate

λ12

ω22
X2 : Mom’s smoking

λ23

ω33
X3 : Baby’s weight

Figure 1.2. Mixed graph representing an instrumental variable model.

show the variances of the error terms, namely, ω11 = Var[ε1 ], ω22 = Var[ε̃2 ], and
ω33 = Var[ε̃3 ]. In the statistical literature, the mixed graph for a structural equation
model is also known as a path diagram.
The ratio Cov[X2 , X3 ]/ Var[X2 ] is the regression coefficient when predicting X3
from X2 . We have
(1.11)

Cov[X2 , X3 ]
ω23
= λ23 +
.
Var[X2 ]
Var[X2 ]

Hence, linear regression predicting X3 from X2 only estimates the coefficient of
interest if ω23 = 0, as is the case when X2 and X3 do not depend on the latent
variable U . When ω23 6= 0, the relation from (1.5), which involves all three variables,
is needed to recover λ23 .
The remainder of this paper is organized as follows. Section 2 introduces linear
structural equation models in full generality. We then formulate questions of statistical interest and the algebraic problems they correspond to (Section 3). Next,
we examine the interplay between covariance matrices and mixed graphs. We treat
the so-called trek rule (Section 4) and review useful results on subgraphs and graph
decomposition (Sections 5 and 6). In Sections 7 and 8, we dive deeper into parameter identifiability, which here means the question of whether a coefficient of interest
can be recovered from the covariance matrix of the observed variables. Finally, we
discuss relations among the entries of the covariance matrix (Sections 9-12).
2. Linear Structural Equation Models
Let ε = (εi : i ∈ V ) be a random vector indexed by a finite set V . Define a
new random vector X = (Xi : i ∈ V ) as the solution to the system of structural
equations
(2.1)

X = ΛT X + ε,

where Λ = (λij ) ∈ RV ×V is a matrix of unknown parameters. Suppose ε has
covariance matrix Ω = (ωij ) = Var[ε], so Ω is a positive definite matrix whose
entries are again unknown parameters. Write I for the identity matrix. If I − Λ is
invertible, then the linear system in (2.1) is solved uniquely by X = (I − Λ)−T ε,
which has covariance matrix
(2.2)

Var[X] = (I − Λ)−T Ω(I − Λ)−1 =: φ(Λ, Ω).

Interesting settings are obtained by restricting the support of Λ and Ω, as is the
case in our motivating example.

STRUCTURAL EQUATION MODELS

5

Example 2.1. Consider the setup from Example 1.2. If the equation system
from (1.7)-(1.9) is written in vector form as in (2.1), then the coefficient matrix is


0 λ12
0
Λ = 0 0 λ23  .
(2.3)
0 0
0
The error covariance matrix is

(2.4)


ω11
Ω = Var[ε] =  0
0

0
ω22
ω23


0
ω23  .
ω33

From (2.2), the covariance matrix of X = (X1 , X2 , X3 ) is found to be


ω11
ω11 λ12
ω11 λ12 λ23
,
ω22 + ω11 λ212
ω23 + λ23 σ22
(2.5)
Var[X] =  ω11 λ12
ω11 λ12 λ23 ω23 + λ23 σ22 ω33 + 2ω23 λ23 + λ223 σ22

where σ22 denotes the (2, 2) entry of Var[X]. The relation from (1.5) can be confirmed from the (1, 2) and (2, 3) entry of Var[X].
Restrictions on the support of a matrix naturally correspond to a graph. Specifically, we adopt mixed graphs because we are dealing with two matrices, Λ and Ω,
whose rows and columns are indexed by the same set V . In structural equation
modeling, this point of view originated in the work of Sewall Wright [72, 73].
A mixed graph with vertex set V is a triple G = (V, D, B) where D, B ⊆ V × V
are two sets of edges. The set D comprises ordered pairs (i, j) that we also denote
by i → j to visualize the fact that such a pair encodes a directed edge pointing
from i to j. Then i is the tail and j is the head of the egde. The pairs in B are
unordered pairs {i, j} that encode bidirected edges that we also denote by i ↔ j.
These edges have no orientiation, and i ↔ j ∈ B if and only if j ↔ i ∈ B. It
will be convenient to call both endpoints i and j heads of i ↔ j. In our context,
neither the bidirected part (V, B) nor the directed part (V, D) contain loops, that
is, i → i 6∈ D and i ↔ i 6∈ B for all i ∈ V . If (V, D) does not contain any directed
cycles i → . . . → i, then the mixed graph G is said to be acyclic.
Let RD be the set of real V × V -matrices Λ = (λij ) with support in D, that is,

(2.6)
RD = Λ ∈ RV ×V : λij = 0 if i → j ∈
/D .

D
Define RD
reg to be the subset of matrices Λ ∈ R for which I − Λ is invertible. If G
is acyclic, then there is a permutation of V that makes I − Λ unit upper triangular
such that det(I − Λ) = 1 for all Λ ∈ RD and thus RD = RD
reg . Similarly, let PD V
be the cone of positive definite symmetric V × V -matrices Ω = (ωij ), and define
PD(B) to be the subcone of matrices supported over B, that is,

(2.7)
PD (B) = Ω ∈ PD V : ωij = 0 if i 6= j and i ↔ j ∈
/B .

Taking the error vector ε to be Gaussian (or in other words, to follow a multivariate normal distribution), we arrive at the following definition of a statistical model
for the random vector X that solves (2.1). Readers looking for background such
as the fact that linear transformations of a Gaussian random vector are Gaussian
may consult a textbook on multivariate statistics, e.g., [2].

6

MATHIAS DRTON

λ13

1
λ12

3
λ23

2

λ34
ω24

4

Figure 2.1. An acyclic mixed graph known as the Verma graph.
Definition 2.1. The linear structural equation model given by a mixed graph
G = (V, D, B) is the family of all multivariate normal distributions on RV with
covariance matrix in the set

MG = (I − Λ)−T Ω(I − Λ)−1 : Λ ∈ RD
reg , Ω ∈ PD (B) .
The covariance parametrization of the model is the map
φG : RD × PD(B) → PD V ,

(Λ, Ω) 7→ (I − Λ)−T Ω(I − Λ)−1 ,

for which we define the fiber of a pair (Λ, Ω) ∈ RD
reg × PD (B) to be the preimage
 ′ ′
′
′
(2.8)
FG (Λ, Ω) = (Λ , Ω ) ∈ RD
reg × PD (B) : φG (Λ , Ω ) = φG (Λ, Ω) .

As defined, a linear structural equation model does not impose any restrictions
on the mean vector of the normal distributions. Consequently, the mean vector
plays no role in our discussion. For instance, in maximum likelihood estimation we
may assume without loss of generality that the mean vector is zero. Other questions
we consider will directly concern the covariance matrices of the model. Therefore,
we may safely identify a linear structural equation model with its set of covariance
matrices MG . On occasion, we will simply refer to MG as the model.
Leaving statistics out of the picture, our interest is in the maps φG , their fibers
FG and their images MG . Algebra comes into play naturally.
Proposition 2.1. For any mixed graph G, the map φG is a rational map whose
image MG and fibers FG (Λ, Ω) are semi-algebraic sets. The map φG is a polynomial
map if and only if G is acyclic.
Proof. That φG is rational follows from Cramer’s rule for matrix inversion. The domain of φG is a semi-algebraic set and, thus, the fibers FG (Λ, Ω) are semi-algebraic
as well. The Tarski-Seidenberg theorem implies that MG is semi-algebraic. If
G = (V, D, B) is acyclic, then det(I − Λ) = 1 for all Λ ∈ RD . Consequently, the
entries of (I − Λ)−1 are polynomial in Λ. If G is not acyclic, then det(I − Λ) is a
non-constant polynomial. The Leibniz formula shows that its terms correspond to
collections of disjoint directed cycles in the graph; compare Theorem 1 in [41]. 
Example 2.2. The mixed graph G = (V, D, B) in Figure 2.1 encodes the structural
equations
X1 = λ01
+ ε1 ,
X2 = λ02 + λ12 X1
+ ε2
X3 = λ03 + λ13 X1 + λ23 X2 + ε3
X4 = λ04 + λ34 X3
+ ε4 .

STRUCTURAL EQUATION MODELS

7

Only the errors ε2 and ε4 may be dependent and the error covariance matrix is


ω11
0
0
0
 0 ω22
0 ω24 
.
Ω = 
 0
0 ω33
0 
0 ω24
0 ω44
Substracting the coefficient matrix from the identity gives


1 −λ12 −λ13
0
0
1
−λ23
0 

I −Λ = 
0
0
1
−λ34 
0
0
0
1
with det(I − Λ) = 1 and inverse

1 λ12
0 1
−1
(I − Λ) = 
0 0
0 0

λ13 + λ12 λ23
λ23
1
0


λ13 λ34 + λ12 λ23 λ34

λ23 λ34
.

λ34
1

To illustrate the form of the map φG , we display the coordinate function

(2.9)

φG (Λ, Ω)24 = λ12 λ13 λ34 ω11 + λ212 λ23 λ34 ω11 + λ23 λ34 ω22 + ω24 .
3. Questions of Interest

Structural equation models are used to empirically estimate, test and possibly
discover cause-effect relationships among a set of variables. In estimation and testing, the underlying graph is given. In discovery, we seek to estimate the underlying
graph, or in other words, perform model selection. In this section we give a broad
overview of algebraic problems that arise in the context of these statistical tasks.
Only some of the problems are treated in the remainder of the paper, in which we
focus on parameter identifiability and polynomial relations between covariances.
3.1. Parameter identification. When considering the model given by the mixed
graph G = (V, D, B), a first question is whether the effects of interest are identifiable, that is, whether they are determined by the joint distribution of the observed
variables. The importance of the question is clear: The joint distribution is what
can be estimated from data. In our setting of linear and Gaussian models, the problem is equivalent to deciding whether the coefficients λij in the linear structural
equations can be recovered from the covariance matrix of the variables.
Different notions of parameter identifiability translate into related but slightly
different algebraic problems. The most stringent identifiability property of a model
is to have all of its coefficients λij , i → j ∈ D, identifiable. In this case, we seek to
answer the following:
Question 3.1. Is the map φG is injective?
Injectivity of φG can be decided efficiently, as we will discuss in Section 7. However, injectivity can be too strong of a requirement because all fibers are required
to be singletons with FG (Λ, Ω) = {(Λ, Ω)}. Indeed, some interesting examples have
fibers that are not singletons.

8

MATHIAS DRTON

Example 3.1. The map φG fails to be injective when G is the graph for the
instrumental variable model from Example 1.2. The relation from (1.5) shows that
FG (Λ, Ω) = {(Λ, Ω)} if λ12 6= 0. If λ12 = 0, however, then the fiber is infinite.
Hence, all model parameters are identifiable as long as λ12 6= 0. In the context of
Example 1.2, this requires making an argument that higher tax rates impact the
amount of smoking.
In the example just given, FG (Λ, Ω) = {(Λ, Ω)} for generic choices of (Λ, Ω) ∈
RD
reg × PD(B). In this case, we call φG generically injective. We are led to:
Question 3.2. Is the map φG is generically injective?
It turns out that generic injectivity is more difficult to decide. The computational
complexity of the problem has not yet been determined. In Section 8, we review
methods to decide whether φG is generically injective as well as methods to decide
when the fibers are generically infinite.
When φG is not generically injective, its generic fibers may be discrete sets. This
property is known as local identifiability in the statistical literature. We will instead
speak of φG being generically finite-to-one to highlight that in our case a discrete
fiber is in fact finite because φG is rational. By the inverse function theorem, the
question of whether φG is generically finite-to-one is the same as:
Question 3.3. Does the Jacobian of φG have full column rank?
The fiber FG (Λ, Ω) is defined by the equation system φG (Λ′ , Ω′ ) = φG (Λ, Ω).
These equation systems have a generic number of complex solutions (i.e., the free
entries of Λ and Ω are allowed to be complex numbers).
Definition 3.1. The map φG is algebraically k-to-one if the equation systems
defining its fibers generically have k complex solutions. We call the number k the
algebraic degree of identifiability of G.
The degree of identifiability may be determined by Gröbner basis methods (see
Section 8). It is finite if and only if φG is generically finite-to-one. The main
theorem in Section 7.3 shows that if φG is injective then its inverse is rational,
which is the same as G having degree of identifiability one. Currently, there are no
combinatorial results about when the degree is finite but larger than one. Example
8(b) in [34] has degree 3 but fibers whose cardinality over the reals is either one or
three. To the author’s knowledge, no example has been discovered in which φG is
generically injective over the reals but algebraically k-to-one for k ≥ 2.
An important question that we will not address in detail is the identifiability
of only a single parameter λij for a designated edge of interest i → j ∈ D. This
amounts to checking whether in every fiber the coefficient for the edge has only a
single value. In other words, it must hold that λ′ij = λ′′ij whenever (Λ′ , Ω′ ) and
(Λ′′ , Ω′′ ) are in the same fiber. In Example 1.2, the fiber of a pair (Λ, Ω) with
λ12 = 0 is infinite but all pairs (Λ′ , Ω′ ) such a fiber have λ′12 = 0. Two well-known
graphical methods for identifying a single edge coefficient are the back-door and
the front-door criterion [49]; see also [11, 36].
3.2. Model dimension. Statistical tests may be used to assess whether a model
is compatible with empirical data. At an intuitive level, such tests are based on
computing a distance between data and model and comparing this distance to
typical distances that are obtained when data are generated from a distribution in

STRUCTURAL EQUATION MODELS

9

the model. For linear Gaussian models, a test can be thought off as assessing the
distance between the empirical (or sample) covariance matrix and the model MG .
Recall that we have defined MG as the set of covariance matrices.
The challenging part of designing a statistical test is to quantify, in a probabilistic
manner, what typical distances between data and model are. Many procedures rely
on asymptotic approximations that are obtained by letting the number of data
points grow to infinity. Under regularity conditions, limiting distribution theory
leads to consideration of so-called chi-square distributions, which are indexed by
an integer parameter. In our context, when testing the model given by the mixed
graph G = (V, D, B), the chi-square parameter is set equal to the codimension of
MG , where we think of MG as embedded in the space of symmetric matrices. This
gives concrete statistical motivation for:
Question 3.4. What is the dimension of MG ?
The model MG is parametrized by the coefficients and covariances associated
with the edges in D and B as well as the variances associated with the nodes in
V . Being a subset of the space of V × V symmetric matrices, MG has expected
dimension


|V |(|V | + 1)
.
min |V | + |D| + |B|,
2
The term |D| + |V | + |B| is the count of nodes and edges in G. Since MG is the
image of φG , its actual dimension is equal to the rank of the Jacobian of φG . A
review of the connection between dimension and Jacobian in a statistical context
is given in [38]. Question 3.4 is tied to parameter identifiability, most directly
to Question 3.3. If φG is generically finite-to-one, then MG has the expected
dimension |V | + |D| + |B|.
3.3. Covariance equivalence. Different graphs may induce the same statistical
model. For example, take V = {1, 2}, and let G1 be the graph with the single
edge 1 → 2. Let G2 and G3 be the graphs with single edge 1 ← 2 and 1 ↔ 2,
respectively. Then MG1 = MG2 = MG3 as each model is easily seen to be equal
to the entire cone of positive definite 2 × 2 matrices.
From an applied perspective, two different graphs G and G′ encode different
scientific/causal hypotheses. If MG = MG′ , then the two hypotheses cannot be
distinguished based on data from a linear and Gaussian structural equation model.
It is thus useful to be able to decide whether two graphs G and G′ are covariance
equivalent, that is, we would like to be able to answer:
Question 3.5. When do two maps φG and φG′ have the same image?
Existing results addressing this questions make comparisons between relations
among the entries of the matrices in each model, and we record:
Question 3.6. What are the algebraic relations among the coordinates of φG ?
Such relations are also of interest for statistical tests that assess whether the
model given by G is compatible with available data; see, e.g., [6, 11, 17]. We review
results on relations among the covariances in Sections 9-12. An important role is
played by determinants that represent probabilistic conditional independence in a
Gaussian random vector. We note that models can, in principle, also be distinguished using inequality constraints. However, as less is know about inequalities,

10

MATHIAS DRTON

we do not treat them here. Examples of models with latent variables for which a
full semi-algebraic description is available can be found in [25, 53].
Remark. As defined above, covariance equivalence is based on data that is observational, meaning that it is collected by merely observing the considered physical
system. The situation is different when experimental data is available, meaning,
that data is collected in different settings in which the system is subject to various
experimental interventions. We will not treat such interventional data in this paper.
Interested readers may find discussions of the problem in [43, 49, 57]. Similarly,
even for observational data, questions of equivalence differ from Question 3.5 in
non-linear models or linear models with Gaussian errors [26, 54].
3.4. Maximum likelihood. The parameters of linear structural equation models
are most commonly estimated using the technique of maximum likelihood. Suppose
we observe a sample X (1) , . . . , X (n) drawn independently from the multivariate
normal distribution with mean vector µ and covariance matrix Σ, which we denote
by N (µ, Σ). The joint distribution of the random vectors X (1) , . . . , X (n) is the
n-fold product of N (µ, Σ). The likelihood of the sample is the value of the joint
density of the product distribution at (X (1) , . . . , X (n) ). The likelihood function is
the function mapping the pair (µ, Σ) to the likelihood of the sample. The maximum
likelihood estimator (MLE) of (µ, Σ) under the model given by a mixed graph G is
the maximizer of the likelihood function when restricting Σ to be in MG .
Define the sample mean vector and the sample covariance matrix as
n
1
1 X (i)
X
and Sn = (X (i) − X̄n )(X (i) − X̄n )T ,
(3.1)
X̄n =
n i=1
n
respectively. It is convenient to treat the likelihood function on the log-scale. With
an additive constant omitted and n/2 divided out, the log-likelihood function is

(µ, Σ) 7→ − log det(Σ) − trace Σ−1 Sn − (X̄n − µ)T Σ−1 (X̄n − µ).

Because the considered models place no constraint on the mean vector, its MLE is
always X̄n . The MLE of Σ solves the problem of maximizing the function

(3.2)
ℓ(Σ) = − log det(Σ) − trace Σ−1 Sn

subject to Σ ∈ MG . Using the covariance parametrization, the MLE is found
by maximizing ℓ ◦ φG . A key problem is then understanding the existence and
uniqueness of the MLE. We record:
Question 3.7. For which sample covariance matrices Sn does the likelihood function ℓ ◦ φG achieve its maximum?
Graphical models theory solves Question 3.7 when G = (V, D, B) is an acyclic
digraph, i.e., has B = ∅ and D without directed cycles [46]. More generally, it
is well known that ℓ ◦ φG is bounded when Sn is positive definite but this is not
necessary [32]. An issue that is not well explored is the fact that even if ℓ ◦ φG is
bounded it may fail to achieve its maximum as the model MG need not be closed.
For instance, the model in Example 3.3 is not closed. We remark that Question 3.7
is closely related to a positive definite matrix completion problem that arises in ML
estimation for other types of graphical models [9, 63, 67].
In some models, the MLE is known to admit a closed-form expression as a
rational function of the data. Such models have maximum likelihood (ML) degree
equal to one, in the sense of the following:

STRUCTURAL EQUATION MODELS

1

λ12

2

3

λ43

11

4

Figure 3.1. Mixed graph for a bivariate seemingly unrelated regressions model.
Question 3.8. The MLE of Σ in model MG is an algebraic function of the data.
What is the degree of this function?
An introduction to the notion of ML degree is given in [21, Chapter 2]. Here, we
merely not that the ML degree is one when G is an acyclic digraph. More general
models may have higher ML degree and a log-likelihood function with more than
one local maximum. We exemplify this for a model discussed in detail in [19].
Example 3.2. Suppose we have data with sample covariance matrix
X1
X1

Sn =

X2
X3
X4

X2

X3

8 −5
 −5 27

 10
4
3
49

10
4
21
24



X4


3
49 
.
24 
114

The matrix is positive definite such that the log-likelihood function ℓ from (3.2) is
bounded above on the entire cone of positive definite matrices. More precisely, ℓ
has compact level sets, that is, for any constant c ∈ R the set of positive definite
matrices Σ with ℓ(Σ) ≥ c is compact [2].
Let G be the graph depicted in Figure 3.1. It is not difficult to show that the
parametrization φG admits a rational inverse. Let Σ = (σij ) satisfy Σ = φG (Λ, Ω)
with Λ = (λij ) ∈ RD and Ω = (ωij ) ∈ PD (B). Then
σ12
σ34
λ12 =
(3.3)
,
λ43 =
,
σ11
σ44
and the entries of Ω = (I − Λ)T Σ(I − Λ) are rational functions of Σ as well. All
the rational functions are defined on the entire cone of positive definite matrices
because σ11 , σ44 > 0. It is also clear that the considered map φG is proper, that is,
compact subsets of the positive definite cone have compact preimages under φG . It
follows that ℓ ◦ φG has compact level sets and, thus, achieves its maximum on the
open set RD × PD(B).
The critical points of ℓ ◦ φG satisfy a rational equation system, in which the
determinant of φG (Λ, Ω) appears in the denominator. Since the directed part of G
is acyclic the determinant is equal to the determinant of Ω. Clearing the denominator yields a polynomial equation system. Saturating the system with respect to
the determinant removes infeasible solutions with det(Ω) = 0. Computing a lexicographic Gröbner basis after the saturation shows that the critical points (Λ, Ω)
solve the equation
10583160 λ512 + 43115307 λ412 + 72738452 λ312
+ 55482894 λ212 + 8437660 λ12 − 4703765 = 0.
All other entries of Λ and also Ω solve linear equations whose coefficients depend
on λ12 and the data. We conclude that the MLE of Σ is an algebraic function of

12

MATHIAS DRTON

1
3

4

2

Figure 3.2. Mixed graph of a model with two instruments.
degree 5. We note that the displayed equation for λ12 has three real roots and,
thus, is not solvable by radicals.
3.5. Model singularities. As noted in Section 3.2, the distributions of test statistics are frequently approximated using asymptotic theory. For so-called likelihood
ratio tests, this asymptotic theory can be thought of as assessing infinitesimal distances between a positive semidefinite data matrix and the given model MG . The
data matrix is generated from a distribution that corresponds to a particular point
in MG . At a smooth point of MG , the distribution of the infinitesimal distance is
given by a chi-square distribution which is the distribution of the distance between
a Gaussian random vector and a linear space. At singular points, the distribution
is determined by the tangent cone at the considered point [15]. Singularities also
impact other approaches such as Wald tests [24], and it is important to clarify:
Question 3.9. Is the image of φG a smooth manifold? If not, what are the tangent
cones of the image?
We do not address the question explicitly in this paper. However, whenever φG
is injective (see Section 7) its image is smooth. Indeed, when φG is injective it has a
rational inverse whose domain of definition includes the cone of all positive definite
matrices [16]. The next example illustrates that not all models are smooth.
Example 3.3. Consider the mixed graph G = (V, D, B) from Figure 3.2. Let
Σ ∈ R4×4 be a positive definite matrix. Define the matrix
−1
Σ{3,4}.{1,2} = Σ{3,4},{1,2} Σ{1,2},{1,2}
,
and the Schur complement

Σ{3,4},{3,4}.{1,2} = Σ{3,4},{3,4} − Σ{3,4},{1,2} Σ{1,2},{1,2}
Change coordinates to the triple of 2 × 2 matrices

−1

Σ{1,2},{3,4} .


Σ{1,2},{1,2} , Σ{3,4}.{1,2} , Σ{3,4},{3,4}.{1,2} .

If Σ = φG (Λ, Ω) for Λ = (λij ) ∈ RD and Ω = (ωij ) ∈ PD (B), then


ω11
λ12 ω11
,
Σ{1,2},{1,2} =
λ12 ω11
ω22


λ13
λ23
Σ{3,4}.{1,2} =
,
λ13 λ34 λ23 λ34


ω33
ω34 + λ34 ω33
.
Σ{3,4},{3,4}.{1,2} =
ω34 + λ34 ω33 ω44 + 2λ34 ω34 + λ434 ω33

We observe that Σ is in the (topological) closure of MG if and only if Σ{3,4}.{1,2}
is a matrix of rank at most one. In order for Σ to be in MG it must also hold that
the second row of Σ{3,4}.{1,2} is zero only if the first row is zero.

STRUCTURAL EQUATION MODELS

13

Geometrically, the closure of MG is equivalent to the product of two cones of
positive definite 2×2 matrices and the set of 2×2 matrices of rank at most one. The
latter set is singular at the zero matrix. For more details see the related example
in [21, Exercise 6.4].
3.6. Singularities of fibers. Finally, without going into any detail, we note that
it is also of statistical interest to study the geometry of the fibers FG (Λ, Ω). In
particular, the resolution of singularities of FG (Λ, Ω) is connected to asymptotic
approximations in Bayesian approaches to model selection.
Bayesian methods assess the goodness-of-fit of a model by integrating the likelihood function with respect to a prior distribution. In models with many parameters,
the integration is over a high-dimensional domain and, thus, constitutes a difficult
numerical problem. While carefully tuned Monte Carlo methods can be effective,
it can also be useful to invoke asymptotics. For large sample size n, the integrated
likelihood function behaves like a Laplace integral. Under regularity conditions,
a Laplace approximation can yield accurate approximations that have been used
in many applications [42]. However, the models considered here may also lead to
singular Laplace integrals for which asymptotic approximations are more involved.
Asymptotic expansions for singular Laplace integrals are well-studied [3]. The
work of Sumio Watanabe brings the ideas to bear in the statistical context [70].
For several practically relevant settings, it has become tractable to determine or
bound the real log-canonical threshold and its multiplicity, which determine how the
integrated likelihood scales with the sample size n. This information can be used
in model selection [18]. Computing real log-canonical thresholds for data generated
under the distribution with covariance matrix φG (Λ, Ω) requires careful study of
the singularities of the fiber FG (Λ, Ω). Bounds on the thresholds can be obtained
from cruder information such as the dimension of the fiber.
Part II. Treks, Subgraphs and Decomposition
4. Trek Rule
In solving the problems from Section 3, it is desirable to exploit the connection
between the covariance parametrization φG of a structural equation model and the
underlying mixed graph G = (V, D, B). The trek rule that we present in this section
makes the connection precise and is behind results that allow one to answer some
of the questions we posed with efficient algorithms.
It is natural to expect the covariance between random variables Xi and Xj to
be determined by the semi-walks between the nodes i and j in the graph G. A
semi-walk is an alternating sequence of nodes from V and edges from either D or
B such that the endpoints of each edge are the nodes immediately preceding and
succeeding the edge in the sequence. In other words, a semi-walk is a walk that uses
bidirected or directed edges but is allowed to traverse directed edges in the ‘wrong
direction’. As we will see, only special semi-walks contribute to the covariance.
Definition 4.1. A trek τ from source i to target j is a semi-walk from i to j whose
consecutive edges do not have any colliding arrowheads. In other words, τ is a
sequence of the form
(a) i ← il ← · · · ← i1 ← i0 ←→ j0 → j1 → · · · → jr → j, or
(b) i ← il ← · · · ← i1 ←−−−− i0 −−−−→ j1 → · · · → jr → j.

14

MATHIAS DRTON

A trek has a left- and a right-hand side, denoted left (τ ) and right (τ ), respectively.
We have left (τ ) = {i0 , . . . , il , i} and right (τ ) = {j0 , . . . , jr , j} in case (a), and
left (τ ) = {i0 , . . . , il , i} and right (τ ) = {i0 , j1 , . . . , jr , j} in case (b). In case (b) the
top node i0 belongs to both sides. A trek τ from i to i may have no edges, in which
case i is the top node, left (τ ) = right (τ ) = {i}. We call such a trek trivial.
In an acyclic graph, if we think of directed edges pointing ‘downward’, then a
trek takes us up and/or down a ‘mountain’. Any directed path is a trek, in which
case |left (τ ) | = 1 or |right (τ ) | = 1 depending on the direction in which the path is
traversed. A trek may contain the same node on both its left- and right-hand sides.
If the graph contains a cycle, then the left- or right-hand side of τ may contain this
cycle, possibly repeated.
For a trek τ that contains no bidirected edge and has top node i0 , define a trek
monomial as
Y
λkl .
τ (Λ, Ω) = ωi0 i0
k→l∈τ

For a trek τ that contains a bidirected edge i0 ↔ j0 , define the trek monomial as
Y
λkl .
τ (Λ, Ω) = ωi0 j0
k→l∈τ

The following rule expresses the covariance matrix Σ as a summation over treks
[57, 72, 73]. We write T (i, j) for the set of all treks from i to j.
Theorem 4.1 (Trek rule). Let G = (V, D, B) be any mixed graph, and let Λ ∈ RD
and Ω ∈ PD (B). Then the covariances are
X
τ (Λ, Ω),
i, j ∈ V.
(4.1)
φG (Λ, Ω)ij =
τ ∈T (i,j)

Some clarification is in order. If G is acyclic, then the summation in (4.1) is
finite and yields a polynomial. If G contains a directed cycle, then the right-hand
side of (4.1) may yield a power series as shown in Example 4.2 below. Under
assumptions on the spectrum of Λ, the power series converges and yields the value
of φG (Λ, Ω)ij . These spectral conditions are also needed to give cyclic models an
interpretation of representing observation of an equilibrium [31, 45]. This said, it is
also useful to treat the series as a formal power series. If so desired, a combinatorial
description can also be given for a rational expression for φG (Λ, Ω)ij ; compare [14].
Proof of the trek rule. Writing (I − Λ)−1 = I + Λ + Λ2 + . . . , we observe that
X
Y
((I − Λ)−1 )ij =
(4.2)
λkl ,
τ ∈P(i,j) k→l∈τ

where P(i, j) is the set of directed paths from i to j in G. If G is acyclic, then
Λm = 0 for all m ≥ |V |, and the geometric series of matrices has only finitely many
nonzero terms. If G is cyclic the geometric series is infinite and converges if and
only if all eigenvalues of Λ have magnitude less than 1. Now, observe that a product
of three entries of (I − Λ)−T , Ω, and (I − Λ)−1 , respectively, corresponds to the
concatenation of two directed paths at a common top node or by joining them with
a bidirected edge. A top node represents a diagonal entry of Ω, and a bidirected
edge an off-diagonal entry of Ω.


STRUCTURAL EQUATION MODELS

λ12

2

λ12

2
ω22
2

λ12

ω11
1
ω11
1
3

λ13

λ12

λ13

λ34

3

4

λ23

2

15

3

4

2

λ34

ω24

4
4

Figure 4.1. Four treks in the graph from Figure 2.1.
Example 4.1. In Example 2.2, the coordinate function (φG )24 is a polynomial with
four terms; see (2.9). The terms correspond to the four treks shown in Figure 4.1.
Example 4.2. Let G be the graph from Figure 4.2, which contains the directed
cycle 2 → 3 → 4 → 2. Due to this cycle, det(I − Λ) = 1 − λ23 λ34 λ42 . As an example
of a coordinate of φG we select
 2
1
λ12 λ23 λ34 ω11 + λ12 λ13 λ34 ω11 (λ23 λ34 λ42 + 1)
φG (Λ, Ω)24 =
2
(1 − λ23 λ34 λ42 )

+λ213 λ234 λ42 ω11 + λ23 λ34 ω22 + λ234 λ42 ω33 + 2λ34 λ42 ω34 + λ42 ω44 .

To understand how this rational formula relates to the trek rule, let us focus on the
treks from 2 to 4 that use the bidirected edge 2 ↔ 4. There are then two treks for
which both left and right side are self-avoiding paths, namely,
τ1 : 2 ← 4 ↔ 3 → 4,

τ2 : 2 ← 4 ← 3 ↔ 4.

Both of these treks yield the same monomial and together contribute the term
2λ34 λ42 ω34 to (φG )24 . All other treks from 2 to 4 that use edge 2 ↔ 4 are obtained
by inserting directed cycles into τ1 or τ2 . For instance, inserting one cycle on the
left- and one on the right-hand side of τ1 gives
2 ← 4 ← 3 ← 2 ← 4 ↔ 3 → 4 → 2 → 3 → 4.
The monomials associated with these treks are
k

λ34 λ42 ω34 (λ23 λ34 λ42 ) ,

k = 1, 2, . . . .

The monomial for exponent k arises from k + 1 different treks; l = 0, 1, . . . , k cycles
are inserted on the left, the remaining k − l cycles are inserted on the right. Hence,
the contribution to (φG )24 made by all treks from 2 to 4 that use edge 2 ↔ 4 is
2

∞
X

k

(k + 1)λ34 λ42 ω34 (λ23 λ34 λ42 )

k=0

=

2λ34 λ42 ω34
,
(1 − λ23 λ34 λ42 )2

assuming that |λ23 λ34 λ42 | < 1. This explains one of the terms in the rational
expression for (φG )24 . The reasoning for the other terms is analogous.
5. Induced Subgraphs and Principal Submatrices
Suppose X = (Xi : i ∈ V ) follows the linear structural equation model given
by mixed graph G = (V, D, B), so Var[X] = φG (Λ, Ω) for some Λ ∈ RD
reg and
Ω ∈ PD (B). Let A ⊆ V be a subset of nodes. Then the covariance matrix of the

16

MATHIAS DRTON

1
3

4

2

Figure 4.2. A cyclic mixed graph.
subvector XA = (Xi : i ∈ A) is obtained by projecting to the relevant principal
submatrix, that is,
(5.1)

Var[XA ] = φG (Λ, Ω)A,A .

The resulting map (Λ, Ω) 7→ φG (Λ, Ω)A,A may be complicated, even when φG is
not.
Example 5.1. Suppose G = (V, D, ∅) is a directed graph with i → j ∈ D if
and only if i ∈
/ A and j ∈ A; the graph is thus bipartite. Then the image of
φG (Λ, Ω)A,A is the set of covariance matrices of a factor analysis model with |V \ A|
factors. Factor analysis models have complicated geometric structure, particularly
when V \ A has more than two elements [8, 20, 23, 62]. Open problems remain even
for |V \ A| = 1 when allowing additional directed edges among the nodes in A [47].
For a general mixed graph G = (V, D, B), let DA = D ∩ (A × A) be the set
of directed edges with both endpoints in A. Similarly, let BA ⊂ B be the set of
bidirected edges that have both endpoints in A. The subgraph induced by A is the
mixed graph GA = (A, DA , BA ). Example 5.1 and also already Example 1.1 show
that the covariance matrices obtained from φGA generally differ from those obtained
by projecting φG onto the A×A submatrix. However, as we now emphasize, induced
subgraphs are relevant in a special case.
Define the set of parents of a node i ∈ V as
pa(i) = {j ∈ V : j → i}.
A set of nodes A ⊆ V is ancestral if i ∈ A implies that pa(i) ⊆ A. The terminology
indicates that such a set contains all its ancestors, where an ancestor is a node
with a directed path to some node in A. Ancestral sets are obtained by recursively
removing sink nodes. We define node i to be a sink node of G if it is a sink of the
directed part (V, D), that is, if all directed edges incident to i have their head at i.
Theorem 5.1. Let G = (V, D, B) be a mixed graph, and let GA be the subgraph
induced by an ancestral set A ⊂ V . Then for all Λ ∈ RD
reg and Ω ∈ PD(B), we have
φGA (ΛA,A , ΩA,A ) = [φG (Λ, Ω)]A,A .
Proof. Let i, j ∈ A. By the trek-rule, the (i, j) entry of φG (Λ, Ω) is given by
summing the monomials associated to treks from i to j in G. Because A is ancestral,
a trek from i to j in G cannot leave A. Hence, the set of treks from i to j in G
coincides with the set of treks from i to j in the subgraph GA . Applying the
trek-rule to GA yields the claim.

Example 5.2. Take up Example 2.1. Clearly, node 3 is a sink in the graph from
Figure 1.2. Hence, the set {1, 2} is ancestral. Inspecting the matrix displayed

STRUCTURAL EQUATION MODELS

17

in (2.5), we see that removing the third row and column yields the matrix for the
induced subgraph 1 → 2.

6. Graph Decomposition
We now present a very useful graph decomposition, which allows one to address
several questions of interest by considering smaller subgraphs. The decomposition
for acyclic mixed graphs was introduced in work of Jin Tian [65, 66]. Here we
formulate the natural extension to possibly cyclic mixed graphs.
Consider partitioning the vertex set of a mixed graph G = (V, D, B) in two ways.
The first partition is given by the connected components of the bidirected part
(V, B). The second partition is obtained from the strongly connected components of
the digraph (V, D). For two distinct nodes to belong to the same strongly connected
component, there must be directed paths in either direction between them. Let
C(G) be the finest common coarsening of the two partitions. Two nodes i 6= j are
in the same block of C(G) if and only if they are connected by a path that uses only
edges that are bidirected or part of some directed cycle. Note that G is acyclic if
and only if all strongly connected components are singleton sets, in which case the
blocks of C(G) are simply the connected components of the bidirected part (V, B).
For a block C ∈ C(G), define
[
V [C] := C ∪
pa(i)
i∈C

to be the union of the block and all parents of nodes in the block. Let D[C] =
D ∩ (V [C] × C) be the set of directed edges with head in C. Let B[C] be the set
of bidirected with both endpoints in C.
Definition 6.1. The graphs G[C] = (V [C], D[C], B[C]), C ∈ C(G), form a decomposition of G, and we refer to them as the mixed components of G.
A graph decomposition partitions the edge set. As we are working with mixed
graphs both edge sets are partitioned in the decomposition. We note that the set
V [C]\C is the set of sources nodes of G[C]. Here, we define a source node as a node
that is a tail on all edges it is incident to, with the convention that both endpoints
of a bidirected edge are heads.
Example 6.1. The graph in Figure 6.1 has the bidirected components {1, 4}, {3},
and {2, 5}. The strong components of the directed part are {1}, {2, 3}, {4}, and {5}.
The finest common coarsening of the two partitions is {{1, 4}, {2, 3, 5}}. The graph
thus has two mixed components with vertex sets V [{2, 3, 5}] = {1, 2, 3, 4, 5} and
V [{1, 4}] = {1, 2, 3, 4}. The mixed component with vertex set V [{2, 3, 5}] contains
all edges with a head in {2, 3, 5}, and the second mixed component contains all
edges with a head in {1, 4}. The components are depicted in Figure 6.1.
→
For C ∈ C(G), define the projection πC
: RV ×V → RV [C]×V [C] by setting
(
λij if j ∈ C,
→
πC (Λ)ij =
0
if j ∈ V [C] \ C.

18

MATHIAS DRTON

3

2

5

3

2

=
1

3

5

2

+

4

1

4

1

4

Figure 6.1. A mixed graph is decomposed into its two mixed components.
↔
Define a second map πC
: RV ×V → RV [C]×V [C] by


ωij if i, j ∈ C,
↔
πC (Ω)ij = 1
if i = j ∈ V [C] \ C,


0
otherwise.

It projects onto the C × C submatrix of Ω and then adds an identity matrix as a
diagonal block over V [C] \ C. Define a subset of PD (B[C]) ⊂ RV [C]×V [C] as
PD I (B[C]) = {Ω = (ωij ) ∈ PD (B[C]) : ωii = 1 if i ∈ V [C] \ C} .
Then we have
→
: RD → RD[C]
πC

→
and πC
: PD (B) → PD I (B[C])

→
↔
because G[C] is a subgraph of G. With πC = (πC
, πC
), we obtain the isomorphism
Y
RD[C] × PD I (B[C]).
π = (πC )C∈C(G) : RD × PD (B) →
C∈C(G)

Example 6.2. Let G be the graph from Figure 6.1, which has C(G) = {{1, 4}, {2, 3, 5}}.
A matrix in RD is of the form


0 λ12 λ13
0
0
0 0 λ23 λ24 λ25 


0 λ34
0 
Λ=
.
0 λ32
0 0
0
0 λ45 
0 0
0
0
0
Its projections are

0
0

→
π{2,3,5}
(Λ) = 
0
0
0

λ12
0
λ32
0
0

λ13
λ23
0
0
0

0
0
0
0
0


0
λ25 

0 
,
λ45 
0


0
0

→
π{1,4}
(Λ) = 
0
0
0

An error covariance matrix in PD (B) has the form


ω11
0
0 ω14
0
 0 ω22
0
0 ω25 


0
0
ω
0
0 
Ω=
33

,
ω14
0
0 ω44
0 
0 ω25
0
0 ω55

0
0
0
0
0

0
0
0
0
0

0
λ24
λ34
0
0


0
0

0
.
0
0

STRUCTURAL EQUATION MODELS

19

and we have

1
0

↔
(Ω) = 
π{2,3,5}
0
0
0

0
ω22
0
0
ω25

0
0
ω33
0
0


0 0
0 ω25 

0 0 
,
1 0 
0 ω55


ω11
 0

↔
(Ω) = 
π{1,4}
 0
ω14
0

0
1
0
0
0

0 ω14
0 0
1 0
0 ω44
0 0


0
0

0
.
0
1

With these preparation in place we may state Tian’s theorem as follows. Recall
that PD V is our symbol for the cone of positive definite V × V matrices.
Theorem 6.1. Let G = (V, D, B) be a mixed graph with mixed components G[C] =
(V [C], D[C], B[C]) for C ∈ C(G). Then there is an invertible map τ such that the
following diagram commutes:

Q

RD
reg × PD (B)
x
π
y

D[C]
C∈C(G) Rreg

φG

−−−−−−−−−−→

(φG[C] )C∈C(G)

× PD I (B[C]) −−−−−−−−−→

Q

PD V
x
τ
y

C∈C(G) PD V [C]

In other words, τ ◦ φG = (φG[C] ◦ πC )C∈C(G) . Both τ and its inverse are rational
Qm
maps, defined on all of PD V and all of k=1 PD Vk , respectively.

Below we give a linear algebraic proof that makes τ and its rational nature explicit. Alternatively, a proof in probabilistic notation could be given by generalizing
the proof of [66, Lemma 1]. For the generalization, the nodes in the setup of [66]
may be replaced by the strong components of the directed part (V, D).
Theorem 6.1 is a very useful result as questions about φG can be answered by
studying, one by one, the maps φG[C] for the mixed components. The fact that
τ and τ −1 are rational is important. For instance, it allows one to obtain precise
algebraic information about parameter identifiability in the sense of Definition 3.1.

Corollary 6.1. The degree of identifiability of a mixed graph G is the product of
the degrees of identifiability of its mixed components G[C], C ∈ C(G). In particular,
φG is (generically) injective if and only if each φG[C] is so, for C ∈ C(G).
Our proof of Theorem 6.1 is presented in terms of Cholesky decompositions.
When applied to a Gaussian covariance matrix, the Cholesky decomposition corresponds to factoring the multivariate normal density into a product of conditional
densities, which is the connection to the probabilistic setting of [66]. We begin by
stating a lemma on uniqueness and sparsity in block-Cholesky decomposition.
If C is a partition of a finite set V , then we write Diag(C) for the space of blockdiagonal matrices. So, A = (aij ) ∈ RV ×V is in Diag(C) if and only if aij = 0
whenever i and j are in distinct blocks of C. If we order the blocks of the partition
as C = {C1 , . . . , Ck }, then we may define a space of strictly block upper-triangular
matrices Upper(C), which contains A = (aij ) ∈ RV ×V if and only if aij = 0
whenever i ∈ Cu and j ∈ Cv with u ≥ v.
Lemma 6.1. Let Σ ∈ PD V , and let C be a partition of V , with ordered blocks.
(i) There exist unique matrices A ∈ Upper(C) and ∆ ∈ Diag(C) such that
Σ = (I − A)−T ∆(I − A)−1 .
The matrix ∆ has positive definite diagonal blocks.

20

MATHIAS DRTON

(ii) Let C ′ be a second partition of V that is coarser than C. If Σ ∈ Diag(C ′ ),
then the matrix A from (i) satisfies A ∈ Diag(C ′ ).
Proof. (i) A block-LDL decomposition yields Σ = (I + L)∆(I + L)T for unique
LT ∈ Upper(C) and ∆ ∈ Diag(C). Unit block upper-triangular matrices form
a group and, thus, (I + L)−T = I − A for A ∈ Upper(C). (ii) The claim is a
consequence of the way fill-in occurs when computing the Cholesky decomposition
of a sparse matrix [68, Section 4.1].

Proof of Theorem 6.1. We first show that, for every block C ∈ C(G), there exists
a map τC such that τC ◦ φG = φG[C] ◦ πC . Let Λ ∈ RD
reg , Ω ∈ PD (B), and
Σ = φG (Λ, Ω). Then the claim is that


−T 
−1


0 ΛC,C
0 ΛC,C
I
0
I−
(6.1)
.
τC (Σ) = I −
0 ΩC,C
0 ΛC,C
0 ΛC,C
Let C(D) be the partition of V given by the strongly connected components
of (V, D). Order the blocks of C(D) topologically as W1 , . . . , Wk such that the
existence of a directed path from a node in Wu to a node in Wv implies that v ≥ u.
By Lemma 6.1(i), there are A ∈ Upper(C(D)) and ∆ ∈ Diag(C(D)) such that
(6.2)

Σ = (I − A)−T ∆(I − A)−1

Letting C = V [C] \ C, we define


−T 
0 AC,C
I
(6.3)
τC (Σ) = I −
0
0 AC,C

0
∆C,C



I−


−1
0 AC,C
.
0 AC,C

If G is acyclic then Λ is strictly upper-triangular under a topological ordering
and, thus, Λ ∈ Upper(C(D)). When G has directed cycles, then Λ is block uppertriangular but not strictly so. Hence, we consider the block-diagonal matrix
∆Λ = diag(I − ΛW,W : W ∈ C(D)),
which is invertible because det(I − Λ) = det(∆Λ ) and Λ ∈ RD
reg . Hence,




−1
−T
−1
(6.4)
Σ = (I − Λ)∆−1
∆−1
(I − Λ)∆−1
.
Λ
Λ Ω∆Λ
Λ
Because ∆Λ , Ω ∈ Diag(C(G)), we have

−1
Ω̃ = ∆−T
∈ Diag(C(G)).
Λ Ω∆Λ

Moreover, due to the block upper-triangular shape of Λ,
Λ̃ = I − (I − Λ)∆−1
∈ Upper(C(D)).
Λ
By Lemma 6.1(i) and (ii), there are ∆Ω ∈ Diag(C(D)) and U ∈ Upper(C(D)) ∩
Diag(C(G)) such that
(6.5)

Ω̃ = (I − U )−T ∆Ω (I − U )−1 .

Combining (6.4) and (6.5) gives

−T

−1
(6.6)
Σ = (I − Λ̃)(I − U )
∆Ω (I − Λ̃)(I − U ) ,

where (I − Λ̃)(I − U ) = I − (Λ̃ + U − Λ̃U ) with Λ̃ + U − Λ̃U ∈ Upper(C(D)).
By the uniqueness in Lemma 6.1(i), equations (6.2) and (6.6) imply that
(6.7)

∆ = ∆Ω ,

(6.8)

A = Λ̃ + U − Λ̃U.

STRUCTURAL EQUATION MODELS

21

Since U ∈ Diag(C(G)), we have that

 

0
U(V \C)×C
.
=
(6.9)
UV ×C =
UC×C
UC×C
Therefore, by (6.8), AC,C = Λ̃C,C + UC,C − Λ̃C,C UC,C , and we deduce that
(6.10)

I − AC,C = (I − Λ̃C,C )(I − UC,C ) and AC,C = Λ̃C,C (I − UC,C ).

Moreover,
(6.11)

Ω̃C,C = (I − UC,C )−T ∆C,C (I − UC,C )−1 ,

which follows from (6.7) and the fact that
 




0 
0
−1

=
,
(I − U ) V,C =
(I − U )−1 C,C
(I − UC,C )−1

which in turn follows from U being in Diag(C(G)).
Substituting the formulas from (6.10) into (6.3) yields that
(6.12) τC (Σ) =


I
0

−T

−Λ̃C,C
I
0
0 I − UC,C
I − Λ̃C,C

 

I
−Λ̃C,C
I
I
0
×
0
0 ∆C,C
0 I − Λ̃C,C

Using (6.11), we get that
−T 

I
I
0
(6.13)
0
0 I − UC,C


I
0
∆C,C
0

0
I − UC,C

Recalling the definition of ∆Λ and Λ̃, we have

 

I
−Λ̃C,C
I
−ΛC,C
I
(6.14)
=
0
0 I − ΛC,C
0 I − Λ̃C,C

−1

0
I − UC,C


I
=
0

0
(∆−1
Λ )C,C

−1

0
Ω̃C,C



.

.



Plugging (6.13) and (6.14) into (6.12), we obtain the claim from (6.1).
The entries of the matrices A and ∆ in (6.2) are rational functions of Σ that are
defined on all of PD V . Hence, the same is true for the map τC defined in (6.3).
The value of τC (Σ) uniquely determines the matrices AC,C , AC,C , and ∆C,C in
(6.3). They are determined through a block LDL decomposition and, thus, rational
functions of τC (Σ). Knowing the three matrices for all C ∈ C(G), we can form A and
∆ and recover Σ using (6.2). Hence, τ is invertible and the inverse is rational. 

Part III. Parameter Identification
7. Global Identifiability
This section discusses Question 3.1, which asks for a characterization of the
mixed graphs G = (V, D, B) for which the map φG is injective. In the statistical
literature a model with injective parametrization is also called globally identifiable.

22

MATHIAS DRTON

Example 7.1. If G is the graph from Figure 3.1, then φG is injective. Indeed, the
coefficients for the two directed edges of G satisfy σ11 λ12 = σ12 and σ44 λ43 = σ34 ;
recall (3.3). Since every positive definite matrix Σ = (σij ) ∈ R4×4 has σ11 , σ44 > 0,
these two equations always have a unique solution. Hence, all fibers FG (Λ, Ω) are
singleton sets. In contrast, if G is the graph from Figure 1.2, then only generic
fibers are singleton sets and φG is not injective; recall Example 3.1.
Our first observation ties in with classical linear algebra.
Theorem 7.1. If G = (V, D, ∅) is an acyclic digraph, then φG is injective and has
a rational inverse.
We give two proofs. The first one emphasizes the connection to Cholesky decomposition.
Proof A. Suppose V = {1, . . . , m} is enumerated in reversed topological order such
that i → j ∈ D implies that j < i. Then Λ is a strictly lower-triangular matrix,
and φG (Λ, Ω) has matrix inverse (I − Λ)Ω−1 (I − Λ)T . This is the product of a unit
lower-triangular matrix, a positive diagonal matrix and a unit upper-triangular
matrix. We may compute I − Λ and Ω−1 by an LDL decomposition.

The second proof emphasizes the graphical nature of the problem and possible
sparsity of Λ. It shows more explicitly that the inverse of φG is rational.
Proof B. Letting Σ = (σij ) = φG (Λ, Ω), we have that
(7.1)

Σpa(i),i = Σpa(i),pa(i) Λpa(i),i

because if j ∈ pa(i), then every trek from j to i ends with an edge k → i for
k ∈ pa(i). Indeed, a trek from j to i for which this fails has to be a directed path
from i to j. Adding the edge j → i to this path would yield a directed cycle.
Similarly, every nontrivial trek from i to i begins and ends with a directed edge
whose tail is a parent of i. Hence,
(7.2)

σii = ωii + ΛTpa(i),i Σpa(i),pa(i) Λpa(i),i .

The matrix Σpa(i),pa(i) is a principal submatrix of the positive definite matrix Σ
and, thus, invertible. Therefore,
−1
Λpa(i),i = Σpa(i),pa(i)
(7.3)
Σpa(i),i ,
−1
ωii = σii − Σi,pa(i) Σpa(i),pa(i)
Σpa(i),i .


Proof B shows that the formula from (7.3) holds more generally. It merely needs
to hold that every trek from a node j ∈ pa(i) to i ends with a directed edge with i
as its head, so an edge of the form k → i. This holds for every node in the graph if
and only if the graph is ancestral [50]. A mixed graph is ancestral if the presence
of a directed path from node i to node j implies that i 6= j and i ↔ j ∈
/ B. An
ancestral graph is in particular acyclic.
The next easy lemma is crucial for the understanding of injectivity of φG .
Lemma 7.1. If φG is injective and H ⊆ G is a subgraph, then φH is injective.
Proof. Any subgraphs can be obtained by removing edges one at a time, and then
removing isolated nodes. If H is obtained from G = (V, D, B) by removing the
edge i → j, then φH is the restriction of φG to the subset of matrices Λ ∈ RD
reg
that have λij = 0. If we instead remove the edge i ↔ j, then the restrictions is to

STRUCTURAL EQUATION MODELS

1

(a)

3
2

1
4

(b)

23

3
2

4

Figure 7.1. (a) A mixed graph for which the parametrization φG
is injective. (b) A graph for which φG is not injective.
matrices Ω ∈ PD (B) with ωij = 0. If H is obtained by removing the isolated node
i, then


φH (Λ, Ω) 0
.
φG (Λ, Ω) =
0
ωii
In either case non-injectivity of φH implies non-injectivity of φG .

Corollary 7.1. If φG is injective, then G is simple, that is, for any vertices i 6= j
at most one of the three edges i ↔ j, i → j and i ← j may appear in G.
Proof. If G is not simple then it contains a subgraph H with two nodes and two
edges. The map φH is infinite-to-one as it maps a four-dimensional domain into
the three-dimensional set of symmetric 2 × 2 matrices. Now apply Lemma 7.1. 
Theorem 7.2. If φG is injective, then G is acyclic.
Proof sketch. By Lemma 7.1, we may restrict to studying directed cycles 1 → 2 →
. . . → m → 1. The case of m = 2 is covered by Corollary 7.1. If m ≥ 3, then
it is possible to show that φG is generically 2-to-1, that is, the fiber FG (Λ, Ω) is
generically of size two [16].

It remains to characterize injectivity for acyclic graphs G = (V, D, B). The
following theorem shows that injectivity can be decided in polynomial time by
alternatingly decomposing the bidirected part (V, B) into connected components
and removing sink nodes of the directed part (V, D).
Theorem 7.3. Suppose G is an acyclic mixed graph. Then:
(a) φG is injective if and only if G does not contain a subgraph whose bidirected
part is connected and whose directed part has a unique sink.
(b) If φG is injective, then its inverse is rational and MG smooth.
Figure 7.1 illustrates the characterization in part (a) of the theorem. The fact
that φG is not injective if the combinatorial condition in (a) fails can be shown by
a counterexample for the particular subgraph and then invoking Lemma 7.1. For
a proof of the sufficient condition in Theorem 7.3, we refer the reader to [16]. We
note that the sufficiency of the condition for injectivity can be proven by repeatedly applying the graph decomposition result in Theorem 6.1 and the result on
ancestral subgraphs from Theorem 5.1. These results as well as Theorem 7.3 have
generalizations to nonlinear structural equation models [56, 66].
8. Generic Identifiability
The difference between injectivity and generic injectivity of φG may appear
minute. However, the two properties are quite different, and failure of generic
injectivity cannot be argued by studying subgraphs (as in Lemma 7.1). According
to Corollary 7.1, a mixed graph G can have the map φG injective only if it is acyclic

24

MATHIAS DRTON

and simple. The deeper issue is then to find out which simple acyclic mixed graphs
have φG injective. In contrast, the next result shows that all simple acyclic mixed
graphs are generically injective. The deeper issue for generic injectivity is thus the
treatment of graphs that contain directed cycles or are not simple.
Theorem 8.1. If G = (V, D, B) is acyclic and simple, then φG is generically
injective and algebraically one-to-one.
The theorem is due to [7]. It shows that the graph from Figure 7.1(b) has φG
generically injective, but not injective. A short proof of Theorem 8.1 is obtained
through the following observation that we use repeatedly in this section.
Lemma 8.1. Let G = (V, D, B) be a mixed graph, and let Σ = φG (Λ0 , Ω0 ) for
Λ 0 ∈ RD
reg and Ω0 ∈ PD (B). The fiber FG (Λ0 , Ω0 ) is isomorphic to the set of
matrices Λ ∈ RD
reg that solve the equation system


(8.1)
(I − Λ)T Σ(I − Λ) ij = 0,
i 6= j, i ↔ j ∈
/ B.
Proof. The projection (Λ, Ω) 7→ Λ maps FG (Λ0 , Ω0 ) to the set of matrices Λ ∈ RD
reg
that solve the equations in (8.1). Indeed, as I − Λ is invertible for Λ ∈ RD
reg ,
Σ = φG (Λ, Ω) = (I − Λ)−T Ω(I − Λ) =⇒ Ω = (I − Λ)T Σ(I − Λ).
Any entry of Ω that is indexed by a pair (i, j) with i 6= j and i ↔ j ∈
/ B is zero.
Conversely, if Λ ∈ FG (Λ), then (Λ, (I − Λ)T Σ(I − Λ)) ∈ FG (Λ, Ω).

We emphasize that the equations in (8.1) are bilinear as
X
X
X


σil λlj +
λki σki −
(I − Λ)T Σ(I − Λ) ij = σij −
k∈pa(i)

l∈pa(j)

X

λki σkl λlj .

k∈pa(i) l∈pa(j)

Proof of Theorem 8.1. Because G is acyclic, we may enumerate the vertex set in a
topological order as V = {1, . . . , m}. Then pa(i) ⊆ {1, . . . , i − 1} for i = 1, . . . , m.
Moreover, because G is simple, j ∈ pa(i) implies that j ↔ i ∈
/ B. By Lemma 8.1,


T
i = 1, . . . , m.
(I − Λ) Σ(I − Λ) pa(i),i = 0,
These equations can be rewritten as




(8.2)
(I − Λ)T Σ pa(i),pa(i) Λpa(i),i = (I − Λ)T Σ pa(i),i ,

i = 1, . . . , m.

By the tolopogical order, if j ∈ pa(i), then the entries in the j-th row of (I − Λ)T Σ
depend only on the first i − 1 columns of Λ. The system in (8.2) can thus be solved
recursively, where each step requires solving a linear system.
To show that φG is generically injective, it remains to argue that the equations
in (8.2) generically have a unique solution. It suffices to exhibit a single pair (Λ, Ω)
for which this is true. We may choose Λ = 0 and Ω = I, so Σ = I. Then the matrix
for the i-th group of equations in (8.2) is Σpa(i),pa(i) , which is invertible.

Although a combinatorial characterization of the graphs with generically injective parametrization φG is not known, Gröbner basis techniques can be used to determine the degree of identifiability from Definition 3.1 and, thus, decide whether
φG is algebraically one-to-one. Gröbner bases are computationally tractable for
non-trivial examples and have been used for a classification of all graphs with up
to 5 nodes [34]. For larger graphs, algebraic methods can be applied after decomposition according to Theorem 6.1.

STRUCTURAL EQUATION MODELS

25

We describe two options for the computation. In either case, we advocate
working with the equation system from (8.1) as opposed to the fiber equation
Σ = φG (Λ, Ω). System (8.1) has Ω eliminated and may be far more compact as
it avoids the inversion of I − Λ. This said, although system (8.1) is polynomial
also for graphs that contain directed cycles, care must be taken to avoid spurios
solutions with I − Λ non-invertible.
The first possibility is to perform a parametric Gröbner basis computation. We
introduce a matrix Λ whose nonzero entries λij , i → j ∈ D, are indeterminates
and a pair of matrices (Λ0 , Ω0 ) that are parameters. We form the matrix (I −
Λ)T φG (Λ0 , Ω0 )(I − Λ) and set to zero the off-diagonal entries indexed by non-edges
of the bidirected part (V, B). We then compute a Gröbner basis for the resulting
system in the polynomial ring with coefficients in the field of rational fractions
R(Λ0 , Ω0 ). The Gröbner basis readily yields the dimension of the generic fibers. If
the dimension is finite we may also find the algebraic degree of the generic fibers,
which is what we referred to as degree of identifiability. When the graph G contains
directed cycles, the matrix I − Λ can be non-invertible. We thus first saturate our
equation system with respect to det(I − Λ).
Example 8.1. The following code for the system Singular [13] implements the
approach just described for a directed 3-cycle:
LIB "linalg.lib"; option(redSB);
ring R = (0,l012,l023,l031,w011,w022,w033),(l12,l23,l31),dp;
matrix L[3][3] = 1,-l12,0,
0,1,-l23,
-l31,0,1;
matrix L0[3][3] = 1,-l012,0,
0,1,-l023,
-l031,0,1;
matrix W0[3][3] = w011,0,0,
0,w022,0,
0,0,w033;
matrix W[3][3] = transpose(L)*inverse(transpose(L0))*W0*inverse(L0)*L;
ideal GB = sat(ideal(W[1,2],W[1,3],W[2,3]), det(L))[1];
dim(GB); mult(GB);

The output from the last line first certifies that the fibers are generically zerodimensional, that is, contain finitely many points. The multiplicity computed with
the last command shows the degree of identifiability to be two.
The second possibility is to consider only polynomials with real-valued coefficients but to introduce as polynomial variables the nonzero entries of Λ as well as a
symmetric matrix Σ. These variables are ordered with respect to a block monomial
order in which the variables in Λ are larger than the variables in Σ. Let I be the
ideal generated by the off-diagonal entries of (I − Λ)T Σ(I − Λ) that are indexed by
the non-edges of (V, B). Saturate I with respect to det(I − Λ). Let J be the reduced Gröbner basis of the resulting ideal. Elimination theory yields the following
[34, Section 8 of the supplemental material].
Proposition 8.1. The parametrization φG of a mixed graph G = (V, D, B) is
algebraically one-to-one if and only if for each i → j ∈ D, the reduced Gröbner
basis J contains an element with leading monomial a(Σ)λij .

26

MATHIAS DRTON

More generally, the generic dimension and degree of the fibers FG (Λ, Ω) can be
determined by analyzing the monomials under the staircase of the initial ideal of
J [12, Chapter 9]. This way we may determine the degree of identifiability of G.
In comparison to the first approach, the second method yields relations that show
how to identify coefficients λij from Σ.
Example 8.2. Treating again a directed 3-cycle, we give an example of the second
type of computation in Singular:
LIB "linalg.lib"; option(redSB);
ring R = 0,(l12,l23,l31,s11,s12,s13,s22,s23,s33),(dp(3));
matrix L[3][3] = 1,-l12,0,
0,1,-l23,
-l31,0,1;
matrix S[3][3] = s11,s12,s13,
s12,s22,s23,
s13,s23,s33;
matrix W[3][3] = transpose(L)*S*L;
ideal GB = sat(ideal(W[1,2],W[1,3],W[2,3]), det(L))[1]; GB;

The output is a list of 9 polynomials whose leading terms are, in our usual notation,
λ23 λ31 σ23 ,

λ12 λ31 σ13 ,

λ12 λ23 σ12 ,

λ12 λ31 σ12 σ33 ,

λ12 σ11 σ13 σ23 ,

λ12 λ23 σ11 σ23 ,

λ23 σ12 σ13 σ22 ,

λ23 λ31 σ13 σ22 ,

λ231 σ13 σ22 σ33 .

By Proposition 8.1, φG is not algebraically one-to-one because there is no leading
term of the form λ31 a(Σ). The last leading term belongs to a polynomial that
shows that λ31 is algebraic function of degree 2 of the covariance matrix Σ because
it solves the equation
2
2
2
λ231 σ33 (σ13 σ22 − σ12 σ23 ) − λ31 (σ13
σ22 − σ11 σ23
− σ12
σ33 + σ11 σ22 σ33 )

+ σ11 (σ13 σ22 − σ12 σ23 ) = 0.
The equations with leading terms λ23 σ12 σ13 σ22 and λ12 σ11 σ13 σ23 show that λ23
and λ12 are rational functions of Σ and λ31 . Altogether, we have verified that φG
is algebraically 2-to-one. Checking this by counting monomials under the staircase
means considering the leading monomials considering only the variables λ12 , λ23 , λ31
we seek to solve for. The monomials are
(8.3)

λ23 λ31 ,

λ12 λ31 ,

λ12 λ23 ,

λ12 ,

λ23 ,

λ231 ,

and generate the ideal I = hλ12 , λ23 , λ231 i. The monomials under the staircase are
the monomials in R[λ12 , λ23 , λ31 ] \ I. There are two, namely, 1 and λ31 .
Although Gröbner basis methods can be effective, it is desirable to obtain combinatorial methods that are efficient also for large-scale problems. The half-trek
criteria of [34] are state-of-the-art criteria that can be checked in time that is polynomial in the size of the vertex set of the considered graph. They provide a sufficient
as well as a necessary condition for generic injectivity of φG . More precisely, there
is a condition that is sufficient for φG to be algebraically one-to-one and a related
condition that is neessary for φG to be generically finite-to-one. The conditions are
implemented in a package for the R project for statistical computing [4]. We begin
our discussion of the half-trek criteria by introducing some needed terminology.
A half-trek from source node i to target node j is a trek τ from i to j whose
left-hand side is a singleton set, so left (τ ) = {i}. In other words, a half-trek is of

STRUCTURAL EQUATION MODELS

27

the form
i → j1 → . . . → jr → j or i ↔ j1 → . . . → jr → j.
Let X, Y ⊆ V be two sets of nodes of equal cardinality |X| = |Y | = k. Let Π be a
set of k treks. Then Π is a system of treks from X to Y , denoted Π : X ⇒ Y , if X
is the set of source nodes of the treks in Π and Y is the set of target nodes. Note
that we allow X ∩ Y 6= ∅. The system Π is a system of half-treks if every trek πi is
a half-trek. Finally, a system Π has no sided intersection if
left (π) ∩ left (π ′ ) = ∅ = right (π) ∩ right (π ′ )
for all pairs of treks π, π ′ ∈ Π.
Definition 8.1. A set Y ⊆ V satisfies the half-trek criterion with respect to node
i if (i) |Y | = | pa(i)|, (ii) j = i or j ↔ i implies that j 6∈ Y , and (iii) there exists a
system of half-treks Π : Y ⇒ pa(i) that has no sided intersection.
Theorem 8.2. Let G = (V, D, B) be a mixed graph.
(i) If for every i ∈ V there exists a set Yi ⊆ V that satisfies the half-trek
criterion with respect to i, and if there exists a total ordering ≺ such that
j ≺ i whenever j ∈ Yi and there is a half-trek from i to j, then φG is
generically injective and algebraically one-to-one.
(ii) For φG to be generically finite-to-one it is necessary that there exists a
family of subsets Yi ⊆ V , i ∈ V , such that Yi satisfies the half-trek criterion
with respect to i and j ∈ Yi implies i 6∈ Yj .
We merely outline the proof of the theorem; for details see [34]. Some of the
arguments are further illustrated in Example 8.3. Note also that Theorem 8.1 is
obtained from Theorem 8.2(i) by taking Yi = pa(i) and ≺ as a topological order.
Outline of proof of Theorem 8.2. (i) Let Σ = φG (Λ0 , Ω0 ) for Λ0 ∈ RD
reg and Ω0 ∈
PD(B). Suppose (Λ, Ω) ∈ FG (Λ0 , Ω0 ). To show that (Λ, Ω) = (Λ0 , Ω0 ), we visit
the nodes i ∈ V from smallest to largest in the order ≺ and iteratively find a linear
equation system that is uniquely solved by the i-th column of Λ. The starting point
is Lemma 8.1, by which we have


(8.4)
(I − Λ)T Σ(I − Λ) Yi ,i = 0, i ∈ V.
This is true because Definition 8.1 yields that j 6= i and j ↔ i ∈
/ B when j ∈ Yi .
Similar to the proof of Theorem 8.1, we may rearrange (8.4) to

Ai (Λ, Σ)Λpa(i),i = bi (Λ, Σ),




with Ai (Λ, Σ) = (I − Λ)T Σ Yi ,pa(i) and bi (Λ, Σ) = (I − Λ)T Σ Yi ,i . Both Ai (Λ, Σ)
and bi (Λ, Σ) can be shown to only depend on those columns of Λ that are indexed
by nodes j with a half-trek from i to j. Hence, the proof is complete if we can show
that Ai (Λ0 , Σ) is invertible for generic choices of Λ0 and Ω0 . To verify this, we may
use the existence of a half-trek system without sided intersection from Yi to pa(i)
to argue that the determinant of Ai (Λ0 , Σ) is not the zero polynomial. This last
step is in the spirit of the Lindström-Gessel-Viennot lemma.
(ii) We study the Jacobian of the equations from Lemma 8.1. Its rows are indexed
by the non-edges of the bidirected part (V, B) and its columns by the edges in D.
For φG to be generically finite-to-one, it is necessary that the Jacobian has full
column rank D. It can be shown that the Jacobian contains an invertible |D| × |D|
submatrix only if the given condition holds. Let Ji be the submatrix of the Jacobian

28

MATHIAS DRTON

1

3

2

5

4

Figure 8.1. Illustration of Theorem 8.2.
obtained by selecting the columns corresponding to directed edges with head at i.
Then, more specifically, Ji has full column rank only if there exists a subset Yi ⊆ V
that satisfies the half-trek criterion with respect to i. Moreover, if j ∈ Yi and i ∈ Yj ,
then the same row, namely, that corresponding to i ↔ j ∈
/ B, would be used to get
an invertible square submatrix of Ji and Jj .

The conditions from Theorem 8.2 seem involved but as we mentioned they can
be checked in polynomial time. Indeed, the problem of finding suitable sets Yi that
satisfy the half-trek criteria can be shown to correspond to solving network-flow
problems. For condition (i), we repeatedly solve a network-flow problem. Condition
(ii) can be implemented as a single larger network-flow problem [34, Section 6].
Example 8.3. Let G be the graph in Figure 8.1. Each one of the sets
Y1 = {2, 5},

Y2 = {5},

Y3 = ∅,

Y4 = ∅,

Y5 = {3}

satisfies the half-trek criterion with respect to the node it is indexed by. This is least
evident for Y1 , and we highlight the half-treks 2 ↔ 3 and 5 ↔ 4 → 2, which have
no sided intersection. Choosing the ordering as 3 ≺ 4 ≺ 5 ≺ 1 ≺ 2, Theorem 8.2(i)
shows that φG is algebraically one-to-one. Other possible orderings are obtained
by permuting {3, 4, 5} or {1, 2}.
To illustrate ideas from the proof of Theorem 8.2(i), we focus on node 1, with
pa(1) = {2, 3}. Since Y1 = {2, 5}, we work with the equations




(I − Λ)T Σ(I − Λ) 21 = 0.
(I − Λ)T Σ(I − Λ) 51 = 0,

Expanding out the matrix product, the equations become
(8.5)

σ51 − (σ52 λ21 + σ53 λ31 ) − λ35 σ31 + (λ35 σ32 λ21 + λ35 σ33 λ31 ) = 0,

(8.6)

σ21 − (σ22 λ21 + σ23 λ31 ) − λ42 σ41 + (λ42 σ42 λ21 + λ42 σ43 λ31 ) = 0,

and we wish to solve for λ21 and λ31 . With 5 ≺ 1, we have already solved for λ35 ;
since Y5 = pa(5) we have λ35 = σ35 /σ55 as is also clear from the discussion after
Proof B for Theorem 7.1. Substituting the ratio for λ35 turns (8.5) into a linear
equation in λ21 and λ31 . The equation in (8.6) could be linearized similarly, except
that now the relevant coefficient λ42 has not yet been determined in an ordering
with 1 ≺ 2. However, if Λ is part of a pair (Λ, Ω) in the fiber given by Σ, then
−λ42 σ41 + (λ42 σ42 λ21 + λ42 σ43 λ31 ) = 0
because there is no half-trek from 1 to 2. To see this note that the term λ42 σ41
corresponds to treks from 2 to 1 that start with the edge 2 ← 4, whereas the sum
λ42 σ42 λ21 + λ42 σ43 λ31 corresponds to treks from 2 to 1 that start with the edge
2 ← 4 and end in either 2 → 1 or 3 → 1. These two sets of treks coincide when
there is no half-trek from 1 to 2.

STRUCTURAL EQUATION MODELS

29

5

1

5

2

1

4

2

3

3
4

(a)

(b)

Figure 8.2. Graphs that satisfy the necessary but not the sufficient condition from Theorem 8.2: (a) φG is algebraically 3-to-one,
(b) φG is algebraically one-to-one and, thus, generically injective.
The sufficient condition from Theorem 8.2(i) can be strengthened by first applying the graph decomposition from Section 6 and then check condition (i) in
each subgraph. No such strengthening is possible for the necessary condition from
part (ii) of the theorem [34]. Further strengthening of the sufficient condition is
possible by first removing sink nodes from the graph using the observation from
Theorem 5.1. When a sink node is removed a more refined graph decomposition
may become possible; we refer the reader to [10, 22]. While a specific polynomialtime algorithm using this idea is given in [22], it is still unclear how to best design
algorithms based on recursive graph decomposition and removal of sink nodes.
We conclude our discussion of parameter identification with two examples from
the exhaustive computational study of graphs with up to 5 nodes in [34]. Both
graphs in Figure 8.1 satisfy the necessary condition in Theorem 8.2(ii) and, thus,
have φG generically finite-to-one. Neither graph satisfies the sufficient condition
from Theorem 8.2(i). The graph in panel (a) indeed does not have φG generically
injective. Instead, φG is algebraically 3-to-one. The graph in panel (b), however,
is algebraically one-to-one but Theorem 8.2(i) fails to recognize it. Decomposition
and removal of sink nodes do not help.
Part IV. Relations Among Covariances
9. Implicitization
Let MG be the set of covariance matrices of the structural equation model
given by a mixed graph G = (V, D, B). Motivated, in particular, by the covariance
equivalence problem from Question 3.5, we now discuss polynomial relations among
the entries of the matrices in MG . Let Σ = (σij ) be a symmetric V × V matrix of
variables, and let R[Σ] be the ring of polynomials in the σij with real coefficients.
Then the polynomial relations we seek to understand make up the vanishing ideal
I(G) = {f ∈ R[Σ] : f (Σ) = 0 for all Σ ∈ MG } .
Since MG is the image of the rational map φG , we may compute a generating set
for I(G) by implicitization. Assuming for simplicity that G is acyclic and, thus,
φG polynomial, we have
I(G) = h Σ − φG (Λ, Ω) i ∩ R[Σ].

30

MATHIAS DRTON

1

3
2

4

Figure 9.1. An acyclic digraph.

A better approach, however, is to start with the equations from Lemma 8.1, which
have Ω already eliminated. We compute
D
E

I(G) =
/ B ∩ R[Σ].
(I − Λ)T Σ(I − Λ) ij : i 6= j, i ↔ j ∈

If G is not acyclic, we saturate with respect to det(I − Λ) before intersecting with
R[Σ]; compare the examples in Section 8.

Example 9.1. To illustrate the use of a different software, we change to Macaulay2
[40]. The following code computes a generating set for the vanishing ideal of the
graph G shown in Figure 9.1:
R = QQ[l12,l13,l24,l34, s11,s12,s13,s14, s22,s23,s24, s33,s34, s44,
MonomialOrder => Eliminate 4];
Lambda = matrix{{1, -l12, -l13, 0},
{0, 1, 0, -l24},
{0, 0, 1, -l34},
{0, 0, 0, 1}};
S = matrix{{s11, s12, s13, s14},
{s12, s22, s23, s24},
{s13, s23, s33, s34},
{s14, s24, s34, s44}};
W = transpose(Lambda)*S*Lambda;
I = ideal{W_(0,1),W_(0,2),W_(0,3),W_(1,2),W_(1,3),W_(2,3)};
eliminate({l12,l13,l24,l34},I)

The ‘GraphicalModels’ package [37] automates the computation:
needsPackage "GraphicalModels";
G = digraph {{1,{2,3}},{2,{4}},{3,{4}}};
R = gaussianRing G;
gaussianVanishingIdeal R

Reproduced in our notation, the output shows that the ideal I(G) is generated by
the two polynomials
(9.1) f1 = σ12 σ13 − σ11 σ23 ,
2
(9.2) f2 = σ14 σ23
− σ13 σ23 σ24 − σ14 σ22 σ33 + σ12 σ24 σ33 + σ13 σ22 σ34 − σ12 σ23 σ34 .

Computing I(G) using Gröbner bases is a method that applies to any mixed
graph but can be computationally prohibitive for graphs with more than 5 or 6
nodes. In order to solve model equivalence problems combinatorial insight on particular types of relations is needed.
Example 9.2. Continuing with Example 9.1, observe that the two polynomials
f1 and f2 from (9.1) and (9.2) are determinants of submatrices of the covariance

STRUCTURAL EQUATION MODELS

matrix Σ. The following

σ11 σ12
 σ12 σ22

 σ13 σ23
σ14 σ24

two displays locate the submatrices


σ13 σ14
σ11 σ12 σ13
 σ12 σ22 σ23
σ23 σ24 


 σ13 σ23 σ33
σ33 σ34 
σ14 σ24 σ34
σ34 σ44

31


σ14
σ24 

σ34 
σ44

and show two boxes to visualize that each submatrix is obtained by bordering
a principal submatrix by one additional row and column. The determinants f1
and f2 are seen to be almost principal minors of Σ. As we discuss in Section 10,
the vanishing of almost principal minors of a Gaussian covariance matrix has a
particular probabilistic meaning, namely, conditional independence [60].
10. Conditional Independence
Suppose X = (Xi : i ∈ V ) is a Gaussian random vector indexed by a finite set V
and with covariance matrix Σ ∈ PD V . Let i, j ∈ V be two distinct indices, and let
S ⊆ V \{i, j}. The random variables Xi and Xj are conditionally independent given
XS if and only if det(ΣiS×jS ) = 0. This connection between Gaussian conditional
independence and the vanishing of almost principal minors of the covariance matrix
is explained in detail in [21, Chapter 3] and [48].
It is fully understood which conditional independence relations hold in the covariance matrices of a linear structural equation model. The following concepts
are needed to state the result. Let π be a semi-walk from node i to node j in the
considered mixed graph G = (V, D, B), and let node k be a non-endpoint of π. A
collider on π is a node k that is an internal node on π, and a head on the two edges
that precede and succeed k on π. We recall our convention that the two nodes
incident to a bidirected edge are both heads. Pictorially, π includes the segment
→ k ←, → k ↔, ↔ k ← or ↔ k ↔. A non-collider on π is an internal node of π
that is not a collider on π.
Definition 10.1. Fix a set S ⊆ V . Two nodes i, j ∈ V are d-connected by S if
G contains a semi-walk from i to j that has all colliders in S and all non-colliders
outside S. If no such semi-walk exists, then i and j are d-separated by S.
The following theorem was first proven for acyclic digraphs [39] and later extended to cover arbitrary mixed graphs [58].
Theorem 10.1. Let G = (V, D, B) be a mixed graph. Two nodes i, j ∈ V are dseparated by S if and only if det (φG (Λ, Ω)iS×jS ) = 0 for all Λ ∈ RD
reg , Ω ∈ PD (B).
For acyclic digraphs, the theorem can be derived in a probabilistic setup that
extends to non-Gaussian conditional independence [46]. When lecturing about the
result, the author likes to discuss the example with three binary variables shown
in Figure 10.1. In our linear Gaussian setting, Theorem 10.1 is a special case of
Theorem 11.1 that we treat in more detail.
Define the conditional independence ideal
ICI (G) = h det (ΣiS×jS ) : i, j d-separated by S i.
By Theorem 10.1, ICI (G) ⊆ I(G) for any mixed graph G. In Example 9.1, ICI (G) =
I(G) but this may be false even for acyclic digraphs [61]. Nevertheless, if G is an

32

MATHIAS DRTON
Boring talk?

Early morning talk?

Audience asleep?

Figure 10.1. A graph for three binary variables.
acylic digraph, then the set of covariance matrices MG is cut out by conditional
independence relations. In other words, for an acyclic digraph,
(10.1)

MG = V (ICI (G)) ∩ PD V

is the positive definite part of the variety of the conditional independence ideal. The
equality in (10.1) also holds when G is an ancestral graph, as defined in Section 7.
However, it is false in general as can be seen in Example 3.3. We remark that for
acyclic digraphs it has been proven that saturating the conditional independence
with respect to all principal minors yields the vanishing ideal [52]:
 Y
∞
I(G) = I CI (G) :
det(ΣA×A )
.
A⊂V

For acyclic digraphs and more generally ancestral graphs, the equality from (10.1)
allows us to answer Question 3.5 on covariance equivalence by checking whether
two graphs have the same d-separation relations. The latter comparison can be
accomplished in polynomial time. We state the result for acyclic digraphs [35, 69].
A generalization for ancestral graphs was given more recently [1]; see also [74].
Theorem 10.2. Let G and G′ be two acyclic digraphs. Then MG = MG′ if and
only if G and G′ have the same adjacencies and the same unshielded colliders. An
unshielded collider is an induced subgraph of the form i → j ← k.
We remark that it can also be decided in polynomial time whether two digraphs
that are not necessarily acyclic have the same d-separation relations [51]. When
the graphs have directed cycles then d-separation equivalence is necessary but not
sufficient for covariance equivalence; see, e.g., the example in [15].
11. Trek Separation
We now turn to the characterization of the vanishing of general minors of the
covariance matrices in a linear structural equation model. Our first example clarifies
the importance of minors that are not almost principal.
Example 11.1. If G is the graph from Figure 3.2 and Example 3.3, then I(G) is
generated by det(Σ12,34 ). Such off-diagonal 2 × 2 minors are known as tetrads in
the statistical literature; see [20] and the references therein.
The tetrad representation theorem gives a combinatorial characterization of the
vanishing of any 2 × 2 determinant [57]. The theorem has been greatly generalized, and we now have a full combinatorial understanding of when a minor of the
covariance matrix vanishes based on the notion of trek-separation [64]. Moreover,
the non-vanishing determinants can be described precisely [14].

STRUCTURAL EQUATION MODELS

33

Definition 11.1. Let A, C, SA , SC ⊆ V be sets of nodes of the mixed graph G =
(V, D, B). The pair (SA , SC ) trek-separates A and C if every trek from i ∈ A to
j ∈ C intersects SA on its left side or SC on its right side.
Theorem 11.1. Let G be a mixed graph. Then the A × C submatrix of φG (Λ, Ω)
has generic rank ≤ r if and only if there exist sets SA and SC with |SA | + |SC | ≤ r
such that (SA , SC ) trek-separates A and C.
The theorem for acyclic mixed graphs is proven in [64]. The cases with directed
cycles are covered by the results in [14]. We describe the ideas behind the proof.
Proof outline. The problem can be reduced to the case where G is a digraph by
subdividing bidirected edges. For each edge i ↔ j ∈ B we introduce a new node
{i, j} and two edges {i, j} → i and {i, j} → j. The new digraph G′ thus has
|V | + |B| nodes and |D| + 2|B| edges. If G is the mixed graph from Figure 1.2, then
G′ is the digraph in Figure 1.1. Every trek in G corresponds to a trek in G′ where
an edge i ↔ j in G corresponds to i ← {i, j} → j in G′ . The entries of (φG )A,C
and those of (φG′ )A,C can be shown to admit the same set of relations.
In the sequel, assume that G itself is a digraph. Then PD (B) contains diagonal
matrices with positive entries. The rank of φG (Λ, Ω) for Λ ∈ RD
reg and Ω ∈ PD (B)
is then the same as that of Σ = φG (Λ, I).
To establish the claim, we may study the vanishing of the determinants of square
submatrices. So assume that |A| = |C| = r + 1. The Cauchy-Binet formula gives
that




X


(11.1)
det (ΣA×C ) =
det (I − Λ)−1 E×A det (I − Λ)−1 E×C ,
E

where the sum is over subsets E ⊆ V of cardinality r + 1. By the Lindström-GesselViennot lemma for general digraphs, it holds that



(11.2)
det (I − Λ)−1 E×A = 0 for all Λ ∈ RD
reg ,

if and only if no system of r + 1 directed paths from E to A is vertex-disjoint.
Applying this to all terms in (11.1) shows that det (ΣA×C ) vanishes if and only if
every system of treks from A to C has a sided intersection. Here, an intersection
on the left side of a trek corresponds to the vanishing of determinants of the matrices (I − Λ)−1 E×A and, similarly, interesections on the right side are related to


the determinants of the matrices (I − Λ)−1 E×C . The characterization by sided
intersections in trek systems can be turned into the claimed statement about trekseparation via Menger’s theorem. To account for the distinct role played by the
left and the right sides of the treks, Menger’s theorem is applied in a digraph G̃
that results from duplicating the nodes and edges of G. Each node and each edge
of G has a left and a right side version in G̃. Menger’s theorem yields a cut set S of
cardinality |S| ≤ r in G̃. Partitioning S according to the left and right side yields
the pair (SA , SC ) for the claimed trek-separation.

Example 11.2. When G is the the graph from Figure 3.2, then the submatrix
[φG (Λ, Ω)]12,34 has generic rank 1; recall Example 11.1. Theorem 11.1 shows that
the rank is at least 1 because (∅, ∅) does not trek-separate {1, 2} and {3, 4}. For
instance, there is the trek 1 → 3. That the rank is no larger than 1 follows from
(∅, {3}) trek-separating {1, 2} and {3, 4}. For instance, the node 3 is on the right
side of the two treks 1 → 3 and 2 → 3 → 4.

34

MATHIAS DRTON

c

1

2

3

4

5

6

7

Figure 11.1. A ‘spider graph’ with {1, 2, 3, 4} × {5, 6, 7} submatrix of rank two.
Example 11.3. What is the generic rank of the A × C of φG (Λ, Ω) when G is the
‘spider graph’ from Figure 11.1, A = {1, 2, 3, 4} and C = {5, 6, 7}? The node c is
on every trek between A and C. It follows that ({c}, {c}) trek-separates A and C
and thus the rank is no larger than two. In fact, the rank is equal to two. Consider
the two treks
π1 : 1 ↔ ◦ → c → 5,
π2 : 3 ← c ← ◦ ↔ 6.
They have only node c in common but c ∈ right (π1 ) and c ∈ left (π2 ). Hence, a
pair of trek-separating sets must use at least two nodes.
Trek separation solves the problem of characterizing the vanishing of determinants. However, there is currently no efficient method for deciding when two mixed
graphs are trek separation equivalent.
12. Verma Constraints
Much interesting ground lies beyond determinants of the covariance matrix. We
content ourselves with two examples concerning a relation first presented in [69].
Example 12.1. Let G be the graph from Figure 2.1. The graph has no trekseparation relations as can be checked with the package ‘GraphicalModels’ for
Macaulay2 [37]. The commands
needsPackage "GraphicalModels";
G = mixedGraph(digraph {{1,{2,3}},{2,{3}},{3,{4}}}, bigraph {{2,4}});
R = gaussianRing G;
trekIdeal(R,G)

return the zero ideal. Issuing the command
gaussianVanishingIdeal R

shows that I(G) is generated by
2
(12.1) fVerma = σ11 σ13 σ22 σ34 − σ11 σ13 σ23 σ24 − σ11 σ14 σ22 σ33 + σ11 σ14 σ23
2
2
2
− σ12
σ13 σ34 + σ12
σ14 σ33 + σ12 σ13
σ24 − σ12 σ13 σ14 σ23 .

Clearly, fVerma is not a determinant. Its vanishing can be explained as follows.
Decompose G into its mixed components. The largest component G[{2, 4}] is depicted in Figure 12.1. Appealing to Theorem 6.1, there is a rational function
τ{2,4} : MG → MG′ , so τ{2,4} is the covariance matrix for G[{2, 4}]. In G[{2, 4}],

STRUCTURAL EQUATION MODELS

1

35

3

2

4

Figure 12.1. The largest mixed component of the Verma graph.

1

3

2

5

4

Figure 12.2. A graph that can be decomposed only after removing the sink node 5.
there is no trek from node 1 to node 4. Hence, the (1, 4) entry of τ{2,4} (Σ) is zero.
Clearing the denominator yields fVerma(Σ) = 0 for Σ ∈ MG .
The example suggests that new relations can be discovered by decomposing the
graph and studying d-separation or trek-separation relations in the mixed components. The matter is more delicate, however.
Example 12.2. In order to prevent decomposition of the Verma graph, add a
fifth node and bidirected edges such that (V, B) becomes connected. Specifically,
consider the graph G from Figure 12.2. The new graph G is simple and acyclic
and, thus, has expected dimension 13. Because the nodes 2 and 5 are d-separated
by 1, we have σ12 σ15 − σ11 σ25 ∈ I(G). Other relations must exist, and indeed a
Gröbner basis computation shows that
∞
I(G) = hσ12 σ15 − σ11 σ25 , fVermai : σ11

with fVerma being the polynomial from (12.1). The fact that fVerma ∈ I(G) is
explained by Theorem 5.1. Since no directed edge of G has a tail at node 5, the
theorem allows us to consider the subgraph induced by the set of nodes {1, 2, 3, 4}.
We are back in Example 12.1 and decomposition yields fVerma as a relation.
It is clear that more contrived examples can be constructed in which d-/trekseparation applies only after several rounds of alternating between graph decomposition and forming a subgraph induced by an ancestral set. An overview of what
is known about such a recursive approach can be found in [55], where the focus is
on non-linear models and manipulation of probability density functions.
13. Conclusion
Linear structural equation models have covariance matrices with rich algebraic
structure. As we showed in Section 3, statistical considerations motivate a host of
different algebraic problems. In this review, we focused on methods for parameter
identification as well as relations among covariances. While much progress has
been made, and continues to be made [30], we have encountered a plethora of open
problems of algebraic and combinatorial nature.

36

MATHIAS DRTON

In our review, we focused exclusively on linear and Gaussian models. As noted
repeatedly, many of the questions have interesting generalizations to non-linear or
non-Gaussian models. In particular, in settings with discrete random variables, as
considered in [27, 28], algebra and Gröbner basis techniques continue to be useful
[21]. Similarly, many additional challenges arise in models with explicit latent
variables, which motivate studying the map φG when projected onto a principal
submatrix (recall Section 5).
References
1. R. Ayesha Ali, Thomas S. Richardson, and Peter Spirtes, Markov equivalence for ancestral
graphs, Ann. Statist. 37 (2009), no. 5B, 2808–2837.
2. Theodore W. Anderson, An introduction to multivariate statistical analysis, third ed., Wiley
Series in Probability and Statistics, Wiley-Interscience [John Wiley & Sons], Hoboken, NJ,
2003. MR 1990662
3. Vladimir I. Arnol′ d, Sabir M. Guseı̆n-Zade, and Aleksandr N. Varchenko, Singularities of
differentiable maps. Vol. II, Monographs in Mathematics, vol. 83, Birkhäuser Boston, Inc.,
Boston, MA, 1988, Monodromy and asymptotics of integrals, Translated from the Russian by
Hugh Porteous, Translation revised by the authors and James Montaldi. MR 966191
4. Rina Foygel Barber, Mathias Drton, and Luca Weihs, Semid: Identifiability of linear structural equation models, 2015, R package version 0.2.
5. Kenneth A. Bollen, Structural equations with latent variables, Wiley Series in Probability and
Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons Inc., New
York, 1989, A Wiley-Interscience Publication. MR 996025 (90k:62001)
6. Kenneth A. Bollen and Kwok-fai Ting, A tetrad test for causal indicators, Psychological
methods 5 (2000), no. 1, 3.
7. Carlos Brito and Judea Pearl, A new identification condition for recursive models with correlated errors, Struct. Equ. Model. 9 (2002), no. 4, 459–474. MR 1930449
8. Andries E. Brouwer and Jan Draisma, Equivariant Gröbner bases and the Gaussian two-factor
model, Math. Comp. 80 (2011), no. 274, 1123–1133. MR 2772115
9. Søren L. Buhl, On the existence of maximum likelihood estimators for graphical Gaussian
models, Scand. J. Statist. 20 (1993), no. 3, 263–270.
10. Bryant Chen, Decomposition and identification of linear structural equation models, ArXiv
e-prints (2015), 1508.01834.
11. Bryant Chen, Jin Tian, and Judea Pearl, Testable implications of linear structural equations
models, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (Palo
Alto, CA) (Carla E. Brodley and Peter Stone, eds.), AAAI Press, 2014, pp. 2424–2430.
12. David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, third ed., Undergraduate Texts in Mathematics, Springer, New York, 2007, An introduction to computational
algebraic geometry and commutative algebra. MR 2290010 (2007h:13036)
13. Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann,
Singular 4-0-2 — A computer algebra system for polynomial computations,
http://www.singular.uni-kl.de, 2015.
14. Jan Draisma, Seth Sullivant, and Kelli Talaska, Positivity for Gaussian graphical models,
Adv. in Appl. Math. 50 (2013), no. 5, 661–674. MR 3044565
15. Mathias Drton, Likelihood ratio tests and singularities, Ann. Statist. 37 (2009), no. 2, 979–
1012. MR 2502658
16. Mathias Drton, Rina Foygel, and Seth Sullivant, Global identifiability of linear structural
equation models, Ann. Statist. 39 (2011), no. 2, 865–886.
17. Mathias Drton, Hélène Massam, and Ingram Olkin, Moments of minors of Wishart matrices,
Ann. Statist. 36 (2008), no. 5, 2261–2283. MR 2458187
18. Mathias Drton and Martyn Plummer, A Bayesian information criterion for singular models,
J. R. Stat. Soc. Ser. B. Stat. Methodol. (2016), to appear.
19. Mathias Drton and Thomas S Richardson, Multimodality of the likelihood in the bivariate
seemingly unrelated regressions model, Biometrika 91 (2004), no. 2, 383–392.
20. Mathias Drton, Bernd Sturmfels, and Seth Sullivant, Algebraic factor analysis: tetrads, pentads and beyond, Probab. Theory Related Fields 138 (2007), no. 3-4, 463–493. MR 2299716

STRUCTURAL EQUATION MODELS

21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.

34.
35.
36.

37.
38.

39.
40.
41.
42.
43.

44.
45.

46.
47.

37

, Lectures on algebraic statistics, Oberwolfach Seminars, vol. 39, Birkhäuser Verlag,
Basel, 2009. MR 2723140 (2012d:62004)
Mathias Drton and Luca Weihs, Generic identifiability of linear structural equation models
by ancestor decomposition, ArXiv e-prints (2015), 1504.02992.
Mathias Drton and Han Xiao, Finiteness of small factor analysis models, Ann. Inst. Statist.
Math. 62 (2010), no. 4, 775–783. MR 2652316
, Wald tests of singular hypotheses, Bernoulli 22 (2016), no. 1, 38–59. MR 3449776
Mathias Drton and Josephine Yu, On a parametrization of positive semidefinite matrices with
zeros, SIAM J. Matrix Anal. Appl. 31 (2010), no. 5, 2665–2680. MR 2740626 (2011j:15057)
Jan Ernest, Dominik Rothenhäusler, and Peter Bühlmann, Causal inference in partially linear
structural equation models: identifiability and estimation, ArXiv e-prints (2016), 1607.05980.
Robin J. Evans, Margins of discrete Bayesian networks, ArXiv e-prints (2015), 1501.02103.
Robin J. Evans and Thomas S. Richardson, Smooth, identifiable supermodels of discrete DAG
models with latent variables, ArXiv e-prints (2015), 1511.06813.
William N. Evans and Jeanne S. Ringel, Can higher cigarette taxes improve birth outcomes?,
Journal of Public Economics 72 (1999), no. 1, 135–154.
Alex Fink, Jenna Rajchgot, and Seth Sullivant, Matrix Schubert varieties and Gaussian conditional independence models, ArXiv e-prints (2015), 1510.04124.
Franklin M. Fisher, A correspondence principle for simultaneous equation models, Econometrica 38 (1970), 73–92.
Christopher Fox, Interpretation and inference of linear structural equation models, Ph.D.
thesis, University of Chicago, 2014.
Christopher J. Fox, Andreas Käufl, and Mathias Drton, On the causal interpretation of
acyclic mixed graphs under multivariate normality, Linear Algebra Appl. 473 (2015), 93–
113. MR 3338327
Rina Foygel, Jan Draisma, and Mathias Drton, Half-trek criterion for generic identifiability
of linear structural equation models, Ann. Statist. 40 (2012), no. 3, 1682–1713.
Morten Frydenberg, The chain graph Markov property, Scand. J. Statist. 17 (1990), no. 4,
333–353. MR 1096723
Luis D. Garcia-Puente, Sarah Spielvogel, and Seth Sullivant, Identifying causal effects with
computer algebra, Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence
(UAI) (Peter Grünwald and Peter Spirtes, eds.), AUAI Press, 2010.
Luis David Garcı́a-Puente, Sonja Petrović, and Seth Sullivant, Graphical models, J. Softw.
Algebra Geom. 5 (2013), 1–7. MR 3073716
Dan Geiger, David Heckerman, Henry King, and Christopher Meek, Stratified exponential
families: graphical models and model selection, Ann. Statist. 29 (2001), no. 2, 505–529.
MR 1863967
Dan Geiger, Thomas Verma, and Judea Pearl, Identifying independence in Bayesian networks,
Networks 20 (1990), no. 5, 507–534, Special issue on influence diagrams. MR 1064736
Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in
algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
Frank Harary, The determinant of the adjacency matrix of a graph, SIAM Rev. 4 (1962),
202–210. MR 0144330
Dominique M. A. Haughton, On the choice of a model to fit data from an exponential family,
Ann. Statist. 16 (1988), no. 1, 342–355. MR 924875
Alain Hauser and Peter Bühlmann, Jointly interventional and observational data: estimation
of interventional Markov equivalence classes of directed acyclic graphs, J. R. Stat. Soc. Ser.
B. Stat. Methodol. 77 (2015), no. 1, 291–318. MR 3299409
Jan T. A. Koster, Marginalizing and conditioning in graphical models, Bernoulli 8 (2002),
no. 6, 817–840.
Gustavo Lacerda, Peter Spirtes, Joseph Ramsey, and Patrik Hoyer, Discovering cyclic causal
models by independent components analysis, Proceedings of the Twenty-Fourth Conference
Annual Conference on Uncertainty in Artificial Intelligence (UAI-08) (Corvallis, Oregon),
AUAI Press, 2008, pp. 366–374.
Steffen L. Lauritzen, Graphical models, Oxford University Press, 1996.
Dennis Leung, Mathias Drton, and Hisayuki Hara, Identifiability of directed Gaussian graphical models with one latent source, Electron. J. Stat. 10 (2016), no. 1, 394–422. MR 3466188

38

MATHIAS DRTON

48. Radim Lněnička and František Matúš, On Gaussian conditional independent structures, Kybernetika (Prague) 43 (2007), no. 3, 327–342. MR 2362722
49. Judea Pearl, Causality, second ed., Cambridge University Press, Cambridge, 2009, Models,
reasoning, and inference. MR 2548166 (2010i:68148)
50. Thomas Richardson and Peter Spirtes, Ancestral graph Markov models, Ann. Statist. 30
(2002), no. 4, 962–1030. MR 1926166 (2003h:60017)
51. Thomas S. Richardson, A characterization of Markov equivalence for directed cyclic graphs,
International Journal of Approximate Reasoning 17 (1997), no. 2/3, 107–162.
52. Hajir Roozbehani and Yury Polyanskiy, Algebraic methods of classifying directed graphical
models, 2014 IEEE International Symposium on Information Theory, June 2014, pp. 2027–
2031.
53. Nathaniel Shiers, Piotr Zwiernik, John A. D. Aston, and Jim Q. Smith, The correlation
space of Gaussian latent tree models and model selection without fitting, Biometrika (2016),
forthcoming.
54. Shohei Shimizu, LiNGAM: Non-Gaussian methods for estimating causal structures, Behaviormetrika 41 (2014), no. 1, 65–98.
55. Ilya Shpitser, Robin Evans, Thomas Richardson, and James Robins, Introduction to nested
Markov models, Behaviormetrika 41 (2014), no. 1, 3–39.
56. Ilya Shpitser and Judea Pearl, Identification of joint interventional distributions in recursive semi-Markovian causal models, Proceedings of the Twenty-First National Conference on
Artificial Intelligence (Menlo Park, CA), AAAI Press, 2006, pp. 1219–1226.
57. Peter Spirtes, Clark Glymour, and Richard Scheines, Causation, prediction, and search, second ed., Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2000,
With additional material by David Heckerman, Christopher Meek, Gregory F. Cooper and
Thomas Richardson, A Bradford Book. MR 1815675 (2001j:62009)
58. Peter Spirtes, Thomas Richardson, Chris Meek, Richard Scheines, and Clark Glymour, Using
path diagrams as a structural equation modelling tool, Sociological Methods and Research 27
(1998), 182–225.
59. Paul D. Stolley, When genius errs: R. A. Fisher and the lung cancer controversy, Am. J.
Epidemiol. 133 (1991), no. 5, 416–425.
60. Milan Studený, Probabilistic conditional independence structures, Information Science and
Statistics, Springer, London, 2005. MR 3183760
61. Seth Sullivant, Algebraic geometry of Gaussian Bayesian networks, Adv. in Appl. Math. 40
(2008), no. 4, 482–513. MR 2412156
, A Gröbner basis for the secant ideal of the second hypersimplex, J. Commut. Algebra
62.
1 (2009), no. 2, 327–338. MR 2504939
63. Seth Sullivant and Elizabeth Gross, The maximum likelihood threshold of a graph,
arXiv:1404.6989, 2014.
64. Seth Sullivant, Kelli Talaska, and Jan Draisma, Trek separation for Gaussian graphical models,
Ann. Statist. 38 (2010), no. 3, 1665–1685. MR 2662356 (2011f:62076)
65. Jin Tian, Identifying direct causal effects in linear models, Proceedings of the Twentieth
National Conference on Artificial Intelligence (AAAI), 2005, pp. 346–353.
66. Jin Tian and Judea Pearl, A general identification condition for causal effects, AAAI/IAAI,
2002, pp. 567–573.
67. Caroline Uhler, Geometry of maximum likelihood estimation in Gaussian graphical models,
Ann. Statist. 40 (2012), no. 1, 238–261. MR 3014306
68. Lieven Vandenberghe and Martin S. Andersen, Chordal graphs and semidefinite optimization,
Foundations and Trends in Optimization 1 (2014), no. 4, 241–433.
69. Thomas S. Verma and Judea Pearl, Equivalence and synthesis of causal models, Uncertainty
in Artificial Intelligence 6, Elsevier, 1991, UCLA Cognitive Systems Laboratory, Technical
Report (R-150), pp. 255–268.
70. Sumio Watanabe, Algebraic geometry and statistical learning theory, Cambridge Monographs
on Applied and Computational Mathematics, vol. 25, Cambridge University Press, Cambridge,
2009. MR 2554932
71. Nanny Wermuth, Probability distributions with summary graph structure, Bernoulli 17 (2011),
no. 3, 845–879. MR 2817608
72. Sewall Wright, Correlation and causation, J. Agricultural Research 20 (1921), 557–585.
73.
, The method of path coefficients, Ann. Math. Statist. 5 (1934), no. 3, 161–215.

STRUCTURAL EQUATION MODELS

39

74. Hui Zhao, Zhongguo Zheng, and Baijun Liu, On the Markov equivalence of maximal ancestral
graphs, Sci. China Ser. A 48 (2005), no. 4, 548–562. MR 2157690 (2006e:62069)
Department of Statistics, University of Washington

