通过逐步构建邻居图，解决文本聚类中图不连通问题。
Incremental Graph Construction Enables Robust Spectral Clustering of Texts
- 新方法按顺序插入节点并连接最近的k个已有节点，确保图始终连通。
- 在低k值下（如k=5）性能显著优于传统k-NN，且保持稳定。
- 适合增量更新场景，适用于大规模文本聚类任务。
邻域图是文本嵌入谱聚类中的关键步骤，但在真实文本数据集上，标准k-NN图在低稀疏度（小k）时常出现大量孤立连通分量，导致谱聚类退化且对超参数敏感。本文提出一种简单的增量式k-NN图构建方法：每个新节点仅与之前插入的k个最近节点相连，该策略保证了任意k值下图的连通性。我们提供了归纳法证明其连通性，并讨论了新文档到来时的增量更新能力。在大规模文本嵌入基准（Massive Text Embedding Benchmark）的六个聚类数据集上，使用SentenceTransformer嵌入和拉普拉斯特征映射验证该方法。相比标准k-NN图，本方法在低k区域表现更优，且在较大k值下性能相当。
原文摘要 · Abstract (English)
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$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。