Résumé technique : Une couche Tikhonov généralisée pour des réseaux de neurones sur graphes interprétables par conception

Énoncé du problème

Les réseaux de neurones sur graphes (GNN) ont atteint un succès significatif dans les tâches de classification de graphes et de nœuds en apprenant à agréger des caractéristiques sur la topologie du graphe. Cependant, leur interprétabilité reste un défi critique. Contrairement aux réseaux de neurones classiques, les GNN doivent expliquer non seulement comment les caractéristiques d'entrée sont transformées, mais aussi comment la topologie du graphe elle-même est exploitée. Les méthodes d'interprétabilité existantes reposent souvent sur des approximations a posteriori (par exemple, GNNExplainer, la saillance par gradient) qui manquent de garanties de fidélité, ou sur des architectures à deux modules où un extracteur d'explication est détaché du classifieur, permettant à ce dernier d'ignorer l'explication tout en minimisant la perte. De plus, les GNN profonds souffrent de pathologies telles que le lissage excessif (effondrement des représentations de nœuds) et le compression excessif (décroissance exponentielle de la sensibilité à longue distance).

Méthodologie

Les auteurs proposent la couche Tikhonov, une couche de réseau de neurones sur graphes conçue pour être interprétable par construction. L'innovation centrale réside dans la contrainte de la matrice de propagation de graphe $R$ à une solution en forme fermée spécifique, dérivée d'un problème de régularisation de Tikhonov généralisé sur graphe.

L'opérateur de propagation

Pour un graphe avec un Laplacien normalisé $L$, la sortie de la couche pour des caractéristiques d'entrée $X$ est donnée par :
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
où la matrice de propagation $R$ est définie par :
$$R = (p(L) + Q)^{-1} Q$$
Ici :

• $L$ est le Laplacien normalisé du graphe.
• $Q = \text{diag}(q_1, \dots, q_n)$ est une matrice diagonale apprenable de scores d'importance de nœuds strictement positifs.
• $p(\cdot)$ est un polynôme apprenable satisfaisant $0 < p(\lambda) < 1$ pour $\lambda \in [0, 2]$.
• $\sigma$ est une non-linéarité ponctuelle et $W$ est une matrice de poids.

Interprétation variationnelle

L'opérateur $R$ est le minimiseur unique en forme fermée du problème de Tikhonov généralisé :
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
Cette formulation échange explicitement la fidélité aux données au niveau des nœuds (pondérée par $q_i$) contre la régularisation pilotée par la topologie (gouvernée par $p(L)$).

• $q_i$ élevé : Le nœud $i$ repose fortement sur ses propres caractéristiques ; la sortie $z_i$ reste proche de $x_i$.
• $q_i$ faible : Le nœud $i$ rejette ses propres caractéristiques au profit d'une solution pilotée par la topologie du graphe (lissage ou propriétés spectrales spécifiques définies par $p$).
• Forme de $p(\lambda)$ : Détermine la nature de l'influence topologique. Un $p$ croissant pénalise les hautes fréquences (favorisant l'homophilie/lissage), tandis qu'un $p$ décroissant pénalise les basses fréquences (favorisant l'hétérophilie).

Architecture et expressivité

Pour maintenir une haute expressivité sans sacrifier l'interprétabilité, l'architecture emploie une séparation des préoccupations :

1. Le réseau Q : Un GNN dédié, potentiellement profond (par exemple, ChebNet ou ARMA), qui prend le graphe $(G, X)$ en entrée et produit les scores d'importance des nœuds $Q$. Ce composant gère l'apprentissage représentationnel complexe et adapte $q_i$ aux structures et caractéristiques locales du graphe.
2. La couche Tikhonov : Une couche unique et transparente qui applique la propagation $R$. Elle ne contient aucune non-linéarité cachée ni étapes complexes de passage de messages ; ses paramètres sont les coefficients polynomiaux de $p$ et les sorties du réseau Q.
3. Tête : Une opération de regroupement global suivie d'un MLP pour la prédiction finale.

Le modèle prend en charge des extensions multi-canaux où plusieurs réseaux Q et polynômes indépendants sont utilisés, bien que les expériences se concentrent sur le cas monocanal ($J=1$).

Détails de mise en œuvre

• Calcul : Le calcul de $(p(L) + Q)^{-1}QX$ implique la résolution de systèmes linéaires. Les auteurs utilisent le gradient conjugué préconditionné (PCG) avec un préconditionneur diagonal (Jacobi) pour éviter le coût $O(n^3)$ de l'inversion dense, atteignant une évolutivité $O(dTKm)$où$T$ est le nombre d'itérations.
• Différentiation : Pour éviter de stocker le graphe de calcul du solveur, les auteurs utilisent la différentiation implicite, ne nécessitant qu'une résolution PCG supplémentaire dans le passage arrière pour calculer les gradients par rapport à $Q$ et $p$.
• Contraintes : Le polynôme $p(\lambda)$ est paramétré à l'aide de polynômes de Bernstein avec des activations sigmoïdes pour imposer strictement $0 < p(\lambda) < 1$. Les scores $q_i$ sont mappés vers des valeurs strictement positives via une fonction de saturation dans l'espace logarithmique.

Contributions clés et propriétés théoriques

1. Interprétabilité intégrée : Le couple $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ constitue une explication directe et fidèle. Un $q_i$ élevé indique une dépendance aux caractéristiques ; un $q_i$ faible indique une dépendance à la topologie. La forme de $p$ révèle le biais spectral (homophilie, hétérophilie, passe-bande).
2. Couplage structurel : Les auteurs prouvent (Proposition 3.6) que l'application $Q \mapsto R$ est injective. Contrairement aux méthodes a posteriori, modifier l'explication ($Q$) modifie nécessairement l'opérateur de propagation ($R$), garantissant que l'explication est fidèle au calcul.
3. Expressivité : Il est démontré que la couche est dense dans l'espace des filtres spectraux continus dans le cas homogène. Avec un $Q$ hétérogène, elle étend strictement l'expressivité au-delà des filtres spectraux traditionnels en brisant la stationnarité (Proposition 3.3).
4. Atténuation des pathologies des GNN :
   • Lissage excessif : Évité par l'utilisation d'une seule couche et l'inversibilité de $p(L) + Q$. L'effondrement des nœuds ne se produit que si le modèle conduit délibérément tous les $q_i \to 0$.
   • Compression excessive : Le taux de décroissance de la sensibilité à longue distance $|R_{ij}|$ est gouverné par le nombre de conditionnement $\kappa$ du système, qui dépend du $Q appris. Le modèle peut apprendre à réduire $\kappa$ (en abaissant des $q_i$ spécifiques) pour augmenter la sensibilité à longue distance là où cela est nécessaire, échangeant efficacement la précision locale contre la portée globale.

Résultats expérimentaux

Le modèle a été évalué sur des tâches synthétiques contrôlées et des benchmarks standards, démontrant à la fois des performances et une interprétabilité :

• Tâches synthétiques contrôlées :
  • Colors-3 : La tâche repose uniquement sur les caractéristiques des nœuds. Le modèle a appris des $q_i$ élevés partout, ignorant efficacement la topologie et se comportant comme un MLP, identifiant correctement que les caractéristiques pilotent la prédiction.
  • Distance de clique : Une tâche purement structurelle. Le modèle a appris des $q_i$ faibles pour les nœuds de chemin (s'appuyant sur la topologie pour détecter la distance) et des $q_i$ élevés pour les nœuds de clique (ancres), atteignant une précision de 100 %.
  • Triangles : Une tâche structurelle détectant les triangles. Le modèle a attribué des $q_i$ faibles en général, mais des $q_i$ plus élevés aux sommets des triangles, localisant le motif sans supervision.
• CSBM (Modèle de bloc stochastique contextuel) : Le modèle a suivi avec succès le seuil de transition de phase théorique pour la récupération. Les valeurs apprises de $q_i$ ont transité de manière fluide des régimes dominés par les caractéristiques ($q_i$ élevé) vers les régimes dominés par la topologie ($q_i$ faible), identifiant correctement la source du signal dans les régimes mixtes.
• ECHO-diam (Propagation à longue distance) : Sur une tâche de régression du diamètre de graphe, le modèle a atteint une erreur absolue moyenne (MAE) de 1,17, surpassant les bases de référence GNN profondes (~1,6) et s'approchant des performances des Transformers (1,05). L'explication a révélé que le modèle attribuait des $q_i$ élevés aux nœuds périphériques (extrémités) et des $q_i$ faibles aux nœuds intérieurs, utilisant le contraste entre les extrémités ancrées et l'intérieur lissé pour estimer le diamètre.

Signification et affirmations

L'article affirme que la couche Tikhonov offre une approche novatrice de l'interprétabilité des GNN en concevant la couche pour qu'elle soit auto-explicative plutôt qu'en récupérant des explications a posteriori.

• Fidélité : L'explication est le modèle lui-même ; il n'y a ni sous-graphe détaché ni approximation.
• Granularité : Elle fournit une réponse continue et spatialement résolue (valeurs de $q_i$ graduées) plutôt qu'une sélection binaire de sous-graphe.
• Performance : Le modèle égale ou dépasse les bases de référence opaques (comme GIN, GAT et Transformers) sur diverses tâches tout en fournissant des insights sur comment la tâche est résolue (par exemple, en distinguant le raisonnement basé sur les caractéristiques du raisonnement basé sur la topologie).
• Limitations : Les auteurs reconnaissent que certaines explications peuvent être complexes à interpréter pour les humains et que le coût computationnel du PCG peut être élevé pour les tâches nécessitant des interactions à longue distance (bien qu'ils suggèrent l'algèbre linéaire numérique aléatoire comme direction future pour l'approximation).

Ce travail établit qu'il est possible de contraindre les couches de GNN à des formes variationnelles spécifiques pour gagner en interprétabilité sans sacrifier la capacité d'apprendre des filtres de graphes complexes et non stationnaires.