Filter, Rank, and Prune: Learning Linear Cyclic Gaussian Graphical Models

Soheun Yi, Sanghack LeeAISTATS 2024 · OpenReview

Abstract

Causal structures in the real world often exhibit cycles naturally due to equilibrium, homeostasis, or feedback. However, causal discovery from observational studies regarding cyclic models has not been investigated extensively because the underlying structure of a linear cyclic structural equation model (SEM) cannot be determined solely from observational data. Inspired by the Bayesian information Criterion (BIC), we construct a score function that assesses both accuracy and sparsity of the structure to determine which linear Gaussian SEM is the best when only observational data is given. Then, we formulate a causal discovery problem as an optimization problem of the measure and propose the Filter, Rank, and Prune (FRP) method for solving it. We empirically demonstrate that our method outperforms competitive cyclic causal discovery baselines.

Introduction

Most causal discovery methods assume the world is a Directed Acyclic Graph (DAG), but real-world systems like biology and climate are full of feedback loops. Causal discovery—the art of inferring "what causes what" from data—is notoriously difficult when the underlying system contains cycles. In the linear Gaussian setting, a major hurdle is distributional equivalence: multiple different cyclic graphs can produce the exact same observational data. Without interventions, we cannot distinguish between them.

This paper introduces FRP (Filter, Rank, and Prune), a robust three-stage algorithm designed to learn linear cyclic models from purely observational data by finding the simplest (sparsest) graph that accurately explains the statistical distribution. The authors invoke Occam’s Razor: among all graphs that explain the data equally well, the one with the fewest edges is preferred.

Methodology

The authors propose a score-based approach using a measure inspired by the Bayesian Information Criterion (BIC). This score balances model accuracy (how well the graph represents the data's precision matrix) against sparsity (the number of edges). In Gaussian models, the precision matrix encodes the entire structure, allowing the BIC score to be computed by comparing the estimated precision matrix of a candidate graph to the empirical precision matrix of the data.

The FRP algorithm operates in three distinct stages:

  1. Filter: To avoid searching through all $p^2$ possible edges, partial correlations are used to prune the initial search space. This relies on a novel $λ$-edge-faithfulness assumption, which posits that direct causal links will have non-vanishing statistical signatures.
  2. Rank: Remaining edges are fed into a non-convex optimization problem using the SCAD penalty to assign weights to potential edges without the bias of standard Lasso.
  3. Prune: The algorithm ranks these edges by weight and uses binary and sequential search to iteratively remove edges that do not significantly improve the BIC score.

Key Results

The paper evaluates FRP using both synthetic and real-world data. Synthetic benchmarks involved random Erdős-Rényi graphs with varying node counts ($p$) and edge densities ($e$). Real-world application focused on fMRI data from 24 healthy adults, specifically 10 subregions of the medial temporal lobe.

Comparison of BIC scores for FRP and baseline methods across different graph sizes (p) and edge densities (e).
  • Superior Sparsity and Robustness: As shown in the figure above, FRP consistently achieved lower BIC scores than competitive baselines like DGLEARN, GOLEM, and NODAGS-Flow. As graph density increased (e.g., from $e=19$ to $e=52$ for $p=15$), the performance gap widened, demonstrating FRP's robustness to complex feedback systems.
  • Biological Consistency: When applied to fMRI data, FRP identified symmetric connectivity patterns and highlighted regions like the Entorhinal Cortex (ERC) and Subiculum (SUB) as functional hubs, aligning with established neuroscience.
  • Efficiency: FRP proved more efficient than previous state-of-the-art cyclic learners like DGLEARN, especially as the number of nodes increased.

Conclusion and Future Work

While FRP shows significant promise, the authors identify areas for future research. The current implementation assumes full-rank data ($n > p$), requiring adaptation for high-dimensional "big p, small n" settings. Additionally, the pruning stage's greedy nature can lead to local optima, which might be mitigated by incorporating graph transformations. Finally, extending the framework beyond linear Gaussian models to non-linear or non-Gaussian relationships remains an open challenge.

Summary updated

Abstract

Causal structures in the real world often exhibit cycles naturally due to equilibrium, homeostasis, or feedback. However, causal discovery from observational studies regarding cyclic models has not been investigated extensively because the underlying structure of a linear cyclic structural equation model (SEM) cannot be determined solely from observational data. Inspired by the Bayesian information Criterion (BIC), we construct a score function that assesses both accuracy and sparsity of the structure to determine which linear Gaussian SEM is the best when only observational data is given. Then, we formulate a causal discovery problem as an optimization problem of the measure and propose the Filter, Rank, and Prune (FRP) method for solving it. We empirically demonstrate that our method outperforms competitive cyclic causal discovery baselines.
BibTeX
@inproceedings{yi2024filter,
  author = {Soheun Yi and Sanghack Lee},
  title = {{Filter, Rank, and Prune: Learning Linear Cyclic Gaussian Graphical Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=oSZtQdlyLr},
}
Figure