Symbolic Higher-Order Analysis of Multivariate Time Series

This paper introduces a method that transforms multivariate time series into symbolic sequences to identify statistically significant higher-order dependencies via a Bayesian approach, modeling these motifs as hyperedges in a hypergraph to reveal meaningful interactions in complex systems like neural and social networks.

The Gist

Imagine you are trying to understand the secret language of a bustling city. You have a list of events: a bus arriving, a coffee shop opening, a siren wailing, and a stock market ticker flashing. If you just look at two things at a time (e.g., "Does the bus arrival cause the coffee shop to open?"), you might miss the bigger picture. Maybe the bus, the coffee shop, and the siren all happen together because a parade is passing by. That's a group event, not just a pair of events.

This paper introduces a new "detective tool" to find these hidden group patterns in complex data, whether it's neurons firing in a brain, stocks moving in a market, or people sending emails.

Here is the breakdown of their method using simple analogies:

1. The Problem: The "Pairwise" Trap

Traditionally, scientists look at complex systems like a dating app. They ask: "Do Person A and Person B like each other?" They draw a line between them if they do.

• The Flaw: This misses the "group chat." Sometimes, Person A, Person B, and Person C only act together when all three are in the room. If you only look at pairs, you miss the magic of the trio.
• The Reality: In the real world (brains, economies, social networks), things often happen in groups, not just pairs.

2. The Solution: Turning Data into a "String of Beads"

The authors' method turns messy, complex data into a simple string of symbols, like a necklace of colored beads.

• The Setup: Imagine you are watching a busy train station.
  • A red bead = A train arrives.
  • A blue bead = A bus arrives.
  • A green bead = A taxi arrives.
  • A white bead = Nothing happens (a pause).
• The Process: They watch the station and write down the beads in the order they happen. If a red bead (train) is followed quickly by a blue bead (bus), they put them right next to each other: Red-Blue. If there's a long wait, they insert a white bead: Red-White-Blue.
• The Result: They now have a long sentence made of beads, like: Red-Blue-Green-White-Red-Red-Green...

3. The Detective Work: Finding the "Secret Codes"

Now, the computer looks for repeating patterns in this bead necklace.

• It asks: "Does the pattern Red-Blue-Green happen more often than we would expect by pure luck?"
• The "Luck" Check: If Red happens 10% of the time, Blue 10%, and Green 10%, then seeing them all together should happen 0.1% of the time if they were random.
• The Bayesian Magic: The authors use a smart statistical trick (Bayesian statistics) to say: "Okay, we know Red and Blue often go together. But does adding Green make it a special group, or is Green just tagging along randomly?"
• The Verdict: If the pattern Red-Blue-Green happens way more often than the math predicts, the computer flags it as a "Motif" (a secret code). It's a "hyper-edge"—a connection that links three things together, not just two.

4. Real-World Examples: What Did They Find?

The team tested this on three very different "cities":

• The Brain (Neurons):

  • The Micro View: When they looked at individual neurons, they found mostly pairs working together.
  • The Macro View: When they looked at whole areas of the brain, they found huge groups of neurons firing in sync.
  • The Takeaway: The brain doesn't just work in pairs; it works in massive, coordinated teams, especially when looking at the big picture.

• The Stock Market:

  • They watched 24 different companies.
  • They found that banks (like JPMorgan, Bank of America, Citigroup) tend to move together as a tight-knit trio.
  • They also found a funny pattern with one stock (DOW): When it went up, it was statistically likely to go down right after. It's like a pendulum that swings too far and corrects itself immediately.

• Emails (Enron Company):

  • They tracked who emailed whom.
  • Instead of just seeing who emailed whom, they found "triangles" of communication.
  • The analysis correctly identified the most important people in the company (the bosses) as the ones sitting at the center of these communication triangles.

5. Why This Matters

Think of this method as upgrading from a black-and-white photo to a 3D hologram.

• Old methods gave us a flat map of who is connected to whom.
• This new method gives us a 3D model of who is connected to whom in groups.

It's powerful because it doesn't need to know the "rules" of the system beforehand. It just looks at the data, turns it into beads, finds the repeating secret codes, and tells us where the real teamwork is happening. Whether it's a brain solving a problem, a market reacting to news, or a company running a project, this tool helps us see the invisible groups that hold the system together.

Technical Summary

Here is a detailed technical summary of the paper "Symbolic Higher-Order Analysis of Multivariate Time Series" by Civilini, de Vico Fallani, and Latora.

1. Problem Statement

The central problem addressed is the identification of higher-order (HO) dependencies in complex systems from empirical multivariate time series data.

• Limitations of Current Methods: Traditional network analysis relies on pairwise (2-body) interactions, which often oversimplify complex systems where units interact in groups (e.g., neurons firing in synchrony, stocks moving together). Existing HO reconstruction methods are often restricted by assumptions such as:
  • Continuous and differentiable time series.
  • Specific statistical distributions (e.g., Gaussian).
  • Prior knowledge of the underlying dynamical equations.
• The Gap: Many real-world systems (neural spiking, seismic events, social media activity, financial trades) are best described as discrete, binary, or non-differentiable events. There is a lack of scalable, assumption-free methods to detect HO correlations in such discrete data without requiring surrogate data generation (which is computationally expensive).

2. Methodology

The authors propose a general, scalable framework that combines symbolic dynamics, Bayesian statistics, and hypergraph theory. The method operates in three main stages:

A. Symbolic Transformation

1. Input: A multivariate time series of $N$ binary signals $x_i(t) \in \{0, 1\}$, where $1$ indicates an event.
2. Mapping: The time series is converted into a single ordered symbolic sequence $S$.
   • An alphabet $\mathcal{A}$ of $N+1$ symbols is defined: $N$ symbols representing the specific units (events) and one special "space" symbol.
   • If event $i$ occurs at time $t$ and event $j$ occurs within a time window $\Delta t$, their corresponding symbols are placed adjacently in $S$.
   • If no event occurs within $\Delta t$, the "space" symbol is inserted.
3. Tuple Extraction: From sequence $S$, the method extracts all overlapping $l$-tuples (sequences of $l$ symbols), forming multisets $D_l$ (with repetitions) and sets $T_l$ (unique tuples).

B. Statistical Significance via Bayesian Inference

To distinguish true HO motifs from random coincidences, the authors use a Bayesian approach rather than simple frequency counting.

1. Null Model Construction: The expected probability $p_{exp}(s)$ of an $l$-tuple $s$ is calculated based on the observed probabilities of shorter $(l-1)$ and $(l-2)$ tuples. This accounts for lower-order correlations.
   • For $l=2$: $p_{exp}(s_1, s_2) = p_{obs}(s_1)p_{obs}(s_2)$.
   • For $l>2$: Recursive formulas are used to normalize against lower-order dependencies.
2. Prior and Posterior:
   • Prior ($\Pi$): A Dirichlet distribution is used as the conjugate prior for the multinomial likelihood of tuple occurrences. The concentration parameters $\alpha$ are derived empirically from the expected counts ($n_{exp}$) plus a regularization parameter $\epsilon$.
   • Likelihood: The observed counts $n_{obs}$ follow a multinomial distribution.
   • Posterior ($P$): Updated via Bayes' theorem, resulting in a new Dirichlet distribution with parameters $\alpha + n_{obs}$.
3. Scoring (BJS-score): The significance of a tuple is measured by the Jensen-Shannon (JS) distance between the marginal distributions of the prior and the posterior.
   • If $d_{JS}$ is large, the null hypothesis (that the tuple's probability can be explained by lower-order correlations) is rejected.
   • The tuple is deemed a statistically significant motif (an $l$-hyperedge).
   • A weight is assigned to the hyperedge based on the JS distance (only if the posterior mean is higher than the prior mean).

C. Hypergraph Representation

The significant motifs are modeled as hyperedges in a hypergraph $H(N, E)$.

• Nodes: Represent the system units (e.g., neurons, stocks).
• Hyperedges: Represent groups of $l$ units ($l \ge 2$) that exhibit statistically significant higher-order correlations.

3. Key Contributions

• Assumption-Free Framework: The method does not require assumptions about the underlying dynamics (continuous/differentiable) or data distribution (Gaussian), making it applicable to binary/discrete event data.
• Scalability: Unlike surrogate data methods (e.g., random shuffling) which are computationally intensive, this method scales linearly with sequence length, analyzing only observed tuples.
• Robustness to Noise: The Bayesian approach effectively handles noise and rank-frequency distributions (e.g., Zipf's law), outperforming standard $z$-score methods.
• Unified Metric: Introduction of the BJS-score (Bayesian-Jensen-Shannon), which provides a probabilistic measure of significance that naturally incorporates lower-order dependencies.

4. Results

A. Synthetic Benchmarking

• Performance: Tested on artificial sequences with tunable noise levels ($r_{ns}$) and rank-frequency distributions ($\gamma$).
• Comparison: The BJS-score significantly outperformed the standard $z$-score in Precision-Recall and ROC curves, particularly for 3-motifs where the $z$-score produced many false positives.
• Thresholding: An optimal BJS threshold was identified in the range $[0.5, 0.7]$. The authors adopted 0.6 for real-world applications.
• Robustness: The method maintained high performance even with extreme noise-to-signal ratios ($r_{ns} = 100$).

B. Real-World Applications

1. Neural Activity (Mouse Brain):
   • Micro-scale (Single Neurons): Detected HO motifs, but pairwise interactions dominated.
   • Macro-scale (Functional Areas): When aggregating neurons by functional area, 3-motifs exceeded pairwise interactions (70% of hyperedges were 3-motifs). This suggests that higher-order dynamics are crucial at the level of brain regions, not just individual neurons.
2. Financial Markets (Stock Prices):
   • Analyzed 24 stocks across 8 sectors (1994–2024).
   • Unsigned Changes: ~76% of pairwise motifs involved stocks in the same sector.
   • 3-Motifs: Identified highly significant groups: (BAC, C, JPM) for banking and (COP, CVX, XOM) for energy.
   • Signed Changes: Revealed that most correlations are within the same direction (all up or all down). A unique exception was found for stock DOW, where a positive move is statistically linked to a subsequent negative correction (and vice versa).
3. Social Systems (Email Exchanges):
   • Analyzed the Enron email dataset.
   • Despite few 3-motifs, centrality analysis of the resulting hypergraph successfully identified key organizational figures (VPs, COOs) as the most central nodes, validating the method's ability to capture structural importance.

5. Significance and Conclusion

This paper introduces a powerful tool for higher-order network reconstruction from discrete time series. By moving beyond pairwise correlations, the method reveals hidden group dynamics in complex systems that are invisible to traditional network analysis.

• Theoretical Impact: It bridges symbolic dynamics, Bayesian inference, and hypergraph theory to solve a fundamental problem in complex systems science.
• Practical Impact: The method is broadly applicable to neuroscience (understanding brain function), finance (detecting market sector correlations), and sociology (analyzing group behavior), offering a scalable way to model complex interactions without restrictive dynamical assumptions.
• Future Outlook: The authors suggest that the spatial effect observed in brain data (increase in HO motifs at macro-scales) warrants further investigation, and the method's applicability to continuous signals via thresholding opens new avenues for diverse data types.