Granger Causality Networks for Categorical Time Series

Alex Tank, Emily B. Fox, Ali ShojaiearXiv 2017 · DOI · arXiv

Abstract

We present a new framework for learning Granger causality networks for multivariate categorical time series, based on the mixture transition distribution (MTD) model. Traditionally, MTD is plagued by a nonconvex objective, non-identifiability, and presence of many local optima. To circumvent these problems, we recast inference in the MTD as a convex problem. The new formulation facilitates the application of MTD to high-dimensional multivariate time series. As a baseline, we also formulate a multi-output logistic autoregressive model (mLTD), which while a straightforward extension of autoregressive Bernoulli generalized linear models, has not been previously applied to the analysis of multivariate categorial time series. We develop novel identifiability conditions of the MTD model and compare them to those for mLTD. We further devise novel and efficient optimization algorithm for the MTD based on the new convex formulation, and compare the MTD and mLTD in both simulated and real data experiments. Our approach simultaneously provides a comparison of methods for network inference in categorical time series and opens the door to modern, regularized inference with the MTD model.

Introduction

Granger causality is a cornerstone of time-series analysis, used to determine if the past values of one variable help predict the future of another. While well-established for continuous, Gaussian data, it is significantly more challenging to apply to categorical data, such as "on/off" states, musical notes, or health records.

The Mixture Transition Distribution (MTD) model is an elegant and interpretable approach for categorical data, but it has historically been difficult to use. It suffered from non-convexity, where algorithms frequently became trapped in local optima, and non-identifiability, where multiple parameter settings yielded the same result. These issues, combined with poor scaling, previously limited researchers to analyzing only a handful of variables at a time.

Methodology

This research introduces a framework that transforms MTD inference into a convex problem through a novel re-parameterization. By redefining the transition probabilities as $Z^j = \gamma_j P^j$, where $\gamma_j$ are mixture weights and $P^j$ are transition matrices, the authors convert a non-convex likelihood into a convex one. This guarantees that any local optimum found is a global optimum.

Decomposition of the MTD model into a weighted sum of transition matrices.

Identifiability and Optimization

To ensure model uniqueness, the authors established new identifiability conditions. These conditions are enforced using convex penalties (such as the Lasso) during optimization. This approach allows for the discovery of sparse Granger causality networks in high-dimensional settings.

Comparison of sparsity and identifiability constraints for MTD and mLTD models.

For efficient scaling, the authors developed a projected gradient algorithm using Dykstra’s splitting method. This allows the model to scale nearly linearly with the number of time series, a significant improvement over standard quadratic programming solvers. Additionally, the authors formalize a multi-output logistic transition distribution (mLTD) as a baseline for comparison.

Experimental Results

The framework was evaluated using both synthetic and real-world data:

  • Synthetic Data: Tested across scenarios including Sparse MTD and Sparse mLTD to assess performance under model misspecification.
  • Bach Choral Harmony: Using a dataset of 60 chorales, the MTD model successfully recovered the "circle of fifths"—a fundamental music theory structure—directly from raw categorical data.

The MTD model demonstrated superior interpretability compared to the mLTD baseline. While mLTD parameters are obscured by a non-linear softmax link, MTD parameters represent additive increases in probability, making the resulting causality graphs more intuitive. Furthermore, the Dykstra-based solver achieved orders-of-magnitude speedups, processing 70 time series in milliseconds.

Conclusion

By recasting the MTD model as a convex optimization problem, this work enables the efficient discovery of Granger causality in high-dimensional categorical time series. The approach provides a robust, interpretable alternative to logistic-based models. Future research will focus on establishing formal consistency rates for these estimators and extending the framework to higher-order Markov chains.

Summary updated

Abstract

We present a new framework for learning Granger causality networks for multivariate categorical time series, based on the mixture transition distribution (MTD) model. Traditionally, MTD is plagued by a nonconvex objective, non-identifiability, and presence of many local optima. To circumvent these problems, we recast inference in the MTD as a convex problem. The new formulation facilitates the application of MTD to high-dimensional multivariate time series. As a baseline, we also formulate a multi-output logistic autoregressive model (mLTD), which while a straightforward extension of autoregressive Bernoulli generalized linear models, has not been previously applied to the analysis of multivariate categorial time series. We develop novel identifiability conditions of the MTD model and compare them to those for mLTD. We further devise novel and efficient optimization algorithm for the MTD based on the new convex formulation, and compare the MTD and mLTD in both simulated and real data experiments. Our approach simultaneously provides a comparison of methods for network inference in categorical time series and opens the door to modern, regularized inference with the MTD model.
BibTeX
@misc{tank2017granger,
  author = {Alex Tank and Emily B. Fox and Ali Shojaie},
  title = {{Granger Causality Networks for Categorical Time Series}},
  year = {2017},
  eprint = {1706.02781},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.02781},
}
Figure