What is a directed graph?
A directed graph is a graph in which each edge has a direction — it runs from one specific node to another, and the existence of an edge from node A to node B says nothing about whether an edge exists running from B back to A. That single distinction, direction, changes almost everything about how a graph gets built, stored, and traversed, and it turns out to matter quite a bit for how a proximity graph used in nearest-neighbor search actually behaves once it’s built.
What does direction actually change about how a graph works?
In an undirected graph, a connection between two nodes is symmetric by definition — if A is connected to B, B is connected to A, full stop, and there’s only one relationship to represent. A directed graph drops that symmetry. Each edge is really an ordered pair: it has a source node and a target node, and the relationship it represents only holds in that one direction unless a separate edge exists running the other way. This means a directed graph can represent things an undirected graph structurally cannot — a one-way dependency, a citation from one paper pointing to another, a road that only allows traffic in one direction — where the relationship genuinely isn’t symmetric and forcing it to be would misrepresent the underlying thing being modeled.
This distinction ripples into how the graph is stored and traversed. A node’s out-degree — the number of edges leaving it — and its in-degree — the number of edges arriving at it — become two separate numbers rather than one combined degree, and a traversal that follows edges in their stored direction can only move from a node to the targets of its outgoing edges, never backward along an edge that was defined as pointing the other way, even if that seems like the more useful direction to travel in at some point during the search.
Why would a nearest-neighbor graph end up directed in the first place?
The most common source of directed edges in a proximity graph built for search comes from how the graph is actually constructed rather than from any deliberate choice to model asymmetry. A typical construction process builds a k-nearest-neighbor graph by giving each node an edge to each of its own k nearest neighbors, computed independently for every node. Nearness, as measured this way, is not necessarily a symmetric relationship: point A can easily have point B among its k closest neighbors while B, sitting in a denser region of the space with many points closer to it than A is, does not have A among its own k closest neighbors. When each node’s edges are chosen purely based on that node’s own nearest neighbors, the result is naturally a directed graph, with some edges only existing in one direction because the closeness relationship that produced them wasn’t mutual to begin with.
This is exactly the kind of asymmetry that HNSW‘s construction process is built to correct rather than tolerate. When a new node is inserted and connected to a set of neighbors chosen by the neighbor-selection heuristic, HNSW deliberately adds the reverse edge as well, so that if the new node connects to an existing node, that existing node also gets an edge back to the new node. This is usually described as making the connection bidirectional rather than saying the graph itself is undirected, because the mechanism used to guarantee it — explicitly inserting both edges — is a directed-graph technique being used to simulate the symmetry an undirected graph would provide automatically. The distinction matters for understanding the code: an HNSW implementation’s neighbor lists are directed adjacency lists that happen to be kept symmetric by convention and by the insertion logic, not an undirected structure that enforces symmetry by construction.
Why does this distinction matter for how HNSW actually behaves in practice?
Bidirectional connections matter for HNSW’s search guarantees in a very concrete way: if a search reaches node A and A’s edge to B were one-directional in the wrong sense — an edge that only existed as “B points to A” rather than the reverse — the search could never use that edge to move from A onward to B, even though B might be exactly the useful next hop toward the query. Keeping edges bidirectional means that once two nodes are connected, either one can serve as a stepping stone toward the other regardless of which node happened to initiate the connection during construction, which is important because insertion order in HNSW is essentially arbitrary and unrelated to where the final query workload will actually search.
There’s a subtlety worth being precise about, though: bidirectional in this context means both directed edges exist, not that they’re guaranteed to stay that way forever. Because each node’s neighbor list has a maximum capacity, adding a new bidirectional connection to a node whose list is already full can trigger pruning that drops one of that node’s existing edges — and if the dropped edge was one half of what had been a bidirectional pair, the graph can end up with a one-directional edge as a side effect of capacity management, even though the initial insertion always tries to keep both directions. Production implementations generally accept this as a normal, self-correcting part of graph maintenance rather than treating it as a bug, since a search that can’t traverse one specific one-directional leftover edge in a particular direction usually has other equally good paths available elsewhere in a well-connected graph.
Having seen how direction and its usual counterpart — enforced bidirectionality — shape how a proximity graph gets built, the undirected graph glossary page is a useful next stop for seeing the contrast directly, since it covers the simpler case where symmetry is guaranteed by the structure itself rather than maintained by convention. From there, the adjacency list page shows the actual data structure typically used to store these directed, per-node neighbor relationships in memory, which is the representation HNSW implementations build on directly.