Lecture 17 · Applications

NLP and knowledge graphs.

A question that needs a join is not answered by a paragraph. It is answered by a query — and the query is the thing you can inspect.

3 routes to an answer 4 LLM + KG patterns 1 33-triple lab Self-paced
00 · Learning objectivesLecture 17 · NLP and knowledge graphs

By the end of this lecture

Four moves.

01

Parse a question into a query

Name the variables, constants, and relation directions — not just the keywords.

02

Distinguish three routes

Retrieval, semantic parsing, and KG reasoning differ in what they output and guarantee.

03

Recognize LLM + KG patterns

Four directions, four different promises; a pipeline is not an interface.

04

Evaluate against the claim

Answer accuracy, query accuracy, retrieval recall, and entailment are different tests.

S/V · Lecture 17
00 · The hookLecture 17 · NLP and knowledge graphs

A question a paragraph cannot answer

“Which films directed by a director born in Lebanon won an award?”

A retriever can find sentences that mention Lebanon, directing, and an award. It has no operation that forces them to describe the same film.

A parser can. The question names a film, a director, a birthplace, and an award. The query binds them to one answer.

the graph pattern

?film :directedBy ?director .
?director :bornIn :lebanon .
?film :wonAward ?award .
SELECT DISTINCT ?film

The interesting part is not the answer. It is the object that makes the answer necessary.

S/V · Lecture 17
00 · The hookLecture 17 · NLP and knowledge graphs

Three routes from question to answer

Three outputs. Three guarantees.

Retrieval

Passages

Rank text by relevance; a generator writes the answer from the passages. The output is an answer plus citations.

GUARANTEE · empirical

Semantic parsing

Bindings

Translate the question into a query; an executor returns the bindings and the matched triples.

GUARANTEE · sound vs. query + KG

KG reasoning

Entailments

Query under an ontology or rule set; the reasoner derives facts that are not stored explicitly.

GUARANTEE · sound vs. axioms

The three are often confused because the same chat box can hide all of them. The output tells you which one you actually built.

S/V · Lecture 17
01 · Semantic parsingLecture 17 · NLP and knowledge graphs
01 / 08

From sentence to query.

Composition, schema linking, and the object the executor matches.

S/V · Lecture 17
01 · Semantic parsingLecture 17 · NLP and knowledge graphs

What the parser actually does

Three jobs, not one.

01 · Lexicon

Words to predicates

direct ↦ λy.λx. directedBy(x,y). The word does not become a string; it becomes a relation with a type.

02 · Composition

Parts to a whole

A grammar or a sequence model combines the pieces. The output is a logical form, not a bag of entities.

03 · Schema linking

Mentions to IDs

“Lebanon” becomes :c_lebanon; “directed” becomes :directedBy with the right direction.

Most parser errors are in the third job. The sentence can be parsed perfectly and still link to the wrong entity or the wrong predicate.

S/V · Lecture 17
01 · Semantic parsingLecture 17 · NLP and knowledge graphs

The same meaning in two notations

The query is the composition.

Logical form

λx. Film(x)
  ∧ directedBy(x, mara)
  ∧ bornIn(mara, lebanon)
  ∧ wonAward(x, a)

The sentence denotes a set; the question projects it.

SPARQL

SELECT DISTINCT ?film WHERE {
  ?film :directedBy ?director .
  ?director :bornIn :lebanon .
  ?film :wonAward ?award .
}

Same graph pattern; executable over triples.

If the notation can be executed, the composition can be checked. That is the whole advantage over a paragraph.

S/V · Lecture 17
01 · Semantic parsingLecture 17 · NLP and knowledge graphs

The query is a graph; execution maps it into the data

Execution is a homomorphism.

?film ?director Lebanon constant ?award ?festival directedBy bornIn wonAward awardAt project this variable
A conjunctive query drawn as a graph. Dashed nodes are variables; the solid node is a constant. Execution assigns every variable so that every edge exists in the data.

If one edge is missing, the assignment is not an answer — under open-world semantics it is unknown, not false.

S/V · Lecture 17
01 · Semantic parsingLecture 17 · NLP and knowledge graphs

Interactive · fictional 9-triple demo

Parse it. Then execute it.

Which films directed by directors born in Lebanon won an award?

Press Parse to resolve the mentions.
Template · —
Slots · —
SELECT …
Join trace · —
?

Press Parse, then Execute. Each step is a separate object; the answer comes from the join, not from the button.

S/V · Lecture 17
01 · Semantic parsingLecture 17 · NLP and knowledge graphs

Where the quiet errors live

Most parser errors are not syntax errors.

Direction

?film :directedBy :mara
≠
:mara :directedBy ?film

The first asks what Mara directed. The second asks who directed Mara — a category error in most schemas.

Attachment

?director :bornIn :lebanon
≠
?film :bornIn :lebanon

The birthplace belongs to the director, not the film. A parse that attaches it to the film is syntactically fine and semantically wrong.

Executability is not intent. A query can type-check and still answer a different question. That is why the guide evaluates query accuracy separately from answer accuracy.
S/V · Lecture 17
02 · KGQALecture 17 · NLP and knowledge graphs
02 / 08

What the query has to do.

Shapes, joins, and the open-world answer.

S/V · Lecture 17
02 · KGQALecture 17 · NLP and knowledge graphs

The shapes a KGQA system must handle

Seven shapes, seven operations.

ShapeOperationMain risk
Single-hopFollow one edgeEntity linking
Multi-hopJoin through a variableMissing bridge entity
ConjunctiveIntersect two patternsEmpty join from a wrong predicate
FilterCompare a literalDatatype and timezone
AggregationGroup and countDuplicates and DISTINCT
NegationComplement / absenceOpen world: absence is not falsity
PathTransitive closureCycles and cost

A system that handles single-hop questions is not a smaller version of one that handles conjunctions. The operations are different.

S/V · Lecture 17
02 · KGQALecture 17 · NLP and knowledge graphs

Execution is a join with a cost

Rows in, matches, rows out.

StepPatternRows
1?film :directedBy ?director5 → 5
2?director :bornIn :sweden5 → 2
3?film :wonAward ?award2 → 1

The lab’s default query: 33 triples, three patterns, one answer.

Join order matters. Starting from the selective pattern leaves fewer rows for the rest; starting from the broad one materializes a cross product.

Real engines use predicate and object indexes, cardinality estimates, and rewriting. At public-KG scale, the plan is the performance.

LECTURE 02 · the engine is a search with a cost

The derivation is the audit trail. Each surviving row carries the triples that produced it.

S/V · Lecture 17
03 · RetrievalLecture 17 · NLP and knowledge graphs

Retrieval-augmented generation

Retrieve, then generate.

question natural language retriever similarity over text top-k passages documents, chunks generator conditions on text answer + citations
RAG marginalizes over documents in theory; in practice it conditions on the top-k. A citation is a pointer, not an entailment check.

p(y | x) = Σd∈D pη(d | x) · pθ(y | x, d)

The sum is the idea. The top-k is the engineering. The gap between them is where recall failures enter.

S/V · Lecture 17
03 · RetrievalLecture 17 · NLP and knowledge graphs

What retrieval cannot do

Evidence selection is not composition.

01 · Relevance

Relevance is not entailment. A passage can mention every entity and still not support the answer. Similarity is not truth.

02 · Composition

Retrieval does not join. Two facts in different documents require both to be retrieved and the generator to notice the connection.

03 · Operators

Aggregation and negation have no operator. “How many,” “the only,” and “none” are pattern-matched, not computed.

04 · Context

Context is finite and position-sensitive. More retrieved text is not more evidence; the middle of a long context is used less reliably.

A citation is a pointer, not a proof. Faithfulness is a separate measurement from retrieval recall.
S/V · Lecture 17
04 · LLM + KGLecture 17 · NLP and knowledge graphs
03 / 08

Four patterns. Four promises.

The direction of information decides what can be guaranteed.

S/V · Lecture 17
04 · LLM + KGLecture 17 · NLP and knowledge graphs

The four patterns

Direction decides the guarantee.

PatternDirectionWhat it buysGuarantee
KG as retrieverKG → LLMFacts in the prompt; no query languageEmpirical; retrieval-bound
LLM as query writerLLM → KGNL → SPARQL; execution checkSound vs. query + KG
LLM as traversal policyLLM ↔ KGSearch over relations without a full queryEmpirical; search-bound
LLM as extractorText → KGNew triples and alignmentsEmpirical; errors persist

KAPING verbalizes triples. Think-on-Graph searches the graph. Logic-LM writes a formal query and calls a solver. BERTMap aligns schemas.

S/V · Lecture 17
04 · LLM + KGLecture 17 · NLP and knowledge graphs

The propose–execute–check loop

Execution checks the query, not the intent.

1 · Propose

The model writes a SPARQL query from the question and the schema.

2 · Execute

The engine rejects malformed queries, unknown predicates, and type errors.

3 · Repair

The error goes back to the model; it tries again. The loop stops on a valid query or when the attempt budget runs out.

What the check catches: directedByy, a film where a director belongs, a literal where an entity belongs.
What it cannot catch: directedBy → producedBy. Valid query, plausible rows, wrong question.

The repair loop makes the query well-formed. It does not make the formalization faithful.

S/V · Lecture 17
05 · Extraction & alignmentLecture 17 · NLP and knowledge graphs

Where the triples come from

Text becomes triples in four steps.

01 · Mentions

Find entity spans in the sentence. A missed span is a missed fact.

02 · Linking

Resolve spans to canonical entities. A namesake is a wrong join waiting to happen.

03 · Relation

Classify the relation and its direction. directed and directed by are not the same edge.

04 · Canonicalize

Map surface predicates to the schema; store provenance and confidence with the triple.

Distant supervision is cheap and noisy. Every sentence mentioning a seed pair is labeled positive, even when the sentence is about something else.
S/V · Lecture 17
05 · Extraction & alignmentLecture 17 · NLP and knowledge graphs

The schema-level version of the same problem

Schemas drift. Alignments are revisable.

Ontology A

Film → directedBy → Director
Director → bornIn → Country

Ontology B

Movie → helmedBy → Person
Person → birthplace → Nation

Equivalence

directedBy ≡ helmedBy

Subproperty

helmedBy ⊑ directedBy

Instance

Nadia Haddad ≡ N. Haddad

BERTMap matches labels in context; OAEI scores precision, recall, and F1 against reference alignments. The mapping is empirical and must be revised when the schema changes.

S/V · Lecture 17
06 · What failsLecture 17 · NLP and knowledge graphs

Four places to look before changing the model

Parse, link, query, cover.

FailureSymptomDiagnosis
ParseNo query, or an unknown predicateQuestion outside the grammar
Entity linkPlausible answer about the wrong personPrint resolved IDs and alternatives
QueryEmpty or inverted resultCheck domain, range, direction
CoverageNo answer from an incomplete graphIs the fact present at all?
Open world: zero bindings is unknown, not false. A product may choose closure, but it must say so.
The quiet failure: a valid query that runs and answers the wrong question.
S/V · Lecture 17
06 · What failsLecture 17 · NLP and knowledge graphs

Match the metric to the claim

One number cannot support four claims.

Answer accuracy

Did the returned answer match the gold answer? Necessary, but blind to the query.

Query accuracy

Did the produced query/program match the gold query? Separates a lucky answer from a correct parse.

Retrieval recall

Was the supporting passage in the top-k? A generation score cannot reveal a retrieval miss.

Faithfulness

Does the cited evidence entail the answer? A citation is not a proof.

Report the split too. I.i.d., compositional, and zero-shot questions measure different things; template overlap can inflate all four.

S/V · Lecture 17
07 · The tupleLecture 17 · NLP and knowledge graphs

Read the system, not the slogan

Representation, inference, coupling, guarantee.

SystemRepresentationInferenceGuarantee
RAGPassages + generatorRetrieval + generationEmpirical
Semantic parserTriples + ontologyQuery evaluationSound vs. query + KG
Think-on-GraphTriplesLLM-guided beam searchEmpirical
KAPINGVerbalized triplesIn-context readingEmpirical
BERTMapTwo ontologiesContextual matchingEmpirical

Add cost for a product: index size, retrieval latency, model calls, schema maintenance. The tuple is qualitative; no scores are claimed.

S/V · Lecture 17
07 · The tupleLecture 17 · NLP and knowledge graphs

The field rebuilds the same system under new names

Four names, four recombinations.

KAPING

Retrieval with triples. The corpus is verbalized facts; the retriever is a triple selector; the generator reads.

Think-on-Graph

A parser that searches. Instead of writing the query, the model chooses relations and walks the graph.

BERTMap

Relation extraction at schema level. The entities are classes and properties; the relation is an alignment.

Logic-LM

Parsing into a solver. The target is first-order logic; the executor is a theorem prover or SAT/SMT solver.

The interfaces differ; the questions are stable. What is the symbolic object, what executes it, and what does execution guarantee?

S/V · Lecture 17
08 · RecapLecture 17 · NLP and knowledge graphs

What you should be able to do

Four moves.

Distinguish

Retrieval gives evidence; parsing gives bindings; reasoning gives entailments.

Parse

Read a question as a graph pattern with variables, constants, and directions.

Recognize

Four LLM + KG patterns; only the query writer gets an independent check.

Evaluate

Answer, query, recall, faithfulness — the metric must match the claim.

S/V · Lecture 17
08 · RecapLecture 17 · NLP and knowledge graphs

Next · hands-on

Now execute it yourself.

Open the lab. Ask a question, read the query, expand the derivation, then try one the templates do not cover and inspect the fallback.

Lab 17 · question → query → bindings → open the lab

S/V · Lecture 17
Speaker notes