Discovering Latent Network Structure in Point Process Data

Scott W. Linderman; Ryan P. Adams

Source-linked AI summary

Discovering Latent Network Structure in Point Process Data

Scott W. Linderman, Ryan P. Adams

arXiv:1402.0914v1Feb 4, 2014stat.MLcs.LG

TL;DR

The paper studies networks that cannot be observed directly and must be inferred from noisy event observations. It combines mutually exciting point processes with random graph models and uses Poisson superposition for Bayesian parallel inference. On synthetic networks and market data, the model identifies sparse interactions and improves predictive performance over simpler baselines, while inference with unknown process identities remains sequentially constrained.

Problem
The paper addresses latent networks whose vertices or edges are not directly observed and whose structure must be inferred from noisy event emissions.
Method
The paper combines Hawkes point processes with exchangeable random graph priors and uses Poisson superposition for auxiliary-variable Bayesian inference with parallelism.
Results
The network Hawkes model accurately identifies sparse synthetic interactions, outperforms competitors on 9 of 10 networks, and improves predictive log likelihood by 2.2 ± .1 bits/spike over a homogeneous Poisson process.
Takeaways & Limitations
The model supports interpretable latent interaction analysis in financial markets and social-violence data from event observations.
Takeaways & Limitations
When process identities are unknown, process-identity sampling must be sequential, limiting the dataset sizes the method can handle.

Abstract

from arXiv · show

Networks play a central role in modern data analysis, enabling us to reason about systems by studying the relationships between their parts. Most often in network analysis, the edges are given. However, in many systems it is difficult or impossible to measure the network directly. Examples of latent networks include economic interactions linking financial instruments and patterns of reciprocity in gang violence. In these cases, we are limited to noisy observations of events associated with each node. To enable analysis of these implicit networks, we develop a probabilistic model that combines mutually-exciting point processes with random graph models. We show how the Poisson superposition principle enables an elegant auxiliary variable formulation and a fully-Bayesian, parallel inference algorithm. We evaluate this new model empirically on several datasets.

1. Introduction.

The paper addresses latent networks whose structure must be inferred from noisy event emissions rather than observed directly. It combines mutually interacting point processes with exchangeable random graph priors to model and infer these structures.

Latent networks contain vertices or edges that are unobserved, with noisy emissions generated by dynamics respecting the underlying network.
Financial trades provide a setting where interactions between related stocks must be disentangled from market-wide fluctuations.
Gang violence provides a setting where both gang identities and inter-gang edges may be latent, while spatial information can inform vertex identities.
The model combines Hawkes processes with exchangeable random graph priors to represent latent networks through their regulation of interactions.
Poisson superposition enables an auxiliary-variable formulation that supports Markov chain Monte Carlo inference and efficient parallelism.

2. Preliminaries.

The preliminaries introduce Poisson and Hawkes point processes, Poisson superposition, and exchangeable random graph models. These components provide the event-interaction and latent-network foundations for the paper’s model.

2.1. Poisson Processes: A Poisson process generates a finite set of events on a compact space from a nonnegative intensity function, with independent counts on disjoint subsets.
2.1. Poisson Processes: Poisson superposition decomposes events from summed intensities into independent component processes by assigning each event a latent origin.
2.2. Hawkes Processes: Hawkes processes extend Poisson processes by making each process intensity depend on the history of earlier events.
2.2. Hawkes Processes: Hawkes interactions add nonnegative, causal, local impulse responses to background rates across processes.
2.2. Hawkes Processes: Latent parent variables identify whether each event arose from a background rate or a preceding event, yielding a product-form augmented likelihood.
2.3. Random Graph Models: Random graph models represent network structure through distributions over adjacency or weight matrices, including exchangeable graphs invariant to node-label permutations.
2.3. Random Graph Models: A spatial random graph model makes connection probability decrease with distance between node locations, controlled by sparsity and distance-scale parameters.
2.3. Random Graph Models: The paper uses the generality of the Aldous-Hoover framework to build flexible Hawkes interaction networks.

3. The Network Hawkes Model.

The network Hawkes model separates latent network sparsity, interaction strength, temporal dynamics, and shared background fluctuations within a mutually interacting point-process framework. Bayesian inference uses parent assignments and parallelizable Gibbs updates to infer these components.

3. The Network Hawkes Model.: The impulse response factorization separates binary network structure, nonnegative interaction weights, and normalized temporal dynamics.A encodes sparsity, W interaction strength, and g a compactly supported probability density over interaction delays.
3. The Network Hawkes Model.: A spike-and-slab prior expresses separate beliefs about network sparsity and interaction strength while recovering independent processes or standard Hawkes processes as limiting graph cases.The empty graph gives independent background processes, whereas the complete graph gives the standard Hawkes process.
3. The Network Hawkes Model.: Shared background fluctuations are modeled with a sparse Log Gaussian Cox process rather than attributing all coordinated activity to process-to-process interactions.The covariance kernel is shared across processes, while offsets and scaling factors capture process-specific baseline intensity and sensitivity.
3. The Network Hawkes Model.: When process identities are unknown, spatial Gaussian mixtures, clustering models, or nonparametric models can infer the identities.The paper discusses these alternatives for gang incidents and community-level observations.
3.1. Inference with Gibbs Sampling.: Gibbs sampling jointly infers weights, adjacency, temporal parameters, background rates, identities, and event-parent assignments.Parent variables simplify updates by enabling conjugate priors for several parameter blocks; adjacency columns can be sampled in parallel and the implementation uses GPUs.
3.1. Inference with Gibbs Sampling.: Unknown process identities must be sampled sequentially because they are not conditionally independent, limiting dataset size despite GPU throughput above 4 full iterations per second on thousands of events.This is the paper's explicit computational boundary for identity inference.

4. Stability of Network Hawkes Processes.

The paper uses random matrix theory to set graph sparsity so mutually excitatory Hawkes systems remain stable with high probability. Theoretical eigenvalue approximations are compared with empirical spectra across graph sizes and weight distributions.

4. Stability of Network Hawkes Processes.: Stability is controlled by the largest eigenvalue of the effective interaction matrix, with weak priors placed on network parameters for finite datasets.The generative prior is instead tuned to place little mass on unstable networks.
4. Stability of Network Hawkes Processes.: For noncentral random matrices, the largest eigenvalue is asymptotically distributed as λmax ∼ N(µK, σ^2), while remaining eigenvalues fill a complex disk.The decomposition treats the random matrix as a rank-one mean component plus a zero-mean random perturbation.
4. Stability of Network Hawkes Processes.: For gamma weights and Erdős-Rényi adjacency, sparsity ρ can be tuned for high-probability stability using the resulting mean and variance.The relevant mean and variance depend on ρ and the gamma parameters α and β.
4. Stability of Network Hawkes Processes.: The empirical eigenvalue experiment generates 10^4 random matrices for each weight distribution at K = 4, 64, and 1024 using theoretically maximal stable ρ.Theoretical and empirical maximum-eigenvalue distributions are then compared across these settings.

5. Synthetic Results.

Synthetic experiments test latent-link recovery and held-out event prediction. The network Hawkes model generally outperforms standard Hawkes, GLM, cross-correlation thresholding, and a homogeneous Poisson baseline.

5. Synthetic Results.: The link-prediction experiment evaluates posterior interaction probabilities against standard Hawkes, GLM, and cross-correlation thresholding.The network Hawkes model uses the posterior probability of each adjacency entry to form ROC curves.
5. Synthetic Results.: The synthetic evaluation averages link-prediction and predictive-likelihood comparisons across ten randomly sampled networks of 30 nodes each.Figure 3 reports both ROC-based link recovery and predictive log likelihood normalized as bits per spike.
5. Synthetic Results.: The network Hawkes model accurately identifies sparse interactions and outperforms all other models on ten synthetic 30-node networks.The networks use Erdős-Rényi graph models and constant background rates.
5. Synthetic Results.: On held-out event prediction, the network Hawkes model outperforms competitors on 9 of 10 networks and improves predictive log likelihood by 2.2 ± .1 bits/spike over a homogeneous Poisson process.The standard Hawkes model and GLM provide 60% and 72%, respectively, of this predictive power on average.

6. Trades on the S&P 100.

The financial analysis models daily market-wide variation with short-term excitation to predict trades and infer interpretable stock interactions. Network Hawkes performs close to standard Hawkes while revealing sector structure and stable excitation patterns.

Modeling trading activity: Daily trading-volume variation is modeled with a periodic LGCP background, while short-term interactions are sought within 60 seconds.The background captures shared intraday fluctuations rather than process-to-process interactions.
Predictive evaluation: The models compare independent LGCPs, standard Hawkes processes, and network Hawkes processes with two graph priors using four training days and one test day.Figure 4 evaluates predictive performance relative to a homogeneous Poisson baseline.
Predictive evaluation: Network Hawkes is slightly outperformed by standard Hawkes, but the difference is small relative to the improvement from modeling interactions.The inferred network parameters also provide interpretable insight into market structure.
Inferred market structure: The latent distance model places nearby stocks more likely to interact, with energy and financial stocks tending to cluster while consumer stocks are broadly distributed.The embedding is two-dimensional and represents a posterior sample for ρ = 0.2 and τ = 1.
Stability and excitation: All four displayed network eigenvalues are below 1, indicating stability; the largest is λmax = 0.74 and the fourth is λ4 = 0.34.AAPL, JPM, and XOM have large entries in the leading eigenvector, while WAG and CVS dominate the fourth.

7. Gangs of Chicago.

The Chicago analysis infers clustered homicide interactions from community-labeled events while accounting for spatial identity and temporal background variation. Clustering improves prediction, and the best result uses four clusters with an Erdős-Rényi interaction graph.

Data and evaluation: The dataset contains 1,637 gang-related homicides across Chicago’s 77 communities from 1980 through 1995.Training uses 1980–1993 and testing uses 1994–1995.
Data and evaluation: The analysis compares community and clustered process identities with independent LGCPs, complete Hawkes interactions, Erdős-Rényi graphs, and latent distance graphs.The number of clusters is selected by cross-validation.
Community versus clustered models: Community-level identities improve prediction by accounting for higher homicide rates in South and West Chicago, whereas unrestricted community interactions overfit the data.There are 772 potential interactions, and sparse graph priors bias estimates toward unsupported stronger interactions.
Community versus clustered models: Clustering improves predictive performance for every graph model, with the highest predictive log likelihood from a four-cluster Erdős-Rényi model with interactions.Distance-dependent priors do not improve prediction, but more data is needed to determine why.
Interpreting inferred clusters: The inferred clusters are interpreted as safe suburbs, buffer neighborhoods, and gang territories, with self-excitation in the blue cluster suggesting bursts during turf wars.The interpretation is supported by reports of a 1990–1991 burst of street-gang violence in West Englewood.
Temporal intensity patterns: Homicide rates increase between 1989 and 1995 and show pronounced summer peaks, modeled using quadratic and periodic LGCP kernels.The quadratic component captures the long-term trend, while the periodic component captures seasonality.

8. Related Work.

The paper situates its fully Bayesian latent-network Hawkes framework among approaches combining Hawkes processes with graph priors, alternative inference methods, and competing point-process models. It distinguishes its broader random-network prior framework from prior specialized or optimization-based methods.

Hawkes processes and graph priors: Prior work combined Hawkes processes with specific graph models, including the Infinite Relational Model, to cluster processes and discover interactions.The paper identifies Blundell et al. as a special-case predecessor using an exchangeable graph model.
Applications and competing models: Gang-incident work modeled process identities with a spatial Gaussian mixture model but did not explore structured network priors.This contrasts spatial identity modeling with the paper’s use of network structure for latent interactions.
Inference and network structure: Other Hawkes-process approaches used stochastic EM, low-rank optimization, or partial likelihood rather than the paper’s fully Bayesian random-network framework.The cited alternatives include methods without network priors, low-rank network discovery, and estimators for homophily and other network effects.
Inference and network structure: The paper generalizes related structural-network inference by incorporating recent random-network models into a fully Bayesian approach.This positions the contribution as an extension of partial-likelihood inference toward broader random-network priors.
Applications and competing models: For purely excitatory interactions, Hawkes processes outperform generalized linear models in link- and event-prediction tests.GLMs additionally permit inhibitory interactions, whereas the cited comparison concerns purely excitatory data.
Paper contribution: The framework supports arbitrary Aldous-Hoover graph priors, Log Gaussian Cox Process background rates, unobserved process identities, and parallel fully Bayesian inference.The conclusion also reports uncertainty quantification for latent networks and interpretable results across synthetic and real-world problems.

9. Conclusion.

The appendix introduces a joint likelihood using auxiliary parent variables and records the authors’ acknowledgements and fellowship support.

Acknowledgements: The authors acknowledge Leslie Valiant for valuable discussions.The acknowledgement appears alongside funding information.
Acknowledgements: SWL received support from a National Defense Science and Engineering Graduate Fellowship.The passage names the fellowship as the source of support.
Derivation: The joint likelihood is formed by combining Equations 1 and 2 of the main text with auxiliary parent variables.The passage introduces the resulting likelihood without displaying its full expression here.
Derivation: The section’s derivation links the main-text model equations to an augmented likelihood formulation.This is the stated purpose of combining the two equations.

A.1. Derivation of conjugate prior updates.

The appendix derives conditional updates for model parameters under auxiliary-variable augmentation, including conjugate gamma updates and sparse-grid Gaussian-process background-rate sampling. It also describes prior choices for interaction and graph parameters.

Likelihood decomposition: The augmented likelihood separates background-process likelihood from likelihoods of processes induced by preceding spikes.This decomposition follows the auxiliary parent-variable formulation.
Weight updates: Weight updates depend only on impulse responses whose source and target process identities match the corresponding weight.The derivation isolates W_k,k′ through events assigned to processes k and k′.
Weight updates: When an adjacency entry is active, the weight update uses a truncated event history that ignores spikes after T − ∆tmax.The resulting expression is stated to be approximately proportional under this condition.
Conjugate updates: A gamma prior on an interaction weight yields a gamma conditional distribution, while an absent edge leaves the conditional equal to its prior.The latter behavior follows when A_k,k′ = 0.
Conjugate updates: Analogous conjugate updates apply to constant background rates and impulse-response parameters.The appendix states that these updates are given in the main text.
Background-rate sampling: Sparse-grid Log Gaussian Cox Process sampling and linear interpolation model shared background fluctuations without allowing them to obscure short-timescale interactions.The grid uses M + 1 equally spaced points, with the rate interpolated at each event time.
Background-rate sampling: The equally spaced grid enables trapezoid quadrature, while Elliptical Slice Sampling draws the conditional distribution of the latent vector y.These are the numerical procedures specified for the background-rate calculation.
Prior and hyperparameter choices: Kernel periods are set to one day for S&P100 data and one year for Chicago gang data, reflecting known daily and seasonal trends.Scale and offset priors are chosen so observed training-data event-count extremes fall within two standard deviations of expected LGCP values.

APPENDIX B: SYNTHETIC TEST DETAILS

Synthetic experiments compare network Hawkes models with cross-correlation and GLM alternatives using event prediction and interaction recovery. The reported results favor network Hawkes models on nearly all synthetic networks, with one outlier exception.

Synthetic data and evaluation: Synthetic networks generated T = 1000s of events, averaging 25,732 ± 9,425 spikes per network.Network 6 was an outlier with 44,973 events.
Synthetic data and evaluation: Event prediction trains on the first 900 seconds and tests on the final 100 seconds, using posterior probabilities from the last 500 of 2500 MCMC iterations.The posterior quantities evaluated are A and W.
Comparison methods: Cross-correlation of binned event times provides a simple directed excitatory-interaction measure for threshold-based link prediction.The measure sums cross-correlation over lags from zero through the maximum interaction lag.
Comparison methods: The GLM models event counts as Poisson variables whose means depend on covariates and other events, and it permits inhibitory interactions unlike Hawkes processes.Impulse responses are represented with basis functions and inferred parameters.
Comparison methods: The GLM uses six principal-component impulse-response bases, time-homogeneous background activity, and an L1 penalty selected by cross-validation.The penalty promotes sparsity in GLM parameters.
Synthetic results: On all but network 6, network Hawkes has higher predictive log likelihood than the standard Hawkes model and GLM.Network 6 is the only synthetic network where the GLM outperformed network Hawkes on event prediction.
Synthetic results: 59.2% and 71.6%: standard Hawkes and GLM achieve these fractions of network Hawkes’ average predictive power, respectively.The comparison is based on average predictive performance across sampled synthetic networks.
Financial-data setup: S&P100 trades are grouped by stock and price-change direction, restricted to regular trading hours, with short-term interactions targeted.The dataset covers one-second intervals during September 28–October 2, 2009.

APPENDIX D: GANGS OF CHICAGO MODEL DETAILS

The Chicago gang-model analysis selects cluster counts by cross-validation and compares graph priors on predictive likelihoods. It also identifies a spatial-process baseline failure caused by distributing intensity across all of R2 rather than concentrating it on observed communities.

Data split: The first 12 years train the models, 1993 is used for cross-validation, and the remaining two years test predictive power.The analysis also considered a Chicago crime dataset, but it lacks gang-related incident labels.
Inference: 700 Markov-chain iterations are run, with the final 200 used to compute predictive likelihoods and expectations.For the spatiotemporal data, intensity is factorized into spatial and temporal components.
Model selection: Cross-validation selects K = 15, 4, and 4 clusters for the empty, complete, and Erdős-Rényi graph priors, respectively.These results are reported for the clustered process identity model and four graph models.
Model selection: The latent distance model performs best with K = 5 clusters.Its prior favors spatially localized clusters.
Baseline comparison: The spatial GMM process identity model fails because it spreads spatial intensity over all of R2 instead of concentrating it on communities containing the data.Figure 11 reports this model’s prediction-task results; the latent-distance combination with spatial GMM was not tested.