Traditional signal-processing is based on the idea that the information is supported on a regular structure. For example, the noisy records of a single sensor over time rely on a very strong structure: “time”. Building hypotheses like “The signal shall not change too quickly” on this structure, we can design algorithms to enhance our measurements by removing the noise (with a low-pass filter for example (See Figure 1)).
However, in many cases the information does not have a regular structure. For instance, imagine that instead of having only one temperature sensor, we have many placed at different random points in the space. Instead of time, the structure here is the space. However, it is irregular because the sensors are not distributed on a grid. In this case, the solution is to create a graph that would capture the structure of the data. To do this, we connect the nearest sensors together. The connections model the fact that close sensors should have similar values because the temperatures cannot change abruptly in space. With this construction, we can use a graph algorithm to remove the noise of the sensor array (See Figure 2).
Graph signal processing is a special area in signal processing based on spectral graph theory where the data possess an intrinsic graph structure. Social networks are one of the most common examples of such data since the graph is simply provided by the users themselves. Nevertheless, most of the time this does not happen and the graph is constructed directly from the data or from additional information. The graphs are usually used to discretize the abstract domain of the data and build accurate representations of them. Common tasks in signal-processing on graphs include filtering, de-noising, in-painting, compression, clustering, partitioning, sparsification, features extraction, classification and regression. Almost all signal-processing tools have been generalized to graphs, thus allowing them to be used on irregular data structures. The range of applications cannot be enumerated but contains, among others, automatic text classification, Internet page ranking, digit classification and movie recommendations.