Foundations of Knowledge Graphs: Definitions, History, and Formal Models

Foundations of Knowledge Graphs: Definitions, History, and Formal Models

What exactly is a knowledge graph, and why does the answer matter? This question is not academic posturing; it determines every downstream engineering decision. If you treat a knowledge graph as a flexible property graph with no deductive closure, you will reach for Cypher, materialized joins, and graph neural networks, and the missing edge in your data will be treated as evidence of negation. If you treat it as a description-logic theory, you will reach for SPARQL with OWL 2 profiles, a reasoner, and a triple store with entailment support, and the same missing edge will be treated as evidence of incompleteness. These two worldviews look superficially similar—both speak of "nodes" and "edges"—but they disagree on what a missing edge means, on whether contradictions are errors or facts, and on what counts as a valid query result. The remainder of this book assumes the second worldview with the first as a degenerate or pragmatic case, but the purpose of this opening chapter is to make that commitment precise, justified, and explicit, because every architectural decision in the rest of the book follows from it.

The risk of conflating the two usages is real and current. Google's 2012 introduction of the term in the context of its search engine referred to "things, not strings"—an aggregation of entities and relations harvested from multiple sources and served at query time to enrich result pages. That artifact is not, in the strict sense, a knowledge graph as the term is used in the semantic-web community, because it does not commit to a closed formal ontology, does not expose reasoning services, and tolerates inconsistencies that a description-logic reasoner would reject. Yet it shares enough surface features—nodes represent entities, edges represent relations, both are labeled—that practitioners routinely borrow vocabulary from one camp while implementing in the other. This chapter refuses that borrowing. We will fix a definition, derive its consequences, and use those consequences to motivate the architecture that structures the rest of the book. The cost of the precision is a few pages of formalism; the benefit is that every later chapter can be read against a stable target.

1.1 Disambiguating the Term: Industrial Use Versus Formal Use

The phrase "knowledge graph" entered mainstream vocabulary in 2012 when Amit Singhal, then head of Google Search, wrote in a corporate blog post that Google was introducing "a graph of real-world things and their relationships to one another." Internally, the artifact combined data from Freebase, Wikipedia infoboxes, the CIA World Factbook, and Google's own crawls; externally, it appeared as the knowledge panels in the right-hand rail of search results. Within eighteen months, Microsoft's Satori, Facebook's Entity Graph, and Amazon's Product Graph had all been announced, and the term had become a generic descriptor for any large-scale entity-centric data product.

The semantic-web tradition had, by 2012, used a more restrictive vocabulary. Researchers spoke of RDF graphs, OWL ontologies, and description-logic theories; the term "knowledge graph" was either absent or used as a casual synonym for "RDF dataset." The two communities converged in the late 2010s as industrial systems adopted formal schemas (Google's Schema.org work, Wikidata's ontology, the publication of OWL 2 profiles suited to large-scale reasoning) and as semantic-web researchers accepted that production systems rarely honor the full formal commitments of OWL DL. The contemporary usage of "knowledge graph" therefore spans a spectrum whose endpoints are easy to characterize but whose middle is messy.

At one end—the industrial endpoint—a knowledge graph is a directed, labeled, multi-relational graph stored in some property-graph or triple-store system, indexed for low-latency retrieval, optionally enriched with embeddings for machine-learning consumption, and maintained by a mixture of automated extraction, manual curation, and crowdsourced contribution. It is a pragmatic artifact: useful, large, often inconsistent, and almost never closed under any reasoning regime. Google's internal graph in 2012 had on the order of 500 million entities and 3.5 billion facts, but the schema was shallow, the type system tolerated type overlap, and the system exposed no entailment regime beyond schema-level transitivity of subclass and subproperty. This is the sense in which the term is used in most engineering blogs, product documentation, and vendor whitepapers.

At the other end—the formal endpoint—a knowledge graph is a finite set of RDF triples interpreted as a first-order structure over a vocabulary, together with an ontology that constrains the structure through description-logic axioms. It is a deductive artifact: every entailed triple is, in principle, a member of the graph; reasoning is decidable within the chosen profile; and the system distinguishes between asserted facts and inferred facts. The schema is itself a graph (RDFS plus a subset of OWL 2), and the boundary between schema and data is enforced by entailment rules rather than by table joins. Wikidata is the canonical example at industrial scale: it is stored as RDF, ontologically constrained by a moderate subset of OWL, and queryable through SPARQL with entailment. SNOMED-CT is the canonical example at domain-expert scale: it is encoded in OWL 2 EL, contains over 350,000 classes, and supports instance retrieval at clinical-query latency.

The engineering of a knowledge graph in 2024 is the engineering of an artifact that lives somewhere between these endpoints. The remainder of this book presupposes that the artifact has a formal schema—that the schema is not merely documentation—and that the schema is enforced, either through inference (a reasoner) or through validation (a shape constraint language such as SHACL). The book does not presuppose full OWL 2 DL reasoning, which is intractable for the sizes practitioners care about; we will instead restrict to the OWL 2 profiles (EL, QL, RL) and to RDFS-plus-property-chains as the default reasoning regime. The point of this opening chapter is to make that commitment explicit and to derive the architectural consequences that follow from it.

A second terminological hazard is the conflation of "knowledge graph" with "graph database." A graph database is a persistence layer optimized for adjacency-list traversals, often with transactional semantics inherited from the relational tradition. A knowledge graph is a logical artifact that may or may not be persisted in a graph database. The same knowledge graph can be stored in a triple store, a property-graph database, a relational database with recursive queries, or a columnar file format such as Parquet with a semantic layer on top. The storage choice is an implementation detail; the logical artifact is what determines correctness. We will return to this distinction in Chapter 5, but it is worth fixing at the outset: when this book says "knowledge graph," it means the logical artifact, not the database in which it happens to live.

1.2 Set-Theoretic and Graph-Theoretic Foundations

A knowledge graph, in the sense this book adopts, is a directed, labeled, multi-relational graph together with an ontological schema. We will now give precise set-theoretic specifications for each component and show how they compose. The formalism is the minimum needed to make the rest of the chapter (and the rest of the book) precise; readers familiar with description logics may skim, but the explicit definitions are necessary because later chapters will refer back to them.

Vertices and labels. Let $U$ be a universe of resources partitioned into two disjoint sets: $R$ (IRI-denoted resources) and $L$ (literals, drawn from XML Schema datatypes). An IRI (Internationalized Resource Identifier) is a Unicode string that uniquely identifies a resource