A parameter-free graph reduction for spectral clustering and SpectralNet
This work addresses the need for more stable and user-friendly graph-based clustering methods, though it is incremental as it builds on existing techniques without introducing a new paradigm.
The authors tackled the problem of parameter tuning in graph-based clustering by introducing a parameter-free graph reduction method, which improved stability and performance in spectral clustering and SpectralNet across various datasets.
Graph-based clustering methods like spectral clustering and SpectralNet are very efficient in detecting clusters of non-convex shapes. Unlike the popular $k$-means, graph-based clustering methods do not assume that each cluster has a single mean. However, these methods need a graph where vertices in the same cluster are connected by edges of large weights. To achieve this goal, many studies have proposed graph reduction methods with parameters. Unfortunately, these parameters have to be tuned for every dataset. We introduce a graph reduction method that does not require any parameters. First, the distances from every point $p$ to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. Second, the similarities with close neighbors are computed and only high similarities are kept. The edges that survive these two filtering steps form the constructed graph that was passed to spectral clustering and SpectralNet. The experiments showed that our method provides a stable alternative, where other methods performance fluctuated according to the setting of their parameters.