AdaGraph: A Graph-Native Clustering Algorithm That Overcomes the Curse of Dimensionality and Enables Scientific Discovery

We present AdaGraph, a graph-native clustering algorithm born from the Structure-Centric Machine Learning (SC-ML) paradigm -- a new field of unsupervised learning that replaces geometry-centric (distance-based) computation with structure-centric (topology-based) computation, fundamentally dissolving the curse of dimensionality. AdaGraph operates entirely within the kNN graph topology, a representation that retains meaningful relational structure in arbitrarily high dimensions where Euclidean distance metrics become uninformative. AdaGraph requires no a priori specification of the number of clusters k, handles noise natively, and scales via the SLCD (Sample-Learn-Calibrate-Deploy) prototype-deployment framework. As its unsupervised tuning objective, AdaGraph pairs with Graph-SCOPE, the topology-based cluster validity index introduced as a separate SC-ML contribution. On 10 synthetic benchmarks spanning d=10 to d=5000, Graph-SCOPE achieves mean ARI=0.900 and correctly selects k on 9/10 datasets -- outperforming Silhouette, Davies-Bouldin, and Calinski-Harabasz -- while maintaining Kendall tau >= 0.92 with ground-truth cluster quality across all dimensionalities (Silhouette: tau ~= 0.46). We validate AdaGraph across three scientific domains: (1) gene co-expression discovery in hepatocellular carcinoma (GSE14520, 10,000 genes, 488 patients, no dimensionality reduction), where AdaGraph identifies condition-specific gene modules that WGCNA, ICA, NMF, and Spectral Biclustering fail to resolve; (2) natural language text clustering, where AdaGraph achieves ARI=0.751 on 20NG-6cat versus HDBSCAN's 0.464 (62% relative improvement); (3) materials science clustering of superconductors (145-dimensional Magpie features), perovskites, and JARVIS-DFT materials, where AdaGraph achieves the highest Graph-SCOPE on all three datasets.

📋 한 줄 요약

**[비지도 학습 / 그래프 클러스터링]** 거리 대신 토폴로지로 동작하여 차원의 저주를 극복하는 그래프 네이티브 클러스터링 알고리즘 AdaGraph와 그래프 기반 검증 지수 Graph-SCOPE를 제안했다.

🎯 핵심 기여도

거리(geometry) 중심에서 토폴로지(structure) 중심 비지도 학습으로 패러다임 전환을 표방하는 SC-ML 프레임워크 제시
클러스터 수 $k$ 사전 지정 불필요, 노이즈 네이티브 처리, kNN 그래프 위에서만 동작하는 AdaGraph 제안
Silhouette/DB/CH의 한계를 보완하는 토폴로지 기반 클러스터 검증 지수 Graph-SCOPE 도입
유전체학·자연어·재료과학 세 영역에서 실제 과학 발견 사례로 검증

💡 핵심 아이디어

고차원에서 유클리드 거리는 의미를 잃지만 kNN 그래프의 관계 구조는 유지된다. 따라서 거리 기반 계산을 토폴로지 기반 계산으로 대체하면 차원의 저주가 본질적으로 해소된다. 동시에 클러스터 검증 또한 거리 기반 지수(Silhouette 등) 대신 토폴로지 기반 Graph-SCOPE를 쓰면 고차원에서도 신뢰성 있는 $k$ 선택과 품질 측정이 가능하다.

🔬 기술적 접근법

kNN 그래프 토폴로지 안에서만 동작하는 AdaGraph
Graph-SCOPE: 토폴로지 기반 cluster validity index, AdaGraph의 비지도 튜닝 목적함수로 페어링
SLCD(Sample-Learn-Calibrate-Deploy) 프로토타입–배포 프레임워크로 확장성 확보
차원 축소 없이 원본 고차원 공간에서 직접 클러스터링

📊 주요 결과

10개 합성 벤치마크 ($d=10$ ~ $d=5000$): Graph-SCOPE 평균 ARI=0.900, 10개 중 9개에서 정확한 $k$ 선택
모든 차원에서 Kendall tau ≥ 0.92 (Silhouette은 ~0.46)
간암 유전자 공발현(GSE14520, 10,000 genes, 488 patients): WGCNA/ICA/NMF/Spectral Biclustering이 풀지 못한 조건 특이 모듈 발견
20NG-6cat 텍스트 클러스터링: ARI 0.751 (HDBSCAN 0.464, 62% 상대 개선)
초전도체(Magpie 145D), 페로브스카이트, JARVIS-DFT 재료에서 모두 최고 Graph-SCOPE

💭 의의 및 한계

"차원의 저주를 알고리즘적으로 우회"하는 명확한 동기와, 합성·생물·언어·재료 네 영역에 걸친 검증이 강력하다. 다만 kNN 그래프 구성 비용·하이퍼파라미터 민감도, 매우 큰 $N$에서의 확장성, 그리고 SC-ML 프레임워크가 다른 비지도 과제(차원 축소, 이상 탐지)에도 일반화되는지는 추가 연구가 필요하다.

🚀 실용적 활용

유전체 모듈 발굴, 재료 설계 후보 탐색, 고차원 임베딩 기반 문서 클러스터링, 단일세포 RNA-seq 등 "차원이 크고 $k$를 모른다"는 전형적 과학 데이터 분석 시나리오에 바로 적용 가능하다.