Source-linked AI summary
Penalized Likelihood Methods for Estimation of Sparse High Dimensional Directed Acyclic Graphs
Ali Shojaie, George Michailidis
TL;DR
Estimating DAGs is difficult because observational data may not identify causal directions, while natural ordering can reduce the task to structure estimation. The paper proposes penalized likelihood estimation of adjacency matrices using lasso and adaptive lasso, with an efficient algorithm for high-dimensional settings. Adaptive lasso is consistent under usual regularity assumptions, whereas lasso requires more stringent conditions, and empirical studies compare the methods with alternatives.
Problem
Observational equivalence can prevent causal directions from being inferred from observational data, complicating DAG estimation.
Method
The paper reformulates likelihood using the adjacency matrix and estimates ordered high-dimensional DAGs with lasso and adaptive lasso penalties.
Results
Adaptive lasso consistently estimates the true DAG under usual regularity assumptions, whereas lasso requires stringent conditions.
Takeaways & Limitations
The proposed methods are intended for sparse DAG applications with known ordering and may also be efficient alternatives when ordering is unknown.
Takeaways & Limitations
Adaptive-lasso consistency requires stronger network sparsity, with assumption (A-0′) imposing restrictions that imply b < 1/2.
Abstract
from arXiv · showhide
Directed acyclic graphs (DAGs) are commonly used to represent causal relationships among random variables in graphical models. Applications of these models arise in the study of physical, as well as biological systems, where directed edges between nodes represent the influence of components of the system on each other. The general problem of estimating DAGs from observed data is computationally NP-hard, Moreover two directed graphs may be observationally equivalent. When the nodes exhibit a natural ordering, the problem of estimating directed graphs reduces to the problem of estimating the structure of the network. In this paper, we propose a penalized likelihood approach that directly estimates the adjacency matrix of DAGs. Both lasso and adaptive lasso penalties are considered and an efficient algorithm is proposed for estimation of high dimensional DAGs. We study variable selection consistency of the two penalties when the number of variables grows to infinity with the sample size. We show that although lasso can only consistently estimate the true network under stringent assumptions, adaptive lasso achieves this task under mild regularity conditions. The performance of the proposed methods is compared to alternative methods in simulated, as well as real, data examples.
1 Introduction
DAGs represent causal relationships among variables, but estimating their structure is challenging because observational data can leave causal directions unresolved. With a natural variable ordering, the paper develops penalized likelihood methods for sparse high-dimensional DAG estimation.
- Motivation: DAGs use directed edges to represent causal relationships among random variables in graphical models.They are applied to physical and biological systems, including cellular networks.
- Motivation: Estimating high-dimensional DAGs becomes structure estimation when variables have a natural ordering.Examples include temporal observations, experimentally ordered variables, and transcriptional regulatory networks.
- Related work: Conditional independence relations provide a basis for determining graph structure, with sparse penalization methods established for related inverse covariance estimation.Prior work includes lasso-based and other penalized approaches for estimating sparse concentration matrices.
- Contribution: The paper directly estimates DAG adjacency matrices using lasso and adaptive lasso penalized likelihoods with an efficient high-dimensional algorithm.It studies variable-selection consistency as p grows much faster than n.
2 Representation of Directed Acyclic Graphs
The paper represents DAG structure with an adjacency matrix and uses latent-variable structural equations to connect graph edges, influence matrices, and covariance structure. Observational equivalence motivates focusing on DAG skeletons and their equivalence classes.
- Graph representation: A DAG contains only directed edges and no directed cycles, and its skeleton replaces directed edges with undirected ones.The adjacency matrix A records whether an edge, and possibly its weight, connects nodes j and i.
- Graph representation: Observationally equivalent DAGs can generate the same probability distribution, so observational data may not identify causal edge directions.The paper therefore motivates estimating the equivalence class beginning with the network skeleton.
- Latent variable model: Structural equation models express each variable as a function of its parents and an independent latent variable representing unexplained variation.The paper specializes the general nonlinear form to linear effects for modeling DAG associations.
- Latent variable model: For DAGs, the influence matrix is linked compactly to the adjacency matrix through powers of A, enabling direct likelihood formulation in terms of graph structure.The paper states Λ = (I − A)^−1 for DAGs and uses this relationship in estimation.
- Latent variable model: When latent-variable variances are positive, the covariance matrix and its inverse are full rank for a DAG and all its subnetworks.This follows from the full rank of the influence matrix Λ.
- Latent variable model: The latent-variable model's stated properties do not depend on the probability distribution because independent latent variables make each node depend only on its parents.The paper later illustrates this distributional compatibility using non-Gaussian data.
3 Penalized Estimation of DAGs
With a known variable ordering, DAG estimation is reformulated into penalized regression problems over a lower-triangular adjacency matrix. The resulting procedure has separable subproblems, efficient algorithms, and computational cost O(np^2).
- Problem formulation: The known ordering constrains the adjacency matrix to be lower triangular with zero diagonal, enabling direct estimation of DAG structure.The formulation uses the determinant and variance conditions to estimate the adjacency matrix under this structural constraint.
- Penalized estimation: Lasso and adaptive lasso are represented through a weighted ℓ1 penalty, with adaptive weights derived from an initial lasso estimate.For ordinary lasso, all weights equal one; adaptive lasso uses weights based on preliminary adjacency estimates.
- Computational complexity: Interior-point algorithms solve the quadratic formulation but do not scale well with dimension and are described as applicable only when p is in the hundreds.The alternative formulation in section 3.2 is introduced to obtain considerably more efficient algorithms.
- Optimization algorithm: The objective separates by adjacency-matrix row, reducing estimation to p −1 non-overlapping ℓ1-regularized least-squares problems.Each row contains coefficients for projecting X_i on preceding variables, corresponding to parent candidates under the ordering.
- Optimization algorithm: The proposed algorithm solves the rowwise lasso problems with pathwise coordinate optimization, using problem dimensions from 1 to p −1.The implementation uses the glmnet package and applies the same computational strategy to adaptive lasso.
- Computational complexity: O(np^2) is the total computational cost for estimating the adjacency matrix, matching the cost of computing the full empirical covariance matrix.Because the subproblems do not overlap, estimation can be parallelized for very large graphs or datasets.
4 Asymptotic Properties
The section establishes asymptotic properties for lasso and adaptive lasso estimation of sparse DAG structures in high dimensions. Adaptive lasso attains consistency under fewer structural assumptions, but requires a stronger sparsity restriction.
- Asymptotic framework: The proposed DAG estimator reduces adjacency-matrix estimation to p−1 non-overlapping penalized least-squares problems.The analysis allows the number of nodes to grow polynomially with sample size while assuming the true network is sparse.
- Lasso consistency: Lasso estimates are consistent when n−1(s + 1) log p = o(1).This result is used to formulate the assumptions for adaptive-lasso analysis.
- Adaptive-lasso consistency: The adaptive-lasso result requires stronger sparsity: condition s n2b−1 log n = o(1) implies b < 1/2.Assumption (A-0′) restricts both each node’s parent count and the total number of nonzero adjacency-matrix entries.
- Adaptive-lasso consistency: Adaptive lasso achieves variable-selection consistency without assumptions (A-3) and (A-4), provided (A-0′), (A-1), and (A-2) hold.Its initial weights are computed from regular lasso estimates, and the theorem uses λ ≍ d n−(1−ζ)/2 with b < ζ < ξ.
- Tuning parameter: The proposed tuning-parameter rule controls the probability of falsely joining two distinct ancestral sets, but not false-positive or false-negative probabilities for individual edges.Cross-validation may select the initial adaptive-lasso penalty for prediction consistency, while a higher significance level is recommended to avoid an over-sparse initial solution.
5 Performance Analysis
The simulations compare PC-Algorithm, lasso, and adaptive lasso estimators under Gaussian, non-Normal, and ordering-perturbed settings. Adaptive lasso generally performs best, while method advantages depend on network size, sparsity, and ordering information.
- Normally Distributed Observations: With n = 100 and p = 50, 100, 200, adaptive lasso has the lowest Hamming distance across tuning parameters, and penalized methods outperform pcalg increasingly as p grows.These comparisons use mean and standard deviation of Hamming distance.
- Normally Distributed Observations: MCC confirms the SHD comparison, whereas FP and TP alone provide less clear distinctions among pcalg, lasso, and adaptive lasso.The simulations use optimal tuning settings for the methods.
- Non-Normal Observations: For non-Normal observations from mixture and t-distributions, adaptive lasso remains best, while penalized methods improve as dimension and sparsity increase.These simulations use linear structural models.
- Sensitivity to Ordering: With randomly permuted variable orderings, pcalg performs better on small dense networks, but both penalized methods outperform it in high-dimensional sparse cases.The ordering perturbation can create unnecessary moral edges and miss existing associations.
6 Real Data Application
The real-data applications use known biological orderings to estimate human signaling and E-coli transcriptional regulatory networks. Penalized likelihood methods improve on PC-Algorithm results, although the E-coli application is limited by small sample size and incomplete information from one data source.
- Human Cell Signaling: The human signaling dataset contains 11 proteins and 7,466 samples, with pathway ordering established through molecular interventions.The ordering is treated as known a priori.
- Human Cell Signaling: For human signaling data, pcalg produces several undirected edges, while lasso and adaptive lasso are evaluated against the known network.The application compares all three estimation approaches with performance measures.
- E-coli Transcriptional Regulation: The E-coli application uses known transcription factors and expression data for 7 transcription factors and 40 regulated genes.The natural hierarchy of transcription factors and genes supplies the ordering information.
- E-coli Transcriptional Regulation: In the E-coli example, pcalg detects only one true regulatory connection, while lasso and adaptive lasso substantially improve on it.Overall algorithm performance remains relatively poor, partly because the sample size is small.
- E-coli Transcriptional Regulation: The E-coli results also reflect the limitation that no single transcriptomic data source is expected to reveal regulatory networks successfully.Methods combining multiple data sources are described as more efficient.
7 Conclusion
The paper develops efficient penalized likelihood methods for estimating ordered DAG structures and extends the algorithm beyond lasso and adaptive lasso. Potential applications include biological and temporal causal-network reconstruction, while simulations suggest exact ordering is less crucial in high-dimensional sparse settings.
- The proposed algorithm estimates DAG adjacency structures using penalties applied to individual adjacency-matrix elements.The framework includes lasso and adaptive lasso and can accommodate other elementwise penalty functions.
- Potential applications include transcriptional regulatory networks and causal networks reconstructed from temporal observations.The latter application is based on the concept of Granger causality.
- Simulation studies indicate that the correct variable ordering is less crucial for estimating high-dimensional sparse DAGs.This suggests applicability even when the ordering among variables is unknown, within the scope stated by the authors.
Appendix: Technical Proofs
The appendix establishes technical conditions for weighted lasso and adaptive lasso solutions, using KKT characterizations, concentration bounds, Gaussian assumptions, and union bounds. These arguments support uniqueness, exclusion of nonparents, and probability control in the consistency proofs.
- The weighted lasso KKT conditions characterize active coefficients by signed equality and inactive coefficients by weighted subgradient inequalities.The result also gives a condition forcing a coefficient to zero across all solutions when the inequality is strict.
- The appendix transfers restricted-support solutions to unrestricted lasso or adaptive lasso problems under suitable events and establishes almost-sure uniqueness in the stated cases.The arguments invoke Lemma 7.1 and assume card(pai) < n where needed.
- Additional arguments relate ancestor structure and residual-score independence to covariance and selection properties in DAGs.The proofs use lower-triangular influence representations and independence conditional on selected ancestor sets.