Skip to contents

K Nearest Neighbor (KNN) Graph

Source: R/clustering.R
knn_graph.Rd

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.

Usage

knn_to_graph(knn, use_weights = FALSE, self_loops = TRUE)

knn_to_snn_graph(
  knn,
  min_val = 1/15,
  self_loops = FALSE,
  return_type = c("matrix", "list")
)

knn_to_geodesic_graph(knn, return_type = c("matrix", "list"), threads = 0L)

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.