Résumé Technique : FUSE Contrastif

Énoncé du Problème

L'article aborde le défi de l'apprentissage de représentations de nœuds significatives dans des graphes où les caractéristiques explicites des nœuds sont indisponibles, peu fiables ou non transférables (graphes sans caractéristiques ou à caractéristiques clairsemées). Contrairement aux méthodes d'embedding de graphes non supervisées standard qui reposent uniquement sur la structure du graphe, ou aux méthodes d'apprentissage contrastif auto-supervisé qui dépendent d'augmentations de données, ce travail se concentre sur un cadre où la supervision est disponible uniquement sous la forme de contraintes partielles par paires. Ces contraintes indiquent si deux nœuds doivent être similaires (liens obligatoires) ou dissimilaires (liens interdits), un scénario courant dans des domaines tels que la biologie computationnelle (par exemple, la prédiction de létalité synthétique), les systèmes de recommandation (retour d'information implicite) et les réseaux sensibles à la vie privée où les attributs des nœuds sont inaccessibles.

L'objectif est de développer un cadre rapide et évolutif qui apprend des embeddings de nœuds discriminatifs en optimisant conjointement :

1. Cohérence Structurelle : Préservation de la structure communautaire globale du graphe.
2. Cohérence par Paires : Respect des contraintes de supervision par paires signées fournies (attirance des paires similaires, répulsion des paires dissimilaires).

Méthodologie : FUSE Contrastif

Les auteurs proposent FUSE Contrastif, un cadre unifié qui intègre l'apprentissage structurel basé sur la modularité avec une supervision contrastive via une formulation spectrale.

1. Fonction Objectif

L'objectif principal $J(S)$ combine un terme structurel et un terme contrastif :
$$J(S) = \text{Tr}(S^\top \tilde{B}S) - \lambda \text{Tr}(S^\top L_c S)$$

• Terme Structurel (Modularité) : Le premier terme maximise la modularité, encourageant les nœuds au sein d'une même communauté à avoir des embeddings similaires. Les auteurs utilisent une matrice de modularité modifiée $\tilde{B} = A - \frac{d\mathbf{1}^\top}{2m}$, où $A$ est la matrice d'adjacence, $d$ est le vecteur des degrés, et $m$ est le nombre total d'arêtes.
• Terme Contrastif : Le deuxième terme utilise un Laplacien contrastif signé et normalisé ($L_c$) construit à partir de la matrice de supervision par paires $Y$ (où $Y_{ij} \in \{+1, -1, 0\}$). Ce terme agit comme un régularisateur qui rapproche les paires positives et éloigne les paires négatives dans l'espace d'embedding, normalisé par le degré contrastif de chaque nœud pour éviter la domination des nœuds fortement contraints.

2. Optimisation Efficace par Approximation du Gradient

Une innovation clé réside dans la gestion du gradient de modularité. Le gradient exact de l'objectif de modularité implique un terme de correction degré-degré ($d(d^\top S)$), qui est coûteux en calcul et numériquement instable pour les grands graphes denses.

• Approximation : Les auteurs proposent une approximation légère en remplaçant l'agrégation pondérée des degrés $d^\top S$ par la somme globale non pondérée $\mathbf{1}^\top S$.
• Justification Théorique : L'article démontre (Théorème 2) que, sous des hypothèses modérées concernant la distribution des embeddings et la structure des degrés du graphe, la direction de montée du gradient approximatif proposé reste étroitement alignée avec le gradient exact (similarité cosinus bornée). Cela permet des économies de calcul significatives tout en préservant le comportement de recherche de structure de la modularité.

3. Algorithme d'Optimisation

Le cadre emploie une ascente de gradient projetée :

1. Calculer le gradient structurel ($G_{mod} = \tilde{B}S$) et le gradient contrastif ($G_{con} = -L_c S$).
2. Combiner les gradients : $G = G_{mod} + \lambda G_{con}$.
3. Mettre à jour les embeddings : $\tilde{S} = S + \eta G$.
4. Projection : Imposer des contraintes de norme unitaire par normalisation ligne par ligne ($S_i \leftarrow \tilde{S}_i / \|\tilde{S}_i\|_2$) pour éviter des solutions d'échelle triviales.
5. Classification en Aval : Les embeddings appris sont utilisés comme caractéristiques d'entrée pour un classificateur basé sur un GNN (GCN, GAT ou GraphSAGE) suivi d'un MLP pour prédire les relations par paires.

Contributions Clés

1. Formulation Contrastive Nouvelle : Introduction d'une méthode pour l'apprentissage de représentations de nœuds sous supervision par paires qui intègre directement les contraintes de paires de nœuds étiquetées dans l'objectif d'embedding sans nécessiter de caractéristiques de nœuds.
2. Laplacien Contrastif Signé et Normalisé : Proposition d'un opérateur Laplacien spécifique qui améliore l'apprentissage basé sur la modularité en attirant simultanément les paires similaires et en repoussant les paires dissimilaires de manière normalisée.
3. Schéma d'Optimisation Évolutif : Développement d'une approximation computationnellement efficace du gradient de modularité qui réduit considérablement la surcharge tout en maintenant un alignement théorique avec l'objectif exact, permettant l'entraînement sur des graphes à millions d'arêtes.

Résultats Expérimentaux

La méthode a été évaluée sur un ensemble diversifié de références, incluant des réseaux de citations (Cora, CiteSeer, PubMed), des graphes d'achat commun (Amazon Photo, WikiCS) et des ensembles de données OGB à grande échelle (ArXiv, Products).

• Performance : FUSE Contrastif a obtenu des performances de classification de nœuds en aval compétitives ou supérieures (Précision et Macro-F1) par rapport aux références de l'état de l'art, incluant des méthodes non supervisées (DeepWalk, Node2Vec), des méthodes contrastives auto-supervisées (DGI, GRACE, SGCL) et des méthodes spectrales (COLES).
• Évolutivité et Efficacité : Le cadre a démontré des gains substantiels en temps d'exécution. Sur des ensembles de données de taille moyenne, il était significativement plus rapide que les références contrastives comme GRACE et SGCL. Sur le grand ensemble de données OGBN-ArXiv, il était environ 13 à 14 fois plus rapide que les méthodes basées sur des marches aléatoires (DeepWalk, Node2Vec) tout en maintenant des performances compétitives. Plusieurs autres références n'ont pas pu être exécutées sur ArXiv en raison de contraintes de mémoire.
• Ablation : La suppression du terme contrastif (en fixant $\lambda=0$) a entraîné des performances systématiquement plus faibles, confirmant la nécessité de la supervision par paires pour apprendre des représentations discriminatives dans des contextes sans caractéristiques.

Signification et Revendications

L'article revendique que FUSE Contrastif comble efficacement le fossé entre la détection de communautés structurelles et l'apprentissage supervisé par paires. Sa signification principale réside dans l'offre d'une alternative rapide et évolutive aux méthodes d'apprentissage contrastif existantes qui reposent généralement sur des encodeurs profonds coûteux, des augmentations de données extensives ou des architectures de passage de messages.

En couplant l'apprentissage structurel inspiré de la modularité avec une supervision contrastive, le cadre permet un apprentissage efficace des embeddings de nœuds dans des scénarios où les caractéristiques des nœuds sont absentes mais où les relations par paires sont connues. Les auteurs soulignent que cette approche est particulièrement précieuse pour les graphes évolutifs ou spécifiques au contexte où les embeddings doivent être recalculés efficacement, et pour des domaines comme la bioinformatique et les réseaux sensibles à la vie privée où l'apprentissage basé uniquement sur la structure est une nécessité. La méthode atteint un compromis favorable entre précision prédictive et efficacité computationnelle, la rendant adaptée à des applications réelles à grande échelle.