📊 statistics

On Observation Time for Recovering Latent Hawkes Networks

This paper establishes that for sparse, weakly interacting stationary Hawkes processes, an observation time of order $\log d$ is both necessary and sufficient to exactly recover the underlying latent network among $d$ entities, achieved through a novel two-stage estimator and a lower bound derived from Fano's inequality and Jacod's Girsanov formula.

Original authors: Jonas Linkerhägner, Michele Bortolasi, Lorenzo Baldassari, Maarten V. de Hoop, Ivan Dokmanić

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jonas Linkerhägner, Michele Bortolasi, Lorenzo Baldassari, Maarten V. de Hoop, Ivan Dokmanić

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out who is texting whom in a massive, chaotic group chat with thousands of people. You can't see the phone screens or read the messages directly. All you can see is a log of when people sent messages.

Your goal is to reconstruct the hidden "friendship map" (the network) that explains who influences whom. If Person A sends a message, does it make Person B more likely to send one a second later?

This paper tackles a very specific version of this mystery using a mathematical model called a Hawkes Process. Think of this model as a way to describe "contagious" events: an earthquake triggers aftershocks, a stock market crash triggers more panic selling, or a viral tweet triggers a cascade of retweets.

Here is the core question the authors ask: How long do you have to watch this group chat to be 100% sure you've figured out the entire friendship map?

The Big Discovery: Time vs. Size

The authors prove a surprising and elegant rule: The time you need to watch doesn't have to grow huge just because the group gets bigger.

If you have 10 people, you need a certain amount of time to figure out the map.
If you have 1,000 people, you don't need 100 times more time. You only need a little bit more.
If you have 1,000,000 people, you still only need a tiny bit more time than for 1,000.

Mathematically, they prove that the required observation time grows logarithmically with the number of people. In plain English: Time $\approx$ Logarithm of the Network Size.

Think of it like this: If you are looking for a specific needle in a haystack, and the haystack gets 10 times bigger, you might think you need 10 times more time to search. But if you have a magic metal detector (the right mathematical tools), you only need a little extra time because the "needle" (the signal) becomes easier to distinguish as the system scales, provided the connections are weak and sparse.

How They Solved It (The Two-Stage Detective Work)

The paper doesn't just say "it's possible"; they build a specific method to do it. They call it a two-stage estimator.

Stage 1: The "Screening" (The Rough Draft)
Imagine you have a list of 1,000 suspects. You can't interview all of them deeply right away. So, you do a quick scan.

You look at the moments just before a person sends a message.
You ask: "Who else was active right before this?"
You keep the top 10 people who seem most likely to be the cause and throw the other 990 away.
The Trick: The authors show that even if you clip the data (ignore extremely loud messages) and bin it (look at time in chunks), this quick scan is smart enough to keep the real culprits in the list. It's like a sieve that catches the gold but lets the sand fall through.

Stage 2: The "Refinement" (The Deep Dive)
Now you only have 10 suspects left. You can afford to do a deep, detailed analysis on just these 10.

You run a precise statistical test (Least Squares) on this small group.
You check the numbers to see exactly who influenced whom.
Because the group is so small, you can be mathematically certain about the result.

Why Is This Hard?

The authors point out that this is harder than it looks because of "Indirect Echoes."

Imagine Person A texts Person B, and Person B texts Person C.

Direct Link: A $\to$ B.
Direct Link: B $\to$ C.
The Illusion: A also seems to influence C, even though they never spoke directly. A's message caused B to act, which caused C to act.

In a noisy, busy network, these "echoes" can trick you into thinking A and C are friends when they aren't. The authors prove that if the interactions are weak (people don't get too crazy excited by one message) and sparse (everyone only talks to a few people), you can separate the real direct friends from the fake indirect ones.

The "Impossible" Limit

The paper also proves the other side of the coin: You cannot do it faster.

They used a mathematical tool called Fano's Inequality (think of it as a "minimum information" rule) to show that if you stop watching the group chat too early, the data simply doesn't contain enough clues. No matter how smart your computer or how fancy your algorithm is, if you haven't watched long enough, the different possible friendship maps look statistically identical. You are guessing in the dark.

The Bottom Line

This paper provides a theoretical "speed limit" for network recovery.

Good News: You don't need to watch a massive network for years to understand it. A relatively short observation window (scaling with the log of the size) is enough.
Bad News: If you try to do it in less time than that, it is mathematically impossible to be right.

The authors used this logic on things like earthquake aftershocks, stock market trades, and brain neuron spikes, showing that for these systems, the "time to learn" is surprisingly efficient, growing very slowly as the system gets larger.

Problem Statement
The paper addresses the fundamental statistical problem of inferring the latent interaction network of a multivariate Hawkes process from event-based observations. Specifically, it investigates the scaling relationship between the required observation time $T$ and the number of interacting entities (nodes) $d$ necessary to achieve exact support recovery of the interaction matrix $\Theta$ . The authors focus on a regime where the network is sparse (each node has at most $k \ll d$ parents) and interactions are weak, a setting relevant to phenomena such as seismic aftershocks, high-frequency trading, neuronal spike trains, and epidemic spreading.

Methodology
The authors establish a theoretical framework using a $d$ -dimensional exponential Hawkes process with a known decay rate $\beta$ . The interaction matrix is modeled as $\Theta = \alpha B$ , where $B$ is a sparse non-negative matrix with bounded entries, and $\alpha$ controls the coupling strength. The analysis assumes a stationary observation window $[0, T]$ and treats the initial state $X(0)$ as observable (a standard initialization assumption).

To derive the results, the paper employs two distinct methodological approaches:

Upper Bound (Achievability): The authors construct a two-stage estimator to recover the network.
- Screening Stage: The estimator uses clipped and binned event data to compute empirical covariance scores between candidate parent nodes and the target node's future events. This stage filters the $d$ potential parents down to a candidate set of size $m \geq k$ , ensuring the true support is contained within this set (sure screening).
- Refinement Stage: A local ordinary least-squares (OLS) regression is performed on the screened candidate set. The estimated coefficients are thresholded to distinguish true edges from spurious correlations caused by indirect excitation cascades.
- Analysis: The proof relies on the Poisson cluster representation of Hawkes processes to derive concentration bounds for the dependent block averages used in the estimator. This allows the authors to show that the empirical statistics concentrate around their theoretical values with high probability.
Lower Bound (Impossibility): The authors prove that the logarithmic scaling is optimal by establishing an information-theoretic lower bound.
- They restrict the problem to a specific subclass of networks where only one target node has $k$ unknown parents, while all other nodes are independent.
- Using Fano's inequality, they relate the error probability of any estimator to the mutual information between the unknown support and the observations.
- The mutual information is bounded using the Kullback–Leibler (KL) divergence between the law of the observed process under a specific support and a reference law with no interactions. This calculation utilizes Jacod's Girsanov formula for point processes to handle the change of measure.

Key Results
The paper proves that for a class of stationary Hawkes processes with sparse, weak interactions, the observation time $T$ required for exact network recovery scales as:
$T \asymp \log d$
Specifically:

Theorem 3.1 (Upper Bound): There exists a two-stage estimator such that if $T \geq C^* \log d$ , the probability of exact support recovery is at least $1 - d^{-c^*}$ . The estimator succeeds by separating true parents from non-parents via a "screening gap" in the theoretical scores, which is preserved under clipping and binning.
Theorem 4.1 (Lower Bound): For any estimator, if $T \leq c \log d$ (for a sufficiently small constant $c$ ), the probability of error is bounded away from zero. This implies that no algorithm, regardless of computational cost, can achieve exact recovery with high probability in sub-logarithmic time.

Significance and Claims
The paper claims to provide the first theoretical result characterizing the sample complexity (in terms of time) for exact network recovery in Hawkes processes. The authors emphasize that the logarithmic dependence on $d$ is intrinsic to the problem, driven by the combinatorial cost of identifying a sparse parent set among $d$ candidates.

Key factors enabling this result include:

The Markov state representation provided by the exponential kernel, which simplifies the intensity dynamics.
The linearity of the intensity with respect to the state variable.
The weak interaction condition, which ensures that indirect excitation cascades do not overwhelm the signal from direct parents, allowing for a separation between true and false edges.
Stationarity, which provides uniform distributional control over the observation window.

The authors note that while empirical work has long utilized Hawkes processes for network inference, this work places such success on a theoretical basis, demonstrating that large network sizes do not inherently prohibit exact recovery provided the observation window scales logarithmically with the dimension. The paper concludes by suggesting future directions, such as extending the theory to signed or inhibitory interactions, unknown decay rates, and spatially structured networks, but does not claim these extensions are currently solved.

The Big Discovery: Time vs. Size

How They Solved It (The Two-Stage Detective Work)

Why Is This Hard?

The "Impossible" Limit

The Bottom Line

More like this