Adaptive filtering of signals defined on large graphs

Filtrage adaptatif de signaux définis sur des graphes de grande taille

Elie Chedemail (1, 2) , Basile de Loynes (1) , Fabien Navarro (1) , Baptiste Olivier (2)

1 ENSAI - Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz]
2 Orange Labs [Cesson-Sévigné]

Graph Signal Analysis focuses on extending the theory (Fourier analysis) and methodologies (such as filtering) of the classical field to signals defined on the vertices of a graph. Increasingly popular because of the flexibility of the underlying structure, this research area can be applied in many context such as telecommunications networks, social networks, organic chemistry, neurology or deep learning. The approach implemented in the sequel consists in applying a thresholding procedure in a well-chosen transformed domain in which the signal is presumed sparsely represented. The threshold calibration is obtained by minimizing the unbiased estimator of the risk originally due to Stein and adapted to the chosen transformation. The core of this paper is to propose an approach that scales to large graphs using a Chebyshev polynomial approximation of the functional computation. The implementation of this approach is illustrated numerically on a large graph (exceeding one million nodes).

L'analyse de signaux sur les graphes s'attache à étendre la théorie (analyse de Fourier) et les méthodologies (filtrage notamment) du champ classique à des signaux définis sur les noeuds d'un graphe. De plus en plus populaire de par la flexibilité de la structure de graphe, ce champ de recherche trouve de nombreux domaines d'applications (réseaux de télécommunications, réseaux sociaux, chimie organique, neurologie, apprentissage profond). L'approche mise en oeuvre consiste à appliquer une procédure de seuillage dans un domaine transformé bien choisi dans lequel une représentation parcimonieuse du signal est présumée. La calibration des seuils est obtenue en minimisant l'estimateur sans biais du risque dû originellement à Stein et adapté à la transformation choisie. Le coeur de cette communication est de proposer une approche permettant le passage à l'échelle des grands graphes à l'aide d'une approximation par polynômes de Chebyshev du calcul fonctionnel. La mise en oeuvre de cette approche est illustrée numériquement sur un grand graphe (dépassant le million de noeuds).

Domaines: Traitement du signal et de l'image [eess.SP]; Méthodologie [stat.ME]; Machine Learning [stat.ML]

Elie Chedemail, Basile de Loynes, Fabien Navarro, Baptiste Olivier. Filtrage adaptatif de signaux définis sur des graphes de grande taille. 52èmes Journées de Statistique de la SFdS, Jun 2021, Nice, France. ⟨hal-03219085⟩