Neural-Symbolic Models for Logical Queries on Knowledge Graphs

Zhaocheng ZhuMikhail GalkinZuobai ZhangJian Tang

article2022ICML105 citations

Presents a neural-symbolic framework that executes complex first-order logic queries over incomplete knowledge graphs by combining graph neural networks with product fuzzy logic, providing interpretable intermediate steps and state-of-the-art reasoning accuracy.

Listen

Knowledge graphs organize real-world facts into structured networks of entities and relationships, serving as critical infrastructure for applications such as drug discovery, semantic search, and automated decision support. A central challenge is answering complex First-Order Logic queries—questions requiring multi-hop reasoning alongside logical operations like conjunction (AND), disjunction (OR), and negation (NOT). Traditional symbolic methods provide transparent, step-by-step reasoning but fail on incomplete graphs where facts are missing. Conversely, recent neural embedding models can infer missing information but operate as opaque black boxes, making their intermediate reasoning steps impossible to verify or interpret.

The article introduces and evaluates the Graph Neural Network Query Executor (GNN-QE), a hybrid neural-symbolic framework designed to answer complex logical queries over incomplete knowledge graphs while maintaining step-by-step interpretability.

The framework decomposes complex logical queries into continuous operations over "fuzzy sets"—probabilistic representations of entity memberships. It implements relational transitions between entities using a Graph Neural Network architecture adapted from knowledge graph completion and executes logical operations using product fuzzy logic. To ensure robust generalization on incomplete data, the system incorporates "traversal dropout" during training to prevent the network from memorizing direct graph paths. In addition, the framework introduces a non-recursive batched execution pipeline using postfix notation, allowing efficient GPU processing across diverse and previously unseen query structures. The model was evaluated across 14 standard query types on three established benchmark datasets: FB15k, FB15k-237, and NELL995.

The evaluation produced four key findings. First, GNN-QE established a new state of the art in answering complex logical queries, achieving average relative performance improvements of 22.3% on positive logical queries and 95.1% on queries containing negation compared to leading embedding baselines like ConE. Second, it demonstrated strong sample efficiency, matching or exceeding prior models' full-dataset performance even when trained on only 1% of the training data. Third, the model accurately estimated the total number of correct answers without requiring explicit cardinality supervision, achieving Spearman rank correlations ranging from 0.89 to 0.95 against ground truth. Fourth, the architecture enabled direct inspection and visualization of intermediate reasoning variables, allowing users to audit intermediate entity rankings and identify precisely where reasoning errors occur.

These results demonstrate that organizations do not have to choose between the predictive power of neural networks and the transparency of symbolic systems. In high-stakes environments—such as clinical research, compliance monitoring, and intelligence analysis—the ability to verify intermediate reasoning significantly reduces operational risk and accelerates failure diagnosis. Furthermore, the model's exceptional sample efficiency substantially lowers the computational resources and data labeling required to deploy reasoning systems.

Organizations developing knowledge graph reasoning systems should consider adopting neural-symbolic architectures over pure embedding methods, especially when handling complex queries with negation or when regulatory compliance mandates explainability. Future implementation efforts should focus on integrating GNN-QE with natural language interfaces to enable end-to-end question answering directly from conversational input.

Users should note that while the method performs robustly on standard benchmarks, its accuracy remains bounded by the underlying coverage and quality of the knowledge graph. Missing baseline facts in incomplete graphs can occasionally lead to false intermediate deductions. Further development is also required to scale the framework efficiently to massive, web-scale graphs containing millions of entities.

CIFAR HEC Montréal McGill University Mila – Québec Artificial Intelligence Institute Université de Montréal bipartite graphs knowledge graph embedding Neural-Symbolic Models Logical Queries Knowledge Graphs

arXiv: 2205.10128

Paper: Modeling Relational Data with Graph Convolutional Networks, Michael Schlichtkrull et al. (2018). This paper establishes relational graph convolutional networks for link prediction and knowledge graph completion, providing the foundational message-passing architecture that GNN-QE adapts for relation projections.
Paper: A Survey on Knowledge Graphs: Representation, Acquisition, and Applications, Shaoxiong Ji et al. (2020). This survey offers a comprehensive overview of knowledge graph representation learning, completion, and logical rule reasoning that contextualizes the problem space addressed by GNN-QE.
Paper: A Review of Relational Machine Learning for Knowledge Graphs, Maximilian Nickel et al. (2015). This paper reviews core statistical and relational machine learning paradigms for knowledge graphs, clarifying traditional symbolic and latent-space reasoning methods.
Paper: Convolutional 2D Knowledge Graph Embeddings, Tim Dettmers et al. (2017). This work introduces expressive convolutional embeddings for multi-relational link prediction on knowledge graphs, framing the missing-link reasoning problem addressed by GNN-QE.
Paper: Markov logic networks, Matthew Richardson et al. (2006). This foundational paper combines first-order logic with probabilistic graphical modeling, establishing the principles of soft logical reasoning that underpin fuzzy logic operations over knowledge graphs.
Paper: Graph Neural Networks: A Review of Methods and Applications, Jie Zhou et al. (2018). This survey outlines the core message-passing mechanisms and representational properties of graph neural networks necessary to understand multi-hop graph neural execution.

Paper: Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts, Emanuele Marconato et al. (2023). This paper analyzes and mitigates reasoning shortcuts in neuro-symbolic predictors, extending the investigation into the reliability and faithful interpretability of neural-symbolic logic execution.
Paper: Efficient Rectification of Neuro-Symbolic Reasoning Inconsistencies by Abductive Reflection, Wen-Chao Hu et al. (2025). This work explores efficient neuro-symbolic error correction via abductive reflection, advancing hybrid neural-symbolic reasoning frameworks beyond feedforward query execution.
Paper: Unifying Large Language Models and Knowledge Graphs: A Roadmap, Shirui Pan et al. (2023). This roadmap charts future paradigms combining neural language reasoning with structured symbolic knowledge graphs for complex multi-hop question answering.
Paper: StructGPT: A General Framework for Large Language Model to Reason over Structured Data, Jinhao Jiang et al. (2023). This work develops an iterative framework for reasoning over structured knowledge graphs and tables using modular neural executors and language models.
Paper: NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs, Mikhail Galkin et al. (2022). This paper provides a parameter-efficient, compositional representation method that scales complex multi-relational graph reasoning to massive knowledge graphs.

Cover for Neural-Symbolic Models for Logical Queries on Knowledge Graphs

Abstract

Answering complex first-order logic (FOL) queries on knowledge graphs is a fundamental task for multi-hop reasoning. Traditional symbolic methods traverse a complete knowledge graph to extract the answers, which provides good interpretation for each step. Recent neural methods learn geometric embeddings for complex queries. These methods can generalize to incomplete knowledge graphs, but their reasoning process is hard to interpret. In this paper, we propose Graph Neural Network Query Executor (GNN-QE), a neural-symbolic model that enjoys the advantages of both worlds. GNN-QE decomposes a complex FOL query into relation projections and logical operations over fuzzy sets, which provides interpretability for intermediate variables. To reason about the missing links, GNN-QE adapts a graph neural network from knowledge graph completion to execute the relation projections, and models the logical operations with product fuzzy logic. Experiments on 3 datasets show that GNN-QE significantly improves over previous state-of-the-art models in answering FOL queries. Meanwhile, GNN-QE can predict the number of answers without explicit supervision, and provide visualizations for intermediate variables.

Topics

bipartite graphs knowledge graph embedding

Keywords

Neural-Symbolic Models Logical Queries Knowledge Graphs Symbolic Query Decomposition neural relation projection model multi-hop reasoning First-Order Logic fuzzy logic negation queries probabilistic reasoning

1. Introduction
2. Related Work
3. Preliminary
3.1. First-Order Logic Queries on Knowledge Graphs
3.2. Fuzzy Sets and Fuzzy Logic Operations
4. Proposed Method
4.1. Symbolic Query Decomposition
4.2. Neural Relation Projection
4.3. Fuzzy Logic Operations
4.4. Learning
5. Experiments
5.1. Experiment Setup
5.2. Complex Query Answering
5.3. Answer Set Cardinality Prediction
5.4. Intermediate Variables Visualization
5.5. Ablation Study
6. Conclusion
Acknowledgements
References
A. Dataset Statistics
B. Hyperparameters
C. Batched Expression Execution
D. More Experiment Results
E. More Visualization Results

Knowls

Knowl 1 — GNN-QE neural-symbolic query execution
model/method
Graph Neural Network Query Executor (GNN-QE) answers existential first-order logic queries containing relation atoms, conjunction, disjunction, and negation on an incomplete knowledge graph $G=(V,E,R)$ , where $V$ is the entity set, $E$ is the observed edge set, and $R$ is the relation set. A query is symbolically decomposed into relation projections and logical operations over fuzzy sets represented by vectors in $[0,1]^V$ . Each vector entry is the predicted membership probability of one entity, so intermediate vectors directly expose the model's assignments for intermediate variables.

Relation projections are learned by a graph neural network that predicts missing links, while conjunction, disjunction, and negation are computed with differentiable fuzzy-logic operators. The overview diagram on page 3 depicts this execution process: singleton entity vectors are propagated through learned relation projections, combined by fuzzy operators, and finally projected to the answer variable.
Knowl 2 — Symbolic decomposition of first-order queries into fuzzy-set operations
definition
For a fuzzy entity set $x\in[0,1]^V$ and relation $q\in R$ , GNN-QE defines a forward projection $P_q(x)$ as the fuzzy set of tail entities reachable from $x$ through $q$ , and an inverse projection $P_q^{-1}(x)$ as the fuzzy set of head entities that can reach $x$ through $q$ . For $x,y\in[0,1]^V$ , it also defines conjunction $C(x,y)$ , disjunction $D(x,y)$ , and negation $N(x)$ . Existentially quantified variables are eliminated by composing these operations, leaving a fuzzy vector for each free variable.

For example, the query asking for universities where Turing Award winners in deep learning work is represented as
$P_{\mathrm{University}}\!\left(C\left(P_{\mathrm{Win}}^{-1}(\{\mathrm{Turing\ Award}\}),P_{\mathrm{Field}}^{-1}(\{\mathrm{Deep\ Learning}\})\right)\right),$
where each singleton set is a vector in $[0,1]^V$ with membership one for the named entity and zero elsewhere. This decomposition makes every intermediate variable an explicit fuzzy set rather than an uninterpretable query embedding.
Knowl 3 — Neural relation projection for fuzzy head sets
model/method
GNN-QE learns a relation projection $y=P_q(x)$ that maps a fuzzy head-entity vector $x\in[0,1]^V$ and a relation $q$ to a fuzzy tail-entity vector $y\in[0,1]^V$ , including links absent from the observed graph. Let $d$ be the hidden representation dimension and let $\mathbf e_q\in\mathbb{R}^d$ be the embedding of the projected relation. The graph neural network initializes every entity representation by
$h_v^{(0)}=x_v\mathbf e_q,\qquad v\in V,$
so a singleton head set is a special case in which only one entity receives a nonzero initialization. For an incoming edge $(z,r,v)\in E$ , the message at layer $t$ is parameterized as
$\operatorname{MESSAGE}(h_z^{(t-1)},(z,r,v))=h_z^{(t-1)}\odot\left(W_r^{(t)}\mathbf e_q+b_r^{(t)}\right),$
where $W_r^{(t)}$ and $b_r^{(t)}$ are relation- and layer-specific parameters and $\odot$ is elementwise multiplication. A principal-neighborhood-aggregation operator combines incoming messages to produce $h_v^{(t)}$ . After $T$ message-passing layers, a multilayer perceptron $f$ and componentwise sigmoid $\sigma$ produce
$P_q(x)=\sigma\!\left(f\left(h^{(T)}\right)\right).$
The computational cost is $O(|V|d^2+|E|d)$ per message-passing iteration, avoiding the $O(|V|^2d)$ computation that would be required to score every pair of head and tail entities independently.
Knowl 4 — Product fuzzy logic for logical operators
equation
For fuzzy-set vectors $x,y\in[0,1]^V$ , GNN-QE instantiates the logical operations with product fuzzy logic:
$C(x,y)=x\odot y,$ $D(x,y)=x+y-x\odot y,$ $N(x)=\mathbf{1}-x,$
where $\odot$ is elementwise multiplication and $\mathbf{1}\in\mathbb{R}^{|V|}$ is the all-ones vector representing the complete universe of entities. Thus, for each entity $v\in V$ , conjunction multiplies membership degrees, disjunction computes $x_v+y_v-x_vy_v$ , and negation computes $1-x_v$ . These operators are differentiable and obey important fuzzy-logic laws, including both De Morgan identities:
$N(C(x,y))=D(N(x),N(y)),\qquad N(D(x,y))=C(N(x),N(y)).$
Applying the operators directly to entity-membership vectors, rather than to latent query embeddings, is what enables GNN-QE to visualize intermediate assignments.
Knowl 5 — Query training with traversal dropout
model/method
For a query $Q$ with answer set $A_Q\subseteq V$ , GNN-QE trains the final fuzzy answer vector with binary cross-entropy over every entity:
$\mathcal{L}(Q)=-\frac{1}{|A_Q|}\sum_{a\in A_Q}\log p(a\mid Q)-\frac{1}{|V\setminus A_Q|}\sum_{a'\in V\setminus A_Q}\log\left(1-p(a'\mid Q)\right),$
where $p(a\mid Q)$ is the final fuzzy membership assigned to entity $a$ . Because the model predicts all entities simultaneously, the query loss does not require negative sampling.

To prevent the model from merely memorizing observed relation paths, traversal dropout first extracts the edges used by a symbolic relation traversal for a training query and then independently masks each traversed edge in each relation projection with probability $p$ . With $p=0$ , the model can converge to a relation-traversal solution that fits complete training graphs but fails on missing links; larger nonzero values force prediction from surrounding graph structure. The probability is selected on validation data, and the experiments use $p=0.25$ .
Knowl 6 — Batched postfix execution of heterogeneous query expressions
algorithm
GNN-QE converts each query expression into postfix notation so that expressions with different structures can be executed in one batch without recursively enumerating query types. The input is a batch of postfix expressions whose operands are singleton fuzzy sets or previously computed fuzzy sets; the output is one fuzzy answer vector per expression.
Input: A batch of query expressions in postfix notation
Output: One fuzzy answer set for each query
Allocate one fuzzy-set stack for each query
For each query stack in parallel:
    Scan its postfix instructions from left to right
    If the instruction is an operand, push its fuzzy set
    If the instruction is conjunction, pop two sets, compute C(x, y), and push the result
    If the instruction is disjunction, pop two sets, compute D(x, y), and push the result
    If the instruction is negation, pop one set, compute N(x), and push the result
    If the instruction is a relation projection, pop one set and record its relation
Synchronize queries currently awaiting a projection
Run the neural relation projection on that group in parallel
Push each projection result onto its query stack
Return the remaining item on every stack
The fuzzy operations require $O(|V|)$ time, whereas one neural projection requires $O(|V|d^2+|E|d)$ time. Synchronizing projection instructions therefore improves GPU utilization. If $t$ is the maximum number of relation projections in any query in the batch, the overall execution cost is $O\!\left(t(|V|d^2+|E|d)\right)$ and does not grow with the number of distinct query structures.
Knowl 7 — Benchmark and implementation configuration
experimental setup
GNN-QE is evaluated on FB15k, FB15k-237, and NELL995 using the standard first-order-logic query benchmark. The benchmark contains 14 query structures: nine existential-positive structures and five structures with negation. Training uses ten structures, $1p/2p/3p/2i/3i/2in/3in/inp/pni/pin$ , while evaluation additionally includes the four unseen structures $ip/pi/2u/up$ . Here, $p$ denotes a relation projection, $i$ a conjunction, $u$ a disjunction, and $n$ a negation.

For each query, entities reachable by symbolic traversal on the training or validation graph are treated as easy answers; answers requiring predicted links are hard answers. Hard answers are ranked against all non-answer entities, and performance is reported with mean reciprocal rank (MRR) and Hits at $K$ . The model augments every graph edge with its inverse relation, uses one shared four-layer GNN for all projections, a hidden dimension of 32, and a two-layer MLP with hidden dimension 64. It is trained with Adam at learning rate $5\times10^{-3}$ , traversal-dropout probability $0.25$ , batch size 192 on FB15k and FB15k-237 and 32 on NELL995, for 10,000 batches on the first two datasets and 30,000 on NELL995.
Knowl 8 — State-of-the-art complex-query answering performance
data/table
On the standard test benchmark, GNN-QE obtains the highest average MRR for both existential-positive queries and queries with negation across all three datasets. The test-results table on page 7 reports the following aggregate values; $\mathrm{avg}_p$ averages EPFO query types and $\mathrm{avg}_n$ averages query types with negation. Values are MRR percentages.
Could not parse LaTeX table
The full per-query results show particularly large gains on negation queries, whose answer sets can contain nearly all entities. The paper reports average relative gains of 22.3% on EPFO queries and 95.1% on negation queries relative to the previously strongest comparison model under its aggregate evaluation. The authors attribute the advantage to fuzzy entity sets' ability to represent many simultaneous assignments, which is difficult for low-dimensional geometric query embeddings.
Knowl 9 — Unsupervised answer-set cardinality prediction
empirical result
GNN-QE predicts the number of answers without an auxiliary cardinality-prediction objective. Given a final fuzzy answer vector $p\in[0,1]^V$ , it counts entities whose membership exceeds the threshold $0.5$ :
$\widehat{|A_Q|}=\sum_{v\in V}\mathbf{1}[p_v\ge 0.5],$
where $A_Q$ is the ground-truth answer set and $\mathbf{1}[\cdot]$ is the indicator function. The threshold is chosen to match the binary classification loss. On the three datasets, the mean absolute percentage errors (MAPE, in percent) are:
Could not parse LaTeX table
The prediction also preserves answer-set-size ordering. On FB15k-237, the Spearman correlation between predicted and true cardinalities is $0.940$ averaged over the reported query types, compared with $0.738$ for ConE and $0.540$ for BetaE. No explicit supervision for cardinality is used.
Knowl 10 — Intermediate-variable visualization and localized reasoning errors
empirical result
Because every intermediate GNN-QE state is a fuzzy entity vector, the model's reasoning can be inspected variable by variable. The visualization procedure ranks entities by membership probability, displays the top three easy entities and top six hard entities with probability at least $0.1$ , and separately samples a valid grounding whose final answer is hard. Easy entities are reachable by observed symbolic traversal, whereas hard entities require predicted missing links.

For the 3-hop query
$?c:\ \exists a,b:\ \mathrm{ParticipateCountry}(a,\mathrm{Greece})\land\mathrm{OlympicSports}(a,b)\land\mathrm{TeamSports}(c,b),$
GNN-QE ranked the hard intermediate assignment $a=\text{2010 Winter Olympics}$ first and the hard assignment $b=\text{ice hockey}$ first. For a sampled valid grounding, it recovered those first two hops but ranked the hard final answer $c=\text{Florida Panthers}$ at 433. This visualization distinguishes an error in the final projection from errors in earlier reasoning steps, rather than exposing only an uninterpretable final query score. The visualization examples on pages 8 and 15--25 also show that apparently incorrect predictions can reflect facts missing from the incomplete benchmark graph.
Knowl 11 — Ablation findings on dropout, data efficiency, and GNN parameterization
empirical result
Ablations on FB15k-237 show that traversal dropout is necessary for generalization to incomplete graphs. With $p=0$ , GNN-QE reaches perfect training MRR because it learns ordinary relation traversal, but validation performance is low. Validation performance is best at $p=0.25$ ; $p=1$ is also suboptimal because it removes the opportunity to exploit links that remain observed at test time.

GNN-QE is relatively data-efficient: with only 1% of the FB15k-237 training queries, corresponding to 8,233 queries, it achieves a comparable EPFO MRR and a better negation MRR than BetaE trained on the full dataset. Replacing the NBFNet-style projection with alternative GNN parameterizations gives the following test MRR values:
Could not parse LaTeX table
All GNN-QE parameterizations improve substantially over BetaE on negation queries, and the stronger NBFNet projection performs better than CompGCN, which performs better than RGCN.

Coverage note — The detailed per-query H@1 results, complete dataset-statistics tables, and additional appendix visualizations were omitted because they are redundant with the aggregate test results, cardinality analysis, and representative visualization findings included above.

References

1.Amin, S., Varanasi, S., Dunfield, K. A., and Neumann, G. Lowfer: Low-rank bilinear pooling for link prediction. In International Conference on Machine Learning, pp. 257–268. PMLR, 2020.
2.Arakelyan, E., Daza, D., Minervini, P., and Cochez, M. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021.
3.Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
4.Chen, X., Hu, Z., and Sun, Y. Fuzzy logic based logical query answering on knowledge graph. In International Conference on Machine Learning. PMLR, 2021.
5.Choudhary, N., Rao, N., Katariya, S., Subbian, K., and Reddy, C. K. Self-supervised hyperboloid representations from logical queries over knowledge graphs. In Proceedings of the Web Conference 2021, pp. 1373–1384, 2021.
6.Corso, G., Cavalleri, L., Beaini, D., Lio, P., and Velicković, P. Principal neighbourhood aggregation for graph nets. volume 33, 2020.
7.Dalvi, N. and Suciu, D. Efficient query evaluation on probabilistic databases. The VLDB Journal, 16(4):523–544, 2007.
8.Das, R., Dhuliawala, S., Zaheer, M., Vilnis, L., Durugkar, I., Krishnamurthy, A., Smola, A., and McCallum, A. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In International Conference on Learning Representations, 2018.
9.Guu, K., Miller, J., and Liang, P. Traversing knowledge graphs in vector space. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 318–327, 2015.
10.Hamilton, W., Bajaj, P., Zitnik, M., Jurafsky, D., and Leskovec, J. Embedding logical queries on knowledge graphs. Advances in Neural Information Processing Systems, 31, 2018.
11.Hildebrandt, M., Serna, J. A. Q., Ma, Y., Ringsquandl, M., Joblin, M., and Tresp, V. Reasoning on knowledge graphs with debate dynamics. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4123–4131, 2020.
12.Himmelstein, D. S., Lizee, A., Hessler, C., Brueggeman, L., Chen, S. L., Hadley, D., Green, A., Khankhanian, P., and Baranzini, S. E. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. Elife, 6: e26726, 2017.
13.Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
14.Klir, G. and Yuan, B. Fuzzy sets and fuzzy logic, volume 4. Prentice hall New Jersey, 1995.
15.Lloyd, J. W. Foundations of logic programming. Springer Science & Business Media, 2012.
16.Lukasiewicz, J. Aristotle’s syllogistic from the standpoint of modern formal logic. 1951.
17.Miller, G. A. WordNet: An electronic lexical database. MIT press, 1998.
18.Nickel, M., Murphy, K., Tresp, V., and Gabrilovich, E. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11–33, 2015.
19.Pearl, J. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier, 2014.
20.Qu, M., Chen, J., Xhonneux, L.-P., Bengio, Y., and Tang, J. Rnnlogic: Learning logic rules for reasoning on knowledge graphs. In International Conference on Learning Representations, 2021.
21.Ren, H. and Leskovec, J. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33, 2020.
22.Ren, H., Hu, W., and Leskovec, J. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2019.
23.Sadeghian, A., Armandpour, M., Ding, P., and Wang, D. Z. Drum: End-to-end differentiable rule mining on knowledge graphs. volume 32, pp. 15347–15357, 2019.
24.Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593–607. Springer, 2018.
25.Schmidt, M., Meier, M., and Lausen, G. Foundations of sparql query optimization. In Proceedings of the 13th International Conference on Database Theory, pp. 4–33, 2010.
26.Stuart, R. and Peter, N. Artificial intelligence-a modern approach 3rd ed, 2016.
27.Sun, H., Arnold, A., Bedrax Weiss, T., Pereira, F., and Cohen, W. W. Faithful embeddings for knowledge base queries. Advances in Neural Information Processing Systems, 33, 2020.
28.Sun, Z., Deng, Z.-H., Nie, J.-Y., and Tang, J. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations, 2018.
29.Szklarczyk, D., Gable, A. L., Lyon, D., Junge, A., Wyder, S., Huerta-Cepas, J., Simonovic, M., Doncheva, N. T., Morris, J. H., Bork, P., et al. String v11: protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets. Nucleic acids research, 47(D1):D607–D613, 2019.
30.Teru, K., Denis, E., and Hamilton, W. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pp. 9448–9457. PMLR, 2020.
31.Toutanova, K. and Chen, D. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pp. 57–66, 2015.
32.Trouillon, T., Welbl, J., Riedel, S., Gaussier, E., and Bouchard, G. Complex embeddings for simple link prediction. In International conference on machine learning, pp. 2071–2080. PMLR, 2016.
33.Vashishth, S., Sanyal, S., Nitin, V., and Talukdar, P. Composition-based multi-relational graph convolutional networks. In International Conference on Learning Representations, 2019.
34.Vrandecic, D. and Krötzsch, M. Wikidata: a free collaborative knowledgebase. Communications of the ACM, 57(10):78–85, 2014.
35.Xiong, W., Hoang, T., and Wang, W. Y. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017), Copenhagen, Denmark, September 2017. ACL.
36.Yang, B., Yih, W.-t., He, X., Gao, J., and Deng, L. Embedding entities and relations for learning and inference in knowledge bases. International Conference on Learning Representations, 2015.
37.Yang, F., Yang, Z., and Cohen, W. W. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems, pp. 2316–2325, 2017.
38.You, J., Gomes-Selman, J., Ying, R., and Leskovec, J. Identity-aware graph neural networks. arXiv preprint arXiv:2101.10320, 2021.
39.Zhang, D., Yuan, Z., Liu, H., Lin, X., and Xiong, H. Learning to walk with dual agents for knowledge graph reasoning. arXiv preprint arXiv:2112.12876, 2021a.
40.Zhang, Z., Wang, J., Chen, J., Ji, S., and Wu, F. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. Advances in Neural Information Processing Systems, 34, 2021b.
41.Zhu, Z., Zhang, Z., Xhonneux, L.-P., and Tang, J. Neural bellman-ford networks: A general graph neural network framework for link prediction. arXiv preprint arXiv:2106.06935, 2021.
42.Zou, L., Mo, J., Chen, L., Ozsu, M. T., and Zhao, D. gstore: answering sparql queries via subgraph matching. Proceedings of the VLDB Endowment, 4(8):482–493, 2011.

Citation

MLA

Zhu, Z., et al. “Neural-Symbolic Models for Logical Queries on Knowledge Graphs”. International Conference on Machine Learning, vol. 162, 2022, pp. 27454–78, https://proceedings.mlr.press/v162/zhu22c.html.

APA

Zhu, Z., Galkin, M., Zhang, Z., & Tang, J. (2022). Neural-Symbolic Models for Logical Queries on Knowledge Graphs. International Conference on Machine Learning, 162, 27454–27478. https://proceedings.mlr.press/v162/zhu22c.html

Chicago

Zhu, Z., M. Galkin, Z. Zhang, and J. Tang. 2022. “Neural-Symbolic Models for Logical Queries on Knowledge Graphs”. International Conference on Machine Learning 162: 27454–78. https://proceedings.mlr.press/v162/zhu22c.html.

Harvard

Zhu, Z. et al. (2022) “Neural-Symbolic Models for Logical Queries on Knowledge Graphs”, International Conference on Machine Learning. PMLR, pp. 27454–27478. Available at: https://proceedings.mlr.press/v162/zhu22c.html.

Vancouver

1. Zhu Z, Galkin M, Zhang Z, Tang J (2022) Neural-Symbolic Models for Logical Queries on Knowledge Graphs. In: International Conference on Machine Learning. PMLR, pp 27454–27478

BibTeX

@InProceedings{pmlr-v162-zhu22c,
  title = 	 {Neural-Symbolic Models for Logical Queries on Knowledge Graphs},
  author =       {Zhu, Zhaocheng and Galkin, Mikhail and Zhang, Zuobai and Tang, Jian},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {27454--27478},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/zhu22c/zhu22c.pdf},
  url = 	 {https://proceedings.mlr.press/v162/zhu22c.html},
  abstract = 	 {Answering complex first-order logic (FOL) queries on knowledge graphs is a fundamental task for multi-hop reasoning. Traditional symbolic methods traverse a complete knowledge graph to extract the answers, which provides good interpretation for each step. Recent neural methods learn geometric embeddings for complex queries. These methods can generalize to incomplete knowledge graphs, but their reasoning process is hard to interpret. In this paper, we propose Graph Neural Network Query Executor (GNN-QE), a neural-symbolic model that enjoys the advantages of both worlds. GNN-QE decomposes a complex FOL query into relation projections and logical operations over fuzzy sets, which provides interpretability for intermediate variables. To reason about the missing links, GNN-QE adapts a graph neural network from knowledge graph completion to execute the relation projections, and models the logical operations with product fuzzy logic. Experiments on 3 datasets show that GNN-QE significantly improves over previous state-of-the-art models in answering FOL queries. Meanwhile, GNN-QE can predict the number of answers without explicit supervision, and provide visualizations for intermediate variables.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Neural-Symbolic Models for Logical Queries on Knowledge Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — GNN-QE neural-symbolic query execution

Knowl 2 — Symbolic decomposition of first-order queries into fuzzy-set operations

Knowl 3 — Neural relation projection for fuzzy head sets

Knowl 4 — Product fuzzy logic for logical operators

Knowl 5 — Query training with traversal dropout

Knowl 6 — Batched postfix execution of heterogeneous query expressions

Knowl 7 — Benchmark and implementation configuration

Knowl 8 — State-of-the-art complex-query answering performance

Knowl 9 — Unsupervised answer-set cardinality prediction

Knowl 10 — Intermediate-variable visualization and localized reasoning errors

Knowl 11 — Ablation findings on dropout, data efficiency, and GNN parameterization

References

Citation

BibTeX

Access the Paper