Knowledge Graph Navigator

Essential Knowledge Graph Papers (Annotated)

The papers below are grouped by theme, and each annotation says what the work contributed and whether later work has replaced it. Every entry has been checked for authors, venue and year. Older papers are included where they define a problem or record something for the first time, which is a different reason from being current, and each annotation says which applies.

Definitions and foundations

Tim Berners-Lee, James Hendler and Ora Lassila, “The Semantic Web,” Scientific American (2001). The article that put machine-readable meaning on the web in front of a general audience, using a scenario of agents booking medical appointments by reading structured data. That scenario didn’t happen as described, which is part of why the paper is worth reading: it shows what the standards were designed to enable and explains design choices in RDF and OWL that look strange without that motivation. https://www.scientificamerican.com/article/the-semantic-web/. See /concepts/semantic-web/.

Tim Berners-Lee, “Linked Data,” W3C Design Issues note (2006). Four rules in a short note: use URIs as names for things, make them HTTP URIs so they can be looked up, return useful information when someone looks one up, and include links to other URIs. Almost every subsequent argument about identifiers in knowledge graphs traces back to this page. https://www.w3.org/DesignIssues/LinkedData.html

Christian Bizer, Tom Heath and Tim Berners-Lee, “Linked Data: The Story So Far,” International Journal on Semantic Web and Information Systems (2009). The consolidating survey of the linked open data movement at its peak. Its census of the data cloud is now historical; its account of publishing patterns is the standard citation. See /concepts/linked-data/.

Lisa Ehrlinger and Wolfram Wöß, “Towards a Definition of Knowledge Graphs,” SEMANTiCS (2016). A short paper that collects the definitions in circulation, shows how far apart they are, and proposes one. Useful because it documents the disagreement rather than pretending it away, and it is the paper to cite when a project needs to fix what it means by the term. https://ceur-ws.org/Vol-1695/paper4.pdf

Aidan Hogan et al., “Knowledge Graphs,” ACM Computing Surveys (2021). The comprehensive survey and the current default reference. It covers graph data models, schema, identity, context, deductive and inductive knowledge, embeddings, quality, refinement, and publication, and treats RDF and labeled property graph (LPG) approaches on equal terms. Also published as a book, free at kgbook.org. https://arxiv.org/abs/2003.02320

Aidan Hogan, “Knowledge Graphs: A Guided Tour,” invited paper, OASIcs (2022). A condensed tour of the same material by one of the survey’s authors, for readers who want the shape of the field in one sitting. A good starting point before the longer work. https://aidanhogan.com/docs/kg-tour.pdf

Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen and Philip S. Yu, “A Survey on Knowledge Graphs: Representation, Acquisition and Applications,” IEEE Transactions on Neural Networks and Learning Systems (2022). A machine-learning-oriented complement to Hogan et al.: heavier on representation learning and knowledge acquisition, lighter on standards and data models. https://arxiv.org/abs/2002.00388

The public knowledge graphs

Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak and Zachary Ives, “DBpedia: A Nucleus for a Web of Open Data,” ISWC (2007). The paper that established the pattern of extracting structured data from Wikipedia infoboxes and publishing it as RDF, giving the linked data cloud a hub to link into. Superseded as a system description by the 2015 journal paper below, but this is the origin. https://link.springer.com/chapter/10.1007/978-3-540-76298-0_52

Jens Lehmann et al., “DBpedia: A Large-scale, Multilingual Knowledge Base Extracted from Wikipedia,” Semantic Web Journal (2015). The current reference describes DBpedia: the extraction framework, the ontology, the multilingual chapters, and the release process. Cite this one rather than the 2007 paper for how DBpedia works. DOI: https://doi.org/10.3233/SW-140134. See /ecosystems/dbpedia/.

Fabian M. Suchanek, Gjergji Kasneci and Gerhard Weikum, “YAGO: A Core of Semantic Knowledge,” WWW (2007). Published the same year as the DBpedia paper and solving a different half of the problem: combining Wikipedia’s facts with WordNet’s taxonomy to get a clean type hierarchy rather than a flat pile of assertions. This line of work also showed that a graph needs a coherent taxonomy as well as facts. https://suchanek.name/work/publications/www2007.pdf

Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge and Jamie Taylor, “Freebase: A Collaboratively Created Graph Database for Structuring Human Knowledge,” SIGMOD (2008). The system paper for Freebase, which Google acquired and later shut down, migrating data toward Wikidata. History now, but the primary source on a design that influenced what followed, including the machine identifier (MID) scheme still visible in Google’s Knowledge Graph Search API. https://research.google/pubs/freebase-a-collaboratively-created-graph-database-for-structuring-human-knowledge/. See /ecosystems/google-knowledge-graph-search-api/.

Google, “Introducing the Knowledge Graph: things, not strings” (2012). Not a paper, but the primary source for the phrase that defined how the industry talks about entities, and the announcement that made knowledge graphs a mainstream concern. Anyone quoting “things, not strings” should quote it from here. https://blog.google/products/search/introducing-knowledge-graph-things-not/. See /ecosystems/google-knowledge-graph/.

Denny Vrandečić and Markus Krötzsch, “Wikidata: A Free Collaborative Knowledgebase,” Communications of the ACM (2014). The authoritative description of Wikidata’s data model by its designers: items and properties, statements with qualifiers and references, and the decision to model claims with provenance rather than assert bare facts. That decision is why Wikidata can host contested and time-dependent data, and it is worth copying in any graph that has to record who said what. https://dl.acm.org/doi/10.1145/2629489. See /ecosystems/wikidata/.

Xin Luna Dong et al., “Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion,” KDD (2014). A Google research system that fused extraction from web text with prior knowledge from an existing graph, attaching calibrated probabilities to candidate facts. Knowledge Vault was a research project, not a shipped product, and should not be described as Google’s Knowledge Graph. The standard reference for probabilistic graph population at scale. https://research.google/pubs/knowledge-vault-a-web-scale-approach-to-probabilistic-knowledge-fusion/

Graph data models

Renzo Angles and Claudio Gutierrez, “Survey of Graph Database Models,” ACM Computing Surveys (2008). A systematic history of graph data models from the 1980s onward, showing that most modern designs rediscover earlier ones. It predates the current generation of graph databases, so read it for the model taxonomy rather than product guidance. https://dl.acm.org/doi/10.1145/1322432.1322433. See /concepts/property-graph-vs-rdf/ and /build/graph-databases/.

Embeddings and relational machine learning

Maximilian Nickel, Volker Tresp and Hans-Peter Kriegel, “A Three-Way Model for Collective Learning on Multi-Relational Data,” ICML (2011). RESCAL is the tensor factorization model that framed link prediction over multi-relational data as a factorization problem. Later models beat it on benchmarks, so it is not a method to reach for now, but it defined the task setup that everything after it uses. https://icml.cc/2011/papers/438_icmlpaper.pdf

Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston and Oksana Yakhnenko, “Translating Embeddings for Modeling Multi-relational Data,” NIPS (2013). TransE, which models a relation as a translation in embedding space so that the head vector plus the relation vector approximates the tail vector. Simple, fast, and the reason a large family of successor models carries the same prefix. Its known difficulty with one-to-many and symmetric relations is what those successors were built to fix, so read it first. https://papers.nips.cc/paper/5071-translating-embeddings-for-modeling-multi-relational-data. See /concepts/knowledge-graph-embeddings/.

Maximilian Nickel, Kevin Murphy, Volker Tresp and Evgeniy Gabrilovich, “A Review of Relational Machine Learning for Knowledge Graphs,” Proceedings of the IEEE (2016). The review organized latent-feature and graph-feature models into one framework and connected them to graph construction rather than treating link prediction as a standalone benchmark exercise. Predates graph neural network approaches, which later surveys cover. https://arxiv.org/abs/1503.00759

Quan Wang, Zhendong Mao, Bin Wang and Li Guo, “Knowledge Graph Embedding: A Survey of Approaches and Applications,” IEEE Transactions on Knowledge and Data Engineering (2017). A taxonomy of embedding models organized by scoring function. Superseded in model coverage by the 2021 surveys, still the clearest explanation of how the scoring functions relate to one another.

Knowledge graphs and language models

Fabio Petroni, Tim Rocktäschel, Sebastian Riedel et al., “Language Models as Knowledge Bases?” EMNLP (2019). Probed pretrained language models with fill-in-the-blank templates to see how much relational knowledge they store without fine-tuning, and introduced the LAMA benchmark. The finding that models recover a fair amount of it, unreliably and without provenance, framed the argument for grounding models in explicit graphs. https://aclanthology.org/D19-1250/

Patrick Lewis et al., “Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks,” NeurIPS (2020). The paper that named RAG and demonstrated combining a parametric model with a non-parametric retrieval index. It describes dense passage retrieval rather than graph retrieval, which is the baseline that graph-based approaches are measured against. https://arxiv.org/abs/2005.11401

Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang and Xindong Wu, “Unifying Large Language Models and Knowledge Graphs: A Roadmap,” arXiv (2023). A survey of how graphs and language models combine: graphs enhancing models, models building and completing graphs, and architectures using both. A map of the design space rather than a source of results. https://arxiv.org/abs/2306.08302

Darren Edge et al., “From Local to Global: A Graph RAG Approach to Query-Focused Summarization,” Microsoft Research, arXiv (2024). The report behind Microsoft’s GraphRAG. It builds an entity graph from source documents with a language model, detects communities in that graph, summarizes each one, and answers global questions by aggregating those summaries, which is the class of questions that chunk-retrieval RAG handles badly. The starting point for judging whether a graph layer earns its cost on a given corpus. https://arxiv.org/abs/2404.16130. See /build/graphrag/ and /seo/knowledge-graphs-ai-search-and-llms/.

Related pages

FAQ

Which knowledge graph survey should I read first?

Knowledge Graphs by Aidan Hogan and colleagues, published in ACM Computing Surveys in 2021, is the broadest and most balanced single source, and a free book edition is available at kgbook.org. For a shorter version, readers can read the same author’s Knowledge Graphs: A Guided Tour. For a machine-learning emphasis instead, use the survey by Ji and colleagues.

What is the original knowledge graph paper?

There is no single origin paper, because the term predates its current meaning and Google popularized it in a 2012 blog post rather than a publication. The nearest primary sources are that announcement, the DBpedia and YAGO papers from 2007 that established large-scale extraction from Wikipedia, and the Freebase paper from 2008.

Where can I read the original Semantic Web article?

The article by Tim Berners-Lee, James Hendler, and Olli Lassila appeared in Scientific American in 2001 and is on the magazine’s site. Pair it with Berners-Lee’s 2006 Linked Data design issues note, which states the four rules for publishing data on the web that the rest of the linked data literature builds on.

Which papers cover knowledge graphs with large language models?

Start with Pan and colleagues’ 2023 roadmap for the design space, then the Microsoft Research GraphRAG report from 2024 for a concrete system and its evaluation. The Lewis and colleagues RAG paper from 2020 gives the retrieval baseline those approaches are compared against, and Petroni and colleagues from 2019 explains why grounding is needed at all.

Sources and further reading

Powered by CookieAdmin