Neural Graph Reasoning: A Survey on Complex Logical Query Answering

Abstract

Complex logical query answering (CLQA) is a recently emerged task of graph machine learning that goes beyond simple one-hop link prediction and solves the far more complex task of multi-hop logical reasoning over massive, potentially incomplete graphs. The task received significant traction in the community; numerous works expanded the field along theoretical and practical axes to tackle different types of complex queries and graph modalities with efficient systems. In this paper, we provide a holistic survey of CLQA with a detailed taxonomy studying the field from multiple angles, including graph types (modality, reasoning domain, background semantics), modeling aspects (encoder, processor, decoder), supported queries (operators, patterns, projected variables), datasets, evaluation metrics, and applications. Finally, we point out promising directions, unsolved problems and applications of CLQA for future research.