A causal discovery algorithm using multiple regressions

Abstract

The purpose of a constraint-based causal discovery algorithm (CDA) is to find a directed acyclic graph which is observationally equivalent to the non-interventional data. Limiting the data to follow multivariate Gaussian distribution, existing such algorithms perform conditional independence (Cl) tests to compute the graph structure by comparing pairs of nodes independently. In this paper, however, we propose Multiple Search algorithm which performs Cl tests on multiple pairs of nodes simultaneously. Furthermore, compared to existing CDAs, the proposed algorithm searches a smaller number of conditioning sets because it continuously removes irrelevant nodes, and generates more-reliable solutions by double-checking the graph structures. We show the effectiveness of the proposed algorithm by comparison with Grow-Shrink and Collider Set algorithms through numerical experiments based on six networks. (C) 2010 Elsevier B.V. All rights reserved.