PaperlayerView exact revision on arXiv

Source-linked AI summary

Causal Discovery in Hawkes Processes by Minimum Description Length

Amirkasra Jalaldoust, Katerina Hlavackova-Schindler, Claudia Plant

arXiv:2206.06124v1cs.LGmath.STstat.TH

TL;DR

The paper asks how to discover Granger-causal networks in multidimensional Hawkes processes, especially when short sequences make existing methods prone to overfitting. It applies minimum description length with Monte Carlo estimation, and reports stronger synthetic short-sequence discovery than baselines as well as a more plausible graph on G-7 bonds data.

  • Problem

    Existing graph-discovery methods can overfit short event sequences, defined as horizons at most order 100·p for p dimensions, while applying MDL to Hawkes processes is challenging.

    Source: §1 · p. 1

  • Method

    The paper develops a Monte Carlo procedure for estimating MDL objectives and applies it to Granger-causal graph inference in multidimensional Hawkes processes.

    Source: §1 · p. 1

  • Results

    MDLH shows significant superiority in causal discovery for short event sequences in synthetic experiments, and produces a more plausible causal graph than the baseline on G-7 bonds.

    Source: §1 · p. 1, §7 · p. 8

  • Takeaways & Limitations

    The experiments support MDL-based Hawkes graph discovery for short synthetic sequences and the tested G-7 bonds data.

    Source: §7 · p. 8

    The experiments do not use train/test validation and report each method's highest F1 across hyperparameters, so validated baseline F1 scores would presumably be lower.

    Source: §7.2 · p. 9

Abstract

from arXiv · show

Hawkes processes are a special class of temporal point processes which exhibit a natural notion of causality, as occurrence of events in the past may increase the probability of events in the future. Discovery of the underlying influence network among the dimensions of multi-dimensional temporal processes is of high importance in disciplines where a high-frequency data is to model, e.g. in financial data or in seismological data. This paper approaches the problem of learning Granger-causal network in multi-dimensional Hawkes processes. We formulate this problem as a model selection task in which we follow the minimum description length (MDL) principle. Moreover, we propose a general algorithm for MDL-based inference using a Monte-Carlo method and we use it for our causal discovery problem. We compare our algorithm with the state-of-the-art baseline methods on synthetic and real-world financial data. The synthetic experiments demonstrate superiority of our method incausal graph discovery compared to the baseline methods with respect to the size of the data. The results of experiments with the G-7 bonds price data are consistent with the experts knowledge.

1 Introduction

The paper targets Granger-causal graph discovery in multidimensional Hawkes processes, particularly where short event sequences can lead existing methods to overfit. It proposes an MDL-based approach with Monte Carlo estimation and reports stronger short-sequence discovery than baselines.

1 Introduction

  • The introduction motivates Hawkes processes for asynchronous, continuous-time event sequences because past events can influence current behavior.Applications mentioned include social networks, earthquakes and aftershocks, and high-frequency financial data.Source: §1 · p. 1
  • Existing variable-selection methods often overfit when the observation horizon is short, defined as at most order 100·p for a p-dimensional sequence.They usually perform well when the horizon is several orders of magnitude greater than p.Source: §1 · p. 1
  • The paper presents a general procedure for practical estimation of an MDL objective using Monte Carlo methods to estimate integrals.Source: §1 · p. 1
  • The paper constructs an MDL objective for inferring Granger-causal graphs in multidimensional Hawkes processes.The approach treats causal discovery as model selection.Source: §1 · p. 1
  • The method demonstrates significant superiority in causal discovery for short event sequences in synthetic experiments.The evaluation also includes real-world data.Source: §1 · p. 1

2 Preliminaries

The preliminaries establish notation and define temporal point processes, Hawkes-process causality, and the MDL model-selection framework used in the paper.

2.1 Notation

  • Scalar variables use regular letters, multidimensional variables bold letters, random variables capitals, matrices Greek letters, and ω_i denotes row i of ω.Vectors are column vectors.Source: §2.1 · p. 2

2.2 Temporal Point Processes

  • A temporal point process models event occurrence over an observation window and can equivalently be represented by a counting process that records events up to time t.A multidimensional process comprises coupled temporal point processes.Source: §2.2 · p. 2

Granger-Causality in Temporal Point Processes

  • In temporal point processes, events in one dimension Granger-cause another dimension when that past information improves prediction of its future events.The comparison excludes the candidate cause dimension from the history.Source: Granger-Causality in Temporal Point… · p. 2

Hawkes Processes

Granger-Causality in MHP

  • For a multidimensional Hawkes process, events in dimension j do not Granger-cause events in dimension i exactly when φ_ij is identically zero.Thus the causal structure is encoded in the kernel functions.Source: Granger-Causality in MHP · p. 2

2.3 Minimum Description Length

  • MDL selects models by balancing a code for the model or parameters against a code for the data given that model.The framework connects codes with probability distributions and accommodates codes without assumptions about the data-generating process.Source: §2.3 · pp. 2–3

Normalized Maximum Likelihood Distribution

  • Normalized maximum likelihood model selection uses a luckiness function and trades goodness-of-fit against model complexity, defined through a normalizing integral.The MDL function selects the model minimizing this trade-off.Source: Normalized Maximum Likelihood… · p. 3

3 Our Method to Estimate the MDL Function

The method estimates an MDL objective by computing its goodness-of-fit and model-complexity terms. It uses convex optimization for the MDL estimator and Monte Carlo simulation to estimate model complexity.

3 Our Method to Estimate the MDL Function

  • The proposed general procedure estimates the MDL objective by computing its goodness-of-fit and model-complexity terms for a given dataset, model, and luckiness function.The model-prior term is computable when the prior is known.Source: §3 · p. 3

3.1 Computing the Goodness-of-Fit

  • The MDL estimator is obtained by minimizing the negative log-likelihood plus negative log-luckiness over the model's restricted parameter space.Convex optimization requires convex restricted parameter spaces and a convex objective; a log-concave luckiness function makes its negative log term convex.Source: §3.1 · p. 3

3.2 Estimating Model Complexity

  • Model-complexity estimation rewrites an integral as an expectation, requiring p(s|θ = z) to be positive for every data instance and allowing any full-support parameter distribution.The estimator uses the MDL estimator for simulated data and averages Q values across joint samples.Source: §3.2 · p. 4
  • Monte Carlo samples of parameters and corresponding data yield an unbiased estimate of model complexity, with estimator variance decreasing linearly as the number of simulations increases.The estimator averages computed Q values from joint samples of X and θ.Source: §3.2 · p. 4

4 Causal Discovery in Hawkes Processes

The causal-discovery method is formulated for exponential-decay multi-dimensional Hawkes processes. In this setting, Granger-causal discovery reduces to identifying which influence coefficients are nonzero.

4 Causal Discovery in Hawkes Processes

  • For exponential-decay Hawkes processes with known decay matrix β, the parameters are baseline intensities μ and nonnegative influence coefficients α.The decay matrix has positive entries.Source: §4 · p. 4
  • In exp-MHP, an edge from dimension j to dimension i exists exactly when α_ij is nonzero, so causal discovery identifies the sparsity pattern of α.The adjacency matrix entry η_ij is one when events in dimension j Granger-cause events in dimension i.Source: §4 · p. 4
  • The paper focuses on exponential-decay kernels, while the methodology can also be used with power-law kernels or kernels defined by basis functions.The passage names power-law kernels as one example.Source: §4 · p. 4

4.1 Parameter Learning in exp-MHP

The exp-MHP parameters comprise the influence matrix and baseline intensities, and the model's likelihood is optimized separately for each dimension. The resulting parameter optimization is convex and has a unique solution.

4.1 Parameter Learning in exp-MHP

  • The exp-MHP parameters are the influence coefficient matrix α and baseline vector μ, with the parameter vector assembled from per-dimension parameters.The event data are represented as sequences of event times for each dimension.Source: §4.1 · pp. 4–5
  • The negative log-likelihood is defined with respect to the observed event sequences and the conditional intensity computed from the realization and parameter vector.The sequences record the event times in each dimension over the observation interval.Source: §4.1 · p. 5
  • The passage identifies Ozaki 1979 in connection with the exponential-MHP likelihood.Source: §4.1 · p. 5
  • For each dimension, the search space is a positive cone and the objective is convex, so a unique solution exists and efficient algorithms are available.The cited example of an efficient algorithm is Bacry, Mastromatteo, and Muzy 2015.Source: §4.1 · p. 5

4.2 Causal Discovery As Model Selection

Causal discovery is cast as selecting among Hawkes-process models indexed by binary causal graphs. For exponential-decay models, the MDL estimator can be computed through convex optimization, enabling estimation of the MDL objective for candidate graphs.

4.2 Causal Discovery As Model Selection

  • Each binary adjacency matrix defines a Hawkes-process model whose restricted parameter space contains exactly the parameter vectors matching that graph's zero pattern in α.The baseline vector μ does not influence causal discovery or the model-selection formulation.Source: §4.2 · p. 5
  • Because each α sparsity pattern determines one graph, the graph-indexed parameter spaces partition the parameter space and selecting the true model is equivalent to finding the true graph.Source: §4.2 · p. 5

MDL Objective Function for exp-MHP

  • A graph with w nonzero influence coefficients has p + w nonnegative parameters to estimate, giving a convex restricted parameter space; convex negative log-likelihood and log-concave luckiness yield a convex MDL-estimator problem.The experiments use the uninformative choice v ≡ 1; other suitable luckiness choices can penalize large baseline intensities and influence coefficients.Source: MDL Objective Function for exp-MHP · p. 5
  • Once the MDL estimator is computed, the model-complexity estimate can be used to estimate the MDL objective for any candidate causal graph.Source: MDL Objective Function for exp-MHP · p. 5

4.3 Causal Discovery Algorithm

MDLH selects a causal graph by minimizing an estimated MDL objective separately for each Hawkes-process dimension. Its search can be parallelized under independence assumptions, reduced for sparse graphs, and amortized when the problem specification is fixed.

4.3 Causal Discovery Algorithm

  • Under independent graph distributions and luckiness functions across dimensions, the MDL objective separates into p terms, allowing parallel optimization.The theorem’s conditions yield independent dimension-wise optimization problems.Source: §4.3 · p. 6
  • MDLH searches each dimension’s model space for the graph minimizing its estimated MDL objective, then combines the selected models into an adjacency matrix.By default, each model space contains all p-dimensional binary vectors.Source: §4.3 · p. 6, Computational Complexity · p. 6

Computational Complexity

  • Assuming equal computational cost per parameter-learning procedure, exhaustive search requires (N + 1)·p·2^p procedures.Each MDL estimate involves N Monte Carlo simulations and one parameter-learning procedure for the observed data.Source: Computational Complexity · p. 6

Sparse Causal Graphs

  • With at most m causes per node, where m ≪ p, restricting each model space yields O((N + 1)·p^(m+1)) parameter-learning procedures.The paper notes that computational complexity is not its contribution; its focus is methodology and discovery precision.Source: Sparse Causal Graphs · p. 6

Amortization

  • For a fixed problem specification, precomputing model complexities reduces each new query to p·2^p parameter-learning procedures, or p^(m+1) for sparse graphs.The precomputation costs N·p·2^p procedures by default, or N·p^(m+1) for sparse graphs.Source: Amortization · pp. 6–7

5 Related Work

Prior Granger-causal discovery methods for multidimensional Hawkes processes use regularized selection, penalized likelihood, or moment matching, while related MDL work had not addressed this setting.

Granger-causal discovery in MHP

  • ADM4 combines lasso and nuclear-norm regularization, Xu et al. use penalized-likelihood EM, and NPHC fits integrated second- and third-order cumulants.These methods perform well for long horizons, but can overfit when the horizon is short.Source: §5 · p. 7

MDL and related causal inference

  • Earlier MDL causal-inference work addressed i.i.d. settings or other time-series models, not Granger-causal discovery in multidimensional Hawkes processes.The cited work includes Gaussian and Poisson time-series models and models from the exponential family.Source: §5 · p. 7
  • For multidimensional i.i.d. causal inference, Mian et al. use greedy forward and backward search, whose criterion convexity is hard to ensure and whose algorithm lacks a unique-solution guarantee.This work extends earlier bivariate MDL causal-inference studies.Source: §5 · p. 7

6 Experiments and Discussion

Experiments compare MDLH with several causal-discovery and model-selection baselines on synthetic Hawkes data and G-7 bond volatility. MDLH outperforms baselines on short synthetic sequences and yields a more plausible G-7 graph than maximum likelihood.

Baseline Methods

  • The evaluation includes NPHC, ADM4, information criteria, regularized maximum likelihood, and regularized least-squares methods.For each comparison method, the authors report its best score over regularization choices and a hyperparameter grid.Source: Baseline Methods · p. 7

Data Generation Process

  • Synthetic graphs allow self-excitation in every dimension; experiments use a random-edge setting for p = 7 and graphs with at most one cause per node for p = 20.The experiments draw α entries from unif([0.1, 0.2]), μ entries from unif([0.5, 1.0]), and set β to a matrix of ones.Source: Data Generation Process · p. 7

Evaluation and Results

  • MDLH significantly outperforms all baselines on short-horizon synthetic data; on G-7 bonds, it produces a more plausible graph than ML.The reported evaluation uses F1 for synthetic graph recovery; the G-7 comparison is based on plausibility relative to expert knowledge.Source: Evaluation and Results · p. 7, Table 1 · p. 8, Results · p. 8
  • IC methods return an empty graph in all short-data cases, which the authors attribute presumably to weak short-data performance.F1 is used to evaluate directed-graph accuracy, and each setting includes 100 randomly generated processes with one sample drawn from each.Source: Evaluation and Results · pp. 7–8

G-7 Bonds

  • The G-7 analysis seeks the influence network among daily return volatilities for the United States, Germany, France, Japan, the United Kingdom, Canada, and Italy.The data cover 2003–2014.Source: G-7 Bonds · p. 8

Shock Identification

  • To convert volatility time series into events, the authors register a daily event when a value falls in the top 20% of its one-year rolling window.They report around 500 events per dimension and assume T = 400 based on the synthetic experiments.Source: Shock Identification · p. 8

Results

  • On G-7 data, MDLH’s graph agrees with cited expert knowledge that Japanese bonds neither influence nor are influenced by other G-7 countries, unlike ML’s bidirected US–Japan edge.Only MDLH and ML were tested on these data.Source: Results · p. 8

7 Conclusion

The paper presents Monte Carlo integral estimation for MDL objectives and applies it to Granger-causal graph inference in multidimensional Hawkes processes. It reports short-sequence superiority in synthetic experiments and a more plausible graph than the baseline on G-7 bonds.

7 Conclusion

  • The paper presents a general procedure for practical estimation of MDL-based objectives using Monte Carlo integral estimation.It constructs an objective for Granger-causal graph inference in multidimensional Hawkes processes.Source: §7 · p. 8
  • Figure 3 presents the causal graph inferred by MDLH for G-7 bonds.Source: Figure 3 · p. 8
  • In synthetic experiments, the method shows significant superiority in causal discovery for short event sequences.In the G-7 bond experiment, it gives a more plausible causal graph than the baseline.Source: §7 · p. 8

Appendix

The appendix describes the dimension-wise MDL computation and experimental setup, and reports small-data information-criterion behavior, baseline-selection caveats, computational costs, and a real-data baseline result.

7.1 Proof of Theorem 2

  • For each dimension, the proof procedure optimizes goodness-of-fit, estimates model complexity, and combines these in the MDL objective.Source: §7.1 · p. 9

7.2 Experimental Setup

  • Baseline graph extraction thresholds kernel norms at 0.01; comparisons test L1, L2, elastic-net, and no-penalty settings, plus ADM4 lasso-nuclear ratios.Source: §7.2 · p. 9
  • The reported baseline F1 is each method’s highest score across hyperparameters without train/test validation; validated baseline scores would presumably be lower.Source: §7.2 · p. 9
  • On small datasets, AIC, BIC, and HQ do not perform well; their roughly 1-unit edge-entry threshold cannot be met at the experiments’ 0.01 or 0.1 log-likelihood scale.Source: §7.2 · p. 9
  • The method used 1,000 MC iterations at p=7 and 500 for sparse p=20; complexity estimation took about an hour per setting, followed by 100 test runs of about ten seconds each.Source: §7.2 · p. 9
  • ML returned a bidirected US–Japan edge at every tested regularization level, which the authors say contradicts domain expertise.Source: §7.2 · p. 9
Loading 2206.06124v1…