⚡ electrical engineering

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

This paper introduces SampEn $_{G}$ , a novel graph-signal generalization of Sample Entropy that utilizes multi-hop graph-based embeddings to quantify signal irregularity, thereby extending nonlinear analysis capabilities to diverse network data while maintaining consistency with classical methods on path graphs.

Original authors: Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

Published 2026-04-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand the "personality" of a complex system, like a heartbeat, a stock market, or a social network. You want to know: Is this system predictable and boring, or is it chaotic and full of surprises?

For decades, scientists have used a tool called Sample Entropy to answer this for things that happen in a straight line over time (like a heartbeat). But what if your data isn't a straight line? What if it's a messy web of connections, like a city's subway map or the internet?

This paper introduces a new tool called SampEnG (Sample Entropy for Graphs) to measure the "chaos" or "irregularity" of data living on these complex webs.

Here is the breakdown using simple analogies:

1. The Old Way: Walking Down a Hallway

Imagine you are walking down a long, straight hallway (a time series). To understand the pattern, you look at the last few steps you took.

Step 1: You look at your last 2 steps.
Step 2: You look at your last 3 steps.
The Question: "If I take one more step, will it look like the pattern I just made?"

If your steps are very predictable (like a robot marching), the answer is always "Yes." The entropy is low.
If your steps are random (like a drunk person stumbling), the answer is "No, I can't guess the next one." The entropy is high.

2. The New Problem: The Spaghetti Network

Now, imagine that hallway is gone. Instead, you are standing in a giant, messy room full of people holding hands in a giant web (a Graph). You can't just walk "forward" because there is no single forward direction. You can go left, right, up, or down to a neighbor.

How do you measure the "personality" of this web? You can't just look at a timeline. You have to look at neighbors.

3. The New Solution: The "Social Circle" Detective

The authors created SampEnG, which acts like a detective looking at a person's social circle instead of their timeline.

The "Hop" Concept: Instead of "time steps," the tool uses "hops."
- 0 Hops: The person themselves.
- 1 Hop: Their direct friends.
- 2 Hops: Their friends' friends.
- 3 Hops: Their friends' friends' friends.
The Pattern: For every person in the network, the tool builds a "profile" by averaging the data of their friends, then their friends' friends, and so on. It creates a snapshot of the local neighborhood.
The Comparison: The tool asks: "Does Person A's neighborhood look similar to Person B's neighborhood?"
- If everyone's neighborhood looks exactly the same (highly connected, uniform), the system is predictable (Low Entropy).
- If everyone's neighborhood is totally unique and wild, the system is chaotic (High Entropy).

4. The Experiments: Did it Work?

The authors tested this new detective tool in two ways:

A. The "Straight Line" Test (The Logistic Map)
They took a classic math problem that creates chaos and forced it onto a straight line of people.

Result: When they used their new tool on this straight line, it gave the exact same answer as the old, famous tool.
Meaning: This proves the new tool is a valid upgrade. It works on the old stuff and the new stuff.

B. The "Random Web" Test (Erdős–Rényi Graphs)
They created random webs of 2,700 people and changed how many connections (friends) each person had.

Low Connections: When people had few friends, the tool found high chaos (high entropy). The network was irregular.
High Connections: As they added more and more connections, the tool found the chaos dropping. Why? Because when everyone is connected to everyone, the neighborhoods start to look the same. The "surprise" disappears.
Speed: They also checked how fast it was. On a modern computer, it took less than 1.5 seconds to analyze a network of 2,700 nodes. That's fast enough for real-world use!

Why Does This Matter?

Think of Sample Entropy as a "complexity thermometer."

Old Thermometer: Only worked on straight lines (time).
New Thermometer (SampEnG): Works on webs, networks, and maps.

This opens the door to analyzing all kinds of messy, real-world data:

Brain Networks: Is a brain in a seizure (too regular) or healthy (complex)?
Traffic Grids: Is a city's traffic flow chaotic or stuck in a predictable jam?
Social Media: Is a rumor spreading in a chaotic way or a controlled, predictable pattern?

In a nutshell: The authors built a bridge that lets us measure the "wildness" of data, whether that data is flowing in a straight river or swirling in a complex whirlpool of connections.

1. Problem Statement

Existing entropy-based methods for Graph Signal Processing (GSP), such as Graph Permutation Entropy, Dispersion Entropy, and Bubble Entropy, are effective but fundamentally limited. They rely on symbolic dynamics, which requires discretizing continuous signals to compute Shannon entropy. This discretization loses information inherent in continuous state spaces.

There is a need for a method that:

Generalizes Sample Entropy (SampEn)—a robust measure of irregularity and complexity in continuous time series—to graph signals.
Operates directly in a continuous state space without requiring signal discretization.
Accounts for the topological structure of graphs (non-Euclidean domains) rather than just temporal sequences.

2. Methodology: SampEnG

The authors propose SampEnG, a graph-signal generalization of Sample Entropy. The core innovation is replacing the temporal delay embedding used in classical SampEn with a multi-hop graph-based embedding.

Key Technical Components:

Graph Embedding via Shift Operators:
Instead of using time steps ( $t, t+1, \dots$ ), SampEnG uses graph hops. For a graph $G=(N, E, A)$ , the embedding is constructed using powers of the graph shift operator (the adjacency matrix $A$ or weighted matrix $W$ ).
- $L$ -hop Neighbors: The method identifies nodes reachable in exactly $L$ hops.
- Walk-Weighted Aggregates: For each node $i$ , the signal value at hop $L$ ( $x_i^L$ ) is computed as a weighted average of the $L$ -hop neighborhood:
  $x_i^L = \frac{1}{\text{deg}_L(i)} \sum_{j \in N_L(i)} (A^L)_{ij} x_j$
  where $\text{deg}_L(i)$ is the row sum of $A^L$ (total walks of length $L$ ).
Pattern Construction:
For each node $i$ , patterns of length $m$ and $m+1$ are constructed as vectors of these aggregated values:
- $x^m(i) = [x_i^0, x_i^1, \dots, x_i^{m-1}]$
- $x^{m+1}(i) = [x_i^0, x_i^1, \dots, x_i^m]$
- Constraint: The method restricts analysis to nodes with non-zero reachability up to $m$ hops to avoid undefined patterns in sparse graphs.
Entropy Calculation:
The algorithm follows the standard SampEn logic using Chebyshev distance:
1. Count the number of pattern pairs within a tolerance threshold $\epsilon = r \times \text{SD}$ (where SD is the standard deviation of the signal).
2. Compute $B_m(r)$ : The probability that two patterns of length $m$ match.
3. Compute $A_m(r)$ : The probability that two patterns of length $m+1$ match.
4. SampEnG Formula:
  $\text{SampEnG}(m, r, N) = -\ln \left( \frac{A_m(r)}{B_m(r)} \right)$

3. Key Contributions

Continuous State Space Analysis: Extends Sample Entropy to graph signals without discretization, preserving the continuous nature of the data.
Topological Awareness: Introduces a novel embedding mechanism that aggregates signal information based on graph topology (multi-hop neighborhoods) rather than time.
Theoretical Consistency: Proves that SampEnG reduces to classical 1D SampEn when applied to directed path graphs, ensuring backward compatibility.
Scalability: Demonstrates computational feasibility on large graphs (thousands of nodes) with practical runtimes.

4. Experimental Results

A. Validation on Logistic Map (Nonlinear Dynamics)

Setup: The logistic map ( $x_{t+1} = \rho x_t(1-x_t)$ ) was mapped onto directed and undirected path graphs.
Findings:
- Directed Paths: SampEnG perfectly replicated the behavior of classical 1D SampEn, correctly identifying the transition from order to chaos as the bifurcation parameter $\rho$ changed.
- Undirected Paths: The results closely tracked the trend of the directed case, successfully identifying bifurcation points and periodicity islands, though with slight quantitative differences due to the symmetric, non-causal neighborhood structure.
Conclusion: The method is sensitive to nonlinear dynamics and generalizes correctly to 1D signals.

B. Analysis on Erdős–Rényi (ER) Graphs

Setup: Directed ER graphs with $N=2700$ nodes. Node values were random uniform samples. Connectivity ( $p$ ) and pattern length ( $m$ ) were varied.
Findings:
- Connectivity vs. Entropy: As connectivity ( $p$ ) increased (making the graph denser), SampEnG decreased. This reflects increased regularity and predictability in the signal patterns due to higher connectivity.
- Pattern Length ( $m$ ): Higher $m$ values led to a faster drop in SampEnG as connectivity increased. This is because larger $m$ expands the neighborhood overlap, leading to homogenization of local patterns and reduced effective variability.
- Sparsity: In sparse networks, SampEnG showed higher values, indicating greater irregularity.
Performance: On an Apple M3 CPU, processing a graph of 2,700 nodes took approximately 295 ms ( $m=1$ ) to 1,400 ms ( $m=3$ ) per realization, confirming the method is computationally practical for large-scale networks.

5. Significance and Future Outlook

Generalization: SampEnG successfully bridges the gap between time-series complexity analysis and graph signal processing, offering a unified framework for conditional entropy on networks.
Applications: The method opens new avenues for analyzing complex network data in fields such as neuroscience (brain connectivity), social networks, and sensor networks where signals are defined over irregular topologies.
Future Work: The authors suggest exploring alternative graph embeddings, improving robustness to noise, and applying the method to real-world networked sensing domains.

In summary, SampEnG provides a rigorous, topology-aware tool for quantifying the irregularity of graph signals in continuous space, overcoming the limitations of symbolic discretization while maintaining the sensitivity to nonlinear dynamics characteristic of classical Sample Entropy.