Learning high-dimensional Gaussian linear structural equation models with heterogeneous error variances

Abstract

A new approach is presented for learning high-dimensional Gaussian linear structural equation models from only observational data when unknown error variances are heterogeneous. The proposed method consists of three steps: inferring (1) the moralized graph using the inverse covariance matrix, (2) the ordering using conditional variances, and (3) the directed edges using conditional independence relationships. These three problems can be efficiently addressed using inversion of parts of the covariance matrix. It is proved that a sample size of n = Omega(d(m)(2) logp) is sufficient for the proposed algorithm to recover the true directed graph, where p is the number of nodes and d m is the maximum degree. It is also shown that the proposed algorithm requires O(p(3)+ pd(m)(4)) operations in the worst-case, and hence, it is computationally feasible for recovering large-scale graphs. It is verified through simulations that the proposed algorithm is statistically consistent and computationally feasible in high-dimensional and large-scale graph settings, and performs well compared to the state-of-the-art structural learning algorithms. It is also demonstrated through protein signaling data that our algorithm is well-suited to the estimation of directed acyclic graphical models for multivariate data in comparison to other methods used for normally distributed data. (C) 2020 Elsevier B.V. All rights reserved.