Hierarchical navigable small worlds

Hierarchical navigable small world (HNSW) is an efficient graph-based algorithm used for Approximate Nearest Neighbor (ANN) search, particularly in high-dimensional spaces. In this topic, we will explore the core concepts of HNSW, how to implement it with the Faiss library, and its main limitations.

Overview of HNSW

Hierarchical navigable small world (HNSW) is a graph-based nearest neighbor indexing algorithm used for Approximate Nearest Neighbor (ANN) search. HNSW belongs to the family of proximity graphs, where nodes or vertices are linked based on their closeness, typically measured using Euclidean distance. It builds a multi-layer structure that combines two techniques:

1. Probabilistic skip lists are built with multiple layers of linked lists, where the first layer contains links that skip over many nodes, and the number of skips decreases as we move down the layers. The upper levels contain only a few points, while the lower levels contain all points. To search, we start at the top layer and move right, dropping to the next layer if the current node's key is greater than the target key or if the end of the layer is reached. This top-down navigation process allows us to first locate an approximate region and then refine the result as we move down through the layers:

   
   

2. Navigable small world (NSW) graphs use long-range connections to link different parts of the network, which helps find paths faster. The first node inserted serves as the starting point for searches, and as new nodes are added, they connect to their closest neighbors. The greedy search algorithm, used in NSW, operates by evaluating the neighbors of the current node at each level. At each step, it rapidly moves towards the target vector without having to scan the entire graph. This process repeats until no better neighbor is found, and a local minimum is reached:

In NSW graphs, high-degree vertices are connected to many neighbors, facilitating fast exploration, while low-degree vertices have fewer connections, ensuring more accurate and localized nearest neighbor searches:

A key characteristic of HNSW is that any point in the dataset can be reached within just a few steps through its multi-layered graph structure. This hybrid structure optimizes both search and insert operations, reducing time complexity to $O(\log(n))$ on average. In optimized setups, even with millions of vectors, inserting new vectors and searching for nearest neighbors can be done in milliseconds, especially when GPU acceleration is used.

Graph Construction

To understand how HNSW graphs are built, let’s explore the process of constructing and organizing the graph using Facebook AI Similarity Search (Faiss) and numpy libraries as an example.

First, we need to install the necessary dependencies:

pip install faiss-cpu numpy

To get started with Faiss, the power of your processor (CPU) will generally be sufficient for most tasks. Once packages is installed, we can import libraries in our code:

import faiss
import numpy as np

Next, when initializing an HNSW index, we specify the vector dimensionality (d) and the number of neighbors per vertex (M), where $d$ defines the vector size, and $M$ controls connectivity, affecting both the number of levels and the number of neighbors at each level. To create the index with the specified parameters, we can use the faiss.IndexHNSWFlat function:

# Parameters for HNSW
d = 128
M = 32
# Initialize the HNSW index
index = faiss.IndexHNSWFlat(d, M)

In addition, there are two important parameters that Faiss automatically configures during our index initialization:

• The $M_{\text{max}}$ parameter is automatically set to the value of $M$ and determines the maximum number of neighbors that can be added to a vertex at any level.

• The $M_{\text{max}_0}$ parameter is set to $2M$ and is used internally to manage connectivity at the base level (level 0) of the graph.

After the initialization of the index and setting these parameters, the next step is to generate and add embeddings to the index using the index.add(xb) method:

# Generate random data embeddings: 1000 vectors, each of dimension 128
xb = np.random.random((1000, 128)).astype('float32')
# Add embeddings to the HNSW index
index.add(xb)

Once the data embeddings are inserted into the graph, this is when the levels and connectivity structure are actually established. At this stage, the levels within the graph are populated, and the HNSW graph structure becomes fully functional. Now, we can inspect the highest level in the graph. This will tell us how many hierarchical layers have been created:

# Returns the highest level in the HNSW graph
index.hnsw.max_level

Also, we can examine the level distribution to understand how the vertices are spread across the different levels using np.bincount():

# Displays the distribution of vertices across different levels
levels = faiss.vector_to_array(index.hnsw.levels)
np.bincount(levels)

As you can see, the majority of vectors typically reside at the base level (level 0), while higher levels contain progressively fewer vectors. The upper layers include sparse, long-range connections that enable fast traversal across the graph, whereas the lower layers are densely connected to support accurate nearest neighbor searches.

With the HNSW graph created, we can now proceed to the search process.

Search Process

In addition to the parameters we’ve already covered, Faiss automatically initializes key search-related settings, including efConstruction and efSearch. The quality of the constructed graph heavily depends on the efConstruction parameter, which determines the thoroughness of the index-building process. Higher values of efSeach improve search accuracy but increase the time required for index construction.

You can inspect the values of these parameters to understand the current configuration of the HNSW index and make adjustments based on your specific needs:

print("efConstruction:", index.hnsw.efConstruction)
print("efSearch:", index.hnsw.efSearch)

To ensure efficient traversal during search, each node in the HNSW graph is connected to a set of neighbors. These connections allow the algorithm to dynamically choose optimal paths, minimizing unnecessary computations:

The search process begins at a designated entry point, typically located at the highest level of the HNSW graph. This point guides the algorithm through the graph layers toward the most relevant results. You can retrieve the entry point and its level using:

# Identify the entry point of the HNSW graph
print("Entry point:", index.hnsw.entry_point)
# Retrieve the level of the entry point
entry_point_level = levels[entry_point]
print("Entry point level:", entry_point_level)

The entry point initiates the search process, which proceeds in several key stages:

1. The search starts by making large jumps across the dataset to quickly identify relevant regions.

2. As the search moves downward through the layers, it gradually focuses on the most similar neighbors, refining the results.

3. At the lowest layer, the search becomes exhaustive, utilizing the efSearch parameter to identify the top-K closest neighbors, ultimately determining the final set of nearest neighbors:

To demonstrate the search in practice, we can now retrieve the top 3 nearest neighbors for the first 10 query vectors using the index.search() method:

# 1000 query vectors with the same dimensionality as our HNSW index
xq = np.random.random((1000, 128)).astype('float32')

# Perform the search on the first 10 query vectors for the top 3 nearest neighbors
D, I = index.search(xq[:10], k=3)

# Print the distances and indices of the nearest neighbors
print("Distances of nearest neighbors:", D) 
print("Indices of nearest neighbors:", I)  

This will return the distances and corresponding indices of the top 3 most similar vectors for each of the 10 query vectors and highlights how efficiently HNSW processes the results, typically within just a few milliseconds. However, this speed comes with trade-offs, which we will explore in the next section.

Limitations

HNSW provides a well-balanced indexing approach that can be optimized for higher quality by adjusting M, efSearch, and efConstruction. However, it comes with several limitations:

1. HNSW requires a significant amount of memory to store the graph, as each vector is connected to multiple neighbors across different levels. This results in higher memory usage compared to other indexing structures, making it less ideal for applications with billions of vectors, especially when RAM is limited.

2. When RAM is not a constraint, tuning parameters allows for a trade-off between speed and accuracy. A lower parameter set ensures faster search times while maintaining good quality, while a higher parameter set enhances search precision at the cost of slightly slower retrieval.

3. Although the layered graph structure of HNSW is conceptually simple, its implementation is complex. Managing the layers and distance comparisons requires careful coordination, making modifications and extensions of the implementation challenging.

Overall, HNSW provides an efficient solution for many use cases but comes with limitations that need to be considered based on requirements.

Conclusion

As a result, you now have an understanding of the following:

• The hierarchical navigable small world (HNSW) algorithm, its graph construction process, and how it optimizes search efficiency.

• How to implement HNSW with the Faiss library, covering indexing, vector addition, graph inspection, and performing search operations.

• The key trade-offs of HNSW, such as its speed and accuracy advantages, increased memory usage, and the complexities of parameter tuning.