A User Guide to Low-Pass Graph Signal Processing and Its Applications: Tools and Applications

The notion of graph filters can be used to define generative models for graph data. In fact, the data obtained from many examples of network dynamics may be viewed as the output of a graph filter. With this interpretation, classical signal processing tools, such as frequency analysis, have been successfully applied with analogous interpretation to graph data, generating new insights for data science. What follows is a user guide on a specific class of graph data, where the generating graph filters are low pass; i.e., the filter attenuates contents in the higher graph frequencies while retaining contents in the lower frequencies. Our choice is motivated by the prevalence of low-pass models in application domains such as social networks, financial markets, and power systems. We illustrate how to leverage properties of low-pass graph filters to learn the graph topology and identify its community structure; efficiently represent graph data through sampling; recover missing measurements; and denoise graph data. The low-pass property is also used as the baseline to detect anomalies.

A growing trend in signal processing and machine learning is to develop theories and models for analyzing data defined in irregular domains, such as graphs. Graphs often express relational ties, such as social, economic, and gene networks, for which several mathematical and statistical models relying on graphs have been proposed to explain trends in the data [1]. Another case is that of physical infrastructures (utility networks, including gas and water delivery, and transportation systems), where physical laws, in addition to connectivity, define the structure in signals.

For a period of time, the graphical interpretation was primarily used in statistics, with the aim of making inferences about graphical models. Meanwhile, the need for processing graph data has led to the emerging field of graph signal processing (GSP), which takes a deterministic and system theoretic approach to justify the properties of graph data and inspire the associated signal processing algorithms. A cornerstone of GSP is the formal definition of graph filter, which extends the notions of the linear time-invariant (LTI) filtering of time series signals to processing data that are defined on a graph as well as graph signals.