Random Wavelet Features for Graph Kernel Machines

1. Problématique

Les machines à noyaux (kernel machines) sont puissantes pour traiter des problèmes non linéaires, mais leur application aux graphes se heurte à des défis computationnels majeurs.

• Coût computationnel : Le calcul explicite d'une matrice de noyau graphique $\Gamma$ (généralement une fonction du Laplacien du graphe $L$) pour un graphe de $N$ nœuds a une complexité de $O(N^3)$, ce qui est prohibitif pour les grands réseaux.
• Limites des méthodes existantes : Les méthodes d'approximation par caractères aléatoires (random features) existantes pour les graphes, comme les graph random features (g-GRFs), reposent sur des marches aléatoires spatiales. Elles convergent lentement pour les noyaux spectralement localisés (c'est-à-dire ceux qui ne dépendent que d'un petit nombre de basses fréquences du Laplacien), car ces noyaux correspondent à des interactions spatiales à longue portée difficiles à capturer par des marches aléatoires locales.

L'objectif est de concevoir des embeddings de nœuds (vecteurs de faible dimension) dont le produit scalaire approxime efficacement un noyau graphique spécifique, en évitant la décomposition spectrale complète du Laplacien.

2. Méthodologie

Les auteurs proposent une méthode d'approximation de noyaux basée sur des caractéristiques spectrales aléatoires utilisant la transformée en ondelettes de graphes (GWT). La méthode s'articule en deux étapes principales (Algorithme 1) :

A. Recherche de domaine (Range Finding)

L'objectif est d'estimer l'espace vectoriel engendré par les $K$ premiers vecteurs propres du Laplacien ($V_{:K}$), sans les calculer explicitement.

1. Filtrage de signaux aléatoires : On génère une matrice de signaux aléatoires gaussiens $G \in \mathbb{R}^{N \times (K+r)}$ (avec un sur-échantillonnage $r$).
2. Approximation polynomiale : Au lieu d'appliquer un filtre idéal (qui nécessiterait la décomposition spectrale), on applique une approximation polynomiale $p_\chi(L)$ (basée sur les polynômes de Chebyshev/Jackson) agissant comme un filtre passe-bas. Cela projette les signaux aléatoires vers le sous-espace des basses fréquences.
3. Orthogonalisation : On orthogonalise le résultat pour obtenir une base orthonormée $Q$ qui approxime $V_{:K}$.

B. Approximation du noyau

Une fois la base $Q$ obtenue, on construit l'embedding des nœuds $\Phi$ :

1. Filtrage spectral : On applique une autre approximation polynomiale $p_h(L)$ (représentant la racine carrée de la fonction du noyau $h^{1/2}(L)$) à la base $Q$.
2. Construction de l'embedding : La matrice d'embedding est définie par $\Phi = (p_h(L)Q)^\top$.
3. Approximation du noyau : Le produit scalaire des embeddings $\tilde{\Gamma} = \Phi^\top \Phi$ fournit une approximation de rang $K$ du noyau original $\Gamma = h(L)$.

Complexité : La méthode évite la décomposition spectrale ($O(N^3)$). Elle repose principalement sur des produits matrice-vecteur avec le Laplacien (sparse), offrant une complexité temporelle de $O(MEK + NK^2)$ et une complexité mémoire de $O(NK)$, où$M$ est le degré du polynôme et $E$ le nombre d'arêtes.

3. Contributions Clés

• Nouvelle approche spectrale : Introduction d'embeddings aléatoires basés sur la transformée en ondelettes de graphes pour approximer des noyaux spectraux, contrairement aux approches spatiales (marches aléatoires) existantes.
• Précision théorique : Démonstration que l'erreur d'approximation est comparable à celle de la décomposition spectrale tronquée optimale (SVD), en particulier pour les noyaux localisés spectralement. L'erreur est décomposée en une erreur de filtrage polynomial ($E_P$) et une erreur de recherche de domaine ($E_R$).
• Lien avec l'algèbre linéaire : Mise en évidence des liens forts avec la décomposition en valeurs singulières randomisée (RSVD), en adaptant les techniques de recherche de domaine pour exploiter la structure du Laplacien.
• Efficacité pour les noyaux localisés : La méthode excelle spécifiquement pour les noyaux à bande étroite (ex: processus de diffusion), là où les méthodes spatiales échouent.

4. Résultats Expérimentaux

Les expériences ont été menées sur des graphes synthétiques (Swiss-Roll, Graphes de communautés) avec 5 000 nœuds.

• Comparaison avec g-GRFs :
  • Pour les noyaux à bande étroite (forte localisation spectrale, $\sigma$ élevé dans un noyau de diffusion), la méthode proposée surpasse nettement les g-GRFs en termes d'erreur relative d'approximation.
  • Les g-GRFs restent compétitifs pour les noyaux à large bande spectrale (comportement localisé spatialement).
• Impact du rang cible $K$ :
  • Sur le graphe Swiss-Roll (valeurs propres réparties régulièrement), la méthode atteint une précision proche de l'approximation optimale jusqu'à $K \approx 1000$.
  • Sur le graphe Community (valeurs propres groupées par communautés), la performance se dégrade si $K$ dépasse la séparation naturelle des valeurs propres, car l'estimation du seuil spectral $\lambda_K$ devient imprécise dans les zones denses.
• Complexité temporelle :
  • Le temps de calcul est dominé par l'estimation de $\lambda_K$ et le filtrage polynomial.
  • L'expérience confirme une complexité linéaire en $N$ (pour $K$ fixe), rendant la méthode beaucoup plus rapide que la décomposition spectrale complète ($O(N^3)$) pour les grands graphes.

5. Signification et Conclusion

Cet article propose une avancée significative pour l'apprentissage représentatif sur les graphes à grande échelle.

• Scalabilité : En évitant la diagonalisation complète du Laplacien, la méthode rend l'apprentissage par noyaux réalisable sur des réseaux massifs.
• Complémentarité : Elle comble un vide important en offrant une approximation précise pour les noyaux spectralement localisés, un cas de figure fréquent en analyse de graphes (ex: lissage, clustering spectral) mais difficile à traiter avec les méthodes spatiales classiques.
• Fondement théorique : La connexion rigoureuse entre les ondelettes de graphes, les polynômes de Chebyshev et la RSVD offre un cadre solide pour de futures recherches en approximation de noyaux graphiques.

En résumé, cette méthode permet d'obtenir des représentations de nœuds de haute qualité et peu coûteuses en calcul, optimisées spécifiquement pour capturer les propriétés géométriques globales des graphes via une localisation spectrale précise.