🤖 machine learning

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

Ce papier présente Hierarchical Multi-view HAAR (HMH), un cadre d'apprentissage spectral de graphes évolutif qui atténue le lissage excessif et le compression excessive dans les graphes hétérophiles en construisant une hiérarchie douce avec des bases de Haar orthonormées et des filtres spectraux apprenables, surpassant ainsi les références de l'état de l'art dans les tâches de classification de nœuds et de graphes.

Auteurs originaux : Md Sazzad Hossen, Avimanyu Sahoo

Publié 2026-05-13

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Md Sazzad Hossen, Avimanyu Sahoo

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de comprendre une ville massive et chaotique en vous promenant dans ses quartiers. Dans le monde de la science des données, cette ville est un graphe (un réseau de points connectés), et les personnes qui y vivent sont des nœuds.

Habituellement, lorsque nous enseignons aux ordinateurs à comprendre ces villes, nous nous heurtons à trois grands problèmes :

Le problème du « Voisin Riche » (Domination des Hubs) : Si un quartier abrite une célébrité super populaire (un « hub » avec des milliers d'amis), son opinion étouffe les voix discrètes des quartiers plus petits et moins connectés. L'ordinateur n'entend que la célébrité.
Le problème de la « Photo Floue » (Sur-lissage) : Si vous continuez à demander aux voisins ce qu'ils pensent, et qu'ils continuent de demander à leurs voisins, finissent par tous se ressembler exactement. Les détails uniques s'estompent et l'image devient une tache grise floue.
Le problème du « Jeu du Téléphone » (Sur-écrasement) : Si vous essayez d'envoyer un message d'un côté de la ville à l'autre, le message est tellement comprimé en passant par des rues bondées qu'il arrive sous forme de charabia.

L'article présente une nouvelle solution appelée HMH (Hiérarchique Multi-vues HAAR). Imaginez HMH non pas comme une personne se promenant dans les rues, mais comme un système intelligent d'urbanisme à plusieurs niveaux utilisant un type spécial de « lentille de zoom ».

Voici comment cela fonctionne, étape par étape :

1. Le Traducteur Intelligent (L'Encodeur Hétérophile)

Dans de nombreuses villes, les voisins sont similaires (ils aiment la même musique). Dans d'autres, les voisins sont opposés (l'un adore le jazz, l'autre le heavy metal). C'est ce qu'on appelle l'hétérophilie.

L'ancienne méthode : Les ordinateurs supposent souvent que tout le monde est similaire et se contentent de moyenner leurs opinions. Cela échoue lorsque les voisins sont opposés.
La méthode HMH : Elle agit comme un traducteur attentif. Si deux voisins sont similaires, elle leur donne un « pouce levé » (poids positif). S'ils sont opposés, elle leur donne un « pouce baissé » (poids négatif). Cela garantit que l'ordinateur apprend à repérer les différences tout aussi bien que les similitudes, sans se confondre avec les inversions de signe.

2. La Lentille de Zoom (Clustering Hiérarchique)

Au lieu d'essayer d'analyser chaque personne de la ville en une seule fois, HMH construit une pyramide de quartiers.

Niveau 1 : Elle regroupe les personnes similaires en petits « grumeaux » ou clusters.
Niveau 2 : Elle traite ces grumeaux comme des « super-personnes » uniques et les regroupe en de plus grands districts.
Niveau 3 : Elle continue de zoomer vers l'extérieur jusqu'à voir la ville entière comme quelques grandes régions.

C'est comme regarder une carte : d'abord vous voyez les maisons, puis les pâtés de maisons, puis les quartiers, puis la ville entière. Cela aide l'ordinateur à gérer le problème du « Voisin Riche » car les petits quartiers silencieux obtiennent leur propre voix dans les petits clusters avant d'être fusionnés dans la grande image.

3. Le Filtre Spécial (Base de Haar)

C'est l'ingrédient secret. La plupart des ordinateurs utilisent un « filtre global » qui tente de lisser toute la ville en une seule fois, ce qui cause le problème de la « photo floue ».
HMH utilise quelque chose appelé une Base de Haar. Imaginez cela comme un ensemble de projecteurs spécialisés :

Certains projecteurs éclairent uniquement une seule maison (détails locaux).
D'autres éclairent un pâté de maisons entier (détails moyens).
D'autres éclairent toute la ville (grandes tendances).

Parce que ces projecteurs sont orthogonaux (ils ne se chevauchent pas et n'interfèrent pas entre eux), HMH peut allumer le projecteur « détail local » sans flouter accidentellement le projecteur « grande tendance ». Il conserve les détails haute fréquence (les différences entre voisins) nets tout en comprenant la grande image.

4. L'Ascenseur (Dégroupage par Connexion Résiduelle)

Après avoir analysé la ville à chaque niveau de zoom, HMH ne s'arrête pas au sommet. Elle utilise un ascenseur pour ramener toutes ces informations au niveau initial de la rue.

Elle prend les aperçus de la « grande image » du sommet de la pyramide.
Elle les mélange avec les « détails locaux » du bas.
Chaque personne (nœud) reçoit un rapport final qui inclut à la fois les ragots de son quartier immédiat et le contexte à l'échelle de la ville.

Pourquoi est-ce important ?

L'article affirme qu'en utilisant ce système « Lentille de Zoom + Projecteurs Spéciaux + Ascenseur », HMH résout les trois grands problèmes :

Plus de Domination des Hubs : Les petits quartiers ne sont pas étouffés par les célébrités car ils sont analysés dans leurs propres clusters en premier.
Plus de Photos Floues : Les projecteurs spéciaux gardent les détails uniques nets, même dans les couches très profondes.
Plus de Messages Comprimés : Parce que la ville est organisée en une hiérarchie (comme un arbre), les messages n'ont pas à se faufiler par des rues bondées ; ils voyagent vers le haut et vers le bas de l'arbre, ce qui est beaucoup plus rapide et clair.

Le Résultat :
Les auteurs ont testé cela sur de nombreux types de « villes » (ensembles de données), allant des réseaux sociaux aux structures moléculaires. Ils ont constaté que HMH était plus rapide (s'étendant presque linéairement, ce qui signifie qu'elle ne s'embourbe pas à mesure que la ville grandit) et plus précise que les méthodes précédentes, en particulier dans les endroits où les voisins sont très différents les uns des autres. Elle a obtenu de meilleurs scores pour identifier à quel groupe appartient qui (classification) sans perdre l'identité unique des individus.

Résumé Technique : Réseaux de Neurones Graphiques Hiérarchiques Multi-Échelle (HMH)

1. Énoncé du Problème

Les graphes du monde réel présentent souvent une hétérophilie, où les nœuds adjacents possèdent des étiquettes ou des caractéristiques différentes. Bien que les Réseaux de Neurones Graphiques (GNN) existants aient fait des progrès dans le traitement de telles données, ils souffrent de trois pathologies critiques, en particulier dans les graphes déséquilibrés en degrés (dominés par des hubs) :

Domination des Hubs : Dans les graphes contenant des nœuds « hubs » de haut degré, les mécanismes de passage de messages conventionnels permettent à ces hubs de dominer le processus d'agrégation. Cela submerge les signaux émanant des nœuds « rayons » de faible degré (petits clusters), provoquant la convergence des plongements de clusters distincts vers une représentation commune induite par le hub, effaçant ainsi les frontières de décision.
Sur-lissage : À mesure que la profondeur des GNN augmente, les plongements de nœuds tendent à converger vers une distribution stationnaire (moyennes de classes), rendant les caractéristiques indistinguables. Ceci est exacerbé par des filtres polynomiaux sous-optimaux qui mélangent des signaux provenant de régions sémantiquement non liées.
Sur-écrasement : L'information provenant de nœuds distants décroît exponentiellement avec la distance du graphe, créant des goulots d'étranglement qui empêchent le flux d'information à longue portée.

Les approches spectrales existantes (par exemple, ChebNet, BernNet) reposent souvent sur des bases polynomiales globales (Tchebychev, Jacobi) qui supposent une orthogonalité continue. Cependant, les graphes réels possèdent des mesures spectrales discrètes, entraînant une fuite de fréquence, une expressivité réduite et une incapacité à s'adapter à l'hétérophilie structurelle locale. À l'inverse, les approches spatiales (par exemple, le Passage de Messages Signé) souffrent souvent d'annulation de signe à travers les couches ou nécessitent des étapes d'agrégation globale coûteuses qui mélangent les signaux entre les régions.

2. Méthodologie : HAAR Hiérarchique Multi-vues (HMH)

Les auteurs proposent HMH, un cadre d'apprentissage spectral de graphes conçu pour évoluer en temps quasi-linéaire tout en atténuant les pathologies susmentionnées. Le cadre fonctionne grâce à une analyse hiérarchique et multi-résolution des signaux de graphe.

2.1. Encodeur Adaptatif Hétérofile

Le processus commence par un encodeur conscient de l'hétérophilie qui apprend des affinités signées, conscientes des caractéristiques et de la structure, sans nécessiter d'étiquettes de nœuds.

Similarité Adaptative : L'encodeur calcule un score de similarité combinant l'affinité des caractéristiques (poids apprenables) et la similarité structurelle (basée sur les voisins communs à deux sauts).
Matrice d'Adjacence Signée : Ces scores sont transformés en une matrice d'adjacence signée et continue ( $A_{adp}$ ). Une forte similarité produit des poids positifs (comportement passe-bas), tandis qu'une faible similarité produit des poids négatifs (comportement passe-haut).
Stabilité du Signe : Contrairement au Passage de Messages Signé (SMP) fixe qui souffre d'un basculement périodique du signe ( $S^2 = I$ ), l'adjacence adaptative de HMH est recalculée à chaque couche en fonction des plongements actuels, empêchant l'oscillation rigide et l'annulation de signe.

2.2. Coarsement Hiérarchique du Graphe

En utilisant les scores de nœuds de l'encodeur, HMH construit une hiérarchie de graphe douce via un processus de regroupement récursif :

Regroupement : Les nœuds sont regroupés en clusters (supernœuds) en utilisant $k$ -means++ sur les plongements de l'encodeur.
Assignation Douce : Une matrice d'assignation probabiliste ( $A_s$ ) mappe les nœuds fins vers des clusters grossiers, contrôlée par un paramètre de température.
Agrégation : Les caractéristiques et les arêtes sont agrégées pour former le niveau suivant de la hiérarchie. Ce processus se répète jusqu'à ce qu'un seuil soit atteint, créant une structure arborescente.

2.3. Bases de Haar Conscientes des Classes et Filtrage Spectral

À chaque niveau hiérarchique, HMH construit une base de Haar orthonormée et creuse ( $U^{(\ell)}$ ) adaptée à la structure de cluster spécifique de ce niveau.

Construction de la Base : La base se compose d'un vecteur d'échelle global (capturant les tendances basse fréquence) et d'ondelettes. Les ondelettes sont divisées en :
- Ondelettes inter-clusters : Capturant les contrastes entre différents supernœuds.
- Ondelettes intra-clusters : Capturant les variations localisées au sein d'un cluster.
Filtrage Diagonal : Les signaux de graphe sont projetés sur cette base. Des matrices de gain diagonales apprenables ( $\Lambda^{(\ell)}$ ) sont appliquées pour amplifier sélectivement les canaux haute fréquence (hétérofiles) et atténuer les signaux basse fréquence (homophiles) ou dominés par les hubs.
Localité : Parce que la base de Haar est strictement localisée (support confiné à de petits voisinages), elle empêche la fuite d'information entre des régions de graphe non liées, adressant directement la domination des hubs.

2.4. Dégroupement Connecté par Sauts

Pour retrouver la résolution originale, HMH emploie un dégroupement connecté par sauts. Les sorties de tous les niveaux hiérarchiques sont agrégées vers les nœuds originaux. Cela garantit que chaque nœud conserve ses caractéristiques de base enrichies d'un contexte multi-échelle provenant de tous les niveaux de la hiérarchie, contournant efficacement la décroissance exponentielle associée au sur-écrasement.

3. Contributions Clés

L'article revendique quatre contributions principales :

Affinité Signée Adaptative Sans Étiquettes : Un mécanisme qui attribue des poids positifs/négatifs basés sur la similarité apprise des caractéristiques/structure, empêchant la pathologie d'annulation de signe trouvée dans les modèles SMP fixes.
Construction de Base Orthonormée Quasi-Linéaire : Le premier cadre à construire une base spectrale orthonormée, creuse et multi-échelle (Haar) en temps quasi-linéaire, évitant le coût $O(n^3)$ de la décomposition en valeurs propres et le coût $O(n^2)$ des bases polynomiales denses.
Atténuation Théorique des Pathologies : Des preuves rigoureuses et des données empiriques démontrant que HMH surmonte la domination des hubs, le sur-lissage et le sur-écrasement. Plus précisément, la base localisée confine l'énergie aux voisinages à deux sauts, et la structure hiérarchique raccourcit logarithmiquement les chemins de communication.
Performance de l'État de l'Art : Démonstration d'une précision supérieure sur les tâches de classification de nœuds et de graphes, tant sur des ensembles de données homophiles que hétérofiles, y compris des benchmarks à grande échelle comme OGBN-ArXiv.

4. Résultats Expérimentaux

Les auteurs ont évalué HMH sur une suite diversifiée d'ensembles de données :

Classification de Nœuds : HMH a été testé sur des benchmarks homophiles standards (Cora, Citeseer) et des ensembles de données hétérofiles difficiles (Chameleon, Squirrel, Texas, Roman-empire, Amazon-ratings, etc.).
- Performance : HMH a obtenu une amélioration allant jusqu'à 3 % sur les tâches de classification de nœuds par rapport aux bases spectrales de l'état de l'art (par exemple, ChebNetII, BernNet, UniFilter).
- Analyse des Hubs : Dans les évaluations stratifiées par degré (Rayons vs Hubs), HMH a considérablement réduit l'écart de performance. Par exemple, sur l'ensemble de données Penn94, il a amélioré la précision des « Rayons » (faible degré) de +10,8 % par rapport aux bases, qui souffrent généralement de la domination des hubs.
- Stabilité de la Profondeur : Contrairement aux GCN qui se dégradent rapidement avec la profondeur (sur-lissage), HMH est resté stable et s'est même amélioré avec la profondeur (atteignant un pic à 32–64 couches sur Penn94).
- Sur-écrasement : Sur le benchmark Tree-NeighborsMatch, HMH a maintenu une précision >98 % à la profondeur 10, tandis que les bases chutaient jusqu'à un tirage au sort (50 %) à la profondeur 8.
Classification de Graphes : Évalué sur les ensembles de données TU (MUTAG, PROTEINS, etc.).
- Performance : HMH a obtenu une amélioration de 7 points sur les ensembles de données de classification de graphes, atteignant notamment 94,5 % sur MUTAG.
- Évolutivité : Le cadre a démontré une évolutivité quasi-linéaire. Sur l'ensemble de données REDDIT-12K, HMH était 8,1 fois plus rapide par époque que les bases basées sur la décomposition en valeurs propres et utilisait 3,9 fois moins de mémoire.

5. Signification et Revendications

L'article positionne HMH comme une solution aux limitations fondamentales des GNN spectraux et spatiaux actuels dans les contextes hétérofiles.

Signification Théorique : Les auteurs affirment qu'en utilisant une base de Haar orthonormée et localisée, ils confinent strictement l'énergie du signal, empêchant le phénomène d'« aliasing des hubs » où les petits clusters sont noyés par les nœuds de haut degré. La structure hiérarchique est revendiquée comme garantissant théoriquement l'absence de sur-écrasement en réduisant logarithmiquement les longueurs de chemin effectives.
Signification Pratique : Le cadre offre une alternative évolutive aux méthodes spectrales coûteuses, rendant l'apprentissage hétérofile haute performance réalisable pour les graphes à grande échelle (par exemple, OGBN-ArXiv avec ~170k nœuds).
Modestie : Les auteurs reconnaissent les limitations actuelles, notant que la formulation suppose des graphes statiques et que l'extension de la méthode aux graphes dynamiques ou multi-relationnels reste une direction pour le travail futur. Ils soulignent que leurs améliorations sont obtenues tout en maintenant une évolutivité linéaire, un facteur crucial pour le déploiement dans le monde réel.