An Algorithm for Fast Recovery of Sparse Causal Graphs

TLDR

Previous asymptotically correct algorithms for recovering causal structure from sample probabilities have been limited even in sparse causal graphs to a few variables. The authors aim to present an asymptotically correct algorithm for recovering sparse causal graphs with polynomial complexity in the number of vertices. The algorithm’s complexity for fixed graph connectivity increases polynomially with the number of vertices, enabling practical recovery of sparse graphs with several hundred variables. On sample data with n = 20,000, the algorithm recovers the edges of a linear ALARM network (37 vertices, 46 edges) in under 10 seconds, misidentifying fewer than 8 % of undirected edges and incorrectly orienting only 14 % of edges without prior ordering information. Keywords: DAGS, Causal Modelling.

Abstract

Previous asymptotically correct algorithms for recovering causal structure from sample probabilities have been limited even in sparse causal graphs to a few variables. We describe an asymptotically correct algorithm whose complexity for fixed graph connectivity increases polynomially in the number of vertices, and may in practice recover sparse graphs with several hundred variables. From sample data with n = 20,000, an implementation of the algorithm on a DECStation 3100 recovers the edges in a linear version of the ALARM network with 37 vertices and 46 edges. Fewer than 8% of the undirected edges are incorrectly identified in the output. Without prior ordering information, the program also determines the direction of edges for the ALARM graph with an error rate of 14%. Processing time is less than 10 seconds. Keywords DAGS, Causal Modelling.