Réponse à des requêtes logiques complexes sur les graphes de connaissances par optimisation de l'arbre de calcul de la requête

Répondre à des requêtes logiques complexes sur des graphes de connaissances incomplets est une tâche ardue et a été largement étudiée. Les méthodes basées sur l'embedding nécessitent un entraînement sur des requêtes complexes et ne peuvent pas généraliser efficacement aux structures de requêtes hors distribution. Des travaux récents abordent cette tâche comme un problème d'optimisation de bout en bout, ne nécessitant qu'un prédicteur de liens pré-entraîné. Cependant, en raison de l'espace de recherche combinatoire exponentiellement grand, la solution optimale ne peut être que approximée, limitant ainsi la précision finale. Dans ce travail, nous proposons QTO (Query Computation Tree Optimization) qui peut trouver efficacement la solution optimale exacte. QTO détermine la solution optimale par une propagation avant-arrière sur le graphe de calcul en forme d'arbre, c'est-à-dire l'arbre de calcul des requêtes. Plus précisément, QTO utilise l'indépendance encodée dans l'arbre de calcul des requêtes pour réduire l'espace de recherche, où seules les opérations locales sont impliquées lors du processus d'optimisation. Des expériences menées sur 3 jeux de données montrent que QTO obtient des performances de pointe dans la réponse à des requêtes complexes, surpassant les meilleurs résultats précédents avec une moyenne de 22 %. De plus, QTO peut interpréter les solutions intermédiaires pour chacun des atomes à un saut dans la requête avec une précision supérieure à 90 %. Le code associé à notre article est disponible à l'adresse suivante : https://github.com/bys0318/QTO.