🤖 machine learning

Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

이 논문은 PageRank, k-core 분해, 클러스터링 계수 분석과 같은 표준 그래프 알고리즘을 UMAP에 의해 구축된 내부 k-최근접 이웃 그래프에 적용하는 것이, 목적에 맞게 제작된 방법들과 대등하거나 이를 능가하는 경우가 많아 고차원 데이터의 의미 파악을 위한 강력하고 상호 보완적인 접근법을 제공한다는 점을 입증한다.

원저자: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

게시일 2026-07-10

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 손으로 쓴 숫자나 가방, 셔츠, 신발 같은 옷 사진이 담긴 6만 장의 거대하고 무질서한 사진 상자가 있다고 상상해 보세요. 당신은 그 패턴을 보고 싶어서, 이 3D(또는 그 이상의 고차원) 혼돈을 평평한 2D 종이 위로 압축해 주는 UMAP이라는 초스마트한 도구를 사용합니다.

보통 사람들은 거기서 멈춥니다. 그들은 예쁜 2D 산점도를 보며 점들을 가늘게 뜨고 바라보다가, "아, 저기에 가방 클러스터가 있네"라고 말하곤 하죠. 하지만 이 논문은 UMAP이 그 그림을 그리는 순간 자신의 가장 강력한 비밀 무기를 버리고 있는 것이라고 주장합니다.

UMAP이 데이터를 종이 위로 압축하기 전, 내부적으로 kNN 그래프라는 숨겨진 구조를 구축합니다. 이 그래프를 거대한, 보이지 않는 친구 관계의 그물망이라고 생각해보세요. 이 그물망 속에서 모든 사진은 자신과 가장 비슷하다고 생각하는 15명의 친구(그들의 "k-최근접 이웃")를 가집니다. 하지만 반전이 있습니다. 모든 사진이 15명의 친구를 '선택'하지만, 모든 사진이 다른 사진들로부터 15번의 '선택을 받는' 것은 아닙니다. 어떤 사진들은 너무 이상하거나 독특해서 거의 아무도 그들을 친구로 선택하지 않습니다. 반면, 어떤 사진들은 너무 "평범"하거나 "전형적"이어서 수백 명의 다른 사진들이 그들을 최고의 매치로 지목하기도 합니다.

저자들은 이렇게 말합니다. "이 그물망을 버리지 마세요! 이것이 2D 그림보다 훨씬 더 정직합니다." 그들은 이 그물망을 활용해 2D 그림보다 데이터를 더 잘 이해할 수 있는 세 가지 멋진 방법을 테스트했습니다.

1. "인기 있는 아이" (PageRank)

질문: 어떤 사진이 특정 그룹의 진정한 "대표"인가?
기존 방식: 사람들은 보통 2D 지도상의 덩어리 중심에 가장 가까운 사진을 고릅니다. 하지만 2D 지도는 왜곡되어 있습니다! 길게 늘어진 덩어리의 "중심"은 실제로는 진짜 사진처럼 보이지 않을 수도 있습니다.
새로운 방식: 저자들은 구글이 웹사이트 순위를 매길 때 사용한 것과 같은 PageRank 알고리즘을 사용했습니다. 이 그물망 속에서 어떤 사진은 단순히 많은 사람에게 선택받았기 때문만이 아니라, 다른 인기 있는 사진들로부터 선택받았기 때문에 높은 점수를 얻습니다.
결과:

상위 점수를 받은 사진들은 클래스의 완벽하고 교과서적인 예시(예: 전형적인 "6"이나 표준적인 메신저 백)처럼 보였습니다.
가장 낮은 점수를 받은 사진들은 이상하고 비전형적인 것들이었습니다.
증거: 이들은 전체 데이터셋을 대표할 200장의 사진을 뽑을 때, PageRank 방식이 기존 방식(k-medoids)보다 훨씬 더 나은 균형을 보여준다는 것을 확인했습니다. 기존 방식은 지저-분하게 퍼져 있는 그룹에서 너무 많은 사진을 계속 뽑아내는 반면, PageRank는 공정한 조합을 선택했습니다.
확신 정도는? 매우 높습니다. 그들은 6만 장의 이미지에 대해 이를 실행했으며, 친구의 수를 5명에서 100명으로 변경해도 결과가 안정적임을 발견했습니다(상관관계 약 0.95). 순위가 거의 동일하게 유지되었습니다.

2. "핵심 vs 가장자리" (k-Core Decomposition)

질문: 어떤 사진이 그룹의 "심장"이고, 어떤 사진이 그저 주변부를 맴돌고 있는가?
기존 방식: HDBSCAN 같은 도구는 "이것은 가방이다"라는 단순한 라벨을 줍니다. 하지만 그 도구는 그 가방이 전형적인 가방인지, 아니면 정의에 간신히 들어맞는 이상하고 모호한 가방인지는 알려주지 않습니다.
새로운 방식: 저자들은 k-core decomposition을 사용했습니다. 양파를 까는 것을 상상해 보세요. 가장 적은 수의 지목을 받은(가장 인기 없는) 사진들을 계속 제거해 나갑니다. 맨 중심에 남은 것들이 바로 "핵심(core)"입니다.
결과:

그들은 "핵심" 사진들이 가장 자기 유사성이 높고 일관적이라는 것을 발견했습니다. 예를 들어, 숫자 "1" 카테고리에서 핵심은 오직 완벽한 "1"들뿐이었습니다.
"가방" 카테고리에서, 핵심은 뚜렷한 하위 그룹을 드러냈습니다: 메신저 백, 웨이스트 팩, 그리고 특이한 질감의 가방들로 나뉘었습니다. 2D 지도는 그저 크고 흐릿한 "가방" 덩어리로 보여주었지만, 그래프는 그 층위들을 파헤쳐 보여주었습니다.
증거: 이들은 이를 HDBSCAN과 비교했습니다. HDBSCAN은 "이것이 가방인가?"라고 말하는 데는 훌륭했지만, "이 가방이 얼마나 중심적인가?"를 말하는 데는 서툴렀습니다. 그래프 방식은 기존 도구들이 놓친 "핵심성(coreness)"의 단계적 척도를 제공했습니다.

3. "비밀 클럽" (Clustering Coefficient)

질문: 서로 똑같이 생긴 아주 작고 촘촘한 사진 그룹이 존재하는가?
기존 방식: 2D 지도를 보면 "6"의 그룹이 하나의 크고 단단한 덩어리처럼 보일 수 있습니다.
새로운 방식: **Clustering Coefficient(클러스터링 계수)**는 그물망 속의 "삼각형"을 찾습니다. 만약 사진 A가 사진 B를 친구라고 생각하고, 사진 B가 사진 C를 친구라고 생각한다면, 사진 A도 사진 C를 친구라고 생각할까요? 만약 그렇다면, 그것은 긴밀하게 연결된 클리크(clique)입니다.
결과:

이 방법은 매우 구체적인 스타일을 공유하는 사진들의 "마이크로 네이버후드(미세 이웃)"를 찾아냈습니다. "6"의 경우, 아주 미세한 디테일에 따라 그룹을 분리했습니다: 어떤 것은 루프가 컸고, 어떤 것은 기울어져 있었으며, 어떤 것은 특정한 곡선을 가지고 있었습니다.
증거: 가장 높은 "클리크 결속력"을 가진 상위 5%의 사진들은 98%의 순도(purity)를 보였습니다(즉, 그들의 이웃 중 거의 대부분이 동일한 유형임). 이는 무작위로 사진을 뽑는 것보다 훨씬 높은 수치입니다.

결론

이 논문은 2D 그림이 쓸모없다고 말하는 것이 아닙니다. 단지 불완전하다고 말할 뿐입니다. 숨겨진 친구 관계의 그물망(kNN 그래프)을 유지하고 그 위에 표준적인 그래프 알고리즘을 실행하면, 여러분의 데이터에 대해 훨씬 더 명확하고 정직한 관점을 얻을 수 있습니다.

얼마나 확신하는가?
그들은 6만 장의 이미지가 담긴 두 개의 거대한 표준 데이터셋(MNIST 및 Fashion MNIST)을 통해 이를 테스트했습니다. 결과는 빨랐으며(노트북에서 1초 미만으로 실행), 수학적 결과 또한 기존의 최고 도구들과 견줄 만했습니다. 그들은 이 접근 방식이 다른 유사한 도구들에도 작동할 것이라고 제안하지만, 오직 이 특정 이미지 세트들에 대해서만 증명했을 뿐입니다. 그들이 모든 데이터 문제를 해결한다고 주장하는 것은 아니지만, 단순히 2D 점들을 응시하는 것보다 훨씬 더 나은 "의미 형성(sensemaking)" 방법이라는 점에는 꽤 확신을 가지고 있습니다.

기술 요약: 차원 축소와 네트워크 과학의 만남

문제 정의

UMAP은 고차원 데이터 시각화를 위한 지배적인 도구이지만, 일반적인 분석 워크플로우는 결과물인 2D 산점도를 유일한 관심 대상으로 취급하는 경면이 있습니다. 이러한 접근 방식은 UMAP이 투영(projection) 전 내부에 구축하는 풍부하고 중간 단계적인 k-최근접 이웃(kNN) 그래프를 버리는 결과를 초래합니다. 저자들은 이 그래프가 2D 레이아웃에서 필연적으로 발생하는 왜곡보다 원래의 고차원 공간에서의 데이터 매니폴드(manifold)의 국소적 기하학 및 연결성을 더 충실하게 인코딩한다고 주장합니다. 이 그래프를 무시함으로써, 분석가들은 2D 투영에서 가려지는 대표점 식별, 밀도 계층 구조 분석, 국소적 응집성 탐지와 같은 의미 파악(sensemaking) 과업을 수행할 기회를 놓치게 됩니다.

방법론

본 논문은 UMAP의 내부 kNN 그래프를 2D 임베딩이 아닌, 표준 네트워크 과학 알고리즘을 직접 적용할 수 있는 "일급 분석 자원"으로 격상할 것을 제안합니다. 이 방법론은 그래프의 특정 구조적 특성인 고정된 외차수(out-degree) $k$ , 가변적인 내차수(in-degree), 그리고 밀도 적응형 에지 가중치를 활용합니다. 세 가지 특정 알고리즘이 다음과 같이 적용됩니다:

대표점 선택을 위한 PageRank:
- 메커니즘: 왜곡된 2D 공간의 기하학적 중심점(centroid)을 기준으로 표본을 선택하는 대신, 저자들은 kNN 그래프에 PageRank를 적용합니다.
- 논리: 노드의 점수는 전이적으로 증폭됩니다. 즉, 어떤 점이 높게 평가되는 것은 단순히 많은 노드가 그 점을 가리키기 때문(높은 내차수)만이 아니라, 그 점을 가리키는 노드들 자체가 이미 높은 순위를 갖고 있기 때문입니다. 이는 매니폴드 내에서 "권위자(authority)" 역할을 하는 전역적으로 대표적인 점들을 식별합니다.
- 구현: 에지 가중치는 UMAP의 밀도 적응형 멤버십 강도에서 유도됩니다.
밀도 계층 구조를 위한 k-core 분해:
- 메커니즘: 저자들은 밀집된 코어 영역과 희소한 주변부를 구분하기 위해 그래프에 k-core 분해를 적용합니다.
- 논리: 고정된 외차수 $k$ 에 의해 제한되는 표준 차수 기반 분해와 달리, 이 방법은 **내차수(in-degree)**만을 기준으로 분해합니다. 이를 통해 노드가 점진적으로 더 조밀하고 상호 연결된 서브그래프 내에 얼마나 깊이 박혀 있는지를 나타내는 "코어성(coreness)" 점수(0, 1, 2...)를 생성합니다.
- 목표: 이산적인 클러스터 레이블(예: HDBSCAN)이 포착할 수 없는 점진적인 서브그래프 계층 구조와 클러스터 내의 하위 범주를 드러내는 것입니다.
국소적 응집성을 위한 클러스터링 계수(Clustering Coefficient):
- 메커니즘: 각 노드에 대해 클러스터링 계수(CC)를 계산하여, 해당 노드의 이웃들이 서로 얼마나 연결되어 있는지 측정합니다.
- 논리: 높은 CC는 점들이 서로를 최근접 이웃으로 간다는 것을 상호 확인하는 "긴밀하게 연결된" 미세 이웃(micro-neighborhood)을 나타냅니다.
- 목표: 2D 투영에서는 단일한 덩어리로 보일 수 있는 (예: 특정 필기 스타일) 의미론적으로 일관된 미세 클러스터를 탐지합니다.

주요 기여

본 논문은 두 가지 주요 기여를 합니다:

개념적 전환: UMAP의 버려진 kNN 그래프를 주요 자원으로 취급함으로써 차원 축소와 네트워크 과학을 연결합니다. 이를 통해 2D 산점도를 보완하며, 특히 대표성, 밀도 구조, 국소적 응집성 문제를 해결하는 의미 파악을 가능하게 합니다.
경험적 검증: MNIST 및 Fashion MNIST에 대한 정량적 및 정성적 평가를 통해, 저자들은 이 그래프 기반 방법들이 목적 기반 방법들보다 경쟁력이 있거나 우수함을 입증했습니다:
- PageRank vs. k-medoids: PageRank로 선택된 점들은 k-medoids(분산이 큰 클래스에서 과다 선택하는 경향이 있음)에 비해 우수한 클래스 균형(낮은 Jensen-Shannon 발산)을 달ей합니다. 매우 작은 예산(budget)에서는 k-medoids가 대표성 측면에서 약간 앞서지만, PageRank는 빠르게 따라잡으며 다운스트림 SVM 분류 정확도에서도 경쟁력을 유지합니다. 결정적으로, k-medoids는 모든 예산 크기에 대해 매번 다시 실행해야 하는 반면, PageRank는 단 한 번의 전역 순위 계산만 필요합니다.
- k-Core vs. HDBSCAN: HDBSCAN이 이산적인 클러스터 레이블을 할당하는 반면, k-core 분해는 클러스터 내의 점진적인 계층 구조를 보여줍니다. HDBSCAN의 멤버십 확률은 코어성(coreness)과 거의 상관관계가 없었으며, 이는 두 방법이 서로 다른 질문(그룹 멤버십 vs. 그룹 내 위치)에 답한다는 것을 확인시켜 줍니다.
- 클러스터링 계수: CC는 위상적으로 응집되어 있지만 2D에서는 시각적으로 구분이 불가능할 수 있는 독특한 미세 이웃(예: 숫자 "6"의 특정 필기 스타일)을 식별합니다.

결과

안정성: PageRank 순위는 이웃 크기( $k=5$ 에서 $100$)의 20배 범위에 걸쳐 매우 안정적이며, 평균 Spearman 순위 상관관계가 ~0.95에 달합니다. 이는 선택된 대표점들이 특정 $k$ 값의 산물이 아님을 나타냅니다.
성능:
- 대표성: PageRank는 가장 가까운 대표점까지의 평균 코사인 거리에 있어, 예산이 증가함에 따라 k-medoids와 대등한 성능을 보입니다.
- 클래스 균형: PageRank는 (특히 예산 $s \ge 200$ 에서) 전역 클래스 분포를 유지하는 데 있어 k-medoids보다 현저히 뛰어난 성능(낮은 JSD)을 보입니다.
- 다운스트림 유용성: PageRank로 선택된 표본으로 학습된 SVM 분류기는 Fashion MNIST에서 k-medoids와 2~3% 이내의 오차를 보이며, MNIST에서도 대등한 정확도를 달in합니다.
- 구조적 통찰: k-core 분해는 특정 코어성 임계값을 필터링함으로써 하위 범주(예: "가방" 클래스 내의 메신저 백 vs. 웨이스트 팩)를 성공적으로 분리합니다. 높은 CC 값은 숫자 "6" 클러스터 내의 일관된 필기 스타일을 고립시킵니다.

의의 및 주장

저자들은 본 연구가 UMAP의 내부 표현이 가진 미개척 잠재력을 입증한다고 주장합니다. kNN 그래프를 유지하고 분석함으로써, 분석가는 2D 투영에서 손실되거나 왜곡되는 구조적 정보(중심성, 연결 계층, 국소적 응집성)에 접근할 수 있습니다.

본 논문은 이러한 그래프 알고리즘을 기존 도구의 대체제가 아닌, 다음과 같은 뚜렷한 장점을 제공하는 보완적 방법론으로 배치합니다:

거리 목적 함수를 최적화할 필요 없이 대표점을 선택하는 파라미터 프리(parameter-free)(또는 안정적인) 방식을 제공합니다.
이산적인 클러스터 할당 대신 밀도의 연속적인 계층 구조(k-core를 통해)를 제공합니다.
UMAP의 사전 계산된 이웃 배열을 재사용함으로써 60,000개의 포인트에 대해 1초 미만으로 실행될 만큼 계산 효율적입니다.

저자들은 결론적으로 이러한 관점이 커뮤니티로 하여금 "산점도를 넘어, 그것을 만든 그래프를 들여다보라"고 권고하며, 이 접근 방식이 kNN 그래프를 구축하는 다른 차원 축소 방법론(예: TriMap, PaCMAP)에도 자연스럽게 확장될 수 있음을 시사합니다.