SPADE가 조합적 인과 발견의 확장성 한계를 밀어낸다

무엇인가

이 논문은 관측 데이터만으로 비선형 인과 구조를 찾는 문제, 그중에서도 인과적으로 충분한(causally sufficient) 비선형 가산 잡음 모델(ANM)을 다룬다. 개입 실험이 비싸거나 불가능한 상황에서 대규모 관측 데이터로 방향성 비순환 그래프(DAG)를 복원하는 것은 과학적 가설 생성과 분포 이동 하에서의 견고성에 직결된다. 문제는 DAG 공간이 초지수적으로 커지고, 비선형 메커니즘은 닫힌 형태의 점수로 다루기 어렵다는 점이다. 저자들은 미분 가능 구조 학습, 상각(amortized) 구조 학습, 스코어 매칭, 조합적 탐색이라는 네 계열을 같은 조건에서 비교해 정확도-런타임 지형을 실증적으로 지도화하는 것에서 출발한다.

어떻게 동작하나

비교 결과 병목은 계열마다 상보적이었다. 미분 가능 방법(SDCD 등)과 상각 방법(CauScale 등)은 가장 큰 변수 차원까지 확장되지만 구조 정확도(F1)가 벤치마크 최고치에 크게 못 미친다. 스코어 매칭(DAS 등)은 저차원에서는 경쟁력이 있으나 변수 수가 늘면 고차원 스코어 도함수 추정이 어려워져 정확도가 급격히 무너지고, Stein 추정량의 표본 크기에 대한 삼차 런타임 때문에 1만 표본에서 시간 제한에 걸린다. 조합적 방법(Topic)은 변수 수가 커져도 F1이 완만하게만 떨어져 가장 강한 구조 신호를 주지만, 변수 수에 대해 삼차 개수의 국소 점수 평가를 수행하고 각 평가마다 비선형 모델을 적합해야 해서 느리다. 저자들이 주목한 것은 바로 이 지점, 즉 신호 자체가 아니라 "반복적이고 중복된 국소 점수 계산"이 병목이라는 사실이다.

무엇과 다른가

제안 방법 SPADE는 이 병목을 캐싱으로 제거한다. 각 변수마다 중심화된 고정 기저 스플라인 설계행렬 B_k를 만들고, 부모 집합 S에 대해 B_S = [B_k]_{k∈S}로 조건부 평균을 표현한 뒤 페널티 최소제곱(β̂ = argmin ||Y_j − B_S β||² + βᵀP_S β, P_S = λΩ_S + εI)으로 계수를 추정한다. 핵심은 탐색 전에 전역 설계행렬 B와 중심화 응답 Y로부터 G = BᵀB, H = BᵀY, c_j = Y_jᵀY_j를 한 번만 계산해 두는 것이다. 그러면 어떤 부모 집합 질의든 정규방정식 [G_{I(S),I(S)} + P_S] β̂ = H_{I(S),j}로 축소되어, 캐시 블록을 꺼내 |S|K 차원의 선형계를 푸는 것으로 끝난다. 잔차 제곱합도 RSS = c_j − 2β̂ᵀH + β̂ᵀGβ̂로 캐시만으로 계산된다. 잔차 우도는 두 가지인데, 가우시안 변형(SPADE-Gauss)은 캐시된 이차형식만으로 점수를 내고, 히스토그램 변형(SPADE-Hist)은 같은 평균 적합을 쓰되 잔차 벡터를 실제로 만들어 유연한 잔차 밀도를 추정한다. 탐색은 Topic의 위상 순서 탐색 절차를 그대로 쓰되, 기존의 개별 큐빅 스플라인 + MDL 점수 대신 공유 고정 기저 + BIC 페널티(k_S log n)를 사용한다.

어떻게 쓰나

복잡도 분석이 이 논문의 핵심 주장이다. 캐시 구축은 고정 K에 대해 O(nd²) 시간과 O(d²) 저장공간을 쓰고, 부모 집합 크기 p에 대해 SPADE-Gauss는 질의당 O(p³), SPADE-Hist는 O(np + p³)가 든다. 유계 진입차수(bounded indegree) 가정 아래에서는 각각 상수 시간과 O(n) 시간이 된다. Topic이 O(d³)번의 국소 점수 질의를 하므로, 총 점수 평가 비용은 직접 반복 적합의 O(nd³)에서 SPADE-Gauss의 O(nd² + d³)로 줄어든다. SPADE-Hist는 점근적으로는 여전히 O(nd³)이지만 평균 적합의 반복이 사라져 실측 속도 향상은 크다.

전제와 한계

확장성 실험은 변수 수 d = 25·2^k, 표본 n = 2500(기대 차수 3의 에르되시-레니 DAG, 5시드, 24시간 타임아웃, 40GB GPU 초과 시 OOM)과, d = 100 고정 후 n = 2500·2^k로 구성됐다. d = 800에서 Topic이 12.5시간 걸린 반면 SPADE-Gauss는 99.3초(456배), SPADE-Hist는 386.9초(117배)에 끝났다. d = 1600에서는 Topic이 24시간 안에 완료하지 못했지만 두 변형 모두 제한 내에 종료했다. 표본 확장에서는 Topic이 종료하는 최대 표본 크기에서 각각 2708배, 291배 빨랐고, n = 160,000에서도 둘 다 완료하면서 가장 높은 구조 정확도를 유지했다. 정확도 향상은 캐싱 때문이 아니라 BIC 페널티를 붙인 고정 기저 스플라인 점수가 이 영역에서 더 나은 부모 집합 기준을 준다는 해석이다.

강건성 실험은 기대 차수 {2,3,4}의 ER DAG, 가산/비가산 메커니즘, 가우시안·단봉 대칭·단봉 비대칭·다봉 잡음을 아우르는 96개 설정에서 n ∈ {1000, 2000}, d ∈ {20, 50}로 수행됐고, Score, NoGAM, Caps, 커널 기반 PC/FCI를 추가 비교군으로 넣었다. 결과적으로 SPADE-Hist가 전반적으로 가장 강하고 비가우시안 잡음에 가장 견고했으며, SPADE-Gauss는 가우시안 잡음 영역에서 최고였다. 전체 합성 설정 평균에서 SPADE-Hist는 F1 0.748로 최강 비-SPADE 비교군인 Topic의 0.616을 앞서면서 평균 런타임을 75.35초에서 1.24초로 약 61배 줄였다. 가장 빠른 외부 방법인 CauScale은 평균 6.23초에 F1 0.542에 그쳤다. 실제 데이터인 Causal Chamber 벤치마크에서도 SPADE-Hist가 F1 0.50을 0.97초에 달성했고, F1이 가장 가까운 SDCD는 0.49를 내려면 520초가 필요했으며 CauScale은 10초에 F1 0.27이었다.

개발자 관점에서 이 논문이 주는 실무적 시사점은 명확하다. 첫째, 인과 발견 파이프라인에서 "가장 정확한 방법"과 "가장 빠른 방법" 사이의 선택은 규모에 따라 달라지며, 변수 수가 수백을 넘으면 미분 가능·상각 계열은 속도는 얻지만 F1을 크게 잃는다. 둘째, 조합적 탐색을 쓸 경우 병목은 탐색 알고리즘이 아니라 국소 점수 평가의 반복이므로, 기저를 고정하고 충분통계를 미리 컴파일하는 것만으로 수백 배의 속도 향상이 가능하다. 셋째, 잔차 분포가 가우시안에서 멀면 SPADE-Hist를, 규모가 극단적이거나 잔차가 가우시안에 가까우면 SPADE-Gauss를 기본값으로 고려하라는 것이 저자들의 권고다.

한계도 분명히 밝힌다. 이 비교는 어디까지나 실증적이므로 각 계열의 강점과 병목은 연구된 벤치마크에서의 패턴으로 읽어야 하고, 다른 시뮬레이터와 응용 영역에서의 재현이 필요하다. 또한 인과적으로 충분하고 완전히 식별 가능한 가산 잡음 모델만 다루며, 부분 식별 CPDAG 설정, 이분산 메커니즘, 잠재 교란, 더 넓은 함수적 인과 모델로 컴파일된 국소 점수를 확장하는 일은 미해결 과제로 남는다. 저자들은 조합적 탐색이 확장 가능한 인과 발견의 유일한 경로가 아니며, 스코어 도함수 추정·미분 가능 최적화·상각 인과 발견의 개선이 상보적 해법이 될 수 있다고 덧붙인다.