Knowledge Graphs

What a knowledge graph is and how it is queried, built on this site's own pages as a graph of 10,105 entities and 39,157 triples. The data model (triples, RDF, property graphs, schema and ontology in outline), basic graph patterns as conjunctive queries with proofs that checking a solution is polynomial, that deciding whether one exists is NP-complete, and that containment is decided by a homomorphism, regular path queries evaluated by a product construction, the open- and closed-world assumptions, how completeness is estimated (with a sample of 40 mentions judged by a language model, the site's links cover about 91% of the exact-title mentions that call for one), and retrieval from a graph for a language model by subgraphs and verbalized triples. Worked problems evaluate a pattern by hand, decide an equivalence, run a path query through its automaton, put an interval on the completeness estimate and prove when a pattern's solutions must be injective.

The page Okapi BM25 on this site is linked from 52 other pages and links to 14. Its References name works by S. E. Robertson, and so do eight other pages. A reader who wants every page that cites a work by Robertson can search the text and read the results. A program can answer exactly, in milliseconds, if the facts "page cites work" and "work has author" are stored as records it can join. This article asks what such a store of facts is, how it is queried, and how anyone can tell what it is missing.

A knowledge graph is a set of facts of the form (head, relation, tail), each fact an edge labeled with the relation from one entity to another. Hogan and colleagues (2021, §3) use the term for such a data graph "potentially enhanced with representations of schema, identity, context, ontologies and/or rules." Everything in this article is about the data graph and the parts of schema needed to query and check it.

First we fix the data model: triples, the W3C's RDF, property graphs, and schema in outline. Then we build the running example, this site's own pages as a graph, and measure it. Next come queries. Basic graph patterns are conjunctions of triple patterns; we prove what evaluating them costs and when two of them are equivalent. Regular path queries follow paths of any length; we prove that they are evaluated in polynomial time. Then we turn to what a graph does not contain: the open- and closed-world assumptions, and an estimate of how complete the site's links are. Finally we retrieve from the graph for a language model. The article assumes nothing beyond sets and relations and the evaluation measures of the course. The numbers come from tools/experiments/knowledge-stores/knowledge-graphs.py, which builds the graph with the unit's loader sitegraph.py.

Triples and the data model

Start with one fact from the site: the page on BM25 cites Robertson and Zaragoza's 2009 monograph. Written as a triple it is (page okapi-bm25, cites, work robertson-2009-…). The head and the tail are entities; the relation is a label on the edge between them.

Definition (knowledge graph). Let $\mathcal{E}$ be a set of entities and $\mathcal{R}$ a set of relations. A knowledge graph is a finite set $G \subseteq \mathcal{E} \times \mathcal{R} \times \mathcal{E}$ of triples $(h, r, t)$. We write $n_e = |\mathcal{E}|$ and $n_r = |\mathcal{R}|$, and $G_r = \{(h, t) : (h, r, t) \in G\}$ for the edges of one relation.

Hogan and colleagues call this a directed edge-labelled graph (§2.1.1). Two features separate it from a table. No schema has to be fixed in advance: a new relation is just a new label. And a missing fact is simply an absent edge, so incomplete information needs no null values (§2.1.1). The same survey shows the step from a relational schema that keeps being remodeled to a set of binary relations, which "can be viewed as modelling a graph" (§2.1).

RDF. The W3C's Resource Description Framework standardizes this model. "An RDF graph is a set of RDF triples", and a triple has a subject, which is an IRI or a blank node; a predicate, which is an IRI; and an object, which is an IRI, a literal or a blank node (W3C, 2014, §3, §3.1). IRIs give entities global names on the Web. Literals hold strings, numbers and dates. Blank nodes stand for something that exists but has no name. RDF writes the triple in the order subject, predicate, object; this unit says head, relation, tail, after the embedding literature (Bordes et al., 2013, write (head, label, tail)).

Property graphs. Graph databases such as Neo4j use a different model, in which nodes and edges carry a label and a set of property-value pairs (Hogan et al., 2021, §2.1.3). A flight from Santiago to Arica can then be one edge with company = LATAM written on it. In a triple graph the same fact needs a node for the flight, with edges for its origin, destination and company. The survey notes that property graphs and directed edge-labeled graphs can be translated into each other without loss (§2.1.3). The choice is about convenience and available systems, not about what can be said.

Schema and ontology, in outline. Hogan and colleagues distinguish three kinds of schema (§3.1).

  • A semantic schema gives meaning to the vocabulary so that new facts can be inferred: classes and subclasses, properties and subproperties, and the domain and range of a property. RDF Schema (RDFS) provides these four features, and the Web Ontology Language (OWL) lets the meaning of terms be defined in much more depth (§3.1.1, and §4.1 for OWL's features). If city has range City, a triple (Santa Lucía, city, Santiago) entails (Santiago, type, City).
  • A validating schema states constraints that the data must satisfy, such as "every event has a name and a venue", and lists the nodes that violate them. Shapes are a standard way to write such constraints (§3.1.2).
  • An emergent schema is a structure discovered in the data rather than declared (§3.1.3).

An ontology, in this sense, is a semantic schema written in a logic precise enough to reason with. This unit uses schema only for checking, as the next section does.

The site as a knowledge graph

Here is the running example. The unit's loader reads every page of this site's wiki and library from one fixed commit of the source (0c5cb000, before this unit was written), so that the graph does not change as pages are added. It uses the site's own bibliography parser for the References sections. The result has 850 pages (270 in the wiki, 580 in the library) and 10,105 entities in all.

Relation From To Triples What it records
links_to page page 9,631 the body has a [[link]] to that page
in_topic page page 802 the page's topic: field
in_course page course 41 a topic page's course: field
tagged page tag 6,486 one of the page's tags
cites page work 4,763 a References entry names the work
notes_on page work 347 a reading note's source: is the work
has_author work person 6,989 an author of the work
type any class 10,098 the entity's class

The 39,157 triples connect 850 pages, 2,492 tags, 2,831 works, 3,921 persons and 4 courses, and each of these has one type triple to one of 7 classes. Pages fall into three classes: 459 articles, 68 topic pages and 323 reading notes (pages with a source:). A SHA-256 digest of the sorted triples, beginning 0011bcc09cd4e8fe, identifies the graph every number below was computed on.

The schema checked. The "From" and "To" columns of the table are a domain and range for each relation, in the RDFS sense, used here as a validating schema. The script checks every triple against them and finds 0 violations. It also checks three relations that should be functional, with at most one tail per head: in_topic, in_course and type all are. And every in_topic tail is a topic page. 48 pages have no topic at all. They are the roots of the site's tree: the 41 topic pages of the four courses, which name a course instead, and 7 others, among them the collections.

Sizes and degrees. Counting a graph's edges by their endpoints gives the first small result.

Proposition 1. For every relation $r$, the out-degrees of $G_r$ sum to $|G_r|$, and so do the in-degrees. A functional relation has at most as many triples as there are distinct heads.

Proof. Each pair $(h, t) \in G_r$ is counted once in the out-degree of $h$ and once in the in-degree of $t$, and in no other degree. Summing over all heads counts every pair once, and likewise for tails. If $r$ is functional, each head has out-degree at most 1, so $|G_r| = \sum_h \deg^+(h) \le |\{h : \deg^+(h) > 0\}|$. $\square$

For links_to the mean out-degree, which by Proposition 1 equals the mean in-degree, is $9{,}631 / 850 = 11.33$. The distribution is skewed. The collection page for Anthropic's research has out-degree 324, because it lists every note in its collection, and the next largest has 155. The largest in-degree is 57, for significance testing. No page has out-degree or in-degree 0, and the 14,942 link mentions in the bodies collapse to 9,631 distinct pairs, about 1.55 mentions per pair.

The link graph has more structure than its degrees show. Of the 9,631 links, 4,098 (0.43 of them) are reciprocated: they form 2,049 pairs of pages that link to each other. And the whole link graph is a single strongly connected component: from any page a chain of links leads to any other. From the BM25 page, 14 pages are one link away, 88 are two away, 278 three, 242 four, 224 five and 3 six. Over all 850 starting pages the longest shortest path (the diameter) is 10 links and the smallest eccentricity (the radius) is 5. The course's PageRank article explains why a random surfer needs teleportation on a graph that is not strongly connected; this graph is, so its surfer could never be trapped. It is also aperiodic, since it has cycles of length 2 (the reciprocated pairs) and 3 (the triangles below), so the plain random walk on it already has a unique stationary distribution, the second condition that article gives.

Identity. Works and persons are entities too, and here the graph is weaker. A person is the bibliography's name string. Robertson appears as "Robertson, E. F.", "Robertson, S." and "Robertson, S. E.". The first, with other initials, is presumably someone else; whether the second is the same person as the third cannot be decided from the strings. Among the 3,778 names written as a surname, a comma and the rest (a few of them are organizations), 376 surnames occur with more than one set of initials, and in 103 pairs one set is a prefix of the other, as "S." is of "S. E.". Hogan and colleagues treat identity as a subject of its own (§3.2), beginning with persistent identifiers for entities, and list the prediction of links that say two nodes refer to the same entity among the tasks of refining a graph (§8.1.3). Entity linking, the subject of the article before this one, is the same problem met in text.

Basic graph patterns

Back to the question of the opening: which pages cite a work by Robertson? As a pattern over the graph it reads

$$Q_R = \{(?p,\ \texttt{cites},\ ?w),\ (?w,\ \texttt{has\_author},\ \text{Robertson, S. E.})\}.$$

The terms that begin with a question mark are variables. An answer assigns a value to each variable so that both triples, with the values put in, are in the graph.

Definition (basic graph pattern, solution). A triple pattern is a triple whose positions hold constants or variables. A basic graph pattern (BGP) $Q$ is a finite set of triple patterns. Let $\mathrm{var}(Q)$ be its variables. A solution of $Q$ over $G$ is a mapping $\mu : \mathrm{var}(Q) \to \mathcal{E} \cup \mathcal{R}$ such that $\mu(Q) \subseteq G$, where $\mu(Q)$ replaces each variable by its value and leaves constants alone. The answer $Q(G)$ is the set of all solutions.

SPARQL's basic graph patterns match in this way, with RDF terms substituted for the variables (W3C, 2013, §2). This is the homomorphism-based semantics: two variables may take the same value. Cypher instead requires different variables on edges to take different edges, an isomorphism-based semantics (Hogan et al., 2021, §2.2.1). A conjunctive query is a BGP together with a choice of the variables to return; Hogan and colleagues note that graph patterns with projection "equate to conjunctive queries on graphs" (§2.2.2).

On the site graph $Q_R$ has 17 solutions. They name 9 distinct pages and 7 distinct works. Two of the 7 are cited on 4 pages each, more than any other: Robertson and Spärck Jones's 1976 "Relevance weighting of search terms" and Robertson and Walker's 1994 paper on simple approximations to the 2-Poisson model. The 9 pages include BM25, the binary independence model, the probability ranking principle and relevance feedback. The answer is exact for the graph, which is a narrower claim than it sounds: works listed under "Robertson, S." are not in it.

A pattern is a join

A triple pattern alone is a table: the triples it matches, one column per variable. A BGP is the natural join of those tables on their shared variables. For $Q_R$, the first pattern's table has columns $(?p, ?w)$ and the second's has column $?w$; their join on $?w$ is the answer. Hogan and colleagues write the same thing in relational algebra over one three-column relation (§2.2.2).

Join is commutative and associative, so the order in which the patterns are joined does not change the answer. It changes the work. Joined in the order written, $Q_R$ first produces all 4,763 cites triples and then keeps those whose work has the right author. Joined the other way, it first produces Robertson's 7 works and then looks up who cites each one. The script evaluates both orders and gets the same 17 solutions. Choosing the order is the job of a query optimizer, and the next result shows why no order can make every pattern cheap.

What evaluation costs

Three questions about a BGP $Q$ and a graph $G$ have different costs. Write $|Q|$ for the number of triple patterns and $|G|$ for the number of triples.

Theorem 2 (checking a solution). Whether a given mapping $\mu$ is a solution of $Q$ over $G$ can be decided in time $O(|Q| \cdot |G|)$, and in $O(|Q|)$ expected time if $G$ is stored in a hash set.

Proof. Compute $\mu(Q)$, one triple per pattern, and test each for membership in $G$. A scan of $G$ tests one triple in $O(|G|)$; a hash lookup does it in expected constant time. $\mu$ is a solution exactly when all $|Q|$ tests succeed. $\square$

Pérez, Arenas and Gutierrez (2006, Theorem 1) prove the same bound for SPARQL patterns built with AND and FILTER, where the problem is posed as checking a given mapping.

Theorem 3 (enumerating solutions). All solutions of $Q$ over $G$ can be listed in time $O(|Q| \cdot |G|^{|Q|})$. For a fixed $Q$ this is polynomial in $|G|$.

Proof. Every solution maps each triple pattern to some triple of $G$, so it is determined by a choice of one triple of $G$ for each of the $|Q|$ patterns, and there are at most $|G|^{|Q|}$ choices. For each choice, read off the value each variable must take and check that a variable never receives two different values and that constants match; this takes $O(|Q|)$ steps. Every solution arises from at least one choice, so the procedure lists them all. $\square$

The exponent $|Q|$ is where the difficulty lies. Treating the query as fixed and the data as the input, as in this theorem, is what the database literature calls data complexity; Angles and colleagues (2017, §3.4) note that it has proved a useful guide because queries are usually small.

Theorem 4 (deciding whether a solution exists). The problem "given $Q$ and $G$, does $Q$ have a solution over $G$?" is NP-complete.

Proof. Membership in NP. A solution is a certificate: it assigns at most $3|Q|$ values, and Theorem 2 checks it in polynomial time.

Hardness. We reduce from the clique problem: given an undirected graph $H = (V, E)$ with no self-loops and an integer $k$, does $H$ have $k$ vertices that are pairwise adjacent? The clique problem is one of the problems Karp (1972) proved NP-complete. Two kinds of instance are decided at once, and the reduction maps them to fixed instances with the same answer. If $k > |V|$ the answer is no; if $k \le 1$ it is yes exactly when $k = 0$ or $V$ is nonempty. For a no, output the one-pattern query $\{(?x, e, ?x)\}$ over the empty graph, which has no solution; for a yes, output the empty query over the empty graph, whose one solution is the empty mapping. Otherwise $2 \le k \le |V|$. Build the knowledge graph $G_H = \{(u, e, v), (v, e, u) : \{u, v\} \in E\}$ with one relation $e$, and the pattern $Q_k = \{(?x_i, e, ?x_j) : 1 \le i, j \le k,\ i \ne j\}$. $G_H$ has $2|E|$ triples and $Q_k$ has $k(k-1) < |V|^2$ patterns, so both are polynomial in the size of $H$, however $k$ is written.

If $\{v_1, \ldots, v_k\}$ is a clique, then $\mu(?x_i) = v_i$ is a solution: for $i \ne j$, $v_i$ and $v_j$ are adjacent, so $(v_i, e, v_j) \in G_H$. Conversely, let $\mu$ be a solution. For $i \ne j$ the triple $(\mu(?x_i), e, \mu(?x_j))$ is in $G_H$, so $\mu(?x_i)$ and $\mu(?x_j)$ are adjacent in $H$. They are also different, because $H$ has no self-loops and so $G_H$ has no triple $(u, e, u)$. Hence $\mu(?x_1), \ldots, \mu(?x_k)$ are $k$ distinct, pairwise adjacent vertices: a clique. $H$ has a $k$-clique exactly when $Q_k$ has a solution over $G_H$. $\square$

Angles and colleagues (2017, §3.4) state the corresponding result for checking whether a given tuple is an answer of a BGP with projection, of which deciding non-emptiness is the case with no output variables, and attribute the hardness to a reduction from graph homomorphism. The two theorems together say the expected thing: a short query over a big graph is affordable, and a long query with many shared variables can be as hard as any problem in NP. The same survey adds that the difficulty grows with how cyclic the pattern is, measured by treewidth (§3.4).

Example (cycles in the link graph). The pattern $\{(?a, \texttt{links\_to}, ?b), (?b, \texttt{links\_to}, ?c), (?c, \texttt{links\_to}, ?a)\}$ asks for directed triangles. It has 18,240 solutions. Each triangle $a \to b \to c \to a$ is found three times, once for each starting point, so the site has 6,080 directed triangles. Joining the first two patterns alone produces 123,637 partial solutions, almost thirteen times the 9,631 links, before the third pattern cuts them down. The 18,240 solutions under homomorphism semantics are also all injective. Worked Problem 5 proves that this must be so in any graph without self-loops, and the site graph has none.

When are two patterns the same query?

Consider the query "pairs (page, author) such that the page cites a work by that author", written twice:

$$Q_1 = \{(?p, \texttt{cites}, ?w), (?w, \texttt{has\_author}, ?a)\},$$ $$Q_2 = Q_1 \cup \{(?p, \texttt{cites}, ?w_2), (?w_2, \texttt{has\_author}, ?a)\},$$

each returning $(?p, ?a)$. On the site graph $Q_1$ has 12,106 solutions and $Q_2$ has 16,480, but both return the same 10,525 pairs. That is no accident of the data. The two queries are equivalent on every graph, and a classical theorem tells exactly when such an equivalence holds.

For a conjunctive query $Q$ with output variables $\bar{x}$, write $Q(G)$ for the set of tuples $\mu(\bar{x})$ over the solutions $\mu$. $Q$ is contained in $Q'$ if $Q(G) \subseteq Q'(G)$ for every graph $G$. A homomorphism from $Q'$ to $Q$ is a mapping $\theta$ from the variables of $Q'$ to the terms of $Q$ (variables or constants) such that $\theta(Q') \subseteq Q$ and $\theta(\bar{x}') = \bar{x}$, output to output, position by position.

Theorem 5 (homomorphism theorem). $Q \subseteq Q'$ if and only if there is a homomorphism from $Q'$ to $Q$.

Here is the idea in one sentence: a homomorphism transports every solution of $Q$ into a solution of $Q'$, and conversely $Q$ read as a graph is itself a database on which $Q'$ must find $Q$'s output.

Proof. (If.) Let $\theta$ be a homomorphism from $Q'$ to $Q$, and let $\mu$ be a solution of $Q$ over some $G$, extended to constants by the identity (since $\theta$ may send a variable to a constant of $Q$). Then $\mu \circ \theta$ maps the variables of $Q'$ to entities and relations, and $(\mu \circ \theta)(Q') = \mu(\theta(Q')) \subseteq \mu(Q) \subseteq G$, so it is a solution of $Q'$. Its output is $\mu(\theta(\bar{x}')) = \mu(\bar{x})$. Every answer of $Q$ is therefore an answer of $Q'$.

(Only if.) Build the canonical graph of $Q$: replace each variable $?v$ of $Q$ by a fresh constant $c_v$ that occurs nowhere else, and call the resulting set of triples $G_Q$. We assume that $\mathcal{E}$ and $\mathcal{R}$ hold enough unused names, as the IRIs of RDF do, so that $c_v$ can be an entity where $?v$ stands in a head or tail position and a relation where it stands in a relation position. Because the $c_v$ occur nowhere else, replacing them back by their variables is one-to-one on $G_Q$ and turns $G_Q$ back into $Q$. The mapping $\mu_0(?v) = c_v$ is a solution of $Q$ over $G_Q$, so its output, the tuple of constants $c_{\bar{x}}$, is in $Q(G_Q)$. Since $Q \subseteq Q'$, it is also in $Q'(G_Q)$: some solution $\nu$ of $Q'$ over $G_Q$ has $\nu(\bar{x}') = c_{\bar{x}}$. Now undo the freezing: let $\theta$ replace each $c_v$ in $\nu$'s values by $?v$ and leave other constants alone. Each triple of $\nu(Q')$ is in $G_Q$, so the corresponding triple of $\theta(Q')$ is in $Q$, and $\theta(\bar{x}') = \bar{x}$. So $\theta$ is a homomorphism from $Q'$ to $Q$. $\square$

The theorem is Chandra and Merlin's (1977). Applied to the example: the identity maps $Q_1$ into $Q_2$, so $Q_2 \subseteq Q_1$; and $\theta(?w_2) = ?w$, identity elsewhere, maps $Q_2$ into $Q_1$, so $Q_1 \subseteq Q_2$. The second half of $Q_2$ is redundant, and an optimizer may delete it. Worked Problem 2 runs the same test on a pair that is not equivalent.

What a pattern cannot ask

Every BGP is monotone: if $G \subseteq G'$ then $Q(G) \subseteq Q(G')$, because a solution's triples stay in the larger graph. The script checks this on the site graph with 5% of the triples deleted at random (seed 7): $Q_R$ keeps 16 of its 17 solutions, each of them a solution over the full graph. Monotonicity has a consequence. "Topic pages that do not link to some page of their own topic" is not monotone, since adding one link can remove a page from the answer, and so no BGP expresses it. Negation, difference and optional matches need the operators that SPARQL and Cypher add on top of patterns (Hogan et al., 2021, §2.2.2), and they cost more: with optional matches and union, evaluating SPARQL patterns is PSPACE-complete (Pérez et al., 2006, Theorem 3). Negation is also where the open- and closed-world assumptions part ways, as a later section shows.

Path queries

The topic structure of the site is a chain of in_topic edges: an article belongs to a unit, the unit to a collection. "Which collection does this page sit in?" asks for a path of any length, which no fixed BGP can express in general.

Proposition (paths of any length are not a BGP). No BGP $Q$ with output variables $(?x, ?y)$ returns, on every graph, exactly the pairs joined by a path of one or more in_topic edges.

Proof. Suppose $Q$ did. Take the chain graph $v_0 \to v_1 \to \cdots \to v_n$ of in_topic edges with $n > |Q|$. The pair $(v_0, v_n)$ is an answer, so some solution $\mu$ has $\mu(Q) \subseteq G$ and outputs $(v_0, v_n)$. $\mu(Q)$ has at most $|Q| < n$ triples, so some edge $(v_i, v_{i+1})$ is not among them. Then $\mu$ is still a solution over the chain with that edge removed, where $v_n$ cannot be reached from $v_0$. So $Q$ returns a pair it should not. $\square$

Definition (regular path query). A path expression is built from relation names $r$, inverses $r^-$ (follow an edge backwards), concatenation $e_1 \cdot e_2$, alternation $e_1 \mid e_2$ and the Kleene star $e^*$ (zero or more repetitions). The regular path query $(x, e, y)$ asks for the pairs of nodes joined by a path whose sequence of labels belongs to the language of $e$ (Hogan et al., 2021, §2.2.3).

A path query over a graph with a cycle matches infinitely many paths, so languages restrict what is returned. SPARQL 1.1 returns the set of pairs, Cypher returns paths without repeated edges, and some systems return shortest paths (§2.2.3). The pair semantics can be computed efficiently, and the proof is a construction worth seeing.

A nondeterministic finite automaton (NFA) for path expressions has a finite set of states $S$, a start state, a set of accepting states, and transitions $s \xrightarrow{a} s'$ labeled by a relation $r$ or an inverse $r^-$. It accepts a word of labels if some sequence of transitions, starting at the start state and following the word's labels in order, ends in an accepting state. That every path expression has an NFA without empty transitions that accepts exactly its language is a standard theorem of automata theory (Kleene's theorem, with the empty transitions removed), which we cite and do not prove. Its number of states can be kept linear in the length of the expression, but not always its number of transitions: an NFA without empty transitions can need on the order of $n (\log n)^2$ transitions for an expression with $n$ relation symbols, and that many always suffice, while Thompson's construction stays linear in both by using empty transitions (Gruber and Holzer, 2014, §3 and Theorem 9). In the examples here the automata are written down directly.

Theorem 6 (product construction). Let $A$ be an NFA without empty transitions, with state set $S$ and $m$ transitions, accepting the language of the expression $e$. For a source node $u$, the set of nodes $v$ such that $(u, v)$ answers $(u, e, ?y)$ can be computed in time $O(|G| \cdot |S| + m \cdot |G|)$, linear in the graph for a fixed expression.

Proof. Form the product graph whose nodes are pairs $(v, s)$ of a graph node and an automaton state. Put an edge $(v, s) \to (w, s')$ whenever the automaton has a transition $s \xrightarrow{r} s'$ and $(v, r, w) \in G$, or a transition $s \xrightarrow{r^-} s'$ and $(w, r, v) \in G$. A path in the product from $(u, s_0)$, with $s_0$ the start state, is exactly a pair of a path in $G$ from $u$ and a run of the automaton on its labels, step for step. So $v$ is an answer exactly when some $(v, f)$ with $f$ an accepting state is reachable from $(u, s_0)$. Breadth-first search finds every reachable product node, visiting each once and each of its edges once. The product has at most $|S|$ times as many nodes as $G$, and each automaton transition contributes at most $|G|$ edges. $\square$

Angles and colleagues (2017, §4.5) give the bound $O(|G| \cdot |L|)$ for deciding whether one node reaches another by a path labeled in the regular expression $L$, achieved by folklore automata techniques; for a fixed expression it is the same linear bound. They also record the contrast with Cypher's semantics: if paths may not repeat a node or an edge, evaluation is NP-complete even for a fixed expression. They credit this to Mendelzon and Wood (1989, Theorem 2.1), who proved it for paths without a repeated node, with the expression fixed as $(r \cdot r)^*$, paths of even length, or as $r^* \cdot s \cdot r^*$.

On the site graph, three path queries show the construction at work.

  • in_topic$^+$ from each page finds its ancestors. 48 pages have none, 657 have one (their unit or course topic is the root), and 145 have two (article, unit, collection). The 48 roots head trees of very different size: the Anthropic research collection holds 325 pages, the statistics collection 120, and the information retrieval collection 49.
  • links_to $\cdot$ cites from BM25 finds the works cited by the pages that BM25 links to: 66 works, found by visiting 81 product nodes.
  • cites $\cdot$ has_author $\cdot$ has_author$^-$ $\cdot$ cites$^-$ from BM25 finds the pages that cite some work sharing an author with a work BM25 cites: 131 pages besides BM25 itself.

links_to$^*$ from any page reaches all 850, as strong connectivity requires.

What the graph does not say

Search the site graph for a link from the cluster hypothesis to vector search and there is none. Does the cluster hypothesis page have nothing to do with vector search? The graph cannot say. Hogan and colleagues frame the two readings as assumptions (§3.1.1).

  • Under the closed-world assumption (CWA), the graph is a complete description, and a fact not in it is false. Classical databases work this way.
  • Under the open-world assumption (OWA), a missing fact is unknown. A statement proved false stays false when edges are added, while under the CWA a new edge can contradict what was assumed false.
  • The local closed-world assumption (LCWA) is the compromise: some parts of the graph are declared complete.

The site graph is a natural case for the local assumption. Four of its relations are complete by construction, because each is read from a page's own frontmatter, and the page is the record: in_topic, in_course, tagged and type. If a page has no topic: field, it has no topic; no fact is missing. links_to and cites are different. They record what the writers linked and cited, not every page that discusses another or every work a page relies on. A query that asks for pages not linked from a topic page is answered correctly under the CWA only for the closed relations.

For rule mining and for training knowledge graph embeddings, a middle assumption is common. Under the partial completeness assumption (PCA), if a head has at least one tail for a relation, its tails for that relation are taken to be complete, so any other tail is a negative example (Hogan et al., 2021, §5.4.1, citing the work behind the AMIE rule miner). On the site graph, the PCA would say that since the cluster hypothesis page links to some pages, its links are complete, and the missing link to vector search is a true negative. The next section measures how often that inference fails.

Completeness and how it is estimated

Hogan and colleagues divide completeness into four aspects (§7.2.1): schema completeness (are the schema's classes and properties used?), property completeness (the share of missing values of a property), population completeness (the share of real-world entities of a type that are present) and linkability completeness (how far instances are interlinked). Measuring completeness exactly needs the "hypothetical ideal knowledge graph" the data should represent. In practice one compares with a gold standard that provides a sample of that ideal graph, or measures the recall of extraction from sources known to be complete (§7.2.1). The site graph shows each kind.

Property completeness, measured directly. Every one of the 850 pages has a summary and at least one tag. Of the 2,831 works, 29 have no parsed author and 165 no year (web pages and documents without a date, mostly); 718 carry a DOI and 374 an arXiv identifier. These counts are exact because the ideal is known: a work either has a year in its entry or it does not.

Population completeness. Every one of the 323 reading notes is matched to its work by the notes_on relation, so that relation is complete with respect to the notes. The works themselves are a different matter. 2,147 of the 2,831 works are cited by exactly one page, and 846 of the 850 pages cite at least one work. Whether every source a page relies on is in its References is not something the graph can check against itself.

Linkability, estimated from a sample. The interesting relation is links_to. What would the ideal set of links be? We take one concrete stand-in: a page should link to another page wherever its running text names that page's subject by the page's exact title. The script finds every such mention.

  1. It takes the 833 page titles of two words or more (the 17 one-word titles, such as "Relevance", are too ambiguous to search for).
  2. It reads each page's text as a reader sees it, with code, math and the References removed, and finds each title wherever it occurs in the running prose.
  3. It also reads the text of every link. A link to a page whose anchor contains that page's title (as a bare [[slug]] does, since it renders as the title) is a mention of the title that is already linked. A title that occurs inside the text of a link to some other page names that other page's subject and is not counted.
  4. It records each pair (page, title) found, once per pair.

There are 7,943 such pairs. In 7,144 of them the page links to the titled page, which is 0.899 of the pairs: 7,068 pairs are named in the text of the link itself (1,374 of the site's links are bare), and 677 name the title in plain prose as well or instead. The other 799 are unlinked mentions: the page names the title in its prose and has no link to that page.

A mention is not always a reference to the page's subject. "International Conference on Genetic Algorithms" contains the title Genetic Algorithms but names a conference. So we drew a seeded random sample of 40 of the 799 unlinked mentions (seed 20261122) and judged each from the 320 characters around it, with one criterion: in its context, does the phrase name the thing the titled page is about? The judgments were made by the writer of this article, a language model, and are recorded with a one-line reason each in data/link-sample.tsv; they were not checked by the owner. 37 of the 40 passed. The three that failed were the conference name, "the central limit theorem for Markov chains" (a different theorem from the one its page proves) and a repository address in a URL.

The estimate. If a share $\pi$ of the 799 unlinked mentions should be links, the estimated completeness of the links with respect to title mentions is

$$\hat{c} = \frac{7{,}144}{7{,}144 + 799\,\pi}.$$

With $\hat\pi = 37/40 = 0.925$, about 739 missing links, $\hat{c} = 0.906$. The sample of 40 leaves real uncertainty in $\hat\pi$. Wilson's score interval for a proportion, derived in Confidence Intervals for a Proportion, gives 0.801 to 0.974 at 95% confidence for 37 of 40. Because $\hat{c}$ decreases as $\pi$ grows, the two ends map to completeness from 0.902 to 0.918. So about nine in ten of the exact-title mentions that should be links are links.

Two cautions bound what the number means. It is completeness relative to exact title mentions, the only part of the ideal graph we sampled. A page can discuss BM25 without using the words "Okapi BM25", and those relations are outside the estimate in both directions. And the 7,144 existing links are assumed correct. Under those terms the PCA's inference from the last section is mostly right but fails where it matters: across the 7,943 named pairs only about a tenth are unlinked, yet among those 799 unlinked pairs, 37 of the 40 sampled are missing facts, not negatives.

Retrieval over a graph for a language model

A language model reads text. To use a knowledge graph it needs a subgraph relevant to the question, turned into words. That is the graph form of retrieval-augmented generation.

Subgraph retrieval. The simplest subgraph is the neighborhood of the entities a question mentions: every triple within $k$ steps, edges taken in either direction. It grows fast. Over the 850 pages the median 1-step neighborhood has 36 triples and the largest 667. The BM25 page's 1-step neighborhood has 79 triples; its 2-step neighborhood has 2,613, of which 1,192 use links_to alone. Two steps from one page already exceed what a prompt should hold. Systems therefore select within the neighborhood. G-Retriever (He et al., 2024) embeds the text of every node and edge, retrieves the $k$ nodes and edges most similar to the question by cosine similarity, and then solves a prize-collecting Steiner tree problem: find a connected subgraph that maximizes the prizes of relevant nodes and edges minus a cost for its size (§5.1 to §5.3). Here the similarity measures of the first unit meet graph search. Entity linking decides which entities a question mentions in the first place; entity-oriented search ranks entities, rather than documents, for a query.

Verbalized triples. The selected triples must then be written as text. G-Retriever lists nodes and edges "akin to a CSV file format" (§4.1). Agarwal and colleagues (2021) went further: they trained a model to turn groups of Wikidata triples into natural sentences and verbalized the whole English Wikidata graph, about 45 million triples as 18 million sentences in the KELM corpus, which a retrieval language model could then search as ordinary text. The loader of this unit has the simplest possible verbalizer, one fixed phrase per relation. The 24 triples that support the answer to $Q_R$ (17 cites and 7 has_author) become 24 sentences of 380 words, beginning

The page "Binary Independence Model" cites the work "Relevance weighting of search terms" (1976). The work "Relevance weighting of search terms" (1976) has the author Robertson, S. E.

Given those sentences, a model can answer the opening question and cite each fact. The query found the facts exactly; the text only carries them.

Graphs built from text. The direction can also be reversed: build the graph from the corpus and retrieve from the graph. GraphRAG (Edge et al., 2024) has a language model extract entities and relationships from every chunk of a corpus, groups closely related entities into communities, writes a summary of each community in advance, and answers a question about the whole corpus by generating partial answers from the summaries and combining them. The reading note From Local to Global: A GraphRAG Approach to Query-Focused Summarization gives its design and the evaluation by language-model judges.

What is proved here, what is cited, what is measured

Proved on this page. The degree sums and the bound for functional relations (Proposition 1); that checking a solution takes $O(|Q| \cdot |G|)$ (Theorem 2); that enumeration takes $O(|Q| \cdot |G|^{|Q|})$, polynomial for a fixed query (Theorem 3); that deciding whether a BGP has a solution is NP-complete, by reduction from the clique problem (Theorem 4); the homomorphism theorem for containment of conjunctive queries (Theorem 5); the proposition that no fixed BGP expresses paths of every length; the product construction for regular path queries (Theorem 6); the monotonicity of BGPs; and, in the worked problems, that a 3-cycle pattern has only injective solutions over a graph without self-loops.

Cited. The NP-completeness of the clique problem (Karp, 1972); the existence of an NFA without empty transitions for every path expression (Kleene's theorem), and the sizes such automata need (Gruber and Holzer, 2014); the attribution of the homomorphism theorem (Chandra and Merlin, 1977); PSPACE-completeness of SPARQL with optional matches (Pérez et al., 2006); NP-completeness of path queries under no-repeated-node semantics (Mendelzon and Wood, 1989, Theorem 2.1); the definitions of RDF and of the world assumptions; and every description of G-Retriever, KELM and GraphRAG.

Measured. Every count on the site graph at the pinned commit, by the script; and the completeness estimate, which rests on 40 judgments by a language model against a stated criterion and on the assumption that existing links are correct.

Worked problems

These units have no course assignments, so the problems are posed on a five-triple graph and on the site graph, and the script checks each number.

Problem 1. The graph $G_1$ has one relation $l$ and five triples: $A \to B$, $B \to A$, $B \to C$, $C \to A$, $A \to C$. List the solutions of $Q = \{(?a, l, ?b), (?b, l, ?c)\}$ under homomorphism semantics and under injective semantics, and count the directed triangles.

Solution. Join the pattern's two copies of $G_1$ on $?b$. For each edge $a \to b$, list the edges leaving $b$.

$a \to b$ edges leaving $b$ solutions $(a, b, c)$
$A \to B$ $B \to A$, $B \to C$ $(A, B, A)$, $(A, B, C)$
$A \to C$ $C \to A$ $(A, C, A)$
$B \to A$ $A \to B$, $A \to C$ $(B, A, B)$, $(B, A, C)$
$B \to C$ $C \to A$ $(B, C, A)$
$C \to A$ $A \to B$, $A \to C$ $(C, A, B)$, $(C, A, C)$

Under homomorphism semantics all 8 are solutions. Injective semantics requires $a$, $b$, $c$ all different, which removes the four with $a = c$ and leaves 4: $(A, B, C)$, $(B, A, C)$, $(B, C, A)$, $(C, A, B)$. For triangles, add $(?c, l, ?a)$: of the 8, only $(A, B, C)$, $(B, C, A)$ and $(C, A, B)$ have the closing edge ($C \to A$, $A \to B$, $B \to C$). These 3 solutions are one triangle, $A \to B \to C \to A$, found from each of its three starting points. ($A \to C \to B$ would need $C \to B$, which is absent.)

Problem 2. Over the site's relations, is $Q_3 = \{(?p, \texttt{cites}, ?w), (?q, \texttt{cites}, ?w)\}$ with output $(?p)$ equivalent to $Q_4 = \{(?p, \texttt{cites}, ?w)\}$ with output $(?p)$? Is $Q_5 = \{(?p, \texttt{cites}, ?w), (?p, \texttt{links\_to}, ?q), (?q, \texttt{cites}, ?w)\}$ with output $(?p)$ equivalent to $Q_4$?

Solution. By Theorem 5 we look for homomorphisms in both directions, output to output.

  • $Q_4 \to Q_3$: the identity maps $(?p, \texttt{cites}, ?w)$ to a triple of $Q_3$, so $Q_3 \subseteq Q_4$.
  • $Q_3 \to Q_4$: $\theta(?q) = ?p$, identity elsewhere, sends $(?q, \texttt{cites}, ?w)$ to $(?p, \texttt{cites}, ?w)$, so $Q_4 \subseteq Q_3$.

So $Q_3 \equiv Q_4$: "a page citing a work that some page cites" is just "a page citing a work", since the page itself is such a page.

For $Q_5$, the identity again gives $Q_5 \subseteq Q_4$. A homomorphism $\theta$ from $Q_5$ to $Q_4$ would have to send $(?p, \texttt{links\_to}, ?q)$ to a triple of $Q_4$ with relation links_to, and $Q_4$ has none. So $Q_4 \not\subseteq Q_5$, and the canonical graph of the proof is the counterexample: the one-triple graph $\{(c_p, \texttt{cites}, c_w)\}$ answers $Q_4$ with $c_p$ and $Q_5$ with nothing.

Problem 3. On $G_1$, which nodes answer the path query $(A, (l \cdot l)^*, ?y)$, the nodes reachable from $A$ by a path of even length, and how long is the shortest such path to each?

Solution. The automaton has two states: 0 (even so far, start and accepting) and 1 (odd), with transitions $0 \xrightarrow{l} 1$ and $1 \xrightarrow{l} 0$. Breadth-first search on the product, level by level:

  • distance 0: $(A, 0)$;
  • distance 1: $(B, 1)$, $(C, 1)$;
  • distance 2: from $(B, 1)$ along $B \to C$, $(C, 0)$; $B \to A$ and $C \to A$ lead to $(A, 0)$, already seen;
  • distance 3: from $(C, 0)$ along $C \to A$, $(A, 1)$;
  • distance 4: from $(A, 1)$ along $A \to B$, $(B, 0)$; $A \to C$ leads to $(C, 0)$, already seen.

All 6 product nodes are reached. The accepting ones give the answer: $A$ at distance 0, $C$ at 2 ($A \to B \to C$) and $B$ at 4 ($A \to B \to C \to A \to B$). $B$ is one step from $A$, but every even path to it is long, which a search that ignored the automaton's state would miss.

Problem 4. Suppose the judged sample had found 30 of 40 unlinked mentions to be genuine instead of 37. What would the completeness estimate be, and how does the estimate behave as $\pi$ moves from 0 to 1?

Solution. With $\hat\pi = 30/40 = 0.75$, $\hat{c} = 7{,}144 / (7{,}144 + 799 \times 0.75) = 7{,}144 / 7{,}743.25 = 0.923$. In general $\hat{c}(\pi) = 7{,}144 / (7{,}144 + 799\pi)$ falls steadily from $\hat{c}(0) = 1$, if no unlinked mention should be a link, to $\hat{c}(1) = 7{,}144/7{,}943 = 0.899$, if all should. The raw linked share 0.899 is therefore the lowest completeness the title mentions allow, reached only if every mention is genuine. Since $\hat{c}$ is decreasing in $\pi$, an interval for $\pi$ maps to an interval for $c$ with its ends exchanged, which is how the article's 0.902 to 0.918 came from Wilson's 0.801 to 0.974.

Problem 5. Prove that if a graph $G$ has no triple of the form $(v, l, v)$, every solution of $Q = \{(?a, l, ?b), (?b, l, ?c), (?c, l, ?a)\}$ over $G$ is injective. Does the same hold for a 4-cycle pattern?

Solution. Let $\mu$ be a solution and write $a = \mu(?a)$, $b = \mu(?b)$, $c = \mu(?c)$. The triples $(a, l, b)$, $(b, l, c)$ and $(c, l, a)$ are in $G$. Since $G$ has no self-loops, $a \ne b$, $b \ne c$ and $c \ne a$, from the three triples respectively. So the three values are distinct. Every pair of variables in a 3-cycle is joined by an edge of the pattern, which is what makes the argument work.

In a 4-cycle $\{(?a, l, ?b), (?b, l, ?c), (?c, l, ?d), (?d, l, ?a)\}$ the variables $?a$ and $?c$ are not joined by an edge. On $G_1$, $\mu = (A, B, A, B)$ is a solution, since $A \to B$ and $B \to A$ are both present, and it is not injective. So the claim fails for 4-cycles. The same solution exists for every reciprocated pair of links, so on the site graph, with its 2,049 such pairs, the 4-cycle pattern has strictly more solutions than injective ones.

What we have learned

A knowledge graph is a set of triples, and the site's pages make one of 39,157 triples over 10,105 entities. Queries over it are patterns. Checking a proposed answer is cheap, listing all answers is polynomial for a fixed pattern, deciding whether any answer exists is NP-complete in general, and two patterns ask the same question exactly when each maps homomorphically into the other. Paths of any length are found in linear time by running the graph and an automaton together. What a graph omits is the harder half. On this site four relations are closed by construction, while the links, measured against exact title mentions, are about nine-tenths complete, and the missing tenth shows that the open-world reading is the right default for them. For a language model the graph is retrieved as a small subgraph and read as sentences.

The next article, Entity-Oriented Search, ranks entities, not documents, for a query, using descriptions and links of the kind this graph holds. After it, Knowledge Graph Embeddings turns to a graph's absent edges: it learns vectors for the entities and relations such that true triples score higher than false ones, and measures how well that recovers held-out links, on a standard benchmark and on this graph.

References

  • Agarwal, O., Ge, H., Shakeri, S., and Al-Rfou, R. (2021). Knowledge graph based synthetic corpus generation for knowledge-enhanced language model pre-training. In Proceedings of NAACL-HLT 2021, 3554–3565. doi:10.18653/v1/2021.naacl-main.278. record
  • Angles, R., Arenas, M., Barceló, P., Hogan, A., Reutter, J., and Vrgoč, D. (2017). Foundations of modern query languages for graph databases. ACM Computing Surveys, 50(5), 1–40. doi:10.1145/3104031. arXiv:1610.06264. record
  • Bordes, A., Usunier, N., Garcia-Durán, A., Weston, J., and Yakhnenko, O. (2013). Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26, 2787–2795. record · 3 pages
  • Chandra, A. K., and Merlin, P. M. (1977). Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the Ninth Annual ACM Symposium on Theory of Computing (STOC '77), 77–90. doi:10.1145/800105.803397. record
  • Edge, D., Trinh, H., Cheng, N., Bradley, J., Chao, A., Mody, A., Truitt, S., Metropolitansky, D., Ness, R. O., and Larson, J. (2024). From local to global: A graph RAG approach to query-focused summarization. arXiv:2404.16130. record · 2 pages
  • Gruber, H., and Holzer, M. (2014). From finite automata to regular expressions and back—a summary on descriptional complexity. In Automata and Formal Languages 2014 (AFL 2014), Electronic Proceedings in Theoretical Computer Science 151, 25–48. doi:10.4204/EPTCS.151.2. arXiv:1405.5594. record
  • He, X., Tian, Y., Sun, Y., Chawla, N. V., Laurent, T., LeCun, Y., Bresson, X., and Hooi, B. (2024). G-Retriever: Retrieval-augmented generation for textual graph understanding and question answering. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024). arXiv:2402.07630. record
  • Hogan, A., Blomqvist, E., Cochez, M., d'Amato, C., de Melo, G., Gutierrez, C., Kirrane, S., Labra Gayo, J. E., Navigli, R., Neumaier, S., Ngonga Ngomo, A.-C., Polleres, A., Rashid, S. M., Rula, A., Schmelzeisen, L., Sequeda, J., Staab, S., and Zimmermann, A. (2021). Knowledge graphs. ACM Computing Surveys, 54(4), 1–37. doi:10.1145/3447772. arXiv:2003.02320. record · 2 pages
  • Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations, 85–103. doi:10.1007/978-1-4684-2001-2_9. record
  • Mendelzon, A. O., and Wood, P. T. (1989). Finding regular simple paths in graph databases. In Proceedings of the 15th International Conference on Very Large Data Bases (VLDB 1989), 185–193. record
  • Pérez, J., Arenas, M., and Gutierrez, C. (2006). Semantics and complexity of SPARQL. In The Semantic Web: ISWC 2006, Lecture Notes in Computer Science 4273, 30–43. doi:10.1007/11926078_3. arXiv:cs/0605124. record
  • W3C (2013). SPARQL 1.1 Query Language. W3C Recommendation, 21 March 2013. https://www.w3.org/TR/sparql11-query/ record
  • W3C (2014). RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation, 25 February 2014. https://www.w3.org/TR/rdf11-concepts/ record