Papers
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
Yu. A. Malkov, D. A. Yashunin · IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI); preprint arXiv:1603.09320, 2018
O problema: busca de vizinhos mais próximos em escala
A busca dos K vizinhos mais próximos (K-NNS) parte de uma função de distância entre elementos e procura, no conjunto armazenado, os K elementos mais próximos de uma consulta. Ela aparece em aplicações como aprendizado de máquina não paramétrico, casamento de características de imagens em bases grandes e recuperação semântica de documentos. A abordagem ingênua calcula a distância da consulta para todos os elementos, e por isso o custo cresce linearmente com o tamanho da base, o que inviabiliza conjuntos grandes. Soluções exatas só trazem ganho substancial de velocidade quando os dados têm poucas dimensões, por causa da chamada maldição da dimensionalidade. A saída é a busca aproximada (K-ANNS), que aceita um pequeno número de erros em troca de velocidade. A qualidade de uma busca inexata é medida pelo recall: a razão entre os vizinhos verdadeiros encontrados e K. O paper lista como famílias populares de K-ANNS as versões aproximadas de algoritmos em árvore, o hashing sensível à localidade (LSH) e a quantização de produto (PQ). Os algoritmos baseados em grafos de proximidade ganharam popularidade por render melhor em dados de alta dimensão, mas o paper aponta que o roteamento deles escala como lei de potência e degrada muito em dados de baixa dimensão ou agrupados em clusters. É nesse ponto que o HNSW propõe uma estrutura incremental, totalmente baseada em grafo, com escala logarítmica.
Grafos navegáveis (NSW) e por que ainda não bastavam
Nos grafos de proximidade, a busca é um roteamento guloso: parte de um ponto de entrada, examina as distâncias da consulta aos vizinhos do nó atual e salta para o vizinho mais próximo, guardando os melhores candidatos até que uma condição de parada seja atendida. O Navigable Small World (NSW) é um grafo construído inserindo os elementos em ordem aleatória e ligando cada novo elemento, nos dois sentidos, aos M vizinhos mais próximos entre os já inseridos. Os vínculos feitos no começo da construção viram pontes entre hubs e mantêm o grafo conectado, o que permite que o número de saltos do roteamento guloso cresça de forma logarítmica com o tamanho da rede. Mesmo assim, o paper explica que o custo total de uma busca no NSW é aproximadamente o número de saltos multiplicado pelo grau médio dos nós no caminho, e esse grau também cresce de forma logarítmica por dois motivos: a busca tende a passar pelos mesmos hubs à medida que a rede cresce, e o número médio de conexões desses hubs cresce de forma logarítmica com o tamanho da rede. O resultado é uma escala polilogarítmica, e não logarítmica. Há ainda uma fase inicial de zoom-out, em que a busca começa em nós de grau baixo e pode ficar presa em um mínimo local falso e distante. Iniciar a busca em um hub ajuda, segundo os testes citados, mas mantém a escala polilogarítmica e rende menos em dados de alta dimensão do que o HNSW.
A ideia central: camadas hierárquicas, como uma skip list
O HNSW separa os vínculos do grafo pela escala de seu comprimento, distribuindo-os em camadas. Cada elemento recebe um nível máximo sorteado com probabilidade que decai exponencialmente, de modo que as camadas superiores contêm subconjuntos cada vez menores dos elementos e o número esperado de camadas cresce de forma logarítmica. Em cada camada há um grafo de proximidade, e as camadas altas têm os vínculos mais longos. A busca começa no ponto de entrada da camada mais alta e faz roteamento guloso até chegar a um mínimo local. Em seguida desce uma camada, reinicia a partir desse elemento e repete o processo até a camada zero, onde estão todos os elementos. Como o número máximo de conexões por elemento pode ser constante em todas as camadas, só uma fração fixa dos vínculos é avaliada por elemento, independentemente do tamanho da rede. Na inserção, o novo elemento sorteia seu nível, desce pelas camadas acima desse nível com busca gulosa simples e, a partir do seu nível, procura vizinhos em cada camada para se conectar. Como a aleatoriedade vem do sorteio de níveis, não é preciso embaralhar os elementos antes da inserção, o que permite indexação incremental. O paper aponta a semelhança com a skip list probabilística, em que as listas encadeadas são substituídas por grafos de proximidade.
Parâmetros: M, mL, Mmax0, efConstruction e ef
O paper descreve poucos parâmetros com papéis distintos. M é o número de conexões que um elemento estabelece na inserção; o paper o apresenta como o único parâmetro de construção realmente relevante para o usuário, com faixa razoável de 5 a 48. Em suas simulações, M menor tende a funcionar melhor com recall baixo ou dados de baixa dimensão, e M maior com recall alto ou dados de alta dimensão. M também define o consumo de memória, que é proporcional a ele. O parâmetro mL normaliza a geração dos níveis; o paper sugere 1/ln(M) como escolha simples, e mL igual a zero equivale a uma única camada. Mmax0 é o máximo de conexões na camada zero, e 2·M é a sugestão do paper, pois fixá-lo em M penaliza muito o recall alto e valores maiores pioram o desempenho e gastam memória. O efConstruction é o tamanho da lista dinâmica de candidatos durante a construção; deve ser grande o bastante para que o recall da busca na construção fique próximo de 1 (o paper diz que 0,95 basta na maioria dos casos). Já o ef é o tamanho da lista de candidatos durante a consulta e controla a qualidade da busca. O paper também descreve uma heurística de seleção de vizinhos que escolhe conexões diversas, em vez de só as mais próximas. Em todos os casos testados ela deu desempenho igual ou maior que a ligação simples aos mais próximos, com efeito mais forte em dados de baixa dimensão, em recall alto para dados de dimensão média e em dados muito agrupados.
Trade-offs: recall, latência, construção e memória
No HNSW, o botão de consulta é o ef: uma lista de candidatos maior examina mais vizinhança e eleva o recall, ao custo de mais cálculos de distância e mais tempo por consulta. Em experimentos com dados aleatórios de 4 dimensões, o paper mostra que o ef necessário para atingir um recall fixo satura ao crescer a base, o que sustenta a escala logarítmica observada em baixas dimensões; o paper ressalta que, para alta dimensão, essa evidência empírica não foi possível e faltam argumentos analíticos. Na construção, o efConstruction troca tempo de indexação por qualidade: para 10 milhões de vetores SIFT, um índice de qualidade razoável com efConstruction=100 foi construído em cerca de 3 minutos num servidor Xeon de 4 processadores de 10 núcleos, e aumentar ainda mais o valor trouxe pouco ganho com tempo bem maior. A memória é dominada pelas conexões; com M típico entre 6 e 48 e links de 4 bytes, o paper estima cerca de 60 a 450 bytes por objeto, sem contar os dados. Na comparação em espaços euclidianos (ann-benchmark, uma thread), o HNSW superou com folga o NSW de base, o FLANN, o Annoy, o VP-tree e o FALCONN nos conjuntos SIFT, GloVe, DEEP e CoPhIR; em dados de baixa dimensão (d=4), foi só um pouco mais rápido que o Annoy em recall alto, embora tenha superado com folga os demais. O paper também afirma que a construção pode ser paralelizada com poucos pontos de sincronização e sem efeito mensurável na qualidade do índice.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.