Attention

The vector search and clustering algorithms in RAFT are being migrated to a new library dedicated to vector search called cuVS. We will continue to support the vector search algorithms in RAFT during this move, but will no longer update them after the RAPIDS 24.06 (June) release. We plan to complete the migration by RAPIDS 24.08 (August) release.

Spectral Clustering#

#include <raft/spectral/partition.cuh>

template<typename vertex_t, typename weight_t, typename EigenSolver, typename ClusterSolver> std::tuple< vertex_t, weight_t, vertex_t > raft::spectral::modularity_maximization (raft::resources const &handle, matrix::sparse_matrix_t< vertex_t, weight_t > const &csr_m, EigenSolver const &eigen_solver, ClusterSolver const &cluster_solver, vertex_t *__restrict__ clusters, weight_t *eigVals, weight_t *eigVecs)

Compute partition for a weighted undirected graph. This partition attempts to minimize the cost function: Cost = \(sum_i\) (Edges cut by ith partition)/(Vertices in ith partition)

Parameters:

  • handle – raft handle for managing expensive resources

  • csr_m – Weighted graph in CSR format

  • eigen_solver – Eigensolver implementation

  • cluster_solver – Cluster solver implementation

  • clusters – (Output, device memory, n entries) Partition assignments.

  • eigVals – Output eigenvalue array pointer on device

  • eigVecs – Output eigenvector array pointer on device

Returns:

statistics: number of eigensolver iterations, .

template<typename vertex_t, typename weight_t> void raft::spectral::analyzeModularity (raft::resources const &handle, matrix::sparse_matrix_t< vertex_t, weight_t > const &csr_m, vertex_t nClusters, vertex_t const *__restrict__ clusters, weight_t &modularity)

Compute modularity.

This function determines the modularity based on a graph and cluster assignments

Parameters:

  • handle – raft handle for managing expensive resources

  • csr_m – Weighted graph in CSR format

  • nClusters – Number of clusters.

  • clusters – (Input, device memory, n entries) Cluster assignments.

  • modularity – On exit, modularity

template<typename vertex_t, typename weight_t, typename EigenSolver, typename ClusterSolver> std::tuple< vertex_t, weight_t, vertex_t > raft::spectral::partition (raft::resources const &handle, matrix::sparse_matrix_t< vertex_t, weight_t > const &csr_m, EigenSolver const &eigen_solver, ClusterSolver const &cluster_solver, vertex_t *__restrict__ clusters, weight_t *eigVals, weight_t *eigVecs)

Compute spectral graph partition.

Compute partition for a weighted undirected graph. This partition attempts to minimize the cost function: Cost = \(sum_i\) (Edges cut by ith partition)/(Vertices in ith partition)

Parameters:

  • handle – raft handle for managing expensive resources

  • csr_m – Weighted graph in CSR format

  • eigen_solver – Eigensolver implementation

  • cluster_solver – Cluster solver implementation

  • clusters – (Output, device memory, n entries) Partition assignments.

  • eigVals – Output eigenvalue array pointer on device

  • eigVecs – Output eigenvector array pointer on device

Returns:

statistics: number of eigensolver iterations, .

template<typename vertex_t, typename weight_t> void raft::spectral::analyzePartition (raft::resources const &handle, matrix::sparse_matrix_t< vertex_t, weight_t > const &csr_m, vertex_t nClusters, const vertex_t *__restrict__ clusters, weight_t &edgeCut, weight_t &cost)

Compute cost function for partition.

This function determines the edges cut by a partition and a cost function: Cost = \(sum_i\) (Edges cut by ith partition)/(Vertices in ith partition) Graph is assumed to be weighted and undirected.

Parameters:

  • handle – raft handle for managing expensive resources

  • csr_m – Weighted graph in CSR format

  • nClusters – Number of partitions.

  • clusters – (Input, device memory, n entries) Partition assignments.

  • edgeCut – On exit, weight of edges cut by partition.

  • cost – On exit, partition cost function.

template<typename index_type_t, typename value_type_t, typename size_type_t = index_type_t>
struct cluster_solver_config_deprecated_t#
template<typename index_type_t, typename value_type_t, typename size_type_t = index_type_t>
struct cluster_solver_config_t#
template<typename index_type_t, typename value_type_t, typename size_type_t = index_type_t>
struct eigen_solver_config_t#
template<typename index_type_t, typename value_type_t, typename size_type_t = index_type_t>
struct kmeans_solver_deprecated_t#
template<typename index_type_t, typename value_type_t, typename size_type_t = index_type_t>
struct kmeans_solver_t#
template<typename index_type_t, typename value_type_t, typename size_type_t = index_type_t>
struct lanczos_solver_t#
Show Source