# kNN 그래프: 가까운 이웃 찾기

> 관측치×특징 행렬에서 각 점의 가장 가까운 이웃 k개를 연결해 그래프로 바꾸는 k-nearest-neighbour graph의 입력, 계산, 출력과 싱글셀 분석에서 군집·UMAP·궤적 분석의 공통 입력이 되는 이유를 설명한다.

**kNN 그래프**(k-nearest-neighbour graph, k-최근접 이웃 그래프)는 **숫자 벡터로 표현된 관측치마다 가장 가까운 이웃 k개를 찾아 선으로 연결한 그래프**입니다. 입력은 관측치×특징 행렬이고, 출력은 관측치를 node, 가까운 관계를 edge로 가진 희소 인접 행렬입니다.

싱글셀 RNA-seq 분석에서는 세포×PCA 좌표 행렬에서 kNN 그래프를 만듭니다. 이 그래프 하나가 [Leiden 군집화](/reference/clustering-methods/), [UMAP](/reference/dimension-reduction-methods/#umap-이웃-그래프를-2차원-평면에-펼친다), [Diffusion Map](/reference/dimension-reduction-methods/#diffusion-map-그래프-위를-걷는-random-walk로-좌표를-만든다), [PAGA](/reference/trajectory-methods/)의 공통 입력이 되므로, 뒤 단계 결과가 이상하면 먼저 이 그래프가 어떻게 만들어졌는지 확인합니다.

## 어떤 문제를 풀 때 쓰는가

세포 30,000개가 각각 유전자 2,000개의 발현값을 가진 행렬이 있다고 해봅시다. 이 행렬에서 "어떤 세포들이 서로 비슷한가"를 알고 싶지만, 30,000 × 30,000개의 모든 세포 쌍 거리를 저장하면 9억 칸이 됩니다. 대부분의 쌍은 전혀 비슷하지 않으므로 그 거리를 들고 있을 이유가 없습니다.

kNN 그래프는 각 세포에서 가장 가까운 k개(보통 10~30개)만 남깁니다. 세포 30,000개 × 이웃 15개면 edge가 45만 개뿐이라 메모리에 가볍게 올라가고, "비슷한 세포끼리 연결된 네트워크"라는 형태로 바뀌어 그래프 알고리즘을 바로 적용할 수 있습니다.

아래는 같은 과정을 점 10개로 줄인 것입니다. k를 늘리면 점마다 가까운 순서대로 edge가 추가됩니다.



| 뒤 단계 | kNN 그래프를 어떻게 쓰는가 |
| --- | --- |
| Leiden·Louvain 군집화 | edge가 촘촘한 node 묶음을 찾는다 |
| UMAP | edge로 연결된 점은 가깝게, 아닌 점은 멀게 2차원에 배치한다 |
| Diffusion Map·pseudotime | edge를 따라 걷는 random walk로 세포 사이 거리를 다시 정의한다 |
| PAGA | 군집 사이에 edge가 얼마나 많은지 세어 군집 연결 지도를 만든다 |

## 입력: 관측치×특징 행렬과 k

입력은 행이 관측치, 열이 숫자 특징인 행렬입니다. 설명을 위한 가상 데이터로 2차원 점 5개를 생각해 봅시다.

| point | x | y |
| --- | ---: | ---: |
| `A` | 0 | 0 |
| `B` | 1 | 0 |
| `C` | 0 | 1 |
| `D` | 5 | 5 |
| `E` | 6 | 5 |

여기에 결정할 것이 세 가지 있습니다.

- **k**: 각 점이 몇 개의 이웃과 연결될지. 작으면 그래프가 잘게 끊기고, 크면 작은 집단이 큰 집단에 묻힙니다.
- **거리 척도**: 보통 Euclidean distance입니다. 방향만 중요하면 cosine distance를 쓰기도 합니다.
- **어떤 좌표에서 거리를 재는가**: 원래 특징 공간인지, [PCA](/reference/pca/)로 줄인 공간인지.

싱글셀에서는 원래 유전자 공간이 아니라 PCA로 줄인 30~50차원 좌표를 입력으로 씁니다. 수천 개 유전자 각각의 측정 잡음이 거리를 지배하는 것을 막고 계산도 빨라집니다.

## 어떻게 계산하는가

점마다 다른 모든 점과의 거리를 구한 뒤 가장 작은 k개를 고릅니다. 위 표에서 k = 2이면 결과는 다음 인접 리스트입니다.

```text
A -> B, C
B -> A, C
C -> A, B
D -> E, A      # D에서 두 번째로 가까운 점은 멀리 있는 A
E -> D, A
```

여기서 두 가지를 볼 수 있습니다.

1. **방향이 있다.** D는 A를 이웃으로 골랐지만 A는 D를 고르지 않았습니다. 대부분의 도구는 `A -> D`와 `D -> A` 중 하나라도 있으면 edge를 두는 식으로 **대칭화**해 무방향 그래프를 만듭니다.
2. **k는 항상 채워진다.** D와 E처럼 외딴 점도 k개의 이웃을 억지로 갖습니다. 그래서 떨어진 두 집단 사이에도 가느다란 edge가 생길 수 있고, 뒤 단계에서 이 edge를 끊는 기준이 필요해집니다.

관측치가 수십만 개가 되면 모든 쌍의 거리를 계산하는 brute force는 느립니다. 그래서 실제 도구는 **근사 최근접 이웃**(approximate nearest neighbour, ANN) 알고리즘을 씁니다. Scanpy는 기본적으로 `pynndescent`를, Seurat는 `annoy`를 사용하며, 정확한 k개 중 일부가 빠질 수 있지만 큰 구조에는 영향이 거의 없습니다.

## 출력: 희소 인접 행렬 두 개

출력은 관측치 × 관측치 크기의 **희소 행렬**입니다. 각 행에 0이 아닌 값이 k개 정도만 있습니다. Scanpy는 두 가지를 저장합니다.

| 저장 위치 | 값 | 쓰임 |
| --- | --- | --- |
| `adata.obsp['distances']` | 이웃까지의 실제 거리 | 거리가 필요한 분석 |
| `adata.obsp['connectivities']` | 0~1 사이 연결 강도(가까울수록 큼) | Leiden, UMAP, PAGA 입력 |

앞에서 본 점 10개로 `distances` 행렬을 만들면 다음과 같습니다. k를 바꾸면 그래프와 행렬이 함께 바뀝니다.



`connectivities`는 거리를 그대로 뒤집은 값이 아닙니다. UMAP 논문의 방식으로 각 점 주변의 밀도에 맞춰 거리를 다시 스케일한 뒤, 양쪽 방향의 값을 합쳐 대칭으로 만든 **가중치**입니다. 밀집한 영역과 성긴 영역 모두에서 "가장 가까운 이웃은 1에 가까운 값"을 받도록 보정된 결과라고 이해하면 됩니다.

`adata.uns['neighbors']`에는 k, 거리 척도, 사용한 좌표 같은 파라미터가 기록됩니다.

## 사례: 싱글셀 분석에 적용하면

정규화와 PCA를 마친 AnnData 객체에서 그래프를 만드는 호출은 한 줄입니다.

```python
import scanpy as sc

sc.pp.neighbors(
    adata,
    n_neighbors=15,     # k
    n_pcs=30,           # PCA 상위 30개 축에서 거리를 잰다
    use_rep='X_pca',    # adata.obsm['X_pca']를 입력으로
    metric='euclidean',
)

adata.obsp['connectivities'].shape   # (n_cells, n_cells), 희소
adata.obsp['connectivities'].nnz     # 0이 아닌 칸 수 ≈ n_cells × k × 2 이하
```

이후 `sc.tl.leiden`, `sc.tl.umap`, `sc.tl.diffmap`, `sc.tl.paga`는 모두 이 호출이 만든 `connectivities`를 읽습니다. 그래프를 다시 만들지 않고 파라미터만 바꾸면 뒤 단계 결과도 모두 바뀌므로, k와 `n_pcs`는 분석 기록에 남깁니다.

### k를 고르는 감각

| k | 그래프 성격 | 영향 |
| ---: | --- | --- |
| 5~10 | 국소적, 잘게 끊김 | 작은 집단이 살아남지만 잡음 edge도 많음 |
| 15~30 | 일반적인 기본값 | 대부분 분석의 출발점 |
| 50 이상 | 전역적, 매끄러움 | 희귀 세포 집단이 이웃 집단에 흡수될 수 있음 |

세포 수가 수십만 개로 늘면 같은 밀도를 유지하기 위해 k를 조금 키우는 것이 일반적입니다.

## 흔한 함정

- **batch가 다른 세포끼리 연결되지 않는다.** 실험 날짜나 장비가 다르면 같은 종류의 세포가 PCA 공간에서 떨어져 있어 batch별로 그래프가 갈립니다. 이 경우 Harmony 같은 보정 좌표를 `use_rep`에 넣거나, batch를 고려해 이웃을 고르는 BBKNN을 씁니다.
- **외딴 세포도 k개 이웃을 갖는다.** doublet이나 손상된 세포가 두 집단 사이를 잇는 다리가 되어 군집이 합쳐지거나 UMAP에서 가짜 연결이 보일 수 있습니다. [QC](/reference/single-cell-qc-metrics/)를 먼저 끝냅니다.
- **그래프는 거리 척도와 전처리의 함수다.** `log1p` 정규화 여부, HVG 선택, PC 개수가 바뀌면 "이웃"의 의미가 바뀝니다. 다른 설정으로 만든 두 그래프의 군집 번호를 직접 비교하지 않습니다.
- **근사 알고리즘은 실행마다 조금 다를 수 있다.** 재현하려면 `random_state`를 고정하고 라이브러리 버전을 기록합니다.

### 공식 자료

- [Scanpy `sc.pp.neighbors` API](https://scanpy.readthedocs.io/en/stable/api/generated/scanpy.pp.neighbors.html)
- [UMAP 논문: McInnes, Healy & Melville (2018), fuzzy simplicial set 구성](https://arxiv.org/abs/1802.03426)
- [PyNNDescent 문서](https://pynndescent.readthedocs.io/)
- [BBKNN: Polański et al., *Bioinformatics* (2020)](https://academic.oup.com/bioinformatics/article/36/3/964/5545955)