Résumé technique : Affinement transductif sur graphes

Énoncé du problème

Dans le cadre transductif pour la classification de nœuds, la structure complète du graphe et les caractéristiques des nœuds sont observées durant l'entraînement, mais les étiquettes ne sont disponibles que pour un sous-ensemble de nœuds ($V_L$). Bien que les réseaux de neurones sur graphes (GNN) aient considérablement progressé grâce à des innovations architecturales (par exemple, des schémas de passage de messages, des transformateurs), la conception des objectifs d'entraînement a reçu une attention relativement moindre. L'entraînement supervisé standard minimise la perte d'entropie croisée uniquement sur les nœuds étiquetés, rejetant les prédictions générées pour les nœuds non étiquetés ($V_U$) à chaque étape d'entraînement. L'article postule que ces prédictions sur les nœuds non étiquetés contiennent des signaux d'entraînement utiles qui sont actuellement sous-exploités, car les objectifs standard ne peuvent les évaluer sans étiquettes de vérité terrain.

Méthodologie : Affinement transductif (TS)

Les auteurs proposent l'affinement transductif (TS), une modification au niveau de la perte qui exploite les prédictions sur les nœuds non étiquetés sans nécessiter de changements architecturaux. La méthode repose sur la décomposition de la perte d'entropie croisée en un terme d'alignement dépendant de l'étiquette et un terme d'entropie indépendant de l'étiquette.

Objectif principal

L'objectif TS enrichit la perte supervisée standard ($L_{sup}$) par des termes qui manipulent l'incertitude (entropie) des prédictions à travers le graphe :

$$L_{TS} = L_{sup} + \lambda \cdot \frac{1}{|V_U|} \sum_{v \in V_U} R(p_v) - \lambda \cdot \frac{1}{|V_L|} \sum_{v \in V_L} R(p_v)$$

Où :

• $p_v$ est la distribution de probabilité prédictive pour le nœud $v$.
• $R(p)$ est une fonction mesurant l'incertitude.
• $\lambda$ est un hyperparamètre scalaire contrôlant la force de l'affinement.

Détails de l'implémentation

• Fonction d'incertitude ($R$) : Les auteurs choisissent l'entropie de Tsallis avec $q=2$ (équivalente à l'impureté de Gini, $S_2(p) = 1 - \sum p_i^2$) plutôt que l'entropie de Shannon. Ce choix est motivé par la forme quadratique de l'entropie de Tsallis, qui produit des gradients linéaires en $p$. Cela assure une dynamique d'entraînement stable et prévient les mises à jour excessivement agressives ou les solutions dégénérées en un seul élément (one-hot solutions) souvent associées aux gradients logarithmiques de l'entropie de Shannon près de la frontière du simplexe de probabilité.
• Mécanisme symétrique :
  • Sur les nœuds non étiquetés ($V_U$) : Le terme minimise l'incertitude (maximise la confiance), encourageant le modèle à traiter ses propres prédictions fiables comme un signal d'apprentissage.
  • Sur les nœuds étiquetés ($V_L$) : Le terme maximise l'incertitude (contrebalance la surconfiance), agissant comme un régularisateur pour prévenir le surapprentissage aux étiquettes d'entraînement.
• Hyperparamètre : La méthode introduit un seul hyperparamètre scalaire, $\lambda$. Les auteurs démontrent qu'un réglage conservateur et universel de $\lambda = 0,25$ fonctionne de manière compétitive sur des ensembles de données et des architectures diversifiés, sans nécessiter de réglage par ensemble de données.

Contributions clés

1. Introduction de l'affinement transductif (TS) : Une modification simple et indépendante de l'architecture de la perte qui transforme les prédictions sur les nœuds non étiquetés en signaux d'entraînement directs pour la classification transductive de nœuds.
2. Compromis performance-complexité : TS améliore les références standard des GNN (GCN, GraphSAGE, GAT) et des MLP sur 13 benchmarks de classification de nœuds, tout en n'ajoutant qu'un seul hyperparamètre et sans nécessiter de modifications de l'architecture de base.
3. Analyse du coefficient d'affinement ($\lambda$) : Les auteurs montrent que TS est efficace sur une plage de valeurs positives de $\lambda$. Ils identifient qu'un affinement modéré (par exemple, $\lambda \in [0, 0,5]$) produit les gains les plus fiables, tandis qu'un affinement excessif peut contraindre le modèle à s'engager trop fortement dans des prédictions incorrectes.
4. Insight mécanistique : L'analyse empirique révèle que TS réalloue avec succès la confiance prédictive vers les nœuds non étiquetés, créant un écart d'entropie plus important entre les nœuds étiquetés et non étiquetés par rapport à la référence supervisée.

Résultats expérimentaux

L'article évalue TS sur 13 ensembles de données (incluant Cora, CiteSeer, PubMed et divers graphes hétérophiles) en utilisant les architectures de base GCN, GraphSAGE, GAT et MLP.

• Améliorations constantes : TS améliore ou égale systématiquement les performances des références supervisées. Par exemple, sur l'ensemble de données Cora, la précision du GCN passe de 84,54 % à 85,74 % (+1,20), et celle du MLP passe de 60,96 % à 64,48 % (+3,52).
• MLP vs GNN : Bien que TS améliore les MLP (démontrant que le signal n'est pas spécifique au passage de messages sur graphes), les performances de MLP+TS restent inférieures à celles des GNN, confirmant que TS ne remplace pas les avantages du passage de messages.
• Hyperparamètre universel : Un $\lambda = 0,25$ fixe appliqué sur tous les ensembles de données et architectures préserve une grande partie du bénéfice du réglage par ensemble de données, causant rarement des régressions de performance significatives.
• Études d'ablation :
  • Supprimer le terme de correction sur les nœuds étiquetés (maximisation de l'entropie sur $V_L$) dégrade généralement les performances, soulignant l'importance d'équilibrer l'affinement sur les nœuds non étiquetés avec la régularisation sur les nœuds étiquetés.
  • Les configurations asymétriques (décalage de $\lambda$) ne produisent pas d'améliorations systématiques par rapport à la formulation symétrique.
  • L'apprentissage par méta-apprentissage de $\lambda$ dynamiquement durant l'entraînement donne de moins bons résultats que l'utilisation d'une constante fixe sélectionnée par validation, suggérant que la complexité ajoutée introduit une instabilité.

Importance et affirmations

L'article affirme que l'affinement transductif offre un compromis performance-complexité fort. En réexaminant l'objectif d'entraînement plutôt que l'architecture, les auteurs démontrent que les prédictions généralement rejetées durant l'apprentissage transductif (en raison de l'absence d'étiquettes) fournissent un signal utile et sous-exploité.

L'importance réside dans la simplicité et la généralité de l'approche :

• Elle ne nécessite aucun changement architectural dans les pipelines GNN existants.
• Elle ajoute une surcharge computationnelle négligeable.
• Elle offre une voie générale pour améliorer les algorithmes d'apprentissage dans des contextes transductifs sans augmenter la complexité du modèle.

Les auteurs concluent que, bien que leur travail se concentre sur la classification transductive de nœuds, le principe d'exploitation des prédictions non étiquetées via des objectifs basés sur la confiance pourrait s'étendre à d'autres contextes, tels que la prédiction de liens ou la classification temporelle de nœuds, offrant une méthode légère pour extraire de la valeur de la structure complète du graphe durant l'entraînement.