기술 요약: 미지의 개입이 존재하는 환경에서의 후회 기반 연합 인과 발견 (Regret-Based Federated Causal Discovery with Unknown Interventions)

문제 정의

관측 데이터로부터의 인과 발견은 일반적으로 마르코프 동치 클래스(MEC)를 나타내는 완성된 부분 방향 비순환 그래프(CPDAG)를 복구한다. 최근의 연합 인과 발견(FCD) 방법들은 데이터의 분산화와 프라이버시 문제를 다루고 있지만, 모든 클라이언트가 개입의 영향을 받지 않는 동일한 인과 모델을 공유한다는 이상적인 가정에 의존한다. 실제 연방 환경(예: 다기관 병원)에서는 클라이언트별 정책과 프로토콜이 자연스럽게 **이질적이고 미지인 개입(heterogeneous and unknown interventions)**을 유도한다. 이러한 개입은 로컬 인과 구조를 변화시키며(예: 구조적 개입을 통한 유입 엣지 제거), 이로 인해 표준 FCD 알고리즘은 미싱된 엣지가 개입에 의한 것인지 아니면 기저의 인과 구조에 의한 것인지 구분하지 못하게 되어 효과가 떨어진다. 또한, 미지 개입이 존재하는 인과 발견을 위한 기존 방법들은 데이터 중앙 집중화를 가정하여 프라이버시 제약을 위반하거나, 개입 대상을 알고 있어야 한다는 현실적이지 않은 요구사항을 가진다.

방법론: I-PERI

저자들은 미지의 클라이언트 수준 개입을 처리하면서 차분 프라이버시(differential privacy)를 보장하도록 설계된 새로운 연합 알고리즘인 I-PERI(Intervention-PERI)를 제안한다. I-PERI는 개입으로 유도된 구조적 차이를 활용하여 전역 인과 그래프를 정교화함으로써 PERI 알고리즘을 확장한다. 이 방법은 두 가지 별도의 단계로 작동한다.

1. 연합 CPDAG 복구 (Phase 1)

첫 번째 단계는 모든 클라이언트의 기초가 되는 공통 CPDAG인 $C(G)$를 복구하는 것을 목표로 한다.

• 과제: 여기서 표준 후회 함수(regret function)는 실패한다. 왜냐하면 구조적 개입은 엣지를 제거하며, 이로 인해 클라이언트의 CPDAG는 진의 전역 CPDAG의 부분 그래프가 되기 때문이다. 직접적으로 후회를 최소화하면, 개입에 의해 실제로 제거된 엣지를 서버가 "놓친" 것으로 간주하여 페널티를 부여하게 된다.
• 해결책: I-PERI는 방향 일치 마스킹(Directed-Consensus Masking, $\mu$)을 도입한다. 서버 그래프를 각 클라이언트의 그래프에 대해 마스킹하는 이 작업은 다음과 같다:
  • 두 그래프 모두에 존재하는 엣지는 유지한다.
  • 서버에는 존재하지만 클라이언트에는 없는 엣지는 제거한다(개입에 의한 것임을 인정).
  • 대응하는 클라이언트 엣지가 방향성을 가지면 서버의 무방향 엣지에 방향을 부여한다.
• 최적화: 알고리즘은 마스킹된 그래프에 대해 최악의 경우의 후회(worst-case regret)를 최소화한다:
  $$\hat{G} = \arg \min_{H \in C(G)} \max_{k} \left( L(\mu(H, C(G^{\Phi_k})), D_k) - L(C(G^{\Phi_k}), D_k) \right)$$
  여기서 $L$은 일관된 스코어링 함수(예: BIC)이다. 이는 서버가 기저의 인과 DAG $G$의 CPDAG로 수렴하도록 보장한다.

2. 방향 정교화 (Phase 2)

두 번째 단계는 구조적 개입이 **차폐된 충돌체(shielded colliders)**를 **비차폐된 충돌체(unshielded colliders, v-structures)**로 변환할 수 있다는 점을 활용하여, 순수 관측 데이터에서는 모호했던 엣지 방향을 밝혀낸다.

• 메커니즘: I-PERI는 무방향 일치 마스킹(Undirected-Consensus Masking, $\nu$)을 사용한다. 이 마스크에서는 무방향 엣지가 방향성 엣지보다 우선권을 갖는다. 알고리즘은 개입으로 유도된 v-structure로 인해 클라이언트 그래프에서 방향성을 갖게 된 엣지를 서버가 방향을 정하지 못했을 때 페널티를 부여한다.
• 최적화: 후회는 무방향 마스킹된 그래프에 대해 계산된다:
  $$R_k(H) = L(\nu(H, C(G^{\Phi_k})), D_k) - L(C(G^{\Phi_k}), D_k)$$
  탐색 공간은 Phase 1의 CPDAG로부터 파생된 부분 방향 그래프로 제한된다.

프라이버시 보장

I-PERI는 $\epsilon$-차분 프라이버시를 염두에 두고 설계되었다. 클라이언트는 로컬 그래프나 모델 파라미터를 공유하는 대신, 로컬 후회를 계산하고 전송 전 라플라스 노이즈(Laplace noise)를 추가한다. 논문은 후회 함수의 민감도에 대한 이론적 경계를 제공하여, 노이즈 추가가 개별 데이터 포인트를 보호하면서도 전역 그래프 복구의 효용성을 크게 저해하지 않음을 보장한다.

주요 기여

1. $\Phi$-마르코프 동치 클래스 ($\Phi$-MEC): 저자들은 표준 관측 MEC보다 엄격하고, 알려진 개입을 전제로 하는 I-MEC보다는 완화된 새로운 동치 클래스인 $\Phi$-MEC를 정의한다. 이는 미지 개입이 존재하는 연합 환경에서 달성 가능한 최선의 복구를 나타낸다.
2. $\Phi$-CPDAG: 클라이언트 수준의 개입에 의해 드러난 v-structure를 바탕으로 CPDAG의 엣지에 방향을 부여하여 얻은 $\Phi$-MEC의 대표 그래프이다.
3. I-PERI 알고리즘: 개입 대상을 알 필요가 없거나 로컬 데이터를 공유하지 않고도 $\Phi$-CPDAG를 복구하는 두 단계의 연합 알고리즘이다.
4. 이론적 보장: 논문은 인과적 충분성(causal sufficiency)과 충실성(faithfulness)을 가정할 때, 샘플 크기가 무한히 커짐에 따라 I-PERI가 $\Phi$-CPDAG로 수렴함을 증명한다. 또한 공식적인 차분 프라이버시 보장을 확립한다.

실험 결과

저자들은 선형 합성 데이터셋을 사용하여 I-PERI를 최신 베이스라인(PERI, FedDAG, NOTEARS-ADMM, FedCDH)과 비교 평가하였다.

• 성능: I-PERI는 변수의 수($p \in \{3, \dots, 20\}$), 클라이언트 수($K$), 샘플 크기($n$)가 변함에 따라 SHD(Structural Hamming Distance)와 F1 스코어 측면에서 일관되게 베이스라인보다 우수한 성능을 보였다.
• 엣지 방향성: I-PERI의 두 번째 단계는 초기 CPDAG에서 모호했던 추가 엣지들에 방향을 성공적으로 부여하였으며, 이는 개입으로 유도된 이질성을 활용하는 것의 유용성을 입증한다.
• 효율성: I-PERI는 경쟁 방법들과 비교하여 현저히 낮은 계산 실행 시간(수 차례의 오더 차이)을 보여주었다.
• 강건성: 이 방법은 서로 다른 로컬 발견 알고리즘(PC 및 GES)을 사용할 때도 효과적이었으며, 동질적 및 이질적 샘플 크기 설정 모두에서 일관된 성능을 보였다.

의의 및 주장

본 논문은 미지 개입이 존재하는 환경에서의 비현실적인 동질성 가정을 넘어섬으로써 연합 인과 발견의 중요한 공백을 메운다고 주장한다.

• 이질성 활용: 전통적인 연합 학습에서 클라이언트 이질성이 종종 최소화해야 할 노이즈로 취급되는 것과 달리, I-PERI는 개입으로 인한 구조적 차이를 인과 방향을 정교화하기 위한 정보의 원천으로 취급한다.
• 프라이버시 보존 발견: 본 연구는 개입 대상을 공개하거나 데이터를 중앙 집중화하지 않고도, 차분 프라이زم 기반의 후회 집계(regret-based aggregation)를 통해 고품질의 인과 발견이 가능함을 보여준다.
• 이론적 발전: $\Phi$-MEC를 정의함으로써, 본 논문은 미지 개입이 있는 연합 환경에서 식별 가능한 이론적 한계를 설정하며, 이는 관측 데이터만으로 얻을 수 있는 한계보다 더 타이트한 경계를 제공한다.

저자들은 I-PERI의 정확도가 클라이언트가 학습한 로컬 CPDAG의 품질에 달려 있으며, 이론적 보장이 복잡한 실제 시나리오에서 위반될 수 있는 표준 가정(인과적 충분성, 충실성)에 의존하고 있음을 언급한다. 향후 연구로는 잠재 변수(latent variables)와 선택 편향(selection bias)이 존재하는 환경으로 프레임워크를 확장하는 것이 제안되었다.