Partial Homoscedasticity in Causal Discovery With Linear Models

Jun Wu, Mathias DrtonIEEE J. Sel. Areas Inf. Theory 2023 · DOI · OpenReview

TL;DR

This paper introduces "partial homoscedasticity" for causal discovery in linear models, a framework that bridges the gap between assuming all error variances are arbitrary or all are equal. By partitioning variables into blocks with shared error variances, they develop a method to uniquely identify causal structures and represent equivalence classes using a refined CPDAG, outperforming existing methods in simulations.

What Problem Does This Paper Address?

Causal discovery aims to uncover the underlying causal relationships between variables from observational data. In the realm of linear structural equation models (SEMs), a key challenge is that different causal structures (represented by Directed Acyclic Graphs or DAGs) can produce the same observed data distribution. This leads to "Markov equivalence classes," where only a subset of the causal graph can be identified.

Traditionally, two extreme assumptions have been made:

  1. Arbitrary Error Variances: This is the most general case, but it limits identifiability to Markov equivalence classes.
  2. Homoscedastic Errors (All Equal Variances): This strong assumption allows for unique DAG identification but might be unrealistic.

This paper addresses the gap between these two extremes by proposing partial homoscedasticity. This means that instead of assuming all error variances are arbitrary or all are equal, we can assume that groups of variables share the same error variance, while different groups might have different variances. This allows for more nuanced prior knowledge about the data-generating process and potentially finer-grained causal discovery.

Methods

The core of the paper lies in developing a theoretical framework and an algorithm for causal discovery under partial homoscedasticity.

  • Partial Homoscedasticity Framework: The authors formalize this by defining a partition of the variables. Each block in the partition represents a group of variables whose errors are assumed to have equal variances. This framework naturally encompasses the arbitrary variance case (each variable in its own block) and the full homoscedasticity case (all variables in a single block).
  • Algebraic Characterization: They derive algebraic constraints that characterize these partially homoscedastic linear Gaussian SEMs. This involves combining conditional independence constraints (derived from d-separation in DAGs) with the new equal variance constraints.
  • Model Equivalence: A key theoretical contribution is the characterization of when two DAGs are "II-model equivalent" under a given partition II. This means they induce the same statistical model. They show this equivalence depends on the DAGs having the same skeleton and unshielded colliders, and specific parent set equalities for nodes within blocks of size two or more.
  • CPDAG Construction: To represent these equivalence classes, they generalize the concept of a Completed Partially Directed Acyclic Graph (CPDAG). They propose an efficient algorithm for constructing this II-CPDAG, which is an adaptation of existing algorithms for handling background knowledge.
  • Greedy Search for Model Selection: For practical causal discovery, they propose a greedy search algorithm that maximizes a Bayesian Information Criterion (BIC) score. This algorithm iteratively searches for DAGs with higher BIC scores in the local neighborhood, effectively leveraging the partial homoscedasticity information.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation studies using synthetic data.

Key Insights and Ideas

  • Bridging the Identifiability Gap: The most significant insight is that by relaxing the strict homoscedasticity assumption to "partial homoscedasticity," we can achieve finer-grained identifiability of causal structures than with arbitrary variances, without requiring the often unrealistic assumption of all equal variances.
  • Equal Variances as Structural Constraints: The paper demonstrates how assumptions about equal error variances translate into specific algebraic constraints on the covariance matrix. These constraints are crucial for distinguishing between DAGs that would otherwise be Markov equivalent.
  • Refined Equivalence Classes: The concept of II-model equivalence and the corresponding II-CPDAG provide a more precise way to represent the set of indistinguishable causal models under partial homoscedasticity. This is a direct generalization of the standard Markov equivalence class.
  • Algorithmic Efficiency: The development of an efficient algorithm for constructing the II-CPDAG is a practical advancement, making the theoretical framework applicable.
  • Greedy Search Effectiveness: The simulation results highlight that a greedy search strategy can effectively exploit partial homoscedasticity information to find better causal structures compared to methods that ignore this information.

Key Results

  • Theoretical Characterization: The paper provides a complete algebraic characterization of partially homoscedastic linear Gaussian SEMs, linking them to conditional independence and equal variance constraints.
  • Model Equivalence Theorem: Theorem 4.1 establishes the conditions under which two DAGs are equivalent under partial homoscedasticity, generalizing the classic Markov equivalence theorem.
  • Efficient CPDAG Construction: An algorithm is presented to construct the II-CPDAG, which represents the equivalence class under partial homoscedasticity.
  • Simulation Study Performance: The proposed greedy search algorithm (GEV) consistently outperforms standard methods like GES and PC in terms of Structural Hamming Distance (SHD) on synthetic data, especially in sparse settings. This demonstrates the practical benefit of incorporating partial homoscedasticity assumptions. The dense settings are more challenging, but GEV still shows competitive performance.

Limitations and Future Work

  • Linear Gaussian Models: The current framework is restricted to linear structural equation models with Gaussian errors. Extending this to non-linear models or non-Gaussian distributions would be a significant future direction.
  • Synthetic Data: The simulation study relies on synthetic data. While informative, testing the methods on real-world datasets with known or partially known ground truth would be valuable.
  • Greedy Search: While effective, greedy search algorithms are prone to local optima. Exploring more advanced search strategies or global optimization techniques could further improve performance.
  • Partition Selection: The paper assumes the partition (i.e., the knowledge about which error variances are equal) is given. Developing methods to learn or infer this partition from data would be a crucial next step for fully automated causal discovery.
  • Computational Complexity: While the CPDAG construction is efficient, the overall complexity of learning the DAG structure can still be high for large numbers of variables. Further optimizations might be needed.

Summary updated

Abstract

Recursive linear structural equation models and the associated directed acyclic graphs (DAGs) play an important role in causal discovery. The classic identifiability result for this class of models states that when only observational data is available, each DAG can be identified only up to a Markov equivalence class. In contrast, recent work has shown that the DAG can be uniquely identified if the errors in the model are homoscedastic, i.e., all have the same variance. This equal variance assumption yields methods that, if appropriate, are highly scalable and also sheds light on fundamental information-theoretic limits and optimality in causal discovery. In this paper, we fill the gap that exists between the two previously considered cases, which assume the error variances to be either arbitrary or all equal. Specifically, we formulate a framework of partial homoscedasticity, in which the variables are partitioned into blocks and each block shares the same error variance. For any such groupwise equal variances assumption, we characterize when two DAGs give rise to identical Gaussian linear structural equation models. Furthermore, we show how the resulting distributional equivalence classes may be represented using a completed partially directed acyclic graph (CPDAG), and we give an algorithm to efficiently construct this CPDAG. In a simulation study, we demonstrate that greedy search provides an effective way to learn the CPDAG and exploit partial knowledge about homoscedasticity of errors in structural equation models.
BibTeX
@article{wu2023partial,
  author = {Jun Wu and Mathias Drton},
  title = {{Partial Homoscedasticity in Causal Discovery With Linear Models}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2023},
  doi = {10.48550/arxiv.2308.08959},
}
Figure