Groupe de lecture sur l’analyse de graphes par ondelettes

Description : Face au défi du traitement et de l’analyse de l’avalanche de données qui s’accumulent, dans des domaines aussi vastes et variés que les neurosciences ou les réseaux sociaux – pour ne nommer que ceux-là – il est nécessaire d’élaborer des approches mathématiques et informatiques efficaces qui exploitent la structure de ces données à différentes échelles. Le traitement du signal sur graphes, et plus précisément les ondelettes sur graphes, offrent un cadre propice à ces analyses couvrant un large spectre des mathématiques appliquées. Nous mettons ainsi en place un groupe de lecture, à destination des doctorants et des chercheurs intéressés par cette thématique, afin de découvrir ou d’approfondir des travaux autour de l’analyse multi-échelle de graphes.

Liste de diffusion (abonnez-vous !) : https://listes.univ-grenoble-alpes.fr/sympa/info/ljk-lecture-graphes-ondelettes

Organisation

La première réunion de groupe aura lieu le mercredi 22 avril à 10h.
Étant donné le contexte actuel celle-ci se déroulera en visioconférence ici : https://bbb-ljk.imag.fr/b/kev-udz-hyu
Les réunions ultérieures auront lieu périodiquement les mercredi à 10h une semaine sur deux (cf. calendrier ci-dessous).
Les participant·es volontaires pourront à tour de rôle lire et présenter au groupe un article de leur choix sur ce thème, ou parmi la liste suggérée à titre indicatif (cf. http://www.kevinpolisano.com/Recherche/Liste-articles.zip).
Les doctorant·es de l'ED MSTII qui participent au groupe de lecture et présentent un exposé bénéficieront de 10h de crédits ECTS.

Les profils des chercheur·es ou doctorant·es peuvent être variés : que vous soyez familiers avec l'analyse par ondelettes et cherchiez à l'appliquer sur des graphes ; ou inversement que vous soyez familiers avec l'analyse de graphes et cherchiez à utiliser les ondelettes pour en explorer les aspects multi-échelles.

Calendrier prévisionnel

Mercredi 22 avril : présentation du groupe de lecture (K. Polisano) + mini-cours introductif (N. Tremblay). [Slides] [Vidéo]
Mercredi 29 avril : mini-cours introductif (suite) (N. Tremblay) [Vidéo]
Mercredi 13 mai (10h) : [Tremblay2014] Graph Wavelets for Multiscale Community Mining (Lorenzo Dall'amico) [Slides] [Vidéo]
Mercredi 27 mai (10h) : [Göbel2018] Construction of tight frames on graphs and application to denoising (Nils Laurent) [Slides] [Vidéo]
Mercredi 10 juin (10h) : [Leonardi2013] Tight wavelet frames on multislice graphs (Yusuf Yigit Pilavci) [Slides] [Vidéo]
Mercredi 24 juin (10h) : [Sevi2018] Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets (Gabriel Destouet) [Slides] [Vidéo]
Mercredi 1er juillet (10h) : [Rustamov2013] Wavelets on graphs via deep learning (Myriam Bontonou) [Slides] [Vidéo]
Mercredi 8 juillet (10h) : [Defferrard2016] Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (Hubert Leterme) [Slides] [Vidéo]

Liste d'articles suggérés

Avant-propos

[Mallat1999] A wavelet tour of signal processing (25944) (La bible de l’analyse des signaux 1D/2D par ondelettes)
[Crovella2003] Graph Wavelets for Spatial Traffic Analysis (253) (Papier « historique » datant l’utilisation des ondelettes sur graphes)

NB : Entre parenthèses (x) est indiqué le nombre de citations de l'article, '*' suggère que l'article est un "incontournable".

Articles fondamentaux introduisant l’analyse de Fourier/ondelettes sur graphes

[Hammond2011] Wavelets on graphs via spectral graph theory (1064) *
[Narang2012] Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data (330) *
[Shuman2013] The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (1902) *
[Sandryhaila2013] Discrete signal processing on graphs (830) *
[Sandryhaila2014] Discrete signal processing on graphs: Frequency analysis (449) *
[Tremblay2017] Design of graph filters and filterbanks (17) (chapitres 1 et 2 : généralisation du traitement du signal sur graphes avec les différentes transformées de Fourier sur graphes possibles ; chapitre 3 : bancs de filtres) *
[Ortega2018] Graph signal processing: Overview, challenges, and applications (282)

Ondelettes sur graphes via autres bancs de filtres
(Transformée pyramidale multi-échelle, frames étroits d’ondelettes sur graphes, etc)

[Narang2013] Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs (172) (extension de [Narang2012])
[Leonardi2013] ~~Tight wavelet frames on multislice graphs~~ (85) (dont extension aux graphes dynamiques) * [Présentation par Yusuf Yigit Pilavci]
[Shuman2015] A multiscale pyramid transform for graph signals (104) *
[Dong2017] Sparse representation on graphs by tight wavelet frames and applications (45) *
[Göbel2018] ~~Construction of tight frames on graphs and application to denoising~~ (6) [Présentation par Nils Laurent]
[Avena2018] Intertwining wavelets or multiresolution analysis on graphs through random forests (9) *

Application : Détection de communauté multi-échelles

[Tremblay2014] ~~Graph Wavelets for Multiscale Community Mining~~ (109) (utilisation des ondelettes de Hammond) * [Présentation par Lorenzo Dall'Amico]
[VonLuxburg2007] A tutorial on spectral clustering (7697) (en complément, pas d'aspects multi-échelles)

Autres approches avec ondelettes sur graphes

[Jansen2009] Multiscale methods for data on graphs and irregular multidimensional situations (105) (lifting en ondelettes)
[Rustamov2011] Average interpolating wavelets on point clouds and graphs (24) (ondelettes interpolantes)
[Szlam2005] Diffusion-driven multiscale analysis on manifolds and graphs: top-down and bottom-up constructions (66) (ondelettes de type Haar)
[Gavish2010] Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning (200) (ondelettes de type Haar) *
[Irion2014] Hierarchical graph laplacian eigen transforms (26) (ondelettes de type Haar)
[Tremblay2016] Subgraph-based filterbanks for graph signals (61) (ondelettes de type Haar, proche de [Gavish2010] dans des termes très différents) *

Diffusion wavelets and diffusion polynomial frames

[Maggioni2005] Biorthogonal diffusion wavelets for multiscale representation on manifolds and graphs (53)
[Coifman2006] Diffusion wavelets (689) *
[Bremer2006] Diffusion wavelet packets (67)
[Maggioni2008] Diffusion polynomial frames on metric measure spaces (80)

Extension aux graphes dirigés

[Zhou2005] Learning from labeled and un-labeled data on a directed graph (441)
[Sardelliti2017] On the graph Fourier transform for directed graphs (49)
[Shafipour2017] A digraph Fourier transform with spread frequency components
[Tay2017] Bipartite graph filter banks: Polyphase analysis and generalization (11)
[Mhaskar2018] A unified framework for harmonic analysis of functions on directed graphs and changing data (23) *
[Sevi2018] ~~Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets~~ (6) * [Présentation par Gabriel Destouet]

Deep learning (voir aussi http://geometricdeeplearning.com/)

[Rustamov2013] ~~Wavelets on graphs via deep learning~~ (73) *
[Defferrard2016] ~~Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering~~ (1745) * [Présentation par Hubert Leterme]

Autres applications

Évaluation multi-échelles de la qualité osseuse :
[Kollmannsberger2017] The small world of osteocytes: connectomics of the lacuno-canalicular network in bone (16)
[Weinkamer2019] Towards a Connectomic Description of the Osteocyte Lacunocanalicular Network in Bone (3)
Graphes et multirésolution pour les données issues des neurosciences : Workshop du GDR ISIS

Autres ressources (Notebooks & codes)