# Incremental Graph Construction Enables Robust Spectral Clustering of Texts

arXiv: https://arxiv.org/abs/2603.03056 · HTML: https://mlsanity.com/paper/2603.03056/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 61 references that are in the map.
- First posted on arXiv 3 Mar 2026.

## Builds on (most cited first, 21 of 21)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [BERTopic: Neural topic modeling with a class-based TF-IDF procedure](https://mlsanity.com/paper/2203.05794/) (2022)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [MTEB: Massive Text Embedding Benchmark](https://mlsanity.com/paper/2210.07316/) (2022)
- [C-Pack: Packed Resources For General Chinese Embeddings](https://mlsanity.com/paper/2309.07597/) (2023)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [ETA Prediction with Graph Neural Networks in Google Maps](https://mlsanity.com/paper/2108.11482/) (2021)
- [A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources](https://mlsanity.com/paper/2011.14867/) (2020)
- [Time for a change: a tutorial for comparing multiple classifiers through Bayesian analysis](https://mlsanity.com/paper/1606.04316/) (2016)
- [Backpropagation-Friendly Eigendecomposition](https://mlsanity.com/paper/1906.09023/) (2019)
- [Graph-based data clustering via multiscale community detection](https://mlsanity.com/paper/1909.04491/) (2019)
- [GCondNet: A Novel Method for Improving Neural Networks on Small High-Dimensional Tabular Data](https://mlsanity.com/paper/2211.06302/) (2022)
- [Embedding-based Silhouette Community Detection](https://mlsanity.com/paper/1908.02556/) (2019)
- [Graph-in-Graph (GiG): Learning interpretable latent graphs in non-Euclidean domain for biological and healthcare applications](https://mlsanity.com/paper/2204.00323/) (2022)
- [Efficient Eigen-updating for Spectral Graph Clustering](https://mlsanity.com/paper/1301.1318/) (2013)
- [Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree](https://mlsanity.com/paper/1309.1795/) (2013)

## Abstract (arXiv)

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.