Résumé technique : Filtrer le filtre, pas le message

Énoncé du problème

Les réseaux de neurones sur graphes pré-propagation (PP-GNN) répondent aux limitations de scalabilité des MP-GNN (GNN à passage de messages) standards en découplant le calcul dépendant du graphe de la boucle d'entraînement. Dans les PP-GNN, la propagation sur le graphe est effectuée une seule fois comme étape de prétraitement pour générer des caractéristiques de nœuds denses (hops), et le modèle s'entraîne uniquement sur ces caractéristiques. Bien que cette approche permette l'entraînement sur des graphes massifs avec des gains de vitesse de plusieurs ordres de grandeur, un mystère persiste : des agrégateurs plus complexes ne surpassent pas systématiquement les plus simples.

Les observations empiriques montrent que des agrégateurs simples basés sur des MLP (par exemple, SIGN) égalent ou dépassent souvent les performances de mécanismes d'attention sur les hops sophistiqués (par exemple, HOGA) sur divers benchmarks. Les explications existantes se concentrant sur la capacité architecturale brute ne parviennent pas à rendre compte de ce phénomène. L'article postule que la limitation ne réside pas dans la complexité de l'agrégateur, mais dans la manière dont les coefficients de filtrage sont partagés entre les nœuds et les canaux de caractéristiques au sein de la base de diffusion précalculée. Plus précisément :

• Les architectures basées sur MLP apprennent des filtres qui dépendent des canaux mais sont largement partagés entre les nœuds.
• Les architectures d'attention sur les hops apprennent des mélanges qui dépendent des nœuds mais sont largement partagés entre les canaux.
  Aucune de ces approches ne réalise pleinement un filtrage adaptatif conjoint nœud-canal, un régime que les conceptions standard de PP-GNN laissent inexploré.

Méthodologie : FilterMoE

Les auteurs proposent FilterMoE, un PP-GNN de type Mixture-of-Experts (MoE) qui introduit un filtrage adaptatif conjoint nœud-canal tout en respectant strictement le contrat de calcul de la pré-propagation (aucun passage de messages clairsemé pendant l'entraînement).

Architecture centrale

1. Prétraitement (Hors ligne) :

   • Une base de diffusion de Chebyshev est matérialisée une seule fois : $B_k = T_k(\tilde{L})X$ pour $k=0, \dots, K$, où $\tilde{L}$ est le Laplacien du graphe rescalé et $T_k$ sont des polynômes de Chebyshev.
   • Une quadrature de Lanczos stochastique (SLQ) est utilisée pour générer une grille spectrale afin d'analyser les réponses des filtres.

2. Banque d'experts :

   • Au lieu de prédire des coefficients polynomiaux indépendants pour chaque paire nœud-canal (ce qui est prohibitivement coûteux et faible en termes de biais inductif), FilterMoE apprend une petite banque de $M$ experts de filtres de Chebyshev.
   • Chaque expert $m$ est défini par un ensemble de coefficients de Chebyshev $\alpha_m$, représentant une réponse spectrale spécifique $g_m(\lambda)$.

3. Routage conjoint nœud-canal :

   • Un tenseur de routage 3D $G \in \mathbb{R}^{N \times M \times F}$ route les experts. $G_{i,m,f}$ détermine le poids de l'expert $m$ pour le nœud $i$ et le canal de caractéristique $f$.
   • Cela permet à chaque paire nœud-canal d'avoir un filtre effectif unique $\beta_{i,f} = \sum_m G_{i,m,f} \alpha_m$, tout en contraignant tous les filtres à être des mélanges de la banque d'experts partagée.

4. Variantes du routeur :

   • MLP conjoint direct : Mappe directement les descripteurs de nœuds vers la grille complète de logits $M \times F$.
   • Routeur à deux étapes sensible à la réponse : Utilise les esquisses de réponse spectrale des experts comme clés. Il calcule d'abord un a priori au niveau du nœud sur les experts, puis l'affine avec des résidus au niveau des canaux. Cela conditionne explicitement le routage sur les formes spectrales des experts qui sont conscientes du graphe.

5. Objectif d'entraînement :

   • La perte principale est la perte de la tâche supervisée.
   • Régularisation auxiliaire :
     • Perte de diversité : Encourage des réponses spectrales distinctes parmi les experts dans l'espace de réponse spectrale (en utilisant la grille SLQ) pour éviter l'effondrement.
     • Perte de lissage : Pénalise les coefficients de Chebyshev de degré élevé pour assurer la stabilité des fil.
     • Équilibrage MoE : Pertes standard d'importance et d'équilibrage de charge pour assurer une utilisation équitable des experts.

Contributions clés

1. Analyse de la perspective Graphe-Filtre : L'article recadre la performance des PP-GNN non pas comme une fonction de la capacité de l'agrégateur, mais comme une fonction de la manière dont les coefficients de filtre sont partagés. Il idente que les méthodes existantes sont soit adaptatives au canal/partagées par le nœud, soit adaptatives au nœud/partagées par le canal, manquant ainsi le régime adaptatif conjoint.
2. Architecture FilterMoE : Un nouveau PP-GNN qui implémente un filtrage adaptatif conjoint nœud-canal via un mélange d'experts de Chebyshev partagés, routés par un tenseur de routage 3D.
3. Alternative robuste au réglage manuel : FilterMoE sert de mécanisme appris et robuste, éliminant le besoin de sélectionner manuellement des agrégateurs de hops spécifiques (MLP vs Attention vs Fusion) pour différents jeux de données.
4. Évaluation exhaustive : Des expériences étendues sur 11 benchmarks (homophiliques, hétérophiliques et à grande échelle) démontrent l'efficacité de l'approche.

Résultats expérimentaux

FilterMoE a été évalué sur 11 jeux de données, incluant quatre homophiliques, quatre hétérophiliques et trois graphes à grande échelle (Pokec, OGBN-Products, OGBN-Papers100M).

• Performance globale : FilterMoE a surpassé les bases les plus fortes des PP-GNN (SIGN, HOGA, GAMLP) sur 9 des 11 jeux de données, améliorant le score de test moyen de 1,53 point.
• Graphes à grande échelle : FilterMoE s'est classé premier sur les trois benchmarks à grande échelle, surpassant le meilleur baseline PP-GNN de +1,76 (Pokec), +0,93 (OGBN-Products) et +0,71 (OGBN-Papers100M).
• Comparaison avec les MP-GNN : Sur les grands graphes, FilterMoE a surpassé tous les MP-GNN évalués tout en maintenant l'efficacité de pré-propagation de l'entraînement. Sur les graphes plus petits, il est resté compétitif avec les variantes adaptatives spécialisées des MP-GNN (ex: variantes AGDN), mais n'a pas uniformément dominé, suggérant que sa force principale réside dans le régime PP-GNN.
• Études d'ablation :
  • Routage : Le routage conjoint nœud-canal a systématiquement surpassé les variantes à axe unique (nœud seul ou canal seul).
  • Opérateur : Le gain de performance n'est pas uniquement dû à l'opérateur de Chebyshev ; remplacer l'opérateur des baselines par Chebyshev les a améliorés mais n'a pas comblé l'écart avec FilterMoE.
  • Régularisation : La perte de lissage spectral était le régularisateur le plus critique, tandis que les pertes de diversité et d'équilibrage MoE apportaient des bénéfices plus faibles et dépendants du jeu de données.

Signification et affirmations

L'article affirme que la principale limitation des PP-GNN existants n'est pas un manque de complexité des agrégateurs, mais l'absence d'un mécanisme structuré pour apprendre des filtres de graphe qui soient conjointement adaptatifs aux nœuds et aux canaux tout en conservant la scalabilité.

FilterMoE établit le routage de filtre conjoint nœud-canal comme une alternative robuste à la sélection de l'agrégateur de hops spécifique à chaque jeu de données. En découplant la réponse spectrale (experts appris) du mécanisme de routage (porte de nœud-canal), le modèle atteint une haute expressivité sans réintroduire le problème d'explosion des voisins ou la surcharge de calcul du passage de messages à chaque époque. Les résultats suggèrent que pour la classification de nœuds à grande échelle, une stratégie de routage adaptative apprise sur une banque de filtres partagés est supérieure à la conception manuelle ou au réglage de têtes d'agrégation spécifiques pour chaque jeu de données.

Les auteurs restent modestes quant à la portée de l'étude, notant que le présent travail se concentre sur des graphes homogènes fixes pour la classification de nœuds. Les extensions vers la prédiction de liens, les tâches au niveau du graphe, les graphes hétérogènes et les graphes dynamiques sont identifiées comme des travaux futurs plutôt que des capacités actuelles.