🧶 Knowledge graph

About 15 minutes to read · every paper named here has its own page in this library

What it is

A knowledge graph (KG) writes facts as small statements that a machine can read. Each statement has three parts: a subject, a predicate and an object. Together they form a triple. Consider three facts about one scientist:

• (Marie Curie, born in, Warsaw)
• (Warsaw, capital of, Poland)
• (Marie Curie, awarded, Nobel Prize in Physics)

Each subject and object becomes a node, and each predicate becomes a directed, labelled edge. "Warsaw" is the same node in the first two triples, so the facts link up. A program can then follow the path from Marie Curie to Warsaw to Poland. It can therefore answer "In which country was Marie Curie born?" even though no single triple states it. Adding a fact means adding an edge, and a question becomes a walk or a pattern match over the graph.

The survey "Knowledge Graphs" by Hogan and colleagues, published in ACM Computing Surveys in 2021, takes a deliberately broad view. It treats a KG as a data graph built to gather and convey real-world knowledge, with nodes for entities and edges for relations (Hogan et al. 2020).

A narrower working description comes from a survey of graph refinement. In that view a knowledge graph:

• is mainly about instances rather than abstract classes;
• is backed by a schema;
• covers many domains;
• allows arbitrary links between entities (Paulheim 2017).

By that test, resources without instances, lexicons of common nouns and single-domain gazetteers are left out (Paulheim 2017).

Knowledge graphs belong to the long tradition of knowledge representation and reasoning, which goes back to the semantic networks of Quillian (1968). In language technology they matter for three reasons:

• They are a target of information extraction.
• They are a source of answers in question answering.
• They are a store of facts that can complement large language models.

The papers on the subject are gathered under Knowledge graphs & ontologies.

How it works

Data models

Two data models dominate. The first is the directed edge-labelled graph, standardised on the web as RDF (Resource Description Framework). In RDF every edge label is an IRI, the internationalised successor of the URI. Most nodes are IRIs too, but a node can also be a literal value, such as a date or a number, or a blank node with no global name. Every fact is a triple, and graphs are queried with SPARQL.

The second is the property graph. Here nodes and edges can carry their own key–value attributes. A "married to" edge can therefore hold a start date directly instead of needing extra nodes.

The survey by Hogan and colleagues compares these models and their query languages. It also treats the questions they raise about schema, identity and context: which node is "the same" entity, and in what time or source a fact holds (Hogan et al. 2020).

Schemas and ontologies

A schema says which kinds of things exist and how they may be related. For example, "born in" links a Person to a Place, and every City is a Place. Richer schemas are ontologies, written in logic-based languages such as RDFS and OWL. They support deduction: a reasoner can infer new facts from rules and class hierarchies (Hogan et al. 2020). Designing such schemas is the craft of ontology engineering.

DBpedia shows how a shared ontology works in practice. Volunteers map Wikipedia infobox templates in many languages onto one common ontology, so that types and properties stay consistent across editions. That ontology has 320 classes and 1,650 properties (Lehmann et al. 2015).

YAGO3 instead attaches every entity to the WordNet taxonomy (Mahdisoltani et al. 2015). Later YAGO releases moved away from WordNet. YAGO 4.5 builds its rich taxonomy from schema.org and Wikidata classes and stresses clean data (Suchanek et al. 2023).

Deductive and inductive knowledge

Hogan and colleagues separate two ways of getting more out of a graph. Deductive methods apply ontologies and rules. Inductive methods learn patterns from the data, through graph analytics, embeddings and graph neural networks (Hogan et al. 2020). The completion methods described under Methods below belong to the inductive family. They learn vectors for nodes and edges and use them to guess missing triples.

Open and enterprise graphs

The open graphs most often studied are DBpedia, Freebase, Wikidata and YAGO. Alongside them sit domain graphs for geography, government, media, tourism and the life sciences (Hogan et al. 2020). Wikidata was built as a free, collaboratively edited knowledge base (Vrandečić & Krötzsch 2014). ConceptNet is an open multilingual graph of general, commonsense knowledge (Speer et al. 2016). Its terms are free-form phrases rather than identifiers drawn from a closed list (Li et al. 2016).

Enterprise knowledge graphs are kept by companies for their own use. They serve web search (Bing, Google), commerce, social networks and finance (Hogan et al. 2020). Domain graphs can be large and specialised. PrimeKG, for precision medicine, merges 20 curated resources into 129,375 nodes and 4,050,249 relationships (Chandak et al. 2023).

History

The phrase "knowledge graph" is older than the current field. Its use dates back to at least 1972, but its present meaning comes from Google's announcement of its Knowledge Graph in 2012. After that, Airbnb, Amazon, eBay, Facebook, IBM, LinkedIn, Microsoft and Uber described graphs of their own (Hogan et al. 2020).

The ideas behind it were older still. Three earlier efforts had each tried to make knowledge explicit and machine-readable:

• semantic networks (Quillian, 1968);
• the Cyc project (Lenat, 1984);
• the Semantic Web programme (Berners-Lee and colleagues, 2001).

The open graphs of the 2000s took Wikipedia as their raw material. DBpedia has been developed since 2006 and became a central hub of the Linked Open Data cloud. It holds 27 million RDF links to more than 30 outside sources (Lehmann et al. 2015). YAGO3 later combined ten language editions into a single resource. As a result, facts too local for English Wikipedia were no longer lost (Mahdisoltani et al. 2015).

Around 2013 the field moved towards machine learning. Translating embeddings (TransE) recast relations as vector offsets (Bordes et al. 2013). In the same year, neural tensor networks addressed knowledge base completion (Socher et al. 2013). Semantic parsers were also trained against Freebase from question–answer pairs alone (Berant et al. 2013).

Over the next six years came a long line of embedding models:

• DistMult (Yang et al. 2014);
• TransD (Ji et al. 2015);
• ComplEx (Trouillon et al. 2016);
• ConvE (Dettmers et al. 2017);
• RotatE (Sun et al. 2019);
• TuckER (Balažević et al. 2019).

From 2019 the question changed again. Researchers asked three things:

• whether pretrained language models already contain a KG's facts (Petroni et al. 2019);
• whether such models can write new graph entries (Bosselut et al. 2019);
• how the two technologies should be combined (Pan et al. 2023).

Methods

Building a graph from text

Much factual knowledge exists only as text, so building graphs is largely a task for the methods covered in papers on information extraction. A classic pipeline runs four steps in turn:

1. named entity recognition;
2. coreference resolution;
3. entity linking;
4. relation extraction.

Each step needs supervised data and a fixed schema, and errors pass down the chain (Petroni et al. 2019).

Entity linking maps a mention to its node, or to NIL when the graph has no entry. One influential system works in two stages. It first selects candidates with title, acronym, alias and string-similarity matches. It then ranks them with a supervised model that treats NIL as one more candidate. The system reaches roughly 80% accuracy on TAC-KBP 2009 (Dredze et al. 2010).

Relation extraction is often trained by distant supervision. Text is aligned with a graph, and sentences mentioning a linked pair are taken as evidence for the relation. This assumes the graph is complete, which it is not: in Freebase, 93.8% of PERSON entities had no recorded place of birth. Treating unlisted pairs as positive-and-unlabelled rather than negative gives better extractors (Min et al. 2013).

Joint models replace the pipeline. A sequence-to-sequence network with a copy mechanism can emit a relation and copy its two entities from the sentence. An entity can be copied more than once, so triples that share entities are handled (Zeng et al. 2018). For scientific text, a multi-task span model learns entities, relations and coreference together, and the coreference links make the resulting graph denser (Luan et al. 2018).

Graphs in different languages often describe the same entities. Graph convolutional networks can align them from a seed set of matched pairs (Wang et al. 2018). YAGO3 instead maps foreign infobox attributes with a statistical test against the English data (Mahdisoltani et al. 2015).

A different route generates entries rather than extracting them. COMET fine-tunes a pretrained transformer on seed tuples, then writes object phrases for new subject–relation pairs. Human judges rated its single top-ranked output correct in 77.5% of cases on ATOMIC and 91.7% on ConceptNet (Bosselut et al. 2019).

Embeddings and link prediction

KG embeddings place each entity and relation in a vector space and score candidate triples with a simple function. The task is link prediction: rank all possible tails for a head and a relation, and hope the true one comes near the top. TransE gives the founding intuition (Bordes et al. 2013):

h + r ≈ t
f(h, r, t) = ‖h + r − t‖

Here h is the vector of the head entity, r the vector of the relation and t the vector of the tail entity, all of the same dimension. The symbol ‖·‖ is a vector norm, usually L1 or L2. A true triple should have a small distance f, so the relation acts as a translation that carries the head onto the tail. Training pushes f down for observed triples and up for corrupted ones, in which the head or tail is swapped at random.

One later model scores a triple as b − ½‖h + r − t‖². The constant bias b is added for numerical stability, and the scores are normalised with a softmax to give probabilities of heads, tails and relations (Wang et al. 2014).

Later models change the scoring function:

DistMult:  f(h, r, t) = Σᵢ hᵢ · rᵢ · tᵢ

In this formula i runs over the embedding dimensions, and hᵢ, rᵢ and tᵢ are the i-th components of the three vectors. The relation is thus a diagonal matrix, and the score is higher for more plausible triples.

A unifying analysis showed that many neural models are special cases of linear or bilinear transformations of entity vectors. Within that framework, this simple diagonal model beat TransE at Freebase link prediction. It placed the correct entity among its top ten candidates (Hits@10) in 73.2% of test cases, against 54.7% for TransE (Yang et al. 2014).

The neural tensor network gives each relation a bilinear tensor layer. It represents an entity as the average of the word vectors in its name, and starts those vectors from unsupervised pretraining. When classifying unseen triples, it reached 86.2% accuracy on WordNet and 90.0% on Freebase (Socher et al. 2013).

Paths carry signal beyond single edges. A recurrent network that composes relation vectors along a path can generalise to paths unseen in training, and even to new relations (Neelakantan et al. 2015). Hyperbolic models fit tree-like parts of a graph in few dimensions. Their gains are largest on hierarchical WordNet relations (Chami et al. 2020).

Combining graphs with text

Text helps fill gaps in several ways:

• Joint embedding of Freebase entities and corpus words lets a model score facts whose arguments are missing from the graph (Wang et al. 2014).
• Adding textual relations, written as dependency paths from web sentences, improves completion (Toutanova & Chen 2015).
• Composing those paths with a convolutional network helps further (Toutanova et al. 2015).
• Commonsense graphs have free-phrase terms. Scorers built on word embeddings can rate their tuples even when the terms never appeared in training (Li et al. 2016).

Uses: search, question answering, dialogue and generation

The most visible use is web search, where both Google and Bing rely on knowledge graphs (Hogan et al. 2020).

In the work collected under papers on question answering, a question is mapped to a query and executed against the knowledge base. This is a form of semantic parsing. The weakly supervised Freebase parser noted under History is an early example (Berant et al. 2013). Later systems took several routes:

• Staged query-graph generation finds the topic entity first, then a chain of relations, then constraints. It reached an F1 of 52.5% on WebQuestions (Yih et al. 2015).
• Some systems paired relation extraction with checks against Wikipedia text (Xu et al. 2016).
• Others ranked candidate SPARQL queries, resolving entities and relations jointly (Bast & Haussmann 2015).
• Questions with several constraints led to multi-constraint query graphs (Bao et al. 2016).
• When the graph lacks a needed link, embeddings can stand in for it and allow multi-hop answers on sparse graphs (Saxena et al. 2020).

Graphs also ground dialogue systems. Mem2Seq copies objects of stored triples into task-oriented replies (Madotto et al. 2018). DialKG Walker picks the next entity in open conversation by learning walks over the graph, and each choice comes with an explicit path (Moon et al. 2019).

In natural language generation, a graph transformer writes multi-sentence abstracts from graphs extracted from scientific text (Koncel-Kedziorski et al. 2019).

Lexical graphs feed other tasks too. In word sense disambiguation, spreading classifier scores along WordNet edges lifted results past 80 F1 on the combined English all-words benchmark (Bevilacqua & Navigli 2020).

Knowledge graphs and language models

Probing showed that BERT-large, with no fine-tuning, can fill masked facts drawn from Wikidata and ConceptNet. On open-domain questions it reached 57.1% precision@10, against 63.5% for a graph built with a supervised relation extractor. Many-to-many relations stayed hard for every model (Petroni et al. 2019).

Facts also go stale. A year-conditioned T5 trained on dated news remembers time-dependent facts better and can be updated cheaply (Dhingra et al. 2022).

Knowledge can also flow the other way, from graph to model:

• K-BERT inserts graph triples into input sentences at fine-tuning time. A visibility mask stops the added triples from distorting the sentence, and the gains are largest on domain tasks (Liu et al. 2019).
• Another approach turns the whole English Wikidata into synthetic sentences, the KELM corpus of about 18 million sentences. These are added to a retrieval corpus (Agarwal et al. 2021), which links graphs to retrieval-augmented generation.

A survey groups the field into three frameworks (Pan et al. 2023):

• graph-enhanced language models;
• language-model-augmented graphs;
• synergised systems in which both reason together.

Datasets and benchmarks

Link prediction was long measured on FB15k and WN18. On these sets, a simple model that looks only at direct links between two entities beat embedding models, because the data contain near-duplicate and inverse relations. The filtered FB15k-237 was introduced in response (Toutanova & Chen 2015), and WN18RR came with the ConvE work (Dettmers et al. 2017).

The two are now the standard harder pair:

• WN18RR has 40,943 entities and 11 relations.
• FB15k-237 has 14,541 entities and 237 relations (Nguyen et al. 2018).

Results are reported as mean rank, mean reciprocal rank (MRR) and Hits@k under a filtered protocol (Nguyen et al. 2018). On WN18RR, TuckER reported an MRR of 0.470 (Balažević et al. 2019). RotH reached an MRR of 0.496 with embeddings of up to 500 dimensions (Chami et al. 2020).

A recurring lesson is that well-tuned old baselines are strong. TransE was omitted from the ConvE comparison, yet it beats ConvE on some WN18RR measures (Nguyen et al. 2018).

For question answering over Freebase, the main benchmarks are these:

• Free917, built by Cai and Yates and used by Berant and colleagues, and WebQuestions, which Berant and colleagues introduced (Berant et al. 2013).
• WebQuestionsSP, which adds SPARQL parses for 4,737 questions (Yih et al. 2016).
• ComplexQuestions, with 2,100 multi-constraint pairs (Bao et al. 2016).
• ComplexWebQuestions, with 34,689 compositional question–answer pairs (Talmor & Berant 2018).

Annotating full parses for WebQuestionsSP took no longer than finding the answers by hand, and training on the parses raised F1 (Yih et al. 2016).

For extraction and probing, several resources are in use:

• T-REx aligns about 11 million Wikidata triples with 3.09 million Wikipedia abstracts. Its best alignment method was 97.8% precise on the triples that were checked (Elsahar et al. 2018).
• LAMA tests factual recall in language models (Petroni et al. 2019).
• TempLAMA adds 50,310 queries whose answers depend on the year (Dhingra et al. 2022).
• SciERC annotates 500 AI abstracts for entities, relations and coreference (Luan et al. 2018).

Cross-lingual alignment is tested on DBP15K (Wang et al. 2018). Graph-grounded dialogue is tested on OpenDialKG's 15K conversations (Moon et al. 2019). Broader questions of measurement are collected under evaluation and benchmarks.

People and institutions

Danqi Chen, now at Princeton University, co-authored the neural tensor network for completion (Socher et al. 2013). She also co-authored two studies on combining graphs with text (Toutanova & Chen 2015; Toutanova et al. 2015). Christopher D. Manning of Stanford University was also an author of the tensor network paper (Socher et al. 2013).

Question answering over Freebase was shaped largely by groups at Stanford University and Microsoft Research.

• At Stanford, Jonathan Berant, now at Tel Aviv University, and Percy Liang built the weakly supervised parser and the WebQuestions data (Berant et al. 2013). Berant later worked on decomposing complex questions over the web (Talmor & Berant 2018).
• At Microsoft Research, Wen-tau Yih, now at Meta, and Jianfeng Gao co-authored DistMult (Yang et al. 2014) and staged query-graph parsing (Yih et al. 2015). Yih also led the WebQuestionsSP annotation (Yih et al. 2016).

At Tsinghua University, Zhiyuan Liu and Maosong Sun co-authored path-based embeddings (Lin et al. 2015). Yejin Choi, now at Stanford University, co-authored the COMET line on commonsense graphs (Bosselut et al. 2019; Hwang et al. 2020). Hannaneh Hajishirzi, of the University of Washington and the Allen Institute for Artificial Intelligence, co-authored work on scientific graph construction (Luan et al. 2018) and on generation from graphs (Koncel-Kedziorski et al. 2019).

Christian Bizer of the University of Mannheim, together with Pablo N. Mendes and Max Jakob, was among the authors behind DBpedia (Lehmann et al. 2015).

Fabio Petroni and Sebastian Riedel asked whether language models are knowledge bases (Petroni et al. 2019). At the time they were at Facebook AI Research, with Riedel also at University College London. Riedel also co-authored ComplEx (Trouillon et al. 2016) and ConvE (Dettmers et al. 2017). William Cohen of Google co-authored the work on time-aware language models (Dhingra et al. 2022).

Several institutions are frequent homes of authors in the area:

• Carnegie Mellon University;
• Stanford University;
• the University of Washington;
• Google;
• Tsinghua University;
• the Chinese Academy of Sciences.

Open questions

Completeness and correctness pull against each other. No large web graph can be both fully complete and fully correct, and no refinement method surveyed improves both at once. Evaluation is also narrow: many studies test on DBpedia alone and rarely report runtime (Paulheim 2017).

Quality also differs between graphs. A comparison of DBpedia, Freebase, OpenCyc, Wikidata and YAGO on 34 criteria found Wikidata with the highest average score (Färber et al. 2018). Which graph is best still depends on the task, since the comparison lets users weight the criteria themselves.

Benchmark validity remains a worry. The redundant relations described under Datasets and benchmarks inflated early scores (Toutanova & Chen 2015). Simple models also hold up well. A linear factorisation, TuckER, outperformed nonlinear convolutional rivals (Balažević et al. 2019), and a properly tuned TransE beat ConvE on some measures (Nguyen et al. 2018). Gains reported on today's splits may therefore partly reflect artefacts of the data or of tuning.

The relation with language models is unsettled:

• Pretrained models recall many simple facts but stumble on many-to-many relations (Petroni et al. 2019).
• They blur facts that change over time (Dhingra et al. 2022).
• Curated commonsense graphs still add knowledge that large models do not produce on their own (Hwang et al. 2020).
• Injected triples can bring "knowledge noise". Without its visibility mask, K-BERT scored below plain BERT on a legal question-answering task (Liu et al. 2019).

The roadmap literature names further open problems: hallucination, opaque parametric knowledge, missing graph facts, and graphs' weak hold on language (Pan et al. 2023).

Entity identity across vocabularies is hard in specialised domains. Disease terms conflict across medical ontologies, and resolving them in PrimeKG was done with language-model clustering (Chandak et al. 2023). Finally, graphs are increasingly built by generation rather than extraction. In that setting the accuracy of the seed facts appears to matter more than sheer volume (Hwang et al. 2020).

The library in figures