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