Incremental Graph Construction Enables Robust Spectral Clustering of Texts

Abstract Neighborhood graphs over document embeddings are a common component of text-mining pipelines, supporting topic discovery, deduplication, semi-supervised label propagation, and retrieval-index construction, and they are a critical but 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 an incremental k -NN graph construction algorithm in which each new node is linked to its k nearest previously inserted nodes; this 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 eleven sentence- and paragraph-level clustering tasks drawn from six dataset sources in 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 . The advantage at low k persists when the standard k -NN graph is repaired with a minimum spanning tree, while our construction avoids the dense distance matrix an exact repair requires and is consequently far cheaper to build, in both time and memory. The code is available on https://github.com/bkolosk1/incremental_clustering_graphs.