Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Cet article propose un cadre de prédiction conforme pour les sorties graphiques, garantissant une couverture distributionnelle sans hypothèse grâce à l'utilisation de la distance Z-Gromov-Wasserstein et d'une extension de la régression quantile pour générer des ensembles de prédiction adaptatifs.

L'essentiel

Voici une explication simplifiée de ce papier de recherche, imagée comme si nous racontions une histoire de détective et de cartes au trésor.

🕵️‍♂️ Le Problème : Le Détective qui a peur de se tromper

Imaginez que vous êtes un détective (un algorithme d'intelligence) chargé de deviner la structure d'un objet complexe, comme une molécule chimique ou un réseau social, simplement en regardant une photo ou un spectre.

Le problème, c'est que les détectives actuels sont très confiants, mais parfois ils se trompent. Et quand ils se trompent, les conséquences peuvent être graves (par exemple, identifier la mauvaise molécule pour un médicament).

Habituellement, le détective vous dit : "Je suis sûr à 100 % que c'est cette molécule-ci."
Mais si vous lui demandez : "Et si tu as tort ?", il ne sait pas quoi répondre. Il ne vous donne pas de "filet de sécurité".

🛡️ La Solution : Le Filet de Sécurité (Conformal Prediction)

Les auteurs de ce papier proposent une nouvelle méthode pour donner au détective un filet de sécurité. Au lieu de donner une seule réponse, le détective va dire : "Je ne suis pas sûr à 100 %, mais je suis certain à 90 % que la bonne réponse se trouve dans cette liste de 5 molécules possibles."

C'est ce qu'on appelle la Prédiction Conformée. C'est comme si le détective dessinait un cercle autour de ses meilleures guesses. Si le cercle est assez grand, il est presque sûr d'y avoir la bonne réponse.

🧩 Le Défi Spécial : Les Graphes (Des structures qui bougent)

Le vrai défi ici, c'est que les objets qu'ils essaient de prédire sont des graphes (des réseaux de points reliés entre eux).
Imaginez que vous devez reconnaître un ami dans une foule.

• Si vous lui demandez de se mettre à côté de son ami, vous pouvez le reconnaître.
• Mais si vous changez l'ordre des gens dans la foule, ou si vous les nommez différemment, votre cerveau doit quand même reconnaître que c'est le même groupe d'amis.

En informatique, c'est un cauchemar. Si vous changez l'ordre des points d'un graphe, l'ordinateur pense que c'est un objet différent, alors que c'est la même chose. C'est comme si vous disiez que votre maison est différente parce que vous avez changé l'ordre des pièces dans la liste de l'adresse.

📏 L'Outil Magique : La Règle "Z-Gromov-Wasserstein"

Pour résoudre ce problème de "changement d'ordre", les auteurs utilisent une règle de mesure très spéciale appelée Distance Z-Gromov-Wasserstein.

L'analogie du puzzle :
Imaginez que vous avez deux puzzles.

1. Le premier est assemblé.
2. Le deuxième est assemblé, mais les pièces sont dans un ordre différent (les pièces bleues sont à droite au lieu de gauche).

Une règle normale dirait : "Ces deux puzzles sont différents !"
La règle Z-Gromov-Wasserstein, elle, dit : "Attends, peu importe l'ordre des pièces, la façon dont elles sont reliées entre elles est la même. C'est le même puzzle."

Cette règle permet de comparer les graphes de manière intelligente, en ignorant le bruit (l'ordre des noms) et en se concentrant sur la structure (qui est relié à qui). C'est cette règle qui permet de mesurer à quel point le détective a "tordu" la réalité.

🎯 L'Innovation : Le Filet de Sécurité Intelligent (SCQR)

Au début, le filet de sécurité était le même pour tout le monde.

• Pour un cas facile (une molécule simple), le filet était énorme (trop large, pas très utile).
• Pour un cas difficile (une molécule complexe), le filet était peut-être trop petit (risque de rater la cible).

Les auteurs ont inventé une version améliorée appelée SCQR.
L'analogie du parapluie :

• L'ancienne méthode : Tout le monde reçoit le même parapluie géant, qu'il pleuve des gouttes ou un orage. C'est sûr, mais c'est encombrant.
• La nouvelle méthode (SCQR) : Le détective regarde la météo (la complexité de l'entrée). S'il pleut des gouttes (cas facile), il sort un petit parapluie de poche (la liste de candidats est courte et précise). S'il y a un orage (cas difficile), il sort un grand parapluie de camping (la liste est plus large pour être sûr).

C'est adaptatif : le filet s'ajuste à la difficulté du problème.

🧪 Les Résultats : Ça marche !

Les auteurs ont testé leur méthode sur deux terrains de jeu :

1. Un jeu de coloriage (Synthétique) : Comme un jeu de puzzle où il faut retrouver un dessin à partir de ses couleurs.
2. L'identification de molécules (Réel) : Identifier des substances chimiques à partir de spectres de masse (comme dans les laboratoires de chimie).

Le verdict ?

• Leur filet de sécurité fonctionne parfaitement : il attrape la bonne réponse 90 % du temps (comme promis).
• Grâce à leur méthode intelligente (SCQR), ils ont réussi à réduire la taille du filet. Au lieu de donner 50 possibilités, ils n'en donnent souvent que 15, tout en restant aussi sûrs d'eux. C'est comme passer d'une liste de courses de 50 articles à une liste de 15, tout en étant sûr de ne rien oublier d'important.

En résumé

Ce papier explique comment donner aux intelligences artificielles la capacité de dire "Je ne suis pas sûr, mais voici une petite liste de suspects probables" pour des objets complexes comme des molécules.

Ils utilisent une règle mathématique spéciale pour ne pas se tromper sur la forme des objets, et un système de filet intelligent qui s'adapte à la difficulté de la tâche. C'est une avancée majeure pour rendre l'IA plus fiable dans des domaines critiques comme la chimie et la médecine.

Résumé technique

Voici un résumé technique détaillé du papier "Conformal Graph Prediction with Z-Gromov Wasserstein Distances" en français.

1. Problématique et Contexte

La prédiction de graphes supervisée (SGP) vise à apprendre des modèles qui mappent des entrées de diverses modalités (images, spectres, texte) vers des graphes de sortie structurés. Cette tâche est cruciale dans des domaines comme l'identification de molécules en chimie ou la compréhension de scènes en vision par ordinateur.

Cependant, les approches existantes souffrent d'un manque majeur : l'absence de quantification rigoureuse de l'incertitude. Dans des contextes où la validation expérimentale est coûteuse (ex: synthèse de molécules), fournir une simple prédiction ponctuelle est risqué. L'utilisateur a besoin d'un ensemble de prédiction (un ensemble de graphes candidats plausibles) garantissant que le vrai graphe s'y trouve avec une probabilité donnée.

Les défis spécifiques à ce problème sont :

• Espace de sortie non-euclidien et combinatoire : Les graphes vivent dans un espace structuré complexe.
• Invariance par permutation : Deux graphes sont identiques s'ils diffèrent seulement par l'étiquetage de leurs nœuds. Les méthodes de prédiction doivent être invariantes à cette permutation.
• Hétéroscédasticité : L'incertitude varie selon l'entrée (certaines prédictions sont faciles, d'autres ambiguës), ce qui rend les seuils globaux trop conservateurs ou insuffisants.

2. Méthodologie Proposée

Les auteurs proposent un cadre de Prédiction Conformale (Conformal Prediction - CP) adapté aux sorties graphiques, reposant sur deux piliers principaux :

A. Mesure de non-conformité via la Distance Z-Gromov-Wasserstein (Z-GW)

Pour comparer un graphe prédit $\hat{y}$ et un graphe candidat $y$, il faut une métrique qui respecte la structure du graphe et l'invariance par permutation.

• Approche : Utilisation de la distance Z-Gromov-Wasserstein (Z-GW). C'est une généralisation de la distance de Wasserstein qui compare des espaces métriques mesurés (ici, les graphes).
• Implémentation pratique : La distance est instantiée via la Fused Gromov-Wasserstein (FGW), qui permet de prendre en compte à la fois la structure du graphe (connectivité) et les attributs des nœuds/arêtes.
• Avantage théorique : La distance Z-GW est définie sur un espace quotient (où les graphes isomorphes sont identifiés). Cela garantit que le score de non-conformité $s(x, y) = GW_Z(f_\theta(x), y)$ est invariant par permutation des nœuds, rendant la prédiction conforme valide dans l'espace des graphes non étiquetés.

B. Score Conformalized Quantile Regression (SCQR)

La CP standard utilise un seuil global unique, ce qui suppose une incertitude homogène. Pour pallier cela, les auteurs introduisent SCQR.

• Principe : Au lieu d'un seuil fixe, SCQR apprend à prédire un seuil conditionnel en fonction de l'entrée $x$ (ou d'attributs dérivés $\omega(x)$).
• Mécanisme :
  1. On entraîne un modèle de régression de quantiles pour estimer la distribution conditionnelle des scores de non-conformité.
  2. On calcule les résidus adaptatifs.
  3. Le seuil final pour un nouvel exemple dépend de ses caractéristiques (ex: taille de l'ensemble candidat, embedding spectral).
• Résultat : Cela permet d'obtenir des ensembles de prédiction adaptatifs (plus petits pour les cas faciles, plus grands pour les cas ambigus) tout en conservant les garanties de couverture marginale.

3. Contributions Clés

1. Cadre de Prédiction Conformale pour Graphes : Première extension rigoureuse de la CP aux sorties graphiques, avec une preuve de validité dans l'espace quotient des graphes (invariance par permutation).
2. Utilisation de la Z-GW : Définition d'un score de non-conformité basé sur la géométrie des graphes (Z-GW/FGW), permettant une comparaison permutation-invariante.
3. Algorithme SCQR : Introduction d'une variante adaptative de la CP pour les espaces de sortie complexes, améliorant l'efficacité sans sacrifier la validité théorique.
4. Validation Empirique : Évaluation sur deux tâches distinctes :
   • Une tâche synthétique (Coloring) : Prédiction de graphes à partir d'images.
   • Une tâche réelle : Identification de métabolites à partir de spectres de masse (MassSpecGym).

4. Résultats Expérimentaux

Les expériences ont été menées sur des ensembles de données synthétiques et réels (MassSpecGym) avec des modèles de base comme ANY2GRAPH et SPECBRIDGE.

• Validité de la couverture : Les deux méthodes (CP standard et SCQR) atteignent une couverture empirique proche du niveau nominal visé (90%), confirmant la validité théorique du cadre Z-GW.
• Efficacité (Taille des ensembles) :
  • Sur la tâche Coloring, SCQR (conditionné par la taille de l'ensemble candidat) réduit légèrement la taille moyenne des ensembles par rapport à la CP standard, mais les deux fonctionnent bien.
  • Sur la tâche Identification de Métabolites, SCQR apporte un gain significatif. En conditionnant le seuil sur l'embedding spectral (DREAMS), la taille moyenne de l'ensemble de prédiction passe de 24 (CP standard) à 15, tout en maintenant une couverture de ~89.5%. Cela représente une réduction de l'incertitude de 84.8% par rapport à la bibliothèque candidate initiale.
• Robustesse : L'utilisation de la FGW (incluant les attributs de nœuds) réduit l'incertitude par rapport à une distance purement structurelle (Gromov-Wasserstein standard), prouvant l'importance des caractéristiques des nœuds dans la prédiction.

5. Signification et Impact

Ce travail est significatif car il comble un vide théorique et pratique dans l'apprentissage automatique structuré :

• Fiabilité : Il offre une méthode "distribution-free" (sans hypothèse sur la distribution des données) pour quantifier l'incertitude dans des espaces de graphes, ce qui est crucial pour les applications scientifiques à haut risque.
• Généralité : Le cadre basé sur les réseaux Z (Z-networks) et la distance Z-GW est généralisable à d'autres structures (maillages, nuages de points, distributions), au-delà des simples graphes.
• Adaptabilité : L'introduction de SCQR montre comment intégrer l'hétéroscédasticité dans les prédictions conformes pour des sorties complexes, rendant les systèmes plus utiles en pratique en évitant les ensembles de prédiction trop larges pour les cas simples.

En résumé, cette paper propose une solution robuste et mathématiquement fondée pour transformer les prédicteurs de graphes "boîte noire" en systèmes fiables capables de fournir des ensembles de candidats plausibles avec des garanties de couverture rigoureuses.