[FEA] Take advantage of MST in hierarchical clustering

[afender]

Minimum spanning trees come up in hierarchical clustering is to enable a single-linkage clustering and the ability to draw dendrograms like Scipy's hierarchy package, which also enables HDBSCAN.

The kernels are being implemented in RAFT since it could also be used un cuGraph in the long run : rapidsai/raft#52

---

Solution

Parallel Baruvka algorithm supporting disconnected components. It is similar to Louvain in the sense it starts from all vertices as seeds and aggregate vertices into super vertices based on edge weights.

relevant papers :

• Large Graph Algorithms for Massively Multithreaded Architectures slower but better scalability with all kernels documented.
• kNN-Boruvka-GPU: A Fast & Scalable MST Construction from KNN Graphs on GPU The benchmarks demonstrated to scale to larger numbers of vertices/edges. The fastest implementation in this paper is “Fast minimum spanning tree for large graphs on the GPU” but has scalability problems.
• Fast Minimum Spanning Tree for Large Graphs on the GPU

Alternatives considered
Specific solutions for KNN-graphs. While this allows some optimizations, a more generic solution would have more benefits for the whole RAPIDS platform

• “Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, & Applications.
• "Design & Implementation of Cover Tree Algorithm on CUDA-Compatible GPU”

[cjnolet]

Ref: #1783

[github-actions]

This issue has been marked rotten due to no recent activity in the past 90d. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.

[github-actions]

This issue has been marked stale due to no recent activity in the past 30d. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be marked rotten if there is no activity in the next 60d.

[github-actions]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.