TFWaveFormer: Temporal-Frequency Collaborative Multi-level Wavelet Transformer for Dynamic Link Prediction

Die Arbeit stellt TFWaveFormer vor, einen neuartigen Transformer, der durch die Integration von Zeit-Frequenz-Analyse und lernbarer Multi-Resolution-Wavelet-Zerlegung komplexe zeitliche Dynamiken erfasst und damit den State-of-the-Art bei der Vorhersage dynamischer Links in Graphen verbessert.

Das Wesentliche

TFWaveFormer: Ein neuer Blick auf das Chaos der Zeit

Stellen Sie sich vor, Sie versuchen, das Verhalten von Menschen in einer riesigen, sich ständig verändernden Stadt vorherzusagen. Wer wird sich morgen treffen? Wer wird eine neue Freundschaft schließen? Wer wird sich wieder streiten? Das ist im Grunde die Aufgabe der dynamischen Link-Vorhersage.

Bisherige Methoden waren wie ein Fotograf, der nur ein einziges, statisches Foto macht, oder ein Musiker, der nur eine einzige Tonhöhe hört. Sie verpassten die Nuancen: den schnellen, kurzen Moment (wie ein kurzer Gruß) und den langsamen, langfristigen Trend (wie eine jahrelange Zusammenarbeit).

Hier kommt TFWaveFormer ins Spiel. Es ist wie ein super-intelligenter Dirigent, der nicht nur die einzelnen Instrumente (die Zeit) hört, sondern auch die gesamte Symphonie (die Frequenzen) versteht.

Hier ist die Erklärung in einfachen Bildern:

1. Das Problem: Warum alte Methoden scheitern

Stellen Sie sich vor, Sie beobachten einen Fluss.

• Alte Methoden (RNNs): Sie schauen nur auf das Wasser, das gerade an Ihnen vorbeifließt. Wenn der Fluss zu schnell ist, verlieren sie den Überblick über das, was vor einer Stunde passiert ist. Sie vergessen die Vergangenheit.
• Andere Methoden (Transformer): Sie können den ganzen Fluss auf einmal sehen, aber sie hören oft nur das "Rauschen" des Wassers. Sie erkennen nicht, ob das Rauschen von einem kleinen Stein (kurze Unterbrechung) oder von einem nahenden Wasserfall (großer Trend) kommt. Sie unterscheiden nicht zwischen kurzen Wellen und langen Wellen.

2. Die Lösung: TFWaveFormer als "Wellen-Analysator"

TFWaveFormer nutzt eine Technik namens Wavelet-Transformation. Das klingt kompliziert, ist aber einfach wie ein Zoom-Objektiv für Zeit.

Stellen Sie sich vor, Sie schauen durch ein Fernglas auf eine Landschaft:

• Das Zeit-Fenster: Sie sehen genau, was jetzt passiert (z. B. zwei Personen grüßen sich).
• Das Frequenz-Fenster: Sie sehen die großen Muster im Hintergrund (z. B. dass sich diese Personen jeden Sonntag treffen).

TFWaveFormer macht beides gleichzeitig. Es zerlegt die Geschichte in verschiedene "Schichten" oder "Wellenlängen":

1. Kleine Wellen: Schnelle, kurzfristige Ereignisse (ein plötzlicher Chat).
2. Große Wellen: Langsame, langfristige Trends (eine sich entwickelnde Freundschaft).

3. Die drei genialen Tricks des Dirigenten

Trick Nr. 1: Der lernbare Wellen-Maler (Multi-Level Wavelet)
Früher mussten Computer mit festgelegten Werkzeugen arbeiten (wie ein Maler, der nur rote und blaue Farben hat). TFWaveFormer hat jedoch lernbare Pinsel.

• Die Analogie: Statt festgelegte Farben zu nutzen, mischt der Computer die Farben selbst, je nachdem, was auf der Leinwand passiert. Wenn die Daten verrauscht sind, sucht er nach feinen Details. Wenn sie ruhig sind, sucht er nach großen Mustern. Er passt sich dem Bild an, anstatt das Bild an ein starres Raster zu zwängen.

Trick Nr. 2: Der Zeit-Frequenz-Tanz (Temporal-Frequency Coordination)
Statt Zeit und Frequenz getrennt zu betrachten, lässt TFWaveFormer sie miteinander tanzen.

• Die Analogie: Stellen Sie sich einen Orchesterleiter vor, der den Geigern (Zeit) sagt: "Spielt leise, denn die Trompeten (Frequenz) haben gerade eine wichtige Melodie." Das Modell kombiniert die lokalen Details mit den globalen Mustern. Es weiß genau, wann es auf das "Jetzt" achten muss und wann es auf das "Ganze" schauen sollte.

Trick Nr. 3: Der Türsteher (Gating Mechanism)
Nicht jede Information ist gleich wichtig. Manchmal ist ein kurzer Gruß nur ein Unfall, manchmal ist er der Anfang einer großen Freundschaft.

• Die Analogie: TFWaveFormer hat einen Türsteher (ein "Gate"), der an der Tür des Gehirns steht. Er entscheidet: "Diese Information ist wichtig, lass sie rein!" oder "Das ist nur Hintergrundrauschen, blockiere es!" So wird das Modell nicht von unnötigen Details überflutet.

4. Das Ergebnis: Warum ist das besser?

In Tests auf echten Daten (wie Reddit, Wikipedia oder Flugdaten) hat TFWaveFormer alle anderen Methoden besiegt.

• Bei schnellen Veränderungen: Es erkennt sofort, wenn sich etwas ändert (wie ein plötzlicher Ausbruch in einem sozialen Netzwerk).
• Bei langfristigen Mustern: Es vergisst nicht, dass sich Dinge oft in Zyklen wiederholen (wie saisonale Trends).
• Bei neuen Szenarien: Es funktioniert auch gut, wenn es völlig neue Personen oder Ereignisse gibt, die es noch nie gesehen hat.

Zusammenfassung in einem Satz

TFWaveFormer ist wie ein All-Seeing-Eye, das nicht nur auf die Sekundenzeiger einer Uhr schaut, sondern auch den Takt der Uhr, die Jahreszeit und die Geschichte der Uhr versteht, um genau zu sagen, was als Nächstes passieren wird.

Es ist der Beweis dafür, dass man, um die Zukunft vorherzusagen, nicht nur die Vergangenheit kennen muss, sondern auch verstehen muss, wie sich die Zeit bewegt.

Technische Zusammenfassung

1. Problemstellung

Die dynamische Link-Vorhersage ist eine Kernaufgabe in der Analyse zeitlicher Graphen, die in Anwendungen wie sozialen Netzwerken, Kommunikationsprognosen und Finanzmodellierung von entscheidender Bedeutung ist. Im Gegensatz zu statischen Graphen unterliegen reale Netzwerke einer ständigen zeitlichen Evolution.

Die bestehenden Herausforderungen liegen in der Erfassung komplexer Multi-Skalen-Zeitabhängigkeiten:

• Multi-Skalen-Muster: Netzwerkdynamiken umfassen sowohl kurzfristige, abrupte Änderungen (z. B. plötzliche Interaktionen) als auch langfristige, periodische Trends (z. B. saisonale Aktivität).
• Limitationen bestehender Methoden:
  • RNNs: leiden unter dem Problem des verschwindenden Gradienten und können langfristige Abhängigkeiten schlecht modellieren.
  • Standard-Transformer (z. B. TGAT, DyGFormer): Sind oft defizitär darin, unterschiedliche Frequenzmuster in nicht-stationären Zeitintervallen zu unterscheiden.
  • Reine Frequenzmethoden: Erfassen globale Frequenzmerkmale gut, verlieren aber lokale zeitliche Details.
  • Feste Fensterlängen: Können sich nicht an variable Periodizitäten anpassen.

Das Ziel ist es, ein Modell zu entwickeln, das sowohl lokale zeitliche Dynamiken als auch globale evolutionäre Trends gleichzeitig und adaptiv erfassen kann.

2. Methodik: TFWaveFormer

Das vorgeschlagene Framework TFWaveFormer (Temporal-Frequency Collaborative Multi-level Wavelet Transformer) integriert Zeit-Frequenz-Analyse mit einer Multi-Resolution-Wavelet-Zerlegung in einer Transformer-Architektur. Der Prozess gliedert sich in drei Hauptkomponenten:

A. Feature-Extraktion und Integration

Für jeden Knoten werden historische Interaktionsmuster extrahiert, um reiche Repräsentationen zu erstellen:

• Knotenmerkmale ($H_{node}$): Inhärente Attribute.
• Kantenmerkmale ($H_{edge}$): Semantik der Interaktion.
• Zeitmerkmale ($H_{time}$): Verarbeitet durch einen Time-Encoder basierend auf Zeitstempeln.
• Interaktionsfrequenz ($H_{if}$): Topologische Beziehungen (NIF-Encoder).
  Diese Modi werden in einen gemeinsamen Raum projiziert und zu einem fusionierten Feature-Vektor $X_v$ komprimiert.

B. Multi-Level Wavelet-Zerlegung (Lernbare Wavelets)

Anstatt traditionelle, fest definierte Wavelet-Basen (z. B. Daubechies) zu verwenden, führt TFWaveFormer eine lernbare, datengesteuerte Wavelet-Zerlegung durch:

• Parallele Multi-Skalen-Faltung: Statt iterativer Zerlegung werden parallele Faltungskerne mit unterschiedlichen Größen ($k$) verwendet, um verschiedene Skalen (fein bis grob) gleichzeitig zu erfassen.
• Lernbare Filter: Die Wavelet-Filter $\Psi$ sind lernbare Parameter, die durch Optimierung des Zielfunktion adaptiv die relevantesten zeitlichen Muster aus den Daten extrahieren.
• Skalen-Attention: Ein Mechanismus gewichtet die Ausgaben der verschiedenen Skalen dynamisch, um die für die Aufgabe relevantesten Muster zu betonen.
• Gating-Mechanismus: Ein Gate-Modul (basierend auf MLP und Sigmoid) moduliert die multi-skalierten Wavelet-Features, um wichtige Merkmale zu selektieren und Rauschen zu unterdrücken. Dies ergibt die rekonstruierte Frequenzdarstellung $Z_{gated}$.

C. Temporal-Frequency Hybrid Transformer

Dieser Schritt fusioniert die zeitlichen und frequenzbasierten Merkmale:

• Positional Encoding: Wird hinzugefügt, um die zeitliche Reihenfolge zu kodieren.
• Fusion: Die zeitlichen Features (durch MLP komprimiert) und die frequenzbasierten Wavelet-Features werden addiert und normalisiert.
• Multi-Head Self-Attention (MHSA): Der Transformer nutzt den Self-Attention-Mechanismus, um die komplexen dynamischen Beziehungen zwischen Knoten und ihren Nachbarn zu modellieren. Dies ermöglicht die Kombination lokaler Wavelet-Features mit globalen zeitlichen Abhängigkeiten.

D. Vorhersage

Nach dem Training werden die Knoten-Embeddings durch Mean-Pooling aggregiert. Die Wahrscheinlichkeit einer zukünftigen Verbindung wird durch eine Sigmoid-Funktion auf der Basis des Hadamard-Produkts der Embeddings des Quell- und Zielknotens berechnet.

3. Hauptbeiträge

1. Lernbare Wavelet-Zerlegung: Ersetzung traditioneller fester Basis-Transformationen durch parallele, multi-skalierte Faltungskerne, die feinkörnige lokale und grobkörnige globale zeitliche Muster direkt aus den Daten adaptiv extrahieren.
2. Zeit-Frequenz-Koordinationsmechanismus: Eine synergistische Integration von Zeit- und Frequenzdarstellungen, die komplementäre Dynamiken erfasst – von transienten Ereignissen bis hin zu langfristigen Periodizitäten.
3. Unified Transformer-Architektur: Nahtlose Integration der Wavelet- und Co-Attention-Module in einem einzigen Framework, das neue State-of-the-Art-Ergebnisse auf zehn Benchmark-Datensätzen erzielt.

4. Ergebnisse

Das Modell wurde auf 10 realen Datensätzen (u. a. Wikipedia, Reddit, MOOC, LastFM, Enron, UN Trade) evaluiert und mit fortschrittlichen Methoden (DyRep, TGN, DyGFormer, FreeDyG, etc.) verglichen.

• Leistung: TFWaveFormer erreicht konsistent State-of-the-Art (SOTA) Ergebnisse in beiden Szenarien:
  • Transduktiv: Durchschnittliche Ränge von 1,20 (AP) und 1,40 (AUC).
  • Induktiv: Durchschnittliche Ränge von 1,70 (AP) und 1,60 (AUC).
• Vergleich: Es übertrifft die zweitbeste Methode (meist DyGFormer) signifikant. Auf sozialen Netzwerken wie Wikipedia und Reddit wurden AP-Werte von über 99,3% erreicht.
• Robustheit: Das Modell zeigt hervorragende Leistung unter schwierigen Bedingungen, einschließlich historischer und induktiver Negativ-Sampling-Strategien, was auf eine starke Generalisierungsfähigkeit hinweist.
• Effizienz: Trotz der komplexen Architektur bietet TFWaveFormer eine optimale Balance zwischen Vorhersagegenauigkeit und Trainingszeit pro Epoche.

5. Bedeutung und Fazit

TFWaveFormer adressiert eine fundamentale Lücke in der dynamischen Graph-Lernforschung: die Fähigkeit, nicht-stationäre Signale sowohl im Zeit- als auch im Frequenzbereich gleichzeitig zu modellieren.

• Innovation: Die Abkehr von festen Wavelet-Basen hin zu lernbaren, parallelen Faltungen ermöglicht eine adaptive Anpassung an die spezifischen zeitlichen Charakteristika verschiedener Netzwerke.
• Anwendbarkeit: Die Methode ist besonders effektiv für Netzwerke mit komplexen, multi-skaligen Mustern (z. B. periodische soziale Interaktionen oder abrupte Ereignisfolgen).
• Zukunft: Die Arbeit zeigt, dass die Kombination von Wavelet-Analyse und Transformer-Architekturen ein vielversprechender Weg ist, um die Grenzen der dynamischen Link-Vorhersage zu überwinden und robustere Modelle für komplexe zeitliche Systeme zu schaffen.

Die Ablationsstudien bestätigen, dass sowohl die zeitliche als auch die frequenzbasierte Komponente für die optimale Leistung unerlässlich sind, wobei die Gewichtung je nach Datendichte und Komplexität variiert.