技術

HNSWとは

Hierarchical Navigable Small World

階層構造を持つグラフを辿ることで、高次元ベクトルの近似最近傍探索を高速に行うアルゴリズム

ひとことで言うと

似ているデータ同士をグラフでつなぎ、階段を降りるように辿って近いものを高速に見つけるアルゴリズム。

概要

HNSW(Hierarchical Navigable Small World)は、高次元ベクトルの集合に対して、厳密な最近傍探索の代わりに高速かつ高精度な近似最近傍探索(ANN)を実現するグラフベースのアルゴリズム。各データ点をノードとし、似たベクトル同士を辺でつないだグラフを、疎な上位層から密な下位層まで複数階層に分けて構築する。検索時は、まず疎な上位層で大まかに目的のベクトルに近い領域まで移動し、階層を降りるごとにより密なグラフの中で探索範囲を絞り込んでいくことで、全データ点との総当たり比較を避けながら少ない計算量で近い点を見つけ出す。 Faiss、Milvus、Qdrant、Weaviateなど主要なベクトルデータベース・ライブラリの多くが、標準的な近似最近傍探索アルゴリズムとしてHNSWを採用している。

背景

埋め込みベクトルの次元数とデータ量が増えるほど、全件を総当たりで比較する厳密な最近傍探索は計算コストが膨大になる。 HNSWは、多少の精度の低下と引き換えに検索速度を高める近似最近傍探索の一手法として、グラフ構造を活用した探索方法を提供するために考案された。

歴史

2016年: MalkovとYashuninがHNSWを提案する論文「Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs」を発表。 2018年以降: FaissやElasticsearch、Milvus、Qdrantなど主要なベクトル検索エンジンが相次いでHNSWを実装に採用。

アーキテクチャ

各データ点をノードとする多層のグラフを構築し、上位層ほどノード数が少なく疎な構造、下位層ほどノード数が多く密な構造を持つ。各ノードは、自身と似たベクトルを持つ少数の近傍ノードとのみ辺で接続される。検索は最上位層のランダムな入口ノードから始め、各層でクエリベクトルに最も近いノードへ貪欲に移動し、下位層へ降りるごとに探索範囲をより細かく絞り込んでいく。

ワークフロー

データ点を挿入する際、ランダムに割り当てた最上層から順に、既存ノードの中から近い近傍を探索して辺を張っていき、グラフを構築する。検索時は最上位層のエントリポイントから始め、各層でクエリベクトルに最も近いノードへ貪欲に移動し、これ以上近いノードが見つからなくなったら1つ下の層へ降りる。最下層まで降りたら、複数の候補ノードを保持しながら探索を続け、上位k件の近似最近傍を結果として返す。

コード例

hnswlibでのインデックス構築と検索

import hnswlib
import numpy as np

dim = 128
data = np.random.rand(10000, dim).astype("float32")

index = hnswlib.Index(space="cosine", dim=dim)
index.init_index(max_elements=10000, ef_construction=200, M=16)
index.add_items(data)
index.set_ef(50)

query = np.random.rand(1, dim).astype("float32")
labels, distances = index.knn_query(query, k=5)

利点

データ量が多くても、全件比較よりはるかに高速に近似最近傍を検索できる
階層構造により、大まかな絞り込みから精密な絞り込みまで段階的に検索を進められる
多くのベクトルデータベース・ライブラリに実装があり、比較的導入しやすい

欠点

近似アルゴリズムであるため、厳密な最近傍探索と比べて精度がわずかに落ちやすい
グラフ構造をメモリ上に保持する必要があり、データ量に応じたメモリ消費が発生する
グラフ構築時のパラメータ(接続数や階層数など)の調整が、検索精度と速度のバランスに影響する

比較

ベクトルデータベース — HNSWは、多くのベクトルデータベースが内部で使う近似最近傍探索アルゴリズムの1つ
Faiss — FaissはHNSWを含む複数の近似最近傍探索アルゴリズムを実装した検索ライブラリ
コサイン類似度 — HNSWによる探索では、ノード間の近さを測る距離指標としてコサイン類似度がよく使われる
IVF — IVFがベクトルをクラスタへ分割し探索範囲を絞り込むのに対し、HNSWはグラフ構造をたどって近傍を探索する
ANN — HNSWは、グラフ構造を用いた代表的なANNアルゴリズムの1つ

よくある質問

HNSWは厳密な最近傍探索と何が違う？

厳密な最近傍探索は全データ点と比較して正確な最近傍を求めるが、計算コストが高い。HNSWはグラフを辿って近似的に近傍を求め、わずかな精度低下と引き換えに検索速度を高める。

HNSWはどこで使われている？

Faiss、Milvus、Qdrant、Weaviateなど主要なベクトルデータベース・検索ライブラリの多くが、標準的な近似最近傍探索アルゴリズムとして採用している。

参考文献

Research PaperEfficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
GitHubnmslib/hnswlib