GFlowNets Conscients de la Symétrie

Informations Fondamentales

• ID de l'article: 2506.02685
• Titre: Symmetry-Aware GFlowNets
• Auteurs: Hohyun Kim, Seunggeun Lee, Min-hwan Oh (Université Nationale de Séoul)
• Classification: stat.ML cs.LG
• Conférence de publication: ICML 2025 (42e Conférence Internationale sur l'Apprentissage Automatique)
• Lien de l'article: https://arxiv.org/abs/2506.02685

Résumé

Les réseaux de flux génératifs (GFlowNets) fournissent un cadre puissant pour l'échantillonnage de graphes proportionnellement aux récompenses. Cependant, les méthodes existantes souffrent de biais systématiques en raison d'inexactitudes dans le calcul des probabilités de transition d'état. Ces biais sont enracinés dans les symétries intrinsèques des graphes, affectant à la fois les schémas de génération basés sur les atomes et basés sur les fragments. Pour résoudre ce défi, cet article introduit les GFlowNets conscients de la symétrie (SA-GFN), qui intègrent les corrections de symétrie dans le processus d'apprentissage par mise à l'échelle des récompenses. En intégrant directement la correction des biais dans la structure des récompenses, SA-GFN élimine le besoin de calculs explicites de transitions d'état. Les résultats expérimentaux démontrent que SA-GFN réalise un échantillonnage sans biais, tout en améliorant la diversité et en générant continuellement des graphes à haute récompense qui correspondent étroitement à la distribution cible.

Contexte de Recherche et Motivation

Problème Central

Les GFlowNets font face au problème des actions équivalentes dans les tâches de génération de graphes : différentes actions peuvent conduire à des graphes structurellement identiques. Par exemple, lors de l'ajout d'un nouveau nœud à un graphe, les actions de connexion à deux nœuds symétriques, bien que différentes, produisent des graphes isomorphes. Dans ce cas, la probabilité de transition d'état doit tenir compte de toutes les actions équivalentes, mais le calcul est coûteux.

Importance du Problème

1. Biais dans la génération moléculaire: En découverte moléculaire, plus de 50% des molécules possèdent plusieurs symétries, et 18% en contiennent quatre ou plus. Ignorer les symétries conduit à une modélisation incorrecte et à une réduction de la précision de génération des structures moléculaires.
2. Biais systématique: Le biais est systématique, favorisant les graphes avec moins de symétries lors de la génération de nœuds et les composants symétriques lors de la génération de fragments.
3. Complexité computationnelle: Le calcul précis des probabilités de transition d'état nécessite des tests d'isomorphisme de graphes coûteux.

Limitations des Approches Existantes

• Ma et al. (2024) proposent d'utiliser l'encodage positional pour détecter approximativement les actions équivalentes, mais cela nécessite une application à chaque transition, entraînant une surcharge computationnelle importante et ne fournissant qu'une solution approximative.
• Les fonctions objectif GFlowNet traditionnelles (TB, DB, etc.) ne peuvent pas éviter le problème des actions équivalentes car elles sont basées sur la formalisation des transitions d'état.

Contributions Principales

1. Contribution théorique: Fournir une formalisation rigoureuse de la génération autorégrressive de graphes dans le cadre GFlowNet, résolvant explicitement le problème des actions équivalentes
2. Solution simple et efficace: Proposer une méthode de mise à l'échelle des récompenses basée sur la taille du groupe d'automorphisme, nécessitant seulement des modifications minimales aux algorithmes d'entraînement existants
3. Estimateur sans biais: Dériver un estimateur sans biais de la vraisemblance du modèle
4. Validation expérimentale: Vérifier les résultats théoriques par l'expérience, démontrant l'efficacité de la méthode pour générer des échantillons diversifiés à haute récompense

Détails de la Méthode

Définition de la Tâche

Étant donné une fonction de récompense R(x), l'objectif des GFlowNets est d'entraîner une politique pₐ telle que la probabilité d'échantillonnage des états terminaux soit proportionnelle à leur récompense : p̄ₐ(x) = R(x)/Z, où Z est la constante de normalisation.

Cadre Théorique Central

1. Isomorphisme de Graphes et Relations d'Équivalence

• Isomorphisme de graphes: Deux graphes G et G' sont isomorphes (G ≅ G') s'il existe une permutation π telle que π(E) = E'
• Groupe d'automorphisme: Le groupe d'automorphisme Aut(G) d'un graphe G est l'ensemble de toutes les permutations préservant la structure du graphe
• Orbite: L'orbite d'un nœud u est Orb(G,u) = {v ∈ V : ∃π ∈ Aut(G), π(u) = v}

2. Formalisation des Actions Équivalentes

Définition 4.1 (Équivalence de transition): Les transitions de graphe (G₁,G'₁) et (G₂,G'₂) sont équivalentes en transition si G₁ ≅ G₂ et G'₁ ≅ G'₂.

Définition 4.2 (Équivalence d'orbite): Les actions de graphe (G₁,t₁,u₁) et (G₂,t₂,u₂) sont équivalentes en orbite si le type d'action est identique et s'il existe une permutation π telle que π(G₁) = G₂ et π(u₁) = u₂.

Théorème 4.3: Les actions équivalentes en orbite conduisent à des transitions équivalentes en transition.

3. Résultats Théoriques Clés

Lemme 4.5: Pour les actions AddEdge, on a $\frac{|\text{Orb}(G,u,v)|}{|\text{Orb}(G',u,v)|} = \frac{|\text{Aut}(G)|}{|\text{Aut}(G')|}$

Théorème 4.6 (Correction d'automorphisme): Si on utilise des fonctions équivariantes par permutation, alors $\frac{p_{\bar{A}}(a|s)}{q_{\bar{A}}(a|s')} = \frac{|\text{Aut}(G)|}{|\text{Aut}(G')|} \cdot \frac{p_E(G'|G)}{q_E(G|G')}$

Méthode de Correction Consciente de la Symétrie

1. Mise à l'Échelle des Récompenses pour la Génération de Nœuds

Corollaire 5.1 (Correction TB): La perte d'équilibre de trajectoire doit être $L_{TB}(\tau) = \left(\log \frac{Z\prod_{t=0}^{n-1} p_E(G_{t+1}|G_t)}{|\text{Aut}(G_n)|R(G_n)\prod_{t=0}^{n-1} q_E(G_t|G_{t+1})}\right)^2$

Solution: Mettre à l'échelle la récompense comme $\tilde{R}(G) = |\text{Aut}(G)|R(G)$

2. Correction pour la Génération de Fragments

Théorème 5.3 (Correction de fragments): Pour un état terminal G généré en connectant k fragments {C₁,...,Cₖ}: $\tilde{R}(G) = \frac{|\text{Aut}(G)|R(G)}{\prod_{i=1}^k |\text{Aut}(C_i)|}$

3. Estimateur Sans Biais de la Vraisemblance du Modèle

$\bar{p}_A(x) = \mathbb{E}_{\tau \sim q_E(\tau|G_n)}\left[\frac{p_E(\tau)}{|\text{Aut}(G_n)|q_E(\tau|G_n)}\right]$

Points d'Innovation Technique

1. Élégance théorique: Simplifier la correction complexe au niveau des transitions en mise à l'échelle des récompenses de l'état terminal
2. Efficacité computationnelle: Éviter les tests d'isomorphisme de graphes en ligne à chaque étape, ne calculer la taille du groupe d'automorphisme qu'une seule fois
3. Universalité: Applicable à plusieurs objectifs GFlowNet (TB, DB, FM, etc.)
4. Exactitude: Fournir une solution exacte plutôt qu'approximative

Configuration Expérimentale

Ensembles de Données

1. Exemples illustratifs: État initial avec 6 nœuds déconnectés, 112 états terminaux
2. Graphes synthétiques: Graphes hétérogènes avec au maximum 7 nœuds, 72 296 états terminaux
3. Génération moléculaire:
   • Niveau atomique: Tâche de prédiction de l'écart HOMO-LUMO
   • Niveau fragment: Tâche de prédiction de l'énergie de liaison de la cible sEH

Métriques d'Évaluation

• Erreur L1: Erreur L1 entre les probabilités cibles et les probabilités terminales du modèle
• Diversité: Distance Tanimoto moyenne entre les molécules
• Indicateurs Top K: Diversité et récompense des K molécules à haute récompense
• Unicité: Proportion de molécules uniques dans les échantillons générés

Méthodes de Comparaison

1. GFlowNets Vanilla: Sans considération de la symétrie des graphes
2. Transition Correction: Identification des actions de transition équivalentes par tests d'isomorphisme multiples
3. PE (Ma et al., 2024): Identification approximative des actions d'orbite équivalente utilisant l'encodage positional
4. Reward Scaling (cet article): Correction par modification du signal de récompense
5. Flow Scaling (cet article): Multiplication par le rapport de symétrie à chaque transition

Résultats Expérimentaux

Résultats Principaux

1. Expériences Illustratives

• Le modèle Vanilla montre des probabilités terminales groupées par |x|, avec un biais évident
• Reward Scaling atteint les mêmes performances que Transition Correction
• Constante de normalisation estimée Z: Reward Scaling = 112 (valeur vraie), Vanilla = 26 706

2. Expériences sur Graphes Synthétiques

• Objectif TB: Reward Scaling réduit significativement l'erreur L1, avec des performances comparables à Transition Correction
• Objectif DB: Reward Scaling converge plus lentement mais atteint finalement la même précision
• La méthode PE, en tant que solution approximative, affiche des performances intermédiaires entre Vanilla et les méthodes exactes

3. Expériences de Génération Moléculaire

Résultats au niveau atomique:

• Diversité: 0,929 → 0,959 (Vanilla → Reward Scaling)
• Unicité: 0,93 → 1,0

Résultats au niveau fragment:

• Récompense Top K: 0,941 → 0,952 (Vanilla → Reward Scaling Exact)
• Utilisation de fragments cyclohexane: 5 220 → 1 042 (réduction significative de la surutilisation de fragments symétriques)

Expériences d'Ablation

• Correction approximative vs exacte: La méthode approximative améliore déjà significativement les performances
• Différentes fonctions objectif: TB et DB peuvent tous deux être efficacement corrigés par mise à l'échelle des récompenses

Analyse de l'Efficacité Computationnelle

• Temps de calcul d'automorphisme: 0,010 ms pour QM9, 0,022 ms pour ZINC250k
• Comparé à la propagation avant du réseau de neurones lors de l'échantillonnage de trajectoires, la surcharge computationnelle est négligeable
• Comparaison du temps d'entraînement: Reward Scaling est environ 15% plus rapide que Transition Correction

Travaux Connexes

Génération Autorégrressive de Graphes

• Méthodes de matrice d'adjacence: Conservent les informations d'ordre des nœuds, moins sujettes au problème des actions équivalentes
• Méthodes de séquence de graphes: Produisent facilement des actions équivalentes, le problème devient critique lors du calcul des probabilités de transition d'état

GFlowNets

• Les fonctions objectif existantes (appariement de flux, équilibre détaillé, équilibre de trajectoire, etc.) ne peuvent pas éviter le problème des actions équivalentes
• Ma et al. (2024) ont identifié le problème en premier mais ne fournissent qu'une solution approximative

Capacité d'Expression des Réseaux de Neurones de Graphes

• L'équivariance par permutation conduit à des représentations identiques pour les nœuds de la même orbite
• La capacité d'expression limitée peut entraîner un chevauchement de représentation entre différentes actions d'orbite

Conclusion et Discussion

Conclusions Principales

1. Contribution théorique: Première analyse rigoureuse du problème des actions équivalentes dans les GFlowNets, prouvant qu'il entraîne des biais systématiques
2. Solution pratique: La mise à l'échelle des récompenses fournit une méthode de correction simple, exacte et efficace
3. Applicabilité générale: La méthode s'applique à la génération au niveau atomique et au niveau fragment, ainsi qu'à plusieurs objectifs d'entraînement

Limitations

1. Dépendance à la conception des actions: Les garanties théoriques dépendent d'un ensemble d'actions de graphe prédéfinies spécifiques
2. Spécificité des tâches: Principalement validée sur des ensembles de données liés à la découverte moléculaire
3. Capacité d'expression des GNN: La capacité d'expression limitée des GNN peut introduire des biais supplémentaires

Directions Futures

1. Explorer des tâches avec différents motifs de symétrie et structures de récompense
2. Concevoir des architectures GNN avec une plus grande capacité d'expression
3. Étendre à des scénarios de génération de graphes plus complexes

Évaluation Approfondie

Avantages

1. Rigueur théorique: Fournir un cadre mathématique complet et une analyse théorique rigoureuse
2. Simplicité de la méthode: La solution est extrêmement simple, facile à implémenter et à intégrer
3. Valeur pratique: Démontrer des effets réels dans des applications importantes comme la génération moléculaire
4. Efficacité computationnelle: Éviter les tests d'isomorphisme de graphes en ligne coûteux
5. Force universelle: Applicable à plusieurs objectifs d'entraînement GFlowNet

Insuffisances

1. Portée expérimentale: Principalement concentrée sur les tâches de génération moléculaire, validation limitée sur d'autres tâches de génération de graphes
2. Hypothèses théoriques: Dépend de la conception d'actions spécifiques et d'hypothèses d'architecture GNN
3. Méthodes approximatives: La correction approximative pour la génération de fragments manque de garanties théoriques
4. Scalabilité: Pour les très grands graphes, le calcul d'automorphisme pourrait devenir un goulot d'étranglement

Impact

1. Valeur académique: Fournir un complément important à la théorie des GFlowNets, résolvant un problème fondamental
2. Valeur pratique: Contribution directe aux domaines d'application tels que la découverte de médicaments
3. Reproductibilité: La méthode est simple et facile à reproduire et appliquer
4. Inspiration: Fournir des idées pour le traitement de la symétrie dans d'autres modèles génératifs

Scénarios d'Application

1. Conception moléculaire: Applications en chimie informatique telles que la découverte de médicaments et la conception de matériaux
2. Génération de graphes: Tâches de génération de graphes nécessitant de considérer les symétries structurelles
3. Optimisation combinatoire: Problèmes d'optimisation combinatoire avec contraintes de symétrie
4. Apprentissage par renforcement: Tâches d'RL dont l'espace d'état possède des symétries

Références

1. Bengio et al. (2021) - Fondements des GFlowNets
2. Ma et al. (2024) - Première identification du problème des actions équivalentes
3. Malkin et al. (2022) - Objectif d'équilibre de trajectoire
4. Jain et al. (2023) - Application des GFlowNets multi-objectifs

Évaluation Globale: Cet article est un excellent travail équilibrant théorie et pratique, résolvant un problème fondamental important mais négligé dans les GFlowNets. La méthode est élégante et simple, l'analyse théorique est rigoureuse, et la validation expérimentale est complète. Il apporte des contributions importantes tant au développement théorique des GFlowNets qu'aux applications pratiques, et devrait avoir un impact durable sur les domaines connexes.