Simple Fix Guarantees Connected Graphs for Robust Text Clustering

One of the quiet workhorses of modern text mining is a deceptively simple data structure: a neighborhood graph, in which every document becomes a node and edges link each document to the items most similar to it. These graphs underpin topic discovery, near-duplicate detection, semi-supervised label propagation, and the retrieval indices used in retrieval-augmented generation. Yet, according to a new study published in the journal Machine Learning, this foundational step is far more fragile than most practitioners realize. On realistic text datasets, the standard k-nearest-neighbor graphs that power spectral clustering can shatter into many disconnected components at the sparsity levels people actually use in practice, silently degrading results and making the whole pipeline hypersensitive to a single hyperparameter.

The study, led by Marko Pranjić and Boshko Koloski of the Jožef Stefan Institute together with Nada Lavrač, Senja Pollak, and Marko Robnik-Šikonja of the University of Ljubljana, quantifies just how badly things can go wrong. Working with the well-known 20 Newsgroups collection of roughly 20,000 documents, the researchers encoded the test split of 7,532 documents into 384-dimensional vectors using the SentenceTransformer model all-MiniLM-L12-v2 and measured cosine distance between the embeddings. When they built epsilon-threshold graphs, connecting every pair of documents closer than a given distance, they found that even the minimal distance required to keep the graph connected demanded around one million edges, and increasing that distance by only five percent inflated the edge count by more than sixty percent. Sparser is better for memory and speed, but sparser also means disconnected.

The k-nearest-neighbor approach fared somewhat better, since every document is linked to its k most similar documents, and tuning k to obtain a connected graph proved easier than tuning a distance threshold. But connectedness is never guaranteed. Theoretical work cited in the study shows that a k-NN graph is only asymptotically connected with high probability when k exceeds roughly 5.1774 times the natural logarithm of the number of points, which for as few as 300 data points already means k above 30, far beyond the small values used in real pipelines. In the experiments, some dataset partitions within the TwentyNewsgroups benchmark exhibited disconnected components even at k equals 15, and a Reddit sentence-clustering dataset remained disconnected at k equals 20. The high-dimensional geometry of embeddings makes matters worse: a phenomenon known as hubness means a few points appear in a disproportionate number of neighbor lists while others become isolated anti-hubs, skewing degree distributions and aggravating disconnection.

Why does disconnection matter so much? In spectral clustering, each connected component of the graph can only be assigned to a single cluster. When the number of components equals or exceeds the number of desired clusters, the clustering becomes trivial, and no similarity-based criterion can rescue it. The same fragility propagates beyond clustering: in item-based recommender systems, unreachable items simply cannot be recommended, and in label propagation, an isolated component of documents can never receive a propagated label. Connectivity, in other words, determines reachability, and reachability determines whether the downstream algorithm can function at all.

The researchers’ solution is elegantly minimal. Instead of letting every node search for neighbors across the entire dataset simultaneously, their incremental construction inserts documents one at a time, and each new node is linked to its k nearest neighbors among the nodes already present in the graph. That single restriction, searching only among previously inserted nodes, guarantees a connected graph for any value of k. The proof is a short induction: the first insertion creates a single connected component, and every subsequent node attaches to k existing members of that component, extending it without ever splitting it. Because the first node of a new region can only attach to earlier nodes, the graph remains one piece by construction, for every k and every insertion order.

The modification also confers a practical bonus that is increasingly relevant in the era of streaming data. In a standard k-NN graph, adding a single new document can trigger a large reconfiguration, since many existing nodes might count the newcomer among their nearest neighbors, effectively forcing a rebuild. The incremental construction induces only local changes, restricted to the row and column of the newly added node in the adjacency matrix. New documents can therefore be inserted without reconstructing the existing graph, and the last added nodes can even be deleted, properties the authors argue could be exploited in applications where data arrives continuously or becomes invalidated over time.

To test whether the guaranteed connectivity translates into better clustering, the team evaluated spectral clustering with Laplacian eigenmaps across eleven sentence- and paragraph-level clustering tasks drawn from six dataset sources in the Massive Text Embedding Benchmark, covering 182 distinct clustering problems in total. Performance was measured with V-measure, the harmonic combination of homogeneity and completeness. The results show a clear pattern: in the low-k regime, where standard k-NN graphs are most prone to fragmentation, the incremental approach consistently outperformed the standard construction, achieving near-top scores already at k equals 3 on many datasets, while matching the standard graph at larger k where both methods operate on connected structures. The largest gains appeared on TwentyNewsgroups, precisely where disconnection was most prevalent.

The team then compared their method against the most obvious alternative: repairing the standard k-NN graph by augmenting it with a minimum spanning tree, a global structure that stitches disconnected pieces together. Under matched MST augmentation, the incremental graph still held the edge in the sparse regime, improving on k-NN plus MST by an average of 2.5 V-measure points for k between 1 and 3, and by 3.8 points at k equals 1. A Bayesian signed-rank analysis with a region of practical equivalence confirmed that the MST is practically beneficial only in the sparsest regime and practically irrelevant from k equals 6 onward. Crucially, the exact MST computation requires forming the dense N-by-N distance matrix, an O(N-squared) step. The incremental construction avoids that matrix entirely because it attains connectivity through the insertion order rather than through added global edges, and it proved between 23 and 44 times faster to build than the MST-augmented alternatives, with peak memory dropping from as much as 20.2 gigabytes to as little as 1.2 gigabytes on the largest evaluated partitions, run on a CPU node of the Vega EuroHPC system.

Two natural objections receive careful treatment in the paper. First, because the incremental graph depends on the order in which nodes are inserted, is the method stable? Across ten randomized orderings per dataset, the standard deviation of clustering performance rarely exceeded one percent and was often below half a percent, and the structural statistics of the resulting graphs, including transitivity, assortativity, and label homophily, varied only in the third decimal place. Even adversarial orderings, in which the first inserted nodes were deliberately concentrated near the embedding centroid or drawn entirely from a single class, changed V-measure by at most 0.4 points relative to random ordering. Second, does the approach depend on the specific embedding model? Tests with larger models such as bge-base-en-v1.5 and all-mpnet-base-v2 showed that bigger encoders consistently improve results, though the benefit of denser graphs and larger models proved dataset-dependent, with Reddit clustering the notable exception.

The authors are candid about limitations. The five largest Reddit paragraph-level partitions exceeded the 32-bit index range of the sparse eigensolver and were excluded from some recomputed comparisons, and the robustness study covers concentrated initial seeds but not fully temporally ordered document streams, since the benchmark snapshots carry no timestamps. Future directions include replacing exact nearest-neighbor search with approximate methods, coupling the incremental graph with efficient eigenvector update techniques, and deploying the construction in temporal community detection. Still, the message is striking: a one-line change to how documents are inserted into a similarity graph eliminates a failure mode that has quietly lurked in spectral text clustering, delivering guaranteed connectivity, faster builds, lower memory, and better low-k performance, all without needing a proper metric, global graph features, or any repair step at all.

Subject of Research: Incremental k-nearest-neighbor graph construction for robust spectral clustering of text embeddings

Article Title: Incremental Graph Construction Enables Robust Spectral Clustering of Texts

Article References: Incremental Graph Construction Enables Robust Spectral Clustering of Texts. (n.d.). https://doi.org/10.1007/s10994-026-07158-z

Image Credits: AI Generated

DOI: 10.1007/s10994-026-07158-z

Keywords: spectral clustering, incremental graph construction, k-nearest neighbor graphs, text embeddings, Laplacian eigenmaps, graph connectivity, minimum spanning tree, Machine Learning journal, SentenceTransformers, MTEB, document clustering, high-dimensional data