Entropy metrics for graph signals

Entropy metrics (for example, permutation entropy) are nonlinear measures of irregularity in time series (1-dimensional data). These entropy metrics can be generalised to data on periodic structures (such as a grid or lattice pattern) using its symmetry, thus enabling their application to images. However, these metrics have not been developed for signals settled on irregular domains, defined by a graph. In this work, we define for the first time an entropy metric to analyse signals measured over irregular graphs by generalising permutation entropy, a well established nonlinear metric based on the comparison of neighbouring values within patterns in a time series, to data on general graphs. Our algorithm is based on the idea of comparing signal values on neighbouring nodes (using the adjacency matrix). We show that this generalisation preserves the properties of classical permutation for time series, and it can be applied to any structure with synthetic and real graphs.