Traversing Knowledge Graphs in Vector Space
Open accessAbstract
Path queries on a knowledge graph can be used to answer compositional questions such as "What languages are spoken by people living in Lisbon?". However, knowledge graphs often have missing facts (edges) which disrupts path queries. Recent models for knowledge base completion impute missing facts by embedding knowledge graphs in vector spaces. We show that these models can be recursively applied to answer path queries, but that they suffer from cascading errors. This motivates a new "compositional" training objective, which dramatically improves all models' ability to answer path queries, in some cases more than doubling accuracy. On a standard knowledge base completion task, we also demonstrate that compositional training acts as a novel form of structural regularization, reliably improving performance across all base models (reducing errors by up to 43%) and achieving new state-of-the-art results.
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.
Integrity signals
Registry
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.
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 Guu et al., 2015
Section 3.4 (p. 3) describes a compositional TransE query model with the traversal operator Tᵣ(xₛ) = xₛ + wᵣ, supporting the citation as an example of a prior query-embedding method. In our copy, the scoring and membership formulas are not decoded, and no readable passage specifies an L1 distance. The paper therefore does not verify the L1-specific part of the citing sentence or its claim about dist_box at α = 1. (LLM, conf=0.78)
Experimental — accuracy not yet measuredPrior work models queries as single points in the vector space.
“However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point.”
From Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings (2020) · cites this paper as Guu et al., 2015
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Incorporating Vector Space Similarity in Random Walk Inference over Knowledge Bases
Gardner, M., Talukdar, P., Krishnamurthy, J., & Mitchell, T. (2014) · Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.3115/v1/d14-1044 · Cited by 189 · see citing works
Flagged first, then by citations
Research works printed but not linked: 24
- F. Bastien, P. Lamblin, R. Pascanu, J. Bergstra, I. J. Goodfellow, A. Bergeron, N. Bouchard, and Y. Bengio. 2012. Theano: new features and speed improvements. Deep Learning and Unsupervised Feature Learning NIPS 2012 Workshop.
- J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio. 2010. Theano: a CPU and GPU math expression compiler. In Proceedings of the Python for Scientific Computing Conference (SciPy) .
- K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In International Conference on Management of Data (SIGMOD) , pages 1247-1250.
- A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems (NIPS) , pages 2787-2795.
- A. Bordes, S. Chopra, and J. Weston. 2014. Question answering with subgraph embeddings. In Empirical Methods in Natural Language Processing (EMNLP) .
- S. R. Bowman, C. Potts, and C. D. Manning. 2014. Can recursive neural tensor networks learn logical reasoning? In International Conference on Learning Representations (ICLR) .
- X. Dong, E. Gabrilovich, G. Heitz, W. Horn, N. Lao, K. Murphy, T. Strohmann, S. Sun, and W. Zhang. 2014. Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In International Conference on Knowledge Discovery and Data Mining (KDD) , pages 601-610.
- J. Duchi, E. Hazan, and Y. Singer. 2010. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COLT) .
- E. Grefenstette. 2013. Towards a formal distributional semantics: Simulating logical calculi with tensors. arXiv preprint arXiv:1304.5823 . · arXiv
- N. Lao and W. W. Cohen. 2010. Relational retrieval using a combination of path-constrained random walks. Machine learning , 81(1):53-67.
- N. Lao, T. Mitchell, and W. W. Cohen. 2011. Random walk inference and learning in a large scale knowledge base. In Empirical Methods in Natural Language Processing (EMNLP) , pages 529-539.
- B. Min, R. Grishman, L. Wan, C. Wang, and D. Gondek. 2013. Distant supervision for relation extraction with an incomplete knowledge base. In North American Association for Computational Linguistics (NAACL) , pages 777-782.
- A. Neelakantan, B. Roth, and A. McCallum. 2015. Compositional vector space models for knowledge base completion. In Association for Computational Linguistics (ACL) .
- M. Nickel, V. Tresp, and H. Kriegel. 2011. A three-way model for collective learning on multirelational data. In International Conference on Machine Learning (ICML) , pages 809-816.
- M. Nickel, X. Jiang, and V. Tresp. 2014. Reducing the rank in relational factorization models by including observable patterns. In Advances in Neural Information Processing Systems (NIPS) , pages 1179-1187.
- J. Pennington, R. Socher, and C. D. Manning. 2014. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP) .
- B. Perozzi, R. Al-Rfou, and S. Skiena. 2014. Deepwalk: Online learning of social representations. In International Conference on Knowledge Discovery and Data Mining (KDD) , pages 701-710.
- S. Riedel, L. Yao, and A. McCallum. 2013. Relation extraction with matrix factorization and universal schemas. In North American Association for Computational Linguistics (NAACL) .
- R. Socher, B. Huval, C. D. Manning, and A. Y. Ng. 2012. Semantic compositionality through recursive matrix-vector spaces. In Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL) , pages 1201-1211.
- R. Socher, D. Chen, C. D. Manning, and A. Ng. 2013. Reasoning with neural tensor networks for knowledge base completion. In Advances in Neural Information Processing Systems (NIPS) , pages 926-934.
- R. Socher, A. Karpathy, Q. V. Le, C. D. Manning, and A. Y. Ng. 2014. Grounded compositional semantics for finding and describing images with sentences. Transactions of the Association for Computational Linguistics (TACL) , 2:207-218.
- J. Turian, L. Ratinov, and Y. Bengio. 2010. Word representations: a simple and general method for semisupervised learning. In Proceedings of the 48th annual meeting of the association for computational linguistics , pages 384-394.
- J. D. Ullman. 1985. Implementation of logical query languages for databases. ACM Transactions on Database Systems (TODS) , 10(3):289-321.
- B. Yang, W. Yih, X. He, J. Gao, and L. Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575 . · arXiv
Cited by
Sorted by citations
Modeling Relational Data with Graph Convolutional Networks
Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-93417-4_38 · Cited by 5,570 · see citing works
Knowledge Graph Embedding: A Survey of Approaches and Applications
Wang, Q., Mao, Z., Wang, B., & Guo, L. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2754499 · Cited by 2,654 · see citing works
Film: Visual reasoning with a general conditioning layer
Perez, E., Strub, F., De Vries, H., Dumoulin, V., & Courville, A. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11671 · Cited by 2,490 · see citing works
Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings
Ren, H., Hu, W., & Leskovec, J. (2020) · arXiv · doi:10.48550/arxiv.2002.05969 · Cited by 135 · see citing works
Natural Language Processing for Information Extraction
Singh, S. (2018) · arXiv · doi:10.48550/arxiv.1807.02383 · Cited by 45 · see citing works
- Authors
- Guu, K., Miller, J., & Liang, P.
- Affiliations
- Stanford University (US)
- Venue
- Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing
- Published
- 2015
- Pages
- 318-327
- OpenAlex
- W2963380480
- Cited by
- 319
- References
- 1
- Citations by year
- 2026: 7 · 2025: 10 · 2024: 15 · 2023: 20 · 2022: 18 · 2021: 39 · 2020: 44 · 2019: 55 · 2018: 41 · 2017: 36 · 2016: 31 · 2015: 3
- FWCI
- 20.85
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- Locations
- Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation ((DGE-114747, 114747)
- 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 graphs, path queries, knowledge base completion, cascading errors, vector space embedding, structural regularization, compositional reasoning
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
