Résumé technique : DiPhon – Diffusion sur les graphons pour la génération de graphes à échelle variable

1. Énoncé du problème

Les modèles de diffusion se sont imposés comme un paradigme de premier plan pour la génération de graphes, particulièrement dans des domaines tels que la conception moléculaire et la recherche d'architecture neuronale. Cependant, l'adaptation de ces modèles à des graphes de grande taille reste un défi fondamental. Les approches actuelles font face à deux limitations principales :

1. Coûts d'entraînement et de déploiement : Les modèles de diffusion sont coûteux en termes de calcul pour l'entraînement et le déploiement lorsqu'ils traitent des graphes à grande échelle.
2. Absence de transférabilité de taille : Même lorsqu'ils sont entraînés sur de petits graphes, il reste incertain si les mécanismes génératifs appris peuvent se généraliser à des tailles de graphes plus grandes sans réentraînement.

Les méthodes de diffusion de graphes existantes peinent à répondre à ce problème dans le cadre des graphes denses. Les modèles de diffusion discrets opèrent sur des variables d'arêtes catégorielles, empêchant une extension naturelle vers le domaine spatial continu requis par les graphons. À l'inverse, les approches basées sur les SDE gaussiennes injectent du bruit point par point mais produisent des trajectoires non bornées, lesquelles ne peuvent pas être directement interprétées comme des probabilités d'arêtes (qui doivent se situer dans $[0, 1]$), rendant leur connexion avec la théorie des graphons, au mieux, implicite.

2. Méthodologie

Le papier propose DiPhon, un cadre de diffusion pour la génération de graphes à échelle variable qui exploite les graphons — les objets limites indépendants de la taille des séquences de graphes denses. La méthodologie comble le fossé entre la dynamique continue des graphons et la génération de graphes discrets via les étapes suivantes :

2.1 Processus direct : Diffusion de graphon via SDE de Jacobi

Les auteurs formulent un processus de diffusion continu directement sur l'espace des graphons $W: [0, 1]^2 \to [0, 1]$. Pour garantir que le processus reste dans la plage de probabilité valide $[0, 1]$, ils adaptent une équation différentielle stochastique (SDE) de Jacobi :
$$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)$$
où $\mu \in (0, 1)$ est la moyenne stationnaire, $\kappa > 0$ est le taux d'attraction, et $\sigma > 0$ est l'intensité du bruit. Le terme de diffusion s'annule aux frontières, maintenant le processus borné.

2.2 Discrétisation : Du graphon au graphe

Comme les graphons continus ne sont pas directement observables, les auteurs proposent une stratégie de type « discrétiser puis diffuser ». Ils partitionnent le carré unité en $N^2$ cellules et définissent un processus discret $\tilde{W}_t^{ij}$ pour chaque cellule.

• Renormalisation : Pour garantir que le processus discret corresponde aux propriétés statistiques du idéal continu « diffuser puis discrétiser », les paramètres de la SDE discrète sont renormalisés. Plus précisément, l'amplitude du bruit est mise à l'échelle ($\tilde{\sigma}^2 = \sigma^2 N^2$) et le taux de dérive est ajusté ($\tilde{\kappa}$) pour compenser la discrétisation.
• Condition initiale : Le processus part d'un graphe binaire observé $A_0$, où chaque entrée $A_0^{ij}$ est traitée comme un échantillon de Bernoulli de la moyenne de la cellule du graphon sous-jacent.

2.3 Processus inverse et apprentissage

La SDE de temps inverse est dérivée en utilisant la formulation standard basée sur le score, nécessitant le score marginal $\nabla \log \tilde{p}_t$.

• Score traitable : Pour le processus de Jacobi, le score conditionnel admet une expression en forme close impliquant des polynômes de Jacobi décalés et leurs dérivées.
• Objectif de débruitage : Puisque la véritable entrée initiale du graphon est inobservée, les auteurs entraînent un réseau de neurones sur graphe (GNN) $\Phi_\theta$ pour prédire le graphe initial propre $A_0$ à partir de l'état bruité $\tilde{W}_t$. Le réseau est entraîné via une perte de cross-entropie binaire (objectif de débruitage).
• Échantillonnage : Lors de l'inférence, la SDE inverse est intégrée vers l'arrière depuis la distribution stationnaire (distribution Beta) vers $t=0$. Le débruiteur appris fournit l'estimation de score nécessaire à chaque étape, et l'état final est converti en un graphe binaire via des tirages de Bernoulli indépendants.

3. Principales contributions

Le papier présente quatre contributions majeures :

1. C1 (Formulation) : Un nouveau processus de diffusion pour les graphons basé sur les SDE de Jacobi, à partir duquel DiPhon est dérivé par la discrétisation de la dynamique sous-jacente.
2. C2 (Alignement des moments) : Une caractérisation théorique montrant que le processus discret de DiPhon correspond exactement au premier moment du processus de graphon continu. L'écart du second moment est dérivé en forme close et montre qu'il est contrôlé par la variance intra-cellule et le facteur de discrétisation, s'annulant à mesure que la taille du graphe augmente.
3. C3 (Échantillonnage et limite) : Une procédure d'échantillonnage qui génère des graphes à partir des distributions marginales du modèle. Les auteurs prouvent que, dans le régime stationnaire, les graphes générés convergent en densité d'homomorphisme vers un graphon d'Erdős–Rényi, établissant une limite structurelle pour le processus.
4. C4 (Scalabilité empirique) : Validation empirique démontrant que DiPhon peut être entraîné sur de petits graphes et générer avec succès des graphes plus grands, hors distribution, sans réentraînement, tout en préservant les propriétés topologiques fondamentales à travers diverses familles de graphes.

4. Résultats expérimentaux

Les auteurs évaluent DiPhon sur trois familles de graphes synthétiques : Modèles de blocs stochastiques (SBM), graphes de type attachement préférentiel (PA) et arbres.

• Configuration : Les modèles sont entraînés sur de petits graphes (ex: 40–80 nœuds) et testés sur des tailles progressivement plus grandes (jusqu'à 300 nœuds).
• Baselines : DiPhon est comparé à des méthodes de diffusion discrète (DiGress, DeFoG) et à des modèles de diffusion gaussienne (GDSS, GruM).
• Résultats :
  • Alignement des moments : Les expériences confirment que la moyenne et la variance empiriques du processus discret s'alignent avec les références théoriques en forme close dérivées de la théorie des graphons continus.
  • Scalabilité : DiPhon maintient une haute précision sur tous les jeux de données et toutes les tailles de nœuds. En revanche, les méthodes de diffusion discrète montrent un effondrement des performances à des tailles plus grandes, et les baselines gaussiennes présentent une certaine inconsistance, particulièrement sur les structures d'arbres.
  • Robustesse : Notamment, DiPhon reste efficace même sur les graphes de type Arbre, un régime creux où la théorie formelle des graphons ne s'applique pas strictement, suggérant que la portée empirique de la méthode dépasse ses garanties théoriques.

5. Signification et affirmations

Le papier affirme que DiPhon offre une voie fondée sur des principes vers la génération de graphes à échelle variable en utilisant les graphons comme support de la dynamique de diffusion.

• Indépendance de la taille : En opérant dans l'espace des graphons, le modèle apprend intrinsèquement une distribution qui est indépendante du nombre de nœuds, permettant le transfert d'un petit régime d'entraînement vers un grand régime d'inférence.
• Fondement théorique : L'utilisation des SDE de Jacobi garantit des probabilités d'arêtes bornées et permet une analyse rigoureuse de l'alignement des moments et de la convergence en densité d'homomorphisme, répondant ainsi aux limites des approches gaussiennes ou discrètes précédentes.
• Utilité pratique : La capacité de générer de grands graphes sans réentraînement offre un avantage significatif pour les applications nécessitant des tailles de graphes variables, telles que la conception moléculaire ou l'analyse de réseaux.

Les auteurs reconnaissent certaines limites, notant que les garanties théoriques sont développées pour les graphes denses et reposent sur l'alignement des moments plutôt que sur la limitation de la distance distributionnelle complète. De plus, le processus d'entraînement nécessite de simuler des trajectoires directes, introduisant un surcoût par rapport aux modèles ayant des densités de transition tractables. Cependant, le cadre est présenté comme une fondation pouvant naturellement s'étendre aux caractéristiques des nœuds et aux arêtes pondérées dans des travaux futurs.