Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians

"Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians" 논문의 상세한 기술적 요약입니다.

1. 문제 정의

연속적 인과 발견 (Causal Discovery) 은 관측 데이터로부터 잠재적인 방향성 비순환 그래프 (DAG) 를 복원하는 것을 목표로 합니다. 현재 최첨단 방법론들 (예: NOTEARS, DAGMA) 은 비볼록 비순환성 패널티 (예: $tr(e^{W \circ W}) = d$) 를 통해 표현 학습과 구조 최적화를 결합하는 연속 제약 최적화에 의존합니다.

주요 한계점:

• 국소 최적해: 비순환성 패널티의 비볼록성으로 인해 경사 기반 솔버가 특히 고차원 영역에서 국소 최소값에 갇히게 됩니다.
• 확장성: 반복적인 비순환성 검사로 인해 각 경사 단계당 $O(d^3)$의 계산 비용이 발생하여, 고차원 데이터셋 ($d \gg 100$) 에 대한 확장성이 제한됩니다.
• 재학습 오버헤드: 기존 점수 기반 접근법은 노드 순서를 식별하기 위해 주변화된 부분집합에 대해 생성 모델을 재귀적으로 재학습해야 하므로 심각한 계산 병목 현상을 초래합니다.

2. 방법론: Score-Schur 위상 정렬 (SSTS)

저자들은 비볼록 최적화의 병목 현상을 통계적 점수 추정으로 전환하는 분리된 패러다임을 제안합니다. 핵심 아이디어는 인과 위계가 **점수 - 야코비안 정보 행렬 (SJIM)**에 기하학적 서명을 남긴다는 것입니다.

A. 이론적 기반

• 점수 함수 및 SJIM: $s(x) = \nabla_x \log p(x)$를 점수 함수라고 합시다. SJIM, $I$는 로그 밀도의 음의 헤시안 (Hessian) 의 기댓값으로 정의됩니다: $I = \mathbb{E}[-\nabla^2_x \log p(x)]$.
• 리프 식별성 (Theorem 3.1): 선형 가우시안 가법 노이즈 모델 (ANMs) 에서 SJIM 의 대각선 항목은 위상적 위계를 인코딩합니다. 구체적으로, 노드 $l$이 위상적 리프 (싱크) 일 필요충분조건은 그 대각선 항목 $I_{ll}$이 최소 ($1/\sigma^2$) 라는 것입니다.
• 슈어 여인자를 통한 정확한 주변화 (Theorem 3.2): 리프가 식별되면, 이를 그래프에서 제거하는 것은 수학적으로 해당 리프에 대한 SJIM 의 **슈어 여인자 (Schur complement)**를 계산하는 것과 동일합니다. 이는 생성 모델을 재학습하지 않고도 재귀적 제거를 가능하게 합니다.
• 비선형 확장 및 기댓값 갭: 비선형 ANMs 에서 기댓값 연산자는 행렬 역행렬과 교환되지 않습니다 ($\text{Schur}(\mathbb{E}[H]) \neq \mathbb{E}[\text{Schur}(H)]$). 저자들은 노이즈 메커니즘의 기울기 공분산에 비례하는 **기댓값 갭 (Expectation Gap, $\Delta$)**을 유도했습니다. 이 갭은 비선형 설정에서 구조적 오차를 유발합니다.

B. 알고리즘: Block-SSTS

기댓값 갭과 유한 표본 분산을 해결하기 위해 저자들은 Block-SSTS를 도입합니다:

1. 생성 모델링: $s_\theta(x)$를 추정하기 위해 제약이 없는 점수 네트워크 (예: MLP) 를 학습합니다.
2. 희소 야코비안 사전: 경험적 야코비안에서 희소성을 유도하여 고차원에서의 추정 분산을 줄이기 위해 입력층 가중치에 그룹 라쏘 ($\ell_{1,2}$) 패널티를 적용합니다.
3. 블록 주변화: 순차적 단일 노드 제거 대신, 알고리즘은 허용 오차 $\gamma$ 내에서 유사한 대각선 에너지를 가진 병렬 리프 노드들을 그룹화하고 블록 슈어 여인자 역행렬을 수행합니다.
   • 이는 추출 깊이를 압축하여 비선형 기댓값 갭의 누적을 단절합니다.
   • 정확한 샘플별 공분산 패칭의 $O(Nd^3)$ 비용을 회피합니다.
4. 엣지 가지치기: 위상적 순서가 추출되면, 각 노드를 허용된 조상들에 대해 표준 희소 회귀 (Lasso) 를 통해 DAG 를 복원합니다.

3. 주요 기여

1. 비순환성의 대수적 매핑: 선형 가우시안 ANMs 에서 반복적 리프 노드 주변화가 SJIM 의 슈어 여인자와 정확히 동등함을 증명했습니다. 비선형 ANMs 에 대해서는 근사 오차 (기댓값 갭) 를 특성화했습니다.
2. 분리된 추출: 비볼록 최적화 병목 현상을 완전히 제거했습니다. 인과 발견은 결정론적 행렬 연산 ($O(d^3)$ 총비용, 단 한 번 수행) 을 따르는 통계적 추정 문제로 재정의되었습니다.
3. $d=1000$까지의 확장성: 고차원 비선형 그래프를 처리하기 위한 Block-SSTS 를 도입하여, 연속 최적화 방법론이 실패하는 영역인 최대 1000 개의 변수까지 구조 복원을 달성했습니다.
4. 지표 수정: 병렬 DAG 평가에 랭크 상관관계 (Kendall's $\tau$) 를 사용하는 것에 반대하며, 위상적 모호성에 불변인 엄격한 지표인 **엣지 위반 (Edge Violations, EV)**을 제안했습니다.

4. 실험 결과

• 선형 영역: SSTS 는 선형 ANMs 에서 $d=1000$까지의 차원에서 영 (zero) 인 인과 엣지 위반을 달성하여 이론적 정확성을 검증했습니다.
• 비선형 영역:
  • 효율성: $d=50$에서 SSTS 는 실행 시간을 DAGMA 의 약 2700 초에서 3.66 초로 단축하면서 구조적 해밍 거리 (SHD: 2.6 대 93.0) 를 현저히 낮췄습니다.
  • 확장성: $d=1000$에서 SSTS 는 1 초 미만으로 추출을 완료하는 반면, 연속적 방법론들은 계산적으로 처리 불가능합니다.
  • 트레이드오프: SSTS 는 비선형 기댓값 갭으로 인해 작은 구조적 오차를 도입하지만, 이는 최적화 수렴이 아닌 점수 네트워크의 유한 표본 추정 분산에 의해 제한됩니다.
• 실제 데이터: Sachs 단백질 신호 전달 네트워크 ($d=12$) 에서 SSTS 는 정확도 (SHD 13.8 대 15.0/16.2) 와 속도 (6.62 초 대 182 초/56 초) 모두에서 DAGMA 와 Scalable SCORE 를 능가했습니다.
• 애블레이션 연구:
  • 희소성: 그룹 라쏘 사전은 데이터가 부족한 영역 ($N=500, d=100$) 에서 안정성에 중요합니다.
  • 블록 허용 오차: 적절한 블록 허용 오차 ($\gamma \approx 0.05$) 는 인과 위계를 위반하지 않으면서 오차 누적을 최적화적으로 단절합니다.

5. 의의 및 결론

이 연구는 인과 발견을 제약 최적화 문제에서 통계적 추정 과제로 근본적으로 재정의합니다. 점수 함수의 기하학적 속성과 슈어 여인자의 대수적 속성을 활용함으로써, SSTS 는 연속적 비순환성 패널티에 내재된 국소 최적해 및 확장성 문제를 우회합니다.

함의:

• 이론적: 점수 매칭, 정보 기하학, 위상 정렬 간의 직접적인 연결을 확립합니다.
• 실용적: 이전까지 연속 최적화 방법론으로 접근할 수 없었던 고차원 비선형 데이터셋 ($d=1000$까지) 에서 인과 구조 학습을 가능하게 합니다.
• 한계: 비선형 영역에서 이 방법의 충실도는 최적화 수렴이 아닌 점수 함수 추정 (유한 표본 분산) 의 정확도와 비선형 기댓값 갭의 크기에 의해 궁극적으로 제한됩니다.

요약하자면, SSTS 는 인과 발견을 위한 결정론적이고 최적화 없는 경로를 제공하며, 비볼록 병목 현상이 제거되면 주요 과제는 점수 기하학의 통계적 추정이 됨을 입증합니다.