Résumé Technique : Condensation de Graphes Attribués à du Texte via la Sélection de Texte et l'Appariement d'Attributs

Énoncé du Problème

Les graphes attribués à du texte (TAG - Text-Attributed Graphs) intègrent la topologie de graphe aux descriptions textuelles des nœuds, permettant des tâches en aval puissantes comme la classification zero-shot et la classification d'articles grâce à l'entraînement conjoint de réseaux de neurones sur graphes (GNN) et de modèles de langage (LM). Cependant, cet entraînement multimodal est coûteux en termes de calcul, nécessitant une mémoire et un temps considérables, particulièrement sur les jeux de données à grande échelle.

Bien que la condensation de jeu de données (Dataset Condensation) offre une solution en compressant de grands jeux de données en d'autres plus petits et représentatifs, les méthodes existantes ne traitent pas les TAG de manière efficace :

1. Condensation de graphes traditionnelle (ex: GCond) : Ces méthodes compressent généralement uniquement la modalité de graphe, ignorant les riches informations textuelles. De plus, elles reposent souvent sur une supervision par étiquettes, ce qui est incompatible avec les scénarios TAG où les étiquettes de vérité terrain sont rares ou coûteuses à obtenir.
2. Condensation multimodale (ex: MTT-VL) : Les méthodes basées sur l'Appariement de Trajectoires d'Entraînement (MTT - Matching Training Trajectories) tentent de compresser à la fois l'image et le texte. Cependant, appliquées aux TAG, elles font face à deux problèmes critiques :
   • Texte illisible : Le MTT optimise le texte dans un espace d'embedding continu via la descente de gradient. Cela produit des vecteurs d'embedding illisibles, incompatibles avec les tokeniseurs et les modèles de langage en aval.
   • Entraînement instable : Dans les TAG, les modèles enseignants sont souvent entraînés via l'apprentissage contrastif. La perte dans l'apprentissage contrastif dépend de l'ensemble du batch, ce qui entraîne une variance élevée dans les trajectoires d'entraînement. Cette instabilité entrave la capacité du modèle étudiant à correspondre à la trajectoire de l'enseignant, entraînant une convergence sous-optimale.

La question de recherche centrale est : Est-il possible de concevoir une méthode de condensation de TAG pour des scénarios sans étiquettes qui génère un texte compressé discret et lisible, et qui atteigne une convergence stable ?

Méthodologie : TAGSAM

Les auteurs proposent TAGSAM, un cadre de condensation comprenant deux composants clés : la Sélection de Texte de Sous-graphe et l'Appariement de Similitude d'Attributs.

1. Sélection de Texte de Sous-graphe

Au lieu d'optimiser des embeddings continus, TAGSAM sélectionne et fusionne des fragments de texte représentatifs de l'espace discret original pour former des textes compressés concis et lisibles.

• Processus :
  1. Échantillonnage de sous-graphes : Échantillonner aléatoirement $M$ sous-graphes à partir du graphe original en utilisant une recherche en largeur (BFS).
  2. Découpage en fragments et notation : Diviser le texte au sein de chaque sous-graphe en fragments. Calculer un Score de Représentativité (RS - Representative Score) pour chaque fragment basé sur l'Information Mutuelle par Fragment (CMI - Chunk-wise Mutual Information). Le RS maximise la couverture d'information du sous-graphe tout en pénalisant la redondance.
  3. Sélection et Fusion : Un algorithme glouton sélectionne séquentiellement les top-$k$ fragments ayant le RS le plus élevé pour former un texte compressé $\hat{T}_i$.
• Garantie Théorique : Les auteurs prouvent que cette sélection gloutonne approxime la solution optimale avec un facteur de $(1 - 1/e)$.

2. Appariement de Similitude d'Attributs (ASM)

Pour compresser la structure du graphe et les caractéristiques des nœuds, TAGSAM remplace l'approche MTT instable par l'Appariement de Similitude d'Attributs.

• Mécanisme : Au lieu d'aligner les trajectoires complètes de mise à jour des paramètres (qui souffrent d'une variance élevée), l'ASM aligne les matrices de similitude d'attributs entre les modèles enseignant et étudiant.
  • La matrice de similitude $S_M$ est calculée comme le produit des embeddings de graphe et des embeddings de texte pour toutes les paires de nœuds.
  • L'appariement minimise l'écart entre la matrice de similitude de l'étudiant et celle de l'enseignant, en utilisant un softmax par ligne avant une entropie croisée binaire (sBCE) pour assurer des gradients plus lents.
• Justification Théorique : Les auteurs démontrent que dans l'apprentissage contrastif, la similitude optimale entre attributs correspond à leur Information Mutuelle Ponctuelle (PMI). Contrairement aux trajectoires complètes, qui sont sensibles aux matrices de rotation et de mise à l'échelle arbitraires dans l'espace de l'encodeur, la matrice de similitude est intrinsèquement stable et invariante à ces transformations.
• Efficacité : Contrairement au MTT, qui nécessite l'entraînement de plusieurs modèles enseignants (typiquement 15) pour capturer des trajectoires diverses, l'ASM ne nécessite qu'un seul modèle enseignant, réduisant considérablement le coût computationnel.

Contributions Clés

1. Identification du Problème : Les auteurs identifient que la condensation de graphes traditionnelle est inappropriée pour les TAG en raison de la négligence du texte et de la dépendance aux étiquettes, tandis que les méthodes multimodales existantes échouent à cause des sorties de texte illisibles et de l'instabilité de l'entraînement causée par les trajectoires contrastives à haute variance.
2. Cadre Novateur (TAGSAM) :
   • Sélection de Texte de Sous-graphe : Une méthode pour compresser le texte dans l'espace discret en sélectionnant des fragments représentatifs via l'information mutuelle, garantissant que la sortie reste lisible et compatible avec les tokeniseurs.
   • Appariement de Similitude d'Attributs : Une technique de condensation robuste qui aligne des matrices de similitude d'attributs stables plutôt que des trajectoires d'entraînement volatiles, améliorant la stabilité de la convergence.
3. Analyse Théorique : L'article fournit des preuves théoriques montrant que la sélection de texte gloutonne approxime la solution optimale et que la similitude d'attribut sert d'estimateur stable de la PMI, justifiant la robustesse de la stratégie d'appariement.

Résultats Expérimentaux

Les auteurs ont évalué TAGSAM sur cinq jeux de données (Cora, Photo, Computer, Arxiv, Products) allant de 2,7K à 2,4M de nœuds, en le comparant à six bases de référence de pointe (Random, Herding, K-Center, GCond*, MTT-TAG, MTT-KNN).

• Précision de Classification : TAGSAM a systématiquement surpassé toutes les bases de référence. En moyenne, il a amélioré la précision de 4,9 % par rapport à la meilleure base de référence (MTT-TAG). Notamment, il a atteint une précision compétitive même en condensant le jeu de données à seulement 1 % de sa taille originale.
• Prédiction de Liens : TAGSAM a obtenu des améliorations significatives de l'AUC (jusqu'à 4,1 % par rapport à Random et 2,1 % par rapport à MTT-TAG), indiquant une meilleure rétention de l'information structurelle.
• Généralisation Trans-Architecture : Les modèles entraînés sur les données condensées par TAGSAM maintiennent une précision plus élevée lorsqu'ils sont testés avec différentes architectures d'encodeurs (ex: GCN, SAGE, Cheby) par rapport aux bases de référence.
• Efficacité : Bien que la condensation entraîne un coût unique, TAGSAM accélère considérablement les recherches d'hyperparamètres en aval. Grâce à l'exigence d'un seul enseignant, TAGSAM est plus scalable que les méthodes basées sur le MTT pour les grands graphes.
• Études d'Ablation : Les expériences ont confirmé que la sélection de texte de sous-graphe et l'appariement de similitude d'attributs sont tous deux essentiels, leur combinaison produisant des performances supérieures aux variantes utilisant une sélection aléatoire ou l'appariement de trajectoire.

Signification

L'article affirme que TAGSAM rend possible le pré-entraînement efficace sur des graphes attribués à du texte à grande échelle. En abordant les défis spécifiques de la compression de texte discret et de l'instabilité de l'apprentissage contrastif, TAGSAM permet la création de jeux de données hautement compressés qui préservent l'information conjointe nécessaire pour une classification zero-shot efficace et d'autres tâches TAG, sans dépendre d'une supervision par étiquettes coûteuse.