EDiS: un framework di sparsificazione in sottografi con archi disgiunti per le reti neurali a grafo

Abstract degli autori

L’addestramento di GNN su grafi sparsi riduce il calcolo necessario, ma decidere quali archi mantenere può essere costoso. Riutilizzare un unico grafo sparso costa poco, ma vincola l’addestramento a una topologia fissa; variarlo tra le epoche, invece, può richiedere campionamenti o ricalcoli ripetuti. Presentiamo EDiS (Edge-Disjoint Subgraph sparsification framework), che separa l’estrazione della struttura, eseguita una sola volta, dalla composizione del grafo a ogni epoca. EDiS scompone il grafo una volta sola in sottografi con archi disgiunti memorizzabili nella cache, poi li ricombina in grafi soggetti a vincoli sul numero di archi, variando epoche e rapporti di conservazione senza estrarre nuovamente la struttura. La nostra costruzione predefinita usa punteggi basati sulle caratteristiche e una successione di foreste di copertura a punteggio massimo, mentre lo stesso meccanismo di composizione supporta anche regole alternative per la selezione degli archi. Forniamo un’analisi combinatoria del campionatore usato a ogni epoca, ossia della fase di composizione che ricava un grafo di addestramento dalla scomposizione memorizzata nella cache. Mostriamo che, con il selettore predefinito basato sulle foreste di copertura, la scomposizione memorizzata preserva in modo deterministico gli archi che attraversano tagli e hanno un punteggio elevato; ricaviamo inoltre un limite condizionale, indipendente dal selettore, sulla sopravvivenza di tali archi nei grafi di addestramento ottenuti per composizione. Su 19 benchmark omofilici, eterofilici e su larga scala per la classificazione dei nodi, nel confronto con 17 metodi di riferimento a parità di numero di archi, EDiS ottiene il punteggio medio più alto nei benchmark (accuratezza/ROC-AUC), nonché la posizione media e lo scarto rispetto al migliore più bassi tra i metodi classificati. Gli studi di ablazione mostrano che i benefici della scomposizione strutturale e della variazione tra epoche sono più evidenti quando il numero di archi consentito è molto limitato.