scikit-learn · OmarManzoor · Dec 4, 2023 · Oct 28, 2023 · Nov 14, 2023 · Nov 14, 2023
diff --git a/sklearn/cluster/_hdbscan/hdbscan.py b/sklearn/cluster/_hdbscan/hdbscan.py
@@ -104,22 +104,28 @@ def _brute_mst(mutual_reachability, min_samples):
     if not issparse(mutual_reachability):
         return mst_from_mutual_reachability(mutual_reachability)
 
-    # Check connected component on mutual reachability
-    # If more than one component, it means that even if the distance matrix X
-    # has one component, there exists with less than `min_samples` neighbors
-    if (
-        csgraph.connected_components(
-            mutual_reachability, directed=False, return_labels=False
-        )
-        > 1
-    ):
+    # Check if the mutual reachability matrix has any rows which have
+    # less than `min_samples` non-zero elements.
+    if (mutual_reachability.getnnz(1) < min_samples).sum():
         raise ValueError(
             f"There exists points with fewer than {min_samples} neighbors. Ensure"
             " your distance matrix has non-zero values for at least"
             f" `min_sample`={min_samples} neighbors for each points (i.e. K-nn"
             " graph), or specify a `max_distance` in `metric_params` to use when"
             " distances are missing."
         )
+    # Check connected component on mutual reachability.
+    # If more than one connected component is present,
+    # it means that the graph is disconnected.
+    n_components = csgraph.connected_components(
+        mutual_reachability, directed=False, return_labels=False
+    )
+    if n_components > 1:
+        raise ValueError(
+            f"Sparse mutual reachability matrix has {n_components} connected"
+            " components. HDBSCAN cannot be perfomed on a disconnected graph. Ensure"
+            " that the sparse distance matrix has only one connected component."
+        )
 
     # Compute the minimum spanning tree for the sparse graph
     sparse_min_spanning_tree = csgraph.minimum_spanning_tree(mutual_reachability)

diff --git a/sklearn/cluster/tests/test_hdbscan.py b/sklearn/cluster/tests/test_hdbscan.py
@@ -401,6 +401,23 @@ def test_hdbscan_sparse_distances_too_few_nonzero(csr_container):
         HDBSCAN(metric="precomputed").fit(X)
 
 
+@pytest.mark.parametrize("csr_container", CSR_CONTAINERS)
+def test_hdbscan_sparse_distances_disconnected_graph(csr_container):
+    """
+    Tests that HDBSCAN raises the correct error when the distance matrix
+    has multiple connected components.
+    """
+    # Create symmetric sparse matrix with 2 connected components
+    X = np.zeros((20, 20))
+    X[:5, :5] = 1
+    X[5:, 15:] = 1
+    X = X + X.T
+    X = csr_container(X)
+    msg = "HDBSCAN cannot be perfomed on a disconnected graph"
+    with pytest.raises(ValueError, match=msg):
+        HDBSCAN(metric="precomputed").fit(X)
+
+
 def test_hdbscan_tree_invalid_metric():
     """
     Tests that HDBSCAN correctly raises an error for invalid metric choices.