To address the challenges of incomplete knowledge graphs, this paper proposes a novel question-answering approach that predicts answers that exist in the complete knowledge graph, even if they are not explicitly present in the graph. We formally introduce and study two question-answering problems: question-answer classification and question-answer retrieval. To achieve this, we propose the AnyCQ model, which can classify answers to arbitrary combined queries on arbitrary knowledge graphs. At its core, AnyCQ is a graph neural network trained using reinforcement learning objectives, which provides answers to Boolean queries. Trained on simple, small instances, AnyCQ generalizes to large queries with arbitrary structure, reliably classifying and retrieving answers to queries that existing approaches fail. We experimentally validate this approach using a newly proposed, challenging benchmark and demonstrate that AnyCQ can effectively transfer to entirely new knowledge graphs using an appropriate link prediction model, highlighting its potential for querying incomplete data.
