Search for: All records

In constraint-based causal discovery, the existing algorithms systematically use a series of conditional independence (CI) relations observed in the data to recover an equivalence class of causal graphs in the large sample limit. One limitation of these algorithms is that CI tests lose statistical power as conditioning set size increases with finite samples. Recent research proposes to limit the conditioning set size for robust causal discovery. However, the existing algorithms require exhaustive testing of all CI relations with conditioning set sizes up to a certain integer k. This becomes problematic in practice when variables with large support are present, as it makes CI tests less reliable due to near-deterministic relationships, thereby violating the faithfulness assumption. To address this issue, we propose a causal discovery algorithm that only uses CI tests where the conditioning sets are restricted to a given set of conditioning sets including the empty set C. We call such set of CI relations IC conditionally closed. We define the notion of C-Markov equivalence: two causal graphs are C-Markov equivalent if they entail the same set of CI constraints from IC. We propose a graphical representation of C-Markov equivalence and characterize such equivalence between two causal graphs. Our proposed algorithm called the C-PC algorithm is sound for learning the C-Markov equivalence class. We demonstrate the utility of the proposed algorithm via synthetic and real-world experiments in scenarios where variables with large support or high correlation are present in the data. Our source code is available online at github.com/kenneth-lee-ch/cpc. 

Existing causal models for link prediction assume an underlying set of inherent node factors—an innate characteristic defined at the node’s birth—that governs the causal evolution of links in the graph. In some causal tasks, however, link formation ispath-dependent: the outcome of link interventions depends on existing links. Unfortunately, these existing causal methods are not designed for path-dependent link formation, as the cascading functional dependencies between links (arising frompath dependence) are either unidentifiable or require an impractical number of control variables. To overcome this, we develop the first causal model capable of dealing with path dependencies in link prediction. In this work, we introduce the concept of causal lifting, an invariance in causal models of independent interest that, on graphs, allows the identification of causal link prediction queries using limited interventional data. Further, we show how structural pairwise embeddings exhibit lower bias and correctly represent the task’s causal structure, as opposed to existing node embeddings, e.g. graph neural network node embeddings and matrix factorization. Finally, we validate our theoretical findings on three scenarios for causal link prediction tasks: knowledge base completion, covariance matrix estimation and consumer-product recommendations.