제약 기반 인과 관계 추론에서의 조건부 독립성 검정 횟수에 대한 연구

On the Number of Conditional Independence Tests in Constraint-based Causal Discovery

관찰 데이터로부터 인과 관계를 학습하는 것은 다양한 분야에서 광범위하게 활용되는 기본적인 문제입니다. 제약 기반 방법은 조건부 독립성 검정을 수행하여 잠재적인 인과 구조를 추론합니다. 그러나 PC 알고리즘과 같은 기존 알고리즘은 최대 인과 그래프의 최대 차수와 관련된 지수적인 수의 독립성 검정을 수행해야 합니다. 많은 연구에도 불구하고, 추가적인 가정을 하지 않고 더 나은 복잡도를 가진 알고리즘이 존재하는지 여부는 여전히 불분명합니다. 본 연구에서는 그래프 내 노드 수 $p$와 기본 필수 그래프의 최대 비방향 클리크 크기 $s$에 대해 $p^{ ext{Ω}(s)}$ 번의 검정을 수행하는 알고리즘을 제시합니다. 이 결과와 함께, 모든 제약 기반 알고리즘은 최소 $2^{ ext{Ω}(s)}$ 번의 조건부 독립성 검정을 수행해야 함을 증명하여, 제안된 알고리즘이 필요한 조건부 독립성 검정 횟수에 대해 지수 최적성을 달성함을 보여줍니다 (로그 스케일까지). 마지막으로, 시뮬레이션, 준-합성 유전자 발현 데이터, 그리고 실제 데이터에 대한 실험을 통해, 제안된 알고리즘이 기존 방법보다 필요한 조건부 독립성 검정 횟수 측면에서 효율성이 높다는 것을 확인했습니다.

Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph. Despite extensive research, it remains unclear if there exist algorithms with better complexity without additional assumptions. Here, we establish an algorithm that achieves a better complexity of $p^{\mathcal{O}(s)}$ tests, where $p$ is the number of nodes in the graph and $s$ denotes the maximum undirected clique size of the underlying essential graph. Complementing this result, we prove that any constraint-based algorithm must perform at least $2^{Ω(s)}$ conditional independence tests, establishing that our proposed algorithm achieves exponent-optimality up to a logarithmic factor in terms of the number of conditional independence tests needed. Finally, we validate our theoretical findings through simulations, on semi-synthetic gene-expression data, and real-world data, demonstrating the efficiency of our algorithm compared to existing methods in terms of number of conditional independence tests needed.