kNNSimilarityGraph

A kNNSimilarityGraph is a sparse graph data structure used to represent a set of data points where each node corresponds to a data point and edges connect a point to its k nearest neighbors according to a chosen similarity measure. The graph is typically undirected after symmetrization, or left directed in the basic k-Nearest Neighbors graph, with edge weights representing pairwise similarity.

Construction involves selecting a feature representation, choosing a similarity metric (for example cosine similarity or Gaussian kernel) or a distance metric (Euclidean), choosing an integer k, and for each node computing its k nearest neighbors. For each pair (i,j) found, an edge is added between i and j, with weight w_ij equal to the similarity between the points. Variants include mutual kNN, where an edge is kept only if i is among j's k nearest and j is among i's, producing a more robust graph; or symmetric kNN, where edges are created if either node lists the other.

Common properties include sparsity (at most n*k edges), possible disconnected components, and a degree distribution focused around k (or 2k in symmetric graphs). The graph is often used as a preprocessing step for spectral methods and graph-based learning, and can be built incrementally or with approximate nearest neighbor search for large datasets.

Applications include spectral clustering, manifold learning (Laplacian Eigenmaps), graph-based semi-supervised learning, community detection, and serving as input to graph neural networks. Weights capture similarity strength, enabling weighted measures such as Laplacian or diffusion processes. Limitations include sensitivity to the choice of k, metric, and feature representation; high-dimensional data may require dimensionality reduction; and approximate methods trade accuracy for speed. In practice, kNNSimilarityGraph converts a point cloud into a graph suitable for downstream analysis, balancing locality and scalability in large datasets.