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

Resumo Técnico: Entropia Amostral para Sinais em Grafos (SampEnG)

Título: Sample entropy for graph signals: An approach to nonlinear analysis of graph signals (Entropia amostral para sinais em grafos: Uma abordagem para análise não linear de sinais em grafos)
Autores: Mei-San Maggie Lei, John Stewart Fabila Carrasco, Javier Escudero.

1. O Problema

A análise de sinais em grafos (Graph Signal Processing - GSP) tem visto o desenvolvimento de métodos baseados em entropia, como Entropia de Permutação, Entropia de Dispersão e Entropia de Bolha. No entanto, essas abordagens atuais possuem uma limitação fundamental: elas dependem da dinâmica simbólica, o que exige a discretização do sinal para calcular a entropia de Shannon. Isso impede a análise direta de sinais em espaços de estado contínuos.

A Entropia Amostral (SampEn) clássica é uma ferramenta poderosa para medir a irregularidade e complexidade de séries temporais em espaços contínuos, estimando a probabilidade de recorrência condicional. Contudo, não existia uma generalização direta da SampEn para sinais definidos sobre grafos, o que limitava a aplicação de técnicas de análise não linear a dados de rede complexos.

2. Metodologia: SampEnG

Os autores propõem o SampEnG (Sample Entropy for Graph Signals), uma generalização da SampEn clássica que substitui o atraso temporal (temporal delay) por uma incorporação baseada em saltos no grafo (multi-hop graph-based embedding).

• Conceito Central: Em vez de observar pontos consecutivos no tempo, o método agrega padrões a partir de vizinhanças locais ponderadas por caminhadas (walks) no grafo.
• Construção do Padrão:
  • Para cada nó $i$, constrói-se um vetor de padrão $x^m(i)$ de dimensão $m$.
  • O componente $x^0_i$ é o valor do sinal no próprio nó.
  • Os componentes subsequentes ($x^L_i$) representam a média ponderada por caminhadas da vizinhança a uma distância de $L$ saltos (hops).
  • Matematicamente, utiliza-se potências do operador de deslocamento do grafo (matriz de adjacência $A$ ou ponderada $W$). O valor $x^L_i$ é calculado como a média dos sinais dos nós alcançáveis em exatamente $L$ passos, ponderada pelo número de caminhadas possíveis.
• Cálculo da Entropia:
  • Define-se um limiar de tolerância $\epsilon = r \times SD$ (desvio padrão do sinal).
  • Calcula-se a probabilidade de que padrões de comprimento $m$ sejam similares (dentro da distância de Chebyshev $\epsilon$) e estenda-se essa comparação para padrões de comprimento $m+1$.
  • A SampEnG é definida como o logaritmo negativo da razão entre a contagem de coincidências para $m+1$ e para $m$:
    $$\text{SampEnG} = -\ln \left( \frac{A_m(r)}{B_m(r)} \right)$$
  • Restrições: O método considera apenas nós que possuem conectividade (grau > 0) até $m$ saltos para evitar padrões indefinidos em grafos esparsos.

3. Contribuições Principais

1. Generalização Contínua: Introdução de uma medida de entropia condicional contínua para sinais em grafos, superando a necessidade de discretização simbólica exigida por métodos anteriores.
2. Incorporação Topológica: Substituição do atraso temporal pela estrutura de hops do grafo, permitindo capturar a dependência espacial e a topologia da rede na análise de complexidade.
3. Validação Teórica e Prática: Demonstração de que o método reduz-se à SampEn 1D clássica em grafos de caminho direcionados e validação da sua sensibilidade a dinâmicas não lineares.

4. Resultados Experimentais

• Mapa Logístico (Validação de Redução):

  • O algoritmo foi testado em grafos de caminho direcionados e não direcionados, simulando o mapa logístico (um modelo clássico de caos).
  • Resultado: O SampEnG em grafos direcionados replicou perfeitamente a curva da SampEn 1D clássica, identificando corretamente as transições ordem-caos e ilhas de periodicidade. Em grafos não direcionados, a tendência geral foi mantida, com pequenas diferenças quantitativas devido à simetria da vizinhança.

• Grafos de Erdős–Rényi (ER) Direcionados:

  • Testes realizados em grafos aleatórios com $N=2700$ nós, variando a conectividade (grau de saída médio $K$) e o comprimento do padrão ($m$).
  • Eficiência Computacional: O método é prático para redes de grande escala. Para $N=2700$, os tempos de execução variaram de ~295 ms ($m=1$) a ~1400 ms ($m=3$) por realização em hardware moderno (Apple M3).
  • Comportamento com Conectividade:
    • Em redes esparsas (baixa conectividade), a SampEnG diminui à medida que a conectividade aumenta, refletindo maior regularidade topológica.
    • Em redes densas, a SampEnG tende a zero. Isso ocorre porque o aumento dos saltos ($m$) e da densidade cria sobreposições massivas nas vizinhanças locais, homogeneizando os padrões e reduzindo a variabilidade efetiva que a entropia consegue explorar.

5. Significado e Conclusão

O SampEnG representa um avanço significativo na análise de dados de rede, permitindo a aplicação de conceitos de entropia condicional e análise não linear a uma vasta gama de dados de rede que não podem ser tratados como séries temporais lineares.

• Aplicabilidade: O método é sensível a transições de ordem para caos e à estrutura de conectividade da rede.
• Futuro: Os autores sugerem que o trabalho abre caminho para o uso de outras incorporações de grafos, análise de robustez a ruído e aplicações em domínios de sensoriamento de rede real.

Em suma, o SampEnG generaliza a análise de complexidade de sinais unidimensionais para o domínio de grafos, oferecendo uma ferramenta robusta para quantificar a irregularidade em dados estruturados em rede sem a perda de informação inerente à discretização simbólica.