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

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

向量的索引, 计算该索引内相似向量节点的邻居连接数的平均值. 该指标直接反映了相似数据节点与图中其他部
分建立有效连接的程度. 从理论上看, 在过度剪枝效应的影响下, 新插入的相似节点在选择邻居时会过早地丢弃大
量候选邻居, 从而难以建立足够数量的多样化连接. 因此, 较低水平的平均邻居连接数可视为图的局部探索能力下
降和结构性孤岛形成的直接表现, 亦是导致宏观召回率退化的关键微观因素.
实验结果表明, 批量插入相似数据会导致召回率的显著下降. 为了探究其内在的结构性根源, 本节将聚焦于图
的微观拓扑层面, 通过观测相似向量的平均邻居数量 (向量的平均邻居连接数) 这一指标来量化分析索引内部连
接模式的动态演变. 表 1 展示了多个数据集中相似向量更新时节点的平均邻居连接和较小邻居数量向量的占比情
况. 其中, 相似向量邻居数量较小向量的占比表示: 相似向量中, 向量的邻居数量小于等于 3 的向量的占比. 同理,
非相似向量邻居数量较小向量的占比代表非相似向量中的该特性.

表 1 向量邻居数量分析

相似向量平均 非相似向量平均 相似向量邻居数量较小 非相似向量邻居数量较小
数据集 索引参数
邻居数量 邻居数量 向量的占比 (%) 向量的占比 (%)
GIST1M M=24, efC=64 6.4 9.0 60 29
Enron M=24, efC=64 9.0 9.8 53 22
MSong M=48, efC=100 4.6 14.5 95.7 37

随着相似数据在索引中持续累积, 新插入的相似数据节点的连接数呈现较低水平, 低于基础索引的平均邻居
数. 例如, MSong 相似数据的平均邻居数为 4.6, 而基础向量的平均邻居数为 14.5, 相似向量的邻居数量较小向量
的占比达到了 95.7%, 说明相似向量多数向量邻居数量都较小, 少数向量连接数量较多, 这种连接势必会影响图结
构的连通性. 在 GIST1M 和 Enron 数据集上, 相似向量的平均邻居数和相似向量的邻居数量较小向量的占比都低
于基础向量.
这一现象表明, 在新插入相似数据时, 索引中已有的相似数据会影响其所选邻居的质量, 并产生了显著的抑制
作用. 这种微观拓扑上的连接受损现象, 与第 2.2 节的召回率退化趋势相吻合. 在更大的索引参数下, 同样表现出
平均邻居数随相似数据占比增加而下降的趋势, 只是其稀疏程度减弱. 此现象进一步印证局部连通性受损的问题
普遍存在, 难以仅通过调优构建参数来规避. 综上所述, 实验结果为召回率退化问题提供了更为直接的证据. 它揭
示了在召回率下降的同时, 索引局部的连通性有所减弱.
2.4 召回率下降的原因分析
第 2.2 和 2.3 节的实验结果表明, 在批量插入相似向量场景下, HNSW 索引的召回率呈现显著下降的趋势; 描
述邻居关系的微观数据显示, 相似数据聚集区域的节点平均邻居数量相较于其他区域显著偏低. 本节将深入剖析
上述现象背后的成因.
● HNSW 启发式规则的系统性误判与过度剪枝. HNSW 的启发式规则的设计初衷是最大化邻居集的多样性.
然而, 当大量相似向量被集中写入索引时, 节点的候选邻居集呈现出局部过度致密的特性, 即邻居之间的距离普遍
较小. 在这种高度同质化的候选环境中, 该启发式规则会发生系统性误判: 算法倾向于保留少数空间区域无重叠的
邻居, 将大量连接错误地识别为冗余连接并予以剪除, 而这些连接可能提供新的探索方向.
如图 6 所示, 过度剪枝的行为切断了图中潜在的有效搜索路径. 图 6(a) 表示为向量 G 选取邻居的过程, D 已
经成为 C 的邻居, 向量 G 在候选集合中, 其中, 虚线所标注的浅绿色区域为向量 D 的辐射区域, 当出现 GC>GD 的
情况时, GC 不会连接, 即 G 未成为 C 的邻居. 同理, 图 6(b) 是为向量 D 选取邻居的过程, E 已经成为 D 的邻居, 向
量 G 在候选集合中, 当出现 GD>GE 的情况时, GD 不会连接, 即 G 无法成为 D 的邻居. 图 6(c) 展示了从向量 A 出
发查询目标点 G 时的查询路径, 其搜索路径到达节点 E, 但 E 是更远的点, 因为缺乏 CG 与 DG 这些连接边, 可能
会陷入局部最优, 因此 E 未被探索, 最终导致召回失败. 在批量插入相似数据时, G 周围的更新都面临这种剪枝的
影响.
● 相似向量的连接稀疏化. 在批量插入相似数据的过程中, 过度剪枝会被不断放大并累积, 逐步演变为索引结