📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

Questo articolo implementa la classificazione k-nearest neighbors utilizzando le distanze Gromov--Wasserstein e fused Gromov--Wasserstein per confrontare rispettivamente grafi e grafi con attributi nodali, e dimostra la coerenza universale di tali classificatori mostrando al contempo le loro forti prestazioni empiriche su molteplici dataset.

Autori originali: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Pubblicato 2026-06-10

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover smistare una pila enorme di oggetti diversi. Alcuni sono forme semplici, altri sono reti complesse come mappe della metropolitana o cerchie sociali. Il tuo obiettivo è capire a quale categoria appartiene un nuovo oggetto, non ancora visto, guardando gli oggetti che già conosci. Questo è il compito di un classificatore $k$ -Nearest Neighbors ( $k$ -NN).

Pensa al $k$ -NN come a un "concorso di popolarità" tra i tuoi vicini. Se lasci cadere un nuovo oggetto in una stanza di oggetti noti, guardi i suoi $k$ vicini più prossimi. Se la maggior parte di quei vicini è composta da "gatti", ipotizzi che anche il nuovo oggetto sia un gatto.

Il problema è: come si misura la "vicinanza" quando gli oggetti sono reti complesse (grafi) prive di una dimensione o di una forma standard? Non puoi semplicemente misurare la distanza tra due punti su una mappa.

Questo articolo introduce un nuovo e intelligente modo per misurare questa distanza utilizzando qualcosa chiamato Gromov–Wasserstein (GW) e Fused Gromov–Wasserstein (fGW). Ecco la suddivisione in termini semplici:

1. Il Problema: Confrontare Mele con Arance (e Arance con Aerei)

Di solito, per confrontare due cose, queste devono avere la stessa dimensione. Se vuoi confrontare due grafi (reti di punti e linee), i metodi tradizionali spesso li costringono ad avere la stessa dimensione o li trasformano in un singolo elenco di numeri (un "embedding"). Questo è come cercare di confrontare un piccolo albero genealogico con un enorme organigramma aziendale schiacciandoli entrambi in una scatolina minuscola. Si perde informazione.

2. La Soluzione: Il Righello "Mutante"

Gli autori utilizzano uno strumento matematico chiamato distanza di Gromov–Wasserstein.

L'Analogia: Immagina di avere due città diverse. Una è una griglia (come Manhattan) e l'altra è una rete di strade tortuose (come San Francisco). Appaiono totalmente diverse.
La Magia del GW: Inve che confrontare le strade direttamente, il GW chiede: "Se potessi magicamente riorganizzare le persone nella Città A per farle corrispondere alla densità di popolazione della Città B, quanto cambierebbe la 'distanza di relazione' tra i vicini?"
Non gli importa se le città hanno 100 persone o 1.000 persone. Gli interessa solo il modello delle relazioni. Se la Città A ha un "hub" con molte connessioni e la Città B ha un "hub" simile, il GW dice: "Queste due città sono strutturalmente simili", anche se appaiono diverse su una mappa.

3. Aggiungere "Caratteristiche": La Versione Fusa

A volte, i punti nella tua rete hanno informazioni extra. Per esempio, in un grafo molecolare, ogni atomo ha un tipo specifico (Carbonio, Ossigeno). In un grafo sociale, ogni persona ha una qualifica professionale.

L'Analogia: Immagina di confrontare di nuovo due città. Il GW osserva i modelli stradali. Ma se volessi anche confrontare i tipi di edifici?
La Magia del fGW: La distanza Fused Gromov–Wasserstein (fGW) fa entrambe le cose contemporaneamente. Controlla se i modelli stradali corrispondono e se gli edifici in punti simili sono dello stesso tipo. È come un righello che misura sia la forma della città che il colore delle case.

4. La Grande Rivendicazione: "Funziona Sempre" (Consistenza Universale)

Gli autori non hanno solo costruito un nuovo righello; hanno dimostrato matematicamente che usare questo righello con il metodo $k$ -NN funziona sempre nel lungo periodo.

La Garanzia: Hanno dimostrato che se continui ad aggiungere sempre più dati di addestramento (più esempi di grafi), il tuo classificatore $k$ -NN usando queste nuove distanze diventerà eventualmente tanto accurato quanto teoricamente possibile.
Il "Trucco": Questa prova è valida per grafi di qualsiasi dimensione, purché si seguano regole specifiche su come scegliere il proprio "numero di vicini" ( $k$ ) man mano che i dati aumentano. Hanno dimostrato che lo spazio di tutti i possibili grafi si comporta abbastanza bene da permettere a questa matematica di reggere.

5. L'Esperimento: Aiuta davvero?

Gli autori hanno testato il loro metodo su dati del mondo reale:

Molecole: Smistare sostanze chimiche in base alla loro struttura e ai tipi di atomi.
Reti Sociali: Classificare reti di collaborazione cinematografica (ad esempio, film d' "Azione" rispetto a film di "Romantici").
Dati Sintetici: Reti create artificialmente per testare i limiti.

I Risultati:

Il loro metodo (GW- $k$ -NN e fGW- $k$ -NN) ha funzionato molto bene, superando spesso o eguagliando altri metodi popolari come le Graph Neural Networks (GCN) e i complessi kernel grafici.
Risultato Chiave: Per le molecole con dati extra (tipi di atomi), la versione "Fusa" (fGW) è stata la vincitrice indiscussa. Ha dimostrato che guardare sia la struttura che le caratteristiche insieme è meglio che guardare solo una delle due cose.
Efficienza: Sebbene la matematica sia pesante, il metodo è stato sorprendentemente veloce ed efficiente rispetto ad altri metodi complessi, specialmente per i grafi non attribuiti.

Riassunto

L'articolo afferma: "Abbiamo trovato un modo per misurare quanto due reti complesse siano simili, indipendentemente dalla loro dimensione o forma. Abbiamo dimostrato che se usi questa misurazione per smistare nuove reti in base ai loro vicini più prossimi, il metodo è matematicamente garantito per migliorare sempre più man mano che lo nutri con più dati. I nostri test mostrano che funziona molto bene su problemi del mondo reale come l'identificazione di molecole e generi cinematografici."

Cosa NON hanno affermato:

Non hanno affermato che questo funzioni per ogni possibile tipo di dato (solo per grafi e oggetti strutturati).
Non hanno affermato che sia il metodo più veloce al mondo (hanno notato che può essere computazionalmente pesante, sebbene abbiano dimostrato che è competitivo).
Non lo hanno applicato alla diagnosi medica o ad usi clinici; si sono limitati strettamente ai compiti di classificazione di grafi.

Sintesi Tecnica: $k$ -Nearest Neighbors nello Spazio di Gromov–Wasserstein

Definizione del Problema
Il documento affronta la sfida della classificazione di dati con struttura a grafo, inclusi grafi non attribuiti e grafi con attributi ai nodi, all'interno di un rigoroso framework di apprendimento metrico. I classificatori tradizionali $k$ -nearest neighbors ( $k$ -NN) si basano su funzioni di distanza definite in spazi euclidei o spazi metrici standard. Tuttavia, i grafi possiedono spesso strutture complesse dove il confronto diretto è difficile, in particolare quando i grafi hanno numeri diversi di nodi o mancano di un embedding canonico. Sebbene la distanza di Gromov–Wasserstein (GW) fornisca un framework per confrontare spazi metrici-misura (mm-spaces) e la distanza fused Gromov–Wasserstein (fGW) estenda questo approccio includendo le caratteristiche dei nodi, le proprietà teoriche dei classificatori $k$ -NN operanti in questi specifici spazi metrici erano precedentemente ignote. Nello specifico, non era chiaro se il $k$ -NN fosse universalmente consistente (ovvero se converga al rischio di Bayes ottimale) quando lo spazio sottostante è lo spazio dei grafi equipaggiato con le distanze GW o fGW.

Metodologia
Gli autori implementano la classificazione $k$ -NN utilizzando le distanze GW e fGW e ne investigano la consistenza teorica. Il nucleo della loro metodologia consiste nell'instaurare le proprietà topologiche degli spazi metrici in questione per soddisfare le condizioni richieste per la consistenza universale.

Definizioni degli Spazi Metrici:
- Spazio GW ( $\mathbb{X}$ ): Lo spazio delle classi di equivalenza di mm-spaces con supporto finito e misura di probabilità uniforme, equipaggiato con la distanza Gromov–Wasserstein $p=2$ . Questo modella grafi non attribuiti.
- Spazio fGW ( $\mathbb{Y}^f$ ): Lo spazio delle classi di isomorfismo debole di oggetti strutturati (mm-spaces con mappe di caratteristiche in $\mathbb{R}^d$ ), equipaggiato con la distanza fused Gromov–Wasserstein ( $p=1, q=2$ ). Questo modella grafi con attributi ai nodi.
Framework Teorico:
Gli autori si affidano a risultati stabiliti nella teoria dell'apprendimento (specificamente Chaudhuri e Dasgupta [9]) che affermano che il $k$ -NN è universalmente consistente su uno spazio metrico separabile se lo spazio possiede una dimensione metrica $\sigma$ -finita (una proprietà relativa alla condizione di differenziazione di Lebesgue). Per dimostrare ciò per gli spazi GW e fGW, gli autori:
- Costruiscono modelli a dimensione finita per spazi a $n$ punti all'interno di questi framework.
- Dimostrano l'esistenza di mappe bi-Lipschitz tra lo spazio dei grafi a $n$ punti e specifici spazi quoziente di matrici euclidee (per GW) e spazi prodotto di matrici e vettori di caratteristiche (per fGW).
- Dimostrano che questi spazi quoziente possiedono una dimensione Assouad-Nagata finita.
- Utilizzano il Lemma 2.4 per mostrare che l'esistenza di mappe bi-Lipschitz verso spazi con dimensione finita implica che gli spazi target ( $\mathbb{X}$ e $\mathbb{Y}^f$ ) possiedano una dimensione metrica $\sigma$ -finita.
Esperimenti Numerici:
Gli autori valutano le prestazioni dei classificatori GW- $k_n$ -NN e fGW- $k_n$ -NN su sette dataset di benchmark:
- Grafi con attributi: BZR, COX-2 e PROTEINS (dataset molecolari).
- Grafi non attribuiti: IMDb-B, IMDb-M (social network) e due dataset sintetici (ERSBM1, ERSBM2).
- Baseline: Confronti con Graph Convolutional Networks (GCN), vari metodi di kernel per grafi (Shortest Path, Graphlet, HOPPER, Propagation) e SVM utilizzando kernel GW/fGW.

Contributi Chiave
Il contributo primario di questo lavoro è la dimostrazione della consistenza universale per i classificatori $k$ -NN nel contesto della classificazione di grafi utilizzando le distanze GW e fGW.

Risultati Teorici:
- Teorema 1.8: Dimostra che il classificatore GW- $k_n$ -NN è universalmente debolmente consistente sullo spazio dei grafi $(\mathbb{X}, GW_2)$ sotto le condizioni $k \to \infty$ e $k/n \to 0$ . È universalmente fortemente consistente se $k/\log(n) \to \infty$ .
- Teorema 1.9: Dimostra gli stessi risultati di consistenza per il classificatore fGW- $k_n$ -NN sullo spazio dei grafi con attributi ai nodi $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- Questi risultati sono stabiliti dimostrando che entrambi gli spazi sono separabili e possiedono una dimensione metrica $\sigma$ -finita, una proprietà derivata tramite embedding bi-Lipschitz in spazi quoziente di spazi euclidei.
Risultati Empirici:
- Sui dataset di grafi con attributi (BZR, COX-2, PROTEINS), fGW- $k_n$ -NN ha costantemente raggiunto l'accuratezza media più elevata, superando le GCN e altri metodi basati su kernel. Anche GW- $k_n$ -NN ha ottenuto prestazioni competitive.
- Sui dataset non attribuiti, GW- $k_n$ -NN ha raggiunto un'accuratezza perfetta (100%) sul dataset sintetico ERSBM2 e una forte performance su IMDb-B, spesso superando i kernel per grafi e le GCN.
- Gli autori osservano che, sebbene i metodi GW/fGW siano interpretabili (le piccole distanze implicano somiglianza strutturale), possono essere computazionalmente intensivi rispetto ad alcuni metodi basati su kernel, pur offrendo miglioramenti di efficienza rispetto alle SVM che utilizzano kernel GW in certi contesti.

Significato e Rivendicazioni
Il documento sostiene di aver stabilito una base teorica per l'uso di classificatori metrici come il $k$ -NN all'interno del framework di Gromov–Wasserstein. Dimostrando la consistenza universale, gli autori sostengono che questi metodi non sono meramente euristici ma sono teoricamente solidi per compiti di classificazione di grafi.

La significatività risiede nel colmare il divario tra la teoria del trasporto ottimo e la teoria dell'apprendimento statistico per dati strutturati. Gli autori sottolineano che il loro approccio offre un "framework altamente interpretabile" in cui la distanza tra i grafi misura direttamente la somiglianza strutturale (l'isomorfismo implica distanza zero). Essi dichiarano esplicitamente che, a loro conoscenza, questa è la prima applicazione di GW- $k$ -NN alla classificazione di grafi e la prima prova teorica della sua consistenza.

Il documento rimane modesto riguardo a possibili generalizzazioni future. Riconosce che, sebbene la consistenza sia provata per parametri specifici ( $p=2$ per GW, $p=1, q=2$ per fGW), rimane un problema aperto se tali risultati valggano per altre scelte di parametri o per l'impostazione più generale di Z-Gromov–Wasserstein. Gli autori ipotizzano che, similmente allo spazio di Wasserstein, la consistenza universale potrebbe non valere in piena generalità senza restrizioni specifiche sugli spazi di interesse.