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

Probleemstelling

Bestaande methoden voor de analyse van graf-signalen (Graph Signal Processing - GSP), zoals Permutation Entropy, Dispersion Entropy en Bubble Entropy, zijn effectief maar hebben een fundamentele beperking: ze zijn gebaseerd op symbolische dynamica. Dit betekent dat de signalen eerst moeten worden gediscretiseerd om de Shannon-entropie te kunnen berekenen. Hierdoor gaan continuïteitsinformatie en fijne nuances in de signaalwaarden verloren.

Er bestaat een behoefte aan een methode die de irreguliere complexiteit van graf-signalen kan kwantificeren in een continu toestandsruimte, vergelijkbaar met hoe Sample Entropy (SampEn) werkt voor tijdreeksen, maar dan aangepast voor de topologische structuur van netwerken.

Methodologie: SampEnG

De auteurs introduceren SampEnG (Sample Entropy for Graph signals), een generalisatie van de klassieke Sample Entropy voor graf-signalen. De kern van de methode is het vervangen van de temporale vertraging (time-delay embedding) door een multi-hop graf-embedding.

De belangrijkste stappen in de methode zijn:

1. Graf-embedding via Shift Operator: In plaats van opeenvolgende tijdstippen, worden patronen opgebouwd door lokale aggregaties van het signaal rondom een knoop te analyseren op basis van het aantal "hops" (stappen) in de graf.

   • Voor een knoop $i$ wordt een patroonvector $x^m(i)$ gedefinieerd met componenten $x^0_i, x^1_i, \dots, x^{m-1}_i$.
   • $x^0_i$ is de signaalwaarde op de knoop zelf.
   • $x^L_i$ is een loop-gewogen gemiddelde van de $L$-hop-buurschappen, berekend via machten van de graf-shift operator (de adjacentiematrix $A$ of gewogen matrix $W$).
   • Formule: $x^L_i = \frac{1}{\text{deg}_L(i)} \sum_{j \in N_L(i)} (A^L)_{ij} x_j$, waarbij $\text{deg}_L(i)$ het aantal paden van lengte $L$ is.

2. Patroonmatching:

   • Er worden patronen van lengte $m$ en $m+1$ geconstrueerd voor elke knoop.
   • De overeenkomst tussen patronen wordt gemeten met de Chebyshev-afstand binnen een tolerantie $\epsilon = r \times \text{SD}$ (standaarddeviatie).
   • Er worden tellingen gemaakt van hoe vaak patronen binnen deze drempel overeenkomen ($B_m(r)$ voor lengte $m$ en $A_m(r)$ voor lengte $m+1$).

3. Berekening van Entropie:

   • De SampEnG wordt berekend als de negatieve logaritme van de verhouding tussen deze tellingen:
     $$\text{SampEnG}(m, r, N) = -\ln \left( \frac{A_m(r)}{B_m(r)} \right)$$
   • Een hogere waarde duidt op meer onregelmatigheid (complexiteit), terwijl een lagere waarde meer regelmaat of voorspelbaarheid aangeeft.

Belangrijkste Bijdragen

• Generalisatie van SampEn: De eerste toepassing van Sample Entropy op graf-signalen in een continue ruimte, zonder discretisatie naar symbolen.
• Topologie-bewust Embedding: Een nieuwe manier om patronen te definiëren die de connectiviteit en de lokale structuur van de graf (via powers of the adjacency matrix) integreert.
• Validatie op 1D en Netwerken: Het bewijzen dat de methode terugvalt op de klassieke 1D SampEn op gerichte pad-grafen, en het testen op willekeurige netwerken (Erdős–Rényi).

Resultaten

De auteurs hebben de methode getest in twee scenario's:

1. Logistische Kaart (Logistic Map):

   • Gebruikt om de gevoeligheid voor niet-lineaire dynamica (overgang van orde naar chaos) te testen.
   • Op gerichte pad-grafen (waarbij $i \to i+1$) reproduceerde SampEnG exact de resultaten van de klassieke 1D SampEn.
   • Op ongerichte pad-grafen volgde het de algemene trend correct, inclusief het identificeren van bifurcatiepunten en periodiciteits-eilanden, met kleine kwantitatieve verschillen door de niet-causale, symmetrische buurschapsstructuur.

2. Erdős–Rényi (ER) Grafen:

   • Getest op gerichte ER-grafen met $N=2700$ knopen en variërende connectiviteit ($p$) en patroonlengte ($m$).
   • Connectiviteit: Bij schaarse netwerken (lage $p$) neemt SampEnG af naarmate de connectiviteit toeneemt, wat overeenkomt met een toename in regelmaat en voorspelbaarheid.
   • Dichtheidseffect: Bij dichte netwerken en grotere $m$ nadert SampEnG nul. Dit komt doordat de lokale buurschappen gaan overlappen en homogeniseren, waardoor de variabiliteit in patronen afneemt.
   • Rekentijd: De methode is computatieel haalbaar; voor $N=2700$ knopen werd een verwerkingstijd van ongeveer 295 ms (voor $m=1$) tot 1400 ms (voor $m=3$) per realisatie gemeten op een Apple M3 CPU.

Betekenis en Toekomstperspectief

SampEnG opent nieuwe wegen voor de analyse van netwerkgedata door de concepten van conditionele entropie en niet-lineaire analyse uit te breiden naar een breed scala aan netwerkstructuren. Het biedt een robuust instrument om de complexiteit van signalen op netwerken te meten zonder informatie te verliezen door discretisatie.

Toekomstig werk richt zich op:

• Het verkennen van alternatieve graf-embeddings.
• Het testen van de robuustheid tegen ruis in graf-signalen.
• Toepassing op real-world netwerkbewakingssystemen (networked sensing domains).