EmbedOR: Provable Cluster-Preserving Visualizations with Curvature-Based Stochastic Neighbor Embeddings

기술 요약: EmbedOR: 곡률 기반 확률적 이웃 임베딩을 통한 증명 가능한 클러스터 보존 시각화

문제 정의

t-SNE 및 UMAP과 같은 확률적 이웃 임베딩(Stochastic Neighbor Embedding, SNE) 알고리즘은 고차원 데이터 시각화에 널리 사용된다. 그러나 이러한 방법들은 기하학적 구조 보존 측면에서 중대한 이론적 및 실무적 한계를 지닌다. 구체적으로, 이 방법들은 다음과 같은 이유로 노이즈가 있는 고차원 데이터의 기저 기하학적 구조를 복원하는 데 실패한다:

1. 클러스터 식별 실패: 데이터가 클러스터링하기 용이한 상태임에도 불구하고 클러스터를 제대로 찾아내지 못함.
2. 파편화(Fragmentation) 유발: 데이터 하부 매니폴드(submanifold)의 연결된 구성 요소들을 시각화 과정에서 부당하게 분리함.

기존의 t-SNE에 대한 이론적 보증은 매우 엄격한 데이터 가정(예: 구형이며 잘 분리된 클러스터)에 국한되어 있으며, UMAP에 대해서는 유의미한 이론적 결과가 존재하지 않는다. 또한, 실증적 연구에 따르면 표준 구현 방식들이 이러한 가정들을 위반하여 최적화되지 않은 시각화를 초래하는 경우가 빈번하다.

방법론

저자들은 **Ollivier-Ricci 곡률(ORC)**을 통합하여 클러스터를 강화하는 거리 메트릭을 구축하는 새로운 SNE 알고리즘인 EmbedOR를 제안한다. 이 방법론은 두 단계로 진행된다:

1. 곡률 기반 메트릭 학습 ($\Delta_E$):

   • 알고리즘은 데이터로부터 최근접 이웃 그래프(nearest-neighbor graph)를 구축한다.
   • 그래프의 각 에지(edge)에 대해 ORC를 계산한다. ORC는 국소적 연결성을 정량화하며, 양(+)의 곡률은 고도로 연결된 커뮤니티 내의 에지를 나타내고, 음(-)의 곡률은 "병목(bottleneck)" 또는 서로 떨어진 클러스터를 잇는 에지를 나타낸다.
   • 곡률 $\kappa$에 기반한 에너지 함수 $E(\kappa; p)$를 정의한다. 이 함수는 음의 곡률을 가진 에지에는 높은 "에너지(패널티)"를 부여하고, 양의 곡률을 가진 에지에는 낮은 에너지를 부여한다.
   • 새로운 쌍별 거리 메트릭 $\Delta_E$는 가중치 그래프에서의 최단 경로 거리로 계산되며, 여기서 에지 가중치는 유클리드 거리와 곡률 기반 에너지 함수의 곱이다. 이 메트릭은 경로가 양의 곡률 에지(클러스터 내부)를 통과하도록 유도하고, 음의 곡률 에지(클러스터 사이)는 피하도록 한다.

2. 커스텀 확률적 이웃 임베딩:

   • EmbedOR는 t-SNE와 UMAP의 요소를 혼합한 커스텀 SNE 프레임워크를 활용한다.
   • 고차원 친화도($p_{ij}$): 유클리드 거리를 사용하는 표준 t-SNE와 달리, EmbedOR는 $\Delta_E$ 메트릭을 사용하여 친화도를 계산한다.
   • 최적화: 알고리즘은 고차원 친화도(Student t-분포로 모델링됨)와 저차원 친화도 사이의 "퍼지 교차 엔트로피(fuzzy cross-entropy)" 손실을 최소화한다. 최적화에는 SGD(확률적 경사 하강법)를 사용하며, t-SNE의 퍼플렉시티(perplexity) 기반 유사도 계산 방식을 유지하면서도 UMAP의 계산 효율성(저차원 친화도의 재정규화 회피)을 활용한다.

주요 기여

1. 이론적 확장: 저자들은 EmbedOR 거리 메트릭이 t-SNE의 이론적 일관성 결과(기존에는 구형이고 잘 분리된 데이터에만 국한되었던 것)를 훨씬 더 넓은 범주의 데이터셋으로 확장함을 증명한다. 구체적으로, 노이즈가 있는 매니폴드 모델 하에서 다음을 보여준다:
   • $\Delta_E$ 하에서의 클러스터 내부 거리는 매니폴드 측지선(geodesic) 거리에 수렴한다.
   • 클러스터 간 거리는 반발 파라미터 $p$에 따라 증가하는 하한값을 갖는다.
   • 결과적으로, 충분히 큰 $p$에 대해 데이터는 t-SNE가 클러스터 보존 시각화를 생성하는 데 필요한 조건을 충족하게 된다.
2. 알고리즘 혁신: 이산 그래프 곡률을 사용하여 파편화를 유발하지 않으면서 기저의 클러스터 구조를 강조하는 거리 메트릭을 만드는 EmbedOR를 제안한다.
3. 진단 도구: EmbedOR 메트릭이 기존 시각화를 주석 처리(annotate)하는 사후(post-hoc) 도구로 사용될 수 있음을 입증한다. $\Delta_E$ 거리가 짧은 에지를 시각화함으로써, 사용자는 파편화(즉, $\Delta_E$에서는 가깝지만 임베딩에서는 멀리 떨어진 경우)를 식별하여 기저의 기하학적 구조에 대한 통찰을 얻을 수 있다.

실험 결과

저자들은 MNIST, Fashion-MNIST, 다양한 단일 세포 RNA 시퀀싱(scRNA-seq) 데이터셋을 포함한 합성 및 실제 데이터셋에 대해 t-SNE, UMAP, PHATE, Isomap, Laplacian Eigenmaps와 같은 베이스라인 모델들과 함께 EmbedOR를 평가하였다.

• 합성 데이터: EmbedOR는 연결된 구성 요소들을 분리하는 동시에 연속적인 경로의 파편화를 방지하는 데 있어 일관되게 우수하거나 최고 수준의 성능을 보였다. UMAP은 종종 파편화를 유발하고 t-SNE는 Swiss Roll과 같은 구조를 펼치는 데 실패한 반면, EmbedOR는 위상적 무결성(topological integrity)을 유지했다.
• 실제 데이터 (scRNA-seq): 발달 궤적(developmental trajectory) 및 세포 유형 데이터셋에서 EmbedOR는 UMAP 및 t-SNE에 비해 궤적의 연속성과 세포 유형의 분리도를 더 잘 보존하였다.
• 파편화 분석: Spearman 상관계수와 z-점수화된 에지 길이를 사용한 정량적 분석 결과, EmbedOR는 $\Delta_E$에 의해 가깝다고 판단된 지점들 사이의 거리를 최소한으로 확장함을 확인했다. 반면, UMAP과 t-SNE는 이러한 거리를 유의미하게 확장하여 파편화를 나타냈다.
• 메트릭의 유용성: 실험을 통해 짧은 $\Delta_E$ 에지가 표준 k-NN 그래프의 에지보다 실제 정답 클러스터(또는 세포 유형) 내의 지점들을 연결할 가능성이 현저히 높음을 확인하였으며, 이는 다른 임베딩에서 발생하는 파편화를 탐지하는 메트릭으로서의 능력을 검증한다.

의의 및 주장

본 논문은 EmbedOR가 클러스터 구조를 강조하는 것과 데이터 매니폴드의 연속성을 보존하는 것 사이에서 "섬세한 균형"을 달 achieves 하며, 이는 테스트된 베이스라인 방법들에서는 관찰되지 않는 특성이라고 주장한다.

• 이론적 의의: 본 연구는 곡률 기반 메트릭을 사용하여 SNE 수렴에 필요한 엄격한 가정을 완화함으로써, 증명 가능한 클러스터 보존의 적용 범위를 넓히는 최초의 이론적 근거를 제공한다.
• 실무적 의의: EmbedOR는 연결된 구성 요소의 무결성을 유지하는 것이 중요한 경우(예: 단일 세포 유전체학) 노이즈가 있는 고차원 데이터를 시각화하기 위한 강력한 대안을 제공한다.
• 진단적 가치: 저자들은 EmbedOR 메트릭이 두 가지 목적을 수행한다고 강조한다. 즉, 알고리즘의 핵심 거리 메트릭 역할을 하는 동시에, 다른 방법으로 생성된 시각화에서 파편화를 식별하고 해석하는 진단 도구로서 기능한다.

저자들은 이론적 범위에 대해 겸허한 태도를 유지하며, 수렴 결과가 특정 t-SNE 인스턴스에 의존하고 커스텀 알고리즘이 UMAP과 t-SNE의 요소를 혼합하고 있다는 점을 언급했다. 그러나 $\Delta_E$ 메트릭에 관한 이론적 통찰이 실제 효과에 대한 강력한 동기를 제공한다고 주장한다.