CoChat
Sign Up
PreprintCited by 176Advanced Graph Neural NetworksTopic ModelingSemantic Web and Ontologies

Embedding Logical Queries on Knowledge Graphs

Open access
Hamilton, William L., Bajaj, Payal, Zitnik, Marinka, Jurafsky, Dan, Leskovec, Jure·2018·arXiv
DOI 10.48550/arxiv.1806.01445arXiv 1806.01445
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1806.01445

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • When α=1, dist_box reduces to the ordinary L1 distance.

    “When α = 1 , dist box reduces to the ordinary L 1 distance, i.e. , ‖ Cen ( q ) -v ‖ 1 , which is used by the conventional TransE (Bordes et al., 2013) as well as prior query embedding methods (Guu et al., 2015; Hamilton et al., 2018).”

    From Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020) · cites this paper as Hamilton et al., 2018

    The citation to Hamilton et al. is attached to the assertion that prior query-embedding methods used ordinary L1 distance, not to the citing paper’s α=1 calculation. In §4, p. 5, Hamilton et al. explicitly state that their method uses cosine distance instead. Their paper does not define dist_box or α. (LLM, conf=0.88)

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured

  • The L1 distance is used as the distance between query and entity vectors in GQE.

    “The L 1 distance is used as the distance between query and entity vectors.”

    From Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020) · cites this paper as Hamilton et al., 2018

    Section 4 (p. 4) says GQE scores a query–node pair using the distance between their embeddings. Its footnote in Section 4 (p. 5) specifies cosine distance, not L1 distance. (LLM, conf=0.90)

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured

  • GQE embeds a query to a single vector and models projection and intersection operators as translation and deep sets, respectively.

    “GQE embeds a query to a single vector, and models projection and intersection operators as translation and deep sets (Zaheer et al., 2017), respectively.”

    From Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020) · cites this paper as Hamilton et al., 2018

    Section 4 (pp. 5–6) says GQE generates a single query embedding and implements intersection with a permutation-invariant neural network operating on sets. But its base projection operator uses a trainable matrix (p. 5); translation is a TransE variant described in Section 4.3 (p. 7), not the general GQE projection operator. (LLM, conf=0.90)

    Experimental — accuracy not yet measured

  • Prior work can only handle queries that use conjunctions and existential quantifiers.

    “Furthermore, prior work can only handle queries that use conjunctions ( ∧ ) and existential quantifiers ( ∃ ).”

    From Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020) · cites this paper as Hamilton et al., 2018

  • Our DNF-query rewriting scheme is general and is able to extend any method that works for conjunctive queries to handle more general class of EPFO queries.

    “Note that our DNF-query rewriting scheme is general and is able to extend any method that works for conjunctive queries ( e.g. , (Hamilton et al., 2018)) to handle more general class of EPFO queries.”

    From Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020) · cites this paper as Hamilton et al., 2018

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

Cited by 176

Research works printed but not linked: 40

  1. [2][2] M. Ashburner, C. Ball, J. Blake, D. Botstein, H. Butler, J. Cherry, A. Davis, K. Dolinski, S. Dwight, J. Eppig, et al. Gene Ontology: tool for the unification of biology. Nature Genetics , 25(1):25, 2000. -
  2. [3][3] S. Bach, M. Broecheler, B. Huang, and L. Getoor. Hinge-loss Markov random fields and probabilistic soft logic. JMRL , 18(109):1-67, 2017. -
  3. [4][4] J. Berant, A. Chou, R. Frostig, and P. Liang. Semantic parsing on freebase from question-answer pairs. In EMNLP , 2013. -
  4. [5][5] A. Bordes, S. Chopra, and J. Weston. Question answering with subgraph embeddings. In EMNLP , 2014. -
  5. [6][6] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS , 2013. -
  6. [7][7] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond Euclidean data. IEEE Signal Processing Magazine , 34(4):18-42, 2017. -
  7. [9][9] R. Cavallo and M. Pittarelli. The theory of probabilistic databases. In VLDB , 1987. -
  8. [11][11] W. Cohen. Tensorlog: A differentiable deductive database. arXiv:1605.06523 , 2016. - · arXiv
  9. [12][12] N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. In VLDB , 2007. -
  10. [13][13] R. Das, S. Dhuliawala, M. Zaheer, L. Vilnis, I. Durugkar, A. Krishnamurthy, A. Smola, and A. McCallum. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. ICLR , 2018. -
  11. [14][14] R. Das, A. Neelakantan, D. Belanger, and A. McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In EACL , 2016. -
  12. [15][15] T. Demeester, T. Rocktäschel, and S. Riedel. Lifted rule injection for relation embeddings. In EMNLP , 2016. -
  13. [16][16] L. Getoor and B. Taskar. Introduction to Statistical Relational Learning . MIT press, 2007. -
  14. [17][17] J. Gilmer, S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. ICML , 2017. -
  15. [18][18] K. Guu, J. Miller, and P. Liang. Traversing knowledge graphs in vector space. EMNLP , 2015. -
  16. [19][19] W. Hamilton, R. Ying, and J. Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin , 2017. -
  17. [20][20] Z. Hu, X. Ma, Z. Liu, E. Hovy, and E. Xing. Harnessing deep neural networks with logic rules. In ACL , 2016. -
  18. [22][22] A. Kahn. Topological sorting of large networks. Communications of the ACM , 5(11):558-562, 1962. -
  19. [23][23] D. Krompaß, M. Nickel, and V. Tresp. Querying factorized probabilistic triple databases. In International Semantic Web Conference , pages 114-129, Cham, 2014. -
  20. [25][25] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. J. Assoc. Inform. Sci. and Technol. , 58(7):1019-1031, 2007. -
  21. [26][26] J. Menche et al. Uncovering disease-disease relationships through the incomplete interactome. Science , 347(6224):1257601, 2015. -
  22. [27][27] A. Neelakantan, B. Roth, and A. McCallum. Compositional vector space models for knowledge base inference. In AAAI , 2015. -
  23. [28][28] M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich. A review of relational machine learning for knowledge graphs. Proc. IEEE , 104(1):11-33, 2016. -
  24. [29][29] M. Nickel, V. Tresp, and H. Kriegel. A three-way model for collective learning on multirelational data. In ICML , 2011. -
  25. [30][30] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop , 2017. -
  26. [32][32] C. Qi, H. Su, K. Mo, and L. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In CVPR , 2017. -
  27. [33][33] G. Ramanathan. Towards a model theory for distributed representations. In AAAI Spring Symposium Series , 2015. -
  28. [34][34] T. Rocktäschel. Combining representation learning with logic for language processing. arXiv:1712.09687 , 2017. - · arXiv
  29. [35][35] T. Rocktäschel, M. Bošnjak, S. Singh, and S. Riedel. Low-dimensional embeddings of logic. In ACL Semantic Parsing , pages 45-49, 2014. -
  30. [36][36] T. Rocktäschel and S. Riedel. End-to-end differentiable proving. In NIPS , 2017. -
  31. [37][37] T. Rocktäschel, S. Singh, and S. Riedel. Injecting logical background knowledge into embeddings for relation extraction. In NAACL HLT , pages 1119-1129, 2015. -
  32. [38][38] T. Rolland et al. A proteome-scale map of the human interactome network. Cell , 159(5):12121226, 2014. -
  33. [41][41] N. Tatonetti et al. Data-driven prediction of drug effects and interactions. Science Translational Medicine , 4(125):12531, 2012. -
  34. [42][42] K. Thulasiraman and Madisetti N. Swamy. Graphs: theory and algorithms . John Wiley & Sons, 2011. -
  35. [43][43] M. Wang, Y. Tang, J. Wang, and J. Deng. Premise selection for theorem proving by deep graph embedding. In NIPS , 2017. -
  36. [44][44] L. Wu, A. Fisch, S. Chopra, K. Adams, A. Bordes, and J. Weston. Starspace: Embed all the things! In AAAI , 2017. -
  37. [45][45] Bi. Yang, W. Yih, X. He, J. Gao, and L. Deng. Embedding entities and relations for learning and inference in knowledge bases. ICLR , 2015. -
  38. [46][46] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R> Salakhutdinov, and A. J. Smola. Deep sets. In NIPS , 2017. -
  39. [47][47] Y. Zhang, H. Dai, Z. Kozareva, A. Smola, and L. Song. Variational reasoning for question answering with knowledge graph. AAAI , 2018. -
  40. [48][48] T. Zhou, J. Ren, M. Medo, and Y. Zhang. Bipartite network projection and personal recommendation. Phys. Rev. E , 76(4):046115, 2007. -

Authors
Hamilton, W. L., Bajaj, P., Zitnik, M., Jurafsky, D., & Leskovec, J.
Affiliations
Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2018
Volume
31
Pages
2026-2037
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1806.01445
arXiv
1806.01445
OpenAlex
W2890273554
Cited by
176
References
0
Citations by year
2025: 17 · 2024: 16 · 2023: 26 · 2022: 22 · 2021: 45 · 2020: 28 · 2019: 21 · 2018: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • neural information processing systems
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Semantic Web and Ontologies
Keywords
knowledge graph embedding, conjunctive queries, incomplete knowledge graphs, first-order logic, geometric operations, query answering, social interaction networks, low-dimensional embedding

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review