Estimate Collapsibility of Causal Effects in Completed Partial DAGs via Strong d-Convex Hulls

기술 요약: 강한 d-볼록 껍질(Strong d-Convex Hulls)을 통한 완성된 부분 방향성 비순환 그래프(CPDAG)에서의 인과 효과 붕괴 가능성 추정

문제 정의
관측 데이터로부터의 인과 효과 추정은 일반적으로 인과 그래프 모델에 의존한다. 백도어 기준(back-door criterion)과 do-calculus는 방향성 비순환 그래프(DAG)에서 정밀한 추정을 가능하게 하지만, 데이터로부터의 인과 발견(causal discovery)은 종종 마르코프 동등 클래스(Markov equivalence class)의 DAG를 나타내는 완성된 부분 방향성 비순환 그래프(CPDAG)만을 산출한다. CPDAG에서의 인과 효과 추정(예: IDA 알고리즘)은 가능한 모든 부모 집합 또는 유효한 조정 집합을 열거하는 과정을 필요로 한다. 이 과정은 고차원 설정에서 계산적으로 매우 부담이 된다. 더욱이, 조정 집합을 축소하는 기존 방법들은 국소적 가지치기(local pruning)나 추가적인 사전 지식에 의존하여, 제거되어야 할 불필요한 변수들을 그래프에 남겨두는 경우가 많다. 핵심적인 과제는 변수를 무시(marginalization)한 후에도 인과 효과 추정치를 보존하는 최소 변수 집합을 식별하는 것인데, 이는 '붕괴 가능성(collapsibility)'이라 알려진 성질이다. 붕괴 가능성은 무방향 그래프와 분포적 특성에 대해서는 연구된 바 있으나, CPDAG에서의 인과 효과 추정에 대한 적용은 아직 미개척 분야로 남아 있다.

방법론
본 논문은 새로운 그래프 이론적 개념인 **강한 d-볼록 껍질(Strong d-Convex Hull)**을 통해 CPDAG에서 최소 붕괴 집합(minimal collapsible sets)을 식별하는 프레임워크를 제안한다.

1. CBN에서의 붕괴 가능성 추정: 저자들은 인과 베이지안 네트워크(CBN)를 위한 *추정 붕괴 가능성(estimate collapsibility)*을 정의한다. 집합 $R$이 추정 붕괴 가능하다는 것은 $R$에 대한 주변 분포의 최대 우도 추정치(MLE)가 전체 그래프에서 계산되든 유도된 부분 그래프(induced subgraph)에서 계산되든 일관되게 유지됨을 의미한다.
2. 강한 d-볼록 껍질: 최소 붕괴 집합을 특징짓기 위해, 본 논문은 강한 d-볼록 껍질이라는 새로운 개념을 도입한다. 집합 $R$이 강하게 d-볼록하다는 것은 다음을 만족함을 의미한다:
   • 유도된 부분 그래프 내에 $R$을 위한 유도 경로(inducing paths)가 존재하지 않는다.
   • $R$의 여집합(complement)의 자식 노드 중 $R$의 조상인 노드들의 집합이 $R$에 대해 선형 순서(linearly ordered)를 가진다.
     본 논문은 (정리 1)을 통해, 어떤 집합이 최소 붕괴 집합인 것은 대상 변수의 강한 d-볼록 껍질인 것과 필요충분조건임을 증명한다.
3. 알고리즘 (ISCHA): 저자들은 **강한 d-볼록 껍질 식별 알고리즘(ISCHA)**을 개발하였다. 이 알고리즘은 두 단계로 작동한다:
   • 먼저, 대상 집합 내의 비인접 노드 사이의 최단 유도 경로 상에 있는 정점들을 반복적으로 흡수하여 d-볼록 껍질을 계산한다.
   • 그 다음, 순서 제약을 위반하는 노드의 부모들을 흡수함으로써 선형 순서 조건을 강제한다.
     ISCHA 알고리즘은 다항 시간($O(k^2 \times |V|^4)$, 여기서 $k$는 대상 집합 크기, $|V|$는 전체 변수 수) 내에 실행된다.
4. CPDAG를 위한 IDA 통합: 이 방법은 강한 d-볼록 껍질이 마르코프 동등 클래스의 모든 DAG에서 불변이라는 사실(정리 5)을 활용하여 CPDAG로 확장된다. 제안된 Subgraph IDA 알고리즘은 다음과 같다:
   • CPDAG의 동등 클래스에서 임의의 DAG를 선택한다.
   • 처치(treatment) 및 결과(outcome) 변수에 대한 강한 d-볼록 껍질을 계산한다.
   • 이 축소된 국소 부분 그래프에서 인과 효과 추정(백도어 조정을 사용)을 수행한다.
     이는 DAG의 열거 공간과 추정에 필요한 조정 집합의 크기를 줄여준다.

주요 기여

• 이론적 특징 규명: 본 논문은 CPDAG에서의 인과 효과 추정을 위한 붕괴 가능성의 개념을 도입하고, 최소 붕괴 집합이 정확히 강한 d-볼록 껍질에 대응함을 입증한다.
• 알고리즘 혁신: 효율적으로 DAG에서 최소 집합을 식별하는 ISCHA 알고리즘을 제안하고, 이를 CPDAG로 일반화한다.
• 인과 추정의 효율성: 그래프 축소를 IDA 프레임워크와 결합함으로써, 추정 정확도를 희생하지 않으면서도 DAG 열거 및 조정 집합의 계산 부담을 크게 줄인다.

실험 결과
저자들은 수치 시뮬레이션과 실제 베이지안 네트워크(예: Hailfinder, Pathfinder, Munin1) 및 합성 랜덤 그래프에 대한 경험적 분석을 통해 방법을 평가하였다.

• 확률적 추론: 국소 부분 그래프 접근 방식은 전체 그래프의 확률 분포를 무시할 만한 수준의 쿨백-라이블러 발산(Kullback-Leibler divergence, $10^{-17}$에서 $10^{-18}$ 차수)으로 보존하였다. 또한 상당한 노드 감소 비율(최대 96%)과 쿼리 시간의 유의미한 가속을 달달성하였다.
• 인과 효과 추정: Subgraph IDA와 표준 IDA를 비교한 결과:
  • 정확도: 다양한 네트워크 크기(20~100 노드)와 밀도에 걸쳐 완벽하거나 거의 완벽한 재현율(Recall)과 정밀도(Precision)(흔히 1.0)를 보였다. 인과 효과 추정치는 전체 그래프 방식과 동일했다.
  • 효율성: 방법론은 일관된 가속 계수를 보여주었으며, 작은 네트워크에서는 약 1.1배에서 큰 네트워크(예: Munin1)에서는 30배 이상의 가속을 기록했다. 가속도는 네트워크 크기와 밀도가 커질수록 증가했다.

의의 및 주장
본 논문은 자신의 방법이 고차원 CPDAG에서 인과 효과 추정을 위한 엄격하고 효율적인 솔루션을 제공한다고 주장한다. 강한 d-볼록 껍질로 정의된 국소 부분 그래프로 문제를 축소함으로써, 이 접근 방식은 주변화 전후의 추정치 일관성을 유지한다. 이를 통해 연구자들은 계산 비용과 모델 복잡성을 크게 낮추면서도 정확한 인과 추론을 수행할 수 있다. 저자들은 이 방법이 비인접 처치-결과 쌍에 특히 효과적이며, 현재는 완전 관측된 데이터를 가정하고 있다는 점을 언급하며, 잠재 변수가 있는 그래프로의 확장을 향후 연구 과제로 남겨두었다.