Graph based data or data indexed by nodes of a graph are of increasing importance in our modern digital world. The (connected, simple) indexing graphs are arbitrary (directed or undirected) and capture dependencies among the data. A new discipline, Graph Signal Processing (GSP), has emerged in the last 10 years to extend methods commonly used with time series and images to graph data. The basic building block is the adjacency matrix A of the graph (or, for undirected graphs, also the graph Laplacian). For example, spectral data analysis follows from the eigen decomposition of A, graph filters are polynomials of A, and graph deep models replace conventional convolution in CNNs by graph filtering.
There has been significant research extending to GSP many common traditional operations, usually, through inspiration and hard work. Sometimes, these extensions do not conform to the traditional time series methods, which of course is undesirable. In this seminar, we consider the graph companion model where the companion graph reproduces the structure of the time graph (directed cycle graph) modified with appropriate boundary conditions. The companion model unwinds the role of the spectral (eigen) graph modes and powers of the vector of graph spectral frequencies λn that coincide for time signals. This enables a two-step systematic methodology to develop novel GSP processing methods: 1) Adopt in the companion model the conventional time signal method modified by the GSP boundary condition – here, the λn play the main role; and 2) Obtain the method in the usual vertex representation of data by applying the transformation between the companion and the vertex data representations – now the eigenvectors play the main role. We illustrate the method with several novel GSP operations.
José M. F. Moura is the Philip L. and Marsha Dowd University Professor at CMU, with interests in distributed, geometric, and graph signal processing and learning. A detector in two of his patents with Alek Kavcic is found in over 60% of the disk drives of all computers sold worldwide in the last 15 years (4 billion and counting)–leading in 2016 to a US $750 Million settlement between CMU and Marvell. He was the 2019 IEEE President and CeO. He is Fellow of the IEEE, AAAS, and the US National Academy of Inventors, holds honorary doctorates from the University of Strathclyde and Universidade de Lisboa, he is a member of the Academy of Sciences of Portugal, and a member of the US National Academy of Engineering. He received the Great Cross of the Order of The Infante D. Henrique bestowed to him by the President of the Republic of Portugal. He is the recipient of the 2023 IEEE Kilby Signal Processing Medal.