What is bidirectional connection during insertion?
Bidirectional connection during insertion is the specific step, occurring immediately after the neighbor-selection heuristic has chosen a new node’s connections at a given layer, where each of those chosen connections gets established in both directions at once — the new node gets an edge to the selected neighbor, and that neighbor also gets a reverse edge back to the new node. It’s the concrete, step-by-step moment where the bidirectional-edge property described elsewhere in this glossary actually gets enforced during construction, and walking through exactly how it plays out clarifies why this one step is also where neighbor-list overflow and pruning most commonly get triggered.
What actually happens, in sequence, once the neighbor-selection heuristic has finished choosing a set of neighbors for the new node?
For each neighbor the heuristic selected, two things happen. First, that neighbor’s identifier gets added to the new node’s own neighbor list at the current layer — straightforward, since the new node’s own neighbor list started empty at this layer and has plenty of room to add every selected connection up to its capacity. Second, and more consequentially, the new node’s identifier gets added to that existing neighbor’s own neighbor list at the same layer, establishing the reverse direction of the same connection. This second half of the step is where things can get more involved, because the existing neighbor’s list wasn’t necessarily empty or even partially full — it might already be sitting right at its own capacity, having accumulated connections from its own original insertion and from other, earlier insertions that also chose to connect to it.
If the existing neighbor’s list has room, the reverse connection simply gets appended, and both halves of the bidirectional edge now exist cleanly. If the existing neighbor’s list is already full, this triggers exactly the overflow-and-pruning mechanism described on the neighbor-list-overflow glossary page: the neighbor-selection heuristic re-runs over that existing neighbor’s current connections plus the new incoming one, and the result gets pruned back down to fit within capacity, potentially dropping one of the existing neighbor’s previous connections to make room for the new one, or rejecting the new connection outright if the heuristic judges it a worse fit than everything already present.
Why does this step matter so much for the overall shape and quality of the finished graph, beyond just the new node’s own connections?
This is the mechanism through which a single insertion’s effects ripple outward beyond the new node itself — every bidirectional connection formed potentially disturbs an existing node’s own neighbor list, and if that existing node’s list was already full, the disturbance can genuinely change which connections that older node keeps, well after its own original insertion was complete. This is precisely why a node’s final set of connections, at any given point during an actively growing index, can look meaningfully different from what its own insertion-time selection process originally produced — later insertions, through this bidirectional-connection step, continue to reshape existing nodes’ connectivity throughout the life of the index.
This ripple effect is also part of why insertion order can influence the finished graph‘s exact structure, as covered on the insertion-order-sensitivity glossary page — a node inserted early sees relatively few bidirectional-connection disturbances from subsequent insertions if it doesn’t happen to be a popular connection target, while a node that turns out to sit in a densely connected region of the graph might have its neighbor list revisited and reshaped many times over as later insertions repeatedly try to connect back to it.
Does this step ever fail to actually establish a genuine bidirectional connection, and what happens then?
Yes — this is exactly the scenario that can produce the occasional one-directional leftover edge described on the directed-graph glossary page. If the reverse connection gets pruned away during the overflow-handling process described above, while the forward connection from the new node to the existing neighbor remains intact, the pair ends up asymmetric: the new node has an edge pointing to the existing neighbor, but that existing neighbor no longer has a corresponding edge pointing back. This is a normal, expected, and generally harmless consequence of enforcing capacity limits consistently across every node in the graph — it isn’t treated as an error condition, since the alternative would be allowing some nodes’ degree to grow unboundedly whenever they happen to be popular connection targets, which is exactly the outcome the capacity limits exist to prevent in the first place.
Having covered exactly how a new node’s chosen connections get established in both directions, and what happens when an existing neighbor’s list is already full, the neighbor-list-overflow and neighbor-selection-heuristic glossary pages are worth revisiting together with this fuller step-by-step picture. From there, the insertion-order-sensitivity glossary page picks up the broader consequence of this mechanism, showing how repeated bidirectional-connection events across many insertions accumulate into the order-dependent effects that page describes.