Page 44 - 《软件学报》2026年第3期

王嘉翼 等: 向量数据库的 K 近邻图高效更新方法 1007

by FastAdjust through a local update strategy, significantly improving update efficiency while maintaining graph quality. Specifically,
FastAdjust first employs a clustering structure based on product quantization to efficiently and accurately locate a subset of candidate
neighbors for each data point, thus narrowing the search space. Secondly, based on data density and the magnitude of embedding variation,
FastAdjust leverages their correlation with changes in the KNNs to adaptively allocate update resources according to the degree of
neighbor relationship changes, thus improving overall update efficiency. Experimental results on real-world datasets demonstrate that
FastAdjust efficiently and accurately adapts KNN graphs to embedding updates with significantly reduced computational cost, showing
strong practical value and scalability.
Key words: K-nearest neighbor (KNN) graph; approximate nearest neighbor search; embedding model

随着深度学习和嵌入技术的发展, 将非结构化数据 (如文本、图像、音频) 转化为稠密向量的嵌入模型
(embedding model) 已成为构建高效语义表示与分析系统的核心手段. 在诸如文本聚类 [2] 、推荐系统 [3] 、图神经
[1]
[7]
网络 [4–6] 建模等任务中, 基于嵌入向量构建的 K 近邻图 (K-nearest neighbor (KNN) graph) 是一种常用且有效的图
结构, 可用于刻画数据点间的相似性关系. K 近邻图通过为每个数据点连接与其最相近的 K 个邻居构建边, 从而
在向量空间中形成反映语义关系的图结构. 然而, 由于嵌入向量的维度较高, 准确构建 K 近邻图的时间成本较高.
因此, 通常采用近似方法来构建 K 近邻图, 以降低计算代价. 与之相似, 本文也聚焦于近似 K 近邻图的构建. 更准
确的 K 近邻图是后续图学习、图搜索与推荐等应用的结构基础 [8] .
然而, 随着预训练嵌入模型在实际系统中的广泛部署, 如何应对模型微调 (fine-tuning) 带来的向量语义变化,
已经成为 K 近邻图构建与更新过程中亟待解决的关键问题. 在实际应用中, 如领域自适应、图神经网络辅助建图、
交互式标签反馈以及推荐系统中的嵌入更新等场景中, 嵌入模型往往不能经过一次性训练后永久使用. 相反, 它们
需要根据特定任务的分布特征、用户行为变化或新增的反馈数据进行持续优化和微调. 例如, 在领域自适应中, 模
型需要将原始训练领域的嵌入能力迁移到目标领域; 在图建模中, 随着图结构的更新或边的变化, 节点嵌入也需随
之调整; 而在交互式系统中, 用户反馈的标签信息能够引导嵌入空间更精确地拟合当前任务需求; 对于推荐系统,
则必须根据实时用户行为和点击日志动态更新嵌入, 以保持个性化推荐的有效性. 这些任务要求嵌入模型具备良
好的可持续学习能力和对任务变化的适应能力.
在上述场景中, 嵌入模型被微调, 使得所有数据点的嵌入向量表示均发生变化, 导致原有 K 近邻图结构失效.
图 1 给出了嵌入模型微调前后 K 近邻图的变化示例, 在嵌入模型微调前后, 各个节点的嵌入向量发生变化, 导致
向量之间的距离发生变化, 进而造成 K 近邻图中存储的各个节点前 K 近的邻居信息不再准确, 需要进行更新和调整.

嵌入向量 嵌入向量

嵌入模型
微调

微调前的 微调后的
嵌入向量
嵌入向量 嵌入向量
K 近邻图 K 近邻图
节点 K 近邻 节点 K 近邻
1 38 274 508 84 … 1 194 230 84 93 …
2 468 13 689 1 005 … 2 468 1 005 874 37 …
… … … …
图 1 嵌入模型微调前后 K 近邻图的变化示例

现有的 K 近邻图构建方法虽然在静态场景下表现良好 [9–11] , 但缺乏对动态嵌入微调的支持. 现有的图增量更
新算法大多针对图中少量节点的局部变动进行优化, 如优化数据插入或删除时的索引更新 [12–18] . 然而, 这些更新方
法难以有效应对模型微调导致的全局性、同步性的嵌入向量变化. 具体来说, 这种大规模变化的动态场景面临着
以下挑战.
(1) 高维空间搜索的复杂性. 模型微调后, 由于数据均发生改变, 高维嵌入空间中数据点的近邻关系可能发生