Stochastic Event Prediction via Temporal Motif Transitions

Deze paper introduceert STEP, een raamwerk dat temporele linkpredictie hervormt als een sequentiële voorspellingsopdracht in continue tijd door gebeurtenisdynamiek te modelleren via Poisson-processen over temporele motieven, wat leidt tot aanzienlijk betere prestaties en lagere rekentijd dan bestaande methoden.

De kern

Stel je voor dat je een enorme, levende stad bent waar mensen elkaar elke seconde een bericht sturen, handtekeningen zetten of foto's delen. Deze stad verandert continu: nieuwe wegen worden aangelegd, oude wegen worden verlaten, en sommige straten zijn altijd drukker dan andere.

De vraag is: Wat gaat er als volgende gebeuren? Wie gaat wie een bericht sturen en op welk moment?

Dit is precies het probleem dat het onderzoekspapier "STEP" (Stochastic Event Predictor) probeert op te lossen. Hier is een uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. Het oude probleem: Het verkeersagentje dat gokt

Vroeger probeerden computers dit te voorspellen door te kijken naar het verleden en te gokken: "Zal er morgen een weg zijn tussen A en B?"

• Het probleem: Ze maakten dit tot een simpel "Ja/Nee"-spel. Ze gaven de computer duizenden voorbeelden van "Ja" (er is een weg) en "Nee" (er is geen weg). Maar in het echte leven zijn er bijna oneindig veel wegen die niet bestaan. Door te gissen op "Nee", leerden de computers vaak alleen maar dat "niets gebeuren" de normaalste zaak is. Ze keken ook niet goed naar de volgorde van dingen. Het was alsof je probeert de volgende zin in een verhaal te raden door alleen te kijken naar woordenlijsten, zonder te luisteren naar de zinnen die ervoor kwamen.

2. De nieuwe oplossing: STEP, de slimme regisseur

De auteurs van dit papier hebben een nieuw systeem bedacht, genaamd STEP. Ze kijken niet naar statische kaarten, maar naar de stroom van gebeurtenissen.

Stel je STEP voor als een slimme regisseur in een theaterstuk die de volgende scène voorspelt. Deze regisseur heeft twee slimme hulpmiddelen:

A. De "Ritme-Regel" (Poisson-processen)

In de stad is er een ritme. Soms sturen mensen snel achter elkaar berichten (een drukke ochtend), en soms is het rustig.

• De analogie: STEP luistert naar het ritme van de stad. Hij weet: "Als iemand om 10:00 uur een bericht stuurde, is de kans groot dat de volgende om 10:05 komt, maar niet om 10:00:01." Hij gebruikt wiskunde om te schatten wanneer de volgende gebeurtenis waarschijnlijk plaatsvindt, net zoals je kunt voorspellen wanneer de bus komt op basis van het verkeer.

B. De "Blokjes-Builder" (Temporele Motieven)

Dit is het meest creatieve deel. STEP kijkt niet alleen naar twee mensen die praten, maar naar patronen.

• De analogie: Stel je voor dat interacties als LEGO-blokjes zijn.
  • Als A naar B praat, en B naar C, en C terug naar A, is dat een specifiek patroon (een "motief").
  • STEP onthoudt deze patronen. Hij ziet: "Oh, elke keer als dit specifieke blokje-patroon wordt afgerond, begint er vaak een nieuw blokje-patroon dat lijkt op een vierkant."
  • In plaats van te raden, bouwt STEP een open lijst van patronen die "half af" zijn. Hij wacht tot het juiste moment om die lijst af te maken.

3. Hoe werkt het in de praktijk?

Het systeem doet twee dingen tegelijk:

1. Starten of Doorgaan?
   Op elk moment vraagt STEP zichzelf af: "Moet ik een nieuwe keten van gebeurtenissen starten (een 'koude' start), of moet ik een bestaande keten afmaken (een 'hete' start)?"

   • Vergelijking: Is het tijd om een nieuw gesprek te beginnen met een vreemde, of moet ik doorgaan met het gesprek dat ik al met mijn vriend voer?

2. De Slimme Gok
   Als hij besluit een patroon af te maken, kiest hij de meest waarschijnlijke volgende stap. Hij gebruikt een soort "wiskundige intuïtie" (Bayesiaanse score) die kijkt naar:

   • Hoe vaak gebeurt dit patroon al?
   • Hoe lang duurt het meestal tussen deze stappen?
   • Wie zijn de mensen die hierbij betrokken zijn?

4. Waarom is dit zo goed?

De onderzoekers hebben STEP getest op vijf echte datasets (zoals e-mails van een universiteit, Facebook-berichten en Wikipedia-bewerkingen).

• Resultaat: STEP was veel beter dan de beste bestaande methoden. In sommige gevallen was hij 21% nauwkeuriger.
• Snelheid: Omdat STEP geen zware neurale netwerken (die veel rekenkracht nodig hebben) gebruikt, maar slimme statistische regels, is hij veel sneller en lichter. Hij kan zelfs op enorme netwerken werken zonder vast te lopen.
• Flexibiliteit: Je kunt STEP ook gebruiken als een "extra laag" voor andere slimme systemen. Het is alsof je een slimme kompas toevoegt aan een bestaande auto; de auto rijdt al goed, maar met het kompas vindt hij de weg nog sneller.

Samenvatting in één zin

In plaats van te gokken of er morgen een weg is tussen twee punten, kijkt STEP naar het ritme van de stad en de patronen in de gesprekken, en voorspelt hij precies wie, wat en wanneer als volgende gaat gebeuren, alsof hij de toekomst van een levend organisme leest.

Het is een stap van "raden" naar "voorspellen op basis van ritme en patroon".

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Stochastic Event Prediction via Temporal Motif Transitions" in het Nederlands.

Probleemstelling

Temporale netwerken, bestaande uit tijdstempelgedragen interacties (zoals in sociale media, financiële systemen en biologische paden), vereisen voorspellingsmodellen die zowel de evoluerende topologie als de strikte temporale volgorde van gebeurtenissen respecteren. Bestaande methoden voor temporale linkpredictie (temporal link prediction) kampen met twee fundamentele beperkingen:

1. Verkeerde probleemformulering: De meeste methoden behandelen het probleem als een binaire classificatie (zal een link ontstaan of niet?) met negatieve bemonstering. Dit negeert de sequentiële en gecorreleerde aard van real-world interacties en introduceert vertekende evaluatiemetrics door het opnemen van onrealistische "negatieve" voorbeelden.
2. Schalings- en expressiviteitsproblemen:
   • Punt-procesmodellen (zoals Hawkes-processen) behouden de tijdsorde maar worden computationeel onhandelbaar bij grote grafen door de noodzaak om intensiteiten voor alle mogelijke knopparen te berekenen.
   • Temporale Graph Neural Networks (TGNNs) leren dynamische embeddings maar zijn vaak gebonden aan classificatiedoelstellingen, vereisen zware geheugenvoorraden, en zijn gevoelig voor hyperparameter-tuning. Ze modelleren niet direct hoe toekomstige interacties in continue tijd worden gegenereerd.

Methodologie: STEP Framework

De auteurs introduceren STEP (STochastic Event Predictor), een raamwerk dat temporale linkpredictie herformuleert als een sequentiële voorspellingsprobleem in continue tijd. In plaats van een classifier te trainen, modelleert STEP de evolutie van het netwerk als een generatief proces.

Kernconcepten:

• Temporale Motieven: STEP gebruikt "temporale motieven" (herhalende patronen van interacties binnen een tijdsvenster) als fundamentele bouwstenen. Een motief is een subgraaf waarbij opeenvolgende gebeurtenissen structureel verbonden zijn.
• Motief-Transities: Het model observeert hoe een bestaand motief overgaat in een nieuw motief door een nieuwe gebeurtenis. Dit wordt gemodelleerd als een Poisson-proces.
• Open Motieven: Het systeem onderhoudt een dynamische set van "open motieven" (deels voltooide motiefinstanties die nog kunnen worden uitgebreid).

Het Voorspellingsproces:
Op elk tijdstip $\tau$ voert STEP de volgende stappen uit:

1. Tijdsvoortgang: Er wordt een wachttijd $\Delta\tau$ getrokken uit een exponentiële verdeling met een globale intensiteit $\lambda_{global}$ om het tijdstip van de volgende gebeurtenis te bepalen.
2. Beslissing (Bernoulli-proef): Het model beslist of de volgende gebeurtenis een koud event is (start van een nieuw motief) of een heet event (uitbreiding van een bestaand open motief). De kans op een koud event ($p_{cold}$) is gebaseerd op historische data.
3. Selectie via Bayesiaanse Score:
   • Bij een koud event: Er wordt een nieuwe rand $(u, v)$ geselecteerd die de hoogste Bayesiaanse posterior-score heeft, gebaseerd op de waarschijnlijkheid van de wachttijd en de empirische prior van die rand.
   • Bij een heet event: Het model evalueert alle geldige uitbreidingen van open motieven. De score combineert de waarschijnlijkheid van de wachttijd (Poisson) en de prior van de transitie tussen motieftypen ($P(m \to m')$).
4. Generatie: De gebeurtenis met de hoogste score wordt gegenereerd en het setje open motieven wordt geüpdatet.

Feature Vectors:
STEP genereert ook compacte, probabilistische feature-vectors gebaseerd op motieftransities. Deze kunnen worden geconcateneerd met de output van bestaande TGNNs (zoals TGN of GraphMixer) om hun representaties te verrijken zonder de architectuur van het neurale netwerk te wijzigen.

Belangrijkste Bijdragen

1. Herformulering van het probleem: De shift van binaire classificatie naar sequentiële voorspelling, wat negatieve bemonstering overbodig maakt en beter aansluit bij realistische scenario's (zoals notificatieplanning).
2. Lichtgewicht Generatief Model: Een model dat Poisson-aankomsten combineert met Bayesiaanse scoring over motieftransities, wat voorspelling mogelijk maakt zonder zware training van neurale netwerken.
3. Complementaire Feature Vectors: Het introduceren van tijdsbewuste, structuur-gebaseerde feature vectors die TGNNs kunnen versterken.
4. Efficiënte Implementatie: Een C++-implementatie die via inter-process communicatie werkt met Python-TGNNs, wat lage latentie mogelijk maakt voor grafen met tot 7 miljoen gebeurtenissen.

Resultaten

De auteurs hebben STEP getest op vijf real-world datasets (CollegeMsg, Email-Eu, FBWall, SMS-A, Wiki-Talk).

• Sequentiële Voorspelling:

  • STEP bereikte een precisie van 0,99 bij het voorspellen van de volgende $k$ opeenvolgende gebeurtenissen op bepaalde datasets.
  • De precisie bleef stabiel en hoog (rond 0,8-0,9) voor voorspellingen tot $k=100$ op de meeste datasets.
  • De prestaties hangen samen met de "Repeated Event Ratio" (RER) en entropie: datasets met veel herhalende interacties (zoals Email-Eu) worden zeer nauwkeurig voorspeld.

• Classificatie (Binaire Link Predictie):

  • Wanneer STEP-feature vectors worden toegevoegd aan TGNN-baselines (TGN en GraphMixer), resulteerde dit in aanzienlijke verbeteringen in Average Precision (AP).
  • De grootste winst was 21,23% op de CollegeMsg dataset voor TGN.
  • STEP presteerde consistent beter dan de state-of-the-art motief-bewuste baseline TempME, die vaak uitviel door geheugenbeperkingen (OOM) op grote datasets.

• Efficiëntie:

  • STEP is aanzienlijk sneller dan TGNNs en TempME. De runtime per voorspelling varieerde van enkele milliseconden tot enkele seconden, zelfs voor de grootste dataset (Wiki-Talk).
  • In tegenstelling tot TempME, die faalde op grote datasets, schaalt STEP goed.

Significantie en Conclusie

Het artikel toont aan dat het modelleren van temporale dynamiek via stochastische motieftransities een krachtig alternatief is voor diepe neurale netwerken.

• Interpreteerbaarheid: Het model is transparant; voorspellingen zijn gebaseerd op expliciete waarschijnlijkheidsmodellen van tijdsintervallen en structurele patronen.
• Scalabiliteit: Door te werken met lokale motieven en Poisson-processen in plaats van globale intensiteiten of zware attention-mechanismen, is STEP schaalbaar naar zeer grote netwerken.
• Complementariteit: De methode bewijst dat klassieke probabilistische modellen (Poisson + Bayes), wanneer gecombineerd met moderne deep learning embeddings, de state-of-the-art kunnen verbeteren zonder de complexiteit van het trainen van nieuwe neurale architecturen.

De belangrijkste beperkingen zijn de afhankelijkheid van reeds bestaande knopparen (moeilijk om volledig nieuwe knopparen te voorspellen) en de gevoeligheid voor concept-drift als de motiefpatronen in de tijd sterk veranderen. Desalniettemin biedt STEP een robuust en efficiënt kader voor temporale voorspelling.