Sparse Navigable Graphs for Nearest Neighbor Search
September 24, 2025 (GHC 8102)
Navigability captures the ability of a complex network to support efficient, decentralized search. The concept has a rich history, from Milgram’s "six degrees of separation" to Kleinberg’s computational model of small-world phenomena. Over the past decade, navigable graphs have also emerged as an important principle behind state-of-the-art heuristics for nearest neighbor search. In this talk, I will present a perspective on this development through the lens of approximation algorithms: given a dataset and a distance function, how efficiently can we construct the (approximately) sparsest navigable graph?
Based on joint work with Sanjeev Khanna and Erik Waingarten.