Identifiability of Linear AMP Chain Graph Models

Yuhao Wang, Arnab BhattacharyyaAAAI 2022 · DOI

Abstract

This paper addresses the fundamental challenge of identifiability in causal discovery for linear Andersson-Madigan-Perlman (AMP) chain graph models. While Directed Acyclic Graphs (DAGs) are standard, they often fail to capture complex dependencies like latent confounders or feedback loops. Chain graphs provide a more flexible framework by partitioning variables into components with directed causal relationships between them and undirected associative relationships within them. We present the first rigorous identifiability conditions for these models and introduce a polynomial-time algorithm, DCOV, which leverages the submodularity of the log-determinant of covariance matrices to recover causal structures even when chain components are unknown.

1. Introduction: Beyond Directed Acyclic Graphs

Causal inference typically relies on Bayesian Networks represented as DAGs. However, the assumption of independent noise terms in DAGs is often violated in real-world systems, such as gene regulatory networks. Chain graphs offer a middle ground, allowing for both directed (causal) and undirected (associative) relationships.

Examples of different chain graph structures with varying component groupings and edge types.

As shown in Figure 1, variables are partitioned into "chain components." The challenge lies in identifying both the grouping of these components and the directed edges between them from observational data, especially without relying on often-violated "faithfulness" assumptions.

2. The Challenge of Identifiability

A central problem in causal discovery is determining whether a specific graph structure can be uniquely recovered. In chain graphs, this involves distinguishing between different possible directions of edges between components.

Illustration of the identifiability problem: two different chain graphs with opposing edge directions between components.

Figure 6 illustrates this core ambiguity: given the same variables and components, should the relationship be $X_1 \to X_3$ or $X_3 \to X_1$? Previous methods struggled to resolve these directions without restrictive assumptions.

3. The DCOV Method and Submodularity

The authors introduce the DCOV (Determinant of Covariance) method, which handles two main scenarios:

  • Known Components: If components are predefined, the structure is identifiable if the determinants of residual covariance matrices follow a specific monotone order (e.g., equal or non-decreasing) according to the topological order.
  • Unknown Components: This is the paper's most significant contribution. The authors prove that the function $F(S) = \log \det(Cov(X_S))$ is submodular. Because the log-determinant is related to differential entropy, the authors can use efficient Submodular Function Minimization (SFM) algorithms to "peel off" the topologically earliest components one by one.

Algorithm 2 implements this as a greedy approach, using SFM at each step to identify the next valid chain component, revealing the entire causal ordering in polynomial time.

4. Key Results and Performance

The DCOV algorithm was evaluated on synthetic data and real-world DAG benchmarks (e.g., ECOLI70, MAGIC-NIAB).

  • Superior Accuracy: DCOV significantly outperformed baselines like PC-LIKE and LCD, achieving much lower Structural Hamming Distance (SHD), meaning the recovered graph was much closer to the ground truth.
  • Robustness: Even when applied to pure DAG data, DCOV often correctly identified the structure, sometimes surpassing DAG-specific methods.
  • Efficiency: The use of submodular minimization ensures the algorithm remains computationally feasible as the number of variables grows.

5. Conclusion and Future Work

This work provides a robust theoretical foundation for identifying AMP chain graphs. While currently constrained to Gaussian distributions and requiring specific variance/correlation patterns, it opens new avenues for high-dimensional causal discovery in fields like biology where latent correlations are prevalent. Future research will focus on extending these results to non-Gaussian and non-linear additive noise models.

Summary updated

BibTeX
@inproceedings{wang2022identifiability,
  author = {Yuhao Wang and Arnab Bhattacharyya},
  title = {{Identifiability of Linear AMP Chain Graph Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21247},
}
Figure