Technische Samenvatting: DiPhon – Diffusie op Graphons voor Schaalbare Grafengeneratie

1. Probleemstelling

Diffusiemodellen hebben zich gevestigd als een leidend paradigma voor grafengeneratie, met name in domeinen zoals moleculaire vormgeving en neurale architectuurzoektochten. Het schalen van deze modellen naar grote grafen blijft echter een fundamentele uitdaging. Huidige benaderingen kampen met twee primaire beperkingen:

1. Trainings- en Implementatiekosten: Diffusiemodellen zijn computationeel duur om te trainen en te implementeren wanneer men te maken heeft met grootschalige grafen.
2. Gebrek aan Grootte-overdraagbaarheid: Zelfs wanneer ze getraind zijn op kleine grafen, blijft het onduidelijk of de geleerde generatieve mechanismen kunnen generaliseren naar grotere grafengroottes zonder hertraining.

Bestaande grafendiffusiemethoden hebben moeite om dit aan te pakken in de dicht-graaf instelling. Discrete diffusiemodellen opereren op categorische randvariabelen, wat een natuurlijke extensie naar het continue ruimtelijke domein dat vereist is door graphons verhindert. Daarentegen injecteren Gaussian SDE-gebaseerde benaderingen ruis puntgewijs maar produceren onbegrensde trajecten, die niet direct geïnterpreteerd kunnen worden als randkansen (die in $[0, 1]$ moeten liggen), waardoor hun verbinding met graphon-theorie hoogstens impliciet is.

2. Methodologie

Het artikel stelt DiPhon voor, een diffusiekader voor grootte-schaalbare grafengeneratie dat gebruikmaakt van graphons — de grootte-onafhankelijke limietobjecten van dichte graafsequenties. De methodologie overbrugt de kloof tussen continue graphon-dynamica en discrete grafengeneratie via de volgende stappen:

2.1 Forward Proces: Graphon Diffusie via Jacobi SDE

De auteurs formuleren een continu diffusieproces direct op de graphon-ruimte $W: [0, 1]^2 \to [0, 1]$. Om te garanderen dat het proces binnen het geldige waarschijnlijkheidsbereik $[0, 1]$ blijft, passen zij een Jacobi stochastische differentiële vergelijking (SDE) aan:
$$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)$$
waarbij $\mu \in (0, 1)$ de stationaire gemiddelde is, $\kappa > 0$ de aantreksnelheid (pull rate) en $\sigma > 0$ de ruissterkte. De diffusieterm verdwijnt bij de grenzen, waardoor het proces begrensd blijft.

2.2 Discretisatie: Van Graphon naar Graaf

Omdat continue graphons niet direct observeerbaar zijn, stellen de auteurs een discretise-dan-diffuse strategie voor. Zij partitioneren het eenheidsvierkant in $N^2$ cellen en definiëren een discreet proces $\tilde{W}_t^{ij}$ voor elke cel.

• Renormalisatie: Om ervoor te zorgen dat het discrete proces overeenkomt met de statistische eigenschappen van de continue "diffuse-dan-discretiseer" ideale, worden de parameters van de discrete SDE gerenormaliseerd. Specifiek wordt de ruisamplitude geschaald ($\tilde{\sigma}^2 = \sigma^2 N^2$) en wordt de driftrate ($\tilde{\kappa}$) aangepast om de discretisatie te compenseren.
• Initiële Conditie: Het proces start vanuit een geobserveerde binaire graaf $A_0$, waarbij elke invoer $A_0^{ij}$ wordt behandeld als een Bernoulli-steekproef van het gemiddelde van de onderliggende graphon-cel.

2.3 Reverse Proces en Leren

De reverse-time SDE wordt afgeleid met behulp van de standaard score-gebaseerde formulering, die de marginale score $\nabla \log \tilde{p}_t$ vereist.

• Hanteerbare Score: Voor het Jacobi-proces staat de conditionele score in een gesloten vorm die verschoven Jacobi-polynomen en hun afgeleiden bevat.
• Denoising Doelstelling: Omdat de ware initiële graphon-invoer niet observeerbaar is, trainen de auteurs een Graph Neural Network (GNN) $\Phi_\theta$ om de schone initiële graaf $A_0$ te voorspellen vanuit de ruisige staat $\tilde{W}_t$. Het netwerk wordt getraind via een binary cross-entropy loss (denoising doelstelling).
• Sampling: Tijdens inferentie wordt de reverse SDE achterwaarts geïntegreerd vanaf de stationaire distributie (Beta-distributie) naar $t=0$. De geleerde denoiser levert de noodzakelijke score-schatting op elke stap, en de finale staat wordt via onafhankelijke Bernoulli-trekken omgezet in een binaire graaf.

3. Belangrijkste Bijdragen

Het artikel levert vier primaire bijdragen:

1. C1 (Formulering): Een nieuw diffusieproces voor graphons gebaseerd op Jacobi SDE's, waaruit DiPhon wordt afgeleid door de onderliggende dynamica te discretiseren.
2. C2 (Moment Alignment): Een theoretische karakterisering die aantoont dat het discrete DiPhon-proces exact overeenkomt met het eerste moment van het continue graphon-proces. De discrepantie in het tweede moment wordt in gesloten vorm afgeleid en wordt getoond als gecontroleerd door de in-cel variantie en de discretiefactor, welke verdwijnt naarmate de grafengrootte toeneemt.
3. C3 (Sampling & Limiet): Een sampling-procedure die grafen genereert vanuit de marginale distributies van het model. De auteurs bewijzen dat in het stationaire regime, de gegenereerde grafen convergeren in homomorfisme-dichtheid naar een Erdős–Rényi graphon, wat een structurele limiet voor het proces vaststelt.
4. C4 (Empirische Schaalbaarheid): Empirische validatie die aantoont dat DiPhon getraind kan worden op kleine grafen en succesvol grotere, out-of-distribution grafen kan genereren zonder hertraining, waarbij de kerntopologische eigenschappen over diverse grafenfamilies behouden blijven.

4. Experimentele Resultaten

De auteurs evalueren DiPhon op drie synthetische grafenfamilies: Stochastic Block Models (SBM), Preferential Attachment (PA) grafen en Bomen (Trees).

• Setup: Modellen worden getraind op kleine grafen (bijv. 40–80 knopen) en getest op progressief grotere groottes (tot 3eling 300 knopen).
• Baselines: DiPhon wordt vergeleken met discrete diffusiemethoden (DiGress, DeFoG) en Gaussian diffusiemodellen (GDSS, GruM).
• Bevindingen:
  • Moment Alignment: Experimenten bevestigen dat het empirische gemiddelde en de variantie van het gediscretiseerde proces overeenkomen met de theoretische, in gesloten vorm afgeleide referenties uit de continue graphon-theorie.
  • Schaalbaarheid: DiPhon behoudt een hoge nauwkeurigheid over alle datasets en grafengroottes. In tegenstelling hiertoe vertonen discrete diffusiemethoden een prestatie-instorting bij grotere groottes, en vertonen Gaussian baselines inconsistentie, met name op boomstructuren.
  • Robuustheid: Opvallend genoeg blijft DiPhon effectief, zelfs op Boom-grafen, een schaars regime waarin de formele graphon-theorie strikt genomen niet van toepassing is, wat suggereert dat de empirische reikwijdte van de methode de theoretische garanties overstijgt.

5. Betekenis en Claims

Het artikel claimt dat DiPhon een geprincipieerde route biedt naar schaalbare grafengeneratie door graphons te gebruiken als drager van de diffusiedynamica.

• Grootte-onafhankelijkheid: Door in de graphon-ruimte te opereren, leert het model inherent een distributie die onafhankelijk is van het aantal knopen, wat transfer mogelijk maakt van kleine trainingsregimes naar grote inferentieregimes.
• Theoretische Onderbouwing: Het gebruik van Jacobi SDE's zorgt voor begrensde randkansen en maakt een rigoureuze analyse van moment-matching en convergentie in homomorfisme-dichtheid mogelijk, waarmee de beperkingen van eerdere Gaussian of discrete benaderingen worden geadresseerd.
• Praktisch Nut: Het vermogen om grote grafen te genereren zonder hertraining biedt een significant voordeel voor toepassingen die variabele grafengroottes vereisen, zoals moleculaire vormgeving of netwerkanalyse.

De auteurs erkennen beperkingen, waarbij zij opmerken dat de theoretische garanties zijn ontwikkeld voor dichte grafen en vertrouwen op moment-matching in plaats van het begrenzen van de volledige distributionele afstand. Daarnaast vereist het trainingsproces het simuleren van forward-trajecten, wat extra overhead introduceert vergeleken met modellen met tractabele transitiedichtheden. Echter, het kader wordt gepresenteerd als een fundament dat van nature kan worden uitgebreid naar knoopkenmerken en gewogen randen in toekomstig werk.