この記事ははてなエンジニアアドベントカレンダー2025の15日目の記事だ。遅くなってすみません。
HNSWというデータ構造がある。
このデータ構造は、あるクエリした点からの（近似的な）近傍のデータを求めるのに最適化されている。なにが近傍かというと、高次元なベクトル空間における距離（距離空間が定義できればなんでもよいはず）が近い、という意味だ。
埋め込みベクトル便利だね
距離の話は簡単なことで、たとえば、3次元ベクトルでは典型的にはユークリッド距離が入れられてユークリッド空間として近いか遠いかを考えられるようになる。
そして、最近は埋め込みベクトルが一般的な技術として浸透してきた。これは文章や画像などの特徴を1000次元くらいの実数ベクトルに押し込んでしまうものだ。
次元がいくら増えてもベクトル同士の距離が定義できることに変わりはないし、埋め込みベクトルは文書間の類似度も空間の距離として保存してくれる。つまり、似た概念はベクトルに埋め込んでも近い距離になるし、あまり関係ない概念はベクトルにすると遠く離れるのだ。
この、おおまかな構造を保存するというのが便利で、例えば通販サイトの商品を埋め込みによりベクトルにしておけば、ベクトルが近いものを選ぶだけで類似商品を探してくることができる。写真をベクトルにしておけば、ベクトルが近いものを選ぶだけで似た被写体やシチュエーションを探すことができる。一度ベクトルという数学的に堅固な構造に変換することで、何も自然言語処理していないのに、ベクトル計算だけで有用な処理ができるのだ。
最近だと、OpenAIを筆頭に、さくらのAIエンジンとか、CloudflareのWorkers AIには埋め込みベクトル生成用のモデルが用意されていて、それを呼び出すだけでベクトルが帰ってくる。良い時代だ。
HNSW
ほんで、HNSWが欲しくなってくる。なんでかというと、ベクトルが近いものを選ぶだけで〜とかあたかも簡単なことのように言ってたけど、普通に面倒だからだ。
ベクトルの近さをコサイン類似度で測るとして、あるベクトルに近いベクトルを探してくるには、ナイーヴに考えると全データのベクトルに対してコサイン類似度を計算して、ソートして類似度が高いものを探してくることになる。これは $O(N)$ で処理しなければならないから大変だ。データが数億件になったらもう使い物にならなそう。
そこで、「ある空間の一点から近いノードを効率良く（確率的に）列挙できるデータ構造」がいろいろ誕生し、HNSWもその中の一つだ。ここでは概略だけ説明して、正確な理論の話はお預けにしておく。
HNSWはグラフ構造であり、グラフにノードを追加していくたびに「追加しようとしているノードに一番近そうなのはどのノードか」を探すことで、自動的に「近傍のノード」同士が接続していくようになっている。
しかしこれだと、近傍のノードを確実に得るにはグラフを全部辿ることになってしまい、うれしくない。
そこでHNSWは、すべてのノードにランダムにレベルの概念を与え、基本的に同じレベルのノード同士が接続するようにしつつ、たまに高いレベルの近いノードにつながれるようにする。
なおかつ、レベルが上がるほどそのレベルになる確率が下がるようになっているため、低いレベルのノードは多いが、高いレベルのノードは少なくなる。
クエリの最初の段階では最も高いレベルのノードで探索し、おおまかな見当がついてくるとどんどんレベルを降下して詳細な探索に移っていくことで、効率的に近傍ノードを探索する。探索の段階に応じて、全体のノードを間引いた「おおざっぱな」地図を利用できるようにするというわけ。遠い場所に移動するのに、高速道路や空路といった大きな規模でまず移動して、どんどん特急やローカル電車、バスやタクシー、徒歩に切り替えながら移動していくような感じだ。
HNSWをざっくり実装する
HNSWをざっくり実装した。どのくらいざっくりかというと、AIに任せてHNSWとは〜みたいな論文を渡してやってもらった。かなりざっくりしている気がするが、師走なので問題ない。ビジュアライザが動いてうれしいという記事だからだ。
けっこう大変。
ビジュアライザを作る
HNSWがあるだけだと何も分からないので、かっこよく可視化したくなってきた。
そこで、HNSWを構築する各過程でメトリクスをWebSocketに送信し、それを受け取ってブラウザがグラフ構造を描写するという作戦を思い付いた。
なんと都合が良いことに、先日Scalaの非同期ライブラリOxについて学んだばかりだったので、これを利用して非同期にHNSW構築の各フェーズで通知をWebSocket経由で送り出すという実装をパッと作ることができた。通知用チャネルを用意しておき、都度そこにメッセージを送り込む方式だ。
例えばノードを追加したらその詳細をWebSocketに送り、ノード間のエッジを接続したらその詳細をまた送り・・・という具合。フロントエンド側では、このWebSocketから得たデータをvis.jsというライブラリで可視化することにした。このあたりもAIにおおまかに書かせてから細部の調整だけ人間がやった。
試しにさくらのAIエンジンで単語ごとの埋め込みベクトルを生成するようにし、単語としてはイヌの品種、ネコの品種、ハトの種名を20個くらいずつ選定して可視化すると上掲のようなグラフが出現した。接続されているノード同士はおおむね近い概念に対応していて、たとえばハトはハトでだいたいまとまっている。HNSWはレベルの高いノードから降下していく構造なので、違うレベル同士の接続はそんなに意味が近くなかったりする。この例では数十程度のデータしかないが、数億オーダーになったときには効率性が出てくる。
まとめ
- HNSWを実装してその構造をある程度理解できた。
- HNSWのビジュアライザを作り、ノードの構造の傾向を把握できた。
