[2603.03056] Incremental Graph Construction Enables Robust Spectral Clustering of Texts

Computer Science > Machine Learning arXiv:2603.03056 (cs) [Submitted on 3 Mar 2026] Title:Incremental Graph Construction Enables Robust Spectral Clustering of Texts Authors:Marko Pranjić, Boshko Koloski, Nada Lavrač, Senja Pollak, Marko Robnik-Šikonja View a PDF of the paper titled Incremental Graph Construction Enables Robust Spectral Clustering of Texts, by Marko Pranji\'c and Boshko Koloski and Nada Lavra\v{c} and Senja Pollak and Marko Robnik-\v{S}ikonja View PDF HTML (experimental) Abstract: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 this http URL 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$. Comm...