HNSW: Hierarchical Navigable Small World Graphs (Day 4/7)

Welcome back! Yesterday, we introduced approximate search and touched upon Hierarchical Navigable Small World Graphs (HNSW). Today, we’re diving deep into HNSW, understanding its structure and how it achieves a balance between speed and accuracy. As we saw on Day 3, approximate search prioritizes speed over perfect matches, and HNSW is a powerful technique to achieve this.

1. What is HNSW? – A Hierarchical Approach to Similarity Search

HNSW is a graph-based algorithm designed for efficient approximate nearest neighbor (ANN) search. It builds a multi-layered graph where each layer represents a progressively coarser approximation of the data. Think of it like a road map: the highest layer shows major highways connecting cities, while lower layers zoom in to show local roads and streets. This hierarchical structure allows for a rapid initial search at a higher level, followed by refinement at lower levels.

Analogy: Imagine searching for a specific book in a massive library. A flat search would involve checking every book one by one. HNSW is like having a card catalog (high-level graph) pointing to shelves (lower-level graphs). You quickly narrow down your search to a specific shelf, then scan that shelf for the book.

Visual Representation:

┌──────────────┐     ┌───────────────┐     ┌─────────────┐
│   Layer N    │──►  │   Layer 2     │──►  │   Layer 0   │
│ (Coarsest)   │     │ (Medium)      │     │ (Finest)    │
│ Few nodes    │     │ More nodes    │     │ ALL nodes   │
└──────────────┘     └───────────────┘     └─────────────┘
   (Top/Start)                                (Bottom/End)

In HNSW, Layer 0 is the base layer containing all data points. Higher-numbered layers contain progressively fewer nodes. Search starts at the highest layer (e.g., Layer N) and descends to Layer 0, refining the search at each level.

2. Core Concepts: Graphs, Layers, and Navigable Small World Structure

Let’s break down the key components:

• Graph: HNSW represents data as a graph where nodes correspond to data points and edges represent proximity. Edges are weighted, indicating the similarity between connected nodes.
• Layers: As mentioned, HNSW is hierarchical. Each layer contains a subset of the nodes from the layer below, creating a coarser approximation.
• Navigable Small World Structure: This is the crucial part. Each layer is designed to be a “small world” graph, meaning that any two nodes can be reached with a small number of hops. This is achieved by strategically adding edges between nodes, even if they’re not initially close.

Analogy: Think of a social network. A small world network means you’re likely to be connected to anyone else in the network through a relatively short chain of connections.

3. Building the Graph: Adding Edges and Maintaining Proximity

The construction of the HNSW graph is a complex process, but the core idea is to add edges that maintain proximity. When a new data point is added, it’s connected to existing nodes based on their similarity. This process also involves periodic graph rebuilding to ensure the graph remains navigable and efficient.

Simple Python Example (Conceptual – Not a full HNSW implementation):

import random

def add_node_to_graph(graph, new_node, new_vector, existing_vectors, M=3):
    """
    Conceptually adds a new node to the HNSW graph.
    In reality, HNSW connects to NEAREST neighbors, not random ones.
    """
    # Calculate distances to all existing nodes
    distances = []
    for i, vec in enumerate(existing_vectors):
        dist = np.linalg.norm(new_vector - vec)
        distances.append((i, dist))
    
    # Sort by distance and connect to M nearest neighbors
    distances.sort(key=lambda x: x[1])
    neighbors = distances[:M]
    
    for neighbor_id, dist in neighbors:
        print(f"Adding edge: {new_node} ↔ Node_{neighbor_id} (distance: {dist:.3f})")
    
    return neighbors
# Example Usage (Conceptual)
data_points = ["A", "B", "C", "D", "E"]
new_node = "F"
add_node_to_graph(data_points, new_node, data_points)

4. The Search Process: Traversing the Layers

The search process starts at the highest layer and gradually descends to lower layers. At each layer, a limited number of candidate neighbors are selected based on their similarity to the query point. This process continues until a satisfactory set of nearest neighbors is found.

Analogy: Imagine searching for a restaurant on a map. You first look at the major highways to find a general area. Then, you zoom in to the city level, and finally, to the street level to pinpoint the restaurant.

Simplified Python Example (Conceptual Search):

def search_hnsw(graph, query_point, num_neighbors):
    """
    Conceptual search function - doesn't implement the full HNSW traversal.
    """
    # 1. Start at the highest layer (assuming we have a layered graph)
    # 2. Find candidate neighbors at the current layer
    # 3. Descend to the next layer and refine the search
    # 4. Repeat until a satisfactory set of neighbors is found

    print(f"Searching for {num_neighbors} nearest neighbors to {query_point}")
    # Placeholder for actual search logic
    return ["Neighbor 1", "Neighbor 2", "Neighbor 3"]

# Example Usage (Conceptual)
query_point = "X"
nearest_neighbors = search_hnsw(None, query_point, 3)
print(f"Nearest neighbors to {query_point}: {nearest_neighbors}")

5. Comparing HNSW to Flat Search and Annoy

Let’s put HNSW in perspective.

As we saw on Day 3, Annoy (Another Nearest Neighbors library) is a good option for many applications, but HNSW generally offers better performance, especially for very large datasets and high-dimensional data, at the cost of higher memory usage.

6. Practical Considerations and Trade-offs

• Memory Usage: HNSW graphs can be quite large, requiring significant memory.
• Construction Time: Building the graph can be time-consuming, especially for large datasets.
• Parameter Tuning: HNSW has several parameters that need to be tuned for optimal performance.
• Dynamic Data: Handling Dynamic Updates (data that changes frequently) can be challenging. Insertions: HNSW supports adding new points efficiently Deletions: Challenging – typically require marking as deleted or rebuilding Best for mostly-read workloads with periodic batch updates"

7. A More Realistic Example: Using a HNSW Library (Python – ScaNN)

While we’re not building HNSW from scratch, using a library demonstrates how it’s applied in practice. We’ll use ScaNN (Scalable Nearest Neighbors) which provides an efficient HNSW implementation.

# This example requires ScaNN to be installed: pip install scann
import numpy as np
from scann import Index

# Sample data (replace with your actual data)
data = np.random.rand(1000, 128)  # 1000 data points, 128 dimensions

# Build the index
# Build the HNSW index with proper parameters
index = Index(
    data.shape[1],  # 128 dimensions
    M=16,           # Max connections per node (typical: 12-48)
    ef_construction=200,  # Construction search parameter
    ef_search=50    # Search-time parameter (higher = more accurate, slower)
)
index.build(data)

# Build the HNSW-based index
searcher = scann.scann_ops_pybind.builder(data, 10, "dot_product") \
    .tree(
        num_leaves=100,
        num_leaves_to_search=10,
        training_sample_size=1000
    ) \
    .score_ah(2, anisotropic_quantization_threshold=0.2) \
    .reorder(100) \
    .build()

# Query
query_vector = np.random.rand(128).astype(np.float32)
neighbors, distances = searcher.search(query_vector, final_num_neighbors=5)

print("Nearest Neighbor Indices:", neighbors)
print("Distances:", distances)

Explanation:

• We generate random data for demonstration. Replace this with your actual data.
• Index(data.shape[1], 10) creates an HNSW index with 10 layers. Experiment with the number of layers.
• index.build(data) builds the HNSW graph.
• index.search(query_vector, 5) performs the nearest neighbor search.

This example highlights the ease of using HNSW through a dedicated library. The complexity of the underlying algorithm is abstracted away, allowing you to focus on your application.

In conclusion, HNSW provides a powerful approach to approximate nearest neighbor search, offering a compelling balance between speed and accuracy. By understanding its hierarchical structure and key components, you can leverage this technique to tackle challenging similarity search problems. Remember to consider the trade-offs and experiment with different parameters to optimize performance for your specific application.