Source-linked AI summary
Embedding Logical Queries on Knowledge Graphs
William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, Jure Leskovec
TL;DR
The paper addresses the challenge of predicting answers to complex conjunctive graph queries involving multiple unobserved edges, nodes, and variables. It introduces graph query embeddings, which represent nodes and logical operators geometrically to make efficient predictions; the approach performs strongly on real-world datasets and consistently outperforms enumeration-based baselines where comparison is feasible.
Problem
Predicting complex graph queries over incomplete knowledge graphs remains difficult because queries can involve multiple unobserved edges, nodes, and variables rather than a single edge.
Method
Graph query embeddings place graph nodes in a low-dimensional space and represent logical operators as learned geometric operations for predicting conjunctive-query answers.
Results
The full Bilinear GQE achieved AUC 91.0 on Bio and 76.4 on Reddit, while GQE consistently outperformed enumeration-based baselines on queries without bound variables.
Takeaways & Limitations
Embedding logical operations provides an efficient and effective alternative to enumerating edge-likelihood products for conjunctive queries.
Takeaways & Limitations
The framework is limited to valid conjunctive queries with at most one free variable and a directed acyclic dependency graph, and it cannot handle negation or disjunction.
Abstract
from arXiv · showhide
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 {\em 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.
1 Introduction
The paper targets complex conjunctive graph queries involving multiple unobserved edges, nodes, and variables. It introduces graph query embeddings to predict likely answers efficiently on large incomplete knowledge graphs.
- Motivation: Conjunctive queries extend edge prediction by reasoning about subgraph relationships involving multiple unobserved edges, nodes, and variables.They use conjunction and existential quantification to express queries over sets of nodes.
- Motivation: Naively answering these queries requires enumerating all possible diseases or candidate subgraphs because missing edges may make many subgraphs valid.The number of possible queries and satisfying subgraphs is combinatorial.
- Approach: Graph query embeddings represent nodes in a low-dimensional space and logical operators as learned geometric operations such as translation and rotation.The framework predicts nodes likely to satisfy valid conjunctive queries, including queries with unobserved edges.
- Approach: GQEs make predictions in time linear in the number of query edges and constant with respect to input-network size.The framework is evaluated on biomedical and Reddit networks containing millions of edges.
2 Related Work
The work builds on knowledge graph embeddings, logical reasoning, probabilistic databases, and neural theorem proving. Its distinction is predicting unobserved logical relationships directly while scaling to real-world graphs.
- Related work: The framework draws on research spanning embedding methods, knowledge graph completion, and logical reasoning.
- Logical reasoning and knowledge graphs: Prior logical-reasoning work primarily uses logical rules to improve edge prediction in knowledge graphs, whereas this work predicts conjunctive logical queries directly.The target query class involves more than single-edge prediction.
- Probabilistic databases: Probabilistic databases score queries over probabilistic facts, while this setting predicts missing knowledge-graph relationships that could potentially be true.Known edges are provided, but missing edges are not assumed false.
- Neural theorem proving: Neural theorem-proving systems have demonstrated first-order logic proofs in toy knowledge bases, while GQEs target efficient embedding of a useful logic subset on real-world networks.The paper emphasizes scalability to networks with millions of edges.
3 Background and Preliminaries
The paper formalizes conjunctive graph queries over typed, directed knowledge graphs and describes their query-DAG structure. Queries return likely nodes connected through paths or more complex subgraph patterns, with unobserved denotations to predict.
- Knowledge graphs: Knowledge graphs are heterogeneous networks of typed nodes and directed edges represented as binary predicates.The paper uses biomedical and Reddit networks as running examples.
- Running examples: The biomedical dataset contains over 8 million edges between 97,000 nodes across drugs, diseases, proteins, side effects, and biological processes.It includes 42 edge types, including protein interactions and drug-disease treatment relationships.
- Running examples: The Reddit dataset contains over 4 million interaction edges among more than 700,000 users, communities, and posts from 105 videogame-related communities.
- Conjunctive graph queries: A conjunctive query has one target variable, existentially quantified bound variables, anchor nodes, and edges formed from typed predicates.The target variable is the node returned by the query, while bound variables represent existentially quantified nodes.
- Conjunctive graph queries: Queries can represent length-two paths, such as returning drugs likely connected to a disease through ASSOC and TARGET edges.The intermediate protein variable is existentially quantified, and the disease is an anchor node.
- Query structure: More complex queries can form polytrees with multiple anchors, while valid dependency graphs must be DAGs whose anchors are sources and the target is the unique sink.A concrete satisfying subgraph may contain cycles even when the query DAG is acyclic.
- Observed versus unobserved denotations: The framework predicts an unobserved denotation set rather than merely answering a query from exactly observed edges.The observed training denotation set may not fully reveal the denotation sought at prediction time.
4 Proposed Approach
GQE embeds conjunctive graph queries in a low-dimensional space by applying learned geometric projection and intersection operators over a query’s DAG. The resulting query embedding supports prediction of likely satisfying nodes and admits an idealized exactness and efficiency guarantee.
- Framework: GQE maps any conjunctive query to an embedding using differentiable projection and intersection operators jointly optimized with node embeddings.The framework represents query structure as a DAG and applies operators P and I to anchor-node embeddings.
- Geometric operators: Projection transforms a query embedding into the union of neighbors reached through a specified edge type.For an input denotation JqK, P produces the denotation formed by the corresponding τ-type neighbors.
- Geometric operators: Intersection combines query embeddings whose denotations share a common output type and represents their set intersection in embedding space.The operator is implemented using a permutation-invariant set-processing network.
- Query inference: At inference, Algorithm 1 generates a query embedding from anchor embeddings and DAG operations, then retrieves likely satisfying nodes by nearest-neighbor search.Locality-sensitive hashing is one suggested way to accelerate the search.
- Theoretical analysis: In an ideal setting, Algorithm 1 can exactly answer any DAG-structured conjunctive query using O(E) geometric-operator applications.The theorem uses embeddings of dimension d = O(|V|) and establishes equivalence between conjunctive queries and operator sequences.
- Training and variants: The framework supports alternative embedding-based projection models, including Bilinear, DistMult, and TransE, and trains parameters with stochastic-gradient max-margin learning.Training samples positive and negative nodes, including hard negatives for intersection queries.
5 Experiments
The experiments evaluate GQE variants on sampled conjunctive queries from biological and Reddit knowledge graphs, using macro-averaged AUC and APR under standard and hard negatives. Full Bilinear GQE performs strongly, outperforms enumeration where comparison is feasible, and benefits substantially from training on complex queries.
- Experimental setup: Experiments use biological and Reddit datasets and evaluate sampled queries across different query DAG structures.Training and test queries are sampled by DAG structure, with test queries constrained to rely on at least one deleted edge.
- Results: Long paths are the most difficult query type, although Bilinear GQE remains strong on complex queries relative to simple edge prediction.Figure 4 breaks performance down by dependency graph structure and negative-example type.
- Evaluation metrics: Performance is measured by ROC AUC and average percentile rank against typed negative nodes, including hard negatives for intersection queries.Hard negatives satisfy the query when conjunction is relaxed to disjunction.
- Results: 91.0 AUC on Bio and 76.4 AUC on Reddit are achieved by the full Bilinear model, macro-averaged across query DAG structures of size 1–3.The full Bilinear model performs best among the reported GQE variants.
- Baseline comparison: GQE consistently outperforms enumeration on queries with no bound variables, where the enumeration baseline is computationally feasible.Enumeration is intractable for queries with bound variables because it scores candidate subgraphs explicitly.
- Ablation: 13.3% Bio and 13.9% Reddit average AUC improvements result from full GQE training versus Edge Training, with both comparisons having p < 0.001.The reported improvements were assessed with Wilcoxon signed-rank tests.
6 Conclusion
The paper concludes that GQE maps conjunctive graph queries to efficient geometric operations and predicts accurately on real-world graphs with millions of relations. It also identifies logical negation, disjunction, and edge features as unsupported areas.
- Contribution: GQE embeds conjunctive graph queries as efficient geometric operations in an embedding space.The framework targets a practical subset of logic.
- Empirical scope: Experiments show accurate predictions on real-world data with millions of relations.
- Limitations: The framework cannot handle logical negation or disjunction and does not incorporate features on edges.The paper suggests learned geometric negation and graph neural networks as future directions.
Appendix A: Proof of Theorem 1
The proof establishes that DAG-structured conjunctive queries can be represented through geometric projection and intersection operations. Algorithm 1 computes these representations in O(E) operations, while exact representability uses an embedding dimension O(|V|).
- Representability: Embedding dimension d = O(|V|) is sufficient for exact representation of any DAG-structured conjunctive query.The construction uses node embeddings, geometric projections, and geometric intersections.
- Proof strategy: The proof reduces conjunctive-query denotations to set projections and set intersections applied in topological order.The final output set is the query denotation.
- Geometric realization: Under the constructed binary-vector representation, projection uses adjacency-matrix multiplication and intersection uses elementwise minima.These operations preserve the represented sets by induction.
- Complexity: O(E) operations suffice for Algorithm 1, with exactly E projection applications and fewer than E intersection applications.
- Inductive step: Algorithm 1 processes query DAGs topologically, applying projection operators to edges and intersection operators when nodes are removed.The induction tracks sets of possible node assignments for processed variables.
- Base cases: A single-edge query is a set projection, while shared-target conjunctions apply projections followed by intersection.
Bio data
The Bio dataset is a heterogeneous biological interaction network linking five entity types through 42 relation types. It combines multiple public biomedical sources and retains relation types with at least 1,000 edges.
- Dataset composition: The biological network contains proteins, diseases, biological processes, side effects, and drugs connected by 42 interaction types.
- Data sources: Protein–protein interactions come from experimentally documented human interaction networks integrated across multiple sources.
- Data sources: Drug–protein, drug–disease, and disease–protein relations are drawn from STITCH, RepoDB, and DisGeNET, respectively.
- Data sources: Protein–process and process–process links come from Gene Ontology, with protein–process links restricted to experimentally verified relations.
- Preprocessing: Relation types with fewer than 1,000 edges are excluded from experiments.
Reddit data
The study analyzes all activity in 105 videogame-related Reddit communities from May 1–5, 2017, using words appearing at least once as post features.
- The dataset covers posts, comments, upvotes, downvotes, and user subscriptions from 105 videogame-related communities.
- The activity was collected from May 1–5, 2017.
- Post word features included every word occurring at least once, without a frequency threshold.
- The videogame communities were selected by crawling /r/ListOfSubreddits.
Appendix C: Further details on empirical evaluation
The empirical evaluation used publicly available code and selected model settings through validation, fixing the embedding dimension at 128 across experiments.
- The model code is available at the graphqembed GitHub repository.
- Models were evaluated across learning rates and symmetric vector aggregation functions, with the best validation-set model selected.
- The embedding dimension was set to d = 128 in all experiments.
- Embedding dimensions of 16, 64, 128, and 256 were tested during early validation studies on a Bio-data subset.
Further training details
Training proceeds from edge prediction to more complex queries, with weighted query losses, periodic validation, structure-compatible GPU batching, and explicit inverse-edge parameterization.
- The full GQE framework was first trained to convergence on edge prediction, followed by training on more complex queries.
- Path-query and intersection-query losses were weighted by 0.01 and 0.005, respectively.
- Validation was performed every 5000 batches to test for convergence.
- GPU batches contained queries sharing the same relations and directed-acyclic-graph structure, so some batches could be smaller than B.
- The experiments used four NVIDIA Titan X Pascal GPUs, and each model took approximately 3 hours to run.
- Each edge was represented with separately parameterized original and inverse relations, and both were removed when an edge was held out.