Foundations of Knowledge Graphs: History, Definitions, and Computational Semantics

1.1 The Problem of Structured World Knowledge

The central motivating question of this chapter is deceptively simple: what is a knowledge graph, and what makes it a distinct artifact of computation rather than a relabeling of older ideas? The temptation to give a quick answer—"a knowledge graph is a graph of knowledge"—should be resisted. Such a definition absorbs the term into a continuum that already includes semantic networks in psychology, ontologies in philosophy, ER diagrams in database theory, citation networks in bibliometrics, and social graphs in network science. If the term is to do useful work, it must carve a region of conceptual space that none of those neighboring notions occupies, while still connecting to them in principled ways. The aim of this chapter is to perform exactly that carving, to trace the intellectual history that made the carving possible, and to install the formal semantic commitments that practitioners must internalize before they can reason coherently about design choices in subsequent chapters.

A useful starting point is to observe that a knowledge graph, in the sense relevant to this book, is a *committed* representation. Unlike a probabilistic embedding or a latent language model, it is a declarative data structure whose contents can be read, audited, and revised by human agents. At the same time, unlike a closed relational database, it is designed to be incomplete in a principled way: a knowledge graph is permitted to say nothing about a query, and the absence of an answer is not by itself evidence of a negative fact. The combination of declarativeness and open-world semantics gives the knowledge graph its distinctive character, and is the reason it can scale to encyclopedic scope without collapsing into either inconsistency or an unmanageable legacy of absences.

The chapter proceeds in seven steps. Section 1.2 sharpens the working definition. Section 1.3 walks the historical lineage from Cyc and WordNet through the Semantic Web to industrial systems. Section 1.4 formalizes the model-theoretic semantics that license reasoning over triples. Section 1.5 draws boundaries with relational databases, taxonomies, and heterogeneous information networks. Section 1.6 introduces the three-layer architecture that will recur throughout the book. Section 1.7 grounds the discussion in a worked example that contrasts a small domain-specific graph with a large-scale open one. Section 1.8 previews the symbolic-neural tension that organizes the remainder of the volume.

1.2 A Precise Definition: Schema, Multirelationality, and Open-World Semantics

A *knowledge graph* is a directed, labeled, multi-relational graph that pairs an instance-level data layer with a schema-level abstraction layer, and that is interpreted under the open-world assumption. Each of the six adjectives in this definition carries weight, and unpacking them is the only way to ensure that the term is used with the precision the rest of the book requires.

*Directed* and *labeled* indicate that edges have a direction and a name. A triple $\langle s, p, o \rangle$ asserts that the subject $s$ stands in the named relation $p$ to the object $o$. The label is not merely cosmetic: it is the element of the representation that supports reasoning, since the semantics of the relation determine which inferences are licensed. In a knowledge graph, the edge label "capital of" carries the implicit commitment that the relation is functional, whereas "neighbor of" carries the commitment that it is symmetric. The label, in other words, is a hook into the schema.

*Multi-relational* means that many edge types coexist, rather than there being a single type of edge that is merely weighted. A weighted citation network has one edge type with real-valued attributes; a knowledge graph has thousands of edge types, each with its own semantics. This is the property that distinguishes a knowledge graph from a generic attributed graph or a property graph without a schema, and it is what permits the data structure to encode the heterogeneous fabric of real-world relationships.

The *schema layer* is the second crucial element. In its weakest form, the schema is a collection of property definitions and class memberships, often expressed in RDFS or a fragment of OWL. In its strongest form, the schema is a full first-order theory with function and inverse axioms. Either way, the schema is what allows an automated reasoner to derive implicit triples from explicit ones and to detect inconsistencies that would otherwise be invisible. The instance layer is the bulk of the data: the millions or billions of factual statements that the graph stores. The schema and the instance layers are mutually constraining: a class in the schema can declare that its instances must satisfy certain properties, and the instance data can be checked against that declaration.

The *open-world assumption* (OWA) is the final and most subtle element. In a relational database, the closed-world assumption (CWA) holds: if a fact is not in the table, it is assumed to be false. In a knowledge graph, the absence of a triple does not entail its negation. The graph may simply not know. This is appropriate for the typical sources of a knowledge graph—text extraction, crowdsourcing, federated queries—each of which is incomplete. The cost of OWA is that queries cannot be answered by simple failure: a "no" answer must be either inferred by negation-as-failure in a separately specified query layer, or marked as unknown. The benefit is that the graph can be extended, merged, and revised without rewriting prior conclusions.

Formally, we may write a knowledge graph as $K = (V, E, C, \mathcal{A}, \mathcal{S})$ where $V$ is the set of nodes, $E \subseteq V \times \mathcal{P} \times V$ is the set of labeled edges over a vocabulary of properties $\mathcal{P}$, $C$ is the set of classes, $\mathcal{A}$ is the set of axioms (the schema), and $\mathcal{S}$ is the model-theoretic structure in which the graph is interpreted. The notation is deliberately aligned with description-logic conventions, and it is in this formalism that Chapter 4 will return when discussing reasoning.

It is worth flagging a frequent confusion. The phrase "property graph," as used in systems such as Neo4j and Amazon Neptune, denotes a representation in which nodes and edges carry arbitrary key–value attributes, and in which there is no formally specified schema layer. A property graph can be used as a storage substrate for a knowledge graph, but the substrate and the artifact are not the same. We will return to the distinction in Section 1.5. For now, the working assumption is that a knowledge graph is, at minimum, a multi-relational directed graph with a schema, and is interpreted under OWA. Any system that lacks one of those three properties may be a useful engine for knowledge-graph construction, but the artifact it stores is not yet a knowledge graph in the strict sense.

1.3 Historical Lineage: From Cyc to Industrial Knowledge Graphs

The contemporary knowledge graph is the product of at least five converging research programs, each of which left an enduring mark on the field. To understand what a knowledge graph is, it is necessary to know what it inherits and what it leaves behind.

The first lineage is *symbolic knowledge engineering*, exemplified by the Cyc project initiated by Douglas Lenat in 1984. Cyc's premise was that general artificial intelligence would require a hand-coded, multi-decade effort to encode "consensus reality" into a formal logical theory. The project produced millions of axioms expressed in a proprietary variant of first-order logic, supported by an inference engine capable of micro-theoretic reasoning. Cyc's contribution to the present notion of a knowledge graph is the conviction that commonsense knowledge can in principle be formalized, and that the formalization must include not only factual assertions but also rules for combi