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

The paper addresses the challenge of analysing complex real-world systems (e.g., industrial processes, weather phenomena) that exhibit nonlinear, transient temporal dynamics alongside nontrivial spatial/topological structure. Traditional multivariate entropy methods capture temporal complexity across multiple channels but typically ignore network topology; conversely, recent graph-based entropy methods emphasize topology while downplaying temporal dynamics. The research goal is to develop a unified method that integrates temporal and topological information to better characterize multivariate time series defined on graphs, with high computational efficiency suitable for both short and long series. The authors propose Multivariate Multiscale Graph-based Dispersion Entropy (mvDEG), which extends classical multivariate dispersion entropy by embedding signals using a graph structure that models inter-channel interactions and temporal adjacency. They underline practical importance with applications to two-phase flow and weather datasets, where discerning the interplay between spatial topology and temporal evolution is crucial. The contributions include: a new multiscale multivariate entropy on graphs integrating time and topology; an efficient implementation using matrix and Kronecker product properties that reduces complexity from exponential to linear in the number of nodes; and empirical demonstrations on synthetic and real datasets showing improved discrimination and substantial speedups over classical methods.

Multivariate entropy methods (e.g., Multivariate Multiscale Entropy; Multivariate Dispersion Entropy, mvDE) are widely used to quantify complexity across multiple time series, often outperforming sample entropy and being effective on short data. In parallel, graph signal processing has enabled entropy definitions on graphs (Permutation Entropy and Dispersion Entropy for graph signals), capturing topological dependencies. Extensions such as Bubble Entropy on graphs build on this line of work. However, existing approaches often treat temporal and topological dimensions separately, limiting their ability to capture joint spatiotemporal complexity. In two-phase flow and meteorology, entropy metrics like Sample Entropy and Permutation/Dispersion Entropy have provided insights, yet they may miss the combined spatial-temporal structure. There is thus a need for methods that integrate multivariate temporal dynamics with graph topology efficiently and scalably.

mvDEG computes multiscale graph-based dispersion entropy for multivariate time series by combining a temporal coarse-graining scheme with a graph-structured embedding and an efficient matrix-power computation. Main steps: 1) Coarse-graining: For each channel, the time series is divided into nonoverlapping segments of length (scale factor) and averaged to produce a coarse-grained multivariate signal at each scale. 2) Graph-based embedding: Inter-channel interactions are encoded via an adjacency matrix over channels (which may be predefined, fully connected, or learned from data). The overall embedding uses the adjacency of a product graph that integrates temporal adjacency (path graph over time) with channel topology (the channel graph). Powers of the product-graph adjacency are used to form an embedding matrix whose columns are generated by iteratively propagating a vectorized multivariate signal through the graph structure. 3) Quantization: A mapping assigns each embedding entry to one of c classes, producing symbolic dispersion patterns. 4) Pattern statistics and entropy: Relative frequencies of dispersion patterns are computed, and the normalized Shannon entropy is reported as mvDEG at that scale. Efficient implementation: Direct computation of powers of the large product-graph adjacency matrix is expensive. The authors exploit Kronecker sum structure of the adjacency of the Cartesian product graph (A_time ⊗ I_channels + I_time ⊗ A_channels), together with commutativity properties, to express high powers as sums of Kronecker products of much smaller matrices. This reduces the dominant cost from manipulating an (N·p)×(N·p) matrix to operations on N×N and p×p matrices, cutting the number of required dispersion patterns from exponential in embedding dimension and channels to linear with respect to nodes, and enabling scalable computation across scales.

Synthetic uncorrelated noise: For trivariate signals (WGN vs 1/f noise), both mvDE and mvDEG show higher entropy for WGN at low scales and nearly constant entropy for 1/f across scales. With a zero adjacency (no inter-channel links), mvDEG mirrors mvDE; with a correlation-derived adjacency, mvDEG entropy slightly decreases, reflecting detected inter-channel dependencies. Synthetic correlated noise: Across sets with varying correlation structures, mvDE shows overlapping entropy distributions across scales, struggling to separate degrees of correlation. mvDEG clearly separates cases; mean values are distinct and standard deviations do not overlap, and it differentiates correlation levels (e.g., 0.95, 0.75, 0.55, 0.35, 0.15) with minimal SD overlap across scales. Computational efficiency: Classical mvDE suffers from exponential growth in dispersion patterns and memory issues (e.g., RAM overflow around N≈2000, m=5, p=8). Example counts: classical mvDE needs ~1.3×10^9 patterns for N=2000, p=8, m=5; mvDEG needs ~1.6×10^3. In weather data with 37 channels and 744 samples, classical mvDE would require ~3.4×10^11 patterns versus mvDEG’s ~2.7×10^4, making mvDEG feasible on standard hardware. Weather data: Using a distance-weighted station graph, mvDEG finds rainfall to have consistently low entropy, temperature slightly higher and stable, and wind (mean/max) the highest with decreases at lower scales, reflecting higher complexity and variability. Univariate dispersion and sample entropy fail to separate wind and temperature well; sample entropy becomes undefined beyond scale factor 6. Two-phase flow: mvDEG processes full 16-electrode ERT data without reduction and distinguishes flow regimes via characteristic multiscale entropy profiles. Bubbly and stratified flows show lower, stable entropy; slug and plug show distinct scale-dependent trends and transitions (notably around scale 10), churn exhibits intermediate-high complexity, and annular shows highest entropy, aligning with known physical behavior.

By embedding multivariate time series within a graph that captures inter-channel topology and temporal adjacency, mvDEG better resolves differences in dependency structure and complexity than classical multivariate entropy. The synthetic experiments demonstrate that mvDEG detects and separates varying degrees of correlation that mvDE largely overlaps. Real-world analyses in meteorology and two-phase flow show that mvDEG captures meaningful spatiotemporal dynamics (e.g., higher complexity in wind, distinct flow-regime profiles) that are informative for modelling and classification, while remaining computationally tractable. The efficient Kronecker-based implementation is central to enabling analysis at scale, allowing mvDEG to handle more channels and longer signals, and making it suitable for scenarios where classical methods either fail due to memory limits or provide insufficient discrimination. These findings directly address the study’s objectives: to integrate topology and time for more informative complexity analysis, and to do so with an implementation scaling linearly with graph size.

The paper presents mvDEG, a multiscale multivariate entropy for graph-structured time series that integrates temporal dynamics with topological structure. Empirical studies on synthetic and real-world datasets (weather and two-phase flow) show that mvDEG differentiates complex patterns and degrees of correlation more effectively than classical mvDE, while requiring drastically fewer patterns and computation time. A key innovation is an efficient algorithm based on Kronecker product properties that reduces complexity from exponential to linear in the number of vertices. Potential future work includes extending the efficient implementation principles to other graph-based entropy metrics (e.g., multivariate multiscale permutation entropy), exploring learned interaction graphs in diverse domains, and deploying mvDEG for real-time monitoring in large-scale sensor networks.