ANN 방법론중 하나인 HNSW 알고리즘 정리

NSW (Navigable Small World Graphs)
Skip List
HNSW
- Search
- Construction
Parameters
References

HNSW(Hierarchical Navigable Small World Graphs) 는 이름 그대로 계층적이지만 서로 이동 가능한, 여러 Small World를 만들어 그 안에서 근접 이웃을 탐색하는 방법이다.

빠른 검색 결과 및 높은 정확도라는 장점을 제공하지만 메모리 사용량이 높은 단점이 있다.

HNSW는 NSW에 skip list의 개념을 적용하여, NSW 그래프를 계층화한다. 가장 아래의 레이어는 모든 노드를 포함하며, 위로 갈수록 더 적은 노드로 구성된 형태의 그래프로 구성된다.

NSW (Navigable Small World Graphs)

우선 계층(Hierarchical)을 고려하기 전에 NSW(Navigable Small World Graphs) 를 먼저 생각해보자.

NSW 에서는 검색 과정에서 임의로 선택된(또는 미리 정의된) 진입 노드(entry point)에서 시작하여 query 노드와 가까운 노드를 찾을때까지 진행하는데, 계속 찾는것은 아니고 일정 수준까지만 탐색을 수행한다.

Small world 이론을 바탕으로, 적은 단계의 탐색만 거쳐도 충분히 쿼리와 근사한 노드를 반환할 수 있다는 가정이 깔려있다.

이렇게 탐색의 정도를 제한하기 때문에, 데이터의 양이 많아져도 빠른 인덱싱 및 검색이 가능하다.

Skip List

Skip list는 linked list 와 binary tree 자료 구조에 영감을 얻어서 만들어진 확률 기반 계층적(hierarchical) 자료 구조다.

Skip list의 가장 하위 레벨의 층은 모든 데이터 노드를 포함하며, 상위 레벨의 층으로 갈수록 더 적은 수의 노드를 가진 linked list로 구성된다. 검색에 사용되는 링크는 다음 노드로 이어지는 기본 링크와 다른 레벨의 노드로 이어지는 링크로 구성된다.

이러한 링크 구조는 전체 구조를 가로지르며 데이터를 빠르게 탐색할 수 있는 경로를 형성하는데, 검색, 삭제, 삽입 연산은 log 복잡도를 가진다.

왜 확률적인 자료 구조로 불리는가? 그 이유는 새로운 노드를 삽입할때의 level 을 랜덤으로 정하기 때문이다.

HNSW

HNSW는 skip list 구조를 채용하여 NSW 에 계층구조 형식을 추가한 것이다.

Search

검색 과정에서는 가장 위쪽 레이어에 있는 노드부터 시작하는데, 일반적으로 진입 노드들은 더 높은 차수의 노드(=여러 레이어에 걸쳐 있는 링크를 가진 노드)로 설정하는 편이다.

각 레이어에서 탐욕적으로 가장 가까운 정점으로 이동하여 local minimum(query 와 가장 가까운 노드) 을 찾는다. 그리고 이 시점에서 하위 레이어로 이동하여 다시 검색을 시작한다. 이 과정을 반복하여 최하위 레이어(레이어 0)의 로컬 최소값을 찾을 때까지 진행한다.

이렇게 찾은 노드들은 최종적으로 쿼리와 가장 가까운 노드가 된다.

Construction

그래프 구성도 상위 레이어에서 시작된다. 어떤 레이어에 주어진 노드를 넣을지는 특정 확률 값으로 결정되는데, 일반적으로 level 이 낮을수록 높은 확률을 가진다.

처음 해야할일은 query 와 가장 가까운 (local minimum) ef(efConstruction)개의 노드를 찾는것이다. 그리고 하위 레이어로 내려가서 똑같은 과정을 반복하고, 랜덤으로 선택된 레벨에 도달할때까지 반복한다.

이후 각 레이어에서 찾은 ef개의 노드들은 신규 노드에 대한 이웃으로 추가되는데, 다 추가되는것은 아니고 M개만 추가된다. 단순한 기준은 노드들의 거리가 가까운 순서대로 추가하는것이다.

이렇게 정해진 레이어로 내려가면서 노드들을 추가하는 과정을 반복하여 타겟 노드에 이웃을 추가해주면 그래프 구성은 완료된다.

Parameters

HNSW의 벡터 인덱싱 및 검색에는 몇 가지 파라미터를 설정해주어야 하는데, 이러한 파라미터와 그 의미는 다음과 같다.

$M$: 각 노드가 가질 수 있는 최대 이웃의 수를 나타낸다. $M$ 값이 높아지면 검색 정확도가 향상될 수 있지만, 그만큼 메모리 사용량과 인덱스 생성 시간이 증가한다.
$\text{efConstruction}$: 인덱스를 생성할 때 탐색 크기를 의미한다. 이 값이 높을수록 더 깊고 정확한 탐색이 가능해져 인덱스 품질이 향상되지만, 인덱스 생성 시간이 길어질 수 있다.
$\text{efSearch}$: 검색 시 탐색 크기를 의미한다. 이 값이 높을수록 더 깊고 정확한 탐색이 가능해져 검색 정확도가 향상되지만, **검색 시간이 늘어날 수 있다.
$L_{max}$: 노드가 가질 수 있는 최대 레벨을 정의한다. 일반적으로 자동으로 설정되지만, 필요에 따라 사용자가 직접 지정할 수도 있다. $L_{max}$는 그래프의 계층적 구조와 깊이에 영향을 미친다.