An extension to the algebraic equivalence deciding algorithm

Abstract

This thesis investigates how to extend the algebraic equivalence deciding algorithm used in causal discovery to a broader class of models. Algebraic equivalence enables a search-space reduction by avoiding redundant scoring of causal graphs that impose the same algebraic constraints on the covariance matrix.

The original algorithm relies on the Half-Trek Criterion (HTC) for identifiability, which limits its applicability. This work incorporates two more powerful identification techniques, edgewise identification (EID) and trek-separation identification (TSID), to expand the set of graphs for which algebraic equivalence can be tested. The updated algorithm detects and filters spurious components, handles rational expressions arising from EID and TSID and performs algebraic containment tests in both directions.

Theoretical error bounds are derived using the Schwartz–Zippel lemma, and the computational complexity of the extended method is analysed. The algorithm is evaluated on 2,100 generated graphs and on 98 known non-HTC-identifiable graphs. With sufficiently large finite fields, the method achieves perfect predictive accuracy in all experiments, demonstrating that EID and TSID substantially broaden the applicability of algebraic-equivalence testing in causal discovery.