Resumo Técnico: Consultas de Intervalo Exatas e Aproximadas para a Construção Eficiente de Ball Mapper

Declaração do Problema

O Ball Mapper é uma ferramenta de análise de dados topológicos que resume conjuntos de dados métricos finitos cobrindo-os com bolas métricas e codificando as sobreposições como um grafo. A construção deste grafo baseia-se num algoritmo guloso para selecionar um conjunto de "marcos" (um $\varepsilon$-rede), onde cada novo marco requer uma consulta de intervalo de raio fixo para identificar todos os pontos de dados dentro da distância $\varepsilon$. Para conjuntos de dados grandes ou de alta dimensão, este passo repetido de consulta de intervalo torna-se um gargalo computacional. As implementações ingênuas escalam mal tanto com o número de observações quanto com a dimensão ambiente, sofrendo com a "maldição da dimensionalidade", onde os métodos de indexação geométrica perdem eficiência de poda.

Este trabalho aborda a necessidade de implementações eficientes de consultas de intervalo no Ball Mapper. Investiga duas estratégias de aceleração: estruturas de dados espaciais hierárquicas (Ball Trees) e bibliotecas otimizadas de busca de similaridade (FAISS). Além disso, aborda o desafio específico de consultas de intervalo aproximadas. Ao contrário dos problemas de vizinhos mais próximos, onde encontrar um ponto próximo é suficiente, o Ball Mapper requer todos os pontos dentro de um raio. O artigo procura compreender como os erros de aproximação (perda de pontos ou inclusão de pontos falsos) afetam o conjunto de marcos resultante, o raio de cobertura e a topologia do grafo.

Metodologia

1. Técnicas de Aceleração

Os autores avaliam duas abordagens principais para acelerar o passo de consulta de intervalo:

• Ball Trees: Estruturas de dados hierárquicas que particionam recursivamente o conjunto de dados em subconjuntos limitados. Elas utilizam a desigualdade triangular para podar subárvores que não podem interceptar uma bola de consulta. Este método é agnóstico à métrica, mas a sua eficiência depende fortemente da geometria dos dados.
• FAISS (Facebook AI Similarity Search): Uma biblioteca otimizada para busca de similaridade de vetores densos.
  • Aceleração Exata: Utilizando índices planos (ex: IndexFlatL2) que aproveitam a vetorização SIMD, rotinas BLAS e multithreading para acelerar os cálculos de distância sem alterar a complexidade algorítmica ou o conjunto de pontos retornados (até à precisão de ponto flutuante).
  • Aceleração Aproximada: Utilizando índices não exaustivos (ex: IndexIVFFlat, IndexHNSWFlat) ou índices comprimidos (ex: IndexPQ, IndexSQ). Estes métodos reduzem o tempo de execução ou a memória ao examinar apenas um subconjunto de dados ou utilizar representações comprimidas, potencialmente alterando o conjunto de pontos retornados.

2. Estrutura Teórica para Aproximação

O artigo distingue entre consultas de intervalo exatas e aproximadas formulando modelos de erro determinísticos:

• Modelo de Erro Aditivo: Um oráculo é $\delta$-preciso se o conjunto de intervalo aproximado $\tilde{R}_\varepsilon(q)$ satisfizer $R_{\varepsilon-\delta}(q) \subseteq \tilde{R}_\varepsilon(q) \subseteq R_{\varepsilon+\delta}(q)$.
• Modelo de Erro Multiplicativo: Uma distância aproximada $\tilde{d}$ tem erro relativo $\eta$ se $(1-\eta)d \le \tilde{d} \le (1+\eta)d$.
• Aproximação Conservadora: Um oráculo é conservador se $\tilde{R}_\varepsilon(q) \subseteq R_\varepsilon(q)$, o que significa que pode perder pontos verdadeiros (falsos negativos), mas nunca inclui pontos fora da bola verdadeira (sem falsos positivos).

Os autores provam que, sob estes modelos de erro:

• O conjunto de marcos resultante $L$ permanece uma $(\varepsilon+\delta)$-cobertura e é $(\varepsilon-\delta)$-separado.
• O nervo aproximado (e, portanto, o grafo) situa-se entre os nervos exatos computados nas escalas $\varepsilon-\delta$ e $\varepsilon+\delta$.
• Aproximações conservadoras garantem que as $\varepsilon$-bolas exatas dos marcos computados ainda cobrem o conjunto de dados, embora os marcos possam não ser estritamente $\varepsilon$-separados.

3. Avaliação Empírica

Experiências foram conduzidas em conjuntos de dados sintéticos com geometrias variadas:

• Gaussiana Isotrópica: Dados de alta dimensão sem estrutura definida.
• Mistura Gaussiana: Dados agrupados (clustered).
• Curva 1D com Ruído: Dados estruturados de baixa dimensão intrínseca.

O estudo comparou Ball Tree, FAISS (flat, IVF, HNSW) e o baseline pyBallMapper em termos de tempo de execução, uso de memória e comportamento de escalonamento. Crucialmente, os experimentos de aproximação focaram-se na estabilidade estrutural (recall/precisão de intervalo, recall/precisão de arestas, contagem de marcos e separação) em vez de apenas velocidade.

Principais Resultados

Desempenho Computacional

• Tempo de Execução: O FAISS (índice plano) demonstrou o melhor desempenho de tempo de execução, mantendo tempos baixos mesmo à medida que o tamanho do conjunto de dados ($n$) e a dimensão ($D$) aumentavam. Alcançou acelerações de mais de duas ordens de magnitude em comparação com o pyBallMapper em cenários de alta dimensão. As Ball Trees funcionaram bem em baixas dimensões, mas degradaram rapidamente à medida que $D$ aumentava.
• Escalonamento: A regressão log-log mostrou o pyBallMapper a aproximar-se de um escalonamento quadrático ($p \approx 2$) com a dimensão, enquanto o FAISS e as Ball Trees mantiveram expoentes de escalonamento significativamente mais baixos ($p < 1.7$).
• Memória: O FAISS exibiu a maior pegada de memória devido às representações de vetores densos e estruturas de indexação. As Ball Trees e o pyBallMapper foram mais eficientes em termos de memória.

Efeitos Estruturais da Aproximação

• Comportamento Conservador: Em todas as configurações de FAISS testadas (IVF e HNSW), as consultas de intervalo aproximadas foram conservadoras. Produziram zero falsos positivos (a precisão foi de 1.0), mas introduziram falsos negativos (o recall foi < 1.0).
• Impacto na Estrutura do Grafo:
  • Perda de Arestas: O principal efeito estrutural foi a remoção de arestas (esparsificação) devido a membros de intervalo perdidos.
  • Seleção de Marcos: Em experiências de ponta a ponta, os falsos negativos fizeram com que alguns pontos permanecessem descobertos, levando à seleção de marcos adicionais e próximos. Isto reduziu a separação mínima dos marcos abaixo de $\varepsilon$, embora o raio de cobertura tenha permanecido próximo do $\varepsilon$ alvo.
• Dependência da Geometria: A sensibilidade à aproximação variou significativamente conforme a geometria dos dados:
  • Gaussiana Isotrópica: Mais sensível. Configurações de aproximação moderadas resultaram em perda significativa de arestas (ex: IVF com $nprobe=32$ recuperou apenas ~31% das arestas).
  • Mistura Gaussiana: Mais estável devido à estrutura agrupada, que fornece múltiplas testemunhas para interseções de bolas.
  • Curva com Ruído: Mais estável. A estrutura de baixa dimensão permitiu que os índices aproximados recuperassem quase 100% das memberships e arestas, mesmo com parâmetros agressivos.

Significância e Alegações

O artigo alega fornecer um quadro rigoroso para integrar a busca aproximada na análise de dados topológicos sem comprometer as garantias teóricas da construção do Ball Mapper. As suas principais contribuições são:

1. Implementação: Desenvolve e compara as implementações de Ball Tree e FAISS para a construção gulosa do Ball Mapper, demonstrando que o FAISS oferece escalabilidade superior para conjuntos de dados euclidianos de alta dimensão e grande escala.
2. Limites Teóricos: Estabelece limites determinísticos mostrando que as consultas de intervalo aproximadas (sob modelos de erro aditivo ou multiplicativo) resultam em conjuntos de marcos e grafos que são limitados por construções exatas em escalas ligeiramente perturbadas.
3. Caracterização Empírica: Demonstra que os índices aproximados padrão do FAISS comportam-se de forma conservadora (sem falsos positivos), tornando-os seguros para a construção do Ball Mapper, desde que o utilizador aceite a potencial esparsificação de arestas e variações menores na separação de marcos.
4. Sensibilidade à Geometria: Destaca que a estabilidade do Ball Mapper aproximado não é uniforme; depende fortemente da geometria intrínseca dos dados, sendo as estruturas agrupadas e de baixa dimensão mais robustas a erros de aproximação do que os dados gaussianos isotrópicos de alta dimensão.

Os autores concluem que, embora a definição de Ball Mapper não precise de mudar, a sua implementação computacional pode ser significativamente melhorada utilizando o FAISS. No entanto, os utilizadores devem estar cientes de que a aproximação introduz um compromisso: redução do custo computacional em troca de uma potencial perda de conectividade do grafo e redução da separação dos marcos, cuja severidade é ditada pela estrutura geométrica dos dados.