HNSW = Hierarchical Navigable Small World Graphs

1. Hierarchical

• hnsw 알고리즘에서 검색을 진행하는 방식은 위의 그림과 같다
• 빨간 점이 검색 시작점이고 초록색이 검색 결과라고 생각하면
• 현재 계층에서 검색 결과에 가장 가까운 위치로 이동한 뒤, 다음 계층으로 내려가 동일한 탐색을 반복한다

2. Small World

• 해당 개념은 '케빈 베이컨의 6단계 법칙'과 유사하다.
  

• 출연 영화를 기준으로 여섯 다리만 거치면 전세계 (거의) 모든 배우와 연결될 수 있다는 이야기다.

• 첫번째 그림은 균일하게 연결된 그래프이고 가장 마지막 그림은 완전 랜덤하게 연결된 그래프로 우측으로 갈수록 불규칙성이 커진다.
• 이때, 균일하게 연결된 그래프에서 특정 지점을 기준으로 다른 지점으로 이동할 경우 떨어진 거리만큼의 이동이 필요한 반면, 아주 적은 수의 연결을 끊고 이를 랜덤하게 연결할 경우 그 이동의 수가 확연하게 줄어든다는 것을 알 수 있다.
• 이처럼 균일하게 연결된 네트워크에서 일부 연결이 끊기고 다시 랜덤하게 연결된 네트워크를 small-world라고 한다. 이러한 네트워크에서 특정 노드로의 연결에 필요한 이동의 수가 급격히 줄어드는 것에서 착안한 알고리즘이 hnsw라고 할 수 있다.

3. Graphs

• 검색하고자 하는 대상에 대해 그래프를 제작해야하는 특징을 가지고 있다.
• 검색 대상을 임베딩화하여 그래프로 제작할 때,
  • 고차원의 그래프를 그리게 된다면 하나의 레이어에서 가장 가까운 위치로 이동할 경우 local minimum에 빠지게 될 위험이 있다.
• 이를 방지하기 위해 레이어를 분리하여 hierarchical한 그래프 여러개를 두어 검색 시 local minimum에 빠지는 것을 방지한다.

결과적으로

hnsw 알고리즘은

1. 그래프, 네트워크를 기반으로 이동하며 가장 가까운 검색 대상을 찾아내는 알고리즘
2. 이때, 계층을 쌓아 점차 밀도가 높아지는 레이어로 이동하며 검색 대상과 가장 가까운 곳으로 이동

   계층을 쌓은 이유는 고차원 임베딩을 가장 가까운 위치로 이동해가며 탐색할 때 (greedy) 나타날 수 있는 local minimum 문제를 방지하기 위함
   또한 그래프를 위계적으로 쌓아 엔터 포인터로부터 크게 점프하여 계산 대상의 수를 획기적으로 감소함

3. 검색 대상의 그래프를 어떻게 구성할 것인가가 검색 성능에 큰 영향을 미침

   그래프 구축 시 파라미터 튜닝을 통해 그 성능을 적절히 조절하는 것이 필요

하이퍼파라미터의 종류

1. 검색 관련

• $k$ : 검색 결과로 반환되는 개수
  - $k$개 만큼의 결과를 찾지 못할 경우 exception이 발생함
• $ef$ : 검색 시, 기준 노드로부터 고려하는 이웃 노드를 저장하는 큐의 크기 (검색 시 참조하는 이웃의 범위)
  - 해당 값만큼의 노드를 탐색함, 탐색 결과로 얻고자 하는 개수($k$)보다 크게 설정해야 함

2. 검색 자원 구축 관련

• $M(Minimum)$ : 하나의 노드가 가지는 이웃 노드의 수
  - 값이 클수록 그래프가 촘촘해진다 -> 메모리 공간 차지 많아짐, 검색 속도 느려짐, 검색 정확도 높아짐
• $ef\_construction$ : 그래프 제작 시, 기준 노드로부터 고려하는 이웃 노드를 저장하는 큐의 크기(그래프 구성 시 참조하는 이웃의 범위)
  - 그래프 신뢰도에 영향을 미침
  • 값이 커질수록
    • 검색 결과가 좋아짐 (검색 속도 & 검색 정확도)
      • 항상 비례하여 좋아지는 것은 아님. 임계치 존재
    • 검색 자원 그래프 구축 속도가 느려짐