PACER: Acyclic Causal Discovery from Large-scale Interventional Data

Motivation

• Known: observational data만으로는 causal graph가 Markov equivalence class까지만 식별되지만, interventional data를 활용하면 식별성이 향상된다는 것이 알려져 있다. NOTEARS 이후 등장한 differentiable causal discovery 방법들(DCDI, DCDFG, ENCO 등)은 augmented Lagrangian penalty 기반 soft acyclicity constraint를 통해 연속 최적화 문제로 DAG 탐색을 재구성해왔다.
• Gap: 기존 differentiable 방법들은 acyclicity를 penalty term으로만 강제하기 때문에 최적화 과정에서 well-defined joint likelihood가 없는 cyclic graph를 평가·최적화하게 되며, 변수 수가 늘어날수록 수치적 불안정성과 과도한 runtime이 발생해 확장성이 제한된다. 또한 permutation 기반 고전적 방법들은 acyclicity를 보장하지만 O(n!) 수준의 조합 탐색 비용과 단일 그래프만 반환하는 한계, DP-DAG/BCD Nets 등 순서 분포 학습 방법들은 O(n^3) 연산으로 확장성이 제한되고 주로 observational data에만 초점을 맞춘다.
• Why: 고차원 perturbation 데이터(예: Perturb-seq)로부터 수천 개 변수 규모의 유전자 조절 네트워크를 정확하고 안정적으로 복원하는 것은 유전체학 등 실제 응용에서 중요한 문제이며, exact하고 scalable한 acyclic causal discovery가 가능함을 보이는 것은 방법론적으로나 실용적으로나 의미가 크다.
• Approach: PACER는 Plackett–Luce 파라미터화를 이용한 topological ordering 분포와 edge 확률 모델을 결합하여 DAG에 대한 분포를 정의하고, 이 분포 위에서 observational/interventional likelihood를 직접 최적화함으로써 acyclicity를 구조적으로(by construction) 보장한다.

Achievement

1. Acyclicity by design: 위상 정렬(topological ordering)과 edge filtering을 결합한 DAG 분포를 도입해, 최적화 과정에서 평가되는 모든 구조가 항상 acyclic하도록 보장하여 별도의 acyclicity penalty term이 필요 없다.
2. 유연한 differentiable 프레임워크: observational 및 interventional data를 함께 다루는 통합 likelihood 기반 목적함수를 제공하며, neural parameterization을 포함한 다양한 conditional density model을 지원한다.
3. Exact gradient 계산: linear-Gaussian mechanism 하에서 interventional log-likelihood의 closed-form expression을 유도하여, penalty 기반 differentiable 방법 대비 최대 두 자릿수(two orders of magnitude) 속도 향상을 달성했다.
4. 구조적 사전지식 통합: node centrality 기대값이나 transcription factor binding constraint 같은 structural prior를 직접 통합할 수 있는 유연성을 갖춘다.
5. 벤치마크 성능: protein signaling network 및 대규모 genetic perturbation benchmark에서 SID, 음의 log-likelihood, Kendall τ 등 지표에서 state-of-the-art 방법들과 동등하거나 이를 상회하는 성능을 보였으며 수천 개 변수까지 효율적으로 확장된다.

How

• Plackett–Luce 분포를 이용해 변수들의 topological ordering에 대한 확률 분포를 파라미터화하고, 이와 결합된 edge probability 모델로 DAG 전체에 대한 결합 분포를 정의한다.
• observational/interventional 데이터에 대해 개입되지 않은 변수들의 조건부 log-likelihood를 결합한 score function을 정의하고, DCDI/DCDFG 방식과 달리 acyclicity penalty 없이 이 score를 직접 최적화한다.
• linear-Gaussian mechanism 가정 하에서 기대 interventional log-likelihood와 그 gradient에 대한 closed-form 수식을 유도해 계산 비용을 크게 줄인다.
• node centrality, transcription factor binding 등 structural prior knowledge를 모델에 직접 반영할 수 있는 메커니즘을 설계한다.
• protein signaling 데이터셋과 Perturb-CITE-seq 등 대규모 genetic perturbation 벤치마크에서 SID, runtime scaling, negative log-likelihood, Kendall τ 지표로 평가한다.

Originality

• soft acyclicity penalty 없이 permutation과 edge probability의 결합 분포만으로 acyclicity를 구조적으로 보장하는 새로운 파라미터화 방식을 제시했다.
• 기존 permutation 기반 방법(SP, CAM 등)의 O(n!) 조합 탐색과 DP-DAG/BCD Nets류의 O(n^3) 연산 한계를 모두 극복하며 quadratic complexity로 stochastic optimization을 가능케 했다.
• linear-Gaussian mechanism에 대한 interventional log-likelihood의 closed-form gradient 유도는 기존에 numerical instability를 유발하던 acyclicity constraint의 gradient 계산 문제를 근본적으로 우회한다.
• observational/interventional data를 단일 likelihood 기반 objective로 통합하면서도 structural prior knowledge까지 반영 가능한 프레임워크로 통합했다는 점이 독창적이다.

Limitation & Further Study

• closed-form gradient는 linear-Gaussian mechanism에 한정되어 있어, 비선형(non-linear) 또는 비가우시안(non-Gaussian) mechanism에 대해서는 여전히 근사적/수치적 방법에 의존해야 할 가능성이 있다.
• Plackett–Luce 기반 permutation 분포가 실제로 얼마나 다양한 구조적 불확실성(structural variability)을 포착할 수 있는지, 매우 큰 n(수만 이상)에서의 이론적 수렴 보장이 충분히 논의되지 않았을 수 있다.
• 실제 생물학적 네트워크에서 ground-truth DAG가 불확실한 경우가 많아, SID나 Kendall τ 같은 평가 지표가 실제 인과 구조 발견 성능을 완전히 반영하는지에 대한 추가 검증이 필요하다.
• 후속 연구로는 비선형 mechanism에 대한 효율적 closed-form 또는 근사 gradient 확장, 그리고 더 다양한 실제 도메인(예: 신경과학, 사회과학 데이터)에서의 검증이 기대된다.

Evaluation

총평: Acyclicity를 penalty가 아닌 구조적 설계로 보장하면서도 interventional likelihood의 closed-form gradient를 통해 대규모 causal discovery의 확장성과 정확성을 동시에 달성한 견실하고 실용적인 기여로 평가된다.