Is an edge weight just the original distance?

Only when that distance is at least as large as both core distances. Otherwise, a core distance determines the weight.

Does the graph itself assign final clusters?

No. It supports hierarchy construction; additional clustering steps determine selected groups and noise labels.

Must software store all pairwise edges?

Not necessarily. The complete graph is the conceptual model, while algorithms can exploit a minimum spanning tree and other computational techniques.

AI Glossary / Graphs and symbolic AI / Intermediate

Mutual Reachability Graph

Definition

A mutual reachability graph is a weighted graph used in density-based hierarchical clustering, notably HDBSCAN. Each data point is a vertex. The weight between two distinct points is the maximum of their original distance and their two core distances, which describe local neighborhood scale. This transformation makes connections involving sparse neighborhoods more expensive.

What it means

Ordinary single-linkage clustering can connect otherwise separate dense groups through a chain of sparse points. Mutual reachability modifies the distances used for those connections. A point with a large core distance cannot form a cheap edge simply because one other point happens to be nearby.
The graph is a representation used to build a hierarchy, not a completed set of cluster labels. Further steps decide how to condense the hierarchy and select clusters. The result still depends on the input features, distance measure, neighborhood parameter, and cluster-selection settings; the graph does not uncover an unquestionable natural grouping.

How it works

Choose a distance measure and neighborhood-count convention. Compute each point's core distance, usually a specified nearest-neighbor distance. For distinct points a and b, assign edge weight max(core(a), core(b), d(a,b)). The conceptual graph connects every pair.
At a threshold epsilon, retain edges whose weights are at most epsilon. Their connected components describe how connections emerge at that scale. A minimum spanning tree preserves the connectivity information needed across edge thresholds while using far fewer edges. HDBSCAN then constructs and condenses a hierarchy and selects clusters. Implementations can avoid explicitly materializing every edge, so the conceptual complete graph is not a universal storage requirement.

Three practical examples

A clustering analyst can inspect why two nearby records remain weakly connected when one sits in a sparse neighborhood.
A research team can compare ordinary-distance and mutual-reachability hierarchies to study the effect of sparse bridges in synthetic data.
A quality-monitoring experiment can explore dense operating regimes while keeping noise assignments and cluster interpretation subject to domain review.

Think of it this way

Think of a bridge whose admission threshold is the largest of the crossing distance and the access requirements on both banks. Even a short crossing is unavailable if one bank requires a higher threshold. The analogy is limited because graph weights are mathematical distances derived from a dataset, not actual travel costs or administrative permissions.

Worked example

Use five invented points on a line: A = 0, B = 1, C = 2, D = 8, and E = 9. Use absolute distance and define core distance as the third-nearest distance counting the point itself, matching the stated scikit-learn convention with min_samples = 3.
For A, the first three distances are 0, 1, and 2, so core(A) = 2. Similarly, core(B) = 1 and core(C) = 2. D's first three distances are 0, 1, and 6, giving core(D) = 6. E's are 0, 1, and 7, giving core(E) = 7.
The mutual reachability weights among A, B, and C are all 2. Although D and E are only 1 unit apart, their edge weight is max(6,7,1) = 7. The C - D edge has weight max(2,6,6) = 6.
At threshold 2, A, B, and C are connected while D and E have no retained edges to other vertices. At threshold 6, D connects to C, but E remains isolated. At threshold 7, all five connect. These are graph-connectivity calculations, not final HDBSCAN cluster labels; cluster condensation and selection have not been performed.

Illustrative case study

In a fictional service-log analysis, an analyst notices that a few unusual records join two large groups under ordinary single linkage. The team inspects feature scaling and then compares a mutual-reachability hierarchy using the same distance definition.
Some sparse connections become more expensive, but the team does not automatically declare the resulting groups meaningful. It checks representative records, parameter sensitivity, and whether the chosen features reflect the operational question. The case illustrates investigation of a clustering mechanism, not an achieved improvement or a guarantee that every sparse bridge will disappear.

Common misconceptions and mistakes

Mutual reachability is not the same as a mutual nearest-neighbor graph. A mutual-neighbor graph usually keeps an edge only when each point lies in the other's neighbor set. Here, the conceptual graph is complete and edge weights are transformed.
Do not treat the neighborhood count as interchangeable across libraries. Some count the point itself and others use a different convention. Also avoid reading final noise labels directly from one isolated thresholded graph without specifying the clustering procedure. Large core distance indicates a sparse neighborhood at the chosen scale; small core distance does not by itself make a point noise.

Business use

The graph helps explain density-sensitive grouping and why a nearby pair need not have a strong cluster connection. This can make clustering reviews more concrete: analysts can show whether an edge weight comes from separation or from sparse local support.
For business use, validate the distance and features before interpreting the hierarchy. Changing units can change neighborhoods and cluster structure. Record the exact implementation, neighborhood convention, and cluster-selection parameters. Evaluate whether proposed groups support the intended workflow; unsupervised labels should not substitute for a meaningful definition of customer, process, or document similarity.

Check your understanding

In the worked example, what is the weight of the B - D edge?

Answer: The original distance is 7, core(B) is 1, and core(D) is 6. The maximum is 7, so the edge is absent at threshold 6 and retained at threshold 7.

Related terms

Minimum spanning tree
Nearest neighbor
HDBSCAN
core distance
single linkage
density-based clustering
connected component
cluster hierarchy

Learn next

Next, construct a minimum spanning tree for the worked graph: two weight-2 edges connect A, B, and C, a weight-6 edge connects C to D, and a weight-7 edge connects E. Verify the same connected components at thresholds 2, 6, and 7. Ties allow more than one valid tree.

Minimum spanning tree

Sources

Scikit-learn, Clustering, Mutual Reachability Graph: https://scikit-learn.org/stable/modules/clustering.html#mutual-reachability-graph . HDBSCAN implementation authors, How HDBSCAN Works: https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html . Formula, transformation, and hierarchy sections were read. The numerical example uses scikit-learn's explicitly stated self-counting convention.

Previous: Mutual preferential independence Next: Mutually Exclusive Events