Knowledge Representation & Graphs
Ontologies, semantic networks and knowledge graphs.
Tell a logical reasoner that birds fly, that penguins are birds that don't, and that Tweety is a penguin, and it will happily prove that Tweety is a fish. Representing knowledge well means choosing a vocabulary, giving every link a precise meaning, and computing what follows without that kind of explosion.
What you’ll learn
- Write an ontology's core axioms (membership, subclass, disjointness, partition) in first-order logic, and derive inherited properties as entailments.
- Explain why defaults with exceptions break classical, monotonic logic, and name the main nonmonotonic remedies.
- Read RDF triples and RDFS rules, and compute a knowledge graph's closure by semi-naive forward chaining, with its cost.
- Describe how knowledge-graph embeddings turn link prediction into geometry, and how they are evaluated.
Ontologies in first-order logic
In the Input Layer, a knowledge graph concluded that Marie Curie is a person by following subclass of edges. To make such inferences precise, an ontology written in first-order logic treats categories as objects in their own right (it reifies them). Membership and subclass become relations between objects, so a single axiom can speak about every category at once:
Inheritance is now ordinary entailment, and the machinery of the previous lesson applies unchanged. Most ontology axioms have this simple shape, unary predicates joined by implications plus disjointness. Restricting a logic to shapes like these, plus a little more, is exactly how description logics buy decidability, as the Deep Layer will show.
An ontology states , and . Which conclusion is entailed?
- Every animal is a bird
- Nothing about penguins and fish: no axiom mentions both
- and
- Only ; subclasses do not inherit disjointness
Show the answer
C. and
Subclass is transitive (it follows from the inheritance axiom), which gives . A penguin that was also a fish would be a bird and a fish at once, which forbids, so the two categories share no member.
Semantic networks, frames and defaults
Before ontologies were written in logic, they were drawn. A semantic network (Quillian, 1968) is a graph of categories and objects joined by labeled links such as is-a. A frame (Minsky, 1974) bundles an object's slots with default values. Their selling point is cheap inheritance: to learn whether Tweety flies, climb the is-a links until some node answers.
Their weakness, as Woods asked in 1975 in What's in a link?, is that a link has no fixed meaning. Does an arrow from Birds to Flies mean that every bird flies, or that a typical one does?
A default such as birds fly needs the opposite behavior: learning that Tweety is a penguin must withdraw the conclusion that it flies. Written as a strict rule, the default does not bend. It breaks the whole knowledge base.
There are three main families of remedies.
- Default logic (Reiter, 1980) adds rules such as : if is a bird and it is consistent to assume that flies, conclude that it does.
- Circumscription (McCarthy, 1980) writes and keeps only the models in which the set of abnormal objects is minimal.
- The closed-world assumption with negation as failure, as in Prolog, Datalog with negation and answer set programming, treats whatever cannot be proved as false.
Think first Under circumscription, the KB is . What follows when is minimized? What follows after you add and ?
At first, the minimal models make empty, so holds in all of them and is concluded. After the addition, every model must put in and make false, so the conclusion is withdrawn: more premises, fewer conclusions. Exceptions can also clash. In the Nixon diamond, Quakers are pacifists by default, Republicans are not, and Nixon is both, so neither conclusion is preferred.
Knowledge graphs: RDF, RDFS and SPARQL
The web-scale descendant of semantic networks is the knowledge graph, with standards from the W3C. In RDF, a graph is a set of triples whose terms are IRIs (global identifiers), literals or blank nodes. The RDFS vocabulary adds a little schema, and its meaning is fixed by entailment rules, each a Horn clause over triples:
| Rule | If the graph contains… | …then add |
|---|---|---|
| rdfs9 | and | |
| rdfs11 | and | |
| rdfs7 | and | |
| rdfs2 | and | |
| rdfs3 | and |
# RDF data in Turtle syntax
:Curie rdf:type :Physicist .
:Physicist rdfs:subClassOf :Scientist .
:Scientist rdfs:subClassOf :Person .
:won rdfs:domain :Person .
:Curie :won :NobelPhysics1903 .
# SPARQL: who is a person?
SELECT ?x WHERE { ?x rdf:type :Person . }Run on the stored triples alone, the query returns nothing. Under RDFS entailment it returns :Curie, twice over: through the subclass rules (rdfs9, rdfs11), and through rdfs2 from the domain of :won.
A SPARQL basic graph pattern is a conjunctive query. Answering it means finding every homomorphism from the pattern into the graph, a mapping of its variables to terms that sends every pattern triple to a stored triple. For a fixed pattern with variables this takes time polynomial in the graph size ( by brute force), but with the pattern as part of the input the problem is NP-complete (Chandra & Merlin, 1977). That is why query engines live and die by join ordering and indexes.
Computing the closure: forward chaining to a fixpoint
RDFS rules, inheritance axioms and many other ontology rules are function-free Horn clauses, that is, a Datalog program . A reasoner can apply them on demand at query time (backward chaining), or materialize every consequence in advance by forward chaining, so that later queries become lookups. Each round applies the immediate-consequence operator .
SEMI-NAIVE(P, D): # P: Datalog rules, D: facts
I ← D; Δ ← D # Δ: the facts that are new
while Δ ≠ ∅:
new ← ∅
for each rule H ← B1, …, Bk in P:
for each substitution θ with B1θ, …, Bkθ ∈ I
and some Biθ ∈ Δ:
if Hθ ∉ I: new ← new ∪ {Hθ}
I ← I ∪ new; Δ ← new
return I # the least model of P ∪ DNaive evaluation repeats every derivation in every round. Demanding at least one premise from the previous round's new facts skips the derivations already made; indexes on each predicate make the matching fast.
Monotone. Rule bodies contain no negation, so more facts can only enable more rule applications:
Terminates. Without function symbols no new constants appear, so every derived fact is one of at most ground atoms. The sequence only grows, so it stabilizes within that many rounds:
Sound. By induction on rounds: each new fact follows from earlier ones by universal instantiation and modus ponens.
Complete. Read as an interpretation in which exactly its atoms are true. It contains and satisfies every rule, because . So an atom outside is false in a model of , and is not entailed:
Polynomial does not mean cheap. Datalog is P-complete in data complexity, and EXPTIME-complete when the rules are part of the input (Vardi, 1982). The closure itself can also dwarf the data:
A class hierarchy is a single chain , stored as 9 subClassOf triples. How many subClassOf triples does its closure under rdfs11 contain, counting the 9 asserted ones (and no reflexive triples)?
Show the answer
45 triples
Every pair gets a triple , so there are . Materializing a transitive relation grows quadratically along chains: a chain of 10,000 classes would yield about 50 million triples, which is why large reasoners store class hierarchies compactly instead of as plain triples.
From symbols to vectors
Deduction reaches only what follows from the facts you have, and real graphs are full of holes. A 2014 study found that most people in Freebase, then a large public knowledge graph owned by Google, had no recorded place of birth. No rule entails a missing birthplace.
Statistical relational learning guesses it instead, from patterns in the rest of the graph. Knowledge-graph embeddings map each entity to a vector and each relation to a vector or a matrix, and score candidate triples with a function . The first widely used model, TransE (Bordes et al., 2013), reads a relation as a translation:
Link prediction is scored by ranking. For each test triple, rank the true tail (and, separately, the true head) among all entities, after removing other candidates already known to be true: the filtered setting. Report the mean reciprocal rank (MRR), the average of , and Hits@10, the fraction of test triples ranked in the top 10.
Key takeaways
- Ontologies reify categories: membership, subclass, disjointness and partition axioms in first-order logic turn inheritance into plain entailment.
- Classical logic is monotonic, so defaults need nonmonotonic tools (default logic, circumscription, negation as failure). A strict "birds fly" plus one penguin makes a KB inconsistent, and an inconsistent KB entails everything.
- RDF stores triples. RDFS rules (subclass, subproperty, domain, range) infer new triples instead of rejecting data, and SPARQL graph patterns are conjunctive queries: polynomial for a fixed query, NP-complete in general.
- Datalog forward chaining reaches the least model, exactly the entailed atoms, in at most rounds; materialized closures of hierarchies can grow quadratically.
- Embeddings such as TransE () predict missing links statistically, and are evaluated by filtered MRR and Hits@k.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why can't classical first-order logic express "birds fly, except penguins" as a strict rule plus exceptions?
- First-order logic is undecidable
- Classical logic is monotonic: adding a premise never removes a conclusion, so an exception can only contradict the rule
- Penguins would require second-order quantifiers
- Resolution is incomplete for Horn clauses
Show the answer
B. Classical logic is monotonic: adding a premise never removes a conclusion, so an exception can only contradict the rule
If , then as well. An exception cannot withdraw the conclusion. Combined with it makes the KB inconsistent, and then everything follows.
An RDFS graph contains and , and nothing else about pat. What does an RDFS reasoner do?
- Reports a constraint violation, because pat is not declared a Woman
- Infers
- Nothing: a range only restricts future insertions
- Infers
Show the answer
D. Infers
Rule rdfs3 types the object of every hasMother triple as a Woman. RDFS has no notion of a violation: under the open-world assumption, what is not stated is simply unknown.
Why does forward chaining over a Datalog program always terminate?
- Without function symbols there are only finitely many ground atoms, at most , and every round adds at least one new atom or stops
- Each rule can fire at most once
- Semi-naive evaluation never derives the same fact twice
- Horn clauses can be checked in linear time
Show the answer
A. Without function symbols there are only finitely many ground atoms, at most , and every round adds at least one new atom or stops
No new constants can be built, so the set of possible facts is finite, and the derived set only grows. That bounds the number of rounds by for constants and predicates of arity at most .
In the filtered ranking protocol for a test query , why are the other known true tails removed from the candidates before ranking?
- To make the task harder
- So the model is not penalized for ranking another correct answer above the test triple's tail
- To remove inverse-relation leakage from the training set
- Because TransE cannot score more than one tail per head
Show the answer
B. So the model is not penalized for ranking another correct answer above the test triple's tail
If and are both true and the test asks for , ranking first is not a mistake. Filtering drops such known-true candidates, so a rank counts only real errors.
holds at a university that employs some of its students. Is a Partition of ?
- Yes: every member is a student or a member of staff
- Yes, because there are only two categories
- No: a partition must also be disjoint, and student employees belong to both
- No: a partition requires its categories to have the same size
Show the answer
C. No: a partition must also be disjoint, and student employees belong to both
means . Here exhaustiveness holds and disjointness fails.
Go deeper
- Description Logics & Ontologies · Decidable fragments behind the semantic web.
- Knowledge Graph Embeddings · TransE, link prediction and relational learning.
- Commonsense Reasoning · Why the obvious is the hardest thing to encode.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 10.
- R. J. Brachman & H. J. Levesque, Knowledge Representation and Reasoning (Morgan Kaufmann, 2004).
- A. Hogan et al., "Knowledge graphs," ACM Computing Surveys 54(4) (2021).
- S. Abiteboul, R. Hull & V. Vianu, Foundations of Databases (Addison-Wesley, 1995).