Résumé Technique : GRAPHLCP

Énoncé du Problème

Les réseaux de neurones à graphes (GNN) sont de plus en plus déployés dans des domaines à haut risque tels que la découverte de médicaments, la prévision météorologique et la détection de fraude, ce qui nécessite une quantification fiable de l'incertitude (UQ). La prédiction conforme (CP) offre un cadre sans distribution pour construire des prédictions sous forme d'ensembles avec des garanties en échantillon fini. Cependant, l'application de la CP aux GNN présente des défis uniques :

1. Dépendances Structurelles : Les nœuds dans les graphes sont naturellement dépendants, ce qui viole les hypothèses standards d'indépendance et d'identité de distribution (i.i.d.) requises pour la CP classique.
2. Limitations des Représentations : Les méthodes de CP localisée existantes pour les graphes reposent souvent sur la proximité dans l'espace des représentations (par exemple, l'estimation de densité par noyau sur les représentations des GNN) pour définir des voisinages locaux. Cette approche est fréquemment peu fiable en raison de :
   • Sur-lissage : La propagation de messages profonde réduit la variance des mesures de similarité, rendant les représentations indifférenciées.
   • Sur-écrasement : Les goulots d'étranglement topologiques restreignent le flux d'informations global, en particulier sous l'hétérophilie.
   • Sous-confiance : Les GNN présentent souvent une séparabilité insuffisante dans les représentations apprises.
3. Inefficacité des Solutions Existantes : Les méthodes de CP spécifiques aux graphes actuelles dépendent soit de l'entraînement de modèles auxiliaires (augmentant la surcharge computationnelle), soit de partitions structurelles rigides (par exemple, le clustering dur) qui échouent à capturer l'hétérophilie locale fine. Par conséquent, les méthodes existantes produisent souvent des ensembles de prédiction excessivement conservateurs ou mal localisés dans des topologies complexes.

Méthodologie : GRAPHLCP

Les auteurs proposent GRAPHLCP, un cadre de prédiction conforme localisée basé sur la proximité, conçu pour intégrer explicitement la topologie du graphe et les dépendances inter-nœuds dans les étapes de localisation et de pondération. La méthode opère dans un cadre transductif où le GNN est pré-entraîné et figé. Le cadre se compose de quatre étapes clés :

1. Densification Sensible aux Caractéristiques

Pour atténuer le biais de localité dans les graphes clairsemés et capturer les dépendances sémantiques à longue portée, les auteurs introduisent une étape de densification avant le calcul du noyau.

• Projection PCA : Les représentations des nœuds sont d'abord projetées via l'Analyse en Composantes Principales (PCA) pour découpler les dimensions de caractéristiques corrélées et condenser l'espace, traitant ainsi le bruit et la redondance causés par le sur-lissage.
• Noyau Anisotrope Adaptatif : Un noyau gaussien anisotrope est construit en utilisant les représentations transformées par PCA. La bande passante est adaptée en fonction des valeurs propres de la matrice de covariance pour tenir compte des échelles variables à travers les dimensions.
• Augmentation des Arêtes : De nouvelles arêtes sont ajoutées à la matrice d'adjacence du graphe si la similarité entre des nœuds non connectés (calculée via le noyau gaussien) dépasse un seuil dynamique $\tau_d$. Ce seuil est automatiquement ajusté en fonction du taux d'homophilie du graphe pour équilibrer l'ajout d'arêtes informatives contre l'introduction de bruit.

2. Noyau PageRank Personnalisé (PPR)

Au lieu de se fier uniquement aux distances dans les représentations, GRAPHLCP utilise le PPR pour modéliser la proximité structurelle.

• Localisation : Le PPR capture l'influence multi-sauts tout en maintenant la localité via une probabilité de redémarrage ($\beta$). Il fournit une notion souple et probabiliste de proximité qui s'aligne naturellement avec la CP pondérée.
• Échantillonnage : Pour un nœud de test, un nœud ancre est échantillonné à partir de la distribution induite par le PPR centrée sur le nœud de test. Cela garantit que les nœuds proches exercent une plus grande influence sur l'estimation du quantile.
• Pondération : Les nœuds de calibration et de test sont pondérés selon leur proximité structurelle par rapport à l'ancre échantillonnée. Les auteurs exploitent la symétrie normalisée par le degré du PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) pour calculer les poids efficacement, même lorsque le nombre d'échantillons de calibration dépasse le nombre d'échantillons de test.

3. Intégration de la Prédiction Conforme Localisée Randomisée (RLCP)

GRAPHLCP adapte le cadre RLCP. En échantillonnant un nœud ancre $\tilde{u}_{n+1}$ à partir de la distribution PPR du nœud de test $u_{n+1}$, la méthode construit un ensemble de prédiction basé sur un quantile pondéré des scores de non-conformité. Les poids sont dérivés des scores PPR par rapport à l'ancre échantillonnée, permettant à la méthode de s'adapter au contexte local du graphe.

4. Construction de la Prédiction

L'ensemble de prédiction final $\hat{C}_n(u_{n+1})$ est construit comme l'ensemble des étiquettes $y$ telles que le score de non-conformité $s(u_{n+1}, y)$ est inférieur ou égal à un quantile pondéré $\hat{q}_{1-\alpha}$. Ce quantile est calculé en utilisant les poids dérivés du noyau PPR et les scores de non-conformité de l'ensemble de calibration.

Contributions Clés

1. Localisation Sensible à la Structure : L'article comble le fossé entre la localisation structurelle et celle basée sur les caractéristiques en remplaçant la proximité basée uniquement sur les représentations par un noyau basé sur le PPR. Cela intègre explicitement la topologie du graphe dans le processus de pondération conforme.
2. Densification Sensible aux Caractéristiques : Une étape de prétraitement novatrice qui enrichit la topologie du graphe en utilisant la similarité des représentations (via PCA et des noyaux anisotropes adaptatifs) pour atténuer la sparsité et capturer les dépendances à longue portée sans dépendre du pondération continue potentiellement bruyante des représentations.
3. Schéma de Pondération Efficace : La méthode fournit un moyen efficace de calculer des poids basés sur le PPR pour les graphes non orientés en exploitant la symétrie normalisée par le degré, évitant ainsi l'inefficacité computationnelle du calcul de vecteurs PPR complets pour de grands ensembles de calibration.
4. Validité Théorique : L'approche maintient les garanties d'échangeabilité requises pour la couverture marginale dans les cadres transductifs tout en visant à améliorer la couverture conditionnelle au test assouplie.

Résultats Expérimentaux

Les auteurs ont évalué GRAPHLCP sur sept ensembles de données de régression de nœuds et huit ensembles de données de classification de nœuds (incluant des réseaux de citations, des achats conjoints Amazon et des ensembles de données géographiques).

• Couverture Marginale : Toutes les méthodes, y compris GRAPHLCP, ont satisfait le taux de non-couverture cible ($\alpha = 0.1$), confirmant la validité de l'approche.
• Couverture Conditionnelle (WSC) : Dans les diagnostics de Dalle de Pire Cas (WSC), qui recherchent de manière adversariale la couverture minimale à travers les directions de projection, GRAPHLCP a obtenu les meilleurs ou deuxième meilleurs résultats sur la plupart des ensembles de données, surpassant des bases de comparaison comme CalLCP, RLCP et SCP.
• Couverture Basée sur les Groupes : GRAPHLCP a démontré une couverture supérieure à travers des partitions basées sur l'homophilie, le clustering de caractéristiques, le coefficient de clustering et le degré des nœuds. La méthode s'est révélée particulièrement efficace dans les régions hétérophiles où les méthodes standard peinaient.
• Efficacité de la Prédiction : Alors que CalLCP produisait souvent des ensembles de prédiction excessivement grands (sur-couverture), GRAPHLCP a atteint des longueurs de prédiction normalisées favorables, offrant un meilleur compromis entre couverture et taille de l'ensemble.
• Études d'Ablation :
  • Le remplacement du noyau PPR par un noyau gaussien (GSS) a entraîné une couverture plus faible et des ensembles de prédiction plus grands, confirmant l'importance de la localisation sensible à la structure.
  • L'étape de densification a été identifiée comme le composant le plus significatif, en particulier pour les tâches de régression.
  • La projection PCA s'est révélée cruciale pour atténuer les effets négatifs des caractéristiques de représentations corrélées.

Importance et Revendications

L'article revendique que GRAPHLCP répond avec succès aux limitations des méthodes de CP sur graphes existantes en modélisant explicitement les dépendances structurelles. En découplant les poids des encodeurs GNN potentiellement destructeurs et en utilisant un noyau basé sur le PPR, la méthode crée une « voie résiduelle à faible bruit » pour la quantification de l'incertitude.

Les auteurs affirment que GRAPHLCP garantit la couverture marginale avec des échantillons finis tout en atteignant efficacement une couverture conditionnelle au test favorable dans divers scénarios de conditionnement. Ils soulignent que la méthode est particulièrement robuste dans des topologies complexes où les similarités basées sur les représentations échouent en raison du sur-lissage ou du sur-écrasement. Le travail souligne la nécessité d'une localisation sensible à la structure pour une UQ efficace sur les graphes, allant au-delà de la simple dépendance à la proximité dans l'espace des caractéristiques. Les auteurs notent modestement que les orientations futures incluent l'extension de ce cadre aux graphes dynamiques avec des topologies évolutives.