On Observation Time for Recovering Latent Hawkes Networks

Problembeschreibung
Der Beitrag behandelt das fundamentale statistische Problem der Inferenz des latenten Interaktionsnetzwerks eines multivariaten Hawkes-Prozesses aus ereignisbasierten Beobachtungen. Konkret untersucht er den Skalierungszusammenhang zwischen der erforderlichen Beobachtungszeit $T$ und der Anzahl der interagierenden Entitäten (Knoten) $d$, die notwendig ist, um eine exakte Unterstützungswiederherstellung der Interaktionsmatrix $\Theta$ zu erreichen. Die Autoren konzentrieren sich auf einen Regime, in dem das Netzwerk spärlich ist (jeder Knoten hat höchstens $k \ll d$ Eltern) und die Interaktionen schwach sind; ein Setting, das für Phänomene wie seismische Nachbeben, Hochfrequenzhandel, neuronale Spikes und die Ausbreitung von Epidemien relevant ist.

Methodik
Die Autoren etablieren einen theoretischen Rahmen unter Verwendung eines $d$-dimensionalen exponentiellen Hawkes-Prozesses mit einer bekannten Zerfallsrate $\beta$. Die Interaktionsmatrix wird als $\Theta = \alpha B$ modelliert, wobei $B$ eine spärliche, nicht-negative Matrix mit beschränkten Einträgen ist und $\alpha$ die Kopplungsstärke steuert. Die Analyse geht von einem stationären Beobachtungsfenster $[0, T]$ aus und behandelt den Anfangszustand $X(0)$ als beobachtbar (eine Standardannahme zur Initialisierung).

Um die Ergebnisse abzuleiten, verwendet der Beitrag zwei unterschiedliche methodische Ansätze:

1. Obere Schranke (Erreichbarkeit): Die Autoren konstruieren einen zweistufigen Schätzer, um das Netzwerk wiederherzustellen.

   • Screening-Phase: Der Schätzer verwendet geklippete und gebinnte Ereignisdaten, um empirische Kovarianzwerte zwischen potenziellen Elternknoten und den zukünftigen Ereignissen des Zielknotens zu berechnen. Diese Phase filtert die $d$ potenziellen Eltern auf eine Kandidatenmenge der Größe $m \geq k$ herunter und stellt sicher, dass die wahre Unterstützung in dieser Menge enthalten ist (sicheres Screening).
   • Verfeinerungsphase: Auf der gescreenten Kandidatenmenge wird eine lokale gewöhnliche Kleinste-Quadrate-Regression (OLS) durchgeführt. Die geschätzten Koeffizienten werden thresholdiert, um wahre Kanten von zufälligen Korrelationen zu unterscheiden, die durch indirekte Erregungskaskaden verursacht werden.
   • Analyse: Der Beweis stützt sich auf die Poisson-Cluster-Darstellung von Hawkes-Prozessen, um Konzentrationsgrenzen für die abhängigen Blockmittelwerte abzuleiten, die im Schätzer verwendet werden. Dies ermöglicht den Autoren zu zeigen, dass sich die empirischen Statistiken mit hoher Wahrscheinlichkeit um ihre theoretischen Werte konzentrieren.

2. Untere Schranke (Unmöglichkeit): Die Autoren beweisen, dass die logarithmische Skalierung optimal ist, indem sie eine informationstheoretische untere Schranke etablieren.

   • Sie beschränken das Problem auf eine spezifische Unterklasse von Netzwerken, bei der nur ein Zielknoten $k$ unbekannte Eltern hat, während alle anderen Knoten unabhängig sind.
   • Unter Verwendung der Fano-Ungleichung setzen sie die Fehlerwahrscheinlichkeit jedes Schätzers in Beziehung zur gegenseitigen Information zwischen der unbekannten Unterstützung und den Beobachtungen.
   • Die gegenseitige Information wird unter Verwendung der Kullback-Leibler-Divergenz (KL-Divergenz) zwischen dem Gesetz des beobachteten Prozesses unter einer spezifischen Unterstützung und einem Referenzgesetz ohne Interaktionen abgeschätzt. Diese Berechnung nutzt die Girsanov-Formel von Jacod für Punktprozesse, um den Maßwechsel zu handhaben.

Hauptergebnisse
Der Beitrag beweist, dass für eine Klasse stationärer Hawkes-Prozesse mit spärlichen, schwachen Interaktionen die für die exakte Netzwerk-Wiederherstellung erforderliche Beobachtungszeit $T$ wie folgt skaliert:
$$T \asymp \log d$$
Konkret:

• Satz 3.1 (Obere Schranke): Es existiert ein zweistufiger Schätzer, sodass, falls $T \geq C^* \log d$, die Wahrscheinlichkeit einer exakten Unterstützungswiederherstellung mindestens $1 - d^{-c^*}$ beträgt. Der Schätzer gelingt, indem er wahre Eltern von Nicht-Eltern durch eine „Screening-Lücke" in den theoretischen Werten trennt, die unter Klippung und Binning erhalten bleibt.
• Satz 4.1 (Untere Schranke): Für jeden Schätzer ist, falls $T \leq c \log d$ (für eine hinreichend kleine Konstante $c$), die Fehlerwahrscheinlichkeit von Null weg nach unten beschränkt. Dies impliziert, dass kein Algorithmus, unabhängig von den Rechenkosten, eine exakte Wiederherstellung mit hoher Wahrscheinlichkeit in sub-logarithmischer Zeit erreichen kann.

Bedeutung und Behauptungen
Der Beitrag behauptet, das erste theoretische Ergebnis zu liefern, das die Stichprobengröße (in Bezug auf die Zeit) für die exakte Netzwerk-Wiederherstellung bei Hawkes-Prozessen charakterisiert. Die Autoren betonen, dass die logarithmische Abhängigkeit von $d$ inhärent für das Problem ist, getrieben durch die kombinatorischen Kosten der Identifizierung einer spärlichen Elternmenge unter $d$ Kandidaten.

Schlüsselfaktoren, die dieses Ergebnis ermöglichen, sind:

• Die Markov-Zustandsdarstellung, die durch den exponentiellen Kern bereitgestellt wird und die Intensitätsdynamik vereinfacht.
• Die Linearität der Intensität bezüglich der Zustandsvariable.
• Die Bedingung schwacher Interaktion, die sicherstellt, dass indirekte Erregungskaskaden das Signal von direkten Eltern nicht überlagern, was eine Trennung zwischen wahren und falschen Kanten ermöglicht.
• Die Stationarität, die eine gleichmäßige Verteilungskontrolle über das Beobachtungsfenster bietet.

Die Autoren weisen darauf hin, dass empirische Arbeiten Hawkes-Prozesse zwar seit langem für die Netzwerkinferenz nutzen, diese Arbeit jedoch solchen Erfolg auf eine theoretische Basis stellt und zeigt, dass große Netzwerkgrößen eine exakte Wiederherstellung nicht inhärent verhindern, sofern das Beobachtungsfenster logarithmisch mit der Dimension skaliert. Der Beitrag schließt mit Hinweisen auf zukünftige Richtungen, wie die Erweiterung der Theorie auf signierte oder inhibitorische Interaktionen, unbekannte Zerfallsraten und räumlich strukturierte Netzwerke, behauptet jedoch nicht, dass diese Erweiterungen derzeit gelöst sind.