기술 요약: EntroPath – 매니폴드 학습을 위한 최대 엔트로피 경로 앙상블 임베딩

1. 문제 정의

단일 세포 전사체학(single-cell transcriptomics) 및 분자 역학 궤적(molecular dynamics trajectories)과 같은 현대의 고차원 데이터셋은 종종 저차원 리만 매니폴드(Riemannian manifolds) 근처에 집중되어 있습니다. 매니폴드 학습의 핵심 목표는 이러한 매니폴드의 내재적 기하 구조, 특히 측지선 거리(geodesic distances)를 저차원 표현으로 복구하는 것입니다.

기존 접근 방식들은 다음과 같은 상당한 한계에 직면해 있습니다:

• 최단 경로 방법 (예: Isomap): 이웃 그래프 상의 단일 최단 경로를 통해 측지선을 추정합니다. 이러한 방식은 취약합니다. 지리적으로 멀리 떨어진 영역 사이에 생성된 단 하나의 "지름길(shortcut)" 에지가 전체 거리를 왜곡할 수 있습니다. 또한, 비볼록(non-convex) 또는 분기형(branching) 매니폴드에서는 이론적인 복구 보장이 실패하는 경우가 많습니다.
• 국소 이웃 방법 (예: t-SNE, UMAP): 확률적 목적 함수를 통해 국소적 관계를 보존하는 데 집중합니다. 시각화에는 효과적이지만, 전역적인 측지선 구조를 명시적으로 인코딩하지는 않습니다.
• 표준 확산 방법 (예: Diffusion Maps, PHATE): 경로 앙상블을 통해 정보를 집계하여 강건성을 제공합니다. 그러나 이들은 일반적으로 로컬 노드 차수(degree)로 정규화된 **표준 무작위 보행(Standard Random Walks, SRW)**에 의존합니다. 이는 확산이 밀도가 높은 영역으로 흐르게 하여, 희소한 가지(sparse branches)와 병목 구간(bottlenecks)을 압축하고, 궤적 데이터에서 고밀도 종단 상태(high-density terminal states)로 표현이 편향되게 만듭니다.

2. 방법론: EntroPath

EntroPath는 **최대 엔트로피 무작위 보행(Maximum Entropy Random Walk, MERW)**과 경로 앙상블에서 유도된 **자유 에너지 비유사도(free-energy dissimilarity)**를 기반으로 비유사도를 구축함으로써 이 문제를 해결합니다.

2.1 최대 엔트로피 무작위 보행 (MERW)

노드 차수에 의해 국소적으로 정규화되는 SRW($T_{ij} = A_{ij}/d_i$)와 달리, MERW는 경로의 엔트로피를 전역적으로 최대화합니다. 전이 행렬은 다음과 같이 정의됩니다:
$$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$$
여기서 $A$는 친화도 행렬(affinity matrix), $\lambda_{\max}$는 최대 고윳값, $\psi$는 그에 대응하는 페론-프로베니우스 고유벡터입니다.

• 전역적 가중치 재설정: MERW는 $\psi$를 통해 전역적 그래프 구조를 통합합니다. 이는 확률을 경로 앙상블 전체에 균등하게 배분하며, 저차수 병목 구간에 적은 질량만을 남깁니다.
• 슈뢰딩거 연산자 구조: MERW 라플라시안($I-T$)은 이산 슈뢰딩거 연산자 $H = \lambda_{\max}I - A = -\Delta + V$와 유사합니다. 여기서 $V$는 차수 불균일성에 의해 유도된 포텐셜($V_i = \lambda_{\max} - d_i$)입니다. 이 구조는 이 방법의 이론적 보장의 핵심입니다.

2.2 자유 에너지 비유사도

EntroPath는 노드 $i$와 $j$ 사이의 비유사도를 단일 최단 경로가 아니라, 모든 $k$-단계 경로에 대한 가중치의 합(분배 함수, partition function)의 음의 로그로 정의합니다.

• 경로 비용: 에지 비용은 음의 로그 친화도, $E(u,v) = -\log A_{uv}$로 정의됩니다.
• Log-Sum-Exp 공식: 비유사도는 다음과 같습니다:
  $$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$$
  여기서 $\tilde{A} = A/\lambda_{\max}$입니다. 이는 최단 경로 거리에 대한 soft-min 완화이며, 전체 $k$-단계 앙상블을 집계합니다.
• 엔트로피 항: 비유사도는 많은 비교 가능한 경로들에 의해 연결된 쌍에 보상을 주는 엔트로피 항($-\sum p(\gamma) \log p(\gamma)$)을 포함하며, 이를 통해 최단 경로 메트릭과 구별됩니다.
• 대칭화: 일반적인 친화도의 경우, 비유사도는 순방향 및 역방향 전이 확률의 기하 평균을 통해 대칭화됩니다: $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$. 대칭인 경우(가우시안 친화도의 경우 표준적임) 이는 $-\log (\tilde{A}^k)_{ij}$로 단순화됩니다.

2.3 기하학적 레짐(Regimes) 및 스케일링

확산 깊이 $k$는 두 가지 레짐 사이를 보간합니다:

1. 측지선 레짐 (작은 $k$): 비유사도는 Varadhan의 단시간 열 커널(heat-kernel) 공식을 통해 그래프 측지선(최단 경로)을 근사합니다.
2. 혼합 레짐 (큰 $k$): 비유사도는 페론 벡터에 의존하는 정상 분포(stationary distribution)로 수렴하며, 미세한 기하학적 세부 사항을 잃습니다.
   EntroPath는 MERW 연산자의 von Neumann 엔트로피의 "knee"를 사용하여 $k$를 자동으로 선택하며, 이는 확산 시간이 점들을 연결하기에는 충분하면서도 과도하게 혼합되지 않도록 보장합니다.

2.4 확장성

대규모 데이터셋을 위해 EntroPath는 다음을 채택합니다:

• 랜드마크 투영(Landmark Projection): 새로운 점들을 하위 집합의 랜드마크 임베딩으로 커널 보간을 통해 투영하는 Nyström 유형의 확장 방식으로, 전역 연산자의 재계산을 피합니다.
• 적응형 커널(Adaptive Kernels): 비균일한 샘플링 밀도를 효과적으로 처리하기 위해 적응형 대역폭(로컬 $k$-NN 거리에 기반함)을 사용합니다.

3. 주요 기여

1. 알고리즘 혁신: MERW와 경로 앙상블에서 유도된 자유 에너지 비유사도를 기반으로 하는 매니폴드 학습 방법인 EntroPath를 도입했습니다.
2. 이론적 정식화: 대칭화된 자유 에너지 비유사도가 단시간 극한에서 밑바탕이 되는 매니폴드의 제곱 측지선 거리로 수렴함을 증명했습니다 (Theorem 5.3). 이는 이산 슈뢰딩거-연산자 구조와 Varadhan의 공식을 기반으로 합니다.
3. 커널 연결성: 대칭화된 MERW 커널이 정확한 **Gram 인자 분해(Gram factorization)**를 가짐을 입증하여 (Proposition 4.1), 많은 프로파일 기반 확산 방법들과 달리 EntroPath를 커널 방법 및 확산 맵과 직접 연결했습니다.
4. 확장 가능한 확장 기능: 랜드마크 기반의 out-of-sample 임베딩 및 확산-포텐셜 의사시간(pseudotime) 방법을 개발했습니다.
5. 평가 프로토콜: 커널 품질(거리 수준)과 레이아웃 품질(임베딩 수준)을 분리하는 2단계 평가를 통해, 지면 참값(ground truth)에 사용된 특정 $k$-NN 그래프에 유리하게 작용할 수 있는 표준 측지선 평가의 편향을 강조했습니다.

4. 실험 결과

EntroPath는 합성 매니폴드(Swiss roll, sparse trees)와 6개의 생물학적 단일 세포 데이터셋(예: Paul15, Nestorowa, Root Atlas)에서 평가되었습니다.

• 합성 매니폴드:

  • 비균일하게 샘플링된 매니폴드 및 희소한 분기형 트리에서, EntroPath는 측지선 기하 구조를 복구하는 데 있어 확산 기반 베이스라인(PHATE, HeatGeo, DTNE) 및 최단 경로 방법(Isomap)보다 일관되게 우수한 성능을 보였습니다.
  • 거리 수준 평가에서 지면 참값 측지선과 가장 높은 Spearman 및 Pearson 상관관계를 달성했습니다.
  • 임베딩 수준 평가에서, EntroPath는 국소적 방법(UMAP, t-SNE)보다 전역 구조를 더 잘 보존했으며, 특히 SRW 기반 방법들이 병목 구간에서 "새어 나가는(leak)" 현상이 발생하는 희소 영역에서 다른 확산 방법들보다 우수한 신뢰성(trustworthiness)과 연속성(continuity)을 보여주었습니다.

• 단일 세포 데이터:

  • EntroPath는 DEMaP(매니폴드 보존) 및 신뢰성 지표에서 PHATE, HeatGeo, DTNE와 대등하거나 능가하는 성능을 보였습니다.
  • 비균일한 샘플링과 잘 분리된 분기 궤적이 있는 데이터셋에서 특히 강력한 강건성을 입증하였으며, 세포 상태들을 밀집된 클러스터로 뭉개지 않고 분리된 상태를 유지했습니다.
  • 대규모 Arabidopsis root atlas ($1.1 \times 10^5$ cells) 데이터셋에서, EntroPath는 랜드마크 및 적응형 커널 전략을 활용하여 하드-$k$NN 방식에 필요한 조밀한 그래프 거듭제곱의 계산 비용을 피하면서 약 15초 만에 DTNE와 대등한 기하학적 충실도를 달 Ach성했습니다.

5. 의의 및 주장

본 논문은 EntroPath가 국소 차수 정규화(SRW에서 확산을 편향시키는 요인)와 전역 측지선 복구(최단 경로 방법에서 취약한 요인) 사이의 긴장에 대한 원칙적인 해결책을 제공한다고 주장합니다.

• 샘플링 밀도에 대한 강건성: MERW를 활용함으로써, EntroPath는 저차수 병목 구간을 쉬운 통로가 아닌 높은 에너지 장벽으로 취급합니다. 이는 희소하게 샘플링된 가지의 분리를 보존하고, SRW 기반 임베딩에서 흔히 나타나는 전역 기하 구조의 "붕괴"를 방지합니다.
• 이론적 보장: 제곱 측지선 거리로의 수렴은 엄격한 기하학적 토대를 제공하며, 이는 휴리스틱한 확산 거리와 차별화됩니다.
• 실용적 유용성: EntroPath는 자동화된 깊이 선택(automatic depth selection)을 사용하는 파라미터가 가벼운 확장 가능한 접근 방식을 제공하며, 다양한 데이터 영역(합성 벤치마크부터 복잡한 생물학적 궤적까지)에서 경쟁력 있는 성능을 보여줍니다.

저자들은 엔트로피 기반 깊이 선택이 매우 짧은 가지에서는 노이즈가 발생할 수 있다는 한계를 언급하며, 향로 연구로서 연속 시간 공식화(continuous-time formulations) 및 유향 친화도(directed affinities, 예: RNA velocity) 처리를 제안했습니다.