Graph-Based Multivariate Multiscale Dispersion Entropy: Efficient Implementation and Applications to Real-World Network Data

The paper addresses the need for methods that jointly capture temporal dynamics and topological (spatial) relationships in multivariate time series recorded over networks, such as industrial processes and weather systems. Existing multivariate entropy techniques (e.g., mvDE and multivariate sample entropy) quantify complexity beyond univariate analysis but largely ignore explicit graph structure. Conversely, graph-tailored entropy methods (e.g., permutation and dispersion entropy on graphs) focus on topology but often neglect temporal scaling. The research question is whether a unified approach can integrate both temporal and topological information efficiently to better characterise complex systems. The authors propose Multiscale Multivariate Graph-based Dispersion Entropy (mvDEG), which leverages graph structures to encode inter-channel relationships and applies multiscale analysis to capture temporal dynamics, while introducing an efficient algorithm that scales linearly with network size, enabling application to large real-world datasets.

• Multivariate entropy methods (e.g., Multivariate Sample Entropy; Multivariate Multiscale Dispersion Entropy) provide robust complexity estimates for multichannel data, often performing well on short series, but do not exploit explicit network topology.
• Graph signal processing has motivated entropy measures for graph-structured data (Permutation Entropy and Dispersion Entropy for graph signals), enabling analyses that incorporate graph connectivity.
• Extensions such as graph-based Bubble Entropy have built on these foundations. However, many graph-oriented approaches have limited treatment of temporal multiscale structure, and prior implementations can be computationally demanding.
• There is a methodological gap in jointly modelling temporal multiscale dynamics and spatial/topological dependencies efficiently, motivating mvDEG.

mvDEG extends dispersion entropy to multivariate time series defined on graphs, integrating temporal multiscale analysis with topological relationships and providing an efficient implementation.

1. Multiscale coarse-graining:

• Given a multivariate signal X = {X^k}{k=1..p} with N samples per channel, for each scale τ, partition each channel into non-overlapping segments of length τ and compute their mean to obtain coarse-grained signals: x̄{i,k} = (1/τ) Σ_{j=(i−1)τ+1}^{iτ} x_{j,k}, for i=1..L, k=1..p, where L is the coarse-grained length. mvDE is then computed on each coarse-grained version per scale.

2. Graph-based multivariate dispersion entropy (per scale):

• Inter-channel interactions are encoded in an adjacency (interaction) matrix I_p ∈ R^{p×p}, which may be predefined (e.g., fully connected), derived from prior knowledge, or learned from data (graph learning). The time axis is represented as a directed path graph P_N. The combined graph is formed via the Cartesian product P_N □ I_p.
• Embedding matrix: choose embedding dimension m ≥ 2 and number of classes c. Construct an embedding matrix Y ∈ R^{N×m} with columns Y_k = D A^k v, where A is the adjacency of the Cartesian product graph P_N^{I_p}, D is a diagonal normalisation matrix, and v is the vectorised multivariate signal. This captures successive graph-shifted versions of the signal.
• Mapping to classes: apply a mapping M: R → {1,...,c} element-wise to Y to obtain M(Y) ∈ N_c^{N×m}.
• Pattern frequencies: each row (embedding vector) corresponds to a dispersion pattern; estimate relative frequencies p(π) across all patterns.
• Entropy: compute normalised Shannon entropy mvDE_c(X,m,L,c) = −(1/log(c^m)) Σ_{π} p(π) ln p(π).

3. Efficient implementation via Kronecker structure:

• The adjacency of the Cartesian product graph is A_{P_N I_p} = A_N ⊗ I_p + I_N ⊗ A_I, where A_N is the adjacency of the time path P_N, A_I is the adjacency of the interaction graph, and ⊗ denotes the Kronecker product.
• Since (A_N ⊗ I_p) and (I_N ⊗ A_I) commute, powers satisfy the binomial expansion: (A_{P_N I_p})^m = Σ_{k=0}^m (m choose k) (A_N)^k ⊗ (A_I)^{m−k}.
• Powers of the path adjacency (A_N)^k have simple banded structure allowing efficient computation. Therefore, the expensive power of the large Np × Np matrix is reduced to sums of Kronecker products of small matrices, greatly lowering time and memory.

4. Computational complexity comparison:

• Classical mvDE computes (N^{m+1})(m p)^p dispersion patterns, which explodes with m and p, incurring heavy memory/time costs.
• mvDEG processes at most (N^m) p patterns and exploits efficient matrix-power computations, resulting in linear growth with number of vertices/nodes and substantial acceleration over classical methods.

Implementation details include selection of I_p (identity/zero, fully connected, or data-driven correlation/learned), typical parameters m=4 and c=6 per literature, and multiscale evaluation over a range of τ.

Synthetic data:

• Uncorrelated noise (trivariate, N=15,000; 40 realisations; m=4, c=6): mvDE and mvDEG yield similar qualitative trends. WGN has higher entropy at small scales; coarse-grained WGN entropy decreases with scale, whereas 1/f noise remains nearly constant across scales, indicating multi-scale complexity in 1/f noise consistent with literature.
• Using a zero/identity interaction graph for uncorrelated noise, mvDEG mirrors mvDE (temporal information dominates). When using estimated correlations as I_p, mvDEG entropy decreases slightly, reflecting reduced complexity due to inter-channel dependencies.
• Correlated noise (N=500; 40 realisations; m=4, c=6): mvDE shows overlapping entropy distributions across different correlation-structure cases, limiting discrimination. mvDEG clearly separates mean and SD of entropy across five correlation configurations (from uncorrelated to fully connected) and across varying correlation strengths (ρ ∈ {0.95, 0.75, 0.55, 0.35, 0.15}), demonstrating sensitivity to dependency structure even in short time series.

Computational efficiency:

• Classical mvDE encountered RAM overflow (e.g., N≈2000, m=5, p=8). mvDEG successfully processed analogous datasets without memory errors and with notably lower runtime.
• Pattern-count example: for N=2000, p=8, m=5, mvDE requires ~1.3×10^9 patterns; mvDEG requires ~1.6×10^3, a drastic reduction consistent with observed speedups.

Real-world data:

• Weather (Brittany ground stations; 37 cities; 744 hourly samples): Graph constructed with Gaussian-kernel distance weights. With m=4, c=6 and distance graph, mvDEG reveals: rainfall shows consistently low entropy across scales (1/f-like, low complexity), temperature shows slightly higher and stable entropy, wind (mean and max) exhibits highest complexity with decreasing trend at lower scales. Classical mvDE is computationally infeasible here (~3.4×10^11 patterns); mvDEG reduces to ~2.7×10^4 patterns. Univariate Dispersion Entropy and Sample Entropy on each sensor detect lower rainfall entropy but fail to separate wind vs temperature dynamics; Sample Entropy undefined beyond scale > 6.
• Two-phase flow (ERT; 16 electrodes; 208 voltage features; ~1400 samples; 105 experiments): mvDEG applied directly to full multichannel data (m=4, c=6), obviating dimensionality reduction. Distinct entropy profiles across six regimes (Bubbly, Stratified, Plug, Slug, Churn, Annular). Bubbly and Stratified: low/stable entropy; Slug: higher at small scales with decreasing trend after scale ~10; Plug: lower at small scales with divergence from Slug around scale ~10 indicating transition; Churn: higher than Slug but below Annular across scales; Annular: highest entropy, rising then stabilising at higher scales. mvDEG robust to noise and different graph choices, and feasible where classical mvDE would face memory limits even at p=8.

The findings confirm that integrating graph topology with temporal multiscale analysis enhances the characterisation of multivariate dynamics. mvDEG captures both spatial dependencies (via I_p) and temporal patterns (via coarse-graining and embedding), enabling discrimination of correlation structures that classical mvDE cannot reliably separate, especially evident in correlated noise experiments. The efficient Kronecker-based implementation enables analysis of high-dimensional, networked datasets that are impractical for classical mvDE, without sacrificing discriminative power. Real-world applications further demonstrate that mvDEG uncovers physically meaningful structure: it distinguishes meteorological variables with different inherent complexities and resolves flow-regime-specific signatures in two-phase ERT data while leveraging all available channels. Overall, mvDEG addresses the core challenge of joint spatial-temporal complexity quantification with computational tractability, making it suitable for large-scale and real-time analyses.

The paper introduces mvDEG, a multiscale, graph-based extension of dispersion entropy for multivariate time series that unifies temporal and topological information. Methodological contributions include an efficient Kronecker-product-based computation for powers of Cartesian-product graph adjacencies, reducing complexity from exponential (in m and p) to linear growth with node count. Empirically, mvDEG matches or surpasses classical mvDE in characterising complexity on synthetic data, distinctly separates varying correlation structures, and is robust on short series. In real-world weather and two-phase flow datasets, mvDEG reveals clear, interpretable entropy profiles while remaining computationally feasible where classical mvDE is not. Future research may explore automated/learned graph construction, extensions to other graph entropy measures (e.g., multivariate multiscale permutation entropy), and deployment in online/real-time monitoring across application domains.