Théorie Spectrale des Graphes en Machine Learning

1. Qu’est-ce que la Théorie Spectrale des Graphes ?

La théorie spectrale des graphes étudie un graphe à travers les valeurs et vecteurs propres des matrices qui le représentent. Plutôt que de raisonner sur les sommets et les arêtes un par un, on encode le graphe entier sous forme de matrice et on lit sa structure dans le spectre de cette matrice, l’ensemble de ses valeurs propres. C’est le pont qui relie les objets discrets et combinatoires à la machinerie continue et très développée de l’algèbre linéaire.

Ce pont est précisément ce qui intéresse le machine learning. Les données réelles sont massivement relationnelles : réseaux sociaux, molécules, graphes de citations, cartes routières, pixels d’une image, cooccurrences de mots. Pourtant, la plupart des algorithmes d’apprentissage attendent en entrée des vecteurs numériques bien rangés. Les méthodes spectrales résolvent cette tension en transformant un graphe en coordonnées : une géométrie que l’on peut regrouper, plonger et fournir à un réseau de neurones.

Le domaine a des racines profondes en mathématiques pures (les travaux de Fiedler, Chung et d’autres) mais est devenu une boîte à outils concrète. Comme l’écrit Daniel Spielman dans ses notes de cours réputées de Yale, le spectre révèle « à quel point un graphe est bien connecté, s’il possède de bons clusters et comment l’information s’y diffuse ». Ces trois questions sont au cœur de l’apprentissage non supervisé.

2. Du Graphe à la Matrice : le Laplacien

Trois matrices décrivent un graphe à n sommets. La matrice d’adjacence A contient un 1 à l’entrée (i, j) lorsqu’une arête relie les sommets i et j. La matrice des degrés D est diagonale et contient le degré de chaque sommet. La vedette est le laplacien du graphe :

L = D − A

Le laplacien est symétrique et semi-défini positif, chacune de ses lignes a une somme nulle, et il se comporte comme une version discrète de l’opérateur de Laplace de la physique : il mesure à quel point un signal sur le graphe varie d’un nœud à son voisin. Cette intuition est capturée par sa forme quadratique, xᵀLx = Σ (xᵢ − xⱼ)² sommée sur chaque arête : petite quand les sommets connectés partagent des valeurs proches, grande quand ils diffèrent.

En pratique, on préfère généralement un laplacien normalisé, qui rééchelonne en fonction des degrés inégaux. La version symétrique est L_sym = I − D^(−1/2) A D^(−1/2) et la version marche aléatoire est L_rw = I − D^(−1) A. La normalisation empêche les nœuds très connectés de dominer le spectre, et la plupart des recettes de machine learning, clustering spectral comme Réseaux de Neurones sur Graphes, reposent sur ces formes normalisées.

3. Le Spectre du Graphe : les Valeurs Propres comme Structure

Comme le laplacien est symétrique et semi-défini positif, toutes ses valeurs propres sont réelles et positives ou nulles. On les ordonne ainsi : 0 = λ₁ ≤ λ₂ ≤ … ≤ λₙ. Cette liste ordonnée est le spectre du graphe, et il est étonnamment riche en informations.

• La plus petite valeur propre vaut toujours 0, avec le vecteur constant pour vecteur propre.
• Le nombre de valeurs propres nulles est égal au nombre de composantes connexes. Un seul 0 signifie que le graphe est connexe.
• La deuxième plus petite valeur propre λ₂ est la célèbre connectivité algébrique, ou valeur de Fiedler (Miroslav Fiedler, 1973). Plus elle est proche de zéro, plus le graphe se scinde facilement en deux parties.

Le saut de λ₂ à λ₃ s’appelle le saut spectral, et un grand saut indique fortement que le graphe possède une structure de clusters nette. Le vecteur propre associé à λ₂, le vecteur de Fiedler, attribue à chaque sommet un nombre dont le signe indique de quel côté de la coupe il se trouve. La célèbre inégalité de Cheeger rend cela rigoureux en bornant la coupe la plus parcimonieuse d’un graphe en fonction de λ₂. En un seul nombre, le spectre répond : ces données forment-elles un seul bloc, ou plusieurs ?

4. Clustering Spectral

Le clustering spectral est l’application phare en machine learning, et il découle directement de la section précédente. La recette est courte :

1. Construire un graphe de similarité à partir des données, généralement un graphe des k plus proches voisins ou un noyau gaussien (RBF) reliant les points proches.
2. Former le laplacien normalisé et calculer ses k plus petits vecteurs propres.
3. Empiler ces vecteurs propres en colonnes pour donner à chaque point une nouvelle coordonnée de dimension k, le plongement spectral.
4. Exécuter le k-means habituel dans cet espace plongé.

Pourquoi s’en soucier puisque le k-means existe déjà ? Parce que le k-means ne sait découper que des blocs ronds et convexes, alors que le clustering spectral peut récupérer des clusters de forme arbitraire, les classiques « deux lunes entrelacées » ou anneaux concentriques qui mettent le k-means totalement en échec. Mathématiquement, c’est une relaxation traitable du problème de coupe normalisée, NP-difficile sous sa forme exacte ; les vecteurs propres en donnent la meilleure approximation continue. L’approche a été popularisée par Normalized Cuts de Shi et Malik pour la segmentation d’images (2000) et par Ng, Jordan et Weiss (2002), et le tutoriel de 2007 d’Ulrike von Luxburg reste le guide pratique de référence.

Une démonstration canonique est le jeu de données des « deux lunes » : deux croissants entrelacés. Le k-means ordinaire le coupe droit par le milieu et échoue, car les croissants ne sont pas linéairement séparables. Le clustering spectral, qui travaille sur le graphe de voisinage, suit la courbe de chaque lune et les retrouve toutes les deux correctement. Le même avantage apparaît avec des cercles concentriques et toute donnée dont les clusters sont connexes mais non compacts.

5. Apprentissage de Variétés et Cartes Propres Laplaciennes

Les mêmes vecteurs propres qui découpent un graphe peuvent aussi aplatir des données de grande dimension. C’est l’idée des cartes propres laplaciennes (Laplacian Eigenmaps), introduites par Mikhail Belkin et Partha Niyogi en 2003. Le postulat, l’hypothèse de variété, est que les données réelles de grande dimension (visages, écriture, expression génique) résident en réalité sur une surface courbe de dimension bien plus faible plongée dans cet espace.

Les cartes propres laplaciennes retrouvent cette surface en construisant un graphe de voisinage puis en choisissant des coordonnées de faible dimension y qui minimisent Σ wᵢⱼ ‖yᵢ − yⱼ‖², gardant proches dans le plongement les points qui étaient proches dans l’espace d’origine. La solution est, là encore, les plus petits vecteurs propres non triviaux du laplacien du graphe. Contrairement à l’ACP, qui ne trouve que des projections linéaires, il s’agit d’une réduction de dimension véritablement non linéaire, étroitement liée aux cartes de diffusion et au plongement spectral fourni par scikit-learn. C’est un outil incontournable pour la visualisation et le prétraitement avant classification.

Il convient de distinguer ces méthodes de t-SNE et UMAP, les outils de visualisation populaires. Ceux-ci reposent aussi sur des graphes et préservent le voisinage dans l’esprit, mais ils optimisent un objectif probabiliste plutôt que de résoudre directement les vecteurs propres laplaciens. Les cartes propres laplaciennes restent attrayantes quand on veut un plongement rapide et déterministe, doté d’une interprétation transparente en algèbre linéaire.

6. Réseaux de Neurones sur Graphes Spectraux

La théorie spectrale des graphes est aussi le fondement théorique de toute une branche de l’apprentissage profond. L’idée clé est la transformée de Fourier sur graphe : projeter un signal défini sur les sommets sur les vecteurs propres du laplacien joue le même rôle que la transformée de Fourier classique pour les séries temporelles. Les valeurs propres jouent le rôle de fréquences, et « filtrer » un signal de graphe revient à repondérer ses composantes spectrales.

Bruna et ses collègues ont défini ainsi la première convolution spectrale sur graphes en 2014. Cela fonctionnait, mais une décomposition propre complète coûte O(n³) et les filtres n’étaient pas localisés. Deux raffinements ont rendu l’idée pratique :

• ChebNet (Defferrard, Bresson et Vandergheynst, NeurIPS 2016) approxime les filtres spectraux par des polynômes de Chebyshev du laplacien. Les filtres deviennent strictement locaux et le calcul est linéaire en nombre d’arêtes, sans décomposition propre.
• Le Réseau de Convolution sur Graphe (Kipf et Welling, ICLR 2017) simplifie ChebNet à un ordre un, donnant la règle de propagation désormais omniprésente H' = σ( D̃^(−1/2) Ã D̃^(−1/2) H W ), où à = A + I ajoute les boucles.

Cette unique couche élégante, descendante directe du laplacien normalisé, est ce qui alimente les applications actuelles des GNN dans les systèmes de recommandation, la détection de fraude, la prévision du trafic et la découverte de médicaments et de matériaux.

Une réserve pratique : un filtre purement spectral est lié à un seul graphe fixe, car les vecteurs propres changent dès que le graphe change. C’est pourquoi une grande partie du domaine s’est tournée vers les réseaux spatiaux à passage de messages, qui se généralisent à des graphes de tailles différentes. Malgré tout, le point de vue spectral reste la loupe la plus claire pour comprendre ce qu’une convolution de graphe fait réellement à un signal.

7. Outils et Quand Utiliser les Méthodes Spectrales

On implémente rarement l’algèbre linéaire à la main. Des bibliothèques matures et fiables couvrent toute la chaîne :

• scikit-learn, SpectralClustering et SpectralEmbedding pour le clustering et l’apprentissage de variétés.
• NetworkX, laplacian_matrix, normalized_laplacian_matrix et fiedler_vector pour l’analyse.
• SciPy, scipy.sparse.linalg.eigsh pour calculer efficacement seulement les quelques plus petits vecteurs propres d’un grand laplacien creux.
• PyTorch Geometric et DGL, couches GNN de production, dont GCN et ChebNet.

Quelques règles pratiques : travaillez toujours avec le laplacien normalisé ; utilisez des solveurs de valeurs propres creux et ne demandez que les plus petits vecteurs propres nécessaires ; et choisissez le nombre de clusters avec l’heuristique du saut spectral, en cherchant le plus grand écart dans le spectre trié. Tournez-vous vers les méthodes spectrales quand vos données forment naturellement un graphe, quand les clusters ne sont pas convexes, ou quand vous avez besoin d’un plongement de faible dimension bien fondé. Quand les clusters sont nettement ronds et les données déjà vectorisées, un simple k-means peut être plus rapide et tout aussi bon. La théorie spectrale des graphes ne remplace pas votre boîte à outils : elle lui donne une géométrie.

En un Coup d’Œil : Choisir une Méthode