High-dimensional learning of linear causal networks via inverse covariance estimation

Po-Ling Loh; Peter Bühlmann

Source-linked AI summary

High-dimensional learning of linear causal networks via inverse covariance estimation

Po-Ling Loh, Peter Bühlmann

arXiv:1311.3492v1Nov 14, 2013stat.MLmath.ST

TL;DR

The paper addresses DAG structure estimation for linear SEMs when distributions may be non-Gaussian and high dimensional. It estimates the moralized graph from inverse covariance support, then selects the best-scoring consistent DAG. The true DAG is uniquely selected when error variances are known or sufficiently accurate, with consistency under score-gap conditions and efficient dynamic programming for bounded treewidth.

Problem
DAG estimation in linear SEMs requires identifying a suitable search space and comparing candidate structures despite computational and distributional challenges.
Method
The framework estimates the moralized graph from inverse covariance support and selects the minimum-scoring DAG among structures consistent with it.
Results
The true DAG uniquely minimizes weighted squared l2-loss when error variances are known up to sufficiently accurate scaling, and the algorithm is statistically consistent under score-gap conditions.
Takeaways & Limitations
Dynamic programming can select the best-scoring DAG efficiently when the moralized graph has bounded treewidth.
Takeaways & Limitations
The scoring guarantee depends on using error-variance weights equal or sufficiently close to the true values, and the dynamic-programming runtime is exponential in treewidth.

Abstract

from arXiv · show

We establish a new framework for statistical estimation of directed acyclic graphs (DAGs) when data are generated from a linear, possibly non-Gaussian structural equation model. Our framework consists of two parts: (1) inferring the moralized graph from the support of the inverse covariance matrix; and (2) selecting the best-scoring graph amongst DAGs that are consistent with the moralized graph. We show that when the error variances are known or estimated to close enough precision, the true DAG is the unique minimizer of the score computed using the reweighted squared l_2-loss. Our population-level results have implications for the identifiability of linear SEMs when the error covariances are specified up to a constant multiple. On the statistical side, we establish rigorous conditions for high-dimensional consistency of our two-part algorithm, defined in terms of a "gap" between the true DAG and the next best candidate. Finally, we demonstrate that dynamic programming may be used to select the optimal DAG in linear time when the treewidth of the moralized graph is bounded.

1. Introduction

Inferring causal DAGs is computationally difficult, especially when the graph structure and a suitable undirected superstructure are unknown. The paper proposes a two-step framework that estimates the moralized graph from inverse covariance support and then scores consistent DAGs, with guarantees extending to non-Gaussian and high-dimensional settings.

Motivation: DAG estimation can require exponential search over vertex orders, while exhaustive graph search is tractable only for relatively small graphs.Greedy methods are faster but are not generally guaranteed to recover the correct graph.
Framework: The framework estimates inverse covariance support to construct a moralized graph, then searches consistent DAGs for the minimum-scoring structure.The procedure includes inverse covariance estimation, moralized-graph construction, score computation, and selection of the minimal-scoring DAG.
Graph recovery: For almost every choice of linear coefficients, inverse covariance support matches the moralized graph edge structure without Gaussianity assumptions.This result provides the theoretical basis for using inverse covariance estimation as a preprocessing step.
Scoring and identifiability: Under homoscedastic errors, the true DAG uniquely minimizes squared l2-loss, yielding identifiability for linear SEMs with error variances specified up to a constant multiple.The scoring result also covers settings with Gaussian and non-Gaussian errors.
Statistical guarantees: The method is statistically consistent under a score-gap condition and covariance eigenvalue conditions, without requiring a beta-min condition or a gap scaling linearly with graph size.The framework is designed for genuinely high-dimensional settings.
Corrupted data: The methods also apply when observations contain missing data or additive noise because inverse covariance estimation and regression scoring can be modified for systematic corruptions.The paper explicitly considers learning DAG structure under these forms of corruption.

2. Background

The paper reviews undirected and directed graphical models before specializing to linear structural equation models. It defines conditional-independence representations, DAG factorization and moralization, and the autoregression-matrix representation used for graph recovery.

Undirected graphs: A conditional independence graph represents a distribution when graph separation implies the corresponding conditional independences.For disjoint sets A, B, and S, separation of A from B by S implies X_A ⟂ X_B | X_S.
Undirected graphs: For strictly positive distributions, the Hammersley-Clifford theorem characterizes conditional independence graphs through clique potential functions.The complete graph is always a conditional independence graph, although sparser representations may exist.
Directed acyclic graphs: A DAG is a directed graph with no directed paths that start and end at the same node, and each node has a parent set consisting of its incoming neighbors.DAGs distinguish edge directions and admit topological orders.
Directed acyclic graphs: A DAG represents a distribution when the distribution factorizes according to its nodewise conditional distributions.This factorization implies conditional independence of each node from its nondescendants given its parents.
Graph transformations: Moralization fully connects each node’s parents and removes edge orientations, producing an undirected graph that is also a conditional independence graph for the represented distribution.The skeleton is contained in the moralized graph, which generally has more edges and is not itself necessarily a conditional independence graph.
Linear SEMs: In a linear SEM, the autoregression matrix B is strictly upper triangular, and nonzero entries define the DAG edges; recovering B therefore recovers the graph.The model assumes zero means and each error is independent of preceding variables.

3. Moralized graphs and inverse covariance matrices

The paper shows that the inverse covariance matrix of a linear SEM reflects the moralized DAG, extending the Gaussian graphical-model relationship. Under a converse sparsity assumption, its off-diagonal support exactly identifies moralized edges, generically except on a measure-zero set.

The analysis defines Θ as Σ^-1 and uses the best linear predictor together with the error covariance Ω to derive the inverse-covariance representation.The resulting equation underpins the connection between inverse covariance and moralized-DAG structure.
The inverse covariance matrix reflects the structure of the moralized DAG: nonedges have zero off-diagonal entries.This extends the corresponding result for multivariate Gaussian graphical models.
Theorem 2 establishes that Θ_jk = 0 whenever (j, k) is not an edge in M(G).The proof uses the absence of a direct edge and shared child, which eliminates the relevant terms in equation (4).
Assumption 1 supplies the converse implication, making Θ_jk = 0 if and only if (j, k) is not an edge in M(G).Together with Theorem 2, this gives exact support correspondence between Θ and the moralized graph.
When nonzero entries of B are independently sampled from continuous distributions, Assumption 1 holds for every B except on a Lebesgue measure-zero set.The assumption is characterized as a type of faithfulness condition.

4. Score functions for DAGs

The paper uses a weighted squared ℓ2-loss to score candidate DAGs in linear SEMs, showing that appropriate error-variance weighting makes the true DAG uniquely optimal. The analysis also establishes identifiability, robustness to variance misspecification, and gap-dependent behavior in small examples.

The framework scores candidate DAGs using a weighted squared ℓ2-loss under a linear SEM.Each coordinate's prediction error is weighted by the corresponding diagonal entry of the candidate weight matrix.
When error variances are specified up to a constant multiple, the true DAG uniquely minimizes the score.The result applies to linear SEMs with error covariance αΩ0, α > 0, and equality holds only at B = B0.
Correct weighting by the true error covariance makes squared ℓ2-loss an appropriate model-fit criterion, whereas incorrect weights can select an inappropriate structure.The theorem requires a multiple of the true error covariance; identity weighting may therefore be inconsistent with the true model.
The same population result yields identifiability for linear SEMs whose error covariance is known up to a scalar multiple, including homoscedastic models.This conclusion does not require Gaussian or universally non-Gaussian errors, although variance scaling or non-Gaussianity is needed for identifiability in general.
A positive score gap controls robustness to variance misspecification: larger gaps permit less accurate weight specification while preserving the true minimizer.Restricting the candidate search space can increase the relevant gap, and a variance window can justify unweighted squared ℓ2-loss in some heteroscedastic settings.
In two- and three-variable examples, the gap depends on edge strength and error-variance ratios, and can accumulate across successive edge reversals.For two variables, the gap grows with |b0| when |b0| > 1 and is symmetric in the sign of b0.

5. Consequences for statistical estimation

The paper estimates linear-SEM DAGs by first recovering a moralized graph from inverse covariance support, then selecting a minimum-score compatible DAG. Under sparsity and gap conditions, the procedure has high-dimensional consistency and extends to systematically corrupted data.

Inverse covariance estimation: High-dimensional recovery assumes a sufficiently sparse moralized DAG and estimates inverse covariance using graphical Lasso or nodewise ordinary Lasso.For p > n, the method assumes each row of the true inverse covariance is d-sparse; graphical Lasso consistency requires n ≥ C d log p.
Two-part estimation: The algorithm estimates the moralized DAG from inverse covariance support, then searches compatible DAGs for the minimum weighted squared ℓ2-score.Theorem 2 links inverse covariance support to the moralized graph, while Theorem 7 identifies the true DAG through scoring.
Score estimation: The empirical score selects the true DAG when estimation error is smaller than the gap separating it from the next-best candidate.A restricted candidate space can yield a larger gap, and the paper develops a weaker condition than the initial gap requirement.
Statistical rates: If ξ(DΘ) = Ω(1), consistency requires n ≥ C p^2 log p; if ξ(DΘ) = Ω(p), it requires log p / n → 0.The gap scaling therefore determines whether the guarantee is genuinely high-dimensional.
Gap refinements: For bounded-treewidth graphs, a weaker gap condition can suffice, although a full characterization for arbitrary graphs remains outside the paper’s scope.The paper expects analogous results for larger separator sets but does not provide that generalization.
Corrupted data: The method also accommodates systematically corrupted observations, with modified graphical Lasso estimates and score guarantees under analogous sub-Gaussian conditions.In the additive-noise setting, the modified inverse-covariance estimator is consistent under similar scaling to the uncorrupted case.

6. Computational considerations

The computational strategy reduces DAG search to a decomposable-score optimization over a graph estimated from inverse covariance structure. Tree-decomposition dynamic programming makes this optimization tractable for bounded treewidth, with overall complexity O(p^2) including preprocessing.

Search reduction: Searching all p! node orderings is exponential, motivating dynamic programming over DAGs whose skeleton lies within an input undirected graph.The input graph is supplied as a structural restriction for candidate DAGs.
Decomposable scoring: The squared ℓ2-score is decomposable, so the total DAG score is a sum of node-specific scores determined by each node and its parents.Other decomposable examples include maximum likelihood, BDe, BIC, and AIC.
Dynamic programming: Dynamic programming uses a nice tree decomposition and records partial DAGs, parent sets, directed paths, and scores while processing join, introduce, and forget nodes.The records retain only minimal-scoring partial candidates satisfying the skeleton restriction and acyclicity.
Alternative dynamic programming: A variant handles unbounded degree when treewidth is bounded, runs in time linear in p and exponential in w, and assumes the input graph contains the moralized DAG.Its practical efficiency depends on the structure of the moralized graph.

7. Discussion

The discussion summarizes inverse covariance as a way to reduce DAG search and weighted squared ℓ2-loss as a selector when error variances are sufficiently known. It also identifies unknown error variances as a central open problem.

Main conclusions: The inverse covariance matrix reflects the moralized DAG’s edge structure, even in non-Gaussian settings, under a mild faithfulness assumption.This relationship supplies the preprocessing step for reducing the candidate DAG space.
Main conclusions: When error variances are known up to close precision, weighted squared ℓ2-loss can select the correct DAG.The dynamic-programming stage then efficiently searches the restricted candidate space when the moralized graph has small treewidth.
Possible extensions: The dynamic-programming algorithm uses only skeleton containment and does not exploit linear-SEM structure or exact moral-graph equality.The authors suggest these additional restrictions could enable faster methods for bounded-degree graphs with large treewidth.
Open problem: Unknown error variances remain an open problem because misspecified weighting can produce a graph far from the true DAG.The paper also calls for checkable conditions or procedures for selecting the correct variance matrix.

Appendix B. Matrix derivations

The appendix develops matrix identities supporting the uniqueness of the true autoregression matrix under permutation-unit-lower-triangular structure. It also derives score comparisons using regression and gap arguments.

Matrix structure: A permutation-unit-LT matrix is permutation similar to a lower-triangular matrix with ones on its diagonal.This structure is used throughout the matrix uniqueness arguments.
Matrix uniqueness: If two permutation-unit-LT matrices have equal Gram matrices, they are equal, establishing uniqueness from A A^T = B B^T.The proof relabels one matrix into unit lower-triangular form and uses induction on entries.
Matrix inequality: The appendix proves a determinant-one positive-definite matrix inequality using singular values, trace identities, AM-GM, and Hadamard’s inequality.This result supplies the equality characterization used in the subsequent permutation-unit-LT lemma.
Regression argument: For a DAG containing the true graph, adding parent variables does not change the population regression coefficients for the original parents, while added-parent coefficients are zero.Acyclicity prevents added parents from being descendants, allowing the Markov property to yield the regression result.
Score comparison: For graphs excluding the true graph, the score gap bounds their population scores above the true score and supports strict separation under the stated assumptions.The proof combines the gap definition with score inequalities for candidate autoregression matrices.

C.4 Proof of Lemma 11

The proof reduces the candidate DAGs to maximal elements that do not contain the true DAG, then compares their score gaps using autoregression matrices and symmetry.

Score comparison: The candidate score differences are evaluated by direct calculations involving coefficients and error-variance terms.The displayed expressions provide the quantities used for the individual alternatives.
Candidate reduction: Figure 3 enumerates the alternative DAGs used to compute the gap ξ.The relevant candidates are represented through their autoregression matrices.
Candidate reduction: The proof considers only a relatively small set of maximal DAGs that do not contain the true DAG.This follows from score monotonicity under graph inclusion.
Score comparison: The remaining alternatives are obtained by swapping the roles of nodes 1 and 2, because panels (b) and (d) mirror panels (a) and (c).This symmetry reduces the number of distinct calculations.
Conclusion: Taking ξ = min{ξ1, ξ2, ξ3, ξ4} yields the desired lower bound for the gap.The minimum aggregates the four alternative-DAG comparisons.

D.2 Proof of Lemma 18

The proof establishes uniform deviation bounds for regression quantities over node and parent-set choices, then combines them with the population gap to obtain the consistency inequality.

Deviation bounds: For each fixed pair (j, S), the residual e_j is zero-mean and uncorrelated with x_S.The residual depends on the selected set S.
Gap argument: The proof combines the deviation inequalities with the definition of the gap ξ to bound score differences uniformly over candidate graphs.This yields inequality (23) for graphs that do not contain G0.
Deviation bounds: Sub-Gaussian tail bounds and union bounds control the relevant deviations simultaneously over j and all 2^d choices of S.The resulting probability bounds involve d and log p.
Gap argument: Assuming ξ′ > 0, the comparison between a candidate graph and a graph containing G0 implies the desired result.The argument uses the maximizer of γ_Ω(G, G1) and inequalities (27)–(28).

D.5 Proof of Lemma 23

The proof shows that, under a junction-tree moralized graph with singleton separators, each clique marginal remains a linear SEM with the restricted DAG and autoregression matrix, enabling clique-wise gap control.

Clique restriction: Each clique marginal follows a linear SEM whose DAG and autoregression matrix are restrictions of the full SEM.This holds when the junction tree has only singleton separators.
Clique restriction: A topological ordering of the full DAG induces a topological ordering within every clique.The proof uses the structural equation representation under this ordering.
Residual independence: For non-separator nodes, the clique parent set equals the full parent set, so the residual remains the original error term.The required independence follows from the SEM ordering.
Residual independence: For separator nodes, parents either all lie in the clique or none do, making the restricted independence condition valid in both cases.When no parents lie in the clique, the restricted parent set is empty and the condition is vacuous.
Gap aggregation: The proof constructs clique-wise graph extensions and combines their contributions to lower-bound γ_Ω(G0) by the minimum clique gap.Separator-node multiplicities contribute additional terms in the summed score.
Gap aggregation: Uniformly over candidate graphs, the resulting bound is γ_Ω(G0) ≥ min1≤ℓ≤k γ_Ω(Gℓ).Only cliques whose restricted graphs differ contribute to the final comparison.

D.6 Proof of Lemma 24

The proof derives uniform concentration by separately bounding two terms, expanding the second, and applying deviation conditions before a union bound over nodes and subsets.

Concentration argument: The first term is bounded directly using inequality (32) and a union bound over nodes.This is the initial component of the uniform concentration argument.
Concentration argument: The second term is controlled through an expansion and bounds obtained by inverting the deviation condition (32).The proof also applies the deviation condition to the enlarged set S′ := S ∪{j}.
Uniform bound: A union bound over the 2^d choices for S and p choices for j yields a uniform bound.The resulting failure probability has the form exp(−c′_2 log p).
Uniform bound: Combining the uniform bound with inequality (67) and expansion (66) gives the desired result.The proof presents this as the concluding step of the lemma.

Appendix E. Matrix concentration results

This appendix develops matrix concentration results used in the paper’s technical lemmas, for i.i.d. sub-Gaussian vectors, and records spectral-norm notation and proof steps.

The appendix presents matrix concentration results used to establish technical lemmas.The spectral norm is denoted by |||·|||2.
The concentration setting assumes i.i.d. sub-Gaussian vectors with parameter σ2 and covariance Σ.
The proof invokes a matrix inverse expansion for A + ∆ when A and A + ∆ are invertible and the series converges.The derivation rewrites (A + ∆)−1 through (I + A−1∆)−1A−1.
The resulting bounds are obtained using the triangle inequality and multiplicativity of the spectral norm.The appendix states that these steps give the result.