FlowSymm: Physics Aware, Symmetry Preserving Graph Attention for Network Flow Completion

FlowSymm is een nieuwe, fysisch bewuste architectuur die ontbrekende netwerkstromen reconstrueert door symmetriebehoudende acties te combineren met graph attention en Tikhonov-verfijning, waardoor het de state-of-the-art presteert op diverse real-world benchmarks zoals verkeers-, energie- en fietsnetwerken.

De kern

Stel je voor dat je een enorme, ingewikkelde puzzel hebt: een netwerk van wegen, elektriciteitsdraden of fietsroutes. Je hebt op sommige plekken sensoren die vertellen hoeveel verkeer er rijdt, hoeveel stroom er vloeit of hoeveel fietsers er gaan. Maar op veel plekken ontbreken die sensoren. De puzzelstukjes voor die plekken zijn weg.

Het probleem is dat je niet zomaar willekeurige getallen kunt invullen. Als je dat doet, krijg je onmogelijke situaties: auto's die plotseling verdwijnen bij een kruispunt, of stroom die ergens uit de lucht komt. In de echte wereld gelden er strikte natuurwetten (zoals "wat erin gaat, moet eruit komen").

FlowSym is een slimme nieuwe computer-methode die deze ontbrekende stukjes invult, maar dan op een manier die deze natuurwetten eerbiedigt. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De "Minimale" Oplossing (Het Anker)

Eerst kijkt het systeem naar wat het wel weet. Het maakt een eerste, ruwe schatting van de ontbrekende stukjes. Het kiest de "rustigste" oplossing: de oplossing waarbij de veranderingen zo klein mogelijk zijn, maar die wel voldoet aan de basisregels (bijvoorbeeld: geen auto's die verdwijnen).

• Analogie: Stel je voor dat je een drijvend vlot hebt op een meer. Je weet waar de randen zijn (de sensoren). Je legt een plank neer die precies past tussen die randen, zonder dat het vlot te veel zakt of stijgt. Dit is je startpunt.

2. De "Magische" Bewegingen (Symmetrie)

Nu komt het slimme deel. Het systeem weet dat er oneindig veel manieren zijn om de plank te verschuiven zonder dat het vlot zinkt of de randen bewegen. Het noemt deze manieren "groepswerkingen".
In plaats van te raden, maakt het systeem een lijstje met alle mogelijke, wiskundig correcte manieren om de stromen te herschikken zonder de natuurwetten te breken.

• Analogie: Stel je voor dat je een dansgroep hebt. Je weet dat ze allemaal in een cirkel kunnen dansen zonder dat iemand de cirkel verlaat. Het systeem heeft een lijstje met alle mogelijke danspassen die binnen die cirkel passen.

3. De "Slimme Drukker" (Aandacht)

Nu moet het systeem kiezen: welke van die danspassen moeten we nu gebruiken? Het kijkt naar de lokale details (bijvoorbeeld: is het een drukke weg? Is het een smalle fietspad?).
Het gebruikt een "aandachtsmechanisme" (een soort slimme filter) om te beslissen welke danspassen op dat moment het beste werken. Het combineert de juiste bewegingen op basis van de situatie.

• Analogie: Een regisseur die naar de dansers kijkt en zegt: "Jij, doe die stap! En jij, doe die andere!" De regisseur kiest de beste combinatie van bewegingen op basis van wat er op dat moment gebeurt.

4. De "Finishing Touch" (De verfijning)

Soms zijn de sensoren niet 100% precies (ruis). De laatste stap is een kleine, gecontroleerde aanpassing om de metingen zo goed mogelijk te laten kloppen, zonder de natuurwetten te schenden.

• Analogie: Het is alsof je een schilderij hebt gemaakt. Je hebt de grote lijnen goed, maar nu schuif je nog een paar penseelstreken een beetje op om de kleuren perfect te laten matchen met de originele foto, zonder dat het schilderij er anders uitziet.

Waarom is dit zo goed?

Vroeger probeerden computers dit op twee manieren:

1. Alleen wiskunde: Ze hielden zich strikt aan de regels, maar waren niet slim genoeg om de echte wereld te begrijpen (ze waren te stijf).
2. Alleen AI: Ze waren slim en konden patronen leren, maar maakten vaak foute voorspellingen die de natuurwetten schonden (bijvoorbeeld: stroom die verdwijnt).

FlowSym combineert het beste van beide werelden. Het gebruikt de kracht van moderne AI om patronen te leren, maar bouwt die AI zo in dat het onmogelijk is om een fout te maken die de natuurwetten schendt. Het is alsof je een zeer slimme kunstenaar hebt die ook een strenge wiskundeleraar is.

Het resultaat:
In tests met verkeersdata, elektriciteitsnetten en fietsroutes bleek FlowSym veel nauwkeuriger te zijn dan de beste bestaande methoden. Het voorspelt niet alleen beter hoeveel er rijdt of vloeit, maar het begrijpt ook waarom het zo is, omdat het de onderliggende regels respecteert.

Kortom: FlowSym is de perfecte puzzeloplosser die nooit vergeet dat de stukjes fysiek moeten passen.

Technische samenvatting

Probleemstelling

Het paper adresseert het fundamentele inverse probleem van het reconstrueren van ontbrekende stromen op de randen van een netwerk, waarbij strikt wordt voldaan aan lokale behoudswetten (zoals de behoud van massa of lading). Dit komt veel voor in systemen zoals verkeersnetwerken, energienetwerken en mobiliteit.

• Uitdaging: In de praktijk zijn slechts een fractie van de randen uitgerust met sensoren. Eenvoudige imputatie (het invullen van ontbrekende waarden) leidt vaak tot fysisch onwaarschijnlijke voorspellingen die de behoudswetten schenden (bijvoorbeeld verkeersaantallen die niet kloppen op kruispunten of stromen die de wetten van Kirchhoff negeren).
• Formulering: Het probleem wordt wiskundig beschreven door de knooppunt-balansvergelijking $Bf = c$, waarbij $B$ de inidentiematrix is, $f$ de vector van randstromen, en $c$ de onbekende netto-injecties. Het doel is om de onwaargenomen stromen ($E_{miss}$) te schatten op basis van de waargenomen stromen ($E_{obs}$) en de features van de randen, zonder de fysica te schenden.

Methodologie: FLOWSYMM

FLOWSYMM is een nieuwe architectuur die graf-attention combineert met symmetriebehoudende correcties. De aanpak bestaat uit vijf hoofdstappen:

1. Initieel Gebalanceerd Anker:
   Het model begint met het construeren van een voorlopige volledige stroom $f^{(0)}$ die voldoet aan de behoudswet ($Bf=c$) en de waargenomen waarden exact respecteert. Dit wordt gedaan door de minimum-norm oplossing te vinden voor de ontbrekende randen via de Moore-Penrose pseudoinversie. Dit zorgt ervoor dat alle latere updates binnen het fysische manifold blijven.

2. Basis van Groepsacties (Symmetriebehoud):
   In plaats van willekeurige correcties toe te passen, definieert het model een abelse groep van mogelijke, fysisch geldige aanpassingen. Een "groepswerking" is een verdeling van stroom die:

   • De nodale balans behoudt (divergentievrij, $Bu=0$).
   • Geen enkele instrumenteerde (waargenomen) rand verandert ($u_e = 0$ voor $e \in E_{obs}$).
     De auteurs construeren een orthonormale basis $U$ voor deze ruimte van aanpassingen. Dit vormt een gespecialiseerde latente ruimte die specifiek is voor de algebraïsche symmetrieën van het stroomprobleem, in plaats van de gebruikelijke ruimtelijke of permutatie-symmetrieën.

3. Attention-Gestuurde Selectie:
   Een stack van GATv2-lagen (Graph Attention Networks) encodeert de grafstructuur en randfeatures. Voor elke ontbrekende rand en elke basisvector in $U$ wordt een compatibiliteitsscore berekend. Een softmax-functie genereert attention-weights ($\alpha$) die bepalen welke groepswerkingen het meest relevant zijn voor de huidige graf-snapshot. De geselecteerde correctie is een lineaire combinatie van de basisvectoren: $\Delta = U\alpha$. Dit zorgt ervoor dat het model correcties toepast waar de lokale structuur en features om vragen, terwijl de globale balans behouden blijft.

4. Tikhonov-Refinement (Fijnafstelling):
   Hoewel de attention-stap een gebalanceerde kandidaat levert, kan er sprake zijn van meetruis. Een laatste stap gebruikt een Tikhonov-geregulariseerd kleinste-kwadratenprobleem om de ontbrekende waarden verder te verfijnen. Dit lost een convex probleem op dat een compromis zoekt tussen het minimaliseren van de residuen t.o.v. de waarnemingen en dicht bij de attention-gestuurde kandidaat blijven.

5. Implicit Bilevel Training:
   Alle parameters (GAT-weights en de regularisatieparameter $\lambda$) worden end-to-end getraind. In plaats van de iteraties van de solver te "unrollen", wordt gebruik gemaakt van impliciete differentiatie (via Cholesky-factorisatie). Dit maakt het mogelijk om exacte hyper-gradiënten te berekenen met minimale geheugenkost, wat schaalbaarheid en stabiliteit garandeert.

Belangrijkste Bijdragen

• Algebraïsche Symmetrie: Het introduceren van een groepswerkings-basis die specifiek is voor de algebraïsche beperkingen van stroombehoud (divergentievrij en sensor-invariantie), in plaats van geometrische symmetrieën.
• Interpreteerbaarheid: Het model leert gewichten voor fysiek interpreteerbare basisacties, wat inzicht geeft in hoe het model de stroom herverdeelt.
• Efficiënte Optimisatie: De combinatie van attention-gestuurde selectie met een convex Tikhonov-solver en impliciete differentiatie voor training.
• Garantie van Behoud: Het ontwerp garandeert dat waargenomen randen nooit worden gewijzigd en dat de behoudswetten structureel worden gerespecteerd, terwijl het toch flexibel genoeg is om ruis te hanteren.

Resultaten

Het model is getest op drie real-world benchmarks: verkeersstromen (LA County), elektriciteitsnetwerken (Europees transmissienet) en fietsverkeer (Citi Bike).

• Prestaties: FLOWSYMM presteert consistent beter dan state-of-the-art baselines (zoals Bil-GCN, GCN, MLP en pure fysica-baselines).
  • RMSE: Reductie van ongeveer 8% (verkeer), 10% (stroom) en 9% (fiets) ten opzichte van de vorige beste methode (Bil-GCN).
  • MAE & Correlatie: Significante verbeteringen in Mean Absolute Error en Pearson-correlatie, wat aangeeft dat de voorspellingen niet alleen nauwkeuriger zijn, maar ook de onderliggende patronen beter vastleggen.
• Ablatiestudies:
  • Het gebruik van de groepswerkings-basis is cruciaal; zonder deze (alleen attention) daalt de prestatie aanzienlijk.
  • De grootte van de basis ($k=256$) is voldoende om de variabiliteit te vangen; grotere bases brengen geen extra winst.
  • Impliciete differentiatie is essentieel voor stabiele training.

Betekenis en Toekomstperspectief

FLOWSYMM demonstreert dat het koppelen van geleerde graf-attention aan symmetriebehoudende stroomcorrecties een krachtige route is naar state-of-the-art netwerkstroom-completie. Het biedt een transparante en controleerbare methode die fysica respecteert zonder de flexibiliteit van machine learning op te offeren.

• Toepassingen: Het is direct toepasbaar op verkeersplanning, netwerkbetrouwbaarheid en mobiliteitsplanning.
• Toekomst: De auteurs zien kansen in het uitbreiden naar tijdsafhankelijke dynamica (recurrente encoders) en het gezamenlijk infereren van de netto-injecties ($c$) in plaats van deze als vast te beschouwen. De modulaire aard van de architectuur maakt het ook toepasbaar op andere lineaire constraint-problemen, zoals warmtediffusie of epidemiologische modellen.