The kernel of graph indices for vector search
This work addresses the limitation of existing graph indices to Euclidean spaces, offering a novel approach for broader vector search applications, though it appears incremental by extending kernel methods to this domain.
The paper tackles the problem of building graph indices for vector search in metric and non-metric spaces, introducing the Support Vector Graph (SVG) with kernel methods and formal navigability guarantees, and shows that popular indices like HNSW and DiskANN are specializations of SVG, with SVG-L0 incorporating sparsity for bounded out-degree.
The most popular graph indices for vector search use principles from computational geometry to build the graph. Hence, their formal graph navigability guarantees are only valid in Euclidean space. In this work, we show that machine learning can be used to build graph indices for vector search in metric and non-metric vector spaces (e.g., for inner product similarity). From this novel perspective, we introduce the Support Vector Graph (SVG), a new type of graph index that leverages kernel methods to establish the graph connectivity and that comes with formal navigability guarantees valid in metric and non-metric vector spaces. In addition, we interpret the most popular graph indices, including HNSW and DiskANN, as particular specializations of SVG and show that new indices can be derived from the principles behind this specialization. Finally, we propose SVG-L0 that incorporates an $\ell_0$ sparsity constraint into the SVG kernel method to build graphs with a bounded out-degree. This yields a principled way of implementing this practical requirement, in contrast to the traditional heuristic of simply truncating the out edges of each node. Additionally, we show that SVG-L0 has a self-tuning property that avoids the heuristic of using a set of candidates to find the out-edges of each node and that keeps its computational complexity in check.