Search papers, labs, and topics across Lattice.
The paper introduces an incremental $k$-NN graph construction method for spectral clustering of text embeddings that guarantees graph connectivity, addressing the issue of disconnected components in standard $k$-NN graphs at practical sparsity levels. This is achieved by linking each new node to its $k$ nearest *previously inserted* nodes, ensuring a connected graph regardless of $k$. Empirical validation on six text clustering datasets using SentenceTransformer embeddings and Laplacian eigenmaps demonstrates improved performance in the low-$k$ regime compared to standard $k$-NN graphs, while matching performance at higher $k$ values.
Guaranteeing connectivity in text embedding graphs with a simple incremental construction unlocks more robust and parameter-insensitive spectral clustering.
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$.
