When Should Graph Attention Be Sparse? Learning a Per-Edge Tsallis Index

Énoncé du Problème

Les réseaux d'attention sur graphes (GAT) normalisent les scores de pertinence des voisinages à l'aide de la fonction softmax, ce qui correspond à la solution de l'entropie maximale sous les statistiques de Shannon. Cette conception suppose implicitement que les poids d'attention devraient être distribués selon des statistiques extensives (Boltzmann–Gibbs). Cependant, les graphes du monde réel violent souvent ces hypothèses :

• Les graphes homophiles (ex. : réseaux de citations) bénéficient souvent d'une concentration sur quelques voisins hautement pertinents, ignorant la longue traîne des voisins faiblement liés.
• Les graphes hétérophiles (ex. : graphes web) bénéficient souvent de l'agrégation de petites quantités de preuves provenant de nombreux voisins dissemblables.

Le softmax standard est sous-optimal pour les deux régimes car il ne peut pas représenter des zéros exacts (forçant une attention dense) et impose un comportement de queue fixe. Bien qu'il existe des alternatives de sparsité comme Sparsemax et $\alpha$-entmax, elles reposent généralement sur des hyperparamètres fixes ou sont restreintes à des régimes spécifiques (par exemple, $\alpha$-entmax n'est défini que pour $\alpha \ge 1$, manquant ainsi le régime à queue lourde). De plus, les méthodes existantes traitent souvent l'indice de sparsité comme un hyperparamètre gelé nécessitant une recherche par grille par tâche.

Méthodologie : LTGA

Les auteurs proposent le LTGA (Learnable Tsallis Graph Attention), une couche d'attention sur graphe qui remplace la normalisation softmax standard par une $q$-softmax basée sur les statistiques de Tsallis. L'indice entropique $q$ est appris de bout en bout, permettant au modèle d'interpoler continûment entre trois régimes :

1. Queue lourde ($q < 1$) : Support non borné, conservant du poids sur les voisins à faible score.
2. Shannon/Softmax ($q = 1$) : La ligne de base standard de GAT.
3. Support compact ($q > 1$) : Produit des zéros exacts pour les scores inférieurs à un seuil, élagant efficacement les voisins non informatifs.

Composants techniques clés :

• Reparamétrage : Pour assurer la stabilité numérique et empêcher l'indice de dériver vers des régimes dégénérés, $q$ est paramétré comme $q(\alpha) = 1 + \delta \tanh(\alpha)$, où $\alpha$ est un scalaire sans contrainte. Cela fixe l'initialisation à la ligne de base de Shannon ($q=1$) lorsque $\alpha=0$.
• Granularités : L'indice $q$ peut être lié à quatre niveaux de granularité, échangeant l'expressivité contre le nombre de paramètres :
  • Global-q : Un scalaire unique partagé sur toutes les couches et têtes.
  • Layer-q : Un scalaire par couche.
  • Head-q : Un scalaire par tête d'attention.
  • Edge-q (LTGA-Edge) : Un indice par arête généré par un petit MLP qui mappe les plongements des points de terminaison vers un scalaire de porte. Cela permet à différentes arêtes au sein d'un même voisinage d'adopter différents régimes d'attention.
• Stabilité numérique : Une branche de développement de Taylor est utilisée près de $q=1$ pour gérer la singularité rémanente dans la fonction $q$-exponentielle, assurant des valeurs et des gradients continus.
• Stabilisateurs d'entraînement :
  • Optimiseur découplé : Un optimiseur Adam séparé pour les paramètres $\alpha$ avec un calendrier de chauffe (gelant $\alpha=0$ pendant les $T_w$ premiers époques) permet aux poids des caractéristiques de converger avant que la géométrie de l'attention ne change.
  • Régularisateur de priorité de Shannon : Une pénalité quadratique sur $(q-1)^2$ agit comme le rasoir d'Occam, pénalisant les écarts par rapport à la ligne de base softmax, à moins qu'ils n'améliorent la perte de la tâche.

Contributions Clés

1. Indice entropique apprenable : LTGA introduit un $q$ apprenable à l'attention sur graphe, couvrant toute la famille de Tsallis bidirectionnelle ($q<1$ et $q>1$), contrairement aux travaux précédents restreints à $\alpha \ge 1$.
2. Formulation stable : Le papier fournit une formulation $q$-softmax numériquement stable avec une branche de Taylor autour de la limite de Shannon, ainsi que des stratégies de reparamétrage et de régularisation pour permettre un entraînement de bout en bout stable.
3. Évaluation exhaustive : La méthode est évaluée sur huit benchmarks couvrant un large spectre d'homophilie ($h \in [0.05, 0.81]$), comparant softmax, les grilles de $q$ gelés, l' $\alpha$-entmax ajusté, sparsemax et les architectures spécifiques à l'hétérophilie.
4. Analyse d'interprétabilité : Les auteurs analysent le comportement de l'indice appris, liant $q>1$ à l'élagage dépendant des données du voisinage et vérifiant que les arêtes élaguées sont effectivement du "bruit" (faible accord de labels et similitude de caractéristiques).

Résultats

• Performance : Sur 10 graines et 8 jeux de données, LTGA-Edge obtient le meilleur rang de Friedman moyen (2.75), surpassant GAT (3.19) et GATv2 (4.06). Cependant, le test omnibus ne rejette pas l'hypothèse nulle ($p=0.199$), indiquant que la différence de performance globale n'est pas statistiquement significative entre toutes les méthodes.
• Gains spécifiques : Les principaux gains sont observés sur les benchmarks hétérophiles :
  • Roman-Empire ($h=0.05$) : LTGA-Edge améliore la précision de +16,3 % par rapport à GAT et de +1,4 % par rapport à GATv2.
  • Amazon-Ratings ($h=0.38$) : LTGA-Edge améliore la précision de +0,8 % par rapport à GAT et de +1,1 % par rapport à GATv2.
  • Sur les graphes homophiles (Cora, CiteSeer, PubMed), $q$ converge vers 1, et LTGA est comparable à GATv2.
• Apprentissage vs Réglage : Apprendre $q$ ne bat pas strictement la recherche du $q$ gelé optimal. Une grille gelée ajustée par validation atteint 61,4 %, l' $\alpha$-entmax ajusté atteint 62,2 %, et un contrôle de capacité équivalente atteint 62,0 %, contre 61,7 % pour LTGA-Edge. Le papier conclut que la valeur de l'apprentissage de $q$ est la commodité (un seul passage au lieu d'une recherche par grille) et l'adaptabilité, plutôt qu'un plafond de précision brute.
• Validation du mécanisme :
  • Sur Roman-Empire, l'indice appris élague environ 42 % des coefficients d'attention à zéro exact.
  • Sélectivité : Les arêtes élaguées ont un accord de labels significativement plus bas (9,3 % contre 43,5 % pour les arêtes conservées) et une similitude de caractéristiques moindre.
  • Contrefactuels : Restaurer les arêtes élaguées lors de l'inférence fait chuter la précision de 7,1 points. L'élagage aléatoire du même nombre d'arêtes fait chuter la précision de 13,0 points de plus que l'élagage appris, confirmant que la sparsité est sélective et bénéfique.
• Granularité : Bien que LTGA-Edge obtienne le meilleur rang moyen, les granularités scalaires (Global, Layer, Head) se comportent de manière similaire sur les jeux de données où $q$ varie, suggérant que la capacité par arête est le principal moteur de performance sur les graphes hétérophiles.

Signification et Revendications

Le papier affirme modestement que LTGA fournit un cadre unifié et apprenable pour la normalisation de l'attention sur graphe qui s'adapte aux besoins statistiques spécifiques d'un graphe sans réglage manuel d'hyperparamètres.

• Interprétabilité : Là où $q$ s'écarte de la ligne de base de Shannon, il le fait de manière interprétable : $q>1$ correspond à l'élagage sélectif des voisins non informatifs (support compact), tandis que $q<1$ correspond à une diffusion à queue lourde.
• Limitations : Les auteurs déclarent explicitement que le régime à queue lourde ($q<1$) n'a pas montré de bénéfices empiriques sur les benchmarks testés. Ils notent également que sur les petits jeux de données à haute variance (WebKB), la méthode n'offre aucun avantage par rapport à GATv2.
• Positionnement : LTGA ne prétend pas être complémentaire aux architectures spécifiques à l'hétérophilie (comme H2GCN ou GPR-GNN) car ces modèles ne normalisent pas l'attention de la même manière. Au lieu de cela, LTGA concurrence directement les modèles basés sur l'attention et offre un mécanisme pour remplacer la normalisation softmax fixe par une alternative adaptative pilotée par les données.

En résumé, LTGA démontre que l'apprentissage de l'indice entropique permet à un réseau d'attention sur graphe de découvrir automatiquement s'il doit être dense, épars ou à queue lourde en fonction de l'homophilie du graphe, offrant ainsi une alternative robuste et en un seul passage aux mécanismes d'attention sparse ajustés par grille.