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)

Vecteurs propres (Graph signal processing tutorial, M. Defferrard, N. Tremblay)
Signaux temporels issus d'IRM du cerveau (Graph signal processing tutorial, M. Defferrard, N. Tremblay)
css.php