Lecture 09 · The five interfaces

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 is the interface where the symbolic structure is the thing a model reads, completes, and queries.

21 lectures in the arc 4 embedding families 1 link-prediction lab Self-paced
00 · Learning objectivesLecture 09 · Logic as data

By the end of this lecture

Four things you can do.

01

Read a knowledge graph

Separate the TBox from the ABox, and explain what the open world does to an answer.

02

Score a missing triple

Write the TransE, ComplEx, and RotatE scores, and say which pattern each one cannot represent.

03

Mine and compare rules

Compute support, confidence, and head coverage, and explain why confidence alone is not enough.

04

Separate queries from scores

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

S/V · Lecture 09
00 · The hookLecture 09 · Logic as data

A graph with a hole

The answer is a path.

bornIn worksAt locatedIn orgIn citizenOf? Mira Ashford Atlas Lab Avalon country
Schematic. Two paths reach Avalon; the dashed triple is not stored.

No single triple answers the query. Born in Ashford, Ashford in Avalon gives one path; works at Atlas, Atlas in Ashford gives another.

A triple store is a partial model. The structure, not any one row, carries the answer — and the structure can be read by a symbolic engine or a neural scorer.

citizenOf(x,z) ← bornIn(x,y) ∧ locatedIn(y,z)

S/V · Lecture 09
00 · The hookLecture 09 · Logic as data

Two tasks, easily confused

A query is not a nearest neighbour.

Link prediction

score(h, r, t) → ℝ

One candidate triple. A ranking. No guarantee that the edge is true — only that it is plausible.

Query answering

q(x) ← ∃y. r₁(x,y) ∧ r₂(y,z)

A pattern with variables. A set of assignments. Under the open world, the certain answers.

The query needs a join. A scorer that ranks one triple at a time has not answered it. Composition is a separate operation, and it is where the interface earns its name.
S/V · Lecture 09
01 · Graphs & ontologiesLecture 09 · Logic as data
01 / 08

Triples, types, and the open world.

What a knowledge graph stores, what an ontology adds, and why absence is a design decision.

S/V · Lecture 09
01 · Graphs & ontologiesLecture 09 · Logic as data

The unit

A graph is a set of typed triples.

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

Entities

People, cities, countries, organisations, proteins. The nodes. They have identifiers, not just names.

Relations

Typed, directed edges. Each has a signature: a domain and a range, plus properties such as symmetric or transitive.

Triples

The assertions. RDF, property graphs, and Wikidata all encode them; the storage differs, the unit does not.

RelationDomainRangeProperty
bornInPersonCity—
locatedInCityCountrytransitive
spousePersonPersonsymmetric
S/V · Lecture 09
01 · Graphs & ontologiesLecture 09 · Logic as data

An ontology has two layers

Schema above, assertions below.

TBox · terminology
Person ⊑ ∃bornIn.City
Employee ⊑ Person
worksAt ⊑ employedBy
Person ⊓ Organization ⊑ ⊥

Classes, roles, subsumption, disjointness. The schema says what can exist and how it may connect.

ABox · assertions
Employee(Mira)
worksAt(Mira, Atlas)
Organization(Atlas)
bornIn(Mira, Ashford)

Individuals and facts. The reasoner derives Person(Mira) and employedBy(Mira, Atlas).

What the TBox cannot do: it entails that Mira has some birthplace. It does not entail which city. That gap is the open world in miniature.
S/V · Lecture 09
01 · Graphs & ontologiesLecture 09 · Logic as data

The semantics of absence

Absence is not falsity.

Closed world

If a triple is absent, it is false. The default in SQL and Datalog. A query returns the stored facts.

¬stored ⇒ ¬true

Open world

If a triple is absent, its truth is unknown. The default for knowledge graphs. A query returns the certain answers.

absent ⇒ unknown

Negative sampling quietly assumes the closed world. A corrupted triple is treated as negative. That is a training approximation, not a semantic claim. In a dense graph, a corruption can hit a true fact.
S/V · Lecture 09
02 · Graph embeddingsLecture 09 · Logic as data

TransE · 2013

A relation is a translation.

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

h t t′ r d′ > 0
The true tail is near e_h + r; a corrupted tail is farther.
Cheap and strong on hierarchies. The score is a distance, so training is a push-and-pull on points.
Symmetry is impossible. If e_h + r = e_t and e_t + r = e_h, then 2r = 0, so r = 0 and e_h = e_t.

1-to-N relations suffer too: one head plus one relation lands near one tail.

S/V · Lecture 09
02 · Graph embeddingsLecture 09 · Logic as data

Bilinear scores

Symmetry is a choice, not a default.

ModelScoreCan doCannot do
DistMultΣ eh · r · etsymmetric relationsantisymmetric, inverse
ComplExRe(Σ eh · r · et)symmetric and antisymmetriccomposition (limited)
The conjugate is the trick. Conjugating the tail breaks the symmetry: (h, r, t) and (t, r, h) can score differently.
Full expressiveness, at a price. With enough dimensions, ComplEx can represent any truth assignment to triples. The cost is parameters and a geometry that is harder to read.

DistMult is the diagonal special case. Its symmetry is a feature for spouse and a bug for parentOf.

S/V · Lecture 09
02 · Graph embeddingsLecture 09 · Logic as data

RotatE · 2019

A relation is a rotation.

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

h t θ −h
A half-turn (θ = π) swaps two points — a symmetric relation.
Patterns by phase. Symmetry: θ = 0 or π. Inversion: negate the phase. Composition: add phases.
The limit is the bijection. A rotation maps one head to one point, so a genuinely one-to-many relation is approximated, not represented.
S/V · Lecture 09
02 · Graph embeddingsLecture 09 · Logic as data

The objective

Train against corrupted triples.

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

1 · corrupt

Replace the head or the tail with another entity. Assume the corrupted triple is negative.

2 · margin

Push the positive distance below γ and each negative above it. k negatives per positive.

3 · gradient

Decrease the positive distance, increase the negative distances. Normalize entity vectors to keep the space bounded.

Worked numbers. γ=1, dpos=0.2, dneg=1.4 gives 0.371 + 0.513 = 0.884. Push the negative to 2.4 and the total falls to 0.591.
Corrupted is not false. Under the open world, a corruption can be a true fact. Filter known positives from the candidate set before ranking.
S/V · Lecture 09
02 · Graph embeddingsLecture 09 · Logic as data

Reading the numbers

The benchmark can be easier than it looks.

MRR = mean(1/rank)  ·  Hits@k = P(rank ≤ k)

Raw

Rank against every entity. Harsher; the true answer competes with other true facts.

Filtered

Remove other true triples from the candidate list. Standard, and easier to inflate.

Leakage

Inverse relations and test edges can make a simple model look strong. Report the split.

Sun et al. (2020) re-evaluated knowledge-graph completion. A higher MRR in a different filtering or split regime is not a comparison. The metric is not the result.
S/V · Lecture 09
03 · Rule miningLecture 09 · Logic as data

Rules, not vectors

Support, confidence, head coverage.

citizenOf(x,z) ← bornIn(x,y) ∧ locatedIn(y,z)

RuleSupportBodyConfidenceHead cov.
bornIn + locatedIn9100.900.90
worksAt + orgIn + locatedIn8100.800.80
worksAt(x,o) ← bornIn(x, ashford) ∧ orgIn(o, ashford)221.000.20
Confidence is precision when the rule fires. Support is the evidence. Head coverage is how much of the target relation the rule explains.
A perfect confidence can be thin. The third rule covers two people; confidence 1.0 with support 2 may be a coincidence. Confidence 0.8 with support 800 is a regularity.
S/V · Lecture 09
03 · Rule miningLecture 09 · Logic as data

Two ways to find the rules

Search the space, or learn the weights.

AMIE · symbolic search

A language bias says which relations may appear where. Start from an empty body, extend with atoms that share one variable, prune by support and confidence.

PCA confidence corrects for the open world: an absent prediction is not automatically false.

Neural LP · differentiable rules

A rule is a sequence of relations with a weight. Forward chaining runs over a relation tensor; gradient descent learns the weights.

A low-rank approximation controls the rule set. The output is a weighted logic program you can read.

Both are inductive: they generalize from observed triples to rules that cover unseen ones. ILP is the older, more expressive branch; rule mining is its binary-relation case.

S/V · Lecture 09
04 · Query answeringLecture 09 · Logic as data
04 / 08

Queries, not just scores.

Conjunctive queries, path queries, and the certain answers an incomplete graph can actually support.

S/V · Lecture 09
04 · Query answeringLecture 09 · Logic as data

The language

A query is a pattern with variables.

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

Evaluate

A subgraph homomorphism: map the query's variables to entities so every atom is true.

Complexity

NP-complete in combined complexity. Query planning and indexing matter even for modest graphs.

Recursion

Path queries add regular expressions; Datalog adds transitive closure with a least fixpoint.

A link score is not an answer. Ranking citizenOf(Mira, Avalon) highly scores one candidate. It does not return the set of people born in Avalon.
S/V · Lecture 09
04 · Query answeringLecture 09 · Logic as data

The open world, again

There may be no unique answer.

Closed world

Return the matches in the graph. If bornIn(Mira, ?) has no match, the answer is empty.

Open world

Return the tuples true in every model. If the graph does not say Ashford or Bellmere, there is no certain answer.

A top-scoring candidate is a hypothesis. It is useful. It is not an entailment. Report which semantics the system is using, and do not let a ranked list masquerade as a proof.
S/V · Lecture 09
04 · Query answeringLecture 09 · Logic as data

Composition in vector space

Queries as vectors and boxes.

Hamilton et al. 2018

Project and intersect

Embed a query graph by projecting entities through relation vectors and intersecting the results; score entities by proximity.

Query2box · 2020

Boxes

A query is an axis-aligned box. Projection maps the box; intersection takes the overlap; union takes the union.

BetaE · 2020

Beta distributions

A query is a product of beta distributions. Negation and conjunction become operations on the distributions.

Composition is learned, not free. A two-hop query composes relation vectors only if training taught that composition. The geometry does not close under composition on its own.
S/V · Lecture 09
05 · Structure as dataLecture 09 · Logic as data
05 / 08

Input, memory, output.

Three places a graph enters a neural model — and the bill that comes with each.

S/V · Lecture 09
05 · Structure as dataLecture 09 · Logic as data

The same artifact, three interfaces

Three places a graph enters a model.

Input

A GNN or R-GCN passes messages along edges. Permutation-invariant, variable size, relation-aware.

Limit: locality, over-smoothing, over-squashing.

Memory

Retrieve triples or paths and condition a language model on them. The graph supplies facts; the model supplies fluency.

Limit: entity linking, irrelevant retrieval, ignored evidence.

Output

Predict a missing triple, a rule, or a schema axiom. A reasoner can check the candidate before it is committed.

Limit: the checker is only as good as the ontology.

message passing · retrieval · completion

S/V · Lecture 09
05 · Structure as dataLecture 09 · Logic as data

Interactive · two scorers, one query

Rules and embeddings disagree.

#Candidate tailScoreSource
query
scorer

Mined rules

Choose a scorer to rank the candidate tails.

Rules show confidence; TransE shows normalized closeness. The queried edge is removed from training; the marker is the held-out fact.

Default: spouse(vera, ?). Switch to citizenOf(tessa, ?) to see the scorers agree.

S/V · Lecture 09
06 · What it buys & costsLecture 09 · Logic as data

The ledger · assets

What structure buys.

Inspectable

Triples, paths, and rules can be read and audited. The intermediate object is not a hidden vector.

Reusable

The same graph can serve retrieval, prediction, and query answering across teams and tasks.

Data-efficient

A fact is stated once. A rule can cover many cases without many labelled examples.

Auditable

Provenance and source can travel with the triple. Updates are local, not a full retraining.

S/V · Lecture 09
06 · What it buys & costsLecture 09 · Logic as data

The ledger · liabilities

What structure costs.

Incomplete

Absence is unknown. A model trained with corrupted negatives assumes a closed world it does not have.

Drifting

Schemas change, identifiers merge, relations are deprecated. A snapshot becomes a fossil.

Distorted

Every embedding algebra loses some relation pattern. The loss is systematic, not noise.

Leaky

Filtered ranking and inverse relations can inflate a benchmark. Report the split.

S/V · Lecture 09
07 · Six casesLecture 09 · Logic as data

Case 01 · the smallest interface

Score the missing edge.

(mira, bornIn, ashford) (ashford, locatedIn, avalon) (mira, worksAt, atlas) (atlas, orgIn, ashford) triples embedding table f_r(h,t) distance or bilinear higher = more plausible score function 1. avalon 2. borealis 3. cyrenia 4. doria ranked tails
The pipeline is four data structures: triples, vectors, scores, a ranked list.
The models: TransE translates, DistMult multiplies, ComplEx conjugates, RotatE rotates. The algebra decides which patterns survive.
The caveat: the benchmark samples recorded edges. A good rank is not a true edge; it is a plausible completion of a partial graph.
S/V · Lecture 09
07 · Six casesLecture 09 · Logic as data

Case 02 · the graph explains itself

Mine the rule, then read it.

citizenOf(x,z) ←
  bornIn(x,y) ∧ locatedIn(y,z)

support = 9 · body = 10
confidence = 0.90 · coverage = 0.90
AMIE: language bias, refine, prune. PCA confidence stops treating an unrecorded prediction as false.
Neural LP: a rule is a weighted path; gradient descent learns the weights; low rank controls the set.
Support is not causation. A rule can encode a curation artifact, a temporal coincidence, or a naming convention. Hold out edges before you trust the confidence.
S/V · Lecture 09
07 · Six casesLecture 09 · Logic as data

Cases 03–05

Compose, retrieve, complete.

Query · 03

Query embeddings

Project and intersect in vector space. Query2box adds boxes and union; BetaE adds negation.

Guarantee: empirical. Composition must be trained.

Retrieval · 04

Graph-grounded retrieval

Retrieve triples or paths and condition a language model on them. The graph grounds the answer.

Guarantee: none without provenance.

Ontology · 05

Schema completion

Predict a subclass edge, a domain restriction, or a disjointness axiom. A reasoner checks it.

Guarantee: checkable by the reasoner.

The strongest guarantee is the one with a checker. Ontology completion can reject an inconsistent axiom; retrieval cannot reject a fluent answer.
S/V · Lecture 09
08 · RecapLecture 09 · Logic as data

What you should be able to do

Six moves.

Read

Triples, signatures, TBox/ABox, and the open world.

Score

TransE, ComplEx, RotatE, and what each algebra forbids.

Mine

Support, confidence, head coverage; AMIE and Neural LP.

Query

Conjunctive queries, path queries, certain answers.

Consume

Graph as input, memory, or output.

Check

Incompleteness, drift, distortion, leakage.

S/V · Lecture 09
08 · RecapLecture 09 · Logic as data

Next · hands-on

Now train it.

Open the link-prediction lab. Choose a relation, train TransE and RotatE on a small typed graph, and compare the embedding ranks with a rule-based score.

Lab 09 · Link prediction → open the lab

Bring a question. Which relation is symmetric? Which query needs a path? The lab lets you test both, and the guide has the definitions.
S/V · Lecture 09
Speaker notes