1. 概要

Navigable Small World Graph(NSW)は、大規模なベクトルデータにおいて、近い隣接点へ少しずつ移動する local link と、探索距離を縮める long-range link をひとつのグラフの中に一緒に蓄積して approximate nearest neighbor を見つける手法です。正確な nearest neighbor を毎回総当たりで計算するのではなく、十分に近い候補を素早く見つける構造を作ることに焦点があります。

大規模な nearest neighbor search は、推薦システム、画像検索、意味ベースの文書検索などで繰り返し現れる問題です。PQ (Product Quantization) 系がこの問題をベクトルを小さく圧縮する方向から解いたとすれば、NSW と HNSW 系はグラフに沿って高速に探索する方向から解きます。Approximate nearest neighbor algorithm based on navigable small world graphs 論文(Malkov et al., 2014)はその出発点にあたります。後続アルゴリズムである HNSW は別の記事で扱います。

主な問いは次のとおりです。

• Voronoi diagram、Delaunay graph、Navigable small world の概念
• NSW が Delaunay graph の近似と navigable small world の性質を同時に狙う理由
• 新しい点を近い隣接点とつなぐ単純な挿入ルールが、なぜ長距離 link まで作り出すのか
• NSW 検索アルゴリズムの構造と実験結果
• NSW の限界と後続の改善方向

2. 必須概念

2.1. Voronoi Diagram

点の集合が与えられたとき、各点 $p$ の Voronoi cell は、他のどの点よりも $p$ に近いすべての位置の集合です。すべての cell の集まりを Voronoi diagram と呼びます。平面を各点が自分の担当区域として分け合っている様子だと考えればよいでしょう。

Voronoi diagram。query が属する cell の主がそのまま nearest neighbor です。

この定義がそのまま nearest neighbor 検索の本質です。query $q$ の最近傍は、$q$ が属する cell の主です。したがって NN 検索は結局、query がどの Voronoi cell の中に入るかを素早く見つける問題に置き換えることができます。

2.2. Delaunay Graph

Delaunay graph は Voronoi diagram の dual グラフです。2 つの点の Voronoi cell が edge を共有するなら、graph ではその 2 点を edge で結びます。同じ情報を空間分割とグラフという異なる視点で表現したものなので、一方が分かればもう一方も決まります。

Voronoi と Delaunay の幾何学的構成原理。左は Voronoi edge が Delaunay edge の垂直二等分線であるという関係、右は外接円が空であるという条件。

第一に、Voronoi edge は 2 点を結ぶ Delaunay edge の垂直二等分線の上に乗ります。2 点 A、B から等距離にある位置の軌跡がまさに A・B を分ける Voronoi 境界であり、等距離の集合はちょうど垂直二等分線です。第二に、Delaunay 三角形の外接円の中には他の点が入りません(empty circumscribed circle property)。この条件が Delaunay triangulation を一意に決定します。

この構造が ANN で重要なのは、検索の性質のためです。Delaunay graph 上で greedy search を実行すると、どの entry point から出発しても正確な最近傍に到達します。 Delaunay graph がすべての隣接 cell を edge で結んでいるため、現在の点より query に近い cell が残っている間は、必ずより近い隣接点へ移動できます。

Delaunay graph 上の greedy search が NN に到達する過程

Delaunay graph ではなぜ greedy search が常に nearest neighbor に到達するのか?

1. 現在のノード $p$ の cell の外に query $q$ があるなら、$q$ は別の cell に属します。Delaunay graph は隣接する cell の主同士を edge で結んでいるため、$p$ の friend list には $q$ により近い隣接点が必ず存在します。
2. greedy が止まるためには、すべての隣接点が query より遠くなければなりません。これは $q$ が $p$ の cell の中にあるときにだけ可能で、そのとき $p$ こそが $q$ の真の最近傍です。

問題は、一般の metric space では正確な Delaunay graph を作れないという点です。点同士の距離しか分からず座標・次元が不明なため、外接円・垂直二等分線のような幾何学的構成が使えず、次元が高くなると平均 degree が指数的に大きくなり得ます。そこで NSW は Delaunay graph を直接作る代わりに、距離情報だけで Delaunay graph に近い検索の性質を作ろうとします。

2.3. Navigable Small World

Navigable small world(Kleinberg, 2000)は、さまざまな距離スケールの link が敷かれていて、greedy な方法でも任意の 2 ノード間の経路を polylog hop 以内に見つけられるネットワークです。遠いときは長距離 link で大きくジャンプし、近づいた後は短距離 link で微調整します。

Navigable small world graph。greedy が hub を経由しながら、大きなジャンプと微調整を組み合わせます。

Kleinberg が強調したポイントは、単に短い経路が存在することと、局所情報だけを見てその経路を見つけられることは別物だという点です。NSW 論文はこの navigability を ANN graph の中に作りたいと考えています。ただし long-range link の分布を明示的に設計するのではなく、データ挿入の過程で自然に形成されるようにする方法を提示します。

3. 論文整理

3.1. 論文概要

論文が登場した時点で、ANN 検索には次のような流れがありました。

1. 空間分割ベースの正確検索: k-d tree・quad tree のようなデータ構造です。低次元では高速ですが、高次元では worst-case が brute-force に近づきます。

2. Delaunay graph ベースの検索: Delaunay graph 上で greedy search と backtracking を行う方式です。検索の性質は良いものの、一般の metric space では正確な Delaunay graph 自体を作るのが困難です。

3. Permutation Index 系: 基準点までの距離の順序を利用してオブジェクトを表現・比較します。一般の metric space・高次元で高い精度を示しましたが、グラフの navigation 自体を作る方式ではありません。

4. NSW を直接構成しようとする試み: 格子やユークリッド空間で navigable small world を明示的に構成しようとする研究です。ただし事前情報や特定の次元構造に依存します。

3.1.1. なぜ Delaunay graph を諦められないのか

Delaunay graph は greedy search だけで正確な nearest neighbor に到達できる強力な構造です。ANN graph が理想的に似せたい対象に近い存在です。しかし理論的に良い構造だからといって、実務的に作れるとは限りません。一般の metric space では座標の代わりに距離関数だけが与えられる場合が多く、高次元では Delaunay graph の degree が大きくなり、保存と探索が難しくなります。

そこで論文は「正確な Delaunay graph」の代わりに、「Delaunay graph の検索の性質を十分に模倣する sparse graph」を目標に据えます。

3.1.2. なぜ small world が必要なのか

Delaunay graph の近似だけでも local navigation の性質は得られますが、開始点が query から遠いと多くの hop が必要になり得ます。大規模データでは、近い隣接点へ少しずつ移動することだけでは不十分です。遠くにいるときに大きく飛び越えさせてくれる long-range link が必要です。

Navigable small world の役割はここから生まれます。long-range link があれば、greedy search は最初は大きな幅で query に近づき、最後は local link で細かく収束します。

3.1.3. NSW の立ち位置: 近似 Delaunay + 自然形成 small world

NSW は 2 つの要求をひとつのグラフに統合しようとします。

論文が解く問いは、したがって次のように具体化されます。

一般の metric space で、事前情報なしに、単純なアルゴリズムで Delaunay graph の近似と navigable small world graph を同時に作れるのか?

3.2. Graph as Index

NSW はグラフ $G(V,E)$ をインデックスとして使います。各データポイントが vertex であり、edge で結ばれた隣接点は互いの friend list に入ります。検索は別途ツリーやハッシュテーブルをたどるのではなく、この friend list に沿って query に近づく方向へ移動する方式です。

このときグラフは 2 つの性質を同時に持たなければなりません。

• query の近くでは十分な local link が必要です。そうすることで false local minimum に陥りにくくなります。
• query から遠く離れているときは long-range link が必要です。そうすることで多くのノードをひとつずつ経由せずに済みます。

興味深いのは、NSW がこの 2 つを別々のルールで作らないことです。ひとつの単純な挿入ルールから short-range link と long-range link が同時に形成されます。

NSW の核心は「良い edge を精巧に設計する」ことではありません。新しいデータが入ってきたとき、現在のグラフで近い隣接点を見つけて接続し、その接続を時間が経っても保存することです。

3.3. 挿入ルール: 2 種類の link の同時形成

挿入ルールは単純です。新しい要素が入ってきたら、現在の構造で最も近い $f$ 個の隣接点を見つけて双方向に接続します。

このルールはとても単純ですが、2 つの効果を同時に生み出します。

空間的効果: 新しい要素を現時点で近い隣接点と接続します。この edge は最初に作られたときは local link です。近い点同士が接続されるため、Delaunay graph の隣接関係を近似する方向に働きます。

時間的効果: データセットが大きくなると、同じ edge の周辺に、より近い点が後から現れます。ところが NSW は既存の edge を消したり、より近い edge に置き換えたりしません。そのため最初は local link だった edge が、時間の経過とともに相対的に long-range link になります。

これが NSW の最も重要な発想です。古い link を保存することは単なる実装上の便宜ではなく、small world navigation を作り出すメカニズムなのです。

3.4. 短距離 link が Delaunay graph を近似する原理

NSW の short-range link は、「ある点の Voronoi 隣接点の集合」と「その点の $f$ 個の最近傍集合」が大きな共通部分を持つという観察に基づいています。Voronoi 隣接点は cell が隣接する点たちであり、隣接する cell の主同士はおおむね互いに近い位置にあります。したがって最も近い $f$ 個を選ぶことは、Voronoi 隣接点を近似することと同じです。

もちろんこの近似は完璧ではありません。$f$ が小さすぎると必要な隣接点を見逃し、大きすぎるとグラフが密になってメモリと探索コストが上がります。NSW はこの trade-off を受け入れ、正確な Delaunay graph の代わりに sparse な近似 graph を作ります。

3.5. 長距離 link が自然に形成される原理

NSW の link evolution。同じ A-B リンクがデータセットの成長に伴って短距離から長距離へ変わります。

データセットが小さいとき(T1)に挿入された A-B link は短距離です。しかしデータセットが大きくなるにつれて(T3)、A の周辺により近い点が現れます。このとき NSW が A-B link を消さなければ、同じ edge が相対的に長距離 link へと変わります。

これがグラフ全体で繰り返されると、初期のノードはさまざまな距離スケールの link を蓄積します。自然に degree の高い hub が生まれ、greedy search は hub を経由しながら大きなジャンプと微調整を組み合わせます。明示的に設計しなければならなかった long-range link の分布が、挿入順序のランダム性から自動的に形成されるわけです。

3.6. Delaunay graph と NSW を壊さないためには

この構造がうまく機能するには、2 つの条件が重要です。

ランダムな挿入順序が必要です。近い点同士をまとめて順番に挿入すると、「古い link = 相対的に遠い link」という関係がうまく生まれません。データが特定の領域から別の領域へ時系列的に拡張していく場合も、同じ問題が起こり得ます。

古い link を保存しなければなりません。「今となっては遠く見えるから近い点に替えよう」という更新をすると、NSW の核心を消してしまうことになります。遠く見える link こそが small world navigation を可能にする長距離 link です。これが単純な k-NN graph と NSW の決定的な違いです。

4. 論文アルゴリズム

NSW の search と insertion は、実質的に同じ探索ルーチンを共有します。まず graph 上で query に近い候補を見つけ、挿入するときは新しい要素を query のように扱って近い隣接点たちと接続します。

4.1. Search Algorithm

2.2 節で、正確な Delaunay graph 上の greedy search は常に nearest neighbor に到達すると見ました。しかし NSW は近似グラフです。したがって、現在のノードのすべての隣接点が query より遠く見えるのに、グラフのどこかにはより近い点が存在する false global minimum が発生し得ます。

最も単純な greedy search は次のとおりです。

Greedy_Search(q: object, v_entry_point: object)
1   v_curr ← v_entry_point;
2   δ_min ← δ(q, v_curr); v_next ← NIL;
3   foreach v_friend ∈ v_curr.getFriends() do
4       δ_fr ← δ(q, v_friend)
5       if δ_fr < δ_min then
6           δ_min ← δ_fr;
7           v_next ← v_friend;
8   if v_next = NIL then return v_curr;
9   else return Greedy_Search(q, v_next);

K-NN 検索はこの単純な greedy を 2 つの方法で補完します。第一に、top-k 候補がそれ以上改善されなくなるまで候補集合を拡張します。第二に、false global minimum を緩和するために、互いに異なるランダムな entry point から $m$ 回検索します。ただし visitedSet を共有して、同じノードを重複して評価しないようにします。

K-NNSearch(q: object, m: integer, k: integer)
1   TreeSet[object] tempRes, candidates, visitedSet, result
2   for (i ← 0; i < m; i++) do:
3       put random entry point in candidates
4       tempRes ← null
5       repeat:
6           get element c closest from candidates to q
7           remove c from candidates
8           if c is further than k-th element from result then break repeat
9           for every element e from friends of c do:
10              if e is not in visitedSet then add e to visitedSet, candidates, tempRes
11      end repeat
12      add objects from tempRes to result
13  end for
14  return best k elements from result

m=3 multi-search。異なる entry point から始めた 3 回の検索が visitedSet を共有します。

精度は検索時に調節します。recall が必要なら $m$ を大きくし、速度がより重要なら $m$ を小さくします。これは、インデックスを作り直さなくても検索品質と速度を調節できるという意味です。

4.2. Insertion Algorithm

挿入はさらに単純です。新しい要素を query のように見なし、現在の graph で近い $f$ 個の隣接点を見つけてから双方向に接続します。

Nearest_Neighbor_Insert(new_object: object, f: integer, w: integer)
1   SET[object]: neighbors ← K-NNSearch(new_object, w, f);
2   for (i ← 0; i < f; i++) do
3       neighbors[i].connect(new_object);
4       new_object.connect(neighbors[i]);

Insertion の 3 段階。(1) 新しい要素の到着 (2) K-NNSearch で近い f 個を探す (3) 双方向の接続。

この構造の長所は実装の単純さです。

• 事前情報が不要: 座標・次元・分布が分からなくても、距離関数さえあれば十分です。
• 漸進的(incremental): データがひとつずつ入ってきてもインデックスを拡張し続けられます。
• 自然な並列化: 局所情報だけを使うため、同期の負担が小さいです。
• 分散の可能性: friend list をたどるだけで検索できるため、graph を分散保存しやすいです。

4.3. パラメータの意味

論文で重要なパラメータは $f$、$w$、$m$ です。

パラメータ $w$ は挿入時の検索精度を決定し、論文は挿入 recall 0.95~0.99 の水準を推奨しています。データセットが大きくなるほど、必要な $w$ は logarithmic に増加します。

5. 論文の実験結果

論文は synthetic データと実際の画像 feature データセットで、NSW が navigable small world の性質を実際に示すのか、そして既存の ANN アルゴリズムと比べて距離計算をどれだけ減らせるのかを確認します。

5.1. Small World Navigation の性質

NSW graph 上の greedy search の平均 hop 数を、データセットサイズに対して測定しました($k=10, w=20, f=3d$)。

Average hop count for different dimensionality Euclidean data (k=10, w=20)

hop 数はデータセットサイズに対して対数的に増加します。これは NSW が navigable small world の性質を持つという中心的な根拠です。次元が大きくなるほど依存性が弱まりますが、論文は、greedy search が long-range link に出会うと query に近い方向だけを選ぶため、検索が quasi 1 次元的に動作するからだと説明しています。

5.2. 分散 / 並列処理

NSW は接続だけで表現される独立オブジェクトの graph なので、分散が容易です。4-node cluster($d=1$)で core 数にほぼ線形な throughput の拡張を示し、$d=10$ の条件で最初の 1000 個を直列挿入した後に 16-thread の並列挿入を行っても精度低下はありませんでした。つまり追加の同期ロジックなしに大規模な並列挿入が可能です。

5.3. 検索計算量のスケーリング

recall 0.999 に固定し、データセットサイズを増やしながら評価した点の割合を測定($d=3 \sim 50, k=10$、20,000 query)しました。

Average fraction of visited elements (0.999 recall) vs dataset size

データセットが大きくなるほど評価割合はむしろ減り、log-log plot では直線(power-law decay)に近づきます。固定した精度において、全データのうち評価すべき割合がどんどん小さくなるという意味です。

Distance calculations and m for 0.999 recall vs dataset size (d=20)

距離計算の回数は $C \log^2(n)$ で増加します。2 つの $\log$ のうちひとつは平均 hop 数($\log n$)から、もうひとつは必要な multi-search の回数 $m$($\log n$)から来ます。

5.4. 次元のスケーリング

約 2200 万個のデータで、次元ごとの評価割合を測定(recall 0.999、$k=10$)しました。

Average fraction of visited elements for ~22M elements

曲線に plateau(最適な次元領域)が観察されます。次元が小さすぎると small world navigation の効果が弱く、大きすぎると次元の呪いが始まります。その間に安定して良好な領域が存在し、位置はデータセットサイズによって少し移動します。

5.5. CoPHiR データセットでの性能

CoPHiR は 1000 万個の実画像の 208 次元 feature ベクトルのデータセットです($k=30$、L1、10 万 query)。実験は 16-thread で約 2 時間かかりました。

Average fraction of visited vs recall error for 10M 208-dim CoPHiR

recall 0.999 でデータの 0.031% だけ評価すれば済みます。それでいて brute-force とほぼ同じ精度です。

5.6. 他のアルゴリズムとの比較

Permutation Index 系の 2 つのアルゴリズムと比較します — NAPP(Neighborhood Approximation)、OP(Ordering Permutation)。

Average fraction of visited vs recall error for 10M CoPHiR

CoPHiR(10M, 208d)では、NAPP(K=7)と比べて NSW は recall 0.999 で 100 倍以上少ない距離計算で済みます。ただしデータ数が少なく($10^4$)次元が非常に高い(d=1024)場合、NSW は recall 0.9 に約 65% を評価する必要があった一方、OP は 42% で可能でした。

この比較が示すことは明確です。NSW の強みは、大きなデータセットと navigable small world がうまく形成される条件で際立ちます。逆にデータが小さかったり次元が高すぎたりして graph navigation の利点が弱まる条件では、他の方式のほうが良い場合があります。

6. NSW の限界と改善方向

NSW はアイデアが単純で強力ですが、その単純さゆえに生じる限界も明確です。

6.1. 限界

6.1.1. ランダムな挿入順序への依存

NSW の long-range link は挿入順序から自然に生まれます。したがって、挿入順序がランダムに近いという仮定が重要です。データが時系列的に特定の領域から別の領域へ拡張したり、近い点同士がまとまって入ってきたりすると、「古い link が長距離 link になる」という性質が弱まります。

6.1.2. 削除と動的更新に弱い

NSW は古い link を保存してこそ small world の性質が維持されます。ところが実際のシステムでは削除、更新、再挿入が発生します。ノードを削除すると、そのノードが提供していた long-range shortcut も一緒に消え、これをどう復旧するかは明確ではありません。

6.1.3. 小さいデータセット + 非常に高次元では不利

CoPHiR のような大きなデータセットでは強みが際立ちましたが、$10^4$ 個規模で d=1024 の条件では OP に遅れを取りました(65% 評価 vs 42% 評価)。データが十分に大きくないと small world 構造が豊かに形成されにくく、次元が高すぎると距離自体の識別力が弱まります。

6.1.4. 適用範囲が経験的なまま残されている

論文は一般の metric space で動作するアプローチを提案していますが、どのようなデータ分布で安定してうまくいくかについての理論的な境界は明確ではありません。したがって実務では、データセットのサイズ、次元、距離関数、挿入順序に応じた個別の検証が必要です。

6.2. 改善方向

6.2.1. neighbor selection をより精巧にする

NSW の挿入は近い $f$ 個の隣接点を選ぶ方式です。この方式は単純ですが、候補間の距離や方向の多様性を考慮しません。近い隣接点ばかり多く選ぶと、似た方向の edge が重複する可能性があります。同じ friend 数を使うとしても、より多様な方向の隣接点を選べば graph の品質を高められます。

6.2.2. small world の形成を自然発生だけに任せない

NSW は long-range link の形成を挿入順序に任せています。より安定した構造を作るには、距離スケールごとの link を明示的に管理したり、階層構造を導入したりする方向が考えられます。後続の HNSW がまさにこの問いをさらに発展させたアルゴリズムです。

6.2.3. multi-search の管理コストを減らす

検索時には visitedSet、候補の優先度キュー、top-k 結果集合を管理し続けなければなりません。recall を高めようと $m$ を大きくすると、この管理コストも一緒に増えます。同じ精度でより少ない entry point を使ったり、候補拡張の順序をより効率的に組んだりすることが改善ポイントになります。

まとめると、NSW は「単純な挿入ルールから良い graph が自然に生まれる」という点が強みです。同時に、その自然な形成に依存しているため、挿入順序、削除、動的更新には構造的に脆弱です。

7. まとめ

NSW は、Delaunay graph の検索精度と navigable small world の検索効率をひとつの graph の中に収めようとするアルゴリズムです。新しい点を現在の graph の近い隣接点たちと接続する単純なルールで local link を作り、その link を長く保存することで、時間が経つと long-range link まで自然に手に入れます。

この観点は、その後のグラフベース ANN アルゴリズムの重要な出発点になります。特に HNSW を理解するには、NSW がまず解決しようとした問題が何だったのか、そして何が足りなかったのかを理解しておくとよいでしょう。HNSW の階層構造は結局、NSW が持っていた「長距離の navigation をより安定させたい」という問題意識の上に成り立っています。

8. 参考文献

• Approximate nearest neighbor algorithm based on navigable small world graphsdoi.org
• The small-world phenomenon: an algorithmic perspectivedoi.org