Résumé technique : Estimation de l'incertitude pour les graphes hétérophiles à travers le prisme de la théorie de l'information

Énoncé du problème

L'estimation de l'incertitude pour les réseaux de neurones à graphes (GNN) a suscité une attention considérable, pourtant la plupart des méthodes existantes reposent fortement sur l'hypothèse d'homophilie — la tendance des nœuds à se connecter à d'autres de la même classe. Ces méthodes utilisent souvent la diffusion sur le graphe ou des noyaux de lissage pour propager l'incertitude, ce qui est efficace lorsque des nœuds sémantiquement similaires sont connectés. Cependant, dans des contextes hétérophiles, où les nœuds se connectent principalement à des voisins de classes différentes, ces approches se dégradent. La dépendance au lissage pour propager l'(in)certitude est moins justifiée dans les graphes hétérophiles, entraînant de faibles performances dans la détection hors distribution (O.O.D.) et la quantification de l'incertitude. De plus, les travaux antérieurs n'ont pas systématiquement étudié le comportement des estimateurs d'incertitude lorsque les hypothèses d'homophilie sont violées, ni proposé d'approche dédiée aux graphes hétérophiles évitant d'exploiter explicitement l'homophilie.

Méthodologie

Les auteurs abordent le problème d'un point de vue théorique de l'information, en analysant les réseaux de neurones à passage de messages (MPNN) pour comprendre comment les représentations latentes des nœuds évoluent à travers les couches.

1. Analyse théorique de l'information des MPNN

S'inspirant du principe du goulot d'étranglement de l'information (Information Bottleneck) (Tishby & Zaslavsky, 2015), les auteurs modélisent le flux d'information dans les MPNN. Contrairement aux réseaux de neurones standards pour des données indépendantes et identiquement distribuées (i.i.d.), où l'inégalité de traitement de l'information (Data Processing Inequality - DPI) dicte que l'information concernant une variable cible ne peut qu'augmenter ou rester constante à travers les couches, les auteurs dérivent une égalité de traitement de l'information (Data Processing Equality - DPE) pour les MPNN.

Les insights théoriques clés incluent :

• Récupération et gain d'information : Dans les MPNN, l'information concernant l'étiquette $Y$ d'un nœud n'est pas contenue uniquement dans les propres caractéristiques du nœud, mais est distribuée à travers l'ego-graphe. Les auteurs définissent un ego-graphe $G_v$ décomposé en ensembles disjoints $G_v^{(i)}$ basés sur la distance en sauts.
• L'égalité : L'information mutuelle $I(Y; Z^{(i+1)})$ détenue par une représentation à la couche $i+1$ se décompose de manière additive :
  $$I(Y; Z^{(i+1)}) = I(Y; Z^{(i)}) - \Delta_{(-)}^{(0:i)} + \Delta_{(+)}^{(i+1)}$$
  Ici, $\Delta_{(-)}^{(0:i)}$ représente la perte (ou la récupération) d'information concernant l'ego-graphe existant, et $\Delta_{(+)}^{(i+1)}$ représente le gain d'information provenant des nouveaux voisins à $i+1$ sauts.
• Hétérophilie vs Homophilie :
  • Dans les graphes homophiles, les nœuds adjacents partagent des sémantiques similaires. Par conséquent, le gain d'information $\Delta_{(+)}^{(i+1)}$ diminue à mesure que la profondeur augmente, car les couches plus profondes ne fournissent pas de nouvelles informations sémantiques sur la cible.
  • Dans les graphes hétérophiles, les nœuds adjacents présentent des sémantiques différentes. Le gain d'information $\Delta_{(+)}^{(i+1)}$ peut être grand et positif, ce qui signifie que les plongements latents plus profonds contiennent des informations uniques et distinctes sur la distribution des données que les plongements plus superficiels manquent.

2. Estimation de densité latente conjointe (JLDE)

Sur la base du constat que les graphes hétérophiles nécessitent la considération conjointe de toutes les représentations de nœuds pour capturer la pleine distribution des données, les auteurs proposent l'Estimation de densité latente conjointe (Joint Latent Density Estimation - JLDE).

• Mécanisme : Au lieu d'estimer la densité à partir d'une seule couche finale (comme c'est courant dans les contextes i.i.d.) ou d'utiliser la diffusion sur le graphe, la JLDE concatène les plongements latents de toutes les couches du MPNN ($Z^{(0)}, Z^{(1)}, \dots, Z^{(L)}$).
• Implémentation : Un estimateur de densité K-plus proches voisins (KNN) post-hoc simple est appliqué à cet espace de plongement conjoint concaténé. L'incertitude épistémique $u_{epi}(v)$ est calculée comme le logarithme négatif de la vraisemblance de la représentation conjointe du nœud au sein de la distribution d'entraînement.
• Principe de conception : Cette approche n'exploite pas explicitement l'homophilie via un post-traitement (par exemple, le lissage) et est applicable à n'importe quel squelette MPNN.

Contributions clés

1. Cadre théorique : L'article dérive une analogie novatrice de l'inégalité de traitement de l'information pour les MPNN, prouvant que l'information peut augmenter avec la profondeur du modèle dans des contextes hétérophiles en raison de l'information sémantique unique fournie par les voisins à différentes distances.
2. Définition de l'homophilie basée sur l'information : Les auteurs introduisent une définition de l'homophilie fondée sur l'information mutuelle, distinguant l'information partagée pertinente pour l'étiquette cible du bruit irrelevant.
3. Méthode JLDE : Ils proposent l'Estimation de densité latente conjointe, un principe de conception post-hoc simple qui modélise conjointement toutes les représentations latentes. Cette méthode est la première à cibler explicitement la quantification de l'incertitude dans les graphes hétérophiles sans s'appuyer sur des hypothèses d'homophilie.
4. Validation empirique : La méthode est évaluée sur plusieurs jeux de données, décalages de distribution et architectures de base, démontrant des performances de pointe.

Résultats expérimentaux

Les auteurs évaluent la JLDE sur six jeux de données (quatre hétérophiles : Amazon Ratings, Roman Empire, Chameleon, Squirrel ; deux homophiles : CoraML, PubMed) dans le cadre de trois types de décalages de distribution : Leave-Out-Class (LoC), perturbations de caractéristiques proches et perturbations de caractéristiques lointaines.

• Performance hétérophile : Sur les jeux de données hétérophiles, la JLDE atteint systématiquement des performances de pointe en incertitude épistémique (mesurée par l'AUC-ROC et l'AUC-PR de détection O.O.D.). Elle surpasse nettement les méthodes reposant sur la diffusion sur le graphe (par exemple, GPN, GEBM) ou les méthodes d'ensemble standard, en particulier dans les scénarios où l'information des couches plus profondes est critique.
• Performance homophile : Sur les jeux de données homophiles, la JLDE est compétitive par rapport à d'autres estimateurs agnostiques au modèle et égale les performances des méthodes explicitement conçues pour l'homophilie, malgré le fait qu'elle n'utilise pas de post-traitement exploitant l'homophilie.
• Études d'ablation : Les expériences confirment que pour les graphes hétérophiles, l'utilisation de la seule couche finale ou la moyenne des densités par couche donne des résultats inférieurs à la concaténation conjointe de toutes les couches. Inversement, sur les graphes homophiles, l'approche conjointe performe aussi bien que l'utilisation de la seule couche finale, validant la théorie selon laquelle les couches plus profondes n'ajoutent aucune nouvelle information dans ces contextes.
• Agnosticisme vis-à-vis du squelette : La méthode est appliquée post-hoc à divers squelettes (Res-GCN, Res-GAT-Sep, Res-GATE, GPRGNN), se classant systématiquement comme le meilleur estimateur ou le deuxième meilleur à travers différentes architectures.

Importance et affirmations

L'article revendique fournir les fondements théoriques pour faire progresser l'estimation de l'incertitude sur les graphes au-delà de l'hypothèse d'homophilie. En révélant que dans les graphes hétérophiles, chaque couche de plongement fournit une information unique sur la distribution des données, les auteurs établissent un principe de conception clé : l'estimation de l'incertitude doit considérer conjointement toutes les représentations de nœuds.

Les auteurs soulignent que leur travail :

• Comble une lacune dans la littérature où aucun travail antérieur ne cible explicitement les graphes hétérophiles pour la quantification de l'incertitude.
• Démontre que les estimateurs existants échouent souvent lorsque les hypothèses d'homophilie sont violées.
• Offre une solution simple, efficace et agnostique au modèle (JLDE) qui atteint des résultats de pointe sans nécessiter de changements architecturaux complexes ni d'exploitation explicite de l'homophilie.
• Contribue au développement d'une IA fiable et digne de confiance, en particulier dans des domaines à haut risque où la compréhension de l'incertitude du modèle dans des données non homophiles est critique.

Les auteurs restent modestes quant à la portée, notant que si la JLDE améliore l'incertitude épistémique, elle n'améliore pas intrinsèquement l'incertitude aléatoire ou l'étalonnage du modèle, qui restent des voies orthogonales pour les travaux futurs. Ils conjecturent également que des modèles de densité plus sophistiqués pourraient encore améliorer leur réalisation simple basée sur KNN.