2.1. Connect HDBSCAN with Graph Theory
🪄 Step 1: Intuition & Motivation
Core Idea (in 1 short paragraph): Underneath all the math, HDBSCAN is secretly a graph algorithm. Instead of seeing data as isolated points floating in space, it imagines them as nodes in a network — connected by edges whose weights represent how “reachable” one point is from another. By building a Minimum Spanning Tree (MST) from this graph, HDBSCAN captures the natural structure of the data — forming clusters by cutting the weakest connections.
Simple Analogy: Think of connecting towns with roads. Each road’s length represents how hard it is to travel between towns. The MST is the cheapest road network that connects all towns without creating loops. If you start cutting the longest, weakest roads, regions begin to separate — and those regions are your clusters.
🌱 Step 2: Core Concept
What’s Happening Under the Hood?
HDBSCAN constructs a mutual reachability graph — a fully connected graph where each node is a data point, and each edge weight reflects mutual reachability distance (from earlier series):
$$d_{\text{mreach}}(a, b) = \max(\text{core_dist}(a), \text{core_dist}(b), d(a, b))$$These edge weights encode how “dense” or “reachable” one point is from another — smaller weights = denser, more connected regions.
HDBSCAN then builds a Minimum Spanning Tree (MST) from this graph using algorithms like Kruskal’s or Prim’s:
- MST connects all points using the lowest total reachability cost.
- It avoids cycles and ensures global connectivity with minimal redundancy.
Once the MST is built, increasing the distance threshold (i.e., cutting weaker edges) breaks the tree into subtrees — which represent clusters at different density levels.
This process naturally creates a hierarchy — as density decreases, clusters merge or dissolve, forming the condensed tree we explored earlier.
Why It Works This Way
Graphs are incredibly flexible for representing data relationships. While DBSCAN uses fixed neighborhoods, HDBSCAN uses graph connectivity to explore relative density relationships between all points.
The MST serves two powerful roles:
- It compresses the entire dataset’s structure into a minimal, connected skeleton.
- It provides a continuous map of merging and splitting events, allowing HDBSCAN to trace how clusters evolve as density changes.
In essence: the MST transforms the problem of “find dense clusters” into “find natural cuts in the connectivity graph.”
How It Fits in ML Thinking
📐 Step 3: Mathematical & Algorithmic Foundation
Minimum Spanning Tree (MST) Basics
- Given a graph $G(V, E)$ with edge weights $w(e)$, an MST is a subset $T \subseteq E$ that connects all vertices in $V$ with minimum total weight and no cycles.
- Formally: $$T = \arg\min_{T' \subseteq E} \sum_{e \in T'} w(e)$$ subject to $T’$ connecting all vertices.
Two common algorithms:
- Kruskal’s Algorithm: Sort all edges by weight, then add them one by one, skipping edges that would form a cycle.
- Prim’s Algorithm: Start with a random node and repeatedly add the smallest edge that connects the current tree to a new node.
Mutual Reachability Graph as Input
- Nodes = data points.
- Edge weights = mutual reachability distances.
- Because every pair of points can theoretically connect, the graph is fully connected, but only the MST is retained.
This makes the MST an efficient summary of density structure, keeping essential edges while discarding redundant ones.
Time Complexity Analysis
- Building the MST: $$O(n \log n)$$ (using Kruskal’s or Prim’s algorithm with efficient sorting and union-find operations).
- Condensation and hierarchy extraction: $$O(n)$$ (linear traversal through edges to build the hierarchy tree).
- Overall: roughly O(n log n) — efficient for moderately large datasets, though still challenging for very large ones.
🧠 Step 4: Assumptions or Key Ideas
- Graph representation assumes a meaningful distance metric (Euclidean, cosine, etc.).
- MST construction assumes transitive density connectivity — clusters form continuous subgraphs.
- The graph’s structure mirrors the data topology, not just geometry.
- Edge weight definition (mutual reachability) is critical — it balances density fairness and noise resistance.
⚖️ Step 5: Strengths, Limitations & Trade-offs
- Graph-based approach captures complex, non-linear relationships.
- MST ensures compact representation of all density connections.
- Efficient (O(n log n)) and interpretable — the structure directly maps to clusters.
- Building the full reachability graph can be memory-intensive for very large datasets.
- Sensitive to distance metric choice — cosine vs. Euclidean can change results significantly.
- MST captures pairwise relationships but ignores potential higher-order topology.
- Simplicity vs. expressiveness: MST is simple yet powerful; richer graph representations (e.g., spectral Laplacians) can capture deeper structure but add complexity.
- Efficiency vs. completeness: MST provides minimal structure but omits some alternative density paths.
🚧 Step 6: Common Misunderstandings
🚨 Common Misunderstandings (Click to Expand)
- “HDBSCAN builds one MST per cluster.” No — it builds a single MST for the entire dataset and later extracts clusters by cutting edges.
- “The MST directly represents clusters.” Not quite — it represents connections; clusters emerge as you cut weaker edges.
- “It can only use Euclidean distance.” False — any metric that defines pairwise distances can be used (e.g., cosine, Manhattan), but results depend heavily on the metric’s suitability for the data.
🧩 Step 7: Mini Summary
🧠 What You Learned: HDBSCAN builds a Minimum Spanning Tree over a mutual reachability graph, encoding both geometry and density structure.
⚙️ How It Works: Each edge represents how “reachable” two points are based on local density; cutting weak edges reveals clusters at different density scales.
🎯 Why It Matters: Understanding the MST foundation shows how HDBSCAN merges graph theory and density estimation — letting it discover clusters naturally without predefined thresholds.