Incremental Graph Construction Enables Robust Spectral Clustering of Texts

Marko Pranjić; Boshko Koloski; Nada Lavrač; Senja Pollak; Marko Robnik-Šikonja

cs.LGMar 3, 2026

Incremental Graph Construction Enables Robust Spectral Clustering of Texts

Authors: Marko Pranjić, Boshko Koloski, Nada Lavrač, Senja Pollak, Marko Robnik-Šikonja

Organizations: Joˇzef Stefan Institute and International Postgraduate School, Ljubljana, Slovenia. · University of Ljubljana, Faculty of Computer and Information Science, Ljubljana, Slovenia.

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 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$ .

Figures & tables

Figure 1: Proposed methodology. Top : General spectral clustering pipeline. After embedding the documents, a graph is constructed, projected into eigenspace, and clustered using k-means. Bottom : Comparison of a standard nearest-neighbor graph (which may be disconnected) with the proposed incremental approach that progressively links nodes to form a fully connected graph. The colored triangle denotes the search for nearest neighbors among previously considered points, while the yellow circle represents the search for global nearest neighbors.

$\epsilon$	Num comp.	Max comp. size	Graph edges	Digraph edges
$\epsilon_{0}-10\%$	19	7511	404,956	809,912
$\epsilon_{0}-5\%$	3	7530	636,040	1,272,080
$\epsilon_{0}$	1	7532	1,009,318	2,018,636
$\epsilon_{0}+5\%$	1	7532	1,622,168	3,244,336
$\epsilon_{0}+10\%$	1	7532	2,645,373	5,290,746

Table 1: Properties of

\epsilon

neighborhood graphs for different values of

\epsilon

. A minimal number of graph edges to satisfy the connectedness of the graph is achieved with

\epsilon=\epsilon_{0}

. A graph contains disconnected components if the number of components is greater than 1.

$k$	Num comp.	Max comp. size	Graph edges	Digraph edges
1	1,505	216	7,532	12,054
2	49	7,342	15,064	23,470
3	6	7,507	22,596	34,734
4	2	7,527	30,128	45,978
5	1	7,532	37,660	57,132

Table 2: Properties of

k

-NN neighborhood graphs for different values of parameter

k

. A graph contains disconnected components if the number of components is greater than 1.

			S2S				P2P
Dataset	Title	Body	docs.	avg. len.	P	C	docs.	avg. len.	P	C
ArXiv	$\checkmark$	$\checkmark$	732723	74.00	31	171	732723	1009.90	31	171
BioRxiv	$\checkmark$	$\checkmark$	75000	101.60	10	26	75000	1666.20	10	26
MedRxiv	$\checkmark$	$\checkmark$	37500	114.70	10	51	37500	1981.20	10	51
Reddit	$\checkmark$	$\checkmark$	420464	64.70	25	50	459399	727.70	10	87
StackExchange	$\checkmark$	$\checkmark$	373850	57.00	25	50	75000	1090.70	10	385

Table 3: An overview of text datasets used in the evaluation. We report the number of documents, average document length, number of partitions in column P, and maximum number of clusters within the problems in column C. The statistics are presented for both sentence-to-sentence (S2S) and paragraph-to-paragraph (P2P) tasks.

Figure 2: Clustering performance of embeddings induced using incremental

k

-NN (Ours) and standard

k

-NN for a range of parameter

k

. Points, where the standard

k

-NN neighborhood induces connected graphs, are marked, while in Ours, the graph is always connected. Results for sentence-to-sentence (S2S) tasks are shown on the top and for paragraph-to-paragraph (P2P) tasks at the bottom.

		S2S						P2P
	k	Arx.	Bio.	Med.	Red.	SE	20NG	Arx.	Bio.	Med.	Red.	SE
k-NN LD	1	9.33	3.24	15.07	3.43	3.31	7.19	10.23	3.63	15.55	6.67	30.17
	2	21.73	12.91	26.09	5.11	38.83	10.85	28.49	14.13	28.18	25.06	35.49
	3	37.93 $\uparrow$	26.43	29.51	26.99	56.67	14.67	45.61 $\uparrow$	30.16	32.37	54.03	36.35 $\uparrow$
	6	38.85 $\uparrow$	29.03	31.71	45.67	60.48 $\uparrow$	19.10	46.60 $\uparrow$	32.89	34.22–	64.86 $\uparrow$	37.01 $\uparrow$
	8	39.44 $\uparrow$	30.14	32.52 $\uparrow$	49.05	61.22 $\uparrow$	23.10	46.67 $\uparrow$	33.50	34.86 $\uparrow$	65.08 $\uparrow$	37.18 $\uparrow$

Table 4:

V_{1}

scores (in percentages, larger is better) for spectral clustering of low-dimensional embeddings (LD) using standard

k

-NN neighborhood graph and our incremental approach. An arrow is shown to mark the relative difference between two variants for the same value of

k

. Additionally, we provide results for the clustering of high-dimensional embeddings (HD) using the K-means algorithm.

		S2S						P2P
	k	Arx.	Bio.	Med.	Red.	SE	20NG	Arx.	Bio.	Med.	Red.	SE
Ours LD	1	0.84%	0.83%	0.52%	1.25%	1.42%	1.42%	1.06%	0.82%	0.55%	1.38%	0.21%
	2	0.57%	0.77%	0.52%	1.03%	0.95%	1.33%	0.55%	0.66%	0.48%	0.86%	0.17%
	3	0.45%	0.71%	0.45%	0.92%	0.81%	1.53%	0.47%	0.53%	0.40%	0.75%	0.15%
	6	0.43%	0.59%	0.38%	0.63%	0.88%	0.86%	0.36%	0.55%	0.41%	0.60%	0.14%
	8	0.34%	0.43%	0.41%	0.48%	0.86%	0.99%	0.34%	0.48%	0.38%	0.53%	0.14%

Table 5: Standard deviation of clustering on neighborhood graphs created by our approach.

Figure 3: The impact of different embedding models applied to different datasets.

Model	Emb. Dimensions.	Max tokens	Model Size (GB)	average V-measure
all-MiniLM-L6-v2 Reimers and Gurevych (2019)	384	256	0.09	0.41
all-MiniLM-L12-v2 Reimers and Gurevych (2019)	384	256	0.13	0.40
all-mpnet-base-v2 Reimers and Gurevych (2019)	768	384	0.42	0.42
bge-base-en-v1.5 Chen et al. (2024)	768	512	0.44	0.44
gte-large Li et al. (2023)	1024	512	0.67	0.44

Table 6: Additional models used to evaluate the properties of the text embedding space.

Figure 4: The Nemenyi-Friedman test with critical distance of multiple embedding models across all datasets and values of

k

Dataset	P(base $<$ base+mst )	P( ROPE )
ArxivClusteringP2P	0.427	0.573
ArxivClusteringS2S	0.525	0.475
BiorxivClusteringP2P	0.401	0.599
BiorxivClusteringS2S	0.331	0.669
MedrxivClusteringP2P	0.092	0.908
MedrxivClusteringS2S	0.107	0.893

Table 7: Bayesian assessment of model results comparing our approach with and without minimum spanning tree (MST) structure embedded within the graph using ROPE of 0.01.

Figure 5: Comparison of impact of strategy and model selection, averaged across datasets.

Figure 6: Correlation of the graph-level and document-level properties and the V-measure .

Text Clustering

See all 13 papers

Spectral Embeddings of Degree- $α$ Laplacians in Random Dot Product Graphs
Aug 11, 2026John Park, Ning HaoClustering Spectral Clustering
University of Hong Kong · University of Arizona
Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction
Apr 22, 2026Thinh Nguyen-Cong, Truong-Son Hy, Thang N. DinhGraph Reconstruction Spectral Methods
Department of Computer Science Virginia Commonwealth University Richmond, VA, USA · Department of Computer Science The University of Alabama at Birmingham Birmingham, AL, USA
Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling
Aug 4, 2026Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore TraniGraph Neural Networks Graph Pooling
University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy

Aug 11, 2026J/K move · Enter open · S save

Spectral Embeddings of Degree- $α$ Laplacians in Random Dot Product Graphs

John Park, Ning Hao

University of Hong Kong · University of Arizona

Clustering Spectral Clustering Graph Embedding Spectral Graph Embedding

Open paper AskPDF arXiv

Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and block-probability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.

Abstract

Text Clustering

Explore similar work

Spectral Embeddings of Degree-ααα Laplacians in Random Dot Product Graphs

Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction

Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling

Spectral Embeddings of Degree- $α$ Laplacians in Random Dot Product Graphs