Skip to contentSkip to filters

We use cookies for analytics.

Anytime-anywhere FCI+ : a true ‘anytime’ algorithm for causal discovery with high-density regions

Tom Claassen

Radboud University

Abstract

Constraint-based causal discovery methods such as FCI can in principle handle unobserved confounders but implicitly rely on sparse networks to finish in reasonable time, whereas many real systems are dense: protein-protein interaction networks contain hub proteins central to many cellular processes, and power grids and social networks show small-world clustering, so even basic algorithms such as PC can stall in high-density regions without producing useful output. Anytime-FCI (Spirtes, 2001) and more recent alternatives such as ICD (Rohekar et al., 2021) can still take a long time to finish. Tom Claassen presents a new search strategy for graphs with high-density regions that builds the causal graph on the fly, updating the model after each validated edge removal while remaining sound throughout; it uses the intermediate causal model to reduce the size and number of conditional independence tests and prioritizes easy edges, leaving difficult dense regions until last. The resulting anytime-anywhere FCI+ is a true anytime algorithm that is faster and more flexible than its traditional counterparts, handles arbitrary edge removals and opens possibilities such as targeted cause-effect recovery in large graphs.

Topics