What is an edge in a graph?

An edge is the connection between two nodes in a graph — the thing that actually turns a bare collection of nodes into a graph in the first place. Where a node represents a single entity, an edge represents a relationship between two of them, and everything a graph is capable of expressing about how its entities relate to each other lives entirely in the set of edges it contains. In a proximity graph built for nearest-neighbor search, an edge typically means “these two points are close enough, by whatever distance measure the graph uses, that a search should be able to move directly between them.”

What information does an edge actually carry?

At minimum, an edge is just a pair of node identities — it points to the two nodes it connects and nothing else. Many graphs stop there, but it’s common for an edge to carry additional information beyond just which two nodes it links. A weighted edge attaches a number to the connection, typically representing distance, cost, or strength of relationship, and that weight is exactly what a proximity graph needs, since the whole point of connecting two nodes is to represent how close they are, not merely that some connection exists. An unweighted edge, by contrast, only records the fact of a connection and treats every edge as equivalent regardless of what it represents.

Whether an edge is directed or undirected — covered in more depth on their own glossary pages — is really a statement about what an edge means rather than a separate kind of edge object. A directed edge is a connection with an implied direction, so an edge from A to B is a distinct thing from an edge from B to A, while an undirected edge treats the connection as inherently mutual. Most graphs pick one convention and apply it consistently across every edge, since mixing directed and undirected semantics in the same graph tends to create ambiguity about what a traversal is actually allowed to do at each edge it encounters.

What role does an edge’s weight play in a proximity graph specifically?

In a proximity graph, the weight attached to an edge is usually the distance between the two vectors the connected nodes represent, computed under whichever distance function the index was built with — Euclidean distance, cosine distance, or one of the other options covered on the vector and distance math glossary pages. This weight is what a greedy search algorithm actually reads at every step: when deciding which neighbor to move to next, the algorithm compares the weights of the edges leading to unvisited neighbors and prefers the one leading toward the node closest to the query. Without a distance recorded on the edge — or, more precisely, computed fresh from the two vectors the edge connects, since most implementations calculate distance on demand rather than storing it permanently — a graph would have no way to express which of its connections are actually worth following first during a search.

It’s worth being precise here about a detail that trips people up: HNSW implementations generally don’t store a numeric weight directly on each stored edge the way a classic weighted-graph textbook example might. Instead, an edge is represented simply as a reference from one node’s neighbor list to another node’s identity, and the distance between them gets recomputed by running the distance function against their two vectors whenever the search actually needs that value. This is a deliberate space-saving choice — storing a precomputed distance on every edge would mean updating that stored value any time the underlying vectors changed, whereas recomputing it fresh guarantees it’s always correct and costs only a single distance calculation, which HNSW‘s design already assumes is cheap enough to do frequently.

How do edges accumulate into the connectivity a search algorithm actually relies on?

A single edge on its own doesn’t do much — its value comes from how the full set of edges in the graph combine to create paths between nodes that aren’t directly connected. A search algorithm never has direct access to the whole graph at once; it can only see the edges leading out of whatever node it currently occupies, which is exactly why the specific set of edges chosen during construction matters so much. Too few edges, or edges chosen without a diversification strategy, and a search can walk into a dead end with no good path forward, a failure mode described more fully on the missing-bridge-in-connectivity glossary entry. This is also the reason HNSW’s neighbor-selection heuristic goes out of its way to choose a diverse, well-spread-out set of neighbors for each node rather than always picking the naively closest ones, since a handful of well-chosen edges create far more useful paths through the graph than a larger number of redundant ones clustered in the same direction.

Having covered what an edge is and how its weight functions in a distance-based graph, the adjacency list glossary page is the natural next stop, since it shows exactly how a node’s set of outgoing edges gets stored and looked up in practice. From there, the neighbor list and neighbor-list capacity pages go into more depth on the specific constraints HNSW places on how many edges a single node is allowed to keep, which is where the abstract idea of an edge turns into one of the central tuning levers of the whole algorithm.