Incremental Graph Construction Enables Robust Spectral Clustering of Texts
This work addresses the problem of robust spectral clustering for text embeddings, particularly for users dealing with realistic text datasets and low sparsity levels.
The authors tackled the problem of fragile neighborhood graphs in spectral clustering of text embeddings, resulting in a method that preserves connectivity and outperforms standard k-NN graphs in the low-k regime. Their approach matches standard k-NN at larger k values.
Neighborhood graphs are a critical but often fragile step in spectral clustering of text embeddings. On realistic text datasets, standard $k$-NN graphs can contain many disconnected components at practical sparsity levels (small $k$), making spectral clustering degenerate and sensitive to hyperparameters. We introduce a simple incremental $k$-NN graph construction that preserves connectivity by design: each new node is linked to its $k$ nearest previously inserted nodes, which guarantees a connected graph for any $k$. We provide an inductive proof of connectedness and discuss implications for incremental updates when new documents arrive. We validate the approach on spectral clustering of SentenceTransformer embeddings using Laplacian eigenmaps across six clustering datasets from the Massive Text Embedding Benchmark. Compared to standard $k$-NN graphs, our method outperforms in the low-$k$ regime where disconnected components are prevalent, and matches standard $k$-NN at larger $k$.