Graph Signal Processing: Foundations and Emerging Directions

Ours is a connected world where unprecedented quantities of data are being generated, recorded, and processed. Generically, the networks that sustain our societies can be understood as complex systems formed by multiple nodes, where global network behavior arises from local interactions between connected nodes. More succinctly, a network or a graph can be defined as a structure that encodes relationships between pairs of elements of a set. The simplicity of this definition drives the application of graphs and networks to a wide variety of disciplines, such as biology, medicine, psychology, sociology, economics, engineering, computer science, and so on [2]. Often, networks have intrinsic value and are themselves the object of study. On other occasions, the network defines an underlying notion of proximity, but the object of interest is the information defined on top of the graph, i.e., data associated with the nodes of the network.

Graph signal processing (GSP) has approached this problem by modeling the structure of the data using a graph and then viewing the available information as a signal defined on it. A plethora of graph-supported signals exists in different engineering and scientific fields, with examples ranging from gene-expression patterns defined on gene networks; the spread of epidemics, rumors, or memes over a population; or the congestion level at the nodes of a telecommunication network, to name a few. More generally, GSP arises in a broad set of application domains, from social networks to the business and corporate worlds and from health care to critical cyberphysical infrastructures.

Transversal to the particular application, the SP community can contribute to the advancement of the understanding of network data by redesigning traditional tools originally conceived to study signals defined on regular domains (such as time-varying signals) and extend them to analyze signals on the more complex graph domain. This leads to the development of new signal models, data analytics, and algorithms that, by incorporating the underlying network structure, provide the opportunity for gains in the accuracy and efficiency of processing the relevant information present in the network data. In this context, the theoretical and practical success achieved by GSP in the last few years has been noticeable and includes, for example, the generalization of tools such as frequency analysis, filtering, sampling, or statistical stationarity to signals supported on graphs [3], along with their practical use in applications as important as video processing and neuroscience [4], [5]. Nonetheless, many issues remain open, with, e.g., robust, nonlinear, or higher-dimensional GSP being at their infancy. This status is, of course, not surprising. Human knowledge about time-varying signals and images was developed over the course of decades and boosted by real needs in areas such as communications, speech, video, or control. In contrast, the prevalence of network-related SP problems and access to quality network data are recent phenomena. However, the explosion of available network data is generating a pressing need to better understand and process information in network settings that is expected to not only foster the development of GSP but to also cement its relevance via its application to a growing number of problems.