Embedding Logical Queries on Knowledge Graphs

By William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, Jure Leskovec. 2018

336 citations recorded by the source corpus.

Learning low-dimensional embeddings of knowledge graphs is a powerful approach used to predict unobserved or missing edges between entities. However, an open challenge in this area is developing techniques that can go beyond simple edge prediction and handle more complex logical queries, which might involve multiple unobserved edges, entities, and variables. For instance, given an incomplete biological knowledge graph, we might want to predict "em what drugs are likely to target proteins involved with both diseases X and Y?" -- a query that requires reasoning about all possible proteins that might interact with diseases X and Y. Here we introduce a framework to efficiently make predictions about conjunctive logical queries -- a flexible but tractable subset of first-order logic -- on incomplete knowledge graphs. In our approach, we embed graph nodes in a low-dimensional space and represent logical operators as learned geometric operations (e.g., translation, rotation) in this embedding space. By performing logical operations within a low-dimensional embedding space, our approach achieves a time complexity that is linear in the number of query variables, compared to the exponential complexity required by a naive enumeration-based approach. We demonstrate the utility of this framework in two application studies on real-world datasets with millions of relations: predicting logical relationships in a network of drug-gene-disease interactions and in a graph-based representation of social interactions derived from a popular web forum.

Subfields: Artificial Intelligence, Molecular Biology, Information Retrieval & Search, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Information Retrieval & Search

In Graph Learning

Citations in the corpus

RuleBERT: Teaching Soft Rules to Pre-Trained Language Models (2021, methodology): “Unlike previous work (Hamilton et al., 2018; Yang et al., 2017; Minervini et al., 2020), we do not design a new, ad-hoc module for neural reasoning, but we rely solely on the transformer’s capability to emulate algorithms (Wang et al., 2019b; Lample and Charton, 2020).”
Facts as Experts: Adaptable and Interpretable Neural Memory over Symbolic Knowledge (2020, background): “…many cognitive architectures which used hybrid symbolic and subsymbolic systems (Laird et al., 2017), and more recently, compositional query languages for embedding KBs that are similar to symbolic KB query languages (Cohen et al., 2017; Hamilton et al., 2018; Ren et al., 2020; Cohen et al., 2020).”
Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020, methodology): “In order for the query to be valid , the corresponding dependency graph needs to be a Directed Acyclic Graph (DAG), with the anchor entities as the source nodes of the DAG and the query target V ? as the unique sink node (Hamilton et al., 2018).”
Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks. (2019, background): “Its application range is broad, including molecules, social networks, knowledge graphs and recommender systems (Zitnik et al., 2018; Schlichtkrull et al., 2018; Hamilton et al., 2018; Ying et al., 2018), or in general any datasets that have structural information.”
Learning Distributed Representations of Symbolic Structure Using Binding and Unbinding Operations (2018, background): “, 2010) and those that insert discrete structures into neural network representations (Hamilton et al., 2018).”
Knowledge Graphs (2020, neutral): “Machine learning can be used for directly refining a knowledge graph [100]; or for downstream tasks using the knowledge graph, such as recommendation [155], information extraction [135], question answering [60], query relaxation [139], query approximation [45], and so on.”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, background): “A recent line of work (Hamilton et al., 2018; Ren et al., 2020; Ren & Leskovec, 2020; Sun et al., 2020) proposes to embed complex logical queries by designing neural logical operators, which allows for multi-hop reasoning and execution of logical queries in the embedding space.”
Neural Logic Networks (2019, background): “[7] embedded logical queries on knowledge graphs into vectors.”
CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text (2019, background): “Our work is also related to the domain of question answering and reasoning in knowledge graphs (Das et al., 2018; Xiong et al., 2018; Hamilton et al., 2018; Wang et al., 2018; Xiong et al., 2017; Welbl et al., 2018; Kartsaklis et al., 2018), where either the model is provided with a knowledge graph…”
Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs (2019, methodology): “The application regime of the GNN framework is broad, such as chemical molecules, social networks, knowledge graphs and recommender systems (Zitnik et al., 2018; Schlichtkrull et al., 2018; Hamilton et al., 2018; Ying et al., 2018a).”
Heterogeneous Graph Attention Network (2019, background): “Unlike [13], the type-specific transformation matrix is based on node-type rather than edge-type.”
Neural, symbolic and neural-symbolic reasoning on knowledge graphs (2021, background): “For example, Hamilton et al. (2018) propose a neural reasoning model GQE (i.e., graph query embeddings) to deal with the conjunctive logic queries.”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, background): “Hamilton et al. [89] propose a way of mapping a query formulated as a conjunctive ﬁrst-order logic formula into a vector representation (corresponding to a query embedding) through geometric operations.”
Deep multi-view learning methods: A review (2021, background): “Recently, GNN has achieved outstanding performance in graph-structured data analysis, such as social network [74] and knowledge graphs [75].”
Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction (2021, background): “, complex logical queries with conjunctions (∧) and disjunctions (∨) [18, 45].”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “Briefly put, this area is concerned with expanding the body of knowledge in a (usually closed-domain) knowledge base, typically by inferring additional links or answering logical queries (Hamilton et al., 2018; Ren et al., 2019).”