Komplexe logische Abfragen auf Wissensgraphen durch Optimierung des Abfrageberechnungsbaums beantworten

Das Beantworten komplexer logischer Abfragen auf unvollständigen Wissensgraphen ist eine herausfordernde Aufgabe und wurde bereits intensiv untersucht. Methoden basierend auf Einbettungen erfordern ein Training auf komplexen Abfragen und können sich nicht gut auf Abfragestrukturen verallgemeinern, die außerhalb des Trainingsbereichs liegen. Kürzliche Arbeiten stellen diese Aufgabe als ein End-to-End-Optimierungsproblem dar und benötigen lediglich einen vortrainierten Link-Predictor. Allerdings wird die optimale Lösung aufgrund des exponentiell großen kombinatorischen Suchraums nur näherungsweise gefunden, was die endgültige Genauigkeit einschränkt. In dieser Arbeit schlagen wir QTO (Query Computation Tree Optimization) vor, das die exakte optimale Lösung effizient finden kann. QTO findet die optimale Lösung durch eine Vorwärts-Rückwärts-Propagation im baumartigen Berechnungsgraphen, also dem Abfrage-Berechnungsbaum. Insbesondere nutzt QTO die Unabhängigkeit, die im Abfrage-Berechnungsbaum kodiert ist, um den Suchraum zu reduzieren, wobei während des Optimierungsprozesses nur lokale Berechnungen involviert sind. Experimente mit 3 Datensätzen zeigen, dass QTO den Stand der Technik in der Beantwortung komplexer Abfragen erreicht und die bisher besten Ergebnisse durchschnittlich um 22 % übertrifft. Darüber hinaus kann QTO die Zwischenergebnisse für jedes der One-Hop-Atome in der Abfrage mit einer Genauigkeit von über 90 % interpretieren. Der Quellcode unseres Papers ist unter https://github.com/bys0318/QTO verfügbar.