Résumé Technique : UniQGen – Génération de Requêtes Graphiques avec Agents de Langage Naturel Guidés par Contraintes

Énoncé du Problème

La Réponse aux Questions sur les Graphes de Connaissances (KGQA) a traditionnellement été cloisonnée en deux paradigmes isolés : le modèle de Framework de Description de Ressources (RDF) interrogé via SPARQL, et le modèle de Graphes de Propriétés Étiquetées (LPG) interrogé via Cypher ou Gremlin. Cette séparation crée un effet de « verrouillage par modèle de graphe », où les engagements organisationnels envers un paradigme spécifique se propagent aux langages de requête et aux chaînes d'outils, rendant la migration coûteuse. Bien que les Modèles de Langage (LLM) aient montré des promesses dans la génération de requêtes graphiques, le déploiement industriel fait face à quatre défis critiques :

1. Hallucination/Désalignement : Les LLM génèrent souvent des requêtes syntaxiquement valides qui ne correspondent pas au schéma ou à la topologie sous-jacente du Graphe de Connaissances (KG).
2. Absence de Contraintes Pragmatiques : Les requêtes générées échouent fréquemment à capturer les intentions implicites de l'utilisateur (par exemple, filtrer pour des « médicaments approuvés » plutôt que n'importe quel médicament).
3. Coûts Élevés de Maintenance : Les méthodes existantes reposent lourdement sur un fine-tuning spécifique au schéma, ce qui les rend fragiles lorsque les schémas évoluent ou lors de la migration vers de nouveaux KG.
4. Absence de Solutions Unifiées : La plupart des benchmarks et méthodes se concentrent sur un seul langage de requête (généralement SPARQL), laissant un vide pour une génération unifiée et multilingue (par exemple, Cypher) sans réentraînement.

Méthodologie : Cadre UniQGen

Les auteurs proposent UniQGen, un cadre sans entraînement et agnostique au schéma qui convertit les requêtes en langage naturel (NL) en requêtes graphiques exécutables (Cypher ou SPARQL) en utilisant une approche guidée par contraintes basée sur une variante de l'algorithme Chase & Backchase. Le cadre opère à travers trois étapes principales orchestrées par des agents LLM :

1. Extraction de Faits Centrée sur la Requête

Étant donné une requête NL $Q_n$ et un KG $G$, le système effectue d'abord un lien d'entités pour identifier les nœuds mentionnés. Il induit ensuite un sous-graphe local $G'$ en agrégeant les voisinages à $k$-sauts de ces entités. Ce sous-graphe sert de contexte factuel pour l'extraction de contraintes ultérieure.

2. Construction de la Table de Contraintes (CTable)

L'agent $a_1$ construit une Table de Contraintes (CTable), une abstraction agnostique au langage contenant :

• Motifs de Triplets Typés : Relations entre entités.
• Contraintes de Valeur : Filtres sur les littéraux (par exemple, $x > c$).
• Contraintes Structurelles : Jointures, chemins bornés, etc.
  Crucialement, l'agent enrichit cette table avec des contraintes implicites/pragmatiques (par exemple, Approved=True) dérivées du contexte de la requête. Chaque contrainte $c_i$ se voit attribuer un score d'incertitude $u_i \in [0, 1]$ basé sur son nombre de correspondances dans le KG, guidant ainsi le processus de recherche. La CTable est normalisée en un noyau monotone pour faciliter la manipulation logique.

3. Boucle Chase & Backchase Assistée par LLM

L'agent $a_2$ exécute une recherche en deux phases pour équilibrer la complétude LLM (couvrant toutes les réponses de référence) et la sûreté LLM (excluant les réponses non pertinentes), en utilisant une stratégie de recherche faisceau :

• Phase de Chase de Requête (Relaxation) : En partant d'une « Requête Universelle » ($Q_U$) contenant toutes les contraintes, le système retire itérativement une contrainte à la fois si la requête échoue à couvrir l'ensemble des réponses de référence $A$ (fourni par un oracle LLM). Cela garantit une complétude relative.
• Phase de Backchase de Requête (Resserrement) : En partant des sous-requêtes de $Q_U$, le système ajoute itérativement des contraintes pour trouver une « Requête Minimale » ($Q_M$) qui satisfait l'ensemble de référence sans redondance, garantissant ainsi une sûreté et une minimalité relatives.
• Rendu : Le plan logique final est rendu dans le langage de requête cible (Cypher ou SPARQL) via un renduur plugable.

Le cadre repose sur une validation en temps réel par rapport à un ensemble de réponses de référence $A$ plutôt que sur un entraînement hors ligne, le rendant adaptable aux dérives de schéma et aux nouveaux KG avec une configuration minimale (par exemple, mise à jour des listes de synonymes).

Contributions Clés

1. Pipeline Unifié Adapté au Déploiement : UniQGen unifie l'extraction de contraintes, la construction de CTable et l'affinement par Chase & Backchase en un seul pipeline qui génère des requêtes grammaticalement correctes et sémantiquement raisonnables pour la KGQA sans schéma, sans fine-tuning.
2. Reformulation Basée sur les Contraintes : Les auteurs adaptent l'algorithme Chase & Backchase pour la génération de requêtes graphiques, en utilisant des agents LLM pour explorer des contraintes candidates via une recherche faisceau tout en imposant des garanties de complétude et de sûreté relatives.
3. Ressources et Évaluation : Les auteurs ont déployé un graphe Freebase sur Amazon Neptune supportant à la fois Cypher et SPARQL. Ils ont publié un instantané Freebase curaté, une recette de déploiement en une étape, et des paires Cypher or alignées sur des benchmarks SPARQL populaires (GraphQ, GrailQA, WebQSP) pour faciliter une recherche reproductible et multilingue.

Résultats Expérimentaux

Le cadre a été évalué sur trois benchmarks standards : GraphQ, GrailQA et WebQSP.

• Performance : UniQGen a surpassé les bases de référence de l'état de l'art (incluant Pangu et ArcaneQA) tant en précision qu'en efficacité.
  • Sur GraphQ, UniQGen a obtenu un gain F1 de 31,6 % par rapport à la meilleure base de référence.
  • Sur GrailQA, il a obtenu un gain F1 de 4,9 %.
  • Il a démontré une performance supérieure dans des configurations à faible ressource (GraphQ) et pour des requêtes multi-sauts, où les méthodes basées sur l'entraînement se dégradent souvent.
• Capacité Multilingue : Le cadre a généré avec succès des requêtes Cypher de haute qualité, un domaine précédemment sous-exploré dans les benchmarks KGQA dominés par SPARQL.
• Efficacité : Contrairement aux systèmes basés sur l'entraînement nécessitant plusieurs jours de fine-tuning, UniQGen a un coût d'entraînement nul. Il atteint une latence de génération moyenne d'environ 40 secondes par requête, avec des plans minimaux s'exécutant en moins de 0,3 seconde (P50).
• Robustesse : Le système a maintenu une performance stable sous des contraintes de style production (délais d'attente, demandes concurrentes) et a montré une dégradation gracieuse sur les requêtes complexes multi-sauts par rapport aux bases de référence.

Importance et Revendications

L'article revendique que UniQGen comble le fossé critique entre les solutions académiques de KGQA et les besoins industriels en offrant une approche unifiée et sans entraînement qui atténue le « verrouillage linguistique ». En exploitant l'algorithme Chase & Backchase avec des agents LLM, le cadre fournit des garanties relatives de sûreté et de complétude par rapport à un ensemble de réponses de référence, sans nécessiter d'entraînement spécifique coûteux au schéma.

Les auteurs soulignent que leur approche est particulièrement adaptée à la KGQA de niveau entreprise où les schémas sont vastes, dynamiques ou propriétaires (sans schéma), et où la capacité à basculer entre les langages de requête (par exemple, Cypher vs SPARQL) sans réentraînement est essentielle. La publication de l'instantané Freebase prêt pour Neptune et des benchmarks multilingues vise à soutenir la recherche future en KGQA unifiée et reproductible.