Abstract
Enumerating the directed acyclic graphs (DAGs) of a Markov equivalence class (MEC) is an important primitive in causal analysis. The central resource from the perspective of computational complexity is the delay, that is, the time an algorithm that lists all members of the class requires between two consecutive outputs. Commonly used algorithms for this task utilize the rules proposed by Meek (1995) or the transformational characterization by Chickering (1995), both resulting in superlinear delay. In this paper, we present the first linear-time delay algorithm. On the theoretical side, we show that our algorithm can be generalized to enumerate DAGs represented by models that incorporate background knowledge, such as MPDAGs; on the practical side, we provide an efficient implementation and evaluate it in a series of experiments. Complementary to the linear-time delay algorithm, we also provide intriguing insights into Markov equivalence itself: All members of an MEC can be enumerated such that two successive DAGs have structural Hamming distance at most three.
Abstract (translated)
枚举一个 Markov 等价类(MEC)中的有向无环图(DAGs)是因果分析中的一个重要基本操作。从计算复杂性的角度来看,关键资源是延迟,也就是列出该类所有成员所需的算法前后两个输出之间的时间。通常用于该任务的算法利用了 Meek (1995) 提出的规则或 Chickering (1995) 的转化特征,都导致了超级延迟。在本文中,我们介绍了第一个线性时间延迟算法。在理论方面,我们表明,我们的算法可以推广到包括背景知识模型的代表的 DAGs 的枚举,例如 MPDAGs。在实践方面,我们提供了高效的实现,并通过一系列实验评估了它。与线性时间延迟算法相辅相成,我们还提供了对 Markov 等价类的令人感兴趣的洞察力:所有 MEC 成员可以枚举,使得两个后续的 DAGs 的结构哈希距离不超过三个。
URL
https://arxiv.org/abs/2301.12212
