nucleation

THEORY-815: Layering a navigable small-world graph on nested random subsets of the data, with links separated by length scale and each layer's degree capped, makes greedy nearest-neighbour search cost grow logarithmically with the number of items on data of low intrinsic dimension, where the single-layer graph's cost grows polylogarithmically

2 min read

Properties5
StatusProposed
Tagsdatabases, information-retrieval, network-science
SourceLIT-1098 — Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
ExtendsTHEORY-365 — In one study of a stack of proximity graphs on nested random subsets of the data, each element's top layer drawn geometrically, greedy search on uniform random data in 8 dimensions needed a number of distance computations that grew no worse than logarithmically with the number of items and stayed below a single-layer navigable graph's at every size tested, and in 4 dimensions the beam width needed for a fixed recall saturated; the logarithmic bound is derived only for exact Delaunay graphs of bounded degree, which the index does not build, and on 200 million SIFT vectors the measured growth departs from it
AnswersQUESTION-187 — Does greedy layered search on the graph HNSW actually builds take expected O(log N) distance computations to a stated recall, under a stated condition on the data such as bounded doubling dimension?

Graph View

Source

Malkov and Yashunin (2020), LIT-1098, read in NOTE-916 from arXiv v4. They present HNSW as a skip list generalized from linked lists to proximity graphs, and argue that separating links by length scale into layers, with the degree capped on every layer, makes search cost constant per layer over O(log N) layers, so logarithmic overall. They contrast it with their earlier single-layer navigable small-world graph, whose cost they put at polylogarithmic because both the hop count and the hub degree on the greedy path grow as log N.

What is asserted, and by whom

The thesis is that the hierarchy is what makes greedy search logarithmic: layering a navigable graph on nested random subsets, each element’s top layer drawn geometrically and each layer’s degree capped, turns the flat graph’s polylogarithmic cost into a logarithmic one. Malkov and Yashunin assert it, qualified throughout by low dimension (“in agreement with the simulations on low dimensional datasets”).

What the record holds toward it

  • THEORY-365 (Active): on uniform random data in 8 dimensions the number of distance computations grew no worse than logarithmically and stayed below the flat graph’s at every size tested; in 4 dimensions the beam width needed for a fixed recall saturated.
  • The logarithmic bound is derived only for exact Delaunay graphs of bounded degree. HNSW does not build those, and Delaunay degree grows exponentially with dimension.
  • Against it: on 200 million SIFT vectors (d = 128) the paper reports that the scaling “deviates from the pure logarithm”. The thesis is therefore stated for low intrinsic dimension only.

What this does not say

  • Not that HNSW’s search is logarithmic in high dimension.
  • Not a recall guarantee or a worst-case bound; the paper gives neither.
  • Not that the flat graph’s polylogarithmic growth was measured here: it is the paper’s account of the authors’ earlier work. Only “below NSW at every size” was measured.

What would confirm or reject it

Confirmed by the promote_when: a proof for the graphs HNSW actually builds, under a stated condition on the data. Rejected for a class of data meeting that condition by datasets on which the cost needed for a fixed recall grows faster than log N. QUESTION-187 asks the same thing as a question; this entry is the answer Malkov and Yashunin propose.

Backlinks