Convert a KNN object (e.g. returned by `knn_hnsw()`

or `knn_annoy()`

) into
a graph. The graph is represented as a sparse adjacency matrix.

## Arguments

- knn
List of 2 matrices -- idx for cell x K neighbor indices, dist for cell x K neighbor distances

- use_weights
boolean for whether to replace all distance weights with 1

- self_loops
Whether to allow self-loops in the output graph

- min_val
minimum jaccard index between neighbors. Values below this will round to 0

- return_type
Whether to return a sparse adjacency matrix or an edge list

- threads
Number of threads to use during calculations

## Value

**knn_to_graph**

Sparse matrix (dgCMatrix) where `mat[i,j]`

= distance from cell `i`

to
cell `j`

, or 0 if cell `j`

is not in the K nearest neighbors of `i`

**knn_to_snn_graph**

`return_type == "matrix"`

: Sparse matrix (dgCMatrix) where`mat[i,j]`

= jaccard index of the overlap in nearest neigbors between cell`i`

and cell`j`

, or 0 if the jaccard index is <`min_val`

. Only the lower triangle is filled in, which is compatible with the BPCells clustering methods`return_type == "list"`

: List of 3 equal-length vectors`i`

,`j`

, and`weight`

, along with an integer`dim`

. These correspond to the rows, cols, and values of non-zero entries in the lower triangle adjacency matrix.`dim`

is the total number of vertices (cells) in the graph

**knn_to_geodesic_graph**

`return_type == "matrix"`

: Sparse matrix (dgCMatrix) where`mat[i,j]`

= normalized similarity between cell`i`

and cell`j`

. Only the lower triangle is filled in, which is compatible with the BPCells clustering methods`return_type == "list"`

: List of 3 equal-length vectors`i`

,`j`

, and`weight`

, along with an integer`dim`

. These correspond to the rows, cols, and values of non-zero entries in the lower triangle adjacency matrix.`dim`

is the total number of vertices (cells) in the graph

## Details

**knn_to_graph**
Create a knn graph

**knn_to_snn_graph**
Convert a knn object into a shared nearest neighbors adjacency matrix.
This follows the algorithm that Seurat uses to compute SNN graphs

**knn_to_geodesic_graph**
Convert a knn object into an undirected weighted graph, using the same
geodesic distance estimation method as the UMAP package.
This matches the output of `umap._umap.fuzzy_simplicial_set`

from the `umap-learn`

python package, used by default in `scanpy.pp.neighbors`

.
Because this only re-weights and symmetrizes the KNN graph, it will usually use
less memory and return a sparser graph than `knn_to_snn_graph`

which computes
2nd-order neighbors. Note: when cells don't have themselves listed as the nearest
neighbor, results may differ slightly from `umap._umap.fuzzy_simplicial_set`

, which
assumes self is always successfully found in the approximate nearest neighbor search.