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

1016 软件学报 2026 年第 37 卷第 3 期

但其忽略了微调前后向量变化幅度有限的事实, 从头计算所有邻居关系, 需要花费大量时间, 难以在有限时间内
完成有效更新, 因而在短时间内获得的 K 近邻图质量仍然较差, 召回率远低于 FastAdjust. 另一方面, 尽管
NN-descent-init 方法尝试以旧图作为初始化加速更新过程, 但其在图结构更新过程中, 仍然没有考虑微调前后向
量的关联, 产生大量冗余的计算与判断, 导致整体效率较低, 在有限的适应时间内准确度较低.

Stale NN-descent NN-descent-init FastAdjust
100 100 100
97.6
95.5
96.4
95 90 95 93.2
召回率 (%) 90 89.0 召回率 (%) 86.0 召回率 (%) 90

85 84.0 85.0 80 85 85.4
73.1 37.2
72.0
(Stale)
80 70 80
(a) Stack (b) Wiki (c) DigiFace
图 7 不同方法更新 K 近邻图, 3 min 后召回率的比较

相较而言, FastAdjust 充分利用了微调前的 K 近邻图结构以及微调前后向量变化幅度有限这一关键特性. 它
通过聚类引导的候选邻居定位策略和基于局部密度的动态更新资源分配机制, 显著提高了 K 近邻图更新的效率
和质量. 在相同的时间限制下, FastAdjust 能够更快地为每个样本重新识别更准确的近邻, 从而在较短的更新时间
内显著提升召回率.
4.3 时间效率比较
本文对比分析了不同方法在 K 近邻图调整过程中, 召回率随更新时间变化的表现, 结果如图 8 所示. 从图中
可以看出, FastAdjust 能够在极短的时间内显著修复因嵌入向量微调而准确度下降的 K 近邻图, 快速提高其召回
率. 例如, 在 Stack 数据集上, FastAdjust 在 2 min 内即达到了 95% 的召回率, 而排名第 2 的 NN-descent-init 达到
95% 的召回率则耗时 13.4 min, 前者在效率上实现了 6.7 倍的提升. 整体来看, 与其他方法相比, FastAdjust 在达到
高召回率所需时间上具有显著优势, 体现了其在效率上的卓越性能.

Stale NN-descent NN-descent-init FastAdjust
0.98 0.97 0.98
0.96 0.95 0.9 0.94 0.8 0.84 0.88 0.78
0.95
召回率 (%) 0.90 0.91 0.90 0.94 召回率 (%) 0.8 0.84 0.87 0.89 召回率 (%) 0.6 0.67
0.45
0.85 0.84 0.86 0.72 0.4 0.37
0 10 20 30 40 0 10 20 30 40 50 0 2 4 6 8 10
时间 (min) 时间 (min) 时间 (min)
(a) Stack (b) Wiki (c) DigiFace
图 8 不同方法 K 近邻图召回率随更新时间的变化

这种效率提升归功于 FastAdjust 所采用的一系列高效更新策略: 一方面, 其基于乘积量化的数据定位方法能
够准确识别需要更新的区域, 显著减少了冗余计算; 另一方面, 其根据数据密度动态分配检查次数的机制, 有效提
升了资源利用效率, 进而提升更新效率. 这些策略共同保障了 FastAdjust 在效率和精度之间实现了良好的平衡.
4.4 图结构准确度的评估

K 近邻图本身的结构信息反映了不同数据点之间的相关关系, 例如不同数据点的入度即衡量了其在全局中与
其他数据的密切程度. 一个质量更高的 K 近邻图不仅应该在近邻关系的召回率上取得较高的结果, 也应该尽可能
与真实的 K 近邻图保留相似的图结构. 为了评估建立出的 K 近邻图结构上与真实的 K 近邻图的差异, 我们还计
算了各个节点入度与真实 K 近邻图的入度的均方根误差 (RMSE), 从图的结构层面进行评估.