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

FlowSymm ist ein neuartiger, physikbewusster Graph-Attention-Ansatz, der durch die Kombination von divergenzfreien Gruppenaktionen, einem auf Graphen basierenden Encoder und einer Tikhonov-Verfeinerung fehlende Netzwerkflüsse rekonstruiert, wobei lokale Erhaltungsgesetze exakt eingehalten werden und die Methode auf realen Verkehrs-, Energie- und Fahrrad-Datensätzen den aktuellen Stand der Technik übertrifft.

Das Wesentliche

Stell dir vor, du bist ein Verkehrsplaner in einer riesigen Stadt. Du hast Sensoren an vielen Straßen, die dir sagen, wie viele Autos wo fahren. Aber es gibt Lücken! An manchen Kreuzungen fehlen die Sensoren komplett. Deine Aufgabe ist es, den gesamten Verkehrsfluss zu rekonstruieren – also herauszufinden, wie viel Verkehr auf den Straßen ohne Sensoren ist.

Das Problem: Wenn du einfach nur die fehlenden Zahlen „errätst" (wie ein Computer, der nur raten würde), könntest du zu Unsinnigem kommen. Zum Beispiel: 100 Autos kommen an einer Kreuzung an, aber 150 fahren davon weg. Das ist physikalisch unmöglich! Autos verschwinden nicht einfach in der Luft.

Hier kommt FLOWSYMM ins Spiel. Es ist eine neue, clevere Methode, um diese fehlenden Daten zu füllen, ohne die Gesetze der Physik zu brechen.

Hier ist die Erklärung, wie es funktioniert, mit ein paar einfachen Analogien:

1. Das Grundgerüst: Der „perfekte" erste Entwurf

Stell dir vor, du hast ein Puzzle, bei dem einige Teile fehlen. Bevor du anfängst zu raten, legst du erst einmal alle Teile, die du hast, so hin, dass sie perfekt zusammenpassen.
FLOWSYMM macht genau das. Es nimmt die gemessenen Daten und berechnet sofort eine mathematisch perfekte Basis. Diese Basis garantiert, dass an jeder Kreuzung so viele Autos rein- wie rausfahren (das nennt man „Erhaltungssatz"). Es ist wie ein stabiles Fundament, auf dem wir bauen können.

2. Der geheime Trick: Der „Symmetrie-Orchester"

Jetzt kommt der spannende Teil. Wie füllen wir die Lücken, ohne das Fundament zu zerstören?
Stell dir vor, der gesamte Verkehrsfluss ist wie ein Orchester. Die Sensoren sind die Musiker, die wir hören können. Die fehlenden Sensoren sind die Musiker, die wir nicht sehen.

FLOWSYMM weiß, dass es bestimmte „Bewegungsmuster" im Orchester gibt, die man hinzufügen kann, ohne dass sich das Gesamtbild für die Zuhörer (die Sensoren) ändert.

• Die Analogie: Stell dir vor, du hast eine Gruppe von Musikern. Wenn der Geiger leiser spielt, muss der Cellist etwas lauter werden, damit die Melodie gleich klingt. Das ist eine „Symmetrie".
• FLOWSYMM hat eine Bibliothek mit hunderten solcher legalen Bewegungsmuster (die Autoren nennen sie „Gruppenaktionen"). Jedes Muster ist eine Art, wie man den Verkehr auf den fehlenden Straßen umverteilen kann, ohne dass die gemessenen Werte an den Sensoren sich ändern.

3. Der Dirigent: Die „Aufmerksamkeit" (Attention)

Jetzt haben wir hunderte von legalen Bewegungsmustern. Aber welches sollen wir benutzen? Nicht jedes Muster passt zu jeder Situation.
Hier kommt der Aufmerksamkeits-Mechanismus ins Spiel. Stell dir das wie einen intelligenten Dirigenten vor.

• Der Dirigent schaut sich die Umgebung an (die Straßentypen, die Tageszeit, die Topologie).
• Er entscheidet dann: „Heute passt am besten das Muster Nr. 42, bei dem der Verkehr auf der Hauptstraße etwas fließt, während die Nebenstraßen ruhiger sind."
• Er kombiniert also verschiedene Muster zu einer perfekten Lösung, die genau auf die aktuelle Situation zugeschnitten ist.

4. Der Feinschliff: Der „Sanfte Polierer"

Manchmal sind die Sensoren nicht perfekt (Rauschen, Fehler). Die perfekte mathematische Lösung könnte also leicht von der Realität abweichen.
FLOWSYMM nutzt einen letzten Schritt, einen Tikhonov-Filter. Stell dir das wie einen Polierer vor, der das Bild leicht glättet. Er sorgt dafür, dass die Lösung nicht nur mathematisch sauber ist, sondern auch so nah wie möglich an den gemessenen Daten liegt, ohne die physikalischen Gesetze zu verletzen.

Warum ist das so toll?

Bisherige Methoden haben oft einfach geraten oder starre Regeln benutzt. FLOWSYMM ist wie ein erfahrener Detektiv, der:

1. Die Gesetze der Physik (kein Verschwinden von Autos) strikt einhält.
2. Aus einer Bibliothek von „legalen Tricks" das perfekte Muster für den Moment auswählt.
3. Alles in einem Schritt lernt, ohne dass man ihm jede Regel einzeln beibringen muss.

Das Ergebnis: In Tests mit echten Daten (Autos in Los Angeles, Stromnetze in Europa und Fahrräder in New York) war FLOWSYMM deutlich genauer als alle anderen Methoden. Es sagt nicht nur die Zahlen richtig voraus, sondern versteht auch, warum der Verkehr so fließt, wie er fließt.

Kurz gesagt: FLOWSYMM ist ein smarter Assistent, der fehlende Daten in Netzwerken (wie Straßen oder Stromleitungen) ergänzt, indem er die Gesetze der Physik respektiert und wie ein genialer Dirigent die richtigen Muster aus einer Bibliothek auswählt, um das perfekte Bild zu vervollständigen.

Technische Zusammenfassung

1. Problemstellung

Die Rekonstruktion fehlender Flüsse in Netzwerken (z. B. im Verkehr, Energienetz oder bei Mikromobilität) ist ein fundamentales inverses Problem. In der Praxis sind nur ein Bruchteil der Kanten mit Sensoren ausgestattet. Einfache Imputationsmethoden führen oft zu physikalisch unplausiblen Vorhersagen, die lokale Erhaltungsgesetze verletzen (z. B. Kirchhoffsche Gesetze im Stromnetz oder Erhaltungssätze an Verkehrsknoten).

Das Ziel ist es, die fehlenden Flusswerte ($f_{miss}$) basierend auf beobachteten, verrauschten Daten ($\hat{f}_{obs}$) und bekannten Netzwerkinjektionen ($c$) so zu rekonstruieren, dass:

1. Die physikalischen Erhaltungsgesetze ($Bf = c$, wobei $B$ die Inzidenzmatrix ist) eingehalten werden.
2. Die beobachteten Sensordaten unverändert bleiben (da diese als feste Messwerte gelten).
3. Die Lösung robust gegenüber Rauschen ist.

2. Methodik: FLOWSYMM

FLOWSYMM ist eine neue Architektur, die Graph-Attention-Mechanismen mit physikbewussten, symmetrieerhaltenden Korrekturen kombiniert. Der Ansatz folgt einem vierstufigen Prozess:

A. Initialer balancierter Abschluss (Initial Balanced Completion)

Zunächst wird ein vorläufiger vollständiger Flussvektor $f^{(0)}$ konstruiert, der die beobachteten Werte annimmt und die fehlenden Werte so ergänzt, dass die Knotenbilanz ($Bf=c$) exakt erfüllt ist. Dies geschieht durch die Berechnung der Minimum-Norm-Lösung unter Verwendung der Moore-Penrose-Pseudoinversen. Dieser Schritt verankert die Lösung auf dem physikalischen Mannigfaltigkeitsraum der zulässigen Flüsse.

B. Basis für Gruppenaktionen (Group-Action Basis)

Das Kernstück der Methode ist die Identifikation des Raums aller zulässigen, divergenzfreien Anpassungen, die die beobachteten Kanten nicht verändern.

• Algebraische Symmetrie: Die Menge aller Vektoren $u$, für die $Bu=0$ gilt und die auf beobachteten Kanten null sind, bildet eine abelsche Gruppe unter Vektoraddition.
• Orthonormale Basis: Es wird eine orthonormale Basis $U \in \mathbb{R}^{m \times k}$ für diesen Unterraum (den Kern von $B$ eingeschränkt auf fehlende Kanten) konstruiert.
• Unterschied zu herkömmlichen GNNs: Während viele GNNs räumliche Symmetrien (Rotation/Translation) kodieren, kodiert FLOWSYMM algebraische Symmetrien, die spezifisch durch die Inzidenzmatrix und das Sensor-Maskierungsmuster definiert sind.

C. Attention-gesteuerte Auswahl (Attention-Guided Selection)

Anstatt alle Basisvektoren gleichgewichtet zu nutzen, verwendet das Modell einen Graph-Attention-Encoder (GATv2), um die Kantenmerkmale zu verarbeiten.

• Der Encoder erzeugt Embeddings für jede Kante.
• Eine Kompatibilitätsfunktion bewertet, wie stark jede Basisaktion $u^{(i)}$ für die lokale Struktur einer fehlenden Kante $e$ geeignet ist.
• Diese lokalen Bewertungen werden aggregiert und durch eine Softmax-Funktion in Gewichte $\alpha_\theta$ umgewandelt.
• Das Ergebnis ist eine gewichtete Linearkombination der Basisvektoren ($\Delta = U \alpha_\theta$), die eine physikalisch korrekte Korrektur darstellt, die auf den lokalen Merkmalen des Graphen basiert.

D. Tikhonov-Verfeinerung und implizite Bilevel-Optimierung

Der durch die Attention gewählte Kandidat wird durch einen Tikhonov-Regularisierer verfeinert, um Rauschen in den Sensordaten auszugleichen. Dies wird als konvexes Least-Squares-Problem formuliert, das einen Kompromiss zwischen der Einhaltung der empirischen Bilanz und der Nähe zum Attention-Kandidaten findet.

• Implizite Differentiation: Anstatt die Iterationen des Löser zu entrollen (unrolling), wird die Verfeinerungsschicht als implizite Schicht behandelt. Gradienten werden durch die Cholesky-Zerlegung des linearen Systems zurückpropagiert. Dies ermöglicht ein end-to-end Training aller Parameter (einschließlich der Attention-Gewichte und des Regularisierungsterms $\lambda$) mit minimalem Speicheraufwand.

3. Wichtige Beiträge

1. Neue Symmetrie-Formulierung: Die Definition von divergenzfreien Anpassungen als Elemente einer abelschen Gruppenaktion, die spezifisch auf das Problem der unvollständigen Beobachtung zugeschnitten ist.
2. Physikbewusste Attention: Ein Mechanismus, der lernt, welche physikalischen Moden (Basisvektoren) basierend auf lokalen Graphmerkmalen aktiviert werden sollen, anstatt jede Kante unabhängig zu behandeln.
3. Effizientes Training: Die Integration eines konvexen physikalischen Löser in ein tiefes neuronales Netz mittels impliziter Differentiation, was eine stabile und skalierbare Optimierung ermöglicht.
4. Interpretierbarkeit: Die Basisvektoren entsprechen physikalisch interpretierbaren Flussverteilungen, und die Attention-Gewichte zeigen, welche dieser Verteilungen für die Rekonstruktion relevant sind.

4. Ergebnisse

Die Methode wurde auf drei realen Datensätzen evaluiert:

• Verkehr: Straßennetz des Los Angeles County (gerichtet).
• Stromnetz: Kontinentaleuropäisches Übertragungsnetz (PyPSA-Eur, ungerichtet).
• Fahrrad: Citi Bike Mikromobilitätsnetz (ungerichtet).

Vergleich: FLOWSYMM wurde gegen neun Baselines getestet, darunter reine physikalische Methoden, reine Daten-getriebene Modelle (MLP, GCN, GIN, EGNN) und hybride Ansätze (inklusive des aktuellen State-of-the-Art „Bil-GCN").

Ergebnisse:

• Genauigkeit: FLOWSYMM übertrifft den State-of-the-Art (Bil-GCN) konsistent in allen Metriken (RMSE, MAE, Korrelation).
  • RMSE-Reduktion: ca. 8 % (Verkehr), 10 % (Strom), 9 % (Fahrrad).
  • MAE-Reduktion: bis zu 16 %.
• Physikalische Konsistenz: Das Modell erzielt die niedrigsten Divergenz-Residuen, was bedeutet, dass es die Erhaltungsgesetze strikter einhält als andere Methoden, ohne die Genauigkeit zu opfern.
• Ablationsstudie: Die Entfernung der Gruppenaktions-Basis oder der Attention-Mechanismus führt zu signifikanten Genauigkeitsverlusten, was die Notwendigkeit beider Komponenten bestätigt.

5. Bedeutung und Ausblick

FLOWSYMM demonstriert, dass die Kombination von gelernter Graph-Aufmerksamkeit mit explizit konstruierten, physikbasierten Symmetrieräumen zu überlegenen Ergebnissen bei inversen Problemen in Netzwerken führt. Der Ansatz ist besonders wertvoll, da er:

• Robustheit gegenüber Sensorrauschen bietet.
• Interpretierbarkeit durch die Nutzung physikalischer Basisvektoren gewährleistet.
• Skalierbarkeit durch die Verwendung von impliziter Differentiation und die Möglichkeit, iterative Löser zu nutzen, ermöglicht.

Zukünftige Arbeiten könnten die Methode auf zeitliche Dynamiken (rekurrente Architekturen) erweitern oder die Schätzung der Knoteninjektionen $c$ selbst mit einbeziehen, falls diese unsicher sind. Die Architektur ist modular und könnte auf andere lineare Erhaltungsprobleme (z. B. Diffusionsprozesse oder epidemiologische Modelle) übertragen werden.