Sintesi Tecnica: Query di Intervallo Esatte e Approssimate per la Costruzione Efficiente di Ball Mapper

Definizione del Problema

Ball Mapper è uno strumento di analisi topologica dei dati che riassume dataset metrici finiti coprendoli con sfere metriche e codificando le sovrapposizioni come un grafo. La costruzione di questo grafo si basa su un algoritmo greedy per selezionare un insieme di "landmark" (un $\varepsilon$-net), dove ogni nuovo landmark richiede una query di intervallo a raggio fisso per identificare tutti i punti dati entro la distanza $\varepsilon$. Per dataset grandi o ad alta dimensionalità, questo passaggio ripetuto di query di intervallo diventa un collo di bottiglia computazionale. Le implementazioni naive scalano male sia con il numero di osservazioni che con la dimensione ambiente, soffrendo della "maledizione della dimensionalità" dove i metodi di indicizzazione geometrica perdono efficienza di pruning.

Questo lavoro affronta la necessità di implementazioni efficienti delle query di intervallo in Ball Mapper. Investiga due strategie di accelerazione: strutture dati spaziali gerarchiche (Ball Trees) e librerie ottimizzate per la ricerca di similarità (FAISS). Inoltre, affronta la sfida specifica delle query di intervallo approssimate. A differenza dei problemi di k-nearest neighbor dove trovare un punto vicino è sufficiente, Ball Mapper richiede tutti i punti entro un raggio. Il documento cerca di capire come gli errori di approssimazione (punti mancanti o inclusione di falsi positivi) influenzino l'insieme di landmark risultante, il raggio di copertura e la topologia del grafo.

Metodologia

1. Tecniche di Accelerazione

Gli autori valutano due approcci primari per accelerare il passaggio della query di intervallo:

• Ball Trees: Strutture dati gerarchiche che partizionano ricorsivamente il dataset in sottoinsiemi limitati. Utilizzano la disuguaglianza triangolare per scartare (pruning) i sottoalberi che non possono intersecare una sfera di query. Questo metodo è metricamente agnostico, ma la sua efficienza dipende fortemente dalla geometria dei dati.
• FAISS (Facebook AI Similarity Search): Una libreria ottimizzata per la ricerca di similarità di vettori densi.
  • Accelerazione Esatta: Utilizzando indici flat (ad es., IndexFlatL2) che sfruttano la vettorizzazione SIMD, routine BLAS e il multithreading per accelerare i calcoli di distanza senza alterare la complessità algoritmica o l'insieme dei punti restituiti (fino alla precisione in virgola mobile).
  • Accelerazione Approssimata: Utilizzando indici non esaustivi (ad es., IndexIVFFlat, IndexHNSWFlat) o indici compressi (ad es., IndexPQ, IndexSQ). Questi metodi riducono il tempo di esecuzione o la memoria esaminando solo un sottoinsieme di dati o utilizzando rappresentazioni compresse, alterando potenzialmente l'insieme dei punti restituiti.

2. Framework Teorico per l'Approssimazione

Il documento distingue tra query di intervallo esatte e approssimate formulando modelli di errore deterministici:

• Modello di Errore Additivo: Un oracolo è $\delta$-accurato se l'insieme di intervallo approssimato $\tilde{R}_\varepsilon(q)$ soddisfa $R_{\varepsilon-\delta}(q) \subseteq \tilde{R}_\varepsilon(q) \subseteq R_{\varepsilon+\delta}(q)$.
• Modello di Errore Moltiplicativo: Una distanza approssimata $\tilde{d}$ ha un errore relativo $\eta$ se $(1-\eta)d \le \tilde{d} \le (1+\eta)d$.
• Approssimazione Conservativa: Un oracolo è conservativo se $\tilde{R}_\varepsilon(q) \subseteq R_\varepsilon(q)$, il che significa che può mancare alcuni punti veri (falsi negativi) ma non include mai punti al di fuori della vera sfera (nessun falso positivo).

Gli autori dimostrano che sotto questi modelli di errore:

• L'insieme di landmark risultante $L$ rimane una $(\varepsilon+\delta)$-copertura ed è $(\varepsilon-\delta)$-separato.
• Il nervo approssimato (e quindi il grafo) si colloca tra i nervi esatti calcolati alle scale $\varepsilon-\delta$ e $\varepsilon+\delta$.
• Le approssimazioni conservative garantiscono che le sfere $\varepsilon$-esatte dei landmark calcolati coprano ancora il dataset, sebbene i landmark possano non essere strettamente $\varepsilon$-separati.

3. Valutazione Empirica

Gli esperimenti sono stati condotti su dataset sintetici con geometrie variabili:

• Gaussiana Isotropica: Dati ad alta dimensionalità non strutturati.
• Miscela Gaussiana (Gaussian Mixture): Dati clusterizzati.
• Curva 1D Rumorosa: Dati strutturati a bassa dimensionalità intrinseca.

Lo studio ha confrontato Ball Tree, FAISS (flat, IVF, HNSW) e il baseline pyBallMapper in termini di runtime, uso della memoria e comportamento di scaling. Crucialmente, gli esperimenti di approssimazione si sono concentrati sulla stabilità strutturale (recall/precisione dell'intervallo, recall/precisione degli archi, conteggio dei landmark e separazione) piuttosto che solo sulla velocità.

Risultati Chiave

Prestazioni Computazionali

• Runtime: FAISS (indice flat) ha dimostrato le migliori prestazioni di runtime, mantenendo tempi di esecuzione bassi anche all'aumentare della dimensione del dataset ($n$) e della dimensione ($D$). Ha ottenuto accelerazioni di oltre due ordini di grandezza rispetto a pyBallMapper in contesti ad alta dimensionalità. I Ball Trees hanno performato bene a basse dimensioni, ma sono degradati rapidamente all'aumentare di $D$.
• Scaling: La regressione log-log ha mostrato pyBallMapper che si avvicina a uno scaling quadratico ($p \approx 2$) con la dimensione, mentre FAISS e Ball Trees hanno mantenuto esponenti di scaling significativamente più bassi ($p < 1.7$).
• Memoria: FAISS ha presentato l'impronta di memoria più elevata a causa delle rappresentazioni vettoriali dense e delle strutture di indicizzazione. Ball Trees e pyBallMapper sono stati più efficienti in termini di memoria.

Effetti Strutturali dell'Approssimazione

• Comportamento Conservativo: In tutte le configurazioni FAISS testate (IVF e HNSW), le query di intervallo approssimate sono state conservative. Hanno prodotto zero falsi positivi (la precisione era 1.0) ma hanno introdotto falsi negativi (la recall era < 1.0).
• Impatto sulla Struttura del Grafo:
  • Perdita di Archi: L'effetto strutturale principale è stata la rimozione di archi (sparsificazione) dovuta ai membri dell'intervallo mancanti.
  • Selezione dei Landmark: Negli esperimenti end-to-end, i falsi negativi hanno causato il mancato rilevamento di alcuni punti, portando alla selezione di ulteriori landmark vicini. Ciò ha ridotto la separazione minima dei landmark al di sotto di $\varepsilon$, sebbene il raggio di copertura sia rimasto vicino al valore target $\varepsilon$.
• Dipendenza dalla Geometria: La sensibilità all'approssimazione variava significativamente in base alla geometria del dataset:
  • Gaussiana Isotropica: La più sensibile. Impostazioni di approssimazione moderate hanno prodotto una significativa perdita di archi (ad es., IVF con $nprobe=32$ ha recuperato solo circa il 31% degli archi).
  • Miscela Gaussiana: Più stabile grazie alla struttura clusterizzata, che fornisce molteplici testimoni per le intersezioni delle sfere.
  • Curva Rumorosa: La più stabile. La struttura a bassa dimensionalità ha permesso agli indici approssimati di recuperare quasi il 100% delle membership e degli archi anche con parametri aggressivi.

Significato e Rivendicazioni

Il documento sostiene di fornire un framework rigoroso per l'integrazione della ricerca approssimata nella analisi topologica dei dati senza compromettere le garanzie teoriche della costruzione di Ball Mapper. I suoi principali contributi sono:

1. Implementazione: Sviluppa e confronta le implementazioni Ball Tree e FAISS per la costruzione greedy di Ball Mapper, dimostrando che FAISS offre una scalabilità superiore per dataset euclidei grandi e ad alta dimensionalità.
2. Limiti Teorici: Stabilisce limiti deterministici mostrando che le query di intervallo approssimate (sotto modelli di errore additivo o moltiplicativo) producono set di landmark e grafi che sono limitati da costruzioni esatte a scale leggermente perturbate.
3. Caratterizzazione Empirica: Dimostra che gli indici approssimati standard di FAISS si comportano in modo conservativo (nessun falso positivo), rendendoli sicuri per la costruzione di Ball Mapper, a patto che l'utente accetti la potenziale sparsificazione degli archi e le variazioni minori nella separazione dei landmark.
4. Sensibilità alla Geometria: Evidenzia che la stabilità di Ball Mapper approssimato non è uniforme; dipende fortemente dalla geometria intrinseca dei dati, con strutture clusterizzate e a bassa dimensionalità che sono più robuste agli errori di approssimazione rispetto a dati isotropici ad alta dimensionalità.

Gli autori concludono che, sebbene la definizione di Ball Mapper non debba cambiare, la sua implementazione computazionale può essere significativamente migliorata usando FAISS. Tuttavia, gli utenti devono essere consapevoli che l'approssimazione introduce un compromesso: una riduzione del costo computazionale in cambio di una potenziale perdita di connettività del grafo e una riduzione della separazione dei landmark, la cui gravità è dettata dalla struttura geometrica dei dati.