Timezone: »
State-of-the-art approaches to reasoning and question answering over knowledge graphs (KGs) usually scale with the number of edges and can only be applied effectively on small instance-dependent subgraphs. In this paper, we address this issue by showing that multi-hop and more complex logical reasoning can be accomplished separately without losing expressive power. Motivated by this insight, we propose an approach to multi-hop reasoning that scales linearly with the number of relation types in the graph, which is usually significantly smaller than the number of edges or nodes. This produces a set of candidate solutions that can be provably refined to recover the solution to the original problem. Our experiments on knowledge-based question answering show that our approach solves the multi-hop MetaQA dataset, achieves a new state-of-the-art on the more challenging WebQuestionsSP, is orders of magnitude more scalable than competitive approaches, and can achieve compositional generalization out of the training distribution.
Author Information
Mattia Atzeni (Swiss Federal Institute of Technology Lausanne)
Jasmina Bogojeska (International Business Machines)
Andreas Loukas (EPFL, MIT)
Researcher fascinated by graphs and machine learning.
More from the Same Authors
-
2021 Poster: What training reveals about neural network complexity »
Andreas Loukas · Marinos Poiitis · Stefanie Jegelka -
2021 Poster: Partition and Code: learning how to compress graphs »
Giorgos Bouritsas · Andreas Loukas · Nikolaos Karalias · Michael Bronstein -
2020 Poster: How hard is to distinguish graphs with graph neural networks? »
Andreas Loukas -
2020 Poster: Building powerful and equivariant graph neural networks with structural message-passing »
ClĂ©ment Vignac · Andreas Loukas · Pascal Frossard -
2020 Poster: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs »
Nikolaos Karalias · Andreas Loukas -
2020 Oral: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs »
Nikolaos Karalias · Andreas Loukas