Abstract
Traditional measures based solely on pairwise associations often fail to capture the complex statistical structure of multivariate data. Existing approaches for identifying information shared among $d>3$ variables are frequently computationally intractable, asymmetric with respect to a target variable, or unable to account for all the ways in which the joint probability distribution can be factorised. Here we present a systematic framework based on lattice theory to derive higher-order information-theoretic measures for multivariate data. Our construction uses lattice and operator function pairs, whereby an operator function is applied over a lattice that represents the algebraic relationships among variables. We show that many commonly used measures can be derived within this framework, yet they fail to capture all interactions for $d>3$, either because they are defined on restricted sublattices, or because the use of the KL divergence as an operator function, a typical choice, leads to undesired disregard of groups of interactions. To fully characterise all interactions among $d$ variables, we introduce the Streitberg Information, which is defined over the full partition lattice and uses generalised divergences (beyond KL) as operator functions. We validate the Streitberg Information on synthetic data, and illustrate its application in detecting complex interactions among stocks, decoding neural signals, and performing feature selection in machine learning.
Introduction
In complex systems—from neural circuits to global financial markets—variables rarely interact in simple pairs. Much like the harmony of a symphony emerges from the collective interplay of an entire orchestra, significant information in multivariate data often resides in "higher-order interactions" (HOIs) involving three or more variables. Traditional information-theoretic tools, such as Total Correlation (TC) or Interaction Information (II), frequently struggle to capture these dynamics, either becoming less informative as dimensionality increases or suffering from interpretability issues. This paper introduces a rigorous framework based on lattice theory to systematically derive measures capable of characterizing these complex dependencies.
The Lattice Framework and the KL Divergence Trap
The proposed framework represents the algebraic relationships among variables using the partition lattice, which accounts for every possible way a set of variables can be grouped or factorized. By applying Möbius Inversion to this lattice, the authors can isolate information unique to specific group sizes.
A key theoretical finding is the "KL Divergence Trap." Standard measures typically rely on the Kullback-Leibler (KL) divergence to quantify distances between probability distributions. However, for $d > 3$, the use of KL divergence causes different interaction types to mathematically cancel out, leading to a "deatomisation" or collapse of the underlying lattice structure. This effectively blinds researchers to specific groups of higher-order interactions.
Streitberg Information (SI)
To resolve this, the authors introduce Streitberg Information (SI). Unlike previous measures, SI is defined over the complete partition lattice and utilizes generalized divergences, such as the Tsallis-Alpha divergence, as operator functions. This choice prevents lattice collapse, ensuring the measure remains sensitive to all possible factorizations of the joint distribution. SI is symmetric, treating all variables equally, and recursive, allowing for a hierarchical decomposition of information.
Validation and Empirical Results
The authors validated SI across synthetic benchmarks and real-world datasets, demonstrating its robustness and utility.
Key Findings:
- Synthetic Sanity Checks: In tests with Multivariate Gaussians and logical gates (XOR, COPY), SI correctly identified ground-truth interactions. Notably, SI remained at zero when a system was factorable into independent groups, a "sanity check" that Total Correlation failed.
- Financial Markets: Analysis of S&P 500 stock returns showed that 4-way interactions vary significantly by sector. The authors also observed that the COVID-19 pandemic caused a widespread shift in these higher-order dependencies.
- Neural Decoding: Using 4-way SI as a feature significantly improved the accuracy of classifiers distinguishing between preparatory and action brain states in macaque monkeys, outperforming models limited to pairwise or 3-way data.
- Feature Selection: In machine learning benchmarks, SI was the only method (compared to SHAP and RFE) to identify the exact set of variables in a complex XOR relationship with 100% accuracy.
Limitations and Future Work
Despite its strengths, SI faces computational challenges due to the combinatorial explosion of the partition lattice (governed by Bell numbers). While "singleton cancellations" help mitigate this, scaling to very large variable sets ($d > 10$) remains difficult. Additionally, the current k-nearest-neighbours (kNN) estimator assumes i.i.d. data, potentially overlooking temporal dynamics in time-series. Future research will focus on extending SI to causal discovery and optimizing the choice of the alpha parameter.
Summary updated