On Observation Time for Recovering Latent Hawkes Networks

Enunciato del Problema
Il lavoro affronta il problema statistico fondamentale di inferire la rete di interazioni latente di un processo di Hawkes multivariato da osservazioni basate su eventi. Nello specifico, esamina la relazione di scala tra il tempo di osservazione richiesto $T$ e il numero di entità interagenti (nodi) $d$ necessario per ottenere il recupero esatto del supporto della matrice di interazione $\Theta$. Gli autori si concentrano su un regime in cui la rete è sparsa (ogni nodo ha al più $k \ll d$ genitori) e le interazioni sono deboli, un contesto rilevante per fenomeni quali le repliche sismiche, il trading ad alta frequenza, i treni di potenziali d'azione neuronali e la diffusione epidemica.

Metodologia
Gli autori stabiliscono un quadro teorico utilizzando un processo di Hawkes esponenziale a $d$ dimensioni con un tasso di decadimento $\beta$ noto. La matrice di interazione è modellata come $\Theta = \alpha B$, dove $B$ è una matrice non negativa sparsa con elementi limitati, e $\alpha$ controlla la forza di accoppiamento. L'analisi assume una finestra di osservazione stazionaria $[0, T]$ e tratta lo stato iniziale $X(0)$ come osservabile (un'ipotesi standard di inizializzazione).

Per derivare i risultati, il lavoro impiega due distinti approcci metodologici:

1. Limite Superiore (Realizzabilità): Gli autori costruiscono un stimatore a due stadi per recuperare la rete.

   • Fase di Screening: Lo stimatore utilizza dati sugli eventi ritagliati e binnizzati per calcolare punteggi di covarianza empirica tra i nodi genitori candidati e i futuri eventi del nodo target. Questa fase riduce i $d$ potenziali genitori a un insieme candidato di dimensione $m \geq k$, assicurando che il vero supporto sia contenuto in questo insieme (screening sicuro).
   • Fase di Rifinitura: Viene eseguita una regressione dei minimi quadrati ordinari (OLS) locale sull'insieme candidato selezionato. I coefficienti stimati vengono sottoposti a soglia per distinguere i veri collegamenti dalle correlazioni spurie causate da cascate di eccitazione indirette.
   • Analisi: La dimostrazione si basa sulla rappresentazione a cluster di Poisson dei processi di Hawkes per derivare limiti di concentrazione per le medie di blocchi dipendenti utilizzate nello stimatore. Ciò permette agli autori di mostrare che le statistiche empiriche si concentrano attorno ai loro valori teorici con alta probabilità.

2. Limite Inferiore (Impossibilità): Gli autori dimostrano che la scala logaritmica è ottimale stabilendo un limite inferiore di teoria dell'informazione.

   • Limitano il problema a una specifica sottoclasse di reti in cui solo un nodo target ha $k$ genitori sconosciuti, mentre tutti gli altri nodi sono indipendenti.
   • Utilizzando la disuguaglianza di Fano, relazionano la probabilità di errore di qualsiasi stimatore con l'informazione reciproca tra il supporto sconosciuto e le osservazioni.
   • L'informazione reciproca è limitata utilizzando la divergenza di Kullback–Leibler (KL) tra la legge del processo osservato sotto un supporto specifico e una legge di riferimento senza interazioni. Questo calcolo utilizza la formula di Girsanov di Jacod per i processi puntuali per gestire il cambiamento di misura.

Risultati Chiave
Il lavoro dimostra che per una classe di processi di Hawkes stazionari con interazioni sparse e deboli, il tempo di osservazione $T$ richiesto per il recupero esatto della rete scala come:
$$T \asymp \log d$$
Nello specifico:

• Teorema 3.1 (Limite Superiore): Esiste uno stimatore a due stadi tale che, se $T \geq C^* \log d$, la probabilità di recupero esatto del supporto è almeno $1 - d^{-c^*}$. Lo stimatore ha successo separando i veri genitori dai non genitori tramite un "divario di screening" nei punteggi teorici, che viene preservato sotto ritaglio e binnizzazione.
• Teorema 4.1 (Limite Inferiore): Per qualsiasi stimatore, se $T \leq c \log d$ (per una costante $c$ sufficientemente piccola), la probabilità di errore è limitata da un valore diverso da zero. Ciò implica che nessun algoritmo, indipendentemente dal costo computazionale, può ottenere un recupero esatto con alta probabilità in un tempo sub-logaritmico.

Significato e Affermazioni
Il lavoro afferma di fornire il primo risultato teorico che caratterizza la complessità del campione (in termini di tempo) per il recupero esatto della rete nei processi di Hawkes. Gli autori sottolineano che la dipendenza logaritmica da $d$ è intrinseca al problema, guidata dal costo combinatorio di identificare un insieme di genitori sparsi tra $d$ candidati.

I fattori chiave che abilitano questo risultato includono:

• La rappresentazione dello stato Markoviano fornita dal kernel esponenziale, che semplifica la dinamica dell'intensità.
• La linearità dell'intensità rispetto alla variabile di stato.
• La condizione di interazione debole, che garantisce che le cascate di eccitazione indirette non sovrastino il segnale proveniente dai genitori diretti, permettendo una separazione tra collegamenti veri e falsi.
• La stazionarietà, che fornisce un controllo uniforme sulla distribuzione sulla finestra di osservazione.

Gli autori notano che, sebbene il lavoro empirico abbia da tempo utilizzato i processi di Hawkes per l'inferenza di reti, questo lavoro pone tale successo su una base teorica, dimostrando che grandi dimensioni della rete non proibiscono intrinsecamente il recupero esatto, a condizione che la finestra di osservazione scala logaritmicamente con la dimensione. Il lavoro conclude suggerendo direzioni future, come l'estensione della teoria a interazioni con segno o inibitorie, tassi di decadimento sconosciuti e reti strutturate spazialmente, ma non afferma che queste estensioni siano attualmente risolte.