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.
29 personnes membres du GdR ISIS, et 24 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.
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.
(Action "Signaux & Images sur graphes" du thème A) :
Programme :
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"
- 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.
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 IASIS - CNRS - 2024.