Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Sintesi Tecnica: La Riduzione della Dimensionalità incontra la Scienza delle Reti

Enunciato del Problema

Sebbene UMAP sia uno strumento dominante per la visualizzazione di dati ad alta dimensionalità, i flussi di lavoro analitici standard trattano tipicamente il grafico a dispersione 2D risultante come l'unico artefatto di interesse. Questo approccio scarta il ricco grafo k-vicini più prossimi (kNN) intermedio che UMAP costruisce internamente prima della proiezione. Gli autori sostengono che questo grafo codifica la geometria locale e la connettività del manifold dei dati nello spazio originale ad alta dimensionalità in modo più fedele rispetto al layout 2D, che introduce inevitabilmente distorsioni. Ignorando questo grafo, gli analisti perdono opportunità di compiti di sensemaking — come l'identificazione di punti rappresentativi, l'analisi delle gerarchie di densità e il rilevamento della coesione locale — che vengono oscurati nella proiezione 2D.

Metodologia

Il paper propone di elevare il grafo kNN interno di UMAP a "risorsa analitica di prima classe", applicando direttamente algoritmi standard della scienza delle reti al medesimo, anziché all'embedding 2D. La metodologia sfrutta le specifiche proprietà strutturali del grafo: grado uscente $k$ fisso, grado entrante variabile e pesi degli archi adattivi alla densità. Vengono applicati tre algoritmi specifici:

1. PageRank per la Selezione di Rappresentanti:

   • Meccanismo: Invece di selezionare gli esemplari basandosi su centroidi geometrici nello spazio 2D distorto (che possono cadere in regioni non rappresentative), gli autori applicano il PageRank al grafo kNN.
   • Logica: Il punteggio di un nodo viene amplificato trasitivamente; un punto ottiene un ranking elevato non solo perché molti nodi puntano a esso (alto grado entrante), ma perché i nodi che puntano a esso sono essi stessi altamente classificati. Ciò identifica punti globalmente rappresentativi che fungono da "autorità" nel manifold.
   • Implementazione: I pesi degli archi sono derivati dalle intensità di appartenenza adattive alla densità di UMAP.

2. Decomposizione k-Core per la Gerarchia di Densità:

   • Meccanismo: Gli autori applicano la decomposizione k-core al grafo per distinguere le regioni dense del nucleo (core) dalle periferie sparse.
   • Logica: A differenza della decomposizione standard basata sul grado, che è limitata dal grado uscente fisso $k$, questo metodo si basa esclusivamente sul grado entrante. Ciò produce un punteggio di "coreness" (0, 1, 2...) che indica quanto un nodo sia profondamente inserito in sottografi progressivamente più densi e interconnessi.
   • Obiettivo: Rivelare gerarchie di sottografi graduati e sottocategorie all'interno dei cluster che le etichette di clustering discrete (ad es. da HDBSCAN) non riescono a catturare.

3. Coefficiente di Clustering per la Coesione Locale:

   • Meccanismo: Il coefficiente di clustering (CC) viene calcolato per ogni nodo per misurare la frazione dei suoi vicini che sono connessi tra loro.
   • Logica: Un alto CC indica micro-neighborhood "stretti" dove i punti si considerano reciprocamente vicini più prossimi.
   • Obiettivo: Rilevare micro-cluster semanticamente coerenti (ad es. stili di scrittura a mano specifici) che possono apparire come una massa monolitica in una proiezione 2D.

Contributi Chiave

Il paper apporta due contributi primari:

1. Spostamento Concettuale: Colma il divario tra riduzione della dimensionalità e scienza delle reti, trattando il grafo kNN scartato da UMAP come una risorsa primaria. Ciò consente un sensemaking che è complementare ai grafici a dispersione 2D, affrontando specificamente la rappresentatività, la struttura della densità e la coesione locale.
2. Validazione Empirica: Attraverso valutazioni quantitative e qualitative su MNIST e Fashion MNIST, gli autori dimostrano che questi metodi basati sui grafi sono competitivi o superiori ai metodi creati ad hoc:
   • PageRank vs. k-medoids: I punti selezionati tramite PageRank raggiungono una bilanciatura delle classi superiore (minore divergenza di Jensen-Shannon) rispetto a k-medoids, che tende a sovra-selezionare da classi ad alta varianza. Sebbene k-medoids superi leggermente PageRank in rappresentatività con budget molto piccoli, PageRank recupera rapidamente e rimane competitivo nell'accuratezza della classificazione SVM a valle. Fondamentalmente, PageRank richiede un unico calcolo di ranking globale, mentre k-medoids deve essere rieseguito per ogni dimensione di budget.
   • k-Core vs. HDBSCAN: Mentre HDBSCAN assegna etichette di cluster discrete, la decomposizione k-core rivela una gerarchia graduata di centralità all'interno dei cluster. La correlazione tra la probabilità di appartenenza a HDBSCAN e la coreness è risultata quasi nulla, confermando che rispondono a domande diverse (appartenenza al gruppo vs. posizione all'interno del gruppo).
   • Coefficiente di Clustering: Il CC identifica micro-neighborhood distinti (ad es. stili specifici del numero "6" scritto a mano) che sono topologicamente coesi ma possono essere visivamente indistinguibili in 2D.

Risultati

• Stabilità: I ranking di PageRank sono altamente stabili attraverso un intervallo di 20x delle dimensioni del vicinato ($k=5$ a $100$), con correlazioni di rango di Spearman medie di ~0,95, indicando che i rappresentanti selezionati non sono artefatti di un valore specifico di $k$.
• Performance:
  • Rappresentatività: PageRank rivaleggia con k-medoids nella distanza coseno media rispetto ai rappresentanti più prossimi, specialmente all'aumentare del budget di selezione.
  • Bilanciatura delle Classi: PageRank supera significativamente k-medoids nel mantenere la distribuzione globale delle classi (minore JSD), particolarmente per budget $s \ge 200$.
  • Utilità a Valle: I classificatori SVM addestrati sugli esemplari selezionati tramite PageRank raggiungono un'accuratezza entro 2–3 punti percentuali di k-medoids su Fashion MNIST ed sono comparabili su MNIST.
  • Insight Strutturale: La decomposizione k-core isola con successo le sottocategorie (ad es. borse a tracolla vs. zainetti tra la classe "bag") filtrando per specifiche soglie di coreness. Alti valori di CC isolano stili di scrittura coerenti all'interno del cluster del numero "6".

Significato e Rivendicazioni

Gli autori affermano che il loro lavoro dimostra il potenziale inespresso della rappresentazione interna di UMAP. Mantenendo e analizzando il grafo kNN, gli analisti possono accedere a informazioni strutturali (centralità, gerarchia di connettività, coesione locale) che vengono perse o distorte nella proiezione 2D.

Il paper posiziona questi algoritmi di grafo non come sostituti degli strumenti esistenti, ma come metodi complementari che offrono vantaggi distinti:

• Forniscono un modo senza parametri (o stabile) per selezionare i rappresentanti senza ottimizzare un obiettivo di distanza.
• Offrono una gerarchia continua di densità (tramite k-core) piuttosto che assegnazioni di cluster discrete.
• Sono computazionalmente efficienti, eseguendosi in meno di 1 secondo su 60.000 punti riutilizzando gli array dei vicini precalcolati di UMAP.

Gli autori concludono che questa prospettiva incoraggia la comunità a "guardare oltre lo scatter plot e dentro il grafo che lo ha generato", suggerendo che questo approccio si estende naturalmente ad altri metodi di riduzione della dimensionalità che costruiscono grafi kNN (ad es. TriMap, PaCMAP).