BUILD with Precision: Bottom-Up Inference of Linear DAGs

Technical Summary: BUILD (Bottom-Up Inference of Linear DAGs)

Problem Statement
The paper addresses the fundamental problem of learning the structure of Directed Acyclic Graphs (DAGs) from observational data. Specifically, it focuses on the setting of linear Structural Equation Models (SEMs) where the observed variables follow a joint Gaussian distribution with known, equal noise variances. In this specific regime, the underlying DAG is theoretically identifiable from observational data alone. The challenge lies in developing computational methods that can recover the DAG structure (adjacency matrix $A$) efficiently and robustly, particularly when dealing with finite sample sizes and the potential ill-conditioning of the data covariance matrix.

Methodology
The authors propose BUILD (Bottom-Up Inference of Linear DAGs), a deterministic, stepwise algorithm that reconstructs the DAG by iteratively identifying and pruning leaf nodes. The methodology is grounded in the structural properties of the ensemble precision matrix ($\Theta = \Sigma^{-1}$) of the observations.

1. Theoretical Foundation:

   • For a linear Gaussian SEM $x = Ax + z$ with equal noise variance $\sigma^2$, the precision matrix is given by $\Theta = \sigma^{-2}(I - A - A^\top + A^\top A)$.
   • Leaf Identification: The authors establish that a node $i$ is a leaf (has no children) if and only if the corresponding diagonal entry of the precision matrix satisfies $\Theta_{ii} = \sigma^{-2}$. Non-leaf nodes strictly satisfy $\Theta_{jj} > \sigma^{-2}$.
   • Parent Recovery: Once a leaf node $i$ is identified, its parents and the associated edge weights can be recovered directly from the off-diagonal entries of the $i$-th row of $\Theta$. Specifically, $A_{ij} = -\sigma^2 \Theta_{ij}$ for $j < i$ (assuming a topological ordering), and $A_{ij} = 0$ otherwise.

2. Algorithmic Process:

   • Initialization: The algorithm begins by estimating the precision matrix $\hat{\Theta}$ from the data matrix $X$. Due to the potential for ill-conditioning in high-dimensional linear SEMs (where noise accumulates along dependency chains), the authors employ GreedyPrune for this initial estimation, as it performs better than standard methods like Graphical Lasso in these settings.
   • Iterative Pruning: The algorithm maintains a set of active nodes. In each step, it identifies the node with the smallest diagonal entry in the current precision matrix (above a tolerance $\epsilon$) as a leaf. It recovers the edges connecting this leaf to its parents, adds them to the adjacency matrix, and then "prunes" the leaf.
   • Matrix Update: Pruning is performed by updating the precision matrix of the remaining nodes using a block matrix inversion identity (Schur complement), effectively removing the influence of the identified leaf.

3. Error Mitigation Strategy:

   • A critical challenge in practice is that finite-sample estimation errors in $\hat{\Theta}$ can accumulate as the algorithm proceeds, leading to a "snowball effect" of incorrect edge detections.
   • To mitigate this, BUILD incorporates a refreshing scheme. At fixed intervals (defined by a refresh rate $\rho$), the algorithm re-estimates the precision matrix using only the currently active (unpruned) nodes and the original data. This resets accumulated errors and recalibrates the model, trading off runtime for enhanced robustness.

Key Contributions

• Deterministic Bottom-Up Approach: Unlike continuous optimization methods (e.g., NOTEARS, DAGMA) that solve non-convex problems or order-based methods that neglect edge weights, BUILD offers a deterministic, stepwise reconstruction of the DAG and its edge weights.
• Precision Matrix Characterization: The paper provides a specific characterization of the precision matrix entries for linear Gaussian SEMs with equal variances, revealing a distinct structure that allows for exact leaf identification and parent recovery.
• Robustness via Re-estimation: The introduction of the periodic re-estimation mechanism addresses the issue of error propagation in ill-conditioned problems, offering a tunable trade-off between computational cost and accuracy.
• Complexity: In the idealized setting with the true precision matrix, the algorithm runs in $O(N^2)$ time.

Results
The authors evaluate BUILD on synthetic benchmarks involving Erdős–Rényi DAGs with $N=200$ nodes and $M=1,000$ samples.

• Comparison with Optimization Methods: BUILD variants (with different refresh rates) generally outperform state-of-the-art continuous optimization methods (CoLiDE, DAGMA) in terms of Structural Hamming Distance (SHD) and True Positive Rate (TPR). For instance, a variant with frequent refreshing (BUILD-0.005) achieves significantly lower SHD and False Discovery Rate (FDR) than CoLiDE and DAGMA, albeit with higher runtime.
• Comparison with Order-Based Methods: When compared to order-based methods (Gao et al., Daskalakis et al.), BUILD matches the accuracy of the most accurate order-based method (Gao et al.) while maintaining better scalability. Unlike Daskalakis et al., which struggles with general edge weights, BUILD handles the full range of weights effectively.
• Edge Weight Estimation: BUILD demonstrates superior performance in estimating edge weights (measured by Normalized MSE) compared to baselines, particularly as sample size increases.
• Trade-offs: The results highlight a clear trade-off: higher refresh rates lead to lower error rates (better SHD and FDR) but increase computational time.

Significance and Claims
The paper claims that BUILD offers a viable alternative to existing DAG learning algorithms by leveraging the specific identifiability properties of linear Gaussian SEMs with equal noise variances. Its significance lies in:

1. Explicit Complexity Control: It provides an explicit handle on complexity through the refresh rate parameter, allowing users to balance accuracy and runtime.
2. Handling Ill-Conditioning: By integrating a robust precision matrix estimator (GreedyPrune) and a re-estimation strategy, it addresses the numerical instability often found in DAG learning with long dependency chains.
3. Reproducibility: The authors emphasize the deterministic nature of the algorithm and the availability of their implementation, contrasting it with methods that may face optimization convergence issues.

The authors modestly acknowledge limitations, noting that the algorithm's performance is sensitive to the accuracy of the initial precision matrix estimate and that the refreshing mechanism, while robust, introduces inefficiency by discarding previously computed matrix entries. They suggest future work in adaptive refresh scheduling and extending the approach to non-Gaussian or nonlinear settings.