NVIDIA / NVIDIA/cuvs

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

Open
#2,477 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Cuda
Stars
854
Forks
236
Avg merge
3d 3h
Merged PRs (30d)
62

Description

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: https://github.com/NVIDIA/raft/pull/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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in cpp/src/cluster/detail/mst.cuh, comparing the host-data and device-data variants of connect_knn_graph and how each builds the CSR before calling raft::sparse::solver::mst. Run the cuVS connect_knn gtest with the host-data path. Done means the host path supplies symmetric connecting edges and the test confirms all components connect under the replacement solver.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
machine-learning
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
74/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.