Graph Spectral Image Processing

2Graph Learning

Xiaowen DONG¹, Dorina THANOU², Michael RABBAT³, Pascal FROSSARD² 1University of Oxford, UK

²École polytechnique fédérale de Lausanne, Switzerland ³Facebook, Montreal, Canada

2.1. Introduction

Modern data analysis and processing tasks typically involve large sets of structured data, where the structure carries critical information about the nature of the data. Numerous examples of such data sets can be found in a wide diversity of application domains, including transportation networks, social networks, computer networks and brain networks. An image, which consists of a regular array of pixels, is also a special form of structured data. Typically, graphs are used as mathematical tools to describe the underlying data structure, as they provide a flexible way of representing relationships between data entities. Numerous signal processing and machine learning algorithms have been introduced in the past decade for analyzing structured data on a priori known graphs (Zhu 2005; Fortunato 2010). However, there are often settings where the graph is not readily available, and the structure of the data has to be estimated in order to permit effective representation, processing, analysis or visualization of graph data. Furthermore, the pairwise relationships between data entities encoded in the format of graphs are often the goal of analysis. In both cases, a crucial task is to infer a graph topology that describes the characteristics of the data observations, hence capturing ...