Sample entropy for graph signals: An approach to nonlinear analysis of graph signals

Mei-San Maggie Lei 1,* , John Stewart Fabila Carrasco 2 , Javier Escudero 1 · 2026

Read Sample entropy for graph signals: An approach to nonlinear analysis of graph signals by Mei-San Maggie Lei 1,* , John Stewart Fabila Carrasco 2 , Javier Escudero 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20655.txt.

Introduction

Lei, Fabila Carrasco, and Escudero offer a graph version of Sample Entropy, called SampEn-G, to measure roughness of graph signals. Instead of time delay maps, their approach uses multi-hop graph-based maps, pooling patterns from walk-weighted means via powers of the graph shift operator. They show that SampEn-G reduces to standard 1D Sample Entropy on path graphs, and test its sensitivity with the logistic map. Tests on Erdos-Renyi signals show its shape with links and pattern length, at times for thousands of nodes.

Catalog record

CREATORMei-San Maggie Lei 1,* , John Stewart Fabila Carrasco 2 , Javier Escudero 1
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE10135
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20655

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sample entropy for graph signals: An approach to nonlinear analysis of graph signals Mei-San Maggie Lei 1,* , John Stewart Fabila Carrasco 2 , Javier Escudero 1 Abstract We introduce a graph-signal generalisation of Sample Entropy, denoted SampEn G , to quantify irregularity of graph signals on a continuous state space, complementing existing methods on symbolic dynamics. Our approach replaces the temporal delay embedding of classical SampEn with a multi-hop graph-based embedding: for each node, we aggregate patterns from local walk-weighted neighbourhood averages computed via powers of the graph shift operator. We show empirically that SampEn G reduces to classical 1D SampEn on directed path graphs, and validate its nonlinear sensitivity using the logistic map. Experiments on directed Erdős–Rényi graph signals further characterise its behaviour with connectivity and pattern length m m , with practical runtimes on the order of thousands of nodes. We expect SampEn G to open up new ways to analyse graph signals, generalising SampEn and the concept of conditional entropy to extending nonlinear analysis to a wide variety of network data. I Background Current entropy methods for Graph Signal Processing (GSP), including graph-based Permutation Entropy and its variants–Dispersion Entropy, and Bubble Entropy–have been extended to signals defined over graphs and networks [ 4 , 3 , 2 ] . While effective, they are restricted to symbolic dynamics through discretisation to compute Shannon entropy. Sample Entropy (SampEn) measures irregularity (complexity) of a time series by estimating a conditional recurrence probability in a continuous state space via a fixed threshold \epsilon . Specifically, SampEn measures how likely patterns of length m remains similar when extended to length m+1 . Application of SampEn includes finance, electronics, ecology, and engineering [ 1 ] . In this abstract, we summarise our recent work extending SampEn to graph signal ( \SEG ), providing a continuous, conditional entropy-based entropy on graph signal framework. Our experiments with logistic map and Erdős–Rényi (ER) graph signals then evaluate its sensitivity to nonlinear dynamics, and to study its dependence on connectivity using random node attributes. II Methodology II-A SampEn for graph signals: SampEn G Classical SampEn for univariate time series is controlled by the pattern length m and tolerance parameter r , which sets the matching threshold \epsilon=r\times SD (standard deviation of signal), and the patterns are built by concatenating successive temporal observations separated by a time step ( L often taken as L=1 ) [ 7 ] . In this abstract, we use the Chebyshev distance, with m=2 and r=0.2 , as is standard in SampEn [ 8 ] . In our graph-based generalisation, the notion of a step is replaced by the graph hop – one hop corresponds to a single traversal along an edge from one node to another adjacent node. Consider a graph \mathcal{G}=(\mathcal{N},\mathcal{E},\mathbf{A}) . For each node, we construct a vector (pattern) whose components are local graph-signal aggregates to characterise the radial profiles around each node in multiples of L hops ( L=0,1,2,\dots ) via powers of the graph shift operator (adjacency matrix) in analogy to increasing temporal steps in SampEn. To obtain these components, we first identify the local L -hop neighbours for each node. Consider the multiplication of \mathbf{A} with itself: (\mathbf{A}^{L=2})_{ij}=\sum_{k}\mathbf{A}_{ik}\times\mathbf{A}_{kj}. (1) Each entry (\mathbf{A}^{L=2})_{ij} is the sum of walks of length two from node i to j over any intermediate node k . The L -hop degree of node i can be defined as the corresponding row sum: \displaystyle\deg^{L}(i) \displaystyle:=\sum_{j=1}^{N}(\mathbf{A}^{L})_{ij},\qquad L\geq 1. (2) We identify the L -neighbourhood – all nodes that are exactly at L -hops – for each node. For L\in\mathbb{N} , non-zero entries in (\mathbf{A}^{L})_{ij} indicate the total number of L -length walks reachable from node i to j . Building on our previous work on PE G [ 4 ] , we here extend the framework to introduce SampEn G . For each node i\in\mathcal{N} , we construct its m and m+1 -dimensional patterns \mathbf{\overline{x}}^{m}(i) and \mathbf{\overline{x}}^{m+1}(i) as: \mathbf{\overline{x}}^{m}(i)=[\overline{x}_{i}^{0},\overline{x}_{i}^{1},\dots,\overline{x}_{i}^{m-1}]\quad i\in\mathcal{N}^{\star}_{m}, (3) \mathbf{\overline{x}}^{m+1}(i)=[\overline{x}_{i}^{0},\overline{x}_{i}^{1},\dots,\overline{x}_{i}^{m}]\quad i\in\mathcal{N}^{\star}_{m}, (4) \displaystyle\mathcal{N}^{\star}_{m}:=\big\{i\in\mathcal{N}:\deg^{L}(i)>0\quad\text{for}\,L=1,\dots,m\big\}. (5) To avoid undefined patterns with sparse graphs, we restrict to patterns with non-zero reachability up to m -hops. Here, \overline{x}_{i}^{0} is the signal value on node i , and \overline{x}_{i}^{L} is a walk-weighted mean of the L -neighbourhood of node i , in hop-radius propagation: \quad\overline{x}_{i}^{L}=\frac{1}{\text{deg}^{L}(i)}\sum_{j\in\mathcal{N}_{L}(i)}(\mathbf{A}^{L})_{ij}x_{j}. (6) \mathcal{N}_{L}(i) denotes the set of reachable nodes in \mathcal{N} by at least one walk of exactly length L from node i . For weighted graphs, we replace \mathbf{A} with the weighted adjacency \mathbf{W} . The matrix power \mathbf{W}^{L} is the total weighted walks of L hops from i to j : \text{deg}^{L}(i)=\sum_{j=1}^{N}(\mathbf{W}^{L})_{ij},\quad\overline{x}_{i}^{L}=\frac{1}{\text{deg}^{L}(i)}\sum_{j\in\mathcal{N}_{L}(i)}(\mathbf{W}^{L})_{ij}x_{j}. The resulting patterns are of size 1\times m for each node. The successive steps of similarity matching, then follows: B_{i}(r)=\frac{1}{|\mathcal{N}^{\star}_{m}|-1}\!\sum_{\begin{subarray}{c}j\in\mathcal{N}^{\star}_{m}\\ j\neq i\end{subarray}}\|d[\mathbf{\overline{x}}^{m}(i),\text{ }\mathbf{\overline{x}}^{m}(j)]\leq\epsilon\|, (7) where \|\cdot\| denotes cardinality of a set, counting pairwise matches of patterns within Chebyshev distance of \epsilon=r\times SD , the total sums are then computed to obtain B^{m}(r) : B^{m}(r)=\frac{1}{|\mathcal{N}^{\star}_{m}|}\sum_{i\in\mathcal{N}^{\star}_{m}}B_{i}(r). (8) Repeating for \mathbf{\overline{x}}^{m+1}(i) yields count of matches A^{m}(r) for m+1 -patterns. Finally, we compute SampEn as the ratio of A^{m} and B^{m} : \small\text{SampEn}(m,r,N)=-\ln\left(\frac{A^{m}(r)}{B^{m}(r)}\right). (9) III Experiments and Results III-A Logistic Map We validated SampEn G on the logistic map, a classical nonlinear dynamical model that changes between order and chaos as a function of its bifurcation parameter \rho . The map is defined by [ 6 ] : x_{t+1}=\rho x_{t}(1-x_{t}). (10) Each node is associated with a time sample with directed i\rightarrow i+1 , or undirected edges between consecutive nodes, following [ 4 ] . We computed SampEn G for both paths and evaluated them against classical 1D SampEn (implementation from [ 5 ] ) in relation to \rho , repeated over 20 random initial conditions drawn uniformly from the open interval (0,1) . We report the mean and standard deviation across runs. Fig. 1 shows that SampEn G replicates and reduces to the standard 1D case on the directed path graphs. This is because the directed graph imposes the causality in the order of samples within the patterns of length m and m+1 implicitly assumed by classical SampEn. The undirected-path SampEn G closely tracks the overall trend of the other two curves, correctly identifying the bifurcation points and islands of periodicity with slight quantitative differences due to the non-causal, symmetric neighbourhood structure of the undirected path. These results validate the generalisation property of SampEn G on 1D signals. Fig. 1: Directed (blue), undirected (black) SampEn G , classical SampEn (red) ( m=2 , r=0.2 ) against \rho for logistic map. III-B Erdős–Rényi graphs We considered binary, directed ER graphs of N=2700 . Each node value is a random sample drawn from a uniform distribution in the range [0.01,0.10] . The parameter p controls the probability in which an edge exists between any two nodes. We set p=\frac{K}{N-1}, to target mean out-degree K\in\{3,4,5,6,7,8,9,10,12\} and varied pattern length m\in[1,2,3] . We then computed SampEn G over 20 graph realisations on an Apple M3 CPU running MATLAB R2024b. For N=2700 , we observed runtimes of \sim 295~ms ( m=1 ) to \sim 1400~ms ( m=3 ) per realisation. The resulting mean SampEn G across 20 observations are reported in Fig. 2 . SampEn G is computationally practical. In our experiments, graphs of N=2700 nodes can

Read the complete text