Invariant-Based Diagnostics for Graph Benchmarks

Résumé technique : Diagnostics basés sur les invariants pour les benchmarks de graphes

Énoncé du problème
Les progrès dans le développement de modèles de base pour les graphes (GFMs) sont actuellement entravés par des pratiques d'évaluation qui confondent les contributions des caractéristiques des nœuds et de la structure du graphe. Cette confusion rend difficile la détermination de savoir si un modèle apprend véritablement à partir de la connectivité ou s'il exploite simplement des corrélations de caractéristiques. De plus, les pratiques d'évaluation existantes souffrent de tailles de jeux de données réduites, d'un manque de diversité structurelle au sein des jeux de données, et d'une suraccentuation de l'expressivité théorique (par exemple, la capacité à distinguer des graphes non isomorphes) qui peut ne pas correspondre aux performances prédictives réelles sur des tâches spécifiques. Les auteurs soutiennent que les Réseaux de Neurones à Graphes (GNN) standards sont inadaptés pour isoler l'impact de la structure, car ils entremêlent les informations structurelles et les caractéristiques lors du processus de passage de messages.

Méthodologie
Les auteurs proposent un cadre de diagnostic basé sur les invariants de graphe : des descripteurs structurels permutation-invariants et agnostiques de la tâche qui servent d'« empreintes digitales structurelles » pour les graphes. Ces invariants sont des proxies calculables de la structure du graphe qui ne reposent pas sur des paramètres entraînables.

• Construction des invariants : L'étude utilise un ensemble diversifié d'invariants, incluant des mesures de théorie des graphes de base (par exemple, le diamètre, le rang cyclique), des métriques basées sur l'entropie (par exemple, l'entropie de von Neumann), des invariants géométriques et topologiques (par exemple, la torsion analytique, les comptes d'homomorphismes), et des indices moléculaires (par exemple, l'indice de Wiener, l'indice de Balaban). Ceux-ci sont concaténés en un seul vecteur de caractéristiques par graphe.
• Modèles : Les auteurs emploient deux familles de modèles principales :
  1. Ensembles d'arbres à gradient boosté (XGBoost) : Utilisés comme classificateur principal pour les baselines basées sur les invariants. Ce choix est délibéré pour assurer l'efficacité computationnelle et la facilité de réglage des hyperparamètres sur 26 jeux de données divers.
  2. Réseaux de Neurones à Graphes (GIN) : Utilisés dans des expériences d'apprentissage multi-tâches pour analyser l'alignement des gradients et l'hétérogénéité structurelle.
• Scénarios expérimentaux : La méthodologie est appliquée à travers quatre configurations expérimentales distinctes :
  1. Analyse de l'expressivité : Tester la capacité des invariants à distinguer des paires de graphes non isomorphes sur le jeu de données BREC (graphes indistingables par le test 1-Weisfeiler-Lehman).
  2. Caractérisation des jeux de données : Traiter l'appartenance à un jeu de données comme une tâche de « méta-classification » pour quantifier l'hétérogénéité structurelle au sein et entre les domaines.
  3. Prédiction des performances multi-tâches : Investiguer la corrélation entre les différences structurelles (mesurées par la précision de méta-classification basée sur les invariants) et l'alignement des gradients/les performances en aval dans des configurations d'apprentissage multi-tâches.
  4. Étalonnage (Benchmarking) : Évaluer quatre configurations d'entrée — caractéristiques basées sur la somme, caractéristiques basées sur l'agrégation, invariants complets, et un sous-ensemble minimal expressif d'invariants — sur 26 jeux de données pour démêler les rôles des caractéristiques, du passage de messages, de l'expressivité et de la structure globale.

Contributions et résultats clés

1. Expressivité des invariants :

   • Il est démontré que les invariants sont plus expressifs que les GNN standards dans le contexte du jeu de données BREC. Une combinaison simple d'invariants (spécifiquement un sous-ensemble de quatre) atteint 73 % de précision dans la distinction de paires non isomorphes, surpassant la plupart des méthodes basées sur les GNN et égalant les performances d'architectures plus complexes comme N2.
   • Les auteurs démontrent qu'une haute expressivité ne nécessite pas l'ensemble complet des invariants ; une sélection gloutonne révèle qu'un petit sous-ensemble suffit pour capturer le même pouvoir discriminant.

2. Caractérisation de l'hétérogénéité structurelle :

   • Les invariants caractérisent efficacement les jeux de données de référence existants. Un méta-classificateur utilisant les invariants atteint une précision d'environ 56 % pour distinguer 23 jeux de données de domaines différents et d'environ 93 % de précision lors de la distinction de jeux de données au sein du même domaine.
   • Cela indique un « décalage de jeu de données » prononcé où les graphes d'un même domaine possèdent toujours des signatures structurelles distinctes, suggérant que les benchmarks actuels manquent de l'homogénéité requise pour une généralisation robuste.

3. Prédiction des performances multi-tâches :

   • Il existe une corrélation négative constante entre la dissimilarité structurelle de deux jeux de données (mesurée par la précision de méta-classification) et leurs performances dans une configuration d'apprentissage multi-tâches.
   • Une plus grande dissimilarité structurelle entraîne un alignement des gradients plus faible et des performances en aval réduites, suggérant que les décalages structurels sont un obstacle principal à un pré-entraînement efficace et à l'apprentissage par transfert entre les domaines.

4. Compétitivité des modèles basés sur les invariants :

   • Des modèles simples basés sur les invariants (XGBoost entraîné sur des vecteurs d'invariants) sont compétitifs avec, et dans certains cas surpassent, les baselines de transformateurs et de passage de messages les plus avancés sur 26 jeux de données.
   • Notamment, sur les jeux de données « flow », les modèles basés sur les invariants ont surpassé les meilleurs résultats rapportés avec une marge significative.
   • L'étude révèle que l'expressivité n'est pas le moteur principal des performances prédictives. Un sous-ensemble d'invariants ayant la même expressivité que l'ensemble complet produit souvent des performances prédictives inférieures, indiquant que la pertinence spécifique à la tâche de la structure importe plus que la puissance discriminante brute.
   • Dans de nombreux cas, l'ajout d'invariants aux baselines basées sur les caractéristiques améliore les performances, mais dans certaines tâches (par exemple, CIFAR10 représenté sous forme de grilles de pixels), les invariants n'apportent aucun gain, indiquant que la structure joue un rôle marginal.

Signification et affirmations
L'article postule que les baselines basées sur les invariants devraient devenir une norme pour l'évaluation des benchmarks de graphes. Les auteurs soutiennent que ces baselines remplissent deux fonctions critiques :

1. Outil de diagnostic : Elles aident à déterminer si une tâche spécifique nécessite réellement la structure du graphe. Si un modèle simple basé sur les invariants performe aussi bien qu'un GNN complexe, la tâche peut ne pas reposer sur des informations structurelles.
2. Vérification de l'alignement : Elles fournissent un « contrôle de bon sens » pour détecter un désalignement modèle-tâche. Si un modèle complexe ne parvient pas à surpasser substantiellement une baseline invariante, le déficit reflète probablement un sous-réglage ou une incapacité à extraire une structure significative, plutôt qu'une limitation fondamentale de l'architecture.

Les auteurs concluent que l'accent actuel mis sur l'expressivité comme objectif de conception principal mérite d'être reconsidéré. Au lieu de cela, le domaine devrait se concentrer sur la compréhension de la pertinence de la structure pour des tâches spécifiques. Les diagnostics basés sur les invariants offrent un point de contrôle nécessaire pour s'assurer que les jeux de données sont adaptés à l'apprentissage sur graphes avant de poursuivre des objectifs plus ambitieux comme les modèles de base pour les graphes. L'article ne prétend pas que les invariants remplacent les GNN, mais plutôt qu'ils fournissent une baseline minimale et nécessaire pour valider si la structure est apprise efficacement.