Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 25

Understanding NSW Graph Structure

Recommended resources

Hello and welcome back.

In the last lesson, we established the fundamental distinction between exact k-NN and approximate nearest neighbor (ANN) search. We saw that for massive datasets, the linear O(N) complexity of a brute-force scan is a prohibitive bottleneck. The solution is to trade a small, often negligible, amount of accuracy (recall) for a dramatic gain in search speed. This lesson marks our first step into building such a system.

Our goal is to describe the data structure of a Navigable Small World (NSW) graph, including its nodes, edges, and the critical concept of 'long' vs. 'short' range links. This graph structure is the foundation of many high-performance ANN algorithms and will be the first major data structure we design for our vector database. We will move from the abstract idea of an "index" to the concrete mechanics of a graph that can be navigated efficiently.

From Vectors to a Graph Data Structure

At its core, an ANN index is an intelligent data structure built over our collection of vectors. For graph-based methods like NSW, we represent the entire dataset as a proximity graph. If you've encountered graph theory in your computer science courses, the concepts will be familiar.

HNSW — Small World, Yes- But how in the world is it navigable?

This article provides a simple, intuitive entry point into thinking about data as a graph.

Read the short section titled "Graph Theory". It directly maps the abstract idea of a graph to the problem of searching for similar items. Pay attention to how it defines nodes (our vectors) and edges (the relationships between them).

To be explicit, in our context:

  • Nodes (or Vertices): Each node in our graph represents a single high-dimensional vector from our dataset.
  • Edges (or Links): An edge is a connection between two nodes. In a proximity graph, an edge signifies that the two corresponding vectors are "close" to each other in the vector space, according to our chosen distance metric (e.g., Euclidean distance).

The central challenge is to decide which edges to create. A naive approach might be to connect every node to its k nearest neighbors (a k-NN graph), but this can be computationally expensive to build and can lead to problems during search, as we'll see. A more sophisticated approach is needed to ensure the graph is not only connected, but efficiently navigable.

The Small-World Phenomenon

The "Navigable Small World" name comes from a concept in network theory that you might know as the "six degrees of separation." It describes networks that seem paradoxical: they are highly clustered locally, like a regular grid, yet have a surprisingly short average path length between any two random nodes, like a random graph.

This diagram illustrates the transition from a highly clustered but inefficient **ordered lattice** to a **disordered graph** with short paths but no local structure. The **small-world** network in the middle strikes a balance by incorporating both short-range and long-range links.

This image perfectly captures the idea.

  1. Ordered Lattice (p=0): Imagine nodes arranged in a circle, each connected only to its immediate neighbors. This network has high clustering (your friends are likely friends with each other), but to get from node 'x' to 'y' on the other side requires traversing many short steps. The path length is long. These connections are short-range links.
  2. Disordered Graph (p=1): Now, imagine every connection is completely random. The path between any two nodes is likely very short, but the local structure is gone. There's no clustering.
  3. Small-World (0 < p < 1): The magic happens in between. We start with the ordered lattice and then, with some small probability, "rewire" a few edges to connect to random, distant nodes. These new connections are long-range links or "shortcuts." The presence of just a few of these shortcuts dramatically reduces the average path length across the entire graph, while preserving most of the local clustering.

This combination of dense local connections (short-range links) and sparse global connections (long-range links) is the defining characteristic of a small-world network.

From "Small-World" to "Navigable"

Having short paths is great, but it's only half the battle. We also need a way to find them without having a bird's-eye view of the entire graph. This is the "navigable" property.

The search strategy used in these graphs is a greedy search. Starting from an entry point, you look at all its direct neighbors (its "friends list") and move to the one that is closest to your query vector. You repeat this process, hopping from node to node, always moving to the neighbor that gets you closer to your target.

The problem? In a graph with only short-range links, this greedy approach can easily get stuck in a local minimum. You might reach a node where none of its neighbors are closer to the query, even though a much better candidate exists elsewhere in the graph.

The long-range links are the solution. They act as highways, allowing the greedy search to jump across large regions of the vector space and escape local minima. A truly navigable small-world network is one where the long-range links are structured in a way that makes a greedy search highly likely to succeed.

The following video provides an excellent summary of the NSW graph structure, the search process, and the role of these different link types.

HNSW for Vector Search Explained and Implemented with Faiss (Python)

This video by James Briggs breaks down the components and search mechanics of an NSW graph.

Please watch the section covering Navigable Small World graphs, from the introduction. Focus on the definitions of short-range vs. long-range links, the concept of a vertex's friends list, and the greedy routing search process.

Constructing the NSW Graph for Vector Search

We now have the theoretical ingredients: nodes, edges, short-range links for local navigation, and long-range links for global traversal. How do we build a graph with these properties from a set of vectors?

The construction algorithm, pioneered by Yurii Malkov et al., is elegant in its simplicity. We build the graph incrementally by inserting vectors one at a time in a random order.

For each new vector (node) being inserted:

  1. We find its M nearest neighbors among the nodes already present in the graph. This is done by performing a greedy search from one or more entry points.
  2. We create new edges connecting the new node to these M neighbors.

This randomized, incremental process naturally gives rise to the desired small-world properties:

  • Long-range links are formed organically. The very first few nodes inserted into the graph will be, on average, far from each other. The connections made between them become the structural backbone of the graph, acting as the long-range "highways."
  • Short-range links are formed as the graph becomes denser. As more nodes are inserted, the graph fills in, and a new node is much more likely to find and connect to its true geometric nearest neighbors. These connections provide the fine-grained local structure needed for the final steps of the greedy search.

This article provides a great explanation of how the random insertion order creates the two types of links required.

HNSW — Small World, Yes- But how in the world is it navigable?

This article explains how the construction process of Malkov's NSW algorithm naturally leads to a navigable small-world structure.

Read the section titled "NSW paper — A simple explanation". The key insight is how the random insertion order generates both long-hop and short-hop connections.

The resulting data structure is a single graph where some nodes (especially those inserted early) act as hubs with long-range connections, while most nodes have primarily short-range connections to their local neighborhood. When a search begins, it can use the long-range links to quickly traverse to the correct region of the graph, and then use the short-range links to zoom in and find the precise nearest neighbor.

A simplified visualization of a small-world network. The nodes are connected by edges (links), with some acting as short-range local connections and others as long-range shortcuts spanning the graph.

Conclusion

In this lesson, we deconstructed the Navigable Small World graph, the first high-performance data structure in our project. You now understand how it leverages concepts from network theory to enable fast, approximate searches.

Key Takeaways:

  • An NSW graph represents vectors as nodes and proximity as edges.
  • It combines two types of connections:
    • Short-range links: Connect a node to its immediate neighbors, providing high local clustering and enabling fine-grained search.
    • Long-range links: Act as "shortcuts" across the graph, drastically reducing the average path length and allowing a search to quickly traverse to the right region of the vector space.
  • The structure is built by inserting vectors in a random order, which naturally creates a mix of long-range (early insertions) and short-range (later insertions) links.
  • This specific structure makes the graph navigable using a simple greedy search algorithm, which avoids the O(N) complexity of a brute-force scan.

We have now defined the "what" and the "why" of the NSW data structure. In our next lesson, we will move on to the "how." We will begin the practical implementation by designing the C structs for the graph's nodes and edges, ensuring they are laid out in memory for locality and performance. This will be our first step in translating this powerful concept into efficient code.