Post date: 21-oct-2015 16:29:45
Title: Graph Signal Processing: Fundamentals and Applications to Modelling Network Dynamics. Part I-- Fundamentals.
Date: 26 - Oct - 2015
Aula: 3S3 Aulario III
Material: pdf slides, video
Speaker: Antonio García Marqués (URJC)
Abstract: Over the past decade there has been a growing interest in understanding the complex connectedness of modern society. As modern interconnected systems grow in size and importance, while they become more complex and heterogeneous, there is an urgent need to advance a holistic theory of networks. A network can be understood as a complex system formed by multiple nodes, where global network behaviour arises from local interactions between connected nodes. More succinctly, networks and graphs can be defined as structures that encode relationships between pairs of elements of a set. The simplicity of this definition drives the application of graphs and networks to a wide variety of disciplines such as biology, sociology, economics, engineering, or computer science. Often, networks have intrinsic value and are themselves the object of study. In other occasions, the network defines an underlying notion of proximity, but the object of interest is a signal defined on top of the graph, i.e., data associated with the nodes of the network. This is the matter addressed in the field of graph signal processing (GSP), where the notions of, e.g., frequency and linear filtering are extended to signals supported on graphs.
Motivated by the previous issues, we will deliver a two-hour talk on GSP and some of its applications to model and analyze network dynamics. The talk will be organized as follows.
In the first session, we will lay down the foundations of GSP. We will introduce the concepts of graph signal, graph shift operator and graph filter, together with their frequency interpretations. Differences and similarities with respect to traditional discrete signal processing will be discussed. A key insight is that graph filters represent linear transformations between graph signals that can be implemented via local interactions among network nodes, and they are well-suited to model e.g., diffusion or percolation processes in the network.
In the second session, we will apply the previous tools to address two relevant GSP problems. The first one is the problem of sampling bandlimited graph signals. Most of the works that have looked at this problem focus on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, we propose a sampling scheme that uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the values of the signal in the neighborhood of the sampling node. Conditions for perfect recovery are given and, when noise is present, schemes that minimize the reconstruction error are provided. The second problem is the (joint) blind identification of graph filters and sparse inputs. The goal in this case is to identify the filter coefficients and the values of the input, given only an observed (output) graph signal. This is of interest, for example, in social networks where an opinion profile is given and the objective is to identify those influential actors that instilled the observed status-quo. At a fundamental level, this effort broadens the scope of classical blind system identification to networks, or, of blind deconvolution of temporal and spatial signals to less structured graph domains.