Graph theory fundamentals

Graph theory fundamentals name the abstract shape of HNSW: nodes, edges, degree, paths, connectivity, hubs, bridges, and traversals - the language shared by NSW, HNSW, and other proximity-graph indexes.
Created: Updated: 3 min read

These are the topics in this section, each on its own page with a stable path you can bookmark or share.

What topics are covered in this section?

Graph theory fundamentals name the abstract shape of HNSW: nodes, edges, degree, paths, connectivity, hubs, bridges, and traversals – the language shared by NSW, HNSW, and other proximity-graph indexes.

Why learn general graphs before hierarchical ones?

HNSW is a multilayer proximity graph. Without vocabulary for directed versus undirected edges, degree limits, connected components, shortest paths, diameter, and sparse versus dense regimes, talk about M and navigability stays vague. k-NN graphs and proximity graphs situate HNSW among geometric graph families. Hub nodes and bridge edges explain both helpful long-range links and failure modes when critical bridges are missing. Traversal is what search does; damaged connectivity is what deletes and bad builds risk.

These definitions are short on purpose so you can jump back mid-chapter without rereading a textbook.

How do graph terms map onto HNSW operations?

Insertion links a new vertex to selected neighbors under degree caps – local surgery on adjacency. Search is a guided traversal from an entry point downward through layers. Hub-heavy upper layers create small-world shortcuts; the base layer is denser and more local. When Weaviate cleans tombstones, it is repairing graph connectivity so traversals do not waste work on dead vertices. Distributed and frontier pages extend the same ideas across shards and replicas.

Graph literacy also clarifies why not every graph ANN is HNSW – alternatives rearrange edges and hierarchy differently.

What should you open next?

Read node, edge, degree, proximity graph, and hub node pages, then Part II on proximity graphs and small worlds. When debugging recall collapses, return to connected components, bridges, and traversal.

This section is the graph vocabulary for the whole curriculum. Next, start with “What is a proximity graph?” or Part II’s first chapter, then deepen with hubs, bridges, and diameter as needed.