Riepilogo Tecnico: DiPhon – Diffusion on Graphons for Scalable Graph Generation

1. Definizione del Problema

I modelli di diffusione si sono affermati come un paradigma leader per la generazione di grafi, particolarmente in domini come la progettazione molecolare e la ricerca di architetture neurali. Tuttavia, scalare questi modelli a grafi di grandi dimensioni rimane una sfida fondamentale. Gli approcci attuali affrontano due limitazioni primarie:

1. Costi di Addestramento e Deployment: I modelli di diffusione sono computazionalmente costosi da addestrare e implementare quando si trattano grafi su larga scala.
2. Mancanza di Trasferibilità delle Dimensioni: Anche quando addestrati su grafi piccoli, rimane incerto se i meccanismi generativi appresi possano generalizzare a dimensioni di grafo più grandi senza un nuovo addestramento.

I metodi di diffusione per grafi esistenti faticano ad affrontare questo problema nel contesto dei grafi densi. I modelli di diffusione discreti operano su variabili di arco categoriche, impedendo un'estensione naturale al dominio spaziale continuo richiesto dai graphon. Al contrario, gli approcci basati su SDE Gaussiane iniettano rumore punto per punto ma producono traiettorie illimitate, che non possono essere interpretate direttamente come probabilità di arco (che devono appartenere all'intervallo $[0, 1]$), rendendo la loro connessione con la teoria dei graphon al massimo implicita.

2. Metodologia

Il paper propone DiPhon, un framework di diffusione per la generazione di grafi scalabile rispetto alla dimensione, che sfrutta i graphon — gli oggetti limite indipendenti dalla dimensione delle sequenze di grafi densi. La metodologia colma il divario tra la dinamica continua dei graphon e la generazione di grafi discreti attraverso i seguenti passaggi:

2.1 Processo Forward: Graphon Diffusion via Jacobi SDE

Gli autori formulano un processo di diffusione continuo direttamente nello spazio dei graphon $W: [0, 1]^2 \to [0, 1]$. Per garantire che il processo rimanga entro l'intervallo di probabilità valido $[0, 1]$, adattano una SDE di Jacobi (Jacobi stochastic differential equation):
$$dW_t(x, y) = \kappa (\mu - W_t(x, y)) dt + \sigma \sqrt{W_t(x, y)(1 - W_t(x, y))} dB_t(x, y)$$
dove $\mu \in (0, 1)$ è la media stazionaria, $\kappa > 0$ è il tasso di attrazione (pull rate) e $\sigma > 0$ è l'intensità del rumore. Il termine di diffusione svanisce ai bordi, mantenendo il processo limitato.

2.2 Discretizzazione: Dal Graphon al Grafo

Poiché i graphon continui non sono direttamente osservabili, gli autori propongono una strategia discretize-then-diffuse (discretizza-e-poi-diffondi). Partizionano il quadrato unitario in $N^2$ celle e definiscono un processo discreto $\tilde{W}_t^{ij}$ per ogni cella.

• Rinormalizzazione: Per garantire che il processo discreto corrisponda alle proprietà statistiche del ideale continuo "diffuse-then-discretize", i parametri della SDE discreta vengono rinormalizzati. Nello specifico, l'ampiezza del rumore viene scalata ($\tilde{\sigma}^2 = \sigma^2 N^2$) e il tasso di drift viene regolato ($\tilde{\kappa}$) per compensare la discretizzazione.
• Condizione Iniziale: Il processo parte da un grafo binario osservato $A_0$, dove ogni voce $A_0^{ij}$ è trattata come un campione Bernoulli della media della cella del graphon sottostante.

2.3 Processo Inverso e Apprendimento

La SDE nel tempo inverso viene derivata utilizzando la standard formulazione basata sullo score, che richiede lo score marginale $\nabla \log \tilde{p}_t$.

• Score Trattabile: Per il processo di Jacobi, lo score condizionale ammette un'espressione in forma chiusa che coinvolge polinomi di Jacobi traslati e le loro derivate.
• Obiettivo di Denoising: Poiché la vera voce iniziale del graphon non è osservabile, gli autori addestrano una rete neurale su grafi (GNN) $\Phi_\theta$ per predire il grafo iniziale pulito $A_0$ a partire dallo stato rumoroso $\tilde{W}_t$. La rete è addestrata tramite una perdita di cross-entropia binaria (obiettivo di denoising).
• Campionamento: Durante l'inferenza, la SDE inversa viene integrata all'indietro dalla distribuzione stazionaria (distribuzione Beta) fino a $t=0$. Il denoiser appreso fornisce la necessaria stima dello score ad ogni step, e lo stato finale viene convertito in un grafo binario tramite campionamenti Bernoulli indipendenti.

3. Contributi Chiave

Il paper presenta quattro contributi principali:

1. C1 (Formulazione): Un nuovo processo di diffusione per i graphon basato su SDE di Jacobi, da cui deriva DiPhon mediante la discretizzazione della dinamica sottostante.
2. C2 (Allineamento dei Momenti): Una caratterizzazione teorica che mostra come il processo discreto di DiPhon corrisponda esattamente al primo momento del processo continuo del graphon. La discrepanza del secondo momento è derivata in forma chiusa e si dimostra essere controllata dalla varianza intra-cella e dal fattore di discretizzazione, svanendo all'aumentare della dimensione del grafo.
3. C3 (Campionamento e Limite): Una procedura di campionamento che genera grafi dalle distribuzioni marginali del modello. Gli autori dimostrano che, nel regime stazionario, i grafi generati convergono in densità di omoomorfismo a un graphon di Erdős–Rényi, stabilendo un limite strutturale per il processo.
4. C4 (Scalabilità Empirica): Validazione empirica che dimostra come DiPhon possa essere addestrato su grafi piccoli e generare con successo grafi più grandi, out-of-distribution, senza nuovo addestramento, preservando le proprietà topologiche fondamentali attraverso varie famiglie di grafi.

4. Risultati Sperimentali

Gli autori valutano DiPhon su tre famiglie di grafi sintetici: Modelli a Blocchi Stocastici (SBM), grafi di Attaccamento Preferenziale (PA) e Alberi (Trees).

• Setup: I modelli sono addestrati su grafi piccoli (es. 40–80 nodi) e testati su dimensioni progressivamente maggiori (fino a 300 nodi).
• Baseline: DiPhon viene confrontato con metodi di diffusione discreta (DiGress, DeFoG) e modelli di diffusione gaussiana (GDSS, GruM).
• Risultati:
  • Allineamento dei Momenti: Gli esperimenti confermano che la media empirica e la varianza del processo discretizzato si allineano con i riferimenti teorici in forma chiusa derivati dalla teoria dei graphon continui.
  • Scalabilità: DiPhon mantiene un'alta accuratezza su tutti i dataset e le dimensioni dei nodi. Al contrario, i metodi di diffusione discreta mostrano un collasso delle prestazioni a dimensioni maggiori, e le baseline gaussiane esibiscono inconsistenza, particolarmente sulle strutture ad albero.
  • Robustezza: Notevolmente, DiPhon rimane efficace anche sui grafi ad Albero, un regime sparso in cui la teoria formale dei graphon non si applica strettamente, suggerendo che l'ambito empirico del metodo superi le sue garanzie teoriche.

5. Significato e Affermazioni

Il paper sostiene che DiPhon fornisca una via fondata verso la generazione di grafi scalabile utilizzando i graphon come portatori della dinamica di diffusione.

• Indipendenza dalla Dimensione: Operando nello spazio dei graphon, il modello apprende intrinsecamente una distribuzione che è indipendente dal numero di nodi, consentendo il trasferimento da piccoli regimi di addestramento a grandi regimi di inferenza.
• Fondamento Teorico: L'uso di SDE di Jacobi garantisce probabilità di arco limitate e permette un'analisi rigorosa del matching dei momenti e della convergenza nella densità di omoomorfismo, affrontando le limitazioni degli approcci gaussiani o discreti precedenti.
• Utilità Pratica: La capacità di generare grafi su larga scala senza nuovo addestramento offre un vantaggio significativo per applicazioni che richiedono dimensioni di grafo variabili, come la progettazione molecolare o l'analisi di reti.

Gli autori riconoscono i limiti, notando che le garanzie teoriche sono sviluppate per grafi densi e si affidano al matching dei momenti piuttosto che al vincolo della distanza distributiva completa. Inoltre, il processo di addestramento richiede la simulazione di traiettorie forward, introducendo un overhead rispetto ai modelli con densità di transizione trattabili. Tuttavia, il framework è presentato come una base che può naturalmente estendersi alle feature dei nodi e agli archi pesati nel lavoro futuro.