Résumé technique : Réseau de neurones sur graphes exploitant la connectivité de classe d'ordre supérieur pour les graphes hétérophiles

Énoncé du problème

La classification de nœuds dans les réseaux de neurones sur graphes (GNN) a atteint une grande précision dans les graphes homophiles, où les nœuds ayant des étiquettes de classe similaires ont tendance à être connectés. Cependant, les performances se dégradent considérablement dans les graphes hétérophiles, où les nœuds ayant des étiquettes de classe différentes sont plus susceptibles d'être connectés.

Les auteurs identifient une limitation spécifique des GNN actuels (y compris ceux dérivés des réseaux de neurones convolutionnels sur graphes comme GCN, GAT et les modèles avancés pour l'hétérophilie comme H2GCN et LINKX) : ils transforment le problème de classification de nœuds en une simple mise en correspondance de l'espace d'embedding vers l'espace des étiquettes de classe. Par conséquent, ces modèles ne parviennent pas à capturer la connectivité de classe d'ordre supérieur — les relations structurelles entre les étiquettes de classe qui s'étendent sur plusieurs sauts via des arêtes dirigées. Bien que certaines méthodes utilisent une matrice de compatibilité de classe pour capturer la connectivité de premier ordre, elles ne tiennent pas compte des interactions complexes de labels multi-sauts fréquemment observées dans les graphes dirigés du monde réel (par exemple, l'ensemble de données Texas, où les nœuds « Student » se connectent aux nœuds « Department », qui se connectent ensuite aux nœuds « Staff »).

Méthodologie

L'approche proposée introduit un nouveau classificateur, le Label Context Classifier (LCC), et un cadre pour l'intégrer aux GNN existants.

1. Label Context Classifier (LCC)

Le LCC est conçu pour capturer la connectivité de classe d'ordre supérieur en traitant les séquences d'étiquettes de classe le long des marches de graphe comme un contexte, inspiré par le modèle word2vec Skip-gram. Le processus comprend trois étapes principales :

• Extraction de la marche de labels (Label Walk Extraction) : À partir d'un nœud cible, quatre types distincts de marches de labels sont extraits. Une marche de labels est une séquence d'étiquettes de classe où les nœuds sont remplacés par leurs étiquettes. Si un nœuf n'est pas dans l'ensemble d'entraînement, une étiquette nulle est utilisée.
  • Marche directe (Forward Walk) : Une recherche en profondeur suivant la direction des arêtes (Cible $\to$ Enfant $\to$ Petit-enfant).
  • Marche inverse (Backward Walk) : Une recherche en profondeur suivant la direction inverse des arêtes (Cible $\to$ Parent $\to$ Grand-parent).
  • Marche de fratrie (Sibling Walk) : Traverse vers l'arrière vers un nœud parent, puis vers l'avant vers ses autres enfants (Cible $\to$ Parent $\to$ Fratrie). Cela capture la connectivité entre les nœuds partageant un parent commun.
  • Marche de gardien (Guardian Walk) : Traverse vers l'avant vers un nœud enfant, puis vers l'arrière vers ses autres parents (Cible $\to$ Enfant $\to$ Co-parent). Cela capture la connectivité entre les nœuds partageant un enfant commun.
• Génération d'embedding de contexte de label (Label Context Embedding Generation) : En utilisant les marches de labels extraites, le modèle apprend des embeddings qui représentent le « contexte de label ». Un simple perceptron multicouche (MLP) à deux couches est entraîné pour prédire les étiquettes de contexte (les étiquettes suivantes dans la marche) étant donné l'étiquette du nœud cible en entrée. La couche cachée produit les embeddings de contexte de label ($Z$).
• Entraînement du classificateur : Le classificateur LCC final est un MLP entraîné sur la concaténation des caractéristiques originales du nœud et des embeddings de contexte de label dérivés des quatre types de marches.

2. Intégration avec les GNN

Pour tirer parti des forces des GNN traditionnels (qui capturent les caractéristiques et les informations structurelles locales) et du LCC (qui capture la connectivité de classe d'ordre supérieur), les auteurs proposent un schéma d'intégration adaptatif :

• Entraînement indépendant : Le GNN et le LCC sont entraînés indépendamment sur l'ensemble d'entraînement.
• Pondération adaptative : L'importance de chaque modèle est déterminée par la perte de validation. Les poids ($w_{LCC}$ et $w_{GNN}$) sont calculés comme l'inverse de la perte de validation, ajustés par un paramètre de température ($T$).
• Prédiction d'ensemble : La prédiction finale est une moyenne pondérée des sorties du GNN et du LCC. Cette intégration ne nécessite aucun entraînement de modèle supplémentaire, seulement le calcul des poids basés sur la performance de validation.

Principales contributions

1. Proposition du LCC : Un nouveau classificateur qui estime les étiquettes des nœuds en capturant la connectivité de classe d'ordre supérieur via quatre marches de labels orientées (Directe, Inverse, Fratrie, Gardien).
2. Cadre d'intégration adaptatif : Une méthode pour intégrer le LCC à n'importe quel GNN existant en apprenant de manière adaptative les poids d'importance basés sur la perte de validation, sans nécessiter de coûts d'entraînement supplémentaires.
3. Validation empirique : Des résultats expérimentaux démontrant que l'intégration du LCC avec les GNN surpasse les méthodes de l'état de l'art (SOTA) sur les graphes dirigés hétérophiles.

Résultats expérimentaux

Les auteurs ont évalué leur méthode sur sept ensembles de données de graphes dirigés hétérophiles : Cornell, Texas, Wisconsin, Chameleon, Squirrel, Roman-Empire et Amazon-Ratings.

• Amélioration des performances : Les modèles intégrés (ex: H2GCN+LCC, LINKX+LCC, GloGNN+LCC) ont obtenu les taux de précision de classification de nœuds les plus élevés sur tous les ensembles de données par rapport aux GNN seuls, aux MLP et au LCC seul.
• Complémentarité : Les résultats indiquent que le LCC et les GNN capturent des propriétés de graphes différentes. Dans la plupart des cas, l'intégration a amélioré la précision par rapport aux composants individuels.
• Efficacité des marches de labels : Le LCC a nettement surpassé un MLP classique (qui n'utilise que les caractéristiques du nœud), confirmant que les embeddings de contexte de label capturent efficacement la connectivité des étiquettes de classe. Notamment, les gains de précision ont dépassé les 10 % sur des ensembles comme Chameleon, Squirrel, Roman-Empire et Amazon-Ratings.
• Importance du type de marche : L'importance de types de marches spécifiques variait selon l'ensemble de données. Par exemple, les marches de gardien étaient les plus critiques pour Chameleon, Squirrel et Amazon-Ratings, tandis que les marches de fratrie étaient les plus efficaces pour Roman-Empire.
• Longueur de la marche : Augmenter la longueur de la marche (pour les marches directes/inverses) ou utiliser des marches à 2 sauts (fratrie/gardien) a généralement amélioré les performances, soulignant la nécessité de capturer la connectivité d'ordre supérieur.

Signification et affirmations

L'article affirme que la principale faiblesse des GNN actuels dans les contextes hétérophiles est leur incapacité à modéliser comment les étiquettes de classe se connectent à travers plusieurs sauts dans les graphes dirigés. En modélisant explicitement ces relations d'ordre supérieur via des marches de labels, le LCC fournit un signal complémentaire aux GNN basés sur les caractéristiques.

Les auteurs soulignent que leur approche ne nécessite pas de changements architecturaux complexes aux GNN existants ; elle offre plutôt un classificateur modulaire qui peut être combiné de manière adaptative avec n'importe quel GNN pour améliorer les performances. Les résultats suggèrent que l'exploitation des informations structurelles entre les étiquettes de classe, plutôt que simplement les caractéristiques des nœuds ou les voisins immédiats, est cruciale pour une classification précise dans les graphes dirigés hétérophiles. Ce travail est soutenu par les bourses JSPS KAKENHI et JST ASPIRE.