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.