Flowette: Flow Matching with Graphette Priors for Graph Generation

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een meester-architect bent die nieuwe steden moet ontwerpen. Maar deze steden zijn geen gewone steden; het zijn netwerken. Soms zijn het moleculen (voor nieuwe medicijnen), soms sociale netwerken (wie kent wie), en soms biologische systemen.

Het probleem is: deze netwerken hebben een heel specifieke "structuur". Ze hebben ringen (zoals benzine in medicijnen), sterren (zoals een populaire persoon met veel vrienden), en bomen (geen lussen). Als je een computer vraagt om zo'n netwerk te bouwen, maakt hij vaak rommel: onmogelijke moleculen of netwerken die eruitzien als een brij van lijntjes.

Deze paper introduceert Flowette, een slimme nieuwe manier om deze netwerken te laten groeien. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De "Vloeiende" Reis (Flow Matching)

Stel je voor dat je een leeg stuk papier (ruis) wilt omtoveren tot een compleet getekend stadsplan.

De oude manier: Je probeerde het stukje voor stukje te tekenen, maar vaak verdwaalde je in de details en werd het plan onherkenbaar.
De Flowette-methode: Stel je voor dat je een vloeibare substantie hebt. Je begint met een wazige, onduidelijke vlek (de ruis) en je wilt die vloeistof stromen naar een perfect getekend stadsplan. Flowette leert de stroomrichting van die vloeistof. Het is alsof je een rivierbedding graaft die de vloeistof altijd in de juiste richting leidt, zodat hij precies op het einddoel belandt.

2. De "Matchmaker" (De Structuur)

Een groot probleem bij het leren van netwerken is dat computers vaak de verkeerde dingen met elkaar vergelijken.

Het probleem: Stel je voor dat je een computer leert om een huis te bouwen. Als je hem een foto van een hut geeft en vraagt om die te veranderen in een kasteel, maar je vergelijkt de ramen van de hut met de deuren van het kasteel, raakt de computer in de war. De "stroom" wordt chaotisch.
De Flowette-oplossing: Flowette gebruikt een slimme "matchmaker" (genaamd Fused Gromov-Wasserstein). Deze matchmaker kijkt niet alleen naar de kleur van de muren, maar naar de structuur. Hij zegt: "Oké, deze hoek in de hut hoort bij deze hoek in het kasteel omdat ze allebei een hoek zijn, niet omdat ze op hetzelfde punt staan."
- Dit zorgt ervoor dat de computer nooit twee totaal verschillende netwerken met elkaar vergelijkt. Het zorgt voor een soepele, logische reis van chaos naar orde.

3. De "Bouwplaat" met Magische Stickers (Graphettes)

Dit is misschien wel het coolste deel. Stel je voor dat je een standaard bouwplaat hebt (een graphon), maar die bouwplaat maakt alleen maar dichte, rommelige netwerken. Realiteit is vaak anders: soms wil je een boom (geen ringen), soms een ster (veel verbindingen op één punt).

De oude manier: Je moest een heel nieuw bouwplan maken voor elke soort netwerk.
De Flowette-methode: Ze hebben een nieuwe set "magische stickers" bedacht, genaamd Graphettes.
- Je begint met een basis-netwerk.
- Dan plak je een sticker op: "Voeg een ring toe" (voor medicijnen).
- Of: "Verwijder alle lussen" (voor bomen).
- Of: "Maak een ster van deze persoon" (voor sociale netwerken).
- Dit maakt het model extreem flexibel. Het kan van alles maken, van een strakke boom tot een complex molecuul, zonder dat je de hele motor van de computer hoeft te vervangen.

4. De "Kwaliteitscontrole" (Regulering)

Tijdens het bouwen van een molecuul mag je niet zomaar een koolstofatoom 5 bindingen geven; dat is chemisch onmogelijk.

Flowette heeft een veiligheidscontroleur in het systeem. Terwijl het netwerk groeit, kijkt deze controleur voortdurend: "Zit je binnen de regels?"
Als het model probeert een onmogelijke binding te maken, krijgt het een zachte duwtje terug in de juiste richting. Hierdoor ontstaan er bijna nooit "gebroken" of onmogelijke moleculen.

Samenvatting in één zin:

Flowette is als een slimme architect die een vloeibare rivier (de data) van een wazige start naar een perfect einddoel leidt, waarbij hij slimme matchmakers gebruikt om de juiste onderdelen te koppelen, magische stickers (Graphettes) om de juiste vorm te geven, en een strikte veiligheidscontroleur om te zorgen dat het eindresultaat echt bestaat.

Waarom is dit belangrijk?
Omdat het nu veel makkelijker en sneller is om nieuwe medicijnen te ontwerpen, betere sociale netwerken te simuleren of complexe biologische systemen te begrijpen. Het combineert de kracht van moderne AI met de echte regels van de natuur.

Each language version is independently generated for its own context, not a direct translation.

Probleemstelling

Generatieve modellering van grafen is essentieel voor toepassingen zoals moleculair ontwerp, sociale netwerken en biologische systemen. Bestaande methoden kampen echter met drie fundamentele uitdagingen:

Structuurincompatibiliteit: Bestaande Flow Matching (FM) benaderingen voor grafen gebruiken vaak een impliciete of onafhankelijke koppeling tussen ruis- en datagrafen. Dit negeert de structurele compatibiliteit onder permutatie en variatie in grootte. Het dwingen van modellen om te interpoleren tussen topologisch mismatchende paren leidt tot hoog-variatie supervisie en inconsistente snelheidsvelden.
Gebrek aan globale coherentie: Zonder expliciete regularisatie kunnen snelheidsvelden die over continue grafrepresentaties worden gedefinieerd, leiden tot ongeldige structuren (bijvoorbeeld chemisch onmogelijke bindingen) bij eindstap-integratie.
Beperkte inductieve bias: Traditionele priors zoals graphons genereren voornamelijk dichte grafen, terwijl veel real-world grafen (zoals moleculen) spaarzaam zijn en specifieke subgraaf-motieven (zoals ringen, sterren en bomen) vertonen. Bestaande methoden vertrouwen vaak op domeinspecifieke architecturen die niet goed overdraagbaar zijn.

Methodologie: Flowette

Flowette is een continu flow-matching framework dat drie kerncomponenten combineert om structureel bewuste grafgeneratie mogelijk te maken:

1. Structurele Koppeling via Fused Gromov-Wasserstein (FGW)

Om de supervisieparen structureel uit te lijnen, introduceert Flowette een koppelmethode die de topologie respecteert:

FGW-afstand: In plaats van eenvoudige index-koppeling, wordt de Fused Gromov-Wasserstein (FGW) optimale transportafstand gebruikt. Deze berekent een kostenmatrix die zowel attributen (knooppunt- en randkenmerken) als structurele relaties (intra-graf afstanden) combineert.
Hongaarse Matching: Binnen een minibatch wordt een Hongaarse matching-algoritme toegepast op de FGW-kosten om een één-op-één toewijzing te vinden tussen ruisgrafen en datagrafen. Dit zorgt ervoor dat supervisieparen topologisch compatibel zijn, wat de variatie in de snelheids supervisie drastisch verlaagt.

2. Snelheidsveld met GNN-Transformer

Het model leert een tijd-geconditioneerd vectorveld $v_\theta$ dat de transportdynamica van de bronverdeling naar de dataverdeling stuurt.

Architectuur: Een permutatie-equivariante Graph Neural Network (GNN) transformer wordt gebruikt om het snelheidsveld te parameteriseren. Deze voorspelt instantane snelheden voor de burenmatrix ( $A$ ), knooppuntkenmerken ( $X$ ) en randkenmerken ( $F$ ).
Rectified Flow: Het model gebruikt lineaire interpolanten tussen de bron- en doelpunten om een constante conditionele snelheid te leren, wat leidt tot stabielere integratie.

3. Graphette Priors

Om domeinspecifieke structurele bias in de bronverdeling in te bouwen, introduceert het paper Graphettes, een nieuwe probabilistische familie van grafprioren die graphons generaliseert.

Definitie: Een graphette $W = (W, \rho_n, f)$ bestaat uit een graphon $W$ , een verdelingsreeks $\rho_n$ voor verdunning (sparsification), en een graf-bewerkingsfunctie $f$ .
Bewerkingsfuncties (GEF): De functie $f$ $f$ kan specifieke motieven injecteren of verwijderen:
- Ring toevoegen (GEF 3): Essentieel voor moleculaire grafen (bijv. benzeenringen).
- Ster toevoegen (GEF 4): Modellering van hubs in sociale netwerken.
- Cyclus verwijderen (GEF 2): Generatie van bomen.
Dit stelt het model in staat om zowel dichte als spaarzame grafen met complexe motieven te genereren binnen één unified framework, zonder de neurale architectuur aan te passen.

4. Verbeterde Trainingsdoelstelling

De totale loss-functie combineert lokale snelheidsmatching met globale en domeinspecifieke regularisatie:
$L(\theta) = L_{vel} + \beta_{end} L_{end} + \beta_{val} L_{val} + \beta_{atom} L_{atom}$

$L_{vel}$ (Lokale Snelheid): Registreert de voorspelde snelheid tegen de rectified transportrichting.
$L_{end}$ (Eindpuntconsistentie): Straft afwijkingen van het voorspelde eindpunt af. Dit is cruciaal om te voorkomen dat kleine lokale fouten zich ophopen tot grote structurele distorties tijdens eindstap-integratie.
$L_{val}$ (Valentie Regularisatie): Een differentieerbare straal die chemische valentie-beperkingen respecteert (voorkomt over-binding).
$L_{atom}$ (Atoomtype Matching): Zorgt ervoor dat de verdeling van atoomtypen in de gegenereerde grafen overeenkomt met die in de data, wat de diversiteit verbetert.

Kernresultaten

Flowette is geëvalueerd op synthetische en real-world moleculaire datasets en presteert state-of-the-art (SOTA) of zeer competitief:

Synthetische Grafen (SBM, Bomen, Ego-netwerken): Flowette behaalde de beste scores op validiteit, uniciteit en noveliteit (V.U.N.) voor Stochastic Block Models en Bomen. Het slaagt erin om de blokkstructuur en acyclische eigenschappen perfect te behouden.
Moleculaire Generatie (QM9, ZINC250K, Guacamol, MOSES):
- Op QM9 behaalde Flowette een validiteit van 99.81% en uniciteit van 99.30%, wat een verbetering is ten opzichte van bestaande modellen zoals DiGress, GruM en DeFoG.
- Op ZINC250K werd een validiteit van 99.90% en een uniciteit van 100% bereikt.
- De ablatiestudies tonen aan dat elke component (vooral $L_{end}$ en $L_{val}$ ) essentieel is; zonder deze regularisatie daalt de validiteit drastisch (bijv. naar ~69% op QM9 zonder regularisatie).

Bijdragen en Significantie

De belangrijkste bijdragen van dit werk zijn:

Structuurbehoudende Koppeling: Het introduceren van FGW-gebaseerde koppeling en Hongaarse matching lost het probleem van topologische mismatch op in flow-matching voor grafen, wat leidt tot lagere-variatie supervisie.
Graphettes: Een nieuw wiskundig object dat graphons uitbreidt met bewerkingsfuncties voor motieven. Dit biedt een flexibele manier om inductieve bias in te bouwen zonder de modelarchitectuur te veranderen.
Stabiele Continu-Tijd Generatie: Door endpoint-consistentie en chemische regularisatie toe te voegen, garandeert Flowette dat gegenereerde grafen (vooral moleculen) geldig en chemisch haalbaar zijn, zelfs bij gebruik van numerieke integratoren met eindige stappen.
State-of-the-art Prestaties: Flowette demonstreert consistent verbeterde prestaties op diverse benchmarks, wat aantoont dat het combineren van structurele prioren met flow-based training een krachtige aanpak is voor complexe grafverdelingen.

Conclusie: Flowette overbrugt de kloof tussen theoretische flow-matching en praktische eisen voor grafgeneratie door structurele alignement, globale coherentie en domeinkennis (via graphettes) te integreren. Dit resulteert in een robuust model dat zowel de topologische als de semantische eigenschappen van grafen effectief leert modelleren.