DS0705 - Fondements du numérique

Graph Signal Processing – GRAPHSIP

Graph Signal Processing for massive data analysis

Numerous data from the big data are often represented by graphs. Once vector data is associated with their nodes, one obtains what is called a graph signal. The processing of such graph signals faces several challenges because of the nature of the underlying information; combining graphs theoretical aspects with signal processing methods.

Graph Signal Processing – a rapidly expanding field

Massive datasets have now to be processed in many different application areas. These data are often represented by graphs to encode interactions. When data vectors are associated with graph vertices, a so-called graph signal is obtained. The processing of such graph signals faces several open challenges because of the nature of the involved information. In particular, this requires the extension of classical signal processing methods to irregular, non-Euclidean spaces. Regarding the huge success of classical signal processing tools, it appears essential to generalize their use to graph signals. The project aims at developing a set of advanced methods and algorithms for the processing of graph signals: graph inference, graph signal representation and variational problems on graphs. The project focuses on two emerging graph signals: brain networks and 3D color point clouds to make concrete the methodological advances on emerging applications.

The GRAPHSIP project is a fundamental research project in which a set of methods for processing signals on graphs is developed. The project considers three specific themes focusing on multi-scale representations on graphs (for graph signal representation), variational problems on graphs (for graph signal processing), and applications dedicated to graph signals. The first two themes aim at proposing the adaptation of signal processing techniques (based on harmonic analysis) and image processing techniques (based on variational problems) as well as their computer aspects (construction and optimization of the graph representation). The last theme concerns the application of the methods designed to graph signals that are far from the usual Euclidean grid and that represent difficult applications (computational neuroimaging with signals on brain graphs, computer vision with 3D color point cloud graphs).

The project produced many results in terms of
• Graph data representation: graph inference, graph filter banks, wavelets on directed graphs, semi-supervised learning on graphs.
• Graph data processing: efficient and distributed optimization schemes, evolution equations on graphs, mathematical morphology on graphs.
• Applications for image segmentation and restoration, discovery of interactions in gene networks, editing 3D point clouds, analysis of brain graphs and transportation networks.

The project made it possible to highlight the emerging theme of signal processing on graphs to the research community with the organization of numerous popularization actions and the organization of dedicated scientific events.

The project has resulted in the publication of 4 book chapters, 39 articles in international journals, 54 articles in international conferences, a summer school, thematic semesters and special sessions.

Massive datasets have now to be processed in many different application areas. These data are often represented by graphs to encode complex interactions. When data vectors are associated with graph vertices, a so-called graph signal is obtained. The processing of such graph signals faces several open challenges because of the nature of the involved information, combining graph studies using graph theory and signal and image processing methodologies. In particular, this requires new developments of classical signal processing methods to irregular, non Euclidean spaces. Regarding the huge success of classical signal processing tools, it appears essential to generalize their use to graph signals. The GRAPHSIP project aims at developing a set of advanced methods and algorithms for the processing of graph signals: multi-scale transforms and solutions of variational problems on graphs. The major outcomes of this project are expected to lead to significant breakthroughs for graph data processing. The project will focus also on two novel applications on instances of graph signals: brain networks and 3D color point clouds, so as to make actual the proposed methodological advances on emerging applications.

Project coordinator

Monsieur Olivier LEZORAY (UNIVERSITE DE CAEN - BASSE-NORMAND)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

UNICAEN UNIVERSITE DE CAEN - BASSE-NORMAND
ENSL Laboratoire de Physique, UMR CNRS 5672
GIPSA-lab GIPSA-lab CNRS UMR 5216
UPEM UNIVERSITE PARIS EST MARNE LA VALLE

Help of the ANR 498,508 euros
Beginning and duration of the scientific project: September 2014 - 42 Months

Useful links