[Paper] 邻域稳定性作为最近邻搜索性的度量
发布: (2026年2月19日 GMT+8 02:09)
7 分钟阅读
原文: arXiv
Source: arXiv - 2602.16673v1
概述
本文提出 Neighborhood Stability（邻域稳定性），这是一种轻量级、仅基于数据的方式，用于预测基于聚类的近似最近邻搜索（ANNS）在给定高维数据集上的表现。通过衡量聚类内部和跨聚类的最近邻关系的“稳定性”，作者提供了两个实用指标，使工程师能够提前判断基于聚类的 ANNS 流水线是否可能准确——无需先进行昂贵的搜索实验。
关键贡献
- Clustering‑Neighborhood Stability Measure (clustering‑NSM) – 一个内部质量度量，通过观察真实最近邻在同一簇中保持的频率来评估给定的聚类。
- Point‑Neighborhood Stability Measure (point‑NSM) – 一个数据集层面的“可聚类性”得分，可在执行任何聚类之前预测 clustering‑NSM 的值before任何聚类被执行。
- Theoretical link – point‑NSM 与 clustering‑NSM 之间的理论关联，表明高 point‑NSM 意味着高 clustering‑NSM，从而提升 ANNS 的准确性。
- Empirical validation – 在多个真实世界的高维基准（图像嵌入、文本向量、推荐数据）上进行实证验证，确认两种度量与流行的基于聚类的 ANNS 方法（如 IVF、ScaNN）的 recall@k 强相关。
- Distance‑agnostic design – 这些度量仅依赖最近邻关系（排名），而非原始欧氏距离，使其可用于内积、余弦相似度或自定义相似度函数。
方法论
- 定义邻居集合 – 对数据集中的每个点 (x_i)，计算其前 (k) 个真实最近邻（使用精确度量）。
- Clustering‑NSM
- 给定一个平面聚类（例如 k‑means、层次 k‑means），统计每个点的 (k) 个真实邻居中有多少落在与该点相同的簇中。
- 在所有点上对该计数进行归一化，得到 ([0,1]) 区间的稳定性得分；得分越高表示聚类越尊重真实邻居关系。
- Point‑NSM
- 在没有任何聚类的情况下，检查 相互 最近邻图：如果两个点互相出现在对方的前 (k) 列表中，则它们相连。
- 计算相互最近邻图形成紧密连通分量（高导电率）的点的比例。这反映了数据自然划分为稳定邻域的程度。
- 预测流水线 – 使用 point‑NSM 估计选定聚类算法及其超参数（例如中心数）的预期 clustering‑NSM。
- 评估 – 在相同数据集上运行标准的基于聚类的 ANNS 流水线（IVF‑Flat、IVF‑PQ、ScaNN），测量 recall@k，并与两个稳定性得分进行相关性分析。
结果与发现
| 数据集 (嵌入维度) | Point‑NSM | Clustering‑NSM (IVF‑Flat) | Recall@10 (IVF‑Flat) |
|---|---|---|---|
| ImageNet‑ResNet (128) | 0.78 | 0.71 | 0.92 |
| SQuAD‑BERT (768) | 0.62 | 0.55 | 0.81 |
| MovieLens‑ALS (64) | 0.84 | 0.80 | 0.95 |
- 强线性相关（Pearson ≈ 0.88），在所有测试方法中，clustering‑NSM 与 recall 之间呈现高度相关性。
- Point‑NSM 能预测 clustering‑NSM，(R^{2}) 为 0.81，意味着可以在聚类之前估计 ANNS 性能。
- 当将欧氏距离替换为余弦相似度或内积时，指标保持稳定，验证了距离无关的行为。
- 对于 point‑NSM 较低的数据集（例如噪声大或点分布均匀），基于聚类的 ANNS 一致表现不佳，建议考虑使用图结构或乘积量化等替代索引方式。
实际意义
- 部署前的健全性检查 – 在投入计算资源构建 IVF 或 ScaNN 索引之前，先在样本上运行廉价的最近邻图并计算 point‑NSM。得分低表明基于聚类的 ANNS 可能会导致召回率差。
- 超参数调优捷径 – Point‑NSM 可以指导中心数量的选择：更高的 point‑NSM 允许使用更少的中心而仍保持精度，从而节省内存和索引时间。
- 跨度量可移植性 – 由于这些度量仅需邻居排名，它们可以应用于任何模型的嵌入（视觉、语言、推荐），无需重新推导特定距离的公式。
- 混合流水线 – 对于混合数据集（某些子空间高稳定性，其他则不），可以基于 point‑NSM 对数据进行划分，仅在合理的地方使用基于聚类的 ANNS，在其他地方回退到基于图的搜索。
- 漂移监控 – 在生产环境中，定期在新摄入的数据上重新计算 point‑NSM，以检测数据分布是否已发生足以削弱现有 ANNS 索引的漂移。
限制与未来工作
- 精确邻居计算是获取指标的真实邻居集合所必需的，这在大规模数据集上可能代价高昂；作者建议使用近似邻居图作为代理，但这会引入噪声。
- 本研究聚焦于 平面（单层）聚类；将稳定性概念扩展到层次或多层索引（例如 HNSW‑IVF 混合）仍是未解决的问题。
- Point‑NSM 假设固定的 (k)（通常为 10–20）；对该超参数的敏感性尚未充分探讨。
- 实际系统常常结合多种相似度函数（例如内积与欧氏距离的混合）；在混合度量下评估稳定性是未来的工作方向。
作者
- Thomas Vecchiato
- Sebastian Bruch
论文信息
- arXiv ID: 2602.16673v1
- 类别: cs.LG, cs.IR
- 出版时间: 2026年2月18日
- PDF: 下载 PDF