🤖 machine learning

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

Questo articolo introduce l'HAAR multi-vista gerarchico (HMH), un framework scalabile di apprendimento spettrale su grafi che mitiga l'eccesso di lisciamento e l'eccesso di compressione nei grafi eterofili costruendo una gerarchia soft con basi di Haar ortonormali e filtri spettrali apprendibili, superando di conseguenza le basi di riferimento all'avanguardia sia nelle attività di classificazione dei nodi che in quelle di classificazione dei grafi.

Autori originali: Md Sazzad Hossen, Avimanyu Sahoo

Pubblicato 2026-05-13

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Md Sazzad Hossen, Avimanyu Sahoo

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 cercare di comprendere una città massiccia e caotica camminando attraverso i suoi quartieri. Nel mondo della scienza dei dati, questa città è un grafo (una rete di punti connessi), e le persone che vi abitano sono i nodi.

Di solito, quando insegniamo ai computer a comprendere queste città, ci imbattiamo in tre grandi problemi:

Il problema del "Vicino Ricco" (Dominio degli Hub): Se un quartiere ha una celebrità super popolare (un "hub" con migliaia di amici), la sua opinione soffoca le voci silenziose dei quartieri più piccoli e meno connessi. Il computer sente solo la celebrità.
Il problema della "Foto Sfocata" (Sovra-lisciatura): Se continui a chiedere ai vicini cosa pensano, e loro continuano a chiedere ai loro vicini, alla fine tutti iniziano a suonare esattamente uguali. I dettagli unici vengono lavati via e l'immagine diventa una macchia grigia sfocata.
Il problema del "Gioco del Telefono" (Sovra-schiacciamento): Se provi a inviare un messaggio da un lato della città all'altro, il messaggio viene schiacciato così tanto mentre passa attraverso strade affollate da arrivare come un incomprensibile nonsense.

Il documento introduce una nuova soluzione chiamata HMH (Gerarchico Multi-vista HAAR). Pensa all'HMH non come a una singola persona che cammina per le strade, ma come a un sistema intelligente di pianificazione urbana a più livelli che utilizza una speciale "lente di ingrandimento".

Ecco come funziona, passo dopo passo:

1. Il Traduttore Intelligente (L'Encoder Eterofilo)

In molte città, i vicini sono simili (gli piace la stessa musica). In altre, i vicini sono opposti (uno ama il jazz, l'altro il heavy metal). Questo è chiamato eterofilia.

Vecchio modo: I computer spesso assumono che tutti siano simili e semplicemente mediano le loro opinioni. Questo fallisce quando i vicini sono opposti.
Modo HMH: Agisce come un traduttore che ascolta attentamente. Se due vicini sono simili, dà loro un "pollice in su" (peso positivo). Se sono opposti, dà loro un "pollice in giù" (peso negativo). Questo assicura che il computer impari a cogliere le differenze tanto bene quanto le somiglianze, senza confondersi per il continuo cambio di segno.

2. La Lente di Ingrandimento (Clustering Gerarchico)

Invece di cercare di analizzare ogni singola persona nella città tutta insieme, l'HMH costruisce una piramide di quartieri.

Livello 1: Raggruppa persone simili in piccoli "grumi" o cluster.
Livello 2: Tratta quei grumi come singole "super-persone" e li raggruppa in quartieri più grandi.
Livello 3: Continua ad allontanare lo zoom finché non vede l'intera città come poche grandi regioni.

È come guardare una mappa: prima vedi le case, poi i isolati, poi i quartieri, infine l'intera città. Questo aiuta il computer a gestire il problema del "Vicino Ricco" perché i piccoli quartieri silenziosi ottengono la propria voce nei cluster più piccoli prima di essere fusi nel quadro generale.

3. Il Filtro Speciale (Base di Haar)

Questo è il segreto. La maggior parte dei computer usa un "filtro globale" che cerca di lisciare l'intera città tutta insieme, causando il problema della "foto sfocata".
L'HMH usa qualcosa chiamato Base di Haar. Immagina questo come un set di torce specializzate:

Alcune torce illuminano solo una singola casa (dettagli locali).
Alcune illuminano un intero isolato (dettagli medi).
Alcune illuminano l'intera città (grandi tendenze).

Poiché queste torce sono ortogonali (non si sovrappongono o interferiscono tra loro), l'HMH può accendere la torcia dei "dettagli locali" senza sfocare accidentalmente la torcia della "grande tendenza". Mantiene nitidi i dettagli ad alta frequenza (le differenze tra i vicini) pur comprendendo il quadro generale.

4. L'Ascensore (Unpooling con Connessioni Skip)

Dopo aver analizzato la città a ogni livello di zoom, l'HMH non si ferma in cima. Usa un ascensore per riportare tutte quelle informazioni giù al livello originale della strada.

Prende le intuizioni del "quadro generale" dalla cima della piramide.
Le mescola con i "dettagli locali" dal basso.
Ogni singola persona (nodo) riceve un rapporto finale che include sia i pettegolezzi del proprio quartiere immediato sia il contesto a livello cittadino.

Perché è una grande novità?

Il documento afferma che utilizzando questo sistema "Lente di Ingrandimento + Torce Speciali + Ascensore", l'HMH risolve i tre grandi problemi:

Niente più Dominio degli Hub: I piccoli quartieri non vengono soffocati dalle celebrità perché vengono analizzati nei propri cluster prima.
Niente più Foto Sfocate: Le torce speciali mantengono nitidi i dettagli unici, anche negli strati molto profondi.
Niente più Messaggi Schiacciati: Poiché la città è organizzata in una gerarchia (come un albero), i messaggi non devono schiacciarsi attraverso strade affollate; viaggiano su e giù per l'albero, il che è molto più veloce e chiaro.

Il Risultato:
Gli autori hanno testato questo su molti diversi tipi di "città" (dataset), dalle reti sociali alle strutture molecolari. Hanno scoperto che l'HMH era più veloce (scalando quasi linearmente, il che significa che non si intasa mentre la città cresce) e più accurato dei metodi precedenti, specialmente nei luoghi in cui i vicini sono molto diversi tra loro. Ha ottenuto punteggi migliori nell'identificare a quale gruppo appartiene qualcuno (classificazione) senza perdere l'identità unica degli individui.

Riepilogo Tecnico: Reti Neurali su Grafo Gerarchiche Multi-Scala (HMH)

1. Enunciato del Problema

I grafi del mondo reale spesso esibiscono eterofilia, dove i nodi adiacenti possiedono etichette o caratteristiche diverse. Sebbene le esistenti Reti Neurali su Grafo (GNN) abbiano compiuto progressi nella gestione di tali dati, soffrono di tre patologie critiche, in particolare nei grafi sbilanciati per grado (dominati da hub):

Dominio degli Hub: Nei grafi con nodi "hub" ad alto grado, i meccanismi convenzionali di passaggio dei messaggi permettono a questi hub di dominare il processo di aggregazione. Questo sovraccarica i segnali provenienti dai nodi "raggio" a basso grado (piccoli cluster), causando la convergenza degli embedding di cluster distinti verso una rappresentazione comune indotta dall'hub, cancellando di fatto i confini decisionali.
Sovralisciamento (Oversmoothing): All'aumentare della profondità delle GNN, gli embedding dei nodi tendono a convergere verso una distribuzione stazionaria (medie delle classi), rendendo le caratteristiche indistinguibili. Ciò è aggravato da filtri polinomiali subottimali che mescolano segnali provenienti da regioni semanticamente non correlate.
Sovraschermatura (Oversquashing): Le informazioni provenienti da nodi distanti decadono esponenzialmente con la distanza nel grafo, creando colli di bottiglia che impediscono il flusso di informazioni a lungo raggio.

Gli approcci spettrali esistenti (ad es. ChebNet, BernNet) spesso si basano su basi polinomiali globali (Chebyshev, Jacobi) che assumono ortogonalità continua. Tuttavia, i grafi reali possiedono misure spettrali discrete, portando a dispersione di frequenza, ridotta espressività e incapacità di adattarsi all'eterofilia strutturale locale. Al contrario, gli approcci spaziali (ad es. Signed Message Passing) soffrono spesso di cancellazione del segno attraverso i livelli o richiedono costosi passaggi di aggregazione globale che mescolano segnali tra regioni diverse.

2. Metodologia: HAAR Gerarchico Multi-vista (HMH)

Gli autori propongono HMH, un framework di apprendimento su grafo spettrale progettato per scalare in tempo quasi lineare mitigando le suddette patologie. Il framework opera attraverso un'analisi gerarchica e multi-risoluzione dei segnali del grafo.

2.1. Encoder Adattivo per Eterofilia

Il processo inizia con un encoder consapevole dell'eterofilia che apprende affinità firmate consapevoli delle caratteristiche e della struttura senza richiedere etichette dei nodi.

Similarità Adattiva: L'encoder calcola un punteggio di similarità combinando l'affinità delle caratteristiche (pesi apprendibili) e la similarità strutturale (basata su vicini condivisi a due salti).
Matrice di Adiacenza Firmata: Questi punteggi sono trasformati in una matrice di adiacenza continua e firmata ( $A_{adp}$ ). Un'alta similarità produce pesi positivi (comportamento passa-basso), mentre una bassa similarità produce pesi negativi (comportamento passa-alto).
Stabilità del Segno: A differenza del Signed Message Passing (SMP) fisso che soffre di inversione periodica del segno ( $S^2 = I$ ), l'adiacenza adattiva di HMH viene ricalcolata a ogni livello basandosi sugli embedding correnti, prevenendo oscillazioni rigide e cancellazione del segno.

2.2. Coarsening Gerarchico del Grafo

Utilizzando i punteggi dei nodi dell'encoder, HMH costruisce una gerarchia di grafo soft tramite un processo di clustering ricorsivo:

Clustering: I nodi sono raggruppati in cluster (supernodi) utilizzando $k$ -means++ sugli embedding dell'encoder.
Assegnazione Soft: Una matrice di assegnazione probabilistica ( $A_s$ ) mappa i nodi fini ai cluster grezzi, controllata da un parametro di temperatura.
Aggregazione: Le caratteristiche e gli spigoli vengono aggregati per formare il livello successivo della gerarchia. Questo processo si ripete fino al raggiungimento di una soglia, creando una struttura ad albero.

2.3. Basi Haar Consapevoli della Classe e Filtraggio Spettrale

A ogni livello gerarchico, HMH costruisce una base di Haar ortonormale sparsa ( $U^{(\ell)}$ ) adattata alla specifica struttura del cluster di quel livello.

Costruzione della Base: La base è composta da un vettore di scala globale (che cattura le tendenze a bassa frequenza) e da wavelet. Le wavelet sono divise in:
- Wavelet inter-cluster: Che catturano i contrasti tra diversi supernodi.
- Wavelet intra-cluster: Che catturano le variazioni localizzate all'interno di un cluster.
Filtraggio Diagonale: I segnali del grafo sono proiettati su questa base. Matrici di guadagno diagonali apprendibili ( $\Lambda^{(\ell)}$ ) vengono applicate per amplificare selettivamente i canali ad alta frequenza (eterofili) e attenuare i segnali a bassa frequenza (omofili) o dominati dall'hub.
Località: Poiché la base di Haar è strettamente localizzata (il supporto è confinato in piccoli vicinati), previene la dispersione di informazioni tra regioni del grafo non correlate, affrontando direttamente il dominio degli hub.

2.4. Unpooling con Connessioni Skip

Per recuperare la risoluzione originale, HMH impiega un unpooling con connessioni skip. Gli output da tutti i livelli gerarchici vengono aggregati nuovamente sui nodi originali. Questo garantisce che ogni nodo mantenga le sue caratteristiche di base arricchite con un contesto multi-scala da tutti i livelli della gerarchia, aggirando efficacemente il decadimento esponenziale associato alla sovraschermatura.

3. Contributi Chiave

Il documento rivendica quattro contributi principali:

Affinità Firmata Adattiva Senza Etichette: Un meccanismo che assegna pesi positivi/negativi basandosi sulla similarità appresa di caratteristiche/struttura, prevenendo la patologia di cancellazione del segno riscontrata nei modelli SMP fissi.
Costruzione di Base Ortonormale in Tempo Quasi Lineare: Il primo framework a costruire una base spettrale ortonormale sparsa e multi-scala (Haar) in tempo quasi lineare, evitando il costo $O(n^3)$ della decomposizione spettrale e il costo $O(n^2)$ delle basi polinomiali dense.
Mitigazione Teorica delle Patologie: Prove rigorose ed evidenze empiriche che dimostrano come HMH superi il dominio degli hub, il sovralisciamento e la sovraschermatura. Nello specifico, la base localizzata confina l'energia nei vicinati a due salti, e la struttura gerarchica accorcia i percorsi di comunicazione in modo logaritmico.
Prestazioni allo Stato dell'Arte: Dimostrazione di una precisione superiore sia nelle attività di classificazione dei nodi che in quelle di classificazione dei grafi su dataset omofili ed eterofili, inclusi benchmark su larga scala come OGBN-ArXiv.

4. Risultati Sperimentali

Gli autori hanno valutato HMH su una serie diversificata di dataset:

Classificazione dei Nodi: HMH è stato testato su benchmark omofili standard (Cora, Citeseer) e su dataset eterofili impegnativi (Chameleon, Squirrel, Texas, Roman-empire, Amazon-ratings, ecc.).
- Prestazioni: HMH ha ottenuto un miglioramento fino al 3% nelle attività di classificazione dei nodi rispetto alle basi spettrali allo stato dell'arte (ad es. ChebNetII, BernNet, UniFilter).
- Analisi degli Hub: Nelle valutazioni stratificate per grado (Raggi vs Hub), HMH ha ridotto significativamente il divario di prestazioni. Ad esempio, sul dataset Penn94, ha migliorato l'accuratezza dei "Raggi" (basso grado) del +10.8% rispetto alle basi, che tipicamente soffrono di dominio degli hub.
- Stabilità della Profondità: A differenza delle GCN che degradano rapidamente con la profondità (sovralisciamento), HMH è rimasto stabile e ha persino migliorato le prestazioni con la profondità (raggiungendo il picco a 32–64 livelli su Penn94).
- Sovraschermatura: Sul benchmark Tree-NeighborsMatch, HMH ha mantenuto un'accuratezza >98% alla profondità 10, mentre le basi sono scese a un indovinello casuale (50%) alla profondità 8.
Classificazione dei Grafi: Valutato sui dataset TU (MUTAG, PROTEINS, ecc.).
- Prestazioni: HMH ha ottenuto un miglioramento di 7 punti percentuali sui dataset di classificazione dei grafi, raggiungendo notevolmente il 94.5% su MUTAG.
- Scalabilità: Il framework ha dimostrato una scalabilità quasi lineare. Sul dataset REDDIT-12K, HMH è stato 8.1 volte più veloce per epoca rispetto alle basi basate sulla decomposizione spettrale e ha utilizzato 3.9 volte meno memoria.

5. Significato e Rivendicazioni

Il documento posiziona HMH come una soluzione alle limitazioni fondamentali delle attuali GNN spettrali e spaziali in contesti eterofili.

Significato Teorico: Gli autori rivendicano che, utilizzando una base di Haar ortonormale e localizzata, confinano rigorosamente l'energia del segnale, prevenendo il fenomeno dell'"aliasing degli hub" in cui piccoli cluster vengono sommersi da nodi ad alto grado. Si afferma che la struttura gerarchica garantisce teoricamente l'assenza di sovraschermatura riducendo i percorsi effettivi in modo logaritmico.
Significato Pratico: Il framework offre un'alternativa scalabile ai metodi spettrali costosi, rendendo fattibile l'apprendimento eterofilo ad alte prestazioni per grafi su larga scala (ad es. OGBN-ArXiv con ~170k nodi).
Modestia: Gli autori riconoscono le limitazioni attuali, notando che la formulazione assume grafi statici e che l'estensione del metodo a grafi dinamici o multi-relazionali rimane una direzione per lavori futuri. Sottolineano che i loro miglioramenti sono ottenuti mantenendo la scalabilità lineare, un fattore cruciale per il deployment nel mondo reale.