2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane

Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.

academic

통계적으로 효율적인 인과 추론을 위한 국소 인과 발견

기본 정보

논문 ID: 2510.14582
제목: Local Causal Discovery for Statistically Efficient Causal Inference
저자: Mátyás Schubert (암스테르담 대학교), Tom Claassen (라드바우드 대학교 니메헌), Sara Magliacane (암스테르담 대학교)
분류: stat.ML cs.AI cs.LG
발표 시간: 2025년 10월 16일 (arXiv 사전 인쇄본)
논문 링크: https://arxiv.org/abs/2510.14582v1

초록

인과 발견 방법은 잠재적 인과 그래프가 미지의 상태에서도 목표 변수 쌍의 인과 효과 추정을 위한 유효한 조정 집합을 식별할 수 있습니다. 전역 인과 발견 방법은 전체 인과 그래프 학습에 중점을 두므로 최적 조정 집합(즉, 가장 낮은 점근 분산을 가진 집합)을 복구할 수 있지만, 변수 수의 증가에 따라 계산상 빠르게 감당할 수 없게 됩니다. 국소 인과 발견 방법은 목표 변수의 국소 이웃에 중점을 두어 더 확장 가능한 대안을 제공하지만, 통계적으로 차선의 조정 집합에만 제한됩니다. 본 연구에서 저자들은 국소 방법의 계산 효율성과 전역 방법의 통계적 최적성을 결합한 신뢰할 수 있고 완전한 인과 발견 방법인 국소 최적 조정 발견(LOAD)을 제안합니다.

연구 배경 및 동기

문제 정의

인과 추론에서 두 변수 간의 인과 효과를 추정하는 것은 핵심 과제입니다. 잠재적 인과 그래프가 미지의 상태일 때, 인과 효과 추정을 위한 유효한 조정 집합을 식별하기 위해 인과 발견 방법이 필요합니다. 기존 방법들은 근본적인 트레이드오프에 직면해 있습니다:

전역 방법의 딜레마: 전역 인과 발견 방법(예: PC 알고리즘)은 완전한 인과 그래프를 학습하고 최적 조정 집합을 복구할 수 있지만, 계산 복잡도가 변수 수에 따라 지수적으로 증가하여 대규모 문제에서 실행 불가능합니다.
국소 방법의 한계: 국소 인과 발견 방법(예: MB-by-MB, LDECC)은 계산 효율이 높지만 차선의 조정 집합만 복구할 수 있어 인과 효과 추정의 점근 분산이 높습니다.

연구 동기

저자들은 기존 국소 방법의 다음과 같은 문제점을 발견했습니다:

LocalPC 알고리즘은 인접 변수 식별 시 신뢰성이 부족하여 인접하지 않은 배우자를 인접한 것으로 잘못 식별할 수 있음
LDECC 알고리즘은 불완전하여 특정 상황에서 모든 방향 지정 가능한 간선을 방향 지정할 수 없음
LDP 알고리즘은 특정 식별 가능한 효과가 0일 때 효과를 식별 불가능하다고 잘못 보고할 수 있음

따라서 국소 방법의 계산 효율성을 유지하면서 전역 방법의 통계적 최적성을 달성하는 새로운 방법이 필요합니다.

핵심 기여

국소 정보를 기반으로 인과 효과 식별 가능성을 결정하는 방법 개발: 국소 정보만 사용하여 인과 효과의 식별 가능 여부를 판단하는 필요충분조건을 제안했습니다.
LOAD 알고리즘 제안: 변수 주변의 국소 정보만 사용하여 최적 조정 집합을 식별할 수 있는 신뢰할 수 있고 완전한 방법입니다.
포괄적인 실험 평가: 합성 데이터와 실제 데이터에서 LOAD를 평가하여 낮은 계산 비용으로 고품질의 조정 집합을 복구할 수 있음을 입증했습니다.
이론적 보장: LOAD의 인과 효과 식별 가능성 결정 및 최적 조정 집합 발견에 대한 신뢰성과 완전성을 증명했습니다.

방법론 상세 설명

작업 정의

목표 변수 X와 Y의 쌍이 주어졌을 때, 목표는:

X와 Y 간의 인과 관계 결정(명시적 조상, 가능한 조상 또는 확정 비조상)
인과 효과의 식별 가능 여부 판단
식별 가능한 경우 최적 조정 집합을 찾고, 그렇지 않으면 국소적으로 유효한 부모 조정 집합 반환

LOAD 알고리즘 구조

LOAD 알고리즘은 5개의 주요 단계로 구성됩니다:

단계 1: 목표 변수 간 인과 관계 결정

LocalRelate 알고리즘(알고리즘 1)을 사용하여 다음 정리를 통해 관계를 결정합니다:

명시적 조상 관계(정리 4.1): CPDAG G의 임의의 두 개의 서로 다른 노드 X와 Y에 대해, X ∈ ExplAn_G(Y) ⟺ X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
확정 비조상 관계(정리 4.2): X는 Y의 확정 비조상 ⟺ X ⊥⊥ Y | Pa_G(X)

단계 2: 인과 효과의 식별 가능성 검증

국소 정보를 기반으로 한 적응적 검증을 제안합니다:

보조정리 4.3: CPDAG G의 X ∈ PossAn_G(Y)에 대해, G는 (X,Y)에 대해 조정 적응적 ⟺:

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

이 조건은 LocalAmenTest 알고리즘(알고리즘 2)으로 효율적으로 검출할 수 있습니다.

단계 3-5: 최적 조정 집합 구성

인과 효과가 식별 가능한 경우, LOAD는 다음 단계를 통해 최적 조정 집합을 구성합니다:

명시적 후손 찾기: T의 모든 명시적 후손 식별
중개 노드 식별: T의 명시적 후손이면서 동시에 O의 명시적 조상인 노드 찾기

최적 조정 집합 구성:

Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})

기술적 혁신점

국소 적응성 검증: 국소 정보만 사용하여 적응성을 검증할 수 있는 필요충분조건을 처음으로 제안하여 모든 가능한 방향 경로 확인의 필요성을 제거했습니다.
캐싱 메커니즘: 개선된 MB-by-MB 알고리즘은 캐싱을 사용하여 이전 실행에서 식별된 마르코프 담요와 국소 구조를 재사용하여 계산 효율성을 크게 향상시킵니다.
이론적 완전성: LOAD가 인과 관계 결정, 식별 가능성 및 최적 조정 집합 측면에서 신뢰할 수 있고 완전함을 증명했습니다.

실험 설정

데이터셋

합성 데이터:
- 무작위 생성 Erdős–Rényi 그래프 사용
- 변수 수: 100-1000
- 예상 차수: d=2, 최대 차수: dmax=10
- 샘플 수: nD=10000
실제 네트워크:
- MAGIC-NIAB 네트워크: 44개 노드, 평균 차수 3
- ANDES 네트워크: 223개 노드, 평균 차수 3.03