Root Cause Analysis of Outliers in Unknown Cyclic Graphs

기술 요약: 미지의 순환 그래프에서의 이상치 원인 분석(Root Cause Analysis)

문제 정의
원인 분석(Root Cause Analysis, RCA)은 인과 시스템에서 이상 현상이 어디서 시작되었는지 식별하는 것을 목표로 하며, 단순히 전파에 의해 증상을 보이는 노드와 근본 원인 노드를 구분하는 것을 목적으로 한다. 기존의 방법들은 종종 실제 인과 그래프를 학습하거나 비순환 구조(Directed Acyclic Graphs, DAG)를 가정하는 경우가 많으나, 실제 시스템(예: 유전자 조절 네트워크 또는 마이크로서비스 아키텍처)은 빈번하게 순환 피드백 루프를 포함한다. 또한, 많은 기존 접근 방식은 여러 개의 이상 샘플을 요구하거나 제한적인 그래프 구조 가정을 필요로 한다. 본 논문은 사전 지식 없이 **선형 구조 방정식 모델(Linear Structural Equation Models, SEMs)**을 사용하여, 단 하나의 이상 샘플만으로 미지의 순환 그래프 내에서 근본 원인을 식별하는 과제를 다룬다.

방법론
저자들은 근본 원인 노드에서의 희소한 가산 섭동(sparse additive perturbation)을 제외하고, 정상 상태와 이상 상태 사이의 구조 방정식이 불변(invariance)하다는 점에 기반한 방법을 제안한다.

1. 모델 정식화:

   • 시스템은 $X = AX + N$으로 모델링된다. 여기서$A$는 (순환을 포함할 수 있는) 계수 행렬이며,$N$은 상관관계가 없는 성분을 가진 노이즈 벡터이다.
   • 이상 샘플 $\tilde{X}$는 $\tilde{X} = A\tilde{X} + N' + \Delta$로 모델링된다. 여기서 $\Delta$는 근본 원인 노드에서의 섭동을 나타내는 희소 벡터이다.
   • 이 방법은 선형 관계(행렬 $A$)는 변하지 않고, 오직 노이즈 항만이 섭동된다고 가정한다.

2. 인과적으로 충분한 순환 모델(Causally Sufficient Cyclic Model):

   • 핵심 통찰은 정밀도 행렬(precision matrix) $\Theta_{XX} = \Sigma_{XX}^{-1}$에 있다.
   • 이상치 벡터($\xi = \Theta_{XX}\tilde{X}$)에 정밀도 행렬을 적용함으로써, 저자들은 결과 벡터 $\xi$가 정상 분포에서 벗어나는 지점이 근본 원인 노드 및 그 부모 노드들뿐임을 도출한다.
   • 정리 3.1: 일반적인 파라미터에 대해, $\xi_i$가 정상 사례의 분포와 달라지는 노드 집합은 근본 원인 $R$과 그 부모 $pa(R)$의 합집합의 부분집합이다.
   • 정리 3.2: 이 목록은 관측된 데이터에서의 이상치 노드($\tilde{X}_i$)와의 교집합을 통해 더욱 정교하게 다듬어질 수 있으며, 이를 통해 근본 원인과 그 자손인 부모 노드들의 단기 목록(shortlist)을 얻을 수 있다.

3. 잠재 변수 처리:

   • 이 방법은 잠재 변수를 주변화(marginalizing out)하여 제거하는 시나리오로 확장된다. 이는 관측된 변수의 노이즈 항들이 서로 상관관계를 가질 수 있는 투영된 SEM 결과를 낳는다.
   • 관측된 변수의 정밀도 행렬이 도출되며, 섭동의 지지 집합(support)은 "지그재그(zig-zag)" 구조(잠재 경로의 연속)를 통해 관측 가능한 근본 원인과 연결된 노드들을 포함함을 보여준다.

4. 구현 및 통계적 제어:

   • 알고리즘은 정상 샘플로부터 정밀도 행렬을 추정한다(Graphical Lasso 또는 직접 역행렬 사용).
   • 이상 샘플에 대한 점수 벡터 $\xi$를 계산한다.
   • 후보를 선택할 때 거짓 발견율(False Discovery Rate, FDR)을 제어하기 위해, 저자들은 p-value 대신 e-value(구체적으로 분산으로 정규화된 제곱 Z-score)를 사용하여 의존성이 있는 상황에서도 강건한 다중 검정 보정을 가능하게 한다.
   • 최종 점수는 노드가 이상치인지 여부(임계값 $\tau$ 기준)에 따라 점수를 0으로 설정함으로써 할당된다.

주요 기여

• 순환 그래프 역량: 본 논문은 단 하나의 이상 샘플을 사용하여 미지의 순환 그래프에서 RCA를 수행할 수 있는 최초의 증명 가능한 방법을 제공하며, 기존 연구(예: Li et al., 2025)의 비순환 가정을 극복한다.
• 실제 그래프 지식 불필요: 이 접근 방식은 인과 그래프를 사전에 알거나 학습할 필요가 없으며, 오직 정상 데이터의 공분산 구조에만 의존한다.
• 이론적 보장: 저자들은 이 방법이 실제 근본 원인과 그 부모(특히 근본 원인과 함께 순환 상에 존재하는 노드)를 포함하는 후보 단기 목록을 식별함을 증명한다.
• 잠재 변수 강건성: 프레임워크는 잠재 변수를 처리하도록 확장되어, "관측 가능한 근본 원인"(이상 현상에 의해 영향을 받은 가장 초기 단계의 관측 노드)을 식별한다.
• 계산 효율성: 이전 방법들에서 사용된 조합 탐색(예: 순열 탐색)을 피함으로써, 제안된 방법은 계산 효율성이 높으며 정밀도 행렬 추정 비용에 의해 지배된다.

결과

• 시뮬레이션: 50개 및 100개의 노드를 가진 합성 실험(순환 및 비순환, 잠재 변수 유무 포함)에서, 제안된 방법(Graphical Lasso 또는 역공분산 사용)은 Cholesky 분해 기반 방법(Li et al., 2025)과 BARO 벤치마크를 지속적으로 능가하였다. 특히 순환 환경과 더 큰 규모의 그래프에서 실제 근본 원인을 순위 매기는 정확도가 더 높았으며, 속도 또한 훨씬 빨랐다.
• 실제 데이터: 방법론은 다음을 포함한 다양한 벤치마크에서 평가되었다:
  • 마이크로서비스 시스템: PetShop, Sock Shop, Online Boutique, Train Ticket.
  • 생물학적 데이터: 멘델 질환 환자의 유전자 발현 데이터.
  • 합성 벤치마크: CIRCA 및 RCD 데이터셋.
• 결과: 제안된 방법은 기존 베이스라인(Cholesky, Z-Score, BARO)과 대등하거나 그보다 우수한 성능을 보였다. 특히 유전자 발현 데이터와 연속형 마이크로서비스 데이터에서 Cholesky 방식을 능가하였으며, 축소된 공분산 추정량을 통해 고차원 케이스(특징 수가 샘플 수보다 많은 경우)도 효과적으로 처리하였다.

의의 및 주장
저자들은 이것이 미지의 순환 그래프에서 단 하나의 이상 샘플을 사용하여 증명 가능하게 작동하는 유일한 방법이라고 주장한다. 이 방법의 의의는 "희소 메커니즘 변화(Sparse Mechanism Shift)" 가설 하에 작동한다는 점에 있다. 즉, 분포 변화가 오직 몇 개의 메커니즘(근본 원인)에서 발생하는 변화에 기인하며, 나머지 시스템의 구조 방정식은 불변이라는 가정이다. 저자들은 이 가정이 RCA 과제를 정의하는 데 결정적임을 강조한다. 이 가정이 없다면 이론적으로 어떤 노드든 근본 원인이 될 수 있기 때문이다. 이 방법은 실제적인 인과 그래프를 사용할 수 없는 복잡하고 순환적인 시스템의 신뢰성 공학을 위한 효율적이고 계산 가능한 솔루션을 제공한다.