Network Estimation from Point Process Data

Benjamin Mark, Garvesh Raskutti, Rebecca Willett

Introduction

In diverse fields such as neuroscience, criminology, and social media analysis, researchers frequently encounter "point process" data—sequences of discrete events occurring over time. A central challenge in analyzing these sequences is inferring the underlying "influence network": the hidden structure that dictates how an event at one node (e.g., a neuron firing or a crime occurring) alters the probability of future events at other nodes.

While the Self-Exciting Point Process (SEPP) has long been the standard tool for this task, it suffers from two significant drawbacks. First, standard SEPPs are prone to mathematical instability; stimulatory interactions can cause event counts to "blow up" toward infinity, rendering the model unusable for long-term forecasting. Second, the high dimensionality of modern networks—where $M$ nodes result in $M^2$ potential connections—often exceeds the available observation time, leading to overfitting or computational failure. This paper introduces a "saturated" SEPP framework that addresses these hurdles through a novel clipping mechanism and regularized estimation techniques.

The Saturated SEPP Framework

The authors propose a Saturated SEPP model designed to ensure stability regardless of the strength of stimulatory interactions. The core innovation is a "clipping" function: if the number of events within a specific time window exceeds a predefined threshold $\tilde{U}$, the model treats the count as $\tilde{U}$.

This simple yet effective modification prevents the exponential feedback loops that typically lead to model explosion. Unlike previous approaches that maintained stability by assuming only inhibitory interactions or limiting the model to short-term memory, the Saturated SEPP allows for a rich mix of stimulatory and inhibitory influences across long time horizons while providing the first theoretical guarantees for high-dimensional estimation in such settings.

High-Dimensional Network Estimation

To navigate the $M^2$ parameter space inherent in large networks, the researchers employ Regularized Maximum Likelihood Estimation (RMLE). They demonstrate that the framework is compatible with three primary types of "decomposable regularizers," each reflecting a different structural hypothesis about real-world networks:

  • Element-wise Sparsity ($l_1$): This assumes that most nodes in the network do not influence one another, resulting in a sparse connection matrix.
  • Group Sparsity (Group Lasso): This models networks dominated by "hubs," where a small subset of nodes exerts a broad influence over many others.
  • Low-Rank (Nuclear Norm): This assumes the network's global behavior is driven by a small number of latent factors or shared underlying processes.

The paper provides rigorous mathematical proofs showing that these estimators achieve mean-squared error (MSE) bounds that match the minimax optimal rates found in simpler, independent data settings. Essentially, the error scales linearly with the complexity of the network (its sparsity $s$ or rank $r$) and inversely with the total observation time $T$.

Empirical Validation and Key Insights

The methodology was validated across three distinct real-world domains, demonstrating both its versatility and its ability to uncover hidden structures:

  1. Chicago Crime Data: By analyzing burglary events across 77 community areas, the model successfully recovered the "geometry of influence." Using spectral clustering on the learned network, the authors found that the model grouped neighborhoods into geographically sensible clusters without being provided any spatial or map data.
  2. Rat Spike Train Data: The model analyzed the firing patterns of 51 neurons during different states of consciousness. It successfully differentiated between the neural maps of a rat while awake versus asleep, revealing that connections are significantly stronger and more excitatory during wakefulness.
  3. Memetracker Data: In tracking the spread of information across 198 news sites, the multivariate Saturated SEPP significantly outperformed univariate models, proving that accounting for cross-node influence is essential for accurate event prediction.

The Stability-Information Tradeoff

A critical insight from the study is the "phase transition" associated with the clipping threshold. While clipping ensures stability, a threshold that is too low can cause the system to spend too much time in a "saturated" state. In this state, the data loses its nuance, making the underlying network significantly harder to learn. Furthermore, the authors show that long-range memory (modeled via ARMA components) increases the difficulty of estimation, a factor explicitly accounted for in their theoretical bounds.

Limitations and Future Directions

While the framework represents a significant step forward, the authors identify several areas for future work. The model currently operates in discrete time; while this can approximate continuous-time Hawkes processes, the choice of time-bin size remains a sensitive parameter that requires careful tuning. Additionally, for low-rank models, a technical assumption regarding "row sparsity" was required for the proofs, and it remains unclear if this is a fundamental requirement of the model or a limitation of the current proof technique. Finally, while the framework can be generalized to handle unknown background event rates, the current presentation assumes these rates are known or easily estimated.

Summary updated

Abstract

Consider observing a collection of discrete events within a network that reflect how network nodes influence one another. Such data are common in spike trains recorded from biological neural networks, interactions within a social network, and a variety of other settings. Data of this form may be modeled as self-exciting point processes, in which the likelihood of future events depends on the past events. This paper addresses the problem of estimating self-excitation parameters and inferring the underlying functional network structure from self-exciting point process data. Past work in this area was limited by strong assumptions which are addressed by the novel approach here. Specifically, in this paper we (1) incorporate saturation in a point process model which both ensures stability and models non-linear thresholding effects; (2) impose general low-dimensional structural assumptions that include sparsity, group sparsity and low-rankness that allows bounds to be developed in the high-dimensional setting; and (3) incorporate long-range memory effects through moving average and higher-order auto-regressive components. Using our general framework, we provide a number of novel theoretical guarantees for high-dimensional self-exciting point processes that reflect the role played by the underlying network structure and long-term memory. We also provide simulations and real data examples to support our methodology and main results.
BibTeX
@article{mark2018network,
  author = {Benjamin Mark and Garvesh Raskutti and Rebecca Willett},
  title = {{Network Estimation from Point Process Data}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  doi = {10.1109/tit.2018.2875766},
}
Figure