Connecting Nodes: Bidirectional Logic

The Logic of Bidirectional Connection

After the hnsw_select_neighbors_heuristic function provides us with the M best neighbors for our new node q on a given layer l, we need to update the graph's data structures. This is a two-way street:

1. New Node (q) -> Neighbors (n_i): For layer l, we add each of the M selected neighbors to q's own neighbor list. Since q is new, this list is initially empty, making this step a simple append operation.
2. Neighbors (n_i) -> New Node (q): For each selected neighbor n_i, we must also add q to n_i's neighbor list on layer l. This is where the complexity lies. The neighbor n_i is an existing node and may already have a full list of connections.

This process is clearly laid out in the "Building HNSW from Scratch" guide. Let's examine the Python implementation, as it provides a clear blueprint for our C code.

As you can see, the implementation handles the two directions of the connection separately and addresses the "overflow" scenario head-on.

Handling Connection Overflow and Pruning

Every node in the graph (except on layer 0) is limited to M_max connections per layer. Layer 0 often gets a higher limit, M_max0, typically 2 * M_max, because it's the layer where the final, most precise search happens, and denser connectivity improves accuracy. Your interest in system design will recognize this as a classic trade-off: these limits ensure that the memory footprint of each node is bounded and predictable, preventing "super-nodes" that could become performance bottlenecks, at the cost of needing a strategy to manage the limit.

When we try to add our new node q to a neighbor n's list and find it's already full (i.e., n has M_max connections), we have an overflow. We can't simply add another connection. Instead, we must perform connection pruning:

1. The set of potential neighbors for n is now its M_max old neighbors plus the new node q, for a total of M_max + 1 candidates.
2. We must decide which one to evict to bring the count back down to M_max.
3. The simplest and most common strategy is to evict the worst neighbor. In the context of HNSW, "worst" means the one that is furthest away from n.

The logic from the Medium article you just read implements exactly this:

• It calculates the distance from the candidate (n) to the new node (q).
• It then finds the "worst neighbor" currently connected to n by iterating through them and finding the one with the maximum distance (or minimum similarity).
• If the new connection to q is better (i.e., q is closer to n than the worst neighbor is), the worst neighbor is removed, and q is added.
• If q is further away than all of n's existing neighbors, the connection is rejected, and n's neighbor list remains unchanged.

This pruning process is fundamental to maintaining the graph's quality over many insertions.

The interactive article on HNSW architecture also describes this overflow handling, framing it as a re-evaluation of the neighbor list to maintain connection diversity.

Note that the article mentions using the diversity heuristic for pruning. While this is the most robust method, it's computationally expensive. For our implementation, the simpler distance-based eviction described in the Medium article is highly effective and a common choice.

C Implementation Task

Now it's time to translate this logic into C. You will implement a function, hnsw_connect_neighbors, that takes the new node's ID, its list of selected neighbors for a specific layer, and establishes the bidirectional connections, including the pruning logic.

Here is a skeleton. Your task is to complete the implementation based on the logic we've discussed.

#include <stdbool.h>
#include <stdlib.h>
#include <float.h>

// Assume the following structs and functions are defined:
// typedef struct {
//     int* neighbors;
//     int count;
//     int capacity; // M_max for this layer
// } HNSWLayer;

// typedef struct {
//     int id;
//     float* vector;
//     HNSWLayer* layers;
//     int max_layer;
// } HNSWNode;

// typedef struct {
//     HNSWNode* nodes;
//     // ... other fields
// } HNSW;

// HNSWNode* hnsw_get_node(HNSW* hnsw, int id);
// float hnsw_distance(const float* vec1, const float* vec2, int dim);

/**
 * @brief Creates bidirectional connections for a new node on a specific layer.
 *
 * @param hnsw Pointer to the HNSW index.
 * @param new_node_id The ID of the node being inserted.
 * @param neighbors An array of neighbor IDs selected by the heuristic.
 * @param neighbor_count The number of neighbors in the array (should be <= M).
 * @param layer_level The layer on which to create connections.
 * @param dim The dimension of the vectors.
 */
void hnsw_connect_neighbors(HNSW* hnsw, int new_node_id, int* neighbors, int neighbor_count, int layer_level, int dim) {
    HNSWNode* new_node = hnsw_get_node(hnsw, new_node_id);
    HNSWLayer* new_node_layer = &new_node->layers[layer_level];

    // Part 1: Connect the new node TO its selected neighbors.
    // This is simple, as the new node's neighbor list is empty.
    for (int i = 0; i < neighbor_count; i++) {
        new_node_layer->neighbors[i] = neighbors[i];
    }
    new_node_layer->count = neighbor_count;

    // Part 2: Connect each neighbor back TO the new node (bidirectional part).
    for (int i = 0; i < neighbor_count; i++) {
        int neighbor_id = neighbors[i];
        HNSWNode* neighbor_node = hnsw_get_node(hnsw, neighbor_id);
        HNSWLayer* neighbor_layer = &neighbor_node->layers[layer_level];

        // Check if the neighbor's connection list for this layer is full.
        if (neighbor_layer->count < neighbor_layer->capacity) {
            // Happy path: there is room. Just add the new node.
            neighbor_layer->neighbors[neighbor_layer->count] = new_node_id;
            neighbor_layer->count++;
        } else {
            // Unhappy path: overflow. We need to prune.
            // Find the worst (most distant) neighbor currently in the list.
            float max_dist = -1.0f;
            int worst_neighbor_idx = -1;

            for (int j = 0; j < neighbor_layer->count; j++) {
                int current_neighbor_id = neighbor_layer->neighbors[j];
                HNSWNode* current_neighbor_node = hnsw_get_node(hnsw, current_neighbor_id);
                float dist = hnsw_distance(neighbor_node->vector, current_neighbor_node->vector, dim);
                if (dist > max_dist) {
                    max_dist = dist;
                    worst_neighbor_idx = j;
                }
            }

            // Calculate the distance of the new connection.
            float new_dist = hnsw_distance(neighbor_node->vector, new_node->vector, dim);

            // If the new connection is better than the worst existing one, replace it.
            if (new_dist < max_dist) {
                neighbor_layer->neighbors[worst_neighbor_idx] = new_node_id;
            }
        }
    }
}

This function is the final step in processing a single layer during insertion. The main insertion algorithm will call this function for each layer, from the new node's maximum assigned layer down to layer 0, using the neighbors selected for that specific layer.

Conclusion

You have now implemented one of the most critical parts of the HNSW insertion algorithm. Creating bidirectional connections transforms a mere collection of nodes into a navigable graph. More importantly, you've addressed the hard constraint of M_max by implementing a connection pruning strategy. This ensures the graph's structure remains efficient and its memory usage predictable—key concerns in any high-performance system.

Key Takeaways:

• Creating connections in HNSW is a bidirectional process: the new node connects to its neighbors, and those neighbors must connect back.
• Existing nodes have a maximum connection limit (M_max for upper layers, M_max0 for layer 0) to maintain a bounded memory footprint and graph structure.
• When adding a link to a node with a full neighbor list, connection pruning is necessary.
• A common and effective pruning strategy is to replace the "worst" (most distant) existing neighbor if the new connection is closer.

In the next lesson, we will put all the pieces of the insertion process together. You've implemented layer assignment, searching for candidates, heuristic selection, and now connection creation. We will assemble these into the complete INSERT algorithm, solidifying your understanding of how an HNSW graph is built from the ground up.