DEIM Forum 2023 2b-3-2

機械学習によるグラフベース近似最近傍探索の高速化
菅

寧†

陸

可鏡†

杉浦 健人†

石川 佳治†† 東海国立大学機構名古屋大学大学院情報学研究科 〒 464–8603 愛知県名古屋市千種区不老町
Email: {jian， lu}@db.is.i.nagoya-u.ac.jp， {sugiura， ishikawa}@i.nagoya-u.ac.jp
あらまし 今画像分類や推薦システムなど，様々な分野で近似最近傍探索（approximate nearest neighbor，ANN）の手法がよく活用されている. グラフベース ANN 技術では，データセットをあらかじめグラフとして構築し，グラフ上の任意の点から貪欲に問合せ点にアプローチする. 代表的な手法である HNSW（Hierarchical Navigable Small World）では，スキップリストのアイデアを参考に多層グラフを構築し，探索を高速化する. HNSW は全ての問合せ点に対して同じ数の検索エッジを使用するが，一部の検索しやすいノードに対して検索エッジの数を減らしても結果には影響がない. つまり，一部の問合せ点では，冗長なエッジを検索してしまう問題が発生する. 本稿ではこの問題を解決するた
めに，機械学習の手法を用いて，各問合せ点に応じてグラフ上の最適な検索エッジ数を予測する. また，様々なデータセットで実験により HNSW 手法と比較することで，提案手法の高速化の効果を検証する.
キーワード 近似最近傍探索，高次元データ，近傍グラフ．
究の研究動機を説明する．また，4 章では提案手法の設計およ1 はじめに最近傍探索は画像検索，推薦システムなどの幅広い分野で用いられる基礎的な情報処理技術である．この技術は与えられた
問合せデータに対して，データベースから問合せデータに最も近いデータ（最近傍点）を見つける．しかし，データの次元が大きくなると「次元の呪い」という問題を引き起こすのに加え，

び具体的な手順についてそれぞれ説明する．そして，5 章では提案手法の有効性に関する評価実験について述べる．最後に，
本研究のまとめと今後の課題を 6 章で述べる．

2 先行研究2. 1 NSW

検索精度より検索速度が重要であるという要求が増えている．

データセットのデータをノードとし，各ノードを自身の 𝑘 近

そのため，検索時間を大幅に削減できる近似最近傍探索の研究

傍点を結んだグラフを 𝑘 近傍グラフという．しかし，あるデーが盛んに行われている．

タの近傍点を検索するために，データが全てのデータとの距離

近似最近傍探索の一種であるグラフベースの手法は検索時間を計算する必要がある．そのため，大規模なデータセットにかが短くかつ検索精度も高いため，現在広く研究されている．グら 𝑘 近傍グラフを構築するには，膨大な時間が必要である．グ

ラフベースの探索の基本的なアイデアは，データセットから近ラフの構築時間を短縮するために，近似的に 𝑘 近傍グラフを構

似近傍グラフを生成することである．問合せ点の最近傍点を検成できる方法が提案された．このような方法で構築されるグラ

索する際には近傍グラフ上の任意のノードを開始点とし，そのフの各ノードに接続されたノードは，必ずしも真の 𝑘 近傍点でノードの近傍点，つまりエッジの張られている各ノードと問合あるとは限らないので，近似 𝑘 近傍グラフと呼ばれる．

せ点との距離を計算する．最も問合せ点に近いノードへ移動し近似近傍グラフ上での検索速度を向上させるために，Malkov

この処理を繰り返すことで，問合せ点の最近傍点となるノーらは navigable small world（NSW）グラフを提案した [6]．NSW

ドを探す．現在のグラフベース近似最近傍探索の主流手法ははノードを 1 つずつグラフに追加し，ビームサーチによって現

hierarchical navigable small world（HNSW）グラフ [1] や，navi-

在のグラフ上で距離の近い 𝑘 個のノードへエッジを張り近似近gating spreading-out graphs（NSG） [2],navigating satellite system

傍グラフを生成する．つまり，後半に追加されるノードは近傍graphs(NSSG)） [3] などを用いた手法である．また，近年では

点へのエッジしか持たないが，早期に追加されたノードは遠く

機械学習によるグラフベース近似最近傍探索の高速化手法も提のノードへのエッジを持つ可能性がある．NSW ではそのよう案されている [4, 5]．

な長いエッジを問合せ点への近道として利用できるため，検索

本研究ではグラフベースの近似最近傍探索を高速化するため速度が大幅に向上する．

に，最先端の手法である HNSW グラフの改善点について検討

しかし，このような構成方法は問題点がある．NSW では最する．特に，ユーザに要求された検索精度に対する機械学習に初に追加された点だけがこれらの近道を持ち，後半に追加されよるより高速な近似最近傍探索の実現を図る．

た点はその点に非常に近い点とのみ接続される．そのため，検本稿の構成は以下のとおりである．2 章では，グラフベース

索の早期段階（問合せ点への距離が大きい段階）に後半に追加の近似最近傍探索および今の改善手法に関する先行研究についされたノードを多数経由してしまった場合，細かな移動が重なて概説する．次に，3 章では先行研究の問題点を分析し，本研

り検索が悪化してしまう．

近似最近
傍探索の
中間段階
の検索結
果

Dist(present,query)Dist(start,query)Dist(present,query)

予測
勾配ブー
スティン
グ決定木

必要な
距離計
算の数P

現在の距離
計算回数
𝐜𝐧𝐭 > 𝑷

Dist(start,query)

Y

query

探索の早期
打ち切り

N

探索を
続ける

図 1 早期終了による HNSW の高速化手法の流れ

2. 3 早期終了による HNSW の高速化

2. 2 HNSW
近道となるエッジをより効果的に構築するために，Malkov ら

HNSW を高速化するために，Li らは機械学習によって各問は NSW に階層構造を導入した HNSW を提案した．HNSW は合せ点の終了条件を予測し，検索を早期に終了させる手法を提スキップリストのアイデアを参考にしており，1 つ下位の層に案した [4]．Li らは実験により，HNSW において 80 ％の問合存在するノードが現在の層にも存在する確率が 𝑝 となるように

せ点はより小さな 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ によって最近傍点が見つけられるグラフを構築する．つまり，最下層を第 0 層とし全ノード数をことを示した．しかし，HNSW では全ての問合せ点に同じパラ𝑁 とする場合，第 𝑖 層にあるノードの数はおよそ 𝑝 𝑖 𝑁 であり上

メータ 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ を使用する．つまり，一部の検索が難しい問層になるほどノード数が減少する．したがって，図 2 に示すよ

合せ点の最近傍を見つけるためにより大きな 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ を設定

うに上位層のグラフを検索のための近道として利用できる．検する必要があり，その他多数の問合せ点に対して無駄なノード

索時には最上層から順に問合せ点の最近傍点を見つけ，ある層の検索が多く発生する．

の最近傍点を次の層の開始点として繰り返すことで，最下層にこの問題を解決するために，Li らは機械学習モデルを用いた各問合せ点の終了条件の予測を提案した．Li らの手法の処理手

おける問合せ点の最近傍を検索する．
こうして構築されたインデックスは，上層のノードが疎にな

順を図 1 に示す．HNSW における検索のとき最も時間がかかる

り，その間のエッジは全ての近道と見なすことができる．上層のは，複数のノードと問合せ点の距離計算である．そのため，のグラフは問合せ点のおおよその位置を推定できる．最下層の距離計算の回数を検索時間として見なすことができる．また，

グラフ，すなわち全てのノードを含むグラフから，問合せ点の同じ 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ であっても，問合せ点によって必要な距離計算

最近傍点を可能な限り正確に見つける．

の回数が異なる．したっがて，Li らは距離計算の最大回数を終

HNSW では以下の 3 つのパラメータが使用される．

了条件としている．元の HNSW では大きな 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ を用い（ 1 ） 𝑀 ：各ノードの近傍点の最大数．

るため，検索が容易な問合せ点において仮に全ての最近傍点が（ 2 ） 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛：グラフ作成のためのビームサイズ．

見つかった後でも，より近い結果がないことを確認するために（ 3 ） 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ：検索のためのビームサイズ．

多くのノードが検索される．一方，Li らの手法では各問合せ点

既存研究では 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 と 𝑀 の増加に伴いグラフの作成の距離計算の最大回数を予測し検索処理を早期に終了させ無駄時間とメモリの使用量も増加するが，検索精度は高くなると報な検索を省く．

告されている．

特徴量としては，開始点から問合せ点までの距離，問合せ点のベクトル，一定回数検索した後の結果から問合せ点までの距
離などのデータが用いられる．以上の特徴量を使って距離計算

Layer 2の最大数を終了条件として予測し，距離計算の数が予測値より大きくなったら探索を終了し，現在の結果を返す．

Layer 13 研究動機本章では，まず先行研究の問題点を分析し，提案手法のアイデアを紹介する．次に，予備実験を行い，実験結果により提案
手法の実現可能性を検証する．また，適切な検索エッジ数を予

Layer 0測するために，ユーザの精度要件を考慮する必要があると判断する．

3. 1 先行研究の問題点

開始点

問合せ点

最近傍点

Li の方法は高い検索精度が要求される場合にのみ有効であり，検索精度が求められない場合は早期終了が上手く働かない．

図 2 HNSW グラフ構造

そして，Li の実験結果により再現率が 0.95 に達しない場合，Liの手法では検索時間がほとんど短縮されない．また，検索を早劣っている．GIST1M データセットについては全ての検索エッ期に終了しても，検索中の不要な検索を回避できないという問ジ数で得られた結果が近いが，検索エッジ数 32 と 64 の結果が題点もある．

常に他の検索エッジ数の結果を上回った．

一方，HNSW はビームサーチでの検索時にノード全ての近傍以上の実験から次の結論が得られる．

点を走査する．問合せ点が開始点からまだ遠い場合，問合せ点• 適切な検索エッジ数を選択することで，HNSW の検索速の大まかな方向を推測するために各ノードの近傍点の一部だけ度を効果的に向上させる．同じ問合せデータセットでも，検索を検索して，問合せ点に高速にアプローチすることが可能であエッジ数の違いによって得られる結果は大きく異なる．

る．これらの問合せ点に対して，検索エッジの数を近傍点の最• 最適な検索エッジ数は要求される検索精度によって異な

大数 𝑀 に設定することは明らかに不適切である．問合せ点がる. 低い検索精度でも十分な場合，ノードあたり少数の近傍点の開始点に近い場合，開始点の近傍点はすでに問合せ点の最近傍みを検索することで，より高速な検索を実現できる．一方，高である可能性が高い．そのため，開始点からより多くの近傍点

い検索精度が要求される場合は十分な数の近傍点を検索しなけを検索することで，素早く結果を得ることができる．以上の分れば要求を満たせない．したがって，最適なエッジ数を予測す析により，全ての問合せ点に対して同じ検索エッジ数で検索する際には，ユーザに要求された検索精度を考慮する必要がある．

ると，HNSW の検索性能が制約されることが分かる．
本研究では HNSW と Li の方法の問題点を解決するために，• 最適なエッジ数の選択はデータセットの分布に依存し，単純にデータセットのサイズとデータの次元から最適なエッジ

終了条件の予測ではなく各問合せ点における最適な検索エッジ数を選択することはできない．GIST1M データセットと GAUSS

数の予測に着目する．つまり，問合せに応じて異なる検索エッ

データセットの次元はそれぞれ 960 と 128 であり，データサイジ数を設定することで，任意の検索精度で HNSW の高速化のズは同じである．しかし，検索精度の設定が低い場合，GAUSS実現を図る．

の最適なエッジ数は GIST1M の最適なエッジ数よりも大きい．

3. 2 検索エッジ数の分析
このアイデアの実現可能性を検証するため，まず検索エッジ数
が検索性能に与える影響を分析する予備実験を行った．HNSW

一方，他の二つのデータセットは GAUSS よりもデータサイズと次元が大きいが，最適なエッジ数は GAUSS よりも小さい．
そのため，本研究では機械学習を用いて各問合せ点に対する最適な検索エッジ数を予測する．

は検索時にノード全ての近傍点を走査するため，各ノードの近傍点の最大数 𝑀 がそのまま検索エッジ数となる．そのため，

4 機械学習による検索エッジ数の予測

ノードの最大近傍点の数が異なるグラフを構成し，その上で検索を行うことで検索エッジ数の異なる検索をシミュレートすることが可能である．
本 研 究 は 実 デ ー タ で あ る GIST1M [7]，GLOVE1.2M，

GLOVE2.2M [8] と正規分布に従う人工データ GAUSS を用
いて実験を実施した．なお，各データセットの情報は後述する実験の章の表 1 にて詳細を紹介する．
各データセットに対して， 𝑀 ∈ {16, 32, 64, 96, 128} を用いて

HNSW グラフを構築した．構築した各グラフに対して近似最近傍探索を実施し，異なる 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ に応じた検索時間と再現率を計測した．異なる検索エッジ数で得られた結果を図 3，図 4に示す．図の横軸は問合せ点あたりの平均検索時間，縦軸がその平均検索精度を表す．
図 3 に示した GLOVE1.2M の実験結果により，検索精度が0.95 以下の場合，1 ノードあたり 16 本のエッジのみを検索することで最良の結果が得られることが分かる．一方，要求精度が 0.95 より大きい場合，ノードあたりの検索エッジ数が 32 と64 の方が良い結果となる．GLOVE2.2M の結果は GLOVE1.2Mの結果と似ているが，検索エッジ数が 16 の場合の結果が他の結果よりはるかに優れていることが分かる．
図 4 の結果により GAUSS データセットでは，検索精度 0.90以下の場合，検索するエッジの最適数は 64 個である．要求する検索精度が高くなるにつれて，検索エッジ数 96 の結果が最速で対応する精度に到達するようになる．また，検索エッジ数が16 と 32 の結果は，他の検索エッジ数の結果に比べて一貫してこの章では提案手法のアイデアおよび具体的な処理手順について述べる．

4. 1 ラベルの推測
3 章の実験により検索エッジ数は検索精度と検索時間についてトレードオフの関係を持つため，精度と時間の両方において支配的な検索エッジ数は見つけられない．そのため，本研究ではまずユーザが要求する検索精度を閾値として設定すし，閾値
に最初に到達した検索エッジ数を学習データセットのラベルとして使用する．つまり，検索精度をパラメータとし，精度を満たす範囲で処理時間を最小化できるエッジ数を機械学習における正解ラベルとする．学習データセットにおけるラベル生成のアルゴリズムを図 5 に示す．閾値に最初に到達した検索エッジ
数を学習データセットのラベルとして使用する．
まずノードの近傍点の数がラベルの最大値となるグラフを作成する．次に，学習データセット中の各問合せ点に対して，検索エッジ数を変えてグラフで検索し，検索時間と検索精度を記録する．検索精度が閾値に達した場合，このエッジ数をラベルとする．検索精度が閾値に達しない場合，より大きな検索エッジ数で検索する．検索エッジ数をノードの出次数まで増加させても検索精度が閾値に達しない場合，最も検索精度の高い検索
エッジ数をラベルとする．ただし，学習データセットが大きい
場合，各問合せ点の最適なエッジ数を正確に計算するには時間がかかりすぎる．そのため，各問合せ点に対して最小値から最図 3 GLOVE1.2M と GLOVE2.2M における検索結果

図 4 GAUSS と GIST1M における検索結果

Input: 検索精度の閾値 𝑅 ，問合せ点セット 𝑄 ，問合せ点の近傍くても妥当な次の検索ノードが見つけられると考えられる．一点の集合 𝐺 ，検索エッジ数の最大値 𝑀 ，ラベルの間隔 𝑡方，検索が進み問合せ点に近づくにつれて真の最近傍点を見つ

Output: 最適な検索エッジ数

けるには微調整が必要となり，確認するエッジ数も増加すると

1

𝑏𝑒𝑠𝑡_𝑟 𝑒𝑐𝑎𝑙𝑙 := 0, 𝑏𝑒𝑠𝑡_𝑒𝑑𝑔𝑒𝑠 := 0

考えられる．

2𝑚 := 𝑡3

for each 𝑞 ∈ 𝑄 do

4while 𝑚 <= 𝑀 do

2 つ目は開始点と問合せ点周辺の点密度である．ある点の周囲の点の密度が高い場合，それらは同じ近傍点を多数共有している可能性が高い．したがって，検索エッジ数を減らし周囲の5

results := SearchbyHNSW(𝑞, 𝑚, 𝑒 𝑓 𝑆𝑒𝑎𝑐ℎ);6

𝑡𝑒𝑚 𝑝_𝑟 𝑒𝑐𝑎𝑙𝑙 := Calculate_Recall(results, 𝐺);7

if 𝑡𝑒𝑚 𝑝_𝑟 𝑒𝑐𝑎𝑙𝑙 > 𝑅 then

問合せ点や開始点周辺の点の密度を計算することは困難であ

8

𝑏𝑒𝑠𝑡_𝑒𝑑𝑔𝑒𝑠 := 𝑚

るため，開始点と問合せ点のベクトルを直接特徴量として利用

9

break

する．ある問合せ点の最適なエッジ数が小さい場合，その周辺

10

if 𝑡𝑒𝑚 𝑝_𝑟 𝑒𝑐𝑎𝑙𝑙 > 𝑏𝑒𝑠𝑡_𝑟 𝑒𝑐𝑎𝑙𝑙 then

点の一部を検索するだけで次の最近傍点を発見できると考える．

の他の問合せ点の最適なエッジ数も小さくなると考える．その11

𝑏𝑒𝑠𝑡_𝑒𝑑𝑔𝑒𝑠 := 𝑚

ため，問合せ点の位置を最適なエッジ数を決定するための特徴

12

𝑏𝑒𝑠𝑡_𝑟 𝑒𝑐𝑎𝑙𝑙 := 𝑡𝑒𝑚 𝑝_𝑟 𝑒𝑐𝑎𝑙𝑙

量として利用する．また，開始点と問合せ点のベクトルには既13𝑚 := 𝑚 + 𝑡に両者の距離に関する情報が暗黙に含まれるため，両者の距離

14

return 𝑏𝑒𝑠𝑡_𝑒𝑑𝑔𝑒𝑠

をあらためて特徴量としては扱わない．したがって，本研究で図 5 学習データのラベルの生成

は問合せ点と開始点のベクトルを特徴量として利用する．

4. 3 予測モデルの作成
大値までの等間隔で数値を取り，検索エッジ数の候補とする．

4. 2 特徴量の選択
本研究では，以下の 2 つの要因が，問合せ点に対する最適な検索エッジの数に影響を与えると考える．
１つ目は，開始点から問合せ点までの距離である．開始点が問合せ点からまだ遠い場合，問合せ点への大まかな方向さえ正
しければ距離を縮められる．つまり，確認するエッジ数が少な

本研究では，勾配ブースティング決定木を予測モデルとして利用する．勾配ブースティング決定木はアンサンブル学習を参考にして，複数の決定木を組み合わせることで予測を行う．まず，最適なエッジ数を予測するために単一の決定木を構築し，予測誤差を計算する．そして，最初の決定木の予測誤差を予測するために，もう一つの決定木を生成する．つまり，前の決定木の予測値の誤差を，新しい決定木が引継いで小さくしていく．学習ラウンドごとに新しい決定木が追加される．最後は全

訓練データセット

入力値

勾配ブースティ
ング決定木
事前に構
築したグ
ラフイン
デックス

HNSWグラフ最下層の開始点のベクトル

予測モデ
ル

入力
値
問合せ点のベクトル

予測 検索エッ
ジ数

入力値

図 6 提案手法の流れ

Input: 問合せ点 𝑄 ，返すべき近傍点の数 𝑘 ，HNSW グラフ 𝐺
1

データ点を取り出し，問合せ点として使用する．これらの問合Output: 検索された結果

せ点について 4. 1 章の方法で対応するラベルを生成する．また，

while G のベースレイヤに到達していない do

これらの問合せ点について，4. 2 章で説明した特徴量を収集す2𝑠 ← BeamSearch()

る．そして，学習データセットに基づいて 4. 3 章で紹介した勾3

次のレイヤーに移動します

配ブースティング決定木予測モデルを作る．

// 予測モデルを呼び出し，最適なサーチエッジの数を予測する
4

問合せ点が与えられると，まず事前に構築されたグラフに対

𝑓 𝑒𝑎𝑡𝑢𝑟 𝑒𝑠 ← 𝑠, 𝑞

して検索を行い，HNSW グラフにおける最下層の開始点を探す．

5

𝑏𝑒𝑠𝑡_𝑒𝑑𝑔𝑒𝑠 ← Predict( 𝑓 𝑒𝑎𝑡𝑢𝑟 𝑒𝑠)

次に，開始点と問合せ点のベクトルを特徴量とする勾配ブース

6

𝑟 𝑒𝑠𝑢𝑙𝑡 𝑠 ← SearchbyHNSW(𝑏𝑒𝑠𝑡_𝑒𝑑𝑔𝑒𝑠)
return 𝑟 𝑒𝑠𝑢𝑙𝑡 𝑠

ティング決定木を用いて，最適な検索エッジ数を予測する．最7

図 7 予測モデルへの HNSW の組み込みての決定木の予測値を足し合わせて，最終的な予測値とする．

後に，このエッジ数を用いて，結果が返されるまで検索を実行する．

5 評価実験

勾配ブースティング決定木は今まで多くのライブラリがリリースされており，マイクロソフトが開発した LightGBM ライブラ
リ [9] は高速な学習速度と少ないメモリオーバーヘッドにより，企業で広く利用されている．本研究では，LightGBM ライブラリの関数を直接利用して予測モデルを作成する．
また，この勾配ブースティング決定木を選択した主な理由は
以下の 3 つである．一つ目はメモリのオーバーヘッドの小ささである．決定木のサイズは数千 𝐾 𝐵 であり，グラフのサイズに比べてはるかに小さい．二つ目は時間のオーバーヘッドも少ない点である．勾配ブースティング決定木を用いた各問合せ点の予測時間はわずか数十マイクロ秒であり，HNSW の検索時間と比べても短い．三つ目はこのモデルが特徴量の重要性を定量化

本章では，提案手法の高速化の有効性を実験により評価する．

5. 1 実 験 設 定
まずは，本実験で使用するデータセット，および評価方法についてそれぞれ説明する．

5. 1. 1 使用データセット
提 案 手 法 の 評 価 の た め に ，表 1 に 示 す よ う に GIST1M，

GAUSS，GLOVE1.2M，GLOVE2.2M の 4 つのデータセットを用いる．GIST1M は画像から求まる特徴ベクトルを集めたデー
タセットである．GLOVE1.2M と GLOVE2.2M は単語ベクトルからなるデータセットである．GAUSS は正規分布に従う生成
した人工データである．

する点で，特徴量選択などに用いられる関数も持つ．本研究で
表 1 用いたデータセット

利用する特徴量が最適な検索エッジの数に与える影響を分析す
るのに役立つ．

データセット

データ数

問合せ点数

次元数

データタイプ

GAUSS

1,000,000

1000

128

人工データ

GLOVE1.2M

1,193,514

1000

200

テキストデータ

提案手法の処理手順を図 6 に示す．HNSW では近傍点全て

GLOVE2.2M

2,196,017

1000

300

テキストデータ

を検索するためその検索順序は結果に影響を与えないが，提案

GIST1M

1,000,000

1000

960

画像データ

4. 4 勾配ブースティング決定木による HNSW

手法により検索エッジ数を削減した場合は検索順序も重要となる．そのため，近傍点の検索順が固定されるように各ノードの近傍点はそのノードから近い順に格納する．検索エッジ数が 𝑋の場合，近傍点の配列から最初の 𝑋 個の近傍点を探索する．
また，最適なエッジ数で検索できるように HNSW の検索関数を変更する．まず関連する特徴量を収集し，最適なエッジ数を予測した上で探索を行えるようにする．
変更した HNSW を用いて，まず近傍点の数がラベルの最大値となるグラフを作成する．次に，データベースから一部の

5. 1. 2 パラメータ設定と比較手法
GLOVE1.2M と GLOVE2.2M のデータセットの探索難易度が低いため，オリジナルの HNSW と提案手法では， 𝑀 = 128 と

𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 500 を用いてグラフインデックスを構築した．
他の二つのデータセットに対して，オリジナルの HNSW と提案手法では， 𝑀 = 128 と 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 1000 を用いてグラ
フインデックスを構築した．
また，各問合せ点に対して学習データのラベルを 16 から 256

まで 16 の倍数に設定し，再現率 0.95 を閾値として使用する．
以下，各実験結果では以下の略称で提案手法と比較手法を区別する．

表 3 学習データセットに対する実験結果
データセットサイズ

トレーニング時間 (s)予測時間 (μs)

GAUSS100,000

3.21

59.36

Vanilla HNSW：以上のパラメータ設定でオリジナルの

GLOVE1.2M

108,502

2.94

31.85

HNSW グラフ構造を構築し，このグラフ上で得られた結果を

GLOVE2.2M

109,801

2.81

17.51

GIST1M

100,000

10.99

22.43

•
示す．

•

Optimal HNSW：3 章の実験から，最大近傍数の異なるグラフに対する同じ問合せデータセットで得られた結果の検索た結果は，0.90 以上の検索精度に到達するためには，問合せ点

精度は，同じ検索時間でも異なることが分かる． そこで，同じあたり少なくとも 5𝑚𝑠 が必要であることが分る．

検索時間で異なるグラフで得られた結果の精度を比較し，その5. 2. 2 索引の構築時間とサイズ

中で最も優れた検索精度を求める．このような操作をいくつかの異なる検索時間に対して行い，各検索時間におけるオリジナ
ルの HNSW の最良の検索精度を近似的に実現する．これらの点を結ぶことで optimal HNSW の結果とする．

•

Our approach：提案手法の検索結果を示す．

5. 1. 3 実 験 方 法

表 4 グラフの構築について提案手法と HNSW の比較
データ

アルゴリズム 構築時間 (s) 索引サイズ (GB)GIST1M

HNSW

2291.88

4.54

GIST1M

提案手法

2558.64

4.54

GAUSS

HNSW

3142.86

1.44

GAUSS

提案手法

3878.36

1.44

本研究では，提案手法の有効性を確認するため，提案手法と

GLOVE1.2M

HNSW

2421.69

2.04

HNSW との比較実験を行った．まずは，四つのデータセットに

GLOVE1.2M

提案手法

2462.48

2.04

おいて，各問合せ点に対する 100 個の近似最近傍を見つける探GLOVE2.2M

HNSW

6752.86

4.58

索を行う．検索時の 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ が大きいほど，結果の検索精度

GLOVE2.2M

提案手法

6828.344.58が高く，検索時間が長くなる．これらの異なる 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ の結果を連結することにより，検索精度と検索時間の関係が分かる．

表 4 からもわかるように，データセットによって構築時間

検索時間の評価においては，グラフインデックスの生成などのの増加率が異なることがわかる．提案技術は，全てのノー時間は含まず，問合せ点を与えてから近傍点が出力されるまでドの近傍点をそのノードから近い順に並べる．オリジナルを計測対象としている．最後に，問合せ点ごとの平均検索時間の HNSW は，近傍点数が 𝑀 より大きい場合にのみ近傍点を結果とする．検索精度の評価においては再現率を用いる．再を並べ替える．そのため，提案手法の構築時間はオリジナル

現率の定義は以下のとおりである．

HNSW よりも長くなる．しかし，提案手法により HNSW の高•

M：検索された最近傍点の集合．

速化を実現するため，構築時間の増加は許容できると考える．

•

G：正解となる最近傍点の集合．

GIST1M,GAUSS,GLOVE1.2M,GLOVE2.2M の四つのデータセッ

𝑀 ∩𝐺
再現率 =
(1)
𝐺
以上の設定のもと，各手法における処理結果を比較評価する．
全ての手法は，同じ問合せデータセットを使って実験された．
また，本実験では全てのプログラムを 1 台のサーバ上で実行する．実験に使用したマシンの構成を表 2 に示す．
表 2 実験用サーバの構成

トの構築時間の増加率は，それぞれ 11.64%，23.40%，1.68%，

1.12% である．時間の増加率は，データセットの分布にも関係していると考える．また，提案手法と HNSW のパラメータが同じであるため，グラフの索引サイズが大きくならないことがわかる．予測モデルのトレーニング時間は，グラフの構築時間に比べてごくわずかである．そのため，予測モデルの導入は

HNSW にあまり影響を及ぼさない．
5. 2. 3 探索時間の比較
前述したデータセットにおいて異なる検索精度を達成するたOS

Ubuntu 20.04.5 LTS

CPUIntel(R) Xeon(R) Gold 6262V (two sockets)

めに必要な検索時間を図 8，9 にそれぞれ示す．赤い破線は本

メモリ

DIMM DDR4 (Registered) 2933 MHz (16GB ×14)研究の提案手法による結果である．オレンジ色の破線は，最大近傍数の異なるグラフを用いた実験から得られた最良の結果で

5. 2 実 験 結 果
5. 2. 1 予測モデルのトレーニング
本研究では，各データセットについてそれぞれ予測モデルを作成し，各問合せ点に対応する検索エッジ数を予測する．

ある．また，提案手法で用いたグラフと同じ数の最大最近傍を持つ HNSW グラフを構築し，その結果を青い破線で示す．
図 8 の左の図は，GLOVE1.2M データセットにおける提案手
法と HNSW の結果を示す．この結果から，提案手法の結果は一貫して HNSW の結果を上回っていることが分かる．つまり，また，各予測モデルのトレーニング時間および予測時間を集ある検索精度を得るためには，提案手法はオリジナルの HNSW

計した．関連情報は表 3 のとおりである．この結果から分かる

よりも短い検索時間しか必要としない．閾値として 0.95 の検索

ように，各データセットに対する予測モデルに必要な予測時間精度を達成するために，提案手法は約 13ms の検索時間が必要

は，わずか数十マイクロ秒である．一方，3 章の実験で得られである．同じパラメータで構築した HNSW グラフがこの精度

図 8 GLOVE1.2M と GLOVE2.2M における検索結果

図 9 GAUSS と GIST1M における検索結果を達成するのには 23ms かかり，検索時間を 30% 短縮できていが最も検索性能が高いという予想通りの結果となった．

る．また，実験で得られた最も性能の良いグラフと比較しても5. 2. 4 考

23% 短縮されている．以上の結果より，提案手法の高速化の有以上の分析から使用するグラフの最大近傍点の数が同じであっ効性が検証された．

察ても，提案手法によって得られる結果はオリジナルの HNSW

図 8 の右の図は GLOVE2.2M データセットに対する提案手法

によって得られる結果よりもはるかに優れていることが分かる．

と HNSW の結果である．この結果から，検索精度が 0.90 以下

また，本実験の GIST1M，GLOVE1.2M，GLOVE2.2M 三つのの場合，提案手法は Optimal HNSW の結果とほぼ同じ時間を要

データセットにおいて，提案手法は必要な検索精度をより速くすることが分かる．しかし，検索精度が 0.90 以上の場合，提案達成することが分かる．検索が難しいデータセットに対しては，手法の検索速度は一貫して Optimal HNSW の検索速度より速い

提案手法により要求される検索精度の設定が低い場合の検索時ことが分かる．また，精度がある閾値を超えた後も，Optimal

間を短縮することができる．高い要求される精度を達成するの

HNSW の結果より優れていることが分かる．GLOVE2.2M の問にかかる時間も，オリジナルの HNSW と同じ程度になること

合せ点がバラバラに散らばっており，同じ検索エッジ数で全てが保証される．

の問合せ点に対し良い結果を得られないためと考えられる．一4. 2 章の分析により，問合せ点の検索のしやすさが主に開始

方，提案手法は問合せ点ごとに異なる数の検索エッジ数を用い

点からの距離と，問合せ点が位置する空間のデータ密度に依存るため，このような問合せデータセットを扱うのに適している．

すると考える．オリジナルの HNSW では，異なる問合せ点に

図 9 の左の図は，GAUSS データセットに対する提案手法と応じてパラメータを自動的に設定することを考慮していない．

HNSW の結果である．結果から分かるように，要求される検索その結果，より大きな検索精度を得るために，検索しやすい問

精度が小さい場合，提案手法の結果は HNSW の最良の結果よ

合せ点に対して不要なエッジを大量に検索することになる．

りも常に優れている．GAUSS データセットは検索が難しい分

本研究ではこの問題に対処するため，問合せ点と開始点の位布となっているが，検索精度の要求が低い場合，提案手法によ置に応じて異なる検索エッジ数を設定し，HNSW の高速化を実る検索時間の削減が可能だとわかる．一方，検索精度が 0.95 を現する．最適なエッジ数を予測するのに必要な時間が数十マイ超えると，条件を満たすために検索するノード数を減らすこと

クロ秒であり，予測時間は検索時間に比べてほとんど無視できが難しくなる．その結果，検索時間は元の HNSW が必要とするほど短い．そのため，データセット検索が特に困難な場合，る検索時間に近づいている．

提案手法の検索速度がオリジナル HNSW に劣らないことを保図 9 の右の図は，GIST1M データセットに対する提案手法と

HNSW の結果である．検索精度は 0.95 以下の場合，提案手法

証できる．
また，本研究の提案手法には以下の利点がある．

• 実際の応用では，HNSW の性能を向上させるために，パラメータ 𝑀 を調整する必要がある．しかし，データセットのサイズが大きいため，グラフ索引の構築には長い時間がかかる．
データセットに対して複数の異なるグラフをを構成し，最も性能の良い 𝑀 を探すことは不可能である．そのため，オリジナ
ルの HNSW は今回の実験における Optimal HNSW と同じ検索性能を実現することは困難である．一方，本研究で提案する手法はより大きなパラメータ 𝑀 を設定し，一つのグラフを構成するだけで各問合せ点に応じて最適な検索エッジ数で検索できる．これにより，HNSW の性能を向上させる．

• 従来の HNSW ではユーザの異なる精度要求に対応する
ために，異なるグラフを構築する必要がある．精度の要求が高い場合，より多くの近傍点を持つグラフを構築する必要がある
が，そのようなグラフは小さな 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ の設定でも検索に長い時間を要する．一方，近傍点の数が少ないグラフは高速に結果を出せるが，𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ を上げても高い検索精度は達成できない．これに対し，提案手法はより多くの最近傍点でグラフを構成するものの，短い検索時間で結果を得ることができる．また，𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ を上げることで，より高い精度の要求に対応可能である．

6 おわりに本稿では，HNSW の概要を述べ，HNSW に対する改善点を分析した．予備実験により検索エッジ数の選択が HNSW の性能に影響を与えることを示し，HNSW の問題点を解決するた
めに，機械学習による HNSW の高速化手法を提案した．また，

HNSW に学習した予測モデルを取り込み，4 つのデータセットを用いて評価実験を行った．本実験により，要求される検索精度に対し，提案手法はオリジナルの手法よりも高速に近似最近傍点が検索できることを検証した.
今後の課題としては，検索の進行段階に応じた最適なエッジ数予測への拡張が挙げられる．また，この手法を他のグラフ
ベース近似最近傍検索手法に拡張する予定である．

謝辞

本研究は JSPS 科研費 JP20K19804，JP21H03555，JP22H03594，

JP22H03903 の助成を受けたものである．

文

献[1] Y. A. Malkov and D. A. Yashunin, “Eﬃcient and robust approximate nearest neighbor search using hierarchical navigable small worldgraphs,” IEEE TPAMI, vol. 42, no. 4, pp. 824–836, 2018.
[2] C. Fu, C. Wang, and D. Cai, “Fast approximate nearest neighbor searchwith navigating spreading-out graphs,” CoRR, vol. abs/1707.00143,
2017.
[3] C. Fu, C. Wang, and D. Cai, “High dimensional similarity search withsatellite system graph: Eﬃciency, scalability, and unindexed querycompatibility,” IEEE Transactions on Pattern Analysis and MachineIntelligence, 2021.
[4] C. Li, M. Zhang, D. G. Andersen, and Y. He, “Improving approximate
nearest neighbor search through learned adaptive early termination,”in Proc. SIGMOD, 2020.
[5] D. Baranchuk, D. Persiyanov, A. Sinitsin, and A. Babenko, “Learning

to route in similarity graphs,” CoRR, vol. abs/1905.10987, 2019.
[6] Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov, “Approximate nearest neighbor algorithm based on navigable small worldgraphs,” Information Systems, vol. 45, pp. 61–68, 01 2013.
[7] GIST1M: http://corpus-texmex.irisa.fr/ (accessed: Jan 8,2023).
[8] GloVe: https://nlp.stanford.edu/projects/glove/ (accessed: Jan 8, 2023).
[9] LightGBM Documentation: https://lightgbm.readthedocs.
io/en/latest/index.html (accessed: Jan 8, 2023).