PaperlayerView exact revision on arXiv

Source-linked AI summary

Uncovering higher-order interactions from memory in observed dynamics

Arthur Rondeau, Alain Barrat, Roland Bouffanais

arXiv:2610.20095v1cs.SIphysics.soc-ph

TL;DR

From node sequences alone, it is difficult to tell whether observed dynamics require group interactions or whether pairwise processes can explain them. The paper uses a hyperedge-latent HMM and model selection against pairwise baselines; synthetic tests recover hyperedges, while football possession sequences yield interpretable tactical groupings.

  • Problem

    Observed memory in node sequences can reflect higher-order interactions or pairwise path dependence, making it difficult to establish whether group structure is required.

    Source: §1 · p. 2, §2.1 · p. 3

  • Method

    A hidden Markov model represents latent states as hyperedges and is compared with pairwise baselines using out-of-sample fit and a complexity penalty.

    Source: §1 · pp. 2–3

  • Results

    Synthetic tests recover underlying hyperedges, and football possession analyses yield interpretable tactical units; the BIC-optimal number of hyperedges does not always match the announced formation.

    Source: §1 · p. 3, §3 · p. 14

  • Takeaways & Limitations

    In football possession data, inferred hyperedges can align with recognizable tactical units even when the optimal number of hyperedges differs from the announced formation.

    Source: §3 · p. 14

    The pipeline addresses only random-walk-like trajectories on a fixed hypergraph.

    Source: §3 · p. 14

Abstract

from arXiv · show

Many complex systems involve group interactions, which can readily be represented by higher-order structures such as hypergraphs. However, when observing a system's dynamical evolution, establishing whether that evolution actually results from higher-order interactions, or whether pairwise interactions suffice to explain the data, remains a challenge. Even in the simple case of a temporal sequence of nodes visited during a diffusion process, such a task is intricate. Indeed, group interactions leave their traces as memory on the observed nodes, while path dependence in a purely pairwise process can mimic that same footprint without any group structure. To resolve this, we propose an inference pipeline based on a hidden Markov model (HMM) that tests, directly from an observed sequence of nodes carrying no group labels, whether higher-order interactions are required to describe the dynamics. The HMM latent states represent higher-order interactions, seen as hyperedges of an unobserved hypergraph, so that their detection becomes a model selection problem between the HMM class and a class of null models without higher-order interactions. We first validate this approach on synthetic node sequences generated from random walks on graphs and hypergraphs, showing that it recovers both the number and the composition of the underlying hyperedges, while correctly rejecting them when the generating process is pairwise. As a second step, we consider a validation based on empirical data, namely empirical trajectories of ball possession in football matches. This application shows that the pipeline goes beyond providing statistical evidence of the presence of higher-order interactions, and yields interpretable underlying structures: the recovered hyperedges map directly onto recognizable tactical team formations.

1 Introduction

This section frames the challenge of distinguishing higher-order interactions from pairwise processes with memory, and describes an HMM approach applied to football possession data to detect predictive higher-order structure and recover interpretable tactical states.

2.2 Pipeline Overview

  • The pipeline fits an HMM whose hidden states represent hyperedges, treating observed node-level memory as a possible trace of group interactions and testing whether that structure is needed.T carries memory between latent hyperedges, S selects a hyperedge based on the current vertex, and B emits the next vertex; the process is Markovian on the augmented state space V × E.Source: §1 · p. 2, §2.2 · p. 3, §2.2.2 · pp. 4–5

2.2.1 Step I. Markovianity Test

  • A conditional-mutual-information test first checks Markovianity: Markovian sequences need only pairwise interactions, whereas non-Markovianity motivates testing for structural higher-order interactions.The latter result alone does not establish a hypergraph explanation, because pairwise processes with memory may also produce it.Source: §1 · p. 2, §2.2.1 · pp. 3–4

2.2.3 Step III. Model Comparison

  • Model comparison uses held-out likelihood and BIC against the memoryless SB hypergraph null, first-order MC1, and second-order MC2, which controls for ordinary temporal memory.Any predictive gain over SB specifically tests the contribution of latent temporal structure.Source: §2.2.3 · p. 6

2.3 Validation on Synthetic Hypergraphs

  • The HMM achieved the best predictive and complexity-penalized performance against the baselines, with minimum BIC at the true hyperedge count, K = 15.Its likelihood plateau occurred slightly later than the ground-truth K, which the authors attribute to the HMM’s optimization procedure.Source: Figure 2 · p. 7, Table 1 · p. 8
  • The fitted HMM recovered hyperedge composition and transitions, with cosine similarity 0.910 ± 0.050 for T, 0.918 ± 0.041 for B, and 0.892 ± 0.021 for S.The learned B reproduced the ground-truth incidence structure, and S had similar support.Source: §2.3 · pp. 7–8
  • Synthetic sensitivity tests found robust structure across model settings, while negative controls distinguished hyperedge effects from memoryless and second-order pairwise dynamics.At higher K, additional hyperedges were largely redundant; on Markovian data the HMM did not outperform SB, while MC2 outperformed it on second-order data.Source: §2.3 · p. 8

2.4 Empirical Results on Football Formations

  • Across all examined football datasets, trajectories passed the conditional mutual information test for non-Markovianity, establishing that a first-order Markov description is insufficient and making higher-order latent structure a legitimate modeling target.The datasets include Bayern Munich formations 3-4-2-1 and 3-5-1-1 and Atlético Madrid formation 4-4-2; observed nodes are player roles, not individual players.Source: §2.4 · p. 9

2.4.1 Bayern Munich (Formations (3-4-2-1) and (3-5-1-1))

  • The HMM outperforms all baselines in held-out log-likelihood and BIC at K = 4 and K = 9; K = 4 matches Bayern Munich’s announced formation size.K = 9 is the ceiling, the highest K at which the HMM still has lower BIC than the baselines.Source: §2.4.1 · p. 9, Table 2 · p. 11
  • At BIC-optimal K, Bayern’s recovered states group roles into tactically coherent units, including a shared central midfield engine and a shared defensive build.The estimated affinity and role-composition matrices share only partial support, indicating asymmetric vertex–hyperedge affinities; assignments reflect reliability across cross-validation folds, not ground truth.Source: §2.4.1 · p. 10
  • Bayern’s central-midfield and flank states are highly persistent, while the deep-build and final-third states are tightly coupled, suggesting direct vertical progression that bypasses settled midfield.Self-transition probabilities are 0.986 and 0.997 for States 0 and 2; States 1 and 3 route over 99% of outgoing probability between themselves, without explicit possession-phase supervision.Source: §2.4.1 · p. 10

2.4.2 Case of the Atlético Madrid (Formation 4-4-2)

  • Atlético’s learned structure remains interpretable as K rises from 3 to 5 and 7, but a positive information gap appears only at ceiling K = 11, exposing a prediction–interpretability trade-off.Several groupings, including the central-midfield pairing, recur across those K values; at larger K, the structure can become increasingly fragmented.Source: §2.4.2 · p. 11

2.4.3 Other teams

  • Across most other teams and formations, the edge-latent HMM reaches its lowest BIC at expected K and positive information gain at ceiling K; Bayern and Atlético results are robust to random seed.The seed repetitions varied parameter initialization and the train, validation, and held-out trajectory partitions.Source: §2.4.3 · p. 11

3 Discussion

Across football configurations, the pipeline detects latent tactical phases and recovers interpretable structures; when the announced and BIC-optimal numbers of states coincide, it recovers a formation from possession sequences without team-shape supervision. Its empirical scope is constrained by fixed-structure and data-size assumptions, while Atlético Madrid’s results show that coherent groupings can persist across choices of K.

3 Discussion

  • A debiased conditional mutual information test and hyperedge-latent HMM comparisons against pairwise and Markov-chain baselines test whether higher-order representations are required.The HMM is assessed using held-out likelihood and complexity-penalized model comparison; selected non-Markovianity serves as an observable trace to test rather than assume higher-order structure.Source: §3 · pp. 11, 14
  • Across football configurations, latent tactical phases emerge with significant held-out likelihood advantages over pairwise and memory-expanded baselines, and role profiles align with recognizable tactical units.When announced and BIC-optimal K coincide, the model recovers a team’s formation from possession sequences without supervision on team shape.Source: §3 · p. 14
  • For Atlético Madrid, BIC favors a higher K than the announced formation, yet tactically coherent groupings persist as K increases.Figure 4 tracks states across K = 3, 5, and 7, showing how groupings split, merge, or persist.Source: Figure 4 · p. 13, §3 · p. 14
  • The pipeline is limited to random-walk-like trajectories on a fixed hypergraph, and its HMM assumes one higher-order representation remains constant across trajectories.Football trajectories are a suitable case when a team’s formation remains approximately constant over a match.Source: §3 · p. 14
  • Weaker higher-order signals require more trajectories for reliable recovery, so teams with insufficient data had formations aggregated.A temporally varying representation is proposed for future work, but would expand computation and search while reducing effective sample size if trajectories were partitioned.Source: §3 · pp. 14–15

4 Methods

The methods test whether observed trajectories contain memory, model that memory with latent hyperedges, and compare the model against pairwise alternatives. Synthetic hypergraphs and football possession trajectories provide the respective test setting and empirical application.

4.1 Test of Markovianity via Conditional Mutual Information

  • A positive conditional mutual information test shows that the previous vertex carries information beyond the current one, but does not establish genuine higher-order interactions.The test debiases the plug-in estimate using stratified permutations within each current-vertex stratum and is applied separately within each formation.Source: §4.1 · p. 15

4.2 The Hyperedge-Latent Hidden Markov Model

  • The HMM treats each latent state as a hyperedge, with assignment, emission, and transition matrices governing vertex activation, emission, and hyperedge affinity.The joint vertex-hyperedge process is first-order Markov, but the observed vertex trajectory can retain memory because a vertex may correspond to several hidden hyperedges.Source: §4.2 · pp. 15–16

4.3.1 Direct Estimation for Standard Markov Chains (MC1, MC2)

  • MC1 and MC2 transition probabilities are estimated from empirical frequencies, with Laplace smoothing to avoid zero probabilities for unobserved transitions.The smoothing coefficient is α = 5 × 10^-1; the authors report consistent results with 5 × 10^-2 and 5 × 10^-4.Source: §4.3.1 · p. 16

4.3.2 Expectation-Maximization for the HMM and SB Null

  • The HMM and SB null use generalized EM with forward-backward inference to estimate their unobserved hyperedge sequences.The expected complete-data log-likelihood decomposes into local terms; the emission matrix has a closed-form update, while the full HMM jointly optimizes coupled assignment and transition matrices by projected gradient ascent.Source: §4.3.2 · pp. 16–17

4.4 The null models.

  • The SB null removes latent memory by making hyperedge selection independent across steps given the current vertex; MC1 and MC2 instead model transitions directly on vertices.MC2 conditions on the previous two vertices and captures one step of explicit historical dependence.Source: §4.4 · pp. 18–19

4.5 Model Comparison

  • The HMM is compared with SB, MC1, and MC2 using out-of-sample predictive log-likelihood and in-sample BIC, which penalizes model complexity.Likelihood comparisons use paired 10-fold trajectory-level cross-validation; BIC is computed from one full-dataset fit and is a model-selection metric, not a formal significance test.Source: §4.5 · p. 19

4.6 Synthetic Hypergraphs and Trajectory Generation

  • Synthetic trajectories are generated from known hypergraph parameters, with hyperedge persistence controlling the strength of the induced non-Markovianity.Zero persistence yields the memoryless SB process; weaker higher-order signals require more trajectories for reliable recovery.Source: §4.6 · pp. 19–20

4.7 Empirical Trajectory Extraction

  • Football trajectories encode uninterrupted possessions as sequences of roles, and recovered hyperedges represent co-activation patterns of roles rather than fixed player groups.Formations are tested separately for non-Markovianity before model fitting to rule out a spurious signal from pooling different formations.Source: §4.7 · pp. 20–21

Data and code availability

The paper provides the code repository and identifies the source of its football trajectories.

Supplementary Note 1 Synthetic homogeneous Watts–Strogatz hypergraph

In the homogeneous synthetic setting, recovered hyperedges reflect the ground-truth structure, but increasing the number of latent states beyond the BIC optimum mainly adds redundant groups.

  • At K = 15, the recovered emission matrix reproduces the ground-truth incidence blocks except for hyperedge 10, illustrating that gradient descent does not guarantee convergence to the true solution.Source: Supplementary Note 1 Synthetic… · p. 24, Figure 1 · p. 26
  • Beyond the BIC-optimal K, recovered hyperedges increasingly split into overlapping subsets, with fewer unique parent matches and more near-duplicate groups.The supplementary diagnostics distinguish cross-K refinement from within-K redundancy; the latter counts groups with Jaccard overlap of at least 0.8.Source: Supplementary Note 1 Synthetic… · p. 24, Table 3 · p. 25
  • The recovered assignment and emission matrices have a Jaccard similarity of 0.984 between their binarized supports, consistent with their shared ground-truth support.Source: Supplementary Note 1 Synthetic… · pp. 25, 28
  • The 23 recovered states are matched to the 15 ground-truth hyperedges by Hungarian assignment, leaving eight unmatched states.Source: Figure 2 · p. 27

Supplementary Note 2 Synthetic heterogeneous Watts–Strogatz hypergraph

For heterogeneous synthetic hypergraphs, the HMM recovers ground-truth membership and outperforms the baselines, while finite-sample BIC selects fewer states than the true number.

Supplementary Note 3 Synthetic homogeneous Watts–Strogatz hypergraph Power Analysis

With the sample count fixed, lowering the probability of staying in a hyperedge weakens the HMM’s advantage at the expected hyperedge count. The authors identify low signal magnitude as a setting where sufficient samples are needed to train the HMM.

Supplementary Note 3 Synthetic homogeneous Watts–Strogatz hypergraph Power Analysis

Supplementary Note 4 Overlap and Hyperedge Size Influence on HMM Performance

The HMM advantage over the null model varies with hyperedge overlap and size. It increases with overlap, peaks at size 3, and is near zero at size 2.

Supplementary Note 4 Overlap and Hyperedge Size Influence on HMM Performance

Supplementary Note 5 Negative Samples

The negative controls favor the model class matching the generating process: MC1 for first-order Markov data and MC2 for second-order temporal data. On football data, the contrasting result favors the edge-latent HMM over second-order positional memory.

Supplementary Note 5 Negative Samples

  • For first-order Markov synthetic data, MC1 attains the lowest BIC and highest predictive likelihood.The comparison is at the true K = 15; Supplementary Table 8 reports test-set log-likelihood across 10 folds and full-dataset BIC.Source: Supplementary Note 5 Negative Samples · p. 34, Table 8 · p. 34
  • For second-order temporal synthetic data, MC2 attains the lowest BIC and highest predictive likelihood.The comparison is at the true K = 15; Supplementary Table 9 reports test-set log-likelihood across 10 folds and BIC.Source: Supplementary Note 5 Negative Samples · p. 34, Table 9 · p. 35
  • On empirical football data, MC2 is heavily penalised while the edge-latent HMM retains its advantage, unlike the second-order negative control.The authors interpret this contrast as evidence that the real-data dependencies reflect a latent hyperedge footprint rather than second-order positional memory.Source: Supplementary Note 5 Negative Samples · p. 34

Supplementary Note 6 Markovianity Test For Empirical Data

Every tested formation has statistically significant non-Markovian structure, including when formations are analyzed individually. This within-formation result rules out aggregation of heterogeneous first-order Markov chains as the explanation for the observed signal.

Supplementary Note 6 Markovianity Test For Empirical Data

  • All formations show statistically significant non-Markovian structure (p < 0.01), so first-order Markov dynamics alone do not explain the trajectories.The table estimates debiased conditional mutual information from transition triples and uses stratified permutation tests.Source: Supplementary Note 6 Markovianity Test… · p. 35, Table 10 · p. 35
  • The signal holds within each individual formation, ruling out aggregation of heterogeneous first-order Markov chains across tactical contexts as its explanation.This finding applies to each formation considered in the analysis.Source: Supplementary Note 6 Markovianity Test… · p. 35
  • When multiple formations are pooled, the authors interpret the non-Markovian signal as reflecting higher-order movement dependencies rather than a mixture-of-Markovians artifact.Chelsea FCW is given as an example of pooling three formations.Source: Supplementary Note 6 Markovianity Test… · p. 35

Supplementary Note 7 Empirical Results on Additional Teams and Formations

The additional football results report model comparisons across team formations and formation-size groupings, alongside a Bayern Munich result indicating asymmetry in the recovered higher-order structure.

Supplementary Note 7.1 Bayern Munich (Formations 3-4-2-1,3-5-1-1)

  • For Bayern Munich’s 3-4-2-1 and 3-5-1-1 matches, the binarized group-membership matrices have Jaccard similarity 0.5, indicating asymmetric vertex–hyperedge affinities.The section reports 713 pass trajectories from seven matches; Supplementary Figure 6 compares model performance and recovered states.Source: Supplementary Note 7.1 Bayern Munich… · pp. 35–36, Figure 6 · p. 37

Supplementary Note 7.2 Atlético Madrid (Formation 4-4-2)

Supplementary Note 7.3 Chelsea FCW (Formations 4-1-2-2-1 / 4-2-2-1-1 / 4-1-2-1-2)

Supplementary Note 7.4 Atlético Madrid (All Formations Size 3)

Supplementary Note 7.5 Bayern Munich (All Formations Size 3)

Supplementary Note 7.6 Chelsea FCW (All Formations Size 3)

Supplementary Note 8 Multi Seeding Results on Football Data

The multi-seed analysis tests whether football results depend on random initialization and data partitions. Atlético’s result generalizes across seeds, while Bayern’s results show a predictive-performance versus model-complexity trade-off.

Multi-seeding results

  • Across nine seeds, Bayern’s expected K = 4 has the lowest BIC, but its log-likelihood is indistinguishable from MC1; at K = 9, the advantage over MC1 is +0.070 and significant.The larger-K solution has a higher BIC, reflecting the added parameter cost.Source: Supplementary Note 8 Multi Seeding… · p. 50, Table 17 · p. 51
  • Across nine seeds, Atlético Madrid’s main-text result at optimal K = 11 rather than expected K = 3 generalizes.Supplementary Table 16 aggregates test-set log-likelihood and full-dataset BIC results across seeds.Source: Supplementary Note 8 Multi Seeding… · p. 50, Table 16 · p. 50
  • The repeated pipeline varies EM initialization, train/test splits, and cross-validation partitions to check dependence on a single random draw.The analysis covers Bayern Munich and Atlético Madrid.Source: Supplementary Note 8 Multi Seeding… · p. 50

Supplementary Note 9 Tactical Roles Dictionary

The data provider defines the state space using 24 distinct tactical roles, with standard abbreviations for the listed positions.

Tactical roles dictionary

  • The state space V contains 24 tactical roles defined by the data provider’s specification.The section provides an alphabetical role list with standard abbreviations.Source: Supplementary Note 9 Tactical Roles… · p. 52
  • Attacking and forward roles include RAM, RCF, CAM, LAM, and LCF, denoting right attacking midfield, right center forward, center attacking midfield, left attacking midfield, and left center forward.These are among the roles in the provider-defined state space.Source: Supplementary Note 9 Tactical Roles… · p. 52
  • Defensive and central roles include RCB, RCM, RDM, CDM, LCB, LCM, and LDM; RWB and LWB denote right and left wing back.The abbreviations expand respectively to right/left center back, center midfield, defensive midfield, and wing back.Source: Supplementary Note 9 Tactical Roles… · p. 52

Related papers

Loading 2610.20095v1…