Research Overview

Traditional statistical analysis and machine learning primarily focus on revealing correlations among variables. However, for understanding complex socio-economic or biological phenomena, as well as for policy design and decision-making support, it is essential to identify the causal relationships underlying the data.

Within this context, causal inference aims to estimate intervention and counterfactual effects, while causal discovery seeks to estimate causal structures (directed acyclic graphs; DAGs) directly from observational data.

Recently, approaches that formulate causal discovery as a continuous optimization problem—notably exemplified by NOTEARS—have attracted much attention. These methods relax the combinatorial search of DAGs into a differentiable optimization framework. However, most existing approaches employ an \(L_1\)-norm penalty to promote sparsity, which has been shown to lack consistency over the Markov equivalence class of the true graph. Conversely, the \(L_0\)-norm penalty offers theoretical consistency but is non-continuous and thus difficult to optimize via gradient-based methods.

1. Model Assumptions & A-formulation

We consider a linear Structural Equation Model (SEM) with independent noise: where $B$ is the weighted adjacency matrix and $\Omega$ is a diagonal noise covariance matrix. We introduce the transformation: Under this A-formulation, the log-likelihood optimization is converted into finding a sparse, invertible matrix $A$ that respects the DAG constraint.

2. Coordinate Descent Algorithm

Our method optimizes the structure by updating one coordinate (edge) at a time. Unlike gradient-based methods that move along the steepest descent in continuous space, Coordinate Descent (CD) explores the discrete structure space by making locally optimal, discrete moves that are guaranteed to stay within the DAG manifold.

In each Epoch, the algorithm performs a random permutation of all unordered node pairs $\{i, j\}$. For each pair, we evaluate two potential directed edges ($i \to j$ and $j \to i$). The update is only accepted if it satisfies the acyclicity constraint and provides a larger objective decrease than the alternative direction.

Epoch-based Traversal Strategy

By iterating through epochs and diagonal updates, the algorithm ensures that every potential causal link is revisited under the context of the currently estimated graph. This iterative refinement allows the model to escape local minima that often trap naive greedy search algorithms.

Analytical Closed-Form Solution

Fixing all other entries, the optimal update $\delta^*$ is computed analytically: where $c = S_{ii}$, $b = (SA)_{ij}$, and $\alpha = (A^{-1})_{ji}$. This ensures each step is computationally exact and numerically stable, avoiding the need for expensive line-search or inner-loop iterations.

Index	CD (Ours)	CD_L0 (Ours)	GOLEM_EV	GOLEM_NV
1	0.79	0.78	0.60	0.50
2	0.81	0.64	0.56	0.57
3	1.00	0.88	1.00	1.00
4	0.74	0.38	0.02	0.20
5	0.61	0.45	0.01	0.03
6	0.84	0.84	0.35	0.23
7	0.52	0.36	0.00	0.00
8	0.81	0.56	0.06	0.00
9	0.60	0.68	0.08	0.00

The CD method shows superior performance in recovering true causal links, particularly in high-sparsity scenarios where GOLEM struggles with soft acyclicity penalties.

The proposed method can be applied to various domains requiring causal structure discovery from observational data, including economics, biology, and social sciences.