Jelena Kovačević: Research: Algebraic theory of signal processing (SMART)

discrete signal processing on graphs

Discrete signal processing on graphs was started by Aliaksei Sandryhaila and J. M. F. Moura, inspired from the previous work of algebraic signal processing theory. The goal is to formulate a theoretical framework that generalizes classical discrete signal processing from regular domains, such as lines and rectangular lattices, to arbitrary, irregular domains commonly represented by graphs. Different from network science, discrete signal processing on graphs focuses on the interplay between the graph structure and the corresponding signals. The goal of this research is to build a theoretical foundation from the perspective of signal processing to handle practical data analysis tasks. Our current work focuses on understanding and formulating such a framework for signal representations and signal recovery on graphs.

overview

representations

The task of representations has always been at the heart of most signal processing techniques. It considers describing similar signals by using a mathematical model. In classical signal processing, space-time-frequency representations lay the foundation for analyzing time-series signals and images. Here we consider constructing appropriate models for graph signals. For example, how to model profile data indexed by online social networks or traffic data index by the city traffic networks? Currently, we are studying three graph signal models: smooth model, piecewise-constant model and piecewise-smooth model.

experimentally designed graph dictionary (multiscale approach)

We present a framework for representing and modeling data on graphs. Based on this framework, we study three typical classes of graph signals: smooth graph signals, piecewise-constant graph signals, and piecewise-smooth graph signals. For each class, we provide an explicit definition of the graph signals and construct a corresponding graph dictionary with desirable properties. The main idea of constructing a graph dicitonary is to decompose the vertex domain in a multiscale fashion. We then study how such graph dictionary works in two standard tasks: approximation and sampling followed with recovery, both from theoretical as well as algorithmic perspectives. Finally, for each class, we present a case study of a real-world problem by using the proposed methodology.

S. Chen, T. Ji, R. Varma, A. Singh, and J. Kovačević, Signal representations on graphs: Tools and applications." IEEE Trans. Signal Process., 2016. Submitted.

S. Chen, R. Varma, A. Singh, and J. Kovačević, Representations of piecewise smooth signals on graphs." In Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Shanghai, Mar. 2016.

graph dictionary learning

sampling & recovery

Sampling is about extracting information from graph signals, recovery is about reconstructing the orignal graph signals from limited information. Many sampling frameworks have been proposed during the 60 years after Shannon, and this one focuses on signals that have specific properties on any given graph structure. Currently, we are studying two graph signal models, inluding the bandlimited model and the small variation model. The bandlimited model leads to sampling theory on graphs, and the small variation model, as a relaxation of the bandlimited model, leads to signal recovery on graphs. The goal of this work is to build a theoretical foundation for semi-supervised learning on graphs from the perpective of signal processing.

sampling theory for graph signals

We study a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that the perfect recovery is possible for graph signals bandlimited under the graph Fourier transform, and the sampled signal coefficients form a new graph signal, whose corresponding graph structure is constructed from the original graph structure, preserving frequency contents. We further establish the connection to frames withmaximal robustness to erasures as well as compressed sensing, and show how to choose the optimal sampling operator, how random sampling works on circulant graphs and Erdos-Renyi graphs, and how to design graph filter banks based on this sampling theory.

S. Chen, R. Varma, A. Singh, and J. Kovačević, Signal recovery on graphs: Fundamental limits of sampling strategies." IEEE Trans, Signal and Inform. Process. over Networks, 2016. Submitted.

S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, Discrete signal processing on graphs: Sampling theory." IEEE Trans. Signal Process., 2015.

S. Chen, A. Sandryhaila, and J. Kovačević, Sampling theory for graph signals." In Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Brisbane, Apr. 2015.

signal recovery on graphs

We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a corresponding optimization problem. We provide a general solution by using the alternating direction methods of multipliers. We next show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery, and provide corresponding specific solutions and theoretical analysis. Finally, we validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system, and expert opinion combination of online blog classification.

R. Varma, S. Chen and J. Kovačević, Spectrum-blind signal recovery on graphs, IEEE CAMSAP, Cancun, Mexico, Dec. 2015.

S. Chen, R. Varma, A. Singh and J. Kovačević, Signal recovery on graphs: Random versus experimentally designed sampling, SampTA 2015, Washington, D.C., May, 2015.

S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, Signal recovery on graphs: Variation Minimization." IEEE Trans. Signal Process., 2015. To appear.

S. Chen, A. Sandryhaila, and J. Kovačević, Distributed algorithm for graph signal inpainting." In Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Brisbane, Apr. 2015.

S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, Signal denoising on graphs via graph filtering." In Proc. IEEE Glob. Conf. Signal Information Process., Atlanta, GA, Dec. 2014.

S. Chen, A. Sandryhaila, G. Lederman, Z. Wang, J. M. F. Moura, P. Rizzo, J. Bielak, J. H. Garrett, and J. Kovačević, Signal inpainting on graphs via total variation minimization." In Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Florence, May 2014.

filtering

Graph filtering is about diffusing information on graphs. The most elementary graph filter is called graph shift. A graph shift operator diffuses the value at each vertex to its neighbors. Because of the locality in nature, graph filtering can promote efficient algorithms.

fast algorithms based on graph filtering

We present a distributed algorithm for graph signal recovery. Instead of computing a closed-form solution with matrix inversion, we ease the computation by using a distributed algorithm, which solves graph signal recovery by restricting each node to communicate only with its local nodes. We show that the solution of the distributed algorithm converges to the closed-form solution with the corresponding convergence speed. Since a distributed algorithm does not require to collect data to a center, it is more practical and efficient.

S. Chen, A. Sandryhaila, and J. Kovačević, Distributed algorithm for graph signal inpainting." In Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Brisbane, Apr. 2015.

S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, Signal denoising on graphs via graph filtering." In Proc. IEEE Glob. Conf. Signal Information Process., Atlanta, GA, Dec. 2014.

adaptive filtering design

We present a multiresolution classification framework with semi-supervised learning on graphs. Classification in real-world applications faces two main challenges: reliable features can be hard to extract and few labeled signals are available for training. We propose a novel classification framework to address these problems: we use a multiresolution framework to deal with nonstationarities in the signals and extract features in each localized time-frequency region and semi-supervised learning to train on both labeled and unlabeled signals. We further propose an adaptive graph filter for semi-supervised classification that allows for classifying unlabeled as well as unseen signals and for correcting mislabeled signals. Adaptive graph filters combine decisions from multiple graph filters using a weighting function that is optimized in a semi-supervised manner. We also demonstrate the multiresolution property of adaptive graph filters by connecting them to the diffusion wavelets.

S. Chen, F. Cerda, P. Rizzo, J. Bielak, J. H. Garrett, and J. Kovačević, Semi-supervised multiresolution classification using adaptive graph filtering with application to indirect bridge structural health monitoring." IEEE Trans. Signal Process., 2014.

S. Chen, A. Sandryhaila, J. M. F. Moura and J. Kovačević, Adaptive graph filtering: multiresolution classification on graphs." In Proc. IEEE Glob. Conf. Signal Information Process., Austin, TX, Dec. 2013.

detection & localization

The task of detection is to test whether or not a graph signal activates a structure-correlated pattern in a graph when observations are corrupted by noise. This task is relevant to many applications in- cluding identifying clustered attributes in social networks, special events in the urban traffic networks, unusual brain activity in the brain connectivity networks, and viruses in cyber-physical systems.

Bernoulli noise model

Do users from Carnegie Mellon University form social communities on Facebook? In this paper, we focus on a task of detecting structure-correlated attributes on a graph. A structure-correlated attribute means that the node set activated by the attribute form a community in the graph. This task is relevant to many applications including identifying structure- correlated attributes in social networks, special events in the urban traffic networks, unusual brain activity in the brain connectivity networks, and viruses in cyber-physical systems. To solve this task, we formulate a statistical hypothesis testing to decide if the given attribute activates a community in a graph with interfering by the Bernoulli noise. We propose two statistics: graph wavelet statistic and graph scan statistic. Both are shown to be efficient and statistically effective to detect activations. The intuition behind the proposed statistics is that we study the interaction between graph structure and the given attribute, that is, we denoise the attribute based on the graph structure and localize the underlying community in the graph. We then test the proposed hypothesis tests on simulated data to validate the effectiveness and robustness of the proposed methods. We further apply the proposed methods to two real-world applications: high air pollution detection and ranking attributes for community detection in a coauthorship network collected from IEEE Xplore. The experimental results show that the proposed graph wavelet statistic and graph scan statistic are effective and efficient.

S. Chen, Y. Yang, A. Singh and J. Kovačević, Detecting structure-correlated attributes on graphs, IEEE Trans. Signal Process., 2016. Submitted.

applications

Discrete signal processing on graphs provides a platform to handle signals with irregular, complex structures by using classical signal processing tools. With the explosive growth of information and communication, such signals are being generated at an unprecedented rate from various sources, including social networks, citation, biological, and physical infrastructure. We are considering various applications, such as structural health monitoring, online blog classification, temperature estimation, and recommender system.

Route planning

We employ techniques from work done on graph signal recovery to plan routes for autonomous aerial vehicles. We propose an algorithm that generates an energy-efficient flight trajectory by considering wind velocity data, which is represented with a graph structure. Instead of processing the entire wind dataset, we instead only query a part of the wind velocity data and recover the rest using a novel graph signal recovery algorithm. The proposed algorithm solves an optimization problem. We show that the proposed algorithm is a generalization of the optimal sampling operator in sampling theory for graph signals, and it is additionally computationally efficient to implement. We validate the pro- posed algorithm on real wind velocity data and show that it produces a reliable and energy-efficient route.

T. Ji, S. Chen, R. Varma and J. Kovačević, Efficient route planning of autonomous vehicles based on graph signal recovery, Allerton, Monticello, IL, Oct. 2015.

recent talks

From biomedical imaging to online blogs: Graph signal processing
Discrete signal processing on graphs: inpainting