Vous êtes ici : Réunions » Réunion

# Identification

Identifiant:
Mot de passe :

Mot de passe oublié ?
Détails d'identification oubliés ?

# Apprentissage et/ou traitement du signal et des images sur graphes

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

## Inscriptions

32 personnes membres du GdR ISIS, et 24 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.

## Annonce

Les graphes sont des structures discrètes qui permettent de représenter efficacement des relations entre entités, telles que par exemple la proximité de noeuds dans des réseaux de capteurs ou de communication, l'adjacence de pixels dans des images, la corrélation de signaux, des relations dans des réseaux biologiques, sociaux ou technologiques, ou plus généralement des similarités au sens d'une métrique appropriée pour les données considérées (collections d'images, de signaux, données sociales numériques, etc.).

Le codage de telles relations par des graphes constitue une ouverture vers de nouveaux problèmes en apprentissage statistique, pour la classification non-supervisée ou semi-supervisée, l'apprentissage de variétés, les systèmes recommandation, etc. De même, des concepts et outils classiques du traitement du signal et des images sont à présent déployés sur des structures de graphes. Ces idées ont connu un rapide essor ces dernières années au travers du développement d'outils d'échantillonnage de signaux sur graphe, de représentation spectrale, de débruitage, la définition de bancs de filtres, de bases ou de dictionnaires redondants sur graphe, etc.

Beaucoup de questions et méthodes classiques en traitement du signal et des images restent à être ré-envisagées au jour de données indexées sur des graphes. Ceci implique aussi de se pencher sur certaines propriétés des structures de graphe (régularité, évolution au cours du temps, etc.) et outils d'analyse (matrices aléatoires, etc.), sur l'implémentation efficace d'algorithmes de traitement pour un passage à l'échelle, la distribution d'algorithmes sur les noeuds d'un graphe, etc.
L'objectif de cette journée du GDR ISIS est de confronter les points de vue sur l'analyse et le traitement de données sur ou codées par des graphes. Un appel à communication est ouvert dans tous les domaines décrits dans la présentation de cette journée, plus particulièrement en apprentissage statistique sur graphes et/ou en traitement du signal (ou des images) sur des graphes.

Cette journée contient trois exposés invités
- Hamid Krim (NC State University Raleigh, USA), dans le cadre de ses activités de Distinguished Lecturer de la IEEE Signal Processing Society :
"Convexity, Sparsity, Nullity and all that....in Data Analysis"
- Romain Couillet (Centrale-Supelec, L2S, CNRS, Univ. Paris-Sud) :
"Random Matrices in Machine Learning"
- Nicolas Tremblay (Inria Rennes, projet PANAMA & EPFL, LTS2)
"Compressive Spectral Clustering and Sampling of Graph Signals"
et des exposés suite à l'appel à communication, selon le programme ci-dessous.

### Organisateurs

(Action "Signaux & Images sur graphes" du thème A) :

• Pierre Borgnat (CR CNRS, Laboratoire de Physique, ENS de Lyon, CNRS, Université de Lyon, Lyon)
• Cédric Richard (PU 61, Laboratoire Lagrange, Observatoire de la Côte d'Azur, CNRS, Université de Nice Sophia-Antipolis, Nice)

## Programme

Programme :

10h00 Présentation de la journée
10h15 Romain Couillet (Centrale-Supelec, L2S, CNRS, Univ. Paris-Sud) : "Random Matrices in Machine Learning"
11h15 Emilie Kauffman* (joint work with Thomas Bonald and Marc Lelarge) : "A novel spectral algorithm for the identification of overlapping communities in networks"
11h35 Aurélie Pirayre*, Camille Couprie, Laurent Duval and Jean-Christophe Pesquet (IFP Energies Nouvelles; Facebook AI Research; LIGM, CNRS, Université Paris Est) : "Gene Regulatory Network inference refinement using clustering"
11h55-13h30 Repas
13h30 Hamid Krim (NC State University Raleigh, USA), dans le cadre de ses activités de Distinguished Lecturer de la IEEE Signal Processing Society : "Convexity, Sparsity, Nullity and all that....in Data Analysis"
14h30 Michel Barlaud* (Université Nice Sophia-Antipolis, I3E, UMR CNRS) , Wafa Belhajali, Patrick L. Combettes, Lionel Fillatre : "Classification and regression using constrained convex splitting method; Lasso or Graph regularization ?"
14h50 Pierre Weiss (ITAV USR-3505), Paul Escande* (ISAE Toulouse), Yiqiu Dong (Technial University of Denmark) : "Changement de contraste local optimal"
15h10 Nicolas Tremblay (joint work with Gilles Puy, Rémi Gribonval, Pierre Vandergheynst) (Inria Rennes, projet PANAMA & EPFL, LTS2) : "Compressive Spectral Clustering and Sampling of Graph Signals"
16h00-16h10 Pause
16h10 Abderrahim El Moataz (Université de Caen Normandie, Université de Marne la vallée) : "Nonlocal Tug-Of-War Games with applications in Graph Signal Processing"
16h30 Luc Le Magoarou, Rémi Gribonval* (Inria Rennes, projet PANAMA) "Transformée de Fourier rapide approchée sur graphe via approximation creuse multi-couche"
16h50 Pierre Borgnat, Nicolas Tremblay (CNRS, ENS de Lyon, Lab. Physique ; Inria Rennes, projet PANAMA & EPFL, LTS2) "Subgraph-based filterbanks for graph signals"
17h10 Conclusion et fin de la journée

## Résumés des contributions

Détail des contributions :

Exposés invités :

- Hamid Krim (NC State University Raleigh, USA), dans le cadre de ses activités de Distinguished Lecturer de la IEEE Signal Processing Society :

"Convexity, Sparsity, Nullity and all that....in Data Analysis"

High dimensional data exhibit distinct properties compared to its low dimensional counterpart; this causes a common performance decrease and a formidable computational cost increase of traditional approaches. Novel methodologies are therefore needed to characterize data in high dimensional spaces.

Considering the parsimonious degrees of freedom of high dimensional data compared to its dimensionality, we study the union-of-subspaces (UoS) model, as a generalization of the linear subspace model. The UoS model preserves the simplicity of the linear subspace model, and enjoys the additional ability to address nonlinear data. We show a sufficient condition to use l1 minimization to reveal the underlying UoS structure, and further propose a bi-sparsity model (RoSure) as an effective algorithm, to recover the given data characterized by the UoS model from errors/corruptions.

As an interesting twist on the related problem of Dictionary Learning Problem, we discuss the sparse null space problem (SNS). Based on linear equality constraint, it first appeared in 1986 and has since inspired results, such as sparse basis pursuit, we investigate its relation to the analysis dictionary learning problem, and
show that the SNS problem plays a central role, and may naturally be exploited to solve dictionary learning problems
.
Substantiating examples are provided, and the application and performance of these approaches are demonstrated on a wide range of problems, such as face clustering and video segmentation.

- Romain Couillet (Centrale-Supelec, L2S, CNRS, Univ. Paris-Sud) :

"Random Matrices in Machine Learning"

In this talk, we will introduce new notions of random matrix theory for the assessment and improvement of classical machine learning methods in the regime of large dimensional and numerous datasets. We shall notably discuss (more or less deeply) algorithms such as kernels methods (spectral clustering, semi-supervised learning, support vector machines), community detection on large graphs, and some minute advances in the understanding of simple neural network structures.

- Nicolas Tremblay (joint work with Gilles Puy, Rémi Gribonval, Pierre Vandergheynst) (Inria Rennes, projet PANAMA & EPFL, LTS2) :

"Compressive Spectral Clustering and Sampling of Graph Signals"

Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a feature vector for each object, and run k-means on these features to separate objects into k classes. Each of these three steps becomes computationally intensive for large N and/or k.

We propose to speed up the last two steps based on recent results in the emerging field of graph signal processing: graph filtering of random signals, and random sampling of bandlimited graph signals.

In this presentation, we will take time to go over what filtering and sampling mean for a signal defined on a graph, and explain to what extent they can prove useful for spectral clustering.

- Emilie Kaufmann (joint work with Thomas Bonald and Marc Lelarge)

Title : A novel spectral algorithm for the identification of overlapping communities in networks

Abstract : Spectral algorithms are popular methods for finding a partition of a network into groups of nodes that are densely connected, called communities. However, the structure of many real world networks is better explained by a set of overlapping communities than by a partition. In this talk, I will present SAAC (Spectral Algorithm with Additive Clustering), a simple spectral algorithm designed to identify overlapping communities. The algorithm is motivated by a random graph model called the stochastic blockmodel with overlap (SBMO), under which it is proved to be consistent when the degrees in the graph are (slightly more than) logarithmic. The algorithm is shown to perform well on simulated data and on real-world graphs with known overlapping communities.

- Aurélie Pirayre, Camille Couprie, Laurent Duval and Jean-Christophe Pesquet

"Gene Regulatory Network inference refinement using clustering"

The discovery of novel gene regulatory processes improves the understanding of cell phenotypic responses to external stimuli. To this purpose, we used transcriptomic data: for each gene of a studied organism placed in different living conditions, a sequence of genetic expression levels is obtained. From these data, gene regulation mechanisms can be recovered by revealing topological links encoded in geometric graphs. Such networks are called Gene Regulatory Networks (GRNs), where nodes and links correspond to genes and regulation relationships respectively. Despite the large number of inference methods available ([3, 2, 1]), satisfactory results remain difficult to obtain, due to the very limited length of expression signals, in comparison to the number of genes. A suitable way to refine GRNs is to take advantage of the modular structure arranged around central nodes corresponding to genes encoding for transcription factors. To take network topology into account, a compounding of clustering and inference may be considered [4].

From a complete graph weighted by ?, we formulate network inference refinement problems from a combinatorial optimization standpoint. The problem is re-expressed as an energy minimization problem inspired from previous work (BRANE Cut, [5]). The inferred graph structure, defined by variables x on the edges of the graph, and the clustering solution, defined by variables y on the nodes, are computed through an alternating optimization procedure involving a ?random walker? clustering algorithm. As a result, the variational approach we propose generates the topology of the GRN graph. We validate our approach [6] on benchmark datasets (DREAM4 and 5), showing significant improvement. In addition, promising results are found for the discovery of novel regulatory or co-expressed links in the inferred Escherichia coli network.

- Michel Barlaud, Wafa Belhajali , Patrick L. Combettes, Lionel Fillatre

"Classification and regression using constrained convex splitting method; Lasso or Graph regularization ?

Titre : This talk deals with sparse feature selection and grouping for classification and regression. The underlying classification or regression problem consists in minimizing a convex empirical risk function subject to an $\ell^1$ constraint or pairwise $\ell^\infty$ constraint. We address the constrained problem directly via a splitting method. The structure of the method is that of the classical gradient projection algorithm, which alternates a gradient step on the objective and a projection step onto the lower level set modeling the constraint. Experiments on both synthetic andbiological datas show that regularization using pairwise $\ell^\infty$ constraint outperforms regularization using the $\ell^1$ constraint.

- Pierre Weiss (ITAV USR-3505), Paul Escande (ISAE Toulouse), Yiqiu Dong (Technial University of Denmark)

Titre : "Changement de contraste local optimal'

Dans cet exposé, je décrirai une méthode d'optimisation convexe permettant de trouver une image possédant un arbre de composantes fixé, la plus proche d'une image de référence. L'arbre des composantes permet de coder la relation d'inclusion entre les composantes connexes des ensembles de niveau d'une image et de définir mathématiquement la notion de changement de contraste local. Il peut être décrit par un arbre ou de façon alternative par un graphe dirigé acyclique. Notre algorithme repose sur cette deuxième représentation qui permet d'identifier notre problème à celui d'une régression isotonique. Ce dernier a reçu une attention considérable dans la littérature, mais les approches actuelles ne permettent pas de traiter les graphes à plusieurs millions de sommets apparaissant en traitement des images.

- Abderrahim Elmoataz, Université de Caen Normandie, Université de Marne la vallée

Titre : Nonlocal Tug-Of-War Games with applications in Graph Signal Processing

Résumé: Game theoretic stochastic or deterministic methods have recently emerged as a novel approach to study and to approximate various non-linear partial differential equations (PDE). In particular Tug-of-War Games (TOG) related to the $\infty$-Laplacian or to the p-Laplacian equations have attracted a lot of attention. They were first introduced by Peres, Schramm, Sheffiel, and Wilson. It is now used in many works to study the existence or the regularity of solutions for many PDEs. Recently, there is a high interest in adapting and solving PDEs on data which is given by arbitrary graphs and networks. The demand for such methods is motivated by existing and potential future applications in graph signal processing such as in image, 3D point clouds or machine learning. Indeed, any kind of data can be represented by a graph in an abstract form in an abstract form in which the vertices are associated to the data and the edges correspond to relationships within data.

In this presentation, we consider several Dynamic Programming Equations arising in the discrete game-theoretic interpretation for various non-linear PDEs including ?-Laplacian, game p-Laplacian and Hamilton-Jacobi related equations. We show that under the framework of Partial difference equations (PdEs), these discrete games coincide with PDEs on particular Euclidean graphs. The same PDEs on weighted graph of arbitrary topology lead to non-local statistical functional. We interpret them as non-local Tug-of-War Games and we show their connections to non-local PDEs on Euclidean graphs. We propose to use these operators as a unified framework for solution of many interpolation problems in image processing and machine learning

Références

1) M. Touttain, A. Elmoataz, F. Lozes, A. Mansouri, Nonlocal discrete infini-Poisson and Hamilton Jacobi equations: from stochastic game to generalized distances on images, meshes, and point clouds, Journal of Mathematical Imaging June 2016

2) A. Elmoataz, M. Touttain, D.Tenbrinck, On the p-laplacian and infinity-laplacian on graphs with application in Image and datat processing, SIAM J.Imaging Sciences, 2015.

3) Chakik Abdallah, Elmoataz Abderrahim, DESQUESNES Xavier : Mean Curvature Flow on Graphs for Image and Manifold Restoration and Enhancement. signal processing , 2014.

4) A. Elmoataz, X. Desquesnes, Z. Lakhdari, O. Lezoray, Nonlocal infinity Laplacian equation on graphs with applications in image processing and machine learning, Mathematics and Computers in Simulation, vol. 102, pp. 153--163, 2014.

- Luc Le Magoarou, Rémi Gribonval
Titre : Transformée de Fourier rapide approchée sur graphe via approximation creuse multi-couche
Résumé : Les transformées rapides sont des applications linéaires associées à un algorithme rapide, pouvant être vu comme une séquence de multiplications par des matrices creuses. La transformée de Fourier classique est associée à un algorithme rapide (la FFT), ce qui n'est pas le cas de la transformée de Fourier sur graphe en général. Nous proposons ici deux méthodes distinctes permettant d'obtenir des transformées de Fourier rapides approchées sur graphe, en tant que produits de matrices creuses définissant un algorithme rapide.
- Pierre Borgnat, Nicolas Tremblay
Titre : Subgraph-based filterbanks for graph signals
We have proposed a framework to define filterbanks on a graph that is based on a partition of this graph in a set of connected sub-graph. In this way, we design a critically-sampled compact-support biorthogonal transform for graph signals. Unlike the ?one every two nodes? downsampling on bipartite graphs, we use a coarsening operation of the graph by defining one ?supernode? for each subgraph and the edges for this coarsened graph derives from the connectivity between the subgraphs. This does not have an exact formulation in the graph Fourier domain. Instead, we rely on the local Fourier bases of each subgraph to define filtering operations. We show examples of us of this method to decompose graph signals, and show promising performance on compression and denoising.

Date : 2016-06-17

Lieu : Telecom-Paristech, Amphithéâtre Emeraude, Paris

Thèmes scientifiques :
A - Méthodes et modèles en traitement de signal

Inscriptions closes à cette réunion.

(c) GdR 720 ISIS - CNRS - 2011-2022.