Graph Algorithms: K-Nearest Neighbor Insertion

The Logic of Graph Construction: Iterative Insertion

A Navigable Small World graph isn't built all at once. It's grown organically, one node at a time. The process is conceptually straightforward:

1. Start with an empty graph. The first vector inserted becomes the initial node and, for a time, the graph's only entry point.
2. For every subsequent vector, we insert it as a new node.
3. To integrate this new node into the graph, we find its closest M neighbors among the nodes already in the graph.
4. Finally, we create edges, connecting the new node to these M neighbors.

This iterative process, repeated for all vectors, gradually builds the network of short- and long-range links that makes the NSW graph efficient to search.

The following video gives a quick, high-level overview of this iterative construction.

Reusing Our Search Algorithm for Insertion

The most crucial step in the insertion process is finding the M nearest neighbors for the new vector. How do we do this efficiently? We reuse the very nsw_search function we developed in the last lesson!

By treating the vector we want to insert as a query_vector, we can call nsw_search to find its approximate nearest neighbors within the current state of the graph. This is a powerful example of component reuse in systems design. The same core logic that finds neighbors for a query is used to find neighbors for a new node during construction.

Let's look at the formal algorithm for this process.

The Nearest_Neighbor_Insert algorithm presented in the paper can be broken down as follows:

1. neighbors <- k-NNSearch (new_object, w, f): This is the core step. It uses a k-NN search function to find f nearest neighbors for the new_object.
   • In our implementation, this corresponds to calling our nsw_search function.
   • new_object is the vector we are inserting.
   • f is a parameter we'll call M, the number of neighbors we want to connect to the new node.
   • w is the search beam width, which we called ef in the last lesson. For construction, this is often a distinct parameter, efConstruction, allowing us to tune search thoroughness during indexing independently from query time.
2. for (...) do ... neighbors[i].connect(new_object); new_object.connect(neighbors[i]);: This loop establishes the connections. Since we are building an undirected graph, the connections must be bidirectional. For each neighbor found, we add the new node to its friend list, and we add the neighbor to the new node's friend list.

Connection Management: The Pruning Heuristic

Simply adding connections isn't enough. A critical aspect of maintaining a high-performance graph is managing node degree (the number of connections a node has). If we only ever add edges, some popular or centrally located nodes might accumulate thousands of connections, becoming "hubs." When our greedy search algorithm encounters such a hub, it must calculate the distance to all of its thousands of neighbors, creating a significant performance bottleneck.

To prevent this, we must enforce a hard limit on the number of connections a node can have, a parameter often called M_max.

When we add a new node N and connect it to its neighbor B, B's connection count increases by one. If this new count exceeds M_max, we must prune one of B's connections. Which one? We shouldn't just remove a random edge. The best heuristic is to re-evaluate all of B's neighbors (including the newly added N) and keep only the M_max closest ones. This ensures that each node's connections remain a high-quality set of its nearest neighbors.

This pruning step is a vital, low-level detail that directly impacts the performance characteristics of the final data structure.

Visualizing the Full Insertion Process

The image below shows the insertion of a new node (the blue one). While it depicts a multi-layered HNSW graph (which we will build in a later module), the principle within a single layer is identical to our NSW insertion.

For our current task, you can imagine this process happening entirely on a single plane (Layer 0). The core steps are universal: find the neighbors, and connect to them.

C Implementation Guidance

Based on this logic, we can define a C function to handle the insertion of a single vector.

#include <stdint.h>

// Forward declaration from our existing data structures
typedef struct HNSWGraph HNSWGraph;

/**
 * @brief Inserts a new vector into the NSW graph.
 * 
 * This function finds the nearest neighbors for the new vector and establishes
 * bidirectional connections. It also handles connection pruning for any
 * neighbors that exceed their maximum connection limit.
 *
 * @param graph A pointer to the initialized HNSWGraph.
 * @param new_node_index The index of the new node being inserted.
 * @param M The target number of neighbors to connect to the new node.
 * @param M_max The maximum number of connections any node is allowed.
 * @param ef_construction The size of the candidate list for the neighbor search.
 */
void nsw_insert(
    HNSWGraph* graph, 
    uint32_t new_node_index,
    int M,
    int M_max,
    int ef_construction
);

Your task is to implement the body of this nsw_insert function. The steps are:

1. Handle the Entry Point: If the graph is empty, designate new_node_index as the entry point and return.
2. Find Neighbors: Call your nsw_search function. The query_vector will be the vector at new_node_index. Use ef_construction as the search beam width and M as the number of neighbors to find (k).
3. Connect New Node: For each of the M neighbors found, add its index to the adjacency list of new_node_index.
4. Connect Neighbors and Prune: For each of the M neighbors:
   • Add new_node_index to its adjacency list.
   • Check if its connection count now exceeds M_max.
   • If it does, perform the pruning heuristic: find the true M_max nearest neighbors from its updated list of connections and update its adjacency list to contain only those M_max nodes.

Conclusion

Today, we've designed the algorithm for constructing our NSW graph. We've seen how the search functionality we previously built is a fundamental building block for the insertion process itself. By combining search with intelligent connection management, we can iteratively grow an efficient graph structure.

Key Takeaways:

• Iterative Construction: NSW graphs are built by inserting vectors one at a time.
• Insertion via Search: The nsw_search algorithm is reused to find the M nearest neighbors for each new node.
• Bidirectional Connections: Edges in an NSW graph are typically undirected, requiring you to update the adjacency lists of both the new node and its selected neighbors.
• Connection Pruning: Enforcing a maximum number of connections (M_max) per node is crucial for maintaining search performance. This is done by pruning a node's connections to keep only its nearest neighbors if the limit is exceeded.

With both search and insertion algorithms now designed, we have a complete, functional NSW implementation. In the next lesson, we will finally put it to the test. We'll benchmark the search speed and recall of our NSW implementation against the brute-force k-NN search baseline, quantifying the immense performance gains our approximate search structure provides.