Graph Signal Processing

Graph topologies play an important role in modern network applications, including sensor and communication networks, cyber-physical systems, transportation and logistics networks, social media networks, biological networks such as neural networks, gene regulatory networks, and colony networks of bacteria or insects. In contrast to conventional signal processing and data analysis applications that consider signals defined over time or space, these applications involve data, signals, and measurements indexed by graphs, i.e., the data is associated with the nodes of a graph. Graph signal processing (GSP) has the aim to develop signal processing tools and methods to manipulate measurements generated at the nodes or vertices of a graphs and to extract hidden information about the signals propagating though the graph or the underlying graph topology.

Recently, novel signal processing techniques have emerged under the paradigm of GSP. The Graph Fourier Transform (GFT) has been used as a tool to generalize the concepts originally defined in time series analysis of classical time signals such as spectral analysis, band limitation of signals, filtering, sampling, interpolation, and signal reconstruction, to signals defined over graphs. The GFT represents a link between the measurements on the graph and the graph topology. It can be understood as a generalization of the Discrete Fourier Transform to graph signals where, instead of the classical Fourier basis used in time series analysis, the eigenvectors of the adjacency matrix, or more generally the so-called graph shift operator, form the orthonormal basis. In this context, graph filters can be designed to extract, for example, the smooth signal components of the signals that diffuse over the graph. Under the assumption that the signals are sparse in the GFT domain, which is often the case in applications, sparse dictionary learning approaches can be used to infer hidden graph topology from observed network data. This is, for example, important for learning underlying topologies of gene regulatory networks and detecting hidden data dependencies and similarities in recommendation systems in streaming platforms and of social media networks.

In another line of research, nonlinear graph filters have been successfully applied in diverse learning tasks as a generalization of conventional multi-layer deep convolutional neural networks (CNNs) to artificial neural networks that use graph filters as fundamental building blocks. These so-called graph convolutional neural networks (GCNNs) have the benefit that they usually generalize well after training due to the prior information encoded upfront in the underlying graph structure. GCNNs can, for example, be used in resource allocation of interference networks to efficiently assign spectral resources and power to users in the network. In this application, the interference structure is encoded in the graph topology and used as prior information in the training phase. It turns out that the graph filter coefficients learned in the training phase with the training network can then also be utilized for decision making under other network topologies during network operation.

Further Reading

Fan, Yufan; Trinh-Hoang, Minh; Ardic, Cemil Emre; Pesavento, Marius: Decentralized Eigendecomposition for Online Learning Over Graphs With Applications. 2023, arXiv, doi:10.48550/arXiv.2209.01257, Official URL, [Preprint]

Liu, Tianyi; Hoang, Minh Trinh; Yang, Yang; Pesavento, Marius: A Block Coordinate Descent Algorithm for Sparse Gaussian Graphical Model Inference With Laplacian Constraints. In: IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing 2019, doi:10.1109/CAMSAP45676.2019.9022643, Official URL, [Conference item]

Yang, Yang; Scutari, Gesualdo; Palomar, Daniel P.; Pesavento, Marius: A Parallel Decomposition Method for Nonconvex Stochastic Multi-agent Optimization Problems. In: IEEE Transactions on Signal Processing 2016, 64, ISSN: 1941-0476, doi:10.1109/TSP.2016.2531627, [Article]

Yang, Yang; Pesavento, Marius; Zhang, Mengyi; Palomar, Daniel P.: An Online Parallel Algorithm for Recursive Estimation of Sparse Signals. In: IEEE Transactions on Signal and Information Processing over Networks 2016, 2, ISSN: 2373-776X, doi:10.1109/TSIPN.2016.2561703, [Article]

Suleiman, Wassim; Pesavento, Marius; Zoubir, Abdelhak M.: Performance Analysis of the Decentralized Eigendecomposition and ESPRIT Algorithm. In: IEEE Transactions on Signal Processing 2016, 64, ISSN: 1941-0476, doi:10.1109/TSP.2016.2523448, [Article]

Suleiman, Wassim; Parvazi, Pouyan; Pesavento, Marius; Zoubir, Abdelhak M.: Non-coherent Direction-of-arrival Estimation Using Partly Calibrated Arrays. In: IEEE Transactions on Signal Processing 2018, 66, ISSN: 1941-0476, doi:10.1109/TSP.2018.2867997, [Article]