Refining A \(k\)-nearest Neighbor Graph For A Computationally Efficient Spectral Clustering

Abstract

Spectral clustering became a popular choice for data clustering for its ability of uncovering clusters of different shapes. However, it is not always preferable over other clustering methods due to its computational demands. One of the effective ways to bypass these computational demands is to perform spectral clustering on a subset of points (data representatives) then generalize the clustering outcome, this is known as approximate spectral clustering (ASC). ASC uses sampling or quantization to select data representatives. This makes it vulnerable to 1) performance inconsistency (since these methods have a random step either in initialization or training), 2) local statistics loss (because the pairwise similarities are extracted from data representatives instead of data points). We proposed a refined version of \(k\)-nearest neighbor graph, in which we keep data points and aggressively reduce number of edges for computational efficiency. Local statistics were exploited to keep the edg

Stats

• citations42
• S2 citations—
• github stars0
• HF likes0
• heat score12.25
• arxiv keyalshammari2023refining

Related papers

• A Learning-to-rank Formulation Of Clustering-based Approximate Nearest Neighbor Search (2024)4.52
• PECANN: Parallel Efficient Clustering With Graph-based Approximate Nearest Neighbor Search (2023)0.00
• Scalable K-means Clustering For Large K Via Seeded Approximate Nearest-neighbor Search (2025)0.00
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• A Distributed And Approximated Nearest Neighbors Algorithm For An Efficient Large Scale Mean Shift Clustering (2019)10.85
• Effective And General Distance Computation For Approximate Nearest Neighbor Search (2024)5.84
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58