Course / Act III · The five interfaces / Lectures Lecture 09

Logic as data.

A knowledge graph is a set of triples with holes in it. A query is a path that may not exist. This lecture treats the symbolic structure as data — something a model reads, writes, completes, and queries — and asks what that buys, and what it costs.

~45 min read Lecture 04 first 4 embedding families 1 link-prediction lab Updated 2026-11-17

Lectures 07 and 08 kept the symbolic object inside the model: a penalty on the output, then an executor in the computation graph. This lecture takes the other stance. The logical object is outside the model — a knowledge graph, an ontology, a rule set — and the model reads, completes, or queries it. The interface is the data structure.

00 / The hookA graph, a hole, and a query.

Start with four triples and one question. Mira was born in Ashford, Ashford is in Avalon, Mira works at Atlas Lab, and Atlas Lab is in Ashford. Which country should be printed on Mira's passport? No single triple answers it. The answer is a path: Mira → bornIn → Ashford → locatedIn → Avalon. A second path reaches the same country through her employer. The structure, not any one row, carries the answer.

A small typed knowledge graph with a two-hop query path Mira is connected to Ashford by bornIn and to Atlas Lab by worksAt. Ashford and Atlas Lab are both connected to Avalon by locatedIn and orgIn. A dashed edge marks a missing link, citizenOf. The query asks for the country reached by two paths. person city relation missing / queried bornIn worksAt locatedIn orgIn citizenOf? query path Mira Ashford Atlas Lab Avalon country two paths reach the same country; the dashed triple is not in the graph
Fig. 0.1 A typed graph drawn as a schematic. The query citizenOf(Mira, ?) is answered by following bornIn then locatedIn, or worksAt then orgIn then locatedIn. The graph does not store the answer; it stores the structure that makes the answer reachable.

The symbols are not a constraint on a vector, nor a program inside a network. They are a data structure: typed nodes and edges that a learner can consume, a symbolic engine can query, or both can share. The lecture covers the three operations — embed, induce, query — and their price.

Definition · logic as data

A system uses logic as data when the symbolic structure — triples, classes, rules, or a query — is the input or the output of learning, rather than a penalty on a network's output or an executor inside its computation graph. The model's parameters score, complete, or select structures; the structure remains a first-class artifact that can be inspected, versioned, and queried on its own.

Two tasks recur. Link prediction asks how likely a missing edge is; query answering asks for all assignments that make a pattern true. The first is scoring, the second is search. Confusing them is common; §4 returns to it.

Caveat · the graph is a model, not the world

Every knowledge graph is partial, dated, and sourced. A missing edge may mean “false”, “unknown”, “not worth storing”, or “stored under a different identifier”. The semantics of absence is a design decision, and it changes what a model's score means. Treat a triple as a claim with provenance, not as a fact about the world.

01 / Graphs & ontologiesTriples, types, and the open world.

A knowledge graph is a set of triples over entities and relations. Formally, G ⊆ E × R × E. Each triple (h, r, t) says that relation r holds between head h and tail t. The graph is directed and multi-relational: two entities can share several relations, and a relation can connect many pairs.

G ⊆ E × R × E,    (h, r, t) ∈ G  means  r(h, t)
(1.1)

RDF, property graphs, and Wikidata encode the same object with different storage conventions — IRIs and literals, labels and key–value properties, qualifiers and references. For this lecture, the triple is the unit.

Relations are not just labels. They have a signature — a domain and a range — and logical properties: spouse is symmetric, ancestorOf is transitive, capitalOf is functional, and hasParent has an inverse. A graph that stores only edges is a bag of facts. A graph with these declarations is a small theory.

The schema and the assertions

An ontology separates two layers. The TBox is the terminology: which classes exist, which relations connect them, and which axioms hold. The ABox is the set of assertions about individuals. The distinction is the description-logic distinction between the schema and the data, and it is the difference between “every employee is a person” and “Mira is an employee”.

Here is a small TBox in description-logic notation. It says that every person was born in some city; every employee is a person; worksAt is a sub-role of employedBy; and no entity is both a person and an organization.

Person ⊑ ∃bornIn.City  ·  Employee ⊑ Person  ·  worksAt ⊑ employedBy  ·  Person ⊓ Organization ⊑ ⊥
(1.2)

The ABox contains Employee(Mira), worksAt(Mira, Atlas), and Organization(Atlas). From the TBox and the ABox, a reasoner entails Person(Mira) and employedBy(Mira, Atlas). It also entails that Mira has some birthplace, because Person ⊑ ∃bornIn.City; but it does not entail which city. That gap between “there exists” and “here is the name” is the open world in miniature.

TBox and ABox as two layers of a knowledge base The upper layer holds classes and axioms: Person, Employee, City, Organization, subsumption, domain and range, and disjointness. The lower layer holds individuals and asserted triples: Mira, Atlas, Ashford, and their relations. Dashed lines show instantiation. TBOX · terminology ABOX · assertions Person Employee ⊑ City Organization bornIn → domain(worksAt) = Person range(worksAt) = Organization domain(bornIn) = Person range(bornIn) = City Person ⊓ Organization ⊑ ⊥ Mira Ashford Atlas Lab bornIn worksAt Employee City Organization
Fig. 1.1 A schematic of the two layers. The TBox states what can exist and how it may connect; the ABox states what does exist. Reasoning can derive new ABox facts from the TBox, but the TBox never names the individuals it quantifies over.

Open world, closed world

The closed-world assumption says: if a triple is not in the database, it is false. That is the default in SQL, in Datalog, and in most business systems. The open-world assumption says the opposite: if a triple is not in the graph, its truth is unknown. Knowledge graphs and ontologies usually adopt the open world, because they are built to be extended and because absence of evidence is not evidence of absence.

The choice changes what an answer means. Under the closed world, an absent citizenOf(Mira, Avalon) is false, so a query returns the stored facts. Under the open world, it may be true but unrecorded, so a query returns the certain answers — facts true in every model. Negative sampling quietly assumes the closed world: a corrupted triple is a negative. That is an approximation, not a theorem.

Table 1.1 · Three ways to store structure, and what each one assumes.
ArtifactWhat it storesSemantics of absenceTypical query
Relational databaseRows with a fixed schemaClosed: absent = falseSQL join, aggregation
Knowledge graphTyped triples, often with provenanceOpen: absent = unknownPattern match, path, link prediction
OntologyTBox axioms plus an ABoxOpen: models, not rowsEntailment, instance retrieval, consistency

This is why knowledge-graph completion is a ranking problem rather than a classification problem: the model cannot certify a missing edge as false, so it ranks plausible completions and leaves the decision downstream. It is also why evaluation is hard: the test set is a sample of edges that happened to be recorded.

Caveat · schema drift and identity

Real graphs change their schema: properties are renamed or deprecated, identifiers merge, domains widen. sameAs links are themselves uncertain. A model trained on last year's graph may score a vocabulary that no longer exists. Version the schema and test the graph, not only the model.

02 / Graph embeddingsScore the missing triple.

The first way to make a graph usable by a neural model is to give every entity and relation a vector and define a score for a triple. Training pushes true triples up and corrupted ones down. This is knowledge-graph embedding; its standard task is link prediction.

Let eh, et ∈ ℝd be entity vectors and rr ∈ ℝd a relation vector. A scoring function fr(h, t) maps a triple to a real number. The models differ in the algebra, and the algebra determines which relational patterns the model can represent.

TransE: a relation is a translation

TransE (Bordes et al., 2013) makes the relation a translation in the same space as the entities. The score is the negative distance between the translated head and the tail:

fr(h, t) = −‖eh + rr − et‖2
(2.1)

A true triple has eh + rr ≈ et, so its score is near zero; a false triple's distance is large.

Worked example. Let eMira = (1, 0), eAshford = (0, 1), and rbornIn = (−1, 1). Then eMira + r = (0, 1) = eAshford, so the score is 0. For the corrupted tail Bellmere = (1, 1), the distance is 1 and the score is −1. For Cinder = (0, −1), the distance is 2 and the score is −2. The ranking is Ashford, Bellmere, Cinder; training pushes the first distance down and the others up.

What TransE cannot do. Suppose r is symmetric: both (h, r, t) and (t, r, h) are true. A perfect representation needs eh + r = et and et + r = eh. Adding them gives 2r = 0, so r = 0 and eh = et: every symmetric pair collapses to one point. The same algebra makes 1-to-N relations hard, because one head plus one relation can only land near one tail.

DistMult and ComplEx: bilinear scores

DistMult (Yang et al., 2014) replaces the translation with a trilinear product. Each relation has a diagonal matrix, and the score is the sum of the coordinate-wise product:

fr(h, t) = Σi=1d eh[i] · rr[i] · et[i]
(2.2)

The score is symmetric in h and t: swapping them gives the same number. That is good for spouse and bad for parentOf. DistMult cannot distinguish a relation from its inverse, so it cannot represent antisymmetric relations exactly.

ComplEx (Trouillon et al., 2016) fixes this by moving to complex numbers and conjugating the tail:

fr(h, t) = Re( Σi=1d eh[i] · rr[i] · et[i] )
(2.3)

The conjugate breaks the symmetry: a relation can score (h, r, t) and (t, r, h) differently, so ComplEx can model antisymmetric and inverse relations. Trouillon et al. show that, with enough dimensions, ComplEx is fully expressive: it can represent any assignment of truth values to triples. The cost is parameters and a less intuitive geometry.

RotatE: a relation is a rotation

RotatE (Sun et al., 2019) keeps entities and relations in complex space but constrains each relation coordinate to have modulus one. A relation is a rotation of the head in each complex plane, and the score is the distance after the rotation:

fr(h, t) = −‖eh ∘ rr − et‖,    |rr[i]| = 1
(2.4)

Each relation coordinate is ri = eiθi, a phase. Symmetry is θ = 0 or π; inversion negates the phase; composition adds phases. In one complex dimension, r = −1 swaps head and tail, so both directions hold. TransE needs r = 0 and eh = et; RotatE needs a half-turn.

The constraint |ri| = 1 is not cosmetic. It makes each relation a bijection on the complex plane, which lets rotations compose cleanly. It also limits expressiveness: a rotation maps one head to one point, so a genuinely one-to-many relation can only be approximated by placing several tails near the rotated point.

TransE translation versus RotatE rotation in two dimensions On the left, a head point plus a relation vector lands on a tail point. On the right, a relation rotates the head around the origin by an angle to land on the tail. The left panel shows a translation; the right panel shows a complex-plane rotation. TransE · translation RotatE · rotation h t r e_h + r ≈ e_t h t θ e_h ∘ e^{iθ} ≈ e_t
Fig. 2.1 A schematic of the two geometries. TransE adds a vector; RotatE multiplies by a unit complex number, which is a rotation. The rotation can represent a symmetric relation with a half-turn; the translation cannot, because a non-zero translation cannot undo itself.

R-GCN: an encoder over a multi-relational graph

TransE, DistMult, ComplEx, and RotatE learn one vector per entity. That is transductive: a new entity requires a new row and a retraining. An encoder such as R-GCN (Schlichtkrull et al., 2017) instead computes an entity's representation from its neighbours, using a different weight matrix per relation:

hi(l+1) = σ( Σr∈R Σj∈Nir (1/ci,r) Wr(l) hj(l) + W0(l) hi(l) )
(2.5)

This is message passing with relation-specific messages; the normalization ci,r keeps high-degree nodes from dominating. Basis decomposition, Wr = Σb arb Vb, shares parameters across relations. For link prediction, a decoder such as DistMult scores the encoded vectors. Because the representation is computed from neighbours, the model can in principle score an unseen entity — the inductive setting.

Table 2.1 · Five scoring functions and the relational patterns their algebra allows. “Exact” means the model can represent the pattern with zero loss; approximations are always possible.
ModelScoreSymmetricAntisymmetricInverseComposition
TransE−‖eh + r − et‖No (r = 0)YesYesYes
DistMultΣ eh · r · etYesNoNoNo
ComplExRe(Σ eh · r · et)YesYesYesLimited
RotatE−‖eh ∘ r − et‖, |ri| = 1Yes (θ = 0, π)YesYesYes (θ1 + θ2)
R-GCN + DistMultDistMult on encoded vectorsYesNoNoVia depth

The training objective: negative sampling

A knowledge graph stores positive triples only. Training needs negatives, so each positive is corrupted by replacing the head or tail with another entity, and the corrupted triple is assumed false. The standard objective is a logistic loss with margin γ and k negatives per positive:

L = −log σ(γ − dr(h, t)) − Σj=1k log σ(dr(h′j, t′j) − γ)
(2.6)

The distance is the score negated; the first term wants it small, the second wants each negative distance large.

Worked example. Take γ = 1, a positive with dpos = 0.2, and a negative with dneg = 1.4. The positive term is −log σ(0.8) ≈ 0.371; the negative term is −log σ(0.4) ≈ 0.513; the total is 0.884. Push the negative to 2.4 and its term falls to −log σ(1.4) ≈ 0.220, for a total of 0.591. Training increases the negative distance and decreases the positive one.

TransE's original objective was a margin ranking loss; the logistic form above is the smoother modern variant.

How to read the numbers

Report MRR and Hits@k, and state whether the ranking is filtered. An unfiltered ranking is harsher and less comparable.

MRR = (1/|Q|) Σq∈Q 1/rank(q),    Hits@k = (1/|Q|) Σq∈Q 1[rank(q) ≤ k]
(2.7)
Caveat · the benchmark may be easier than it looks

Sun et al. (2020) re-evaluated knowledge-graph completion and found that inverse relations and filtered ranking can inflate scores: a model can succeed by learning the reverse of a relation it saw in training, or by exploiting test leakage. Report the split, the filtering rule, and the negative-sampling scheme. A higher MRR in a different setting is not a comparison.

03 / Rule miningThe regularities the graph already contains.

An embedding is one way to compress a graph. A rule is another. A rule says that a pattern in the body implies a pattern in the head, for every substitution of its variables. In relational form, the simplest useful rule has two body atoms and one head atom:

r(x, z) ← b1(x, y) ∧ b2(y, z)
(3.1)

The rule says: a b1 edge from x to some y and a b2 edge from that y to z imply an r edge from x to z. The shared y is the join. In a knowledge graph, citizenOf(x,z) ← bornIn(x,y) ∧ locatedIn(y,z) is the path from Fig. 0.1. Rule mining searches for such patterns and for a number that says how often they hold.

A Horn clause is the logical form; a logic program is a set of them; Datalog is the fragment with no function symbols and a least-fixpoint semantics. Recursive rules such as ancestorOf(x,z) ← parentOf(x,y) ∧ ancestorOf(y,z) compute a transitive closure and give reachability for free. Rule mining is the inductive direction: the rules are discovered, not given.

Support and confidence

Two numbers summarize a rule. The support is the number of distinct pairs (x, z) for which body and head both hold. The confidence is support divided by the number of pairs for which the body holds: how often the prediction is right. Head coverage divides support by the number of head facts, and says what fraction of the target relation the rule explains.

supp(r) = |{(x,z) : ∃y. b1(x,y) ∧ b2(y,z) ∧ r(x,z) ∈ G}|
(3.2)
conf = supp / |{(x,z) : ∃y. b1(x,y) ∧ b2(y,z)}|   ·   hc = supp / |{r(x,z) ∈ G}|
(3.3)

Worked example. Ten people, each born in a city, each city in a country, each person with a citizenOf fact. Nine were born in the country of their citizenship; Quinn was born in Avalon but is a citizen of Borealis. For citizenOf(x,z) ← bornIn(x,y) ∧ locatedIn(y,z), the body holds for ten pairs and the head for nine. Support is 9, confidence is 0.9, head coverage is 9/10. The rule is strong but not perfect, and the exception is exactly what a downstream system needs to know about.

Table 3.1 · Three rules on the same toy graph. The confidence column is not a ranking; a rule with confidence 1.0 and support 2 says almost nothing about a new entity.
RuleSupportBodyConfidenceHead coverage
citizenOf(x,z) ← bornIn(x,y) ∧ locatedIn(y,z)9100.900.90
citizenOf(x,z) ← worksAt(x,o) ∧ orgIn(o,y) ∧ locatedIn(y,z)8100.800.80
worksAt(x,o) ← bornIn(x, ashford) ∧ orgIn(o, ashford)221.000.20

The third rule looks perfect, but it only fires for people who have a spouse in the graph. If the target is unmarried, the rule is silent, not wrong. Confidence measures precision when the rule fires; head coverage measures how much of the relation it covers. A rule with confidence 1.0 and support 2 may be a coincidence; confidence 0.8 with support 800 is a regularity.

AMIE and the open-world correction

AMIE (Galárraga et al., 2013) is the standard rule miner for knowledge graphs. It searches under a language bias — which relations may appear where — starts from rules with an empty body, and extends them with atoms that share exactly one variable. It prunes below a support or confidence threshold. The bias is the main engineering decision: a permissive bias explodes; a restrictive one misses rules.

AMIE also corrects for the open world with partial completeness assumption (PCA) confidence. Standard confidence counts every absent predicted head triple as a false positive; under the open world that is too harsh. PCA confidence counts a prediction as a potential positive unless the graph contradicts it for the same subject or object. The effect is less pessimistic confidence on sparse graphs, at the cost of assuming that what is absent is probably true.

Neural LP (Yang, Yang & Cohen, 2017) makes rule learning differentiable. A rule is a sequence of relations; the model performs forward chaining over a relation tensor, with weights on the rules, and learns the weights by gradient descent. A low-rank approximation keeps the rule set manageable. The output is a readable set of weighted rules — an inductive learner in the knowledge base.

Rule mining is the binary-relation case of inductive logic programming (ILP). Classical systems such as FOIL and Progol search a refinement lattice of clauses, guided by examples and background knowledge. They learn recursive programs with function symbols, which Datalog-style miners cannot; the price is search and the need for predicate declarations.

Caveat · a rule is a correlation with a grammar

Support and confidence do not establish causation or transfer. A rule mined on one graph may encode an artifact: a relation populated by the same script as its “consequence”, a temporal coincidence, a naming convention. Hold out edges, mine on one split, test on another, and report support on the test split.

04 / Query answeringFrom one triple to a pattern.

Link prediction scores one triple. Query answering asks a question with variables and returns every assignment that makes the question true. The standard language is the conjunctive query: a conjunction of atoms with existential quantifiers, and a distinguished set of answer variables.

q(x) ← ∃y,z. bornIn(x,y) ∧ locatedIn(y,z) ∧ z = Avalon
(4.1)

The query asks which people were born in a city in Avalon. The answer is the set of constants a such that the formula holds when x is replaced by a. On a graph, evaluation is a subgraph homomorphism problem: map the query's variables to entities so that every atom is true. It is NP-complete in combined complexity, so query planning matters even for modest graphs.

A path query adds regular expressions over relations: bornIn / locatedIn, or parentOf+ for one or more steps. Path queries are evaluated by automata and are tractable for a fixed query, which is why they are the workhorse of graph databases. Recursive Datalog goes further: transitive closure and mutual recursion, with a least fixpoint that guarantees termination. Recursion plus negation can become non-stratified, and then the answer is no longer unique.

Certain answers and incomplete graphs

Under the open world, an answer is not “the matches in the graph” but the tuples that hold in every model of the graph and ontology — the certain answers. If the graph does not say whether Mira was born in Ashford or Bellmere, a query for her birthplace has no certain answer, even though both are plausible. Returning the top-scoring candidate is link prediction, not certain-answer query answering, and the difference is the semantics.

With an ontology, query answering gets harder. A TBox can entail facts absent from the ABox, so an engine must materialize the consequences (compute once, store, pay the update cost) or rewrite the query into a form answerable over the raw data (pay the query cost, accept partial rewritings). ALC with a general TBox is ExpTime-complete; the OWL 2 EL and RL profiles are tractable fragments built for preprocessing.

Queries as vectors

The embedding approach represents the query itself as a vector or region and scores entities in the same space. Hamilton et al. (2018) project entities through relation vectors and intersect the results. Query2box (Ren, Hu & Leskovec, 2020) uses axis-aligned boxes: projection maps the box, intersection takes the overlap, union takes the union. BetaE (Ren & Leskovec, 2020) uses beta distributions, adding negation.

These models train on query–answer pairs from the graph and can answer unseen shapes if they decompose into trained operators. They are not symbolic engines. A two-hop query composes two relation vectors only if training taught that composition; the geometry does not close under composition for free.

Table 4.1 · Three tasks that are easy to conflate. They have different inputs, outputs, and guarantees.
TaskInputOutputGuarantee
Triple scoringOne candidate (h, r, t)A scoreNone; a ranking heuristic
Link predictionA query (h, r, ?) and a candidate setA ranked list of tailsEmpirical, measured by MRR / Hits@k
Query answeringA pattern with variables and a graphA set of assignmentsSound and complete for the given semantics

The practical architecture is often a hybrid: a language model proposes a query in SPARQL, Cypher, or Datalog, a symbolic engine executes it, and a verifier checks the result. The model's output is a query; the data structure decides whether the answer is right.

Caveat · a link score is not an answer

A model that ranks citizenOf(Mira, Avalon) highly has not answered “which country does Mira belong to?”. It has scored one candidate. The query answer is a set, and its correctness depends on the semantics — certain answers under the open world, or matches under the closed world. Report which one you mean.

05 / Structure as dataThree ways a neural model consumes a graph.

Once the graph is a data structure, a neural model can consume it as input, as memory, or as output. The distinction determines what the model can generalize to and what it can be held responsible for.

The graph as input

A graph neural network computes representations by message passing. R-GCN is the multi-relational case: each edge type has its own transformation, and a node's representation sums its neighbours' messages. The architecture is permutation-invariant, handles variable degree, and trains end-to-end with a link-prediction or node-classification loss. Its limit is locality: after L layers a node has seen its L-hop neighbourhood, and depth brings over-smoothing and over-squashing.

The alternative is relational feature engineering: degree, path counts, centrality, rule confidence, neighbour types — fed to a standard classifier. It is less fashionable and often stronger on small graphs, because the features are interpretable and the model has fewer parameters. Learned message passing versus engineered features is a bias–variance choice, not a maturity ladder.

The graph as memory

A graph can be an external memory read at inference time. Retrieval-augmented generation (Lewis et al., 2020) retrieves passages; a knowledge-graph version retrieves entities, triples, or paths and conditions the answer on them. The retrieval does the grounding; the model does the fluent composition. The failures are familiar: entity-linking errors, a true but irrelevant path, and a model that ignores the evidence in favour of its parameters.

This is the interface most visible in products, and the easiest to evaluate badly, because a fluent answer can hide a wrong retrieval. Log the retrieved triples and the model's citation of them; an answer without provenance is not a graph-grounded answer.

The graph as output

The graph can also be the output: missing triples, new rules, or new schema axioms. Link prediction is the smallest case; rule mining is the symbolic case; ontology completion is the schema case, predicting a subclass edge, a domain restriction, or a disjointness axiom. The output can be checked by a reasoner before it is committed — the advantage of making it symbolic rather than a score.

The patterns compose: a GNN encodes the graph, a retrieval step selects a subgraph, and a decoder emits triples or rules that an engine checks. The interface is a pipeline whose joints are all data structures.

Source note · what is standard, what is a position

The score functions, the negative-sampling loss, and the rule metrics are standard definitions. That relational features are often stronger on small graphs is a position supported by practice, not a single benchmark. That retrieval is the most product-visible interface is a 2026 observation, not a theorem.

06 / What it buys & costsThe honest ledger.

Treating structure as data is a trade, not a free upgrade. The table lists what the interface buys and what it costs, with the check that keeps each claim honest.

Table 6.1 · The data interface, in one table. The right column is the test that turns a claim into evidence.
What it buysWhat it costsWhat to check
Inspectable structure: triples, paths, rulesA path can be post-hoc, not the model's reasonDoes the explanation change when the prediction changes?
Knowledge reuse across tasks and teamsSchema drift, entity resolution, version skewIs the schema versioned? Are identifiers stable?
Data efficiency: a fact is stated onceIncompleteness and open-world ambiguityWhat is the coverage on the target relation?
Compositional queries over pathsQuery cost; embedding composition is not freeDoes the model generalize to unseen query shapes?
Local updates without retrainingEmbedding distortion; stale vectorsHow quickly does a new fact change the score?
Provenance and auditabilityProvenance is expensive to store and easy to loseCan you trace every answer to a source?

The first row deserves the most skepticism. A path is interpretable — a human can read it — but not necessarily faithful to the model that produced the prediction. An embedding can rank a triple highly for reasons unrelated to the path a human would draw. Interpretability is a property of the explanation's relation to the computation, not of the notation.

The second row is the maintenance bill. Knowledge graphs are living artifacts: relations are added, entities are merged, the world changes. An embedding trained on last month's graph is a snapshot; a rule mined on it may be a fossil. Production systems have an update path — incremental training, re-mining, versioned schemas — and a way to detect drift.

The evaluation bill belongs here too: because the graph is incomplete, a benchmark samples recorded edges, not true edges. A model can look good by learning which edges a curation process recorded. Sun et al. (2020) warn that inverse relations and filtered ranking can make a simple model look strong.

Caveat · embeddings distort

A d-dimensional vector cannot preserve every relation. The algebra decides which patterns survive: TransE loses symmetry, DistMult loses antisymmetry, RotatE's rotations are bijections. The distortion is a systematic bias, not random noise. If a decision depends on a relation the model cannot represent, more training will not fix it.

07 / Six casesOne interface, six mechanisms.

The cases are mechanisms, not benchmark claims. Read each along the tuple from Lecture 01: symbolic structure, neural part, interface, guarantee.

Table 7.1 · The six cases, read along the interface tuple.
CaseSymbolic structureNeural partInterfaceGuarantee
Link predictionTriplesEmbedding tableScore functionEmpirical
AMIERulesNoneSearch over structuresNone; support is descriptive
Neural LPWeighted rulesDifferentiable chainingInduction as optimizationEmpirical
Query embeddingsQuery patternQuery encoderComposition in vector spaceEmpirical
RetrievalTriples / pathsRetriever + readerExternal memoryNone; provenance required
Ontology completionTBox axiomsClassifier / embeddingStructure as outputCheckable by a reasoner

The table makes the pattern visible. The strongest guarantee belongs to ontology completion, where a reasoner can reject an inconsistent axiom. The weakest belongs to retrieval, where the model can ignore the evidence and still be fluent. Link prediction and query embeddings sit in between: empirical, and dependent on a split that is easy to leak.

08 / RecapWhat you should be able to do now.

01

Define a knowledge graph as a set of typed triples, and distinguish the TBox from the ABox.

02

Explain the open-world assumption and why it turns completion into ranking rather than classification.

03

Write the TransE, DistMult, ComplEx, and RotatE score functions, and name the pattern each one cannot represent.

04

Derive the negative-sampling logistic loss and explain the role of the margin and the corrupted triples.

05

Compute support, confidence, and head coverage for a rule on a small graph, and say why confidence alone is not enough.

06

Distinguish link prediction from query answering, and say what a certain answer requires.

07

Name the three ways a neural model consumes a graph: input, memory, output.

08

State the main costs: incompleteness, schema drift, embedding distortion, and evaluation leakage.

Exercises

  1. Break symmetry. Prove that TransE cannot represent a non-trivial symmetric relation, as in §2.1. Then construct a one-dimensional RotatE representation of spouse and verify both directions.
  2. Rule metrics. On a graph of six people, write three rules for citizenOf and compute support, confidence, and head coverage for each. Which would you trust on a new person, and why?
  3. Query or score? Write a conjunctive query for “people who work in the country where they were born”. Explain why a link predictor that scores worksAt triples cannot answer it without a join.
  4. Lab comparison. In the lab, train TransE and RotatE on the same graph and compare the rank of the held-out spouse fact. Does the symmetry argument predict the result? Report the actual ranks.
  5. Design a graph. Choose a domain you know. Specify ten relations, their signatures, three TBox axioms, and three rules. Then list three ways the graph could be wrong.

Check your understanding

Ten questions, with explanations. The score is not the point; the ones you cannot answer are the reading list.

Reading list

The first four are the spine; the rest are the next layer.

Knowledge Graphs

Hogan et al. · ACM Computing Surveys 2021 · the field’s reference map

Survey

Translating Embeddings for Modeling Multi-relational Data

Bordes et al. · NeurIPS 2013 · TransE, the translation model

Embeddings

Complex Embeddings for Simple Link Prediction

Trouillon et al. · ICML 2016 · ComplEx and full expressiveness

Embeddings

RotatE: Knowledge Graph Embedding by Relational Rotation

Sun et al. · ICLR 2019 · rotations and the pattern trade-offs

Embeddings

Modeling Relational Data with Graph Convolutional Networks

Schlichtkrull et al. · ESWC 2018 · R-GCN and relational message passing

GNN

AMIE: Association Rule Mining under Incomplete Evidence

Galárraga et al. · WWW 2013 · support, confidence, PCA confidence

Rules

Differentiable Learning of Logical Rules for Knowledge Base Reasoning

Yang, Yang & Cohen · NeurIPS 2017 · Neural LP

Rules

Embedding Logical Queries on Knowledge Graphs

Hamilton et al. · NeurIPS 2018 · queries as vectors

Queries

Query2box: Reasoning over Knowledge Graphs in Vector Space

Ren, Hu & Leskovec · ICLR 2020 · boxes, intersection, union

Queries

A Re-evaluation of Knowledge Graph Completion Methods

Sun et al. · ACL 2020 · inverse relations, leakage, and honest numbers

Evaluation

Retrieval-Augmented Generation for Knowledge-Intensive NLP

Lewis et al. · NeurIPS 2020 · the graph-as-memory interface

Retrieval

Beta Embeddings for Multi-Hop Logical Reasoning

Ren & Leskovec · NeurIPS 2020 · negation and probabilistic queries

Queries
Source note · what is redrawn

Figures 0.1, 1.1, and 2.1 are schematic redrawings, not reproductions; the drawings are ours. The worked numbers in §2 and §3 are computed by hand on a toy graph; the lab reports only what its own run produces.