HNSW

HNSW (Hierarchical Navigable Small World — иерархический навигационный малый мир) — это алгоритм приближённого поиска ближайших соседей (ANN, Approximate Nearest Neighbor), основанный на построении многоуровневой графовой структуры. Алгоритм предназначен для эффективного поиска векторов, наиболее близких к заданному запросу в многомерном пространстве, и широко применяется в системах векторного поиска, рекомендательных сервисах и базах данных для машинного обучения.

История

Алгоритм HNSW был предложен в 2016 году российским исследователем Юрием Алексеевичем Малковым (Yury A. Malkov) и его соавторами в статье «Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs». Работа была опубликована в журнале IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). Разработка стала развитием идей, заложенных в алгоритмах Navigable Small World (NSW) и других графовых методов поиска ближайших соседей.

До появления HNSW существовали методы, такие как NSW, которые строили один граф, соединяющий точки данных. HNSW усовершендовал эту идею, добавив иерархическую структуру, напоминающую пропускные списки (skip lists), что позволило значительно ускорить поиск за счёт многоуровневого приближения.

С момента публикации HNSW стал одним из самых популярных алгоритмов ANN, используемым в таких проектах, как Faiss (Facebook AI Research), NMSLIB (Non-Metric Space Library), Milvus, Qdrant и Weaviate. В 2020-х годах он остаётся эталоном по соотношению скорости и точности для многих задач векторного поиска.

Принцип работы

Navigable Small World (NSW)

Основой HNSW является концепция Navigable Small World (NSW) — графа, в котором вершины (векторы данных) соединены рёбрами таким образом, что среднее расстояние между любыми двумя вершинами (длина кратчайшего пути) растёт логарифмически от числа вершин. В NSW поиск начинается с произвольной точки и итеративно переходит к соседям, наиболее близким к запросу, пока не будет достигнут локальный минимум расстояния. Этот процесс напоминает жадный поиск (greedy search).

Иерархическая структура

HNSW добавляет к NSW несколько уровней (слоёв) графа. Каждый уровень представляет собой подмножество точек данных, причём нижний уровень (уровень 0) содержит все точки, а каждый следующий уровень содержит меньшее количество точек, отобранных случайным образом. Вероятность включения точки на уровень l определяется экспоненциальным распределением: P(l) = exp(-l / mL), где mL — параметр, контролирующий плотность уровней.

• Верхние уровни содержат редкие, «дальние» связи между точками. Они позволяют быстро перемещаться по всему пространству, делая большие «скачки» к областям, потенциально содержащим ближайших соседей.
• Нижние уровни содержат более плотные, локальные связи. Они обеспечивают точное нахождение ближайших соседей в окрестности, найденной на верхних уровнях.

Поиск

Поиск в HNSW начинается на самом верхнем уровне с некоторой точки входа. Алгоритм выполняет жадный поиск на этом уровне, переходя к соседям, пока не найдёт локальный минимум. Затем он спускается на уровень ниже, используя найденную точку как начальную, и повторяет процесс. На каждом уровне поиск уточняется, и на нижнем уровне (уровне 0) алгоритм возвращает k ближайших соседей.

Вставка

При вставке нового вектора алгоритм случайным образом определяет максимальный уровень, на котором будет присутствовать эта точка. Затем он находит ближайших соседей на каждом уровне от верхнего до нижнего, устанавливая с ними двунаправленные рёбра. Для ограничения степени вершин (числа рёбер) используется параметр M (максимальное число связей на уровень). При превышении лимита часть рёбер отсекается по принципу наибольшего расстояния.

Параметры алгоритма

HNSW имеет несколько ключевых параметров, влияющих на производительность и точность:

• M — максимальное количество двунаправленных связей (рёбер) на один узел на каждом уровне, кроме нижнего. Обычно M находится в диапазоне от 8 до 64. Более высокое M увеличивает точность, но замедляет вставку и поиск из-за большего числа рёбер.
• efConstruction (ef_construction) — размер динамического списка кандидатов при построении графа. Чем выше значение, тем точнее строится граф, но тем дольше выполняется вставка. Типичные значения — от 100 до 500.
• efSearch (ef) — размер динамического списка кандидатов при поиске. Увеличение efSearch повышает точность (recall) за счёт увеличения времени поиска. Значение может варьироваться от 10 до нескольких тысяч.
• mL (max level) — параметр, определяющий нормализацию экспоненциального распределения для выбора уровня. Влияет на количество уровней в иерархии. Обычно устанавливается как 1 / ln(M).

Преимущества и недостатки

Преимущества

• Высокая скорость поиска: HNSW демонстрирует логарифмическую сложность поиска по числу элементов, что делает его одним из самых быстрых алгоритмов ANN для больших наборов данных (миллионы и миллиарды векторов).
• Хорошая точность: При правильной настройке параметров HNSW достигает очень высокой точности (recall > 0.99) при умеренном времени поиска.
• Динамичность: Алгоритм поддерживает вставку и удаление элементов без перестроения всей структуры, что важно для потоковых данных.
• Не требует обучения: В отличие от некоторых методов (например, Product Quantization), HNSW не требует предварительного обучения на данных.

Недостатки

• Высокое потребление памяти: Хранение графа с рёбрами требует значительного объёма оперативной памяти, особенно при больших значениях M. Для миллиардов векторов это может стать ограничением.
• Сложность настройки: Подбор оптимальных параметров (M, efConstruction, efSearch) может требовать экспериментов и зависит от конкретного набора данных.
• Чувствительность к размерности: Хотя HNSW работает лучше многих других методов, его производительность может снижаться при очень высокой размерности векторов (например, более 1000), когда эффект «проклятия размерности» становится существенным.
• Не поддерживает точный поиск: HNSW является приближённым методом и не гарантирует нахождение точных ближайших соседей, хотя при высоких значениях efSearch может приближаться к точному результату.

Применение

HNSW широко используется в современных системах, где требуется быстрый поиск по векторным представлениям:

• Векторные базы данных: Milvus, Qdrant, Weaviate, Pinecone, Chroma используют HNSW как один из основных алгоритмов индексации.
• Библиотеки для машинного обучения: Faiss (Facebook AI Research) включает реализацию HNSW (класс IndexHNSWFlat). NMSLIB (Non-Metric Space Library) также содержит HNSW.
• Рекомендательные системы: Поиск похожих товаров, фильмов, музыки на основе векторных эмбеддингов.
• Поиск изображений и видео: Нахождение визуально похожих изображений по признакам, извлечённым нейросетями.
• Обработка естественного языка (NLP): Поиск семантически близких текстов, документов, предложений по векторным представлениям (например, от моделей BERT, Sentence-BERT).
• Биоинформатика: Поиск похожих последовательностей ДНК или белков.
• Системы безопасности: Поиск похожих лиц в базах данных.

Сравнение с другими методами ANN

HNSW часто сравнивают с другими популярными алгоритмами приближённого поиска ближайших соседей:

• IVF (Inverted File Index): Основан на кластеризации. Быстрее при вставке, но медленнее при поиске и менее точен, чем HNSW, для больших наборов данных.
• Product Quantization (PQ): Сжимает векторы, экономя память, но жертвует точностью. HNSW обычно точнее, но требует больше памяти.
• LSH (Locality-Sensitive Hashing): Использует хеширование. Может быть быстрым, но часто менее точен, чем HNSW, и требует настройки хеш-функций.
• NSW (Navigable Small World): Предшественник HNSW. HNSW значительно превосходит NSW по скорости поиска за счёт иерархической структуры.

В бенчмарках (например, ANN-Benchmarks) HNSW часто занимает лидирующие позиции по скорости при заданном уровне точности (recall), особенно для наборов данных с размерностью до 1000.

Интересные факты

• Автор алгоритма Юрий Малков работал в Институте прикладной математики имени М. В. Келдыша РАН и впоследствии в компании Google.
• HNSW вдохновлён структурой пропускных списков (skip lists), которые также используют многоуровневую иерархию для ускорения поиска в одномерных данных.
• В 2021 году HNSW был признан одним из наиболее цитируемых алгоритмов в области информационного поиска и баз данных.
• Реализация HNSW в библиотеке Faiss от Facebook (организация Meta признана экстремистской и запрещена в РФ) является одной из самых популярных и оптимизированных.

Источники

1. Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824-836.
2. Malkov, Y. A., & Yashunin, D. A. (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv preprint arXiv:1603.09320.
3. Aumüller, M., Bernhardsson, E., & Faithfull, A. (2017). ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87, 101-115.
4. Документация библиотеки Faiss (Facebook AI Research). IndexHNSWFlat.
5. Документация векторной базы данных Milvus. HNSW Index.
6. Документация векторной базы данных Qdrant. HNSW Index.