Méthodes variationnelles pour les signaux sur graphe – GraVa

Our first axis aims at pushing the boundaries of the current knowledge in spectral graph theory in three important theoretical directions. Concurrently, in a second axis, a better understanding on how to design, analyze and implement efficient algorithms for these more and more complex graph priors is addressed for computational challenges. In particular, to cope with the growing size of the underlying graphs investigated, we will have to rely on modern distributed and parallel optimization schemes. These two axes constitute the core of GraVa and should serve as a basis for future works.

The third axis goes beyond regularized least square regression, and includes classification or segmentation on graphs tasks. Understanding how deep learning can play a role in graph signal analysis would hence be a natural question for this field due to its recent success on images and videos. This axis will be in direct connection to the last one, concerning the deployment to physical networks. In addition to the graph structure, we will have to deal with the time evolution aspect of such contexts. To help us in our deployment phase, we intend to collaborate with a French startup DCBrain, specialized in predictive models for physical networks.

Y. Pilavci, P.-O. Amblard, S. Barthelme, N. Tremblay. Smoothing graph signals via random spanning forests. ICASSP. 2020
N. Keriven, A. Bietti, SV. Convergence and Stability of Graph Convolutional Net- works on Large Random Graphs. NeurIPS. 2020. arXiv:2006.01868.
Q. Bertrand, Q. Klopfenstein, M. Blondel, SV, A. Gramfort, J. Salmon. Implicit differentiation of Lasso-type models for hyperparameter optimization. ICML. 2020. arXiv:2002.08943.
B. Pascal, SV, N. Pustelnik, P. Abry. Automated data-driven selection of the hyperparameters for Total-Variation based texture segmentation. 2020. arXiv:2004.09434. (in revision in J. Math. Vis. Imaging).
N. Keriven, SV. Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model. 2020. arXiv:2002.02892.
Q. Klopfenstein, SV. Linear Support Vector Regression with Linear Constraints. 2019. arXiv:1911.02306. (under review at Mach Learn.).
M. Massias, SV, A. Gramfort, J. Salmon. Dual Extrapolation for Sparse Gener- alized Linear Models. 2019. arXiv:1907.05830. (in revision in JMLR).
X. Dupuis, SV. The Geometry of Sparse Analysis Regularization. 2019. arXiv:1907.01769. (in revision in SIAM J. Optim.).

Beyond the scientific publications expected from this project, we believe in reproducible research through the contribution in open-source projects. It starts with a commitment to publish all numerical simulations associated to reports in an open and accessible way. The authors are familiar with this behavior, with experiments available online (GitHub or homepage) associated to their work.

Concerning the development of packages, the Python module NetworkX could be a good candidate for the novel developed methods, especially described in Tasks 4 and 5. Note that scikit-learn would also be well suited Python module to host some of our contributions. This package is widely used in machine learning both from academic (with around 5,000 citations according to Google Scholar) and industrial perspectives. Besides direct contributions to scikit-learn, we intend to release our work under permissive license such as the MIT or New BSD.

1. 2. 3.
4.
5. 6. 7. 8.
Y. Pilavci, P.-O. Amblard, S. Barthelme, N. Tremblay. Smoothing graph signals via random spanning forests. ICASSP. 2020
N. Keriven, A. Bietti, SV. Convergence and Stability of Graph Convolutional Net- works on Large Random Graphs. NeurIPS. 2020. arXiv:2006.01868.
Q. Bertrand, Q. Klopfenstein, M. Blondel, SV, A. Gramfort, J. Salmon. Implicit differentiation of Lasso-type models for hyperparameter optimization. ICML. 2020. arXiv:2002.08943.
B. Pascal, SV, N. Pustelnik, P. Abry. Automated data-driven selection of the hyperparameters for Total-Variation based texture segmentation. 2020. arXiv:2004.09434. (in revision in J. Math. Vis. Imaging).
N. Keriven, SV. Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model. 2020. arXiv:2002.02892.
Q. Klopfenstein, SV. Linear Support Vector Regression with Linear Constraints. 2019. arXiv:1911.02306. (under review at Mach Learn.).
M. Massias, SV, A. Gramfort, J. Salmon. Dual Extrapolation for Sparse Gener- alized Linear Models. 2019. arXiv:1907.05830. (in revision in JMLR).
X. Dupuis, SV. The Geometry of Sparse Analysis Regularization. 2019. arXiv:1907.01769. (in revision in SIAM J. Optim.).

Traiter de larges bases de données est devenu un défi majeur en mathématiques appliquées, apprentissage machine ou statistiques. Cependant, de nombreuses méthodes proposées dans la littérature ne prennent pas en compte la structure fine (géométrique ou non) sous-jacente à ces données. Ces structures peuvent souvent être modélisées grâce à des graphes.

Si de nombreuses entreprises comme Google, Facebook ou Twitter voient leurs succès basé sur l'extraction d'informations sur des signaux vivant naturellement sur des graphes, les méthodes traditionnelles négligent souvent (dans un soucis de simplicité) cette structure de graphe sous-jacente, ou bien utilisent des estimateurs linéaires afin d'aborder ces problèmes. Dans ce projet en revanche, nous prônons l'utilisation de régularisations non linéaires afin de résoudre des problèmes inverses ou des tâches d'apprentissage (comme la classification) pour de tels signaux, dans l'esprit de ce que l'on appelle aujourd'hui le traitement du signal sur graphe.

Le projet GraVa est une tentative de résoudre de tels problèmes concrets et difficiles par l'utilisation de méthodes variationnelles pour le traitement du signal sur graphe.
Cette approche soulève de nombreux défis :

1. Quels estimateurs sont de bons candidats, et comment évaluer leur performance ? Nous prendrons en compte de récentes contributions de plusieurs communautés (analyse harmonique sur graphe, statistiques, optimisation) et développerons de nouveaux outils en théorie spectrale d'opérateurs non linéaires sur graphe, domaine émergent.

2. Comment construire des algorithmes efficaces pour ces méthodes ? Nous nous appuierons sur des schémas modernes d'optimisation distribuée et parallèle. Notre ambition principale est d'aller plus loin que les approches classiques en exploitant certaines propriétés centrales des graphes, comme la régularité, la parcimonie, etc.

3. Qu'est-ce qu'une bonne métrique pour comparer des signaux sur graphe, et puis comment les classifier? La mesure L2 est commune en traitement du signal mais correspond à un a priori gaussien sur la distribution du bruit. Nous comptons développer des métriques plus robustes, et dépendantes des structures, capables de répondre à différents scénarios comme les problèmes inverses, la segmentation ou la classification.

4. Comment traiter des signaux dépendants du temps? Considérer des signaux statiques est une première étape, mais pour beaucoup de réseaux, il est indispensable de prendre en compte la dimension temporelle de ces structures. Nous prévoyons de transférer l'analyse de séries temporelles aux signaux sur graphes, et de déployer nos réalisations sur des scénarios réels.

En vue d'atteindre un impact industriel, nous collaborerons au sein de GraVa avec Kwyk, une jeune entreprise française spécialisée dans l'apprentissage en ligne, à destination du second degré.