Résumé Technique : Quantification de l'incertitude sans quantiles dans les réseaux de neurones à graphes

1. Énoncé du problème

La quantification de l'incertitude (UQ) dans les réseaux de neurones à graphes (GNN) est cruciale pour des applications à haut risque telles que la santé et la justice pénale, mais elle reste un défi majeur. Les GNN existants produisent généralement des estimations ponctuelles déterministes, échouant à capturer la fiabilité des prédictions. De plus, les mécanismes standards de passage de messages peuvent propager et amplifier les biais des données, augmentant ainsi les risques de prise de décision.

Les approches actuelles d'UQ pour les GNN font face à trois limitations principales :

1. Méthodes bayésiennes : Bien que fondées sur des principes solides, elles souffrent souvent de problèmes d'évolutivité et de sensibilité aux spécifications des a priori.
2. Rééchantillonnage et calibration a posteriori : Les approches fréquentistes comme la prédiction conforme (CP) ou les méthodes d'ensemble reposent sur des inférences répétées ou des ensembles de calibration séparés. Elles sont coûteuses en calcul et dépendent souvent d'hypothèses fortes, telles que l'échangeabilité (souvent simplifiée en i.i.d.), qui sont fréquemment violées dans les données de graphes en raison des dépendances structurelles (par exemple, les hubs, l'hétérophilie).
3. Limites de la régression quantile (QR) : La QR standard nécessite des entrées explicites au niveau des quantiles (par exemple, $\tau = 0,05$) ou des modèles séparés pour chaque quantile. Lorsqu'elle est appliquée aux GNN, cette conception entremêle les représentations des nœuds, conduisant à des problèmes tels que le croisement de quantiles, le sur-étouffement (oversmoothing) et des intervalles mal calibrés.

L'article soutient qu'il existe un besoin d'un cadre fréquentiste qui évite les hypothèses fortes, élimine le besoin d'entrées de quantiles ou de post-traitement, et reste pratiquement calculable pour les données structurées en graphes.

2. Méthodologie : QpiGNN

Les auteurs proposent QpiGNN (Quantile-free Prediction Interval GNN), un cadre conçu pour générer des intervalles de prédiction calibrés et compacts pour la régression au niveau des nœuds, sans nécessiter d'entrées de quantiles, de rééchantillonnage ou de calibration a posteriori.

2.1. Architecture à double tête

QpiGNN utilise une architecture à double tête pour découpler la prédiction de la valeur cible de l'estimation de l'incertitude.

• Encodeur : Un GNN standard (par exemple, GraphSAGE) agrège les informations du voisinage pour produire des embeddings de nœuds $H$.
• Tête de prédiction : Une couche linéaire prédit la moyenne cible $\hat{y} = W_{pred}H + b_{pred}$.
• Tête d'incertitude : Une couche linéaire séparée prédit la demi-largeur de l'intervalle $\hat{d} = \text{Softplus}(W_{diff}H + b_{diff})$. L'activation Softplus garantit que $\hat{d} > 0$.
• Sortie : L'intervalle de prédiction pour le nœud $v$ est défini comme $[\hat{y}_v - \hat{d}_v, \hat{y}_v + \hat{d}_v]$.

Cette séparation prévient les conflits de représentation et les interférences de gradient entre la précision et l'estimation de l'incertitude, atténuant les problèmes de sur-étouffement courants dans les GNN à tête unique.

2.2. Perte conjointe sans quantiles

Au lieu d'optimiser pour des quantiles spécifiques, QpiGNN est entraîné de bout en bout en utilisant une fonction de perte conjointe $\mathcal{L}_{total}$ qui optimise directement la couverture et la largeur de l'intervalle :

$$\mathcal{L}_{total} = \mathcal{L}_{coverage} + \lambda_{width} \cdot \mathcal{L}_{width}$$

• Terme de couverture ($\mathcal{L}_{coverage}$) : Ce terme pénalise les écarts par rapport au taux de couverture cible $(1-\alpha)$. Il inclut un terme d'erreur quadratique $(\hat{c} - (1-\alpha))^2$ et une perte de violation $\hat{\ell}_{viol}$ qui fournit un retour d'information fin lorsque les cibles réelles tombent en dehors des bornes prédites.
  • $\hat{c}$ est la proportion de couverture empirique.
  • $\hat{\ell}_{viol}$ pénalise l'ampleur de la violation lorsque $y_v < \hat{y}^{low}_v$ ou $y_v > \hat{y}^{up}_v$.
• Terme de largeur ($\mathcal{L}_{width}$) : Ce terme minimise la largeur moyenne de l'intervalle $\mathbb{E}[\hat{y}^{up}_v - \hat{y}^{low}_v]$ en utilisant une pénalité $L_1$ pour assurer la stabilité face aux valeurs aberrantes.
• Arbitrage : L'hyperparamètre $\lambda_{width}$ équilibre le compromis entre le maintien de la couverture cible et la minimisation de la largeur de l'intervalle (compacité).

Cette conception permet au modèle d'apprendre des intervalles adaptatifs et spécifiques aux nœuds directement à partir de la supervision par étiquettes, évitant ainsi le besoin d'entrées explicites de quantiles ou d'ensembles de calibration.

3. Garanties théoriques

L'article fournit des justifications théoriques pour QpiGNN sous des hypothèses légères (bruit borné, faible dépendance entre les nœuds, et convergence des moyennes/largeurs prédites) :

• Couverture asymptotique : Selon la loi faible des grands nombres (WLLN), la couverture empirique $\hat{c}$ converge en probabilité vers le niveau cible $1-\alpha$ lorsque le nombre de nœuds $N \to \infty$.
• Bornes à échantillon fini : En utilisant des inégalités de concentration (McDiarmid et Hoeffding), l'article démontre que pour un $N$ modéré, l'écart de la couverture empirique par rapport à la cible est borné par $O(1/\sqrt{N})$, même en présence de dépendances liées au graphe.
• Largeur optimale : La perte conjointe est interprétée comme une relaxation lagrangienne d'un problème d'optimisation sous contraintes. Lorsque la couverture est satisfaite, le modèle privilégie la réduction de la largeur, produisant des largeurs d'intervalle quasi optimales.
• Convergence : La perte conjointe non convexe est montrée comme convergeant vers un point stationnaire sous des conditions d'optimisation stochastique standard.

4. Résultats expérimentaux

Les auteurs ont évalué QpiGNN sur 19 ensembles de données, comprenant 9 graphes synthétiques (par exemple, BA, ER, Grid, Tree) et 10 benchmarks réels (par exemple, données de comtés américains, Twitch, graphes Wikipedia).

4.1. Métriques de performance

Les métriques principales étaient la probabilité de couverture de l'intervalle de prédiction (PICP) et la largeur moyenne de l'intervalle de prédiction (MPIW).

• Couverture : QpiGNN a atteint une couverture moyenne 22 % supérieure à celle des bases de comparaison compétitives (SQR-GNN, RQRadj.-GNN, CF-GNN, BayesianNN, MC Dropout).
• Compacité : QpiGNN a produit des intervalles 50 % plus étroits en moyenne tout en maintenant une couverture valide.
• Comparaison :
  • BayesianNN assurait la couverture mais produisait des intervalles excessivement larges.
  • MC Dropout produisait des intervalles étroits mais souffrait d'une sous-couverture sévère.
  • SQR-GNN et RQRadj.-GNN présentaient souvent une instabilité, un croisement de quantiles ou un mauvais calibrage sur les graphes hétérophiles.
  • CF-GNN (Conformalisé) nécessitait des ensembles de calibration et produisait des intervalles plus larges que QpiGNN.

4.2. Robustesse et généralisation

• Perturbations : QpiGNN est resté robuste face au bruit des caractéristiques, au bruit des cibles et à la suppression d'arêtes, maintenant une couverture valide là où les bases de comparaison échouaient ou nécessitaient des intervalles significativement plus larges.
• Décalages structurels : Dans les tests hors distribution (OOD) où des modèles entraînés sur un type de graphe étaient testés sur d'autres, QpiGNN entraîné sur des graphes expressifs (BA, ER) s'est bien généralisé, tandis que les modèles entraînés sur des structures simples (Tree, Basic) échouaient à couvrir les cibles sur des graphes complexes.
• Échangeabilité : QpiGNN a maintenu ses performances sous des splits non échangeables (par exemple, en divisant par degré de nœud ou communauté), démontrant une robustesse face aux violations de l'hypothèse i.i.d.

4.3. Efficacité

QpiGNN partage la même complexité computationnelle $O(Ed + Nd^2)$ que des bases légères comme SQR-GNN. Contrairement à MC Dropout (nécessitant plusieurs passages avant) ou CF-GNN (nécessitant un module de calibration séparé), QpiGNN effectue l'estimation de l'incertitude en un seul passage lors de l'inférence.

5. Contributions clés

1. Cadre d'UQ sans quantiles : QpiGNN est le premier cadre permettant une quantification de l'incertitude calibrée et compacte au niveau des nœuds dans les GNN sans nécessiter d'entrées au niveau des quantiles, de rééchantillonnage ou de post-traitement.
2. Architecture et conception de la perte : L'introduction d'une architecture à double tête couplée à une perte conjointe sans quantiles qui découple la prédiction et l'incertitude, atténuant le sur-étouffement et permettant un entraînement stable.
3. Validation théorique et empirique : L'article fournit des garanties théoriques pour la couverture asymptotique et à échantillon fini sous des hypothèses légères et démontre des performances supérieures sur 19 benchmarks divers, montrant des améliorations significatives tant en couverture qu'en largeur d'intervalle par rapport aux bases de l'état de l'art.

6. Importance

L'article affirme que QpiGNN comble le fossé critique dans les applications de GNN fiables en fournissant une méthode efficace en calcul, robuste et légère en hypothèses pour la quantification de l'incertitude. En évitant les hypothèses fortes d'échangeabilité requises par la prédiction conforme et la surcharge computationnelle des méthodes bayésiennes, QpiGNN offre une solution pratique pour des domaines à haut risque où des intervalles de prédiction fiables sont essentiels. Les auteurs notent que la méthode reste robuste même lorsque les hypothèses théoriques (comme la symétrie ou l'indépendance) ne sont que approximativement satisfaites dans les données de graphes réels.

Les travaux futurs suggérés par les auteurs incluent l'extension de QpiGNN aux tâches de prédiction au niveau du graphe et de lien, la dissociation de l'incertitude aléatoire et épistémique, et l'application du cadre à des graphes dynamiques ou évolutifs.