A Faster Algorithm for the Half-Trek Criterion in Structural Causal Models

Linear structural causal models (SCMs) are used to analyze relationships among random variables. In these models, directed edges encode direct causal effects, while bidirected edges capture latent confounding. The problem of generically identifying the hidden parameters from observed correlations remains open in causal inference. The half-trek criterion by Foygel, Draisma, and Drton [2012] and its generalization to the edge-wise criterion are important criteria for generic identification in linear SCMs, since the half-trek criterion can be efficiently decided by an algorithm with running time $\mathcal{O}(n^5)$. We here develop a new criterion that is equivalent to the edgewise criterion. Utilizing this criterion, we design a faster randomized algorithm for deciding the half-trek criterion with running time $\mathcal{O}(n^4)$. For sparse graphs, our algorithm even works in $\mathcal{O}(n^3)$. We show that the algorithm is useful in practice by providing an implementation that outperforms the implementation of HTC in the state-of-the art R package SEMID.