Causal structure learning in directed, possibly cyclic, graphical models

Semnani Pardis () and Robeva Elina ()
Additional contact information
Semnani Pardis: Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada
Robeva Elina: Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada

Journal of Causal Inference, 2025, vol. 13, issue 1, 41

Abstract: We consider the problem of learning a directed graph G ⋆ {G}^{\star } from observational data. We assume that the distribution that gives rise to the samples is Markov and faithful to the graph G ⋆ {G}^{\star } and that there are no unobserved variables. We do not rely on any further assumptions regarding the graph or the distribution of the variables. Particularly, we allow for directed cycles in G ⋆ {G}^{\star } and work in the fully nonparametric setting. Given the set of conditional independence statements satisfied by the distribution, we aim to find a directed graph, which satisfies the same d d -separation statements as G ⋆ {G}^{\star } . We propose a hybrid approach consisting of two steps. We first find a partially ordered partition of the vertices of G ⋆ {G}^{\star } by optimizing a certain score in a greedy fashion. We prove that any optimal partition uniquely characterizes the Markov equivalence class of G ⋆ {G}^{\star } . Given an optimal partition, we propose an algorithm for constructing a graph in the Markov equivalence class of G ⋆ {G}^{\star } whose strongly connected components correspond to the elements of the partition, and which are partially ordered according to the partial order of the partition. Our algorithm comes in two versions – one that is provably correct and another one that performs fast in practice.

Keywords: causal discovery; directed cyclic graphs; Markov equivalence; faithfulness; d-separations; conditional independence (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/jci-2024-0037 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:causin:v:13:y:2025:i:1:p:41:n:1001

DOI: 10.1515/jci-2024-0037

Access Statistics for this article

Journal of Causal Inference is currently edited by Elias Bareinboim, Jin Tian and Iván Díaz

More articles in Journal of Causal Inference from De Gruyter
Bibliographic data for series maintained by Peter Golla ().