Clustering Node Attributed Networks with Graph Neural Networks and Self Learning

Sintesi Tecnica: Clustering di Reti con Attributi di Nodo tramite Graph Neural Networks e Self-Learning

Formulazione del Problema
Il paper affronta il problema del clustering di nodi in reti con attributi, dove ogni nodo possiede sia connessioni topologiche (archi) che attributi di caratteristiche. L'obiettivo è partizionare l'insieme dei nodi in sottoinsiemi disgiunti (comunità) che riflettano strutture latenti, sfruttando congiuntamente la topologia della rete e gli attributi dei nodi. Fondamentalmente, il lavoro opera in un contesto completamente non supervisionato, il che significa che non sono disponibili etichette di verità fondamentale (ground-truth) durante l'addestramento; gli unici input sono la struttura del grafo, gli attributi dei nodi e il numero target di cluster ($K$). Gli autori osservano che, sebbene il clustering congiunto sia intuitivamente superiore all'uso della sola topologia o dei soli attributi, progettare algoritmi che fondano efficacemente questi segnali — specialmente quando una delle fonti è rumorosa — non è banale.

Metodologia: DCSL-GNN
Gli autori propongono la Dynamic Context Self-Learning Graph Neural Network (DCSL-GNN), un framework che opera in round iterativi per raffinare le rappresentazioni dei nodi e le assegnazioni ai cluster. Il framework è composto da tre moduli interconnessi:

1. Generazione del Contesto Dinamico:

   • Le classiche Graph Neural Networks (GNN) spesso soffrono di "under-reaching" (profondità insufficiente per catturare centri di cluster distanti) o "over-smoothing" (perdita di distintività con troppi strati). Per mitigare questo problema, DCSL-GNN costruisce un Grafo di Contesto ($G_c$) per ogni round, che differisce dal grafo originale.
   • Archi Virtuali: Il grafo di contesto introduce "archi virtuali" che collegano i nodi ai vicini più prossimi del centro di massa del loro cluster (nello spazio delle rappresentazioni). Ciò consente alle informazioni dai centri dei cluster di propagarsi direttamente, bypassando la necessità di strati GNN profondi.
   • Random Walks: Il grafo di contesto viene generato tramite random walk pesati. In ogni step, il cammino segue un arco originale (pesato dalla similarità delle rappresentazioni dei nodi del round precedente) o salta tramite un arco virtuale a un nodo vicino a un centro di cluster.
   • Vicinanza basata sull'Importanza: Il vicinato di un nodo in $G_c$ è determinato dai conteggi di visita dei random walk che partono da quel nodo, utilizzando una soglia basata sul percentile $k$ della distribuzione delle visite. Ciò assicura che i nodi più influenti (anche se distanti nel grafo originale) diventino vicini diretti nel grafo di contesto.

2. Embedding (Encoder GNN):

   • Un encoder GCN standard elabora il grafo di contesto $G_c$ e gli attributi dei nodi per generare embedding dei nodi.
   • Pesi degli Archi: Gli archi in $G_c$ sono pesati dinamicamente. Se gli attributi dei nodi connessi sono altamente simili (verificato da una soglia del coefficiente silhouette $\beta$), il peso dell'arco è inversamente proporzionale alla distanza euclidea tra i loro attributi. Altrimenti, il peso rimane neutro (1).
   • Addestramento: I parametri della GNN sono addestrati utilizzando una funzione di triplet loss. Questa perdita minimizza la distanza tra un nodo ancora e i campioni positivi (nodi nello stesso cluster) massimizzando al contempo la distanza rispetto ai campioni negativi (nodi in cluster diversi).
   • Persistenza dei Parametri: A differenza dell'addestramento standard, i pesi della GNN appresi nel round $r$ sono inizializzati con i valori del round $r-1$, consentendo al modello di affinare la propria comprensione nel tempo senza dover ripartire da zero.

3. Ciclo di Clustering e Self-Learning:

   • Gli embedding generati vengono inviati a un algoritmo K-means standard per produrre le assegnazioni ai cluster.
   • Queste nuove assegnazioni ai cluster vengono poi utilizzate per aggiornare i centri dei cluster e i bias dei random walk per il round successivo.
   • Ciò crea un meccanismo di auto-rinforzo: migliori rappresentazioni portano a migliori cluster, che a loro volta generano migliori grafi di contesto e rappresentazioni per il round successivo.

Contributi Chiave

• Framework Innovativo: L'introduzione di DCSL-GNN, un framework completamente non supervisionato che affina iterativamente le rappresentazioni dei nodi attraverso un ciclo di self-learning.
• Grafo di Contesto Dinamico: Un meccanismo per costruire un grafo di contesto che combina la topologia originale con archi virtuali verso i centri dei cluster, affrontando efficacemente i limiti di profondità delle GNN senza richiedere strati eccessivi.
• Meccanismo di Self-Learning: Un processo iterativo in cui i risultati del clustering di un round influenzano direttamente la struttura del grafo (contesto) e i pesi degli archi del round successivo, permettendo al modello di denoisare progressivamente e allineare la topologia agli attributi.
• Robustezza al Rumore: La metodologia è progettata per sfruttare la fonte di informazione più affidabile (topologia o attributi) per correggere la fonte più rumorosa.

Risultati Sperimentali
Gli autori hanno valutato DCSL-GNN su dati sintetici (Attributed Stochastic Block Models) e su tre dataset benchmark del mondo reale (Cora, Citeseer, PubMed).

• Dati Sintetici:

  • Efficacia del Self-Learning: Molteplici round di self-learning hanno costantemente superato un singolo round lungo di addestramento (equivalente al classico clustering GNN).
  • Gestione del Rumore: Il framework ha estratto con successo informazioni dalla fonte affidabile quando l'altra era rumorosa. Ad esempio, quando l'informazione di rete era molto rumorosa ($p_I=0.2$) ma gli attributi erano puliti, le prestazioni sono migliorate nel corso dei round. Viceversa, quando gli attributi erano rumorosi ma la rete era pulita, il modello ha comunque raggiunto una buona convergenza. Tuttavia, quando entrambe le fonti erano altamente rumorose, le prestazioni sono degradate verso il caso casuale, come previsto.
  • Confronto: DCSL-GNN ha superato algoritmi basati esclusivamente sulla struttura di rete (Louvain) o esclusivamente sugli attributi (K-means) in scenari in cui nessuna delle due fonti era perfettamente informativa.

• Dataset Reali:

  • Citeseer: DCSL-GNN ha raggiunto l'NMI (Normalized Mutual Information) più alto tra tutti i metodi allo stato dell'arte confrontati.
  • Cora e PubMed: Il modello si è dimostrato competitivo ma non ha superato lo stato dell'arte (MGCCN per Cora, SEComm per PubMed).
  • Limitazione: Gli autori attribuiscono le prestazioni inferiori su Cora e PubMed in parte al disequilibrio dei cluster. Il modello ha mostrato un'alta accuratezza per i cluster dominanti ma un'accuratezza trascurabile per i cluster più piccoli, suggerendo un bias verso i gruppi più grandi nella funzione obiettivo.

Significatività e Rivendicazioni
Il paper sostiene che DCSL-GNN offra un approccio flessibile al clustering di grafi con attributi che fonde efficacemente le informazioni strutturali e di attributo senza supervisione. Gli autori sottolineano che il multi-round self-learning è una componente critica, poiché permette al modello di affinare iterativamente il "contesto" in cui i nodi vengono osservati, portando a un clustering superiore rispetto agli approcci a round singolo.

Gli autori concludono con modestia che, sebbene il metodo sia altamente efficace in scenari con cluster bilanciati o livelli di rumore misti (come dimostrato su Citeseer e sui dati sintetici), esso affronta sfide con dataset reali altamente sbilanciati. Essi affermano che il framework dimostra il potenziale dei meccanismi di self-learning per migliorare le rappresentazioni dei nodi e la qualità del clustering in assenza di dati etichettati, pur non rivendicando di essere una soluzione universale superiore a tutti i metodi esistenti per ogni caratteristica del dataset.