Skip to content

[BUG] Host-data connect_knn_graph passes a non-symmetric CSR to RAFT's MST #2477

Description

@alexfallin

Describe the bug

The host-data variant of connect_knn_graph (cpp/src/cluster/detail/mst.cuh) stores each cross-component connecting edge once, in an arbitrary direction, and passes the resulting CSR to raft::sparse::solver::mst with initialize_colors = false.

raft::sparse::solver::mst operates on undirected graphs and implicitly assumes each undirected edge is stored in both directions.
The device-data variant of connect_knn_graph already satisfies this but the host path does not.

This is masked by the existing implementation. The current solver's per-row min-edge scan happens to see a one-directional edge from whichever row stores it. A pending RAFT PR: NVIDIA/raft#3118 replaces the solver internals with a faster implementation that documents and requires the symmetric input. Under it, the host path can leave components disconnected (a one-directional edge stored only in descending direction is never selected) or, with enough one-directional edges, hit the solver's worklist-overflow guard and throw "input CSR must be symmetric".

Steps/Code to reproduce bug

Exercised by cuVS's own connect_knn gtest with host data once the RAFT PR is in. Standalone reproduction against the replacement solver (replays the host path's resume call exactly):

  1. Build an MSF over a disconnected symmetric CSR (k components), initialize_colors = true.
  2. Build the connecting-edge CSR the way the host path does one entry per component pair, arbitrary direction including at least one edge whose stored direction is descending (row > col).
  3. Call mst(..., initialize_colors = false) on it.

Observed with the replacement solver: the descending edge is never selected; the final coloring retains >1 component (silent under-connection at small k; the overflow guard throws at larger one-directional counts). The same input with both directions stored connects fully with exactly v-1 total edges.

Expected behavior

The host-data path should feed mst a symmetric CSR, exactly as the device-data path already does, so the second solve connects all remaining components regardless of solver version.

Environment details

Observed when testing against the pending RAFT MST replacement (H200, CUDA 13.3) using the current version of cuVS

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions