Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
作者: Nina Mishra, Yonatan Naamad, Tal Wagner, Lichen Zhang
分类: cs.DS, cs.LG
发布日期: 2025-12-19
备注: 37 pages, 23 figures
💡 一句话要点
提出基于随机游走的动态更新图最近邻搜索算法，支持高效删除操作
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 近似最近邻搜索 图算法 随机游走 动态更新 数据删除
📋 核心要点
- 现有图ANN算法，如HNSW，虽然支持数据插入，但在数据删除方面存在效率低、影响查询性能等问题。
- 论文提出基于随机游走的图ANN框架，通过分析随机删除对命中时间的影响，设计确定性删除算法。
- 实验表明，该算法在查询延迟、召回率、删除时间和内存使用之间取得了更好的平衡。
📝 摘要（中文）
近似最近邻搜索（ANN）是检索相关搜索结果的常用方法，尤其是在大型语言模型和检索增强生成（RAG）的背景下。分层可导航小世界（HNSW）是ANN最广泛使用的算法之一，它基于在数据集上构建多层图。虽然该算法支持插入新数据，但不支持删除现有数据。此外，先前工作中描述的删除算法会增加查询延迟、降低召回率或延长删除时间。本文提出了一个新的基于随机游走的图ANN理论框架。然后，我们利用这个框架来分析一种随机删除方法，该方法与删除点之前的图相比，保留了命中时间统计量。接着，我们将这个理论框架转化为确定性删除算法，并通过大量的实验表明，它在查询延迟、召回率、删除时间和内存使用之间提供了更好的权衡。
🔬 方法详解
问题定义：论文旨在解决图ANN中高效数据删除的问题。现有方法在删除数据时，要么需要长时间的重建索引，要么会显著增加查询延迟或降低召回率，无法在删除效率、查询性能和内存占用之间取得良好的平衡。
核心思路：论文的核心思路是利用随机游走理论分析删除节点对图结构的影响，特别是对节点间命中时间的影响。通过保持删除节点前后命中时间统计量不变，从而尽可能地减少删除操作对查询性能的负面影响。
技术框架：该方法首先建立基于随机游走的图ANN理论框架，然后基于此框架分析随机删除策略。接着，将随机删除策略转化为确定性删除算法。该算法主要包含以下步骤：1）选择待删除节点；2）基于随机游走理论，确定需要调整的邻居节点；3）更新邻居节点的连接关系，以保持命中时间统计量不变。
关键创新：该方法最重要的创新在于将随机游走理论引入到图ANN的删除操作中，通过保持命中时间统计量来指导删除过程，从而在理论上保证了删除操作对查询性能的影响最小化。与现有方法相比，该方法不需要全局重建索引，并且能够更有效地维护图的结构。
关键设计：论文的关键设计包括：1）使用随机游走模型来刻画节点之间的关系；2）设计了基于命中时间统计量的删除策略，确保删除操作不会显著改变图的整体结构；3）将随机删除策略转化为确定性算法，使其能够在实际应用中高效执行。具体的参数设置和损失函数等细节在论文中进行了详细描述。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该算法在查询延迟、召回率、删除时间和内存使用之间取得了更好的权衡。与现有算法相比，该算法能够在保证召回率的前提下，显著降低查询延迟和删除时间，并且能够更有效地利用内存资源。具体的性能提升幅度在论文中通过大量实验数据进行了详细展示。
🎯 应用场景
该研究成果可应用于各种需要动态更新的大规模近似最近邻搜索场景，例如推荐系统、图像检索、自然语言处理等。尤其是在数据需要频繁更新或删除的应用中，该算法能够提供更高效、更稳定的搜索服务，具有重要的实际应用价值和广阔的应用前景。
📄 摘要（原文）
Approximate nearest neighbor search (ANN) is a common way to retrieve relevant search results, especially now in the context of large language models and retrieval augmented generation. One of the most widely used algorithms for ANN is based on constructing a multi-layer graph over the dataset, called the Hierarchical Navigable Small World (HNSW). While this algorithm supports insertion of new data, it does not support deletion of existing data. Moreover, deletion algorithms described by prior work come at the cost of increased query latency, decreased recall, or prolonged deletion time. In this paper, we propose a new theoretical framework for graph-based ANN based on random walks. We then utilize this framework to analyze a randomized deletion approach that preserves hitting time statistics compared to the graph before deleting the point. We then turn this theoretical framework into a deterministic deletion algorithm, and show that it provides better tradeoff between query latency, recall, deletion time, and memory usage through an extensive collection of experiments.