Ask a system: “Which films directed by a director born in Lebanon won an award at a festival?” The answer is not a paragraph that mentions Lebanon and an award. It is the result of a join: a director, a birthplace, a film, an award, a festival — all bound to the same film.
00 / The hookA question is a graph pattern.
A person answers by walking a small graph: find a director born in Lebanon, find her films, keep the award winners, find where each award was given. The answer is the set of films that survive every step. A retriever can find sentences containing Lebanon, director, and award, but nothing forces them to be about the same film. A model can write a fluent answer, but fluency is not a join.
A knowledge graph makes the join explicit: a set of triples, subject–predicate–object, over typed entities and relations. The W3C stack calls this model RDF and the query language SPARQL; property graphs are the other common representation. The graph has no fixed table schema, so the ontology is what says which relations and classes are meaningful.
A knowledge graph is a graph whose nodes are entities or literals and whose edges are typed relations, plus an optional schema. The schema has a TBox (classes, properties, domain, range, axioms) and an ABox (asserted facts). The TBox supports inference; the ABox is what the graph contains.
The TBox / ABox split is the difference between “a director is a person” and “this person directed that film.” A reasoner uses the first to infer that a director is a person, and property axioms to infer inverse or transitive relations. That is reasoning in the knowledge-representation sense: deriving facts that are not stored explicitly.
The semantics are usually open-world: the absence of a triple means the graph does not know, not that the fact is false. This is the opposite of the closed-world assumption familiar from databases and Prolog. A question such as “which films did not win an award?” is not a simple complement over an incomplete graph unless the modeller chooses a closure, a negation-as-failure rule, or explicit negatives. Reiter’s 1978 paper states the choice; OWL’s open-world semantics is the alternative.
| Route | Operation | Output | Guarantee | Typical failure |
|---|---|---|---|---|
| Retrieval | Rank passages; condition a generator | Text answer plus citations | Empirical; no entailment | Relevant evidence, unsupported answer |
| Semantic parsing | Translate; execute the query | Bindings plus the query | Sound relative to query and KG | Wrong parse, entity, or relation direction |
| KG reasoning | Query under entailment | Entailed answers plus a proof trace | Sound relative to axioms and rules | Wrong or missing axioms; expensive inference |
A knowledge graph is a model: incomplete, stale, biased, or wrong, with an ontology that may encode the wrong distinctions. An answer is exact relative to the graph, not the world.
01 / Semantic parsingFrom a sentence to a query that can be executed.
Semantic parsing maps an utterance to a formal meaning representation: a logical form, SPARQL query, or program. The mapping is compositional — meaning is built from parts, not retrieved whole. That lets a parser handle an unseen question when its parts are in the lexicon and grammar.
The noun phrase films directed by Mara denotes a set: the films x with Film(x) and directedBy(x, Mara). The interrogative turns the set into the query variable:
The lexicon supplies predicate meanings; the grammar supplies combination. direct might be λy.λx. directedBy(x, y). A neural parser learns the mapping as sequence-to-sequence translation with a logical-form target; a grammar-based parser makes composition explicit. Neither removes the schema.
The parser must also link mentions to entities and relations. Mara must resolve to one director, not every namesake; directed to directedBy with film as subject and director as object; born in to the director, not the film. Most parsing errors live here, and they are not syntactic: a perfect parse can still link to the wrong predicate.
| Phrase | Meaning | Query fragment |
|---|---|---|
| films | a set of films | ?film a :Film |
| directed by ?d | the film has director ?d | ?film :directedBy ?d |
| ?d born in Lebanon | the director's birthplace is Lebanon | ?d :bornIn :c_lebanon |
| won an award | the film has an award | ?film :wonAward ?award |
| at a festival | the award's festival | ?award :awardAt ?festival |
| which films | project the film variable | SELECT DISTINCT ?film |
Formally, a parser defines a distribution over programs, and the answer is the denotation of the chosen program. The crucial constraint is executability: a program that cannot be evaluated against the schema is not an answer, it is a type error.
Training signals differ. A supervised parser is trained on question–program pairs. A weakly supervised parser is trained on question–answer pairs and marginalizes over latent programs: if several programs produce the correct answer, all of them receive credit in proportion to their probability.
Weak supervision is cheap because programs are expensive to annotate, and ambiguous because a wrong program can produce the right answer for the wrong reason. Berant et al. (EMNLP 2013) made it influential on Freebase; Yih et al. (ACL 2016) showed the value of parse labels for WebQuestionsSP. The parser is only as good as its schema linking, the answer as the query it executes.
A conjunctive query is itself a small graph: variables are nodes, relation atoms are edges, constants are fixed labels. Executing it means mapping that graph into the knowledge graph while preserving labels and edge types — a homomorphism from the query graph to the data graph.
Real SPARQL is more than conjunctive queries. OPTIONAL, FILTER, aggregation, property paths, and negation add expressive power and semantic subtleties, and some move evaluation up the complexity ladder. Conjunctive queries are a clean teaching model, not a full engine.
02 / KGQAWhat the query has to do.
Knowledge-graph question answering (KGQA) answers a natural-language question against a knowledge graph. Semantic parsing is one way, not the definition. The definition is behavioural: the answer is supported by the graph, whether support comes from a query, an embedding, or a retrieval-and-read pipeline. The differences show in the question shapes each handles.
| Shape | Example | Graph operation | SPARQL | Main risk |
|---|---|---|---|---|
| Single-hop | Who directed Film A? | Follow one edge | ?f :directedBy ?d | Entity linking |
| Multi-hop | Films by directors born in Country C | Join two edges through a variable | ?f :directedBy ?d . ?d :bornIn :C | Missing bridge entity |
| Conjunctive | Drama films produced by Studio S | Intersect two patterns | Two triple patterns | Empty join from wrong predicate |
| Filter | Films released after 2015 | Compare a literal | FILTER(?y > 2015) | Datatype and timezone |
| Aggregation | How many films won an award? | Group and count | COUNT | Duplicates and DISTINCT |
| Negation | Films that won no award | Complement / absence | NOT EXISTS, MINUS | Open world: absence is not falsity |
| Path | Everything reachable from X | Transitive closure | Property path | Cycles and cost |
Execution is a join, and joins cost. Two unbound patterns can produce a cross product before a selective order is found; a transitive path can visit much of the graph. Engines use indexes, cardinality estimates, and rewriting. At public-KG scale, the plan is the difference between a second and a timeout — Lecture 02’s lesson: the engine is a search with a cost.
Answer semantics matter. SPARQL returns a multiset unless DISTINCT is used; aggregation changes the shape; ORDER BY and LIMIT rank it. Reporting “the answer” without saying which was computed hides a choice: “top five by award count” and “all films with at least one award” are different questions.
Three KGQA families. Semantic parsing makes the query explicit and executes it. Embedding-based methods encode entities, relations, and the query graph; BetaE models multi-hop queries as geometric operations over embeddings (Ren & Leskovec, 2020), generalizing to missing links without a symbolic derivation. Retrieval and LLM methods retrieve a subgraph and let a model read it. The families mix in practice.
The answer set of a conjunctive query has a compact definition. Let q have body atoms R1(…), …, Rn(…). Then:
“Homomorphism into K” means: every variable gets an entity or literal, every constant maps to itself, and every body atom is a triple in the graph. So Fig. 1.1 is more than a picture; it is the object the executor matches. An entailment regime extends the matching relation: a triple can be used if it is entailed by the graph and its ontology, not only if it is explicit.
Evaluation is where the benchmarks live. WebQuestionsSP and ComplexWebQuestions test Freebase questions; KQA Pro supplies compositional programs; GrailQA separates i.i.d., compositional, and zero-shot generalization (Gu et al., WWW 2021). Metrics include answer accuracy, exact match, F1, and query/program accuracy. The last is diagnostic: a system can answer with the wrong query, and an answer-only benchmark will not see it. Template-generated questions can also measure template overlap rather than understanding.
Zero bindings means the graph lacks a matching fact, not that it is false. Rendering the empty result as “no” silently switches to closed-world — maybe the right product decision, but a decision.
03 / Retrieval & RAGEvidence selection is not composition.
Retrieval-augmented generation (RAG) couples a retriever with a generator. The retriever selects documents or passages from a corpus; the generator conditions on the question and the retrieved text. Lewis et al. (2020) formalized the idea for knowledge-intensive NLP. The probabilistic form marginalizes over documents:
In practice the sum is replaced by the top-k documents under a retrieval score, and the generator sees a concatenation of their text:
Retrieval is attractive: no ontology, a sentence can be the evidence, citations are possible, and updating the corpus updates the system. A dense retriever matches paraphrases; a reranker improves precision; a generator synthesizes across passages. For many factoid questions, it is the right choice.
The limits are structural.
- Relevance is not entailment. A passage can mention the entities and still not support the answer.
- Retrieval does not join. Two facts in different documents require both to be retrieved and the generator to notice the connection; top-k can miss the bridge.
- Aggregation and negation have no operator. “How many,” “the only,” and “none” are pattern-matched, not computed.
- Context is finite and position-sensitive. Liu et al. (2023) show the middle of a long context is used less reliably than the ends.
- Sources conflict and age. No truth maintenance, no schema-level consistency check. A citation is a pointer, not a proof.
- Evaluation splits. Recall@k scores retrieval; accuracy or faithfulness scores generation. Barnett et al. (2024) catalogue seven failure points.
| Dimension | RAG over text | KGQA over triples |
|---|---|---|
| Knowledge source | Documents and passages | Entities, relations, ontology |
| Composition | Implicit in the generator | Explicit in the query |
| Answer type | Free text with citations | Bindings, counts, boolean, subgraph |
| Provenance | Passage identifiers | Matched triples and derivation |
| Updates | Re-index the corpus | Insert or retract triples; migrate schema |
| Characteristic failure | Unsupported but fluent answer | Wrong query or missing fact |
The distinction is not an argument for one interface over the other. It is an argument for knowing which one you built. A RAG system described as “reasoning over a knowledge base” will fail the first question that needs a join; a KGQA system described as “reading the web” will fail the first time the graph is incomplete.
“Graph RAG” retrieves from a graph or graph-derived index, so the boundary is porous. The question is whether the answer is computed over relations or synthesized from text that mentions them. The first shows a derivation; the second a citation. Different evidence.
04 / LLM + KGFour patterns, four different promises.
“LLM plus knowledge graph” names a family, not one architecture. Read each by direction: which component supplies structure, which flexibility. Pan et al. (2023) describe three directions — KG-enhanced LLMs, LLM-augmented KGs, and synergized systems. Four patterns suffice.
| Pattern | Direction | What it buys | Guarantee | Main cost |
|---|---|---|---|---|
| KG as retriever | KG → LLM | Facts in the prompt, no query language | Empirical; depends on retrieved triples | Retrieval coverage and context budget |
| LLM as query writer | LLM → KG | Natural language to SPARQL or an API call | Sound relative to the query and KG | Parse errors; execution and repair loop |
| LLM as traversal policy | LLM ↔ KG | Search over relations without a full query | Empirical; search may miss the path | Many model calls; beam width |
| LLM as extractor / aligner | Text → KG | New triples, links, and schema mappings | Empirical; errors enter the graph | Annotation, provenance, review |
The first is simplest: retrieve triples or a subgraph, verbalize them, put them in the prompt. KAPING (Baek et al., 2023) does this for zero-shot KGQA with no fine-tuning and no query language. The model must read the triples correctly and the retriever must return the right ones, but the interface is short and inspectable.
The second makes the LLM a translator: it writes a query — SPARQL, an API call, or a logical form — and an executor runs it. The executor rejects malformed queries and type errors; an empty result can prompt repair. This is Logic-LM’s propose–execute–check loop (Pan et al., 2023), applied to graph queries. The check is real but narrow:
Executability catches syntax and type errors, not a valid query that answers a different question. Swap directedBy for producedBy and the query runs, returns a plausible set, and is wrong. The defence is to compare the query with the question, or to test the answer against independent evidence.
The third pattern uses the graph as a search space. Think-on-Graph (Sun et al., 2023) lets the LLM score candidate relations and entities, walks the graph in a beam search, and stops when evidence suffices. The LLM is a heuristic; the graph is the source of facts. StructGPT (Jiang et al., 2023) generalizes this to structured data through callable interfaces. Both avoid writing a full SPARQL query, but inherit search’s failures: a wrong pruning removes the right path, and beam width is a budget, not a guarantee.
The fourth pattern runs the other way: the LLM proposes entities, relations, and alignments, and the graph stores them. That is §5, with the longest feedback loop — an error becomes a triple later queries treat as fact.
If the LLM writes the answer and the KG only decorates it, the system is a pipeline with an accessory. The KG is an interface only when it constrains, checks, or supplies composition. The test: can the KG say no? If not, the guarantee is whatever the model already had.
05 / Extraction & alignmentWhere the triples come from, and why they drift.
A knowledge graph is not born with facts. Relation extraction turns text into triples: find mentions, link to canonical entities, classify the relation, store with provenance. The pipeline is consequential — every query inherits its errors.
The classic signal is distant supervision. If a seed KB contains (s, r, o), every sentence mentioning both s and o is a positive example of r. The label is noisy but cheap. Multi-instance learning aggregates sentence evidence, so one bad sentence does not decide the label alone.
Schema-based extraction assumes a fixed inventory of relation types with domain and range. Open information extraction proposes surface relations and leaves canonicalization for later — where hard work lives. directed, directed by, and helmed may denote one predicate; born in may be a birthplace or a film’s country. Without relation canonicalization, the graph fragments and queries miss facts under other labels.
Ontology alignment is the schema-level version. Two graphs may use different class names, property names, or granularity. Alignment finds correspondences: equivalence, subproperty, or same entity. Matchers use string similarity, linguistic normalization, structural evidence, and contextual embeddings. BERTMap (He et al., 2021) uses BERT-based context-aware name embeddings plus a taxonomy-based repair step. The Ontology Alignment Evaluation Initiative (OAEI) supplies reference alignments; precision, recall, and F1 against them are the standard measures.
| Stage | Output | Typical error | Downstream effect |
|---|---|---|---|
| Mention detection | Entity spans | Missed or over-long span | No triple, or a triple about the wrong text |
| Entity linking | Canonical entity IDs | Same name, different entity | Wrong join; plausible but false answer |
| Relation classification | Typed relation | Direction reversed; wrong label | Empty query or inverted answer |
| Canonicalization | Schema predicate | Near-duplicate predicates | Fragmented graph; low recall |
| Alignment | Cross-schema mappings | False equivalence; missed subsumption | Wrong class inference; schema drift |
| Provenance | Source, confidence, time | Dropped source or timestamp | No way to audit or retract |
Two design rules follow. Store provenance and confidence with every triple, even if the query engine ignores them: when a wrong answer is traced back, the trace is the only way to find the bad extraction. And treat alignment as a revisable artefact, not one-time preprocessing: schemas change and a mapping correct for one release can be wrong for the next.
A missing triple makes a query return less. A wrong triple makes it return a falsehood indistinguishable from fact unless provenance or an independent check exists. Precision matters more than recall for a queried graph, because the engine cannot be suspicious.
06 / What failsA taxonomy you can debug against.
The failures cluster at four places: the parse, the link, the query, and the graph’s coverage. A system that logs those four can be debugged; one that logs only the final answer cannot.
| Failure | Symptom | Diagnosis |
|---|---|---|
| Parse failure | No query, or a query with an unknown predicate | Is the question outside the grammar? Check the template coverage before blaming the parser. |
| Entity-linking error | A plausible answer about the wrong person or film | Print the resolved entity IDs and the alternatives. The answer is only as good as the link. |
| Relation-direction error | Empty or inverted result | Check domain and range. directedBy and directorOf are not interchangeable in a query. |
| Open-world misread | “No” reported for an empty result | Decide whether the product uses closure or explicit negatives, and say which. |
| Retrieval miss | Answer ignores a document that contains the fact | Measure recall@k separately from answer accuracy. |
| Unsupported generation | Fluent answer, citation does not entail it | Check entailment between the answer and each cited passage, not just topical overlap. |
| Valid query, wrong question | Query executes; answer is off by one relation | Compare the query with the question’s logical form. Executability is not intent. |
| Stale or conflicting graph | Answer reflects an old release or two contradictory triples | Check timestamps, source precedence, and whether the graph has a truth-maintenance policy. |
A five-check protocol catches most of these before a number is reported. Parse: is there a query, and does it type-match? Link: do mentions resolve to the intended IDs? Execute: what are the intermediate bindings and join sizes? Support: which triples or passages entail the answer? Cover: is the fact in the graph or corpus at all? The last is most often skipped, and it decides whether a low score is a modelling or data failure.
Evaluation must match the claim. For “answers from this graph,” report answer and query accuracy on a held-out set, with coverage. For “grounded in documents,” report retrieval recall and faithfulness separately. For “reasons over the ontology,” report entailment under a named regime and a proof checker. One number cannot support all three. Benchmark contamination is a further hazard: template-generated questions measure template recognition.
A parser that refuses a question is visibly broken. A query that runs and returns a confident wrong answer is not; it looks like success wherever only the final string is reported.
07 / The tuple & casesRead each system the same way.
The tuple: representation, inference, coupling, guarantee, plus cost for a product. It forces the question the marketing copy avoids: what is doing the composition, and what would make the answer wrong?
| System | Representation | Inference | Coupling | Guarantee | Cost |
|---|---|---|---|---|---|
| RAG (Lewis et al., 2020) | Text passages plus a generator | Similarity retrieval then generation | Prompt | Empirical | Index, retrieval latency, context |
| Semantic parser (Berant et al., 2013; Yih et al., 2016) | Triples plus ontology | Query evaluation | Parser + executor | Sound relative to query and KG | Schema engineering, parse errors |
| Think-on-Graph (Sun et al., 2023) | Triples | LLM-guided beam search over relations | Tool use | Empirical | Many model calls; beam width |
| KAPING (Baek et al., 2023) | Verbalized triples | In-context reading | Prompt | Empirical | Retrieval coverage; context budget |
| BERTMap (He et al., 2021) | Two ontologies | Contextual matching plus repair | Data | Empirical | Alignment review; label drift |
| Logic-LM (Pan et al., 2023) | First-order logic | Solver | Tool use | Sound relative to the formalization | Formalization errors; solver cost |
Read by column. Representation says what can be stored; inference what can be derived; coupling where information crosses; guarantee what “correct” means. RAG and SPARQL parsing can both answer a film question. Only one can show the join; only one can answer from a document that never names the film.
The field rebuilds the same system under new names. KAPING is retrieval with triples instead of passages; Think-on-Graph is a parser that searches instead of translating; BERTMap is relation extraction at schema level; Logic-LM is parsing into a logic solver. The interfaces differ; the questions are stable: what is the symbolic object, what executes it, what does execution guarantee?
A RAG guarantee is empirical: composition happens inside the generator, and no object can be checked independently. A semantic parser’s guarantee is conditional: the query can be wrong even when it executes. Neither is better in the abstract; they make different promises, meaningful only when the task and evidence are named.
Real systems mix patterns: RAG can call a SPARQL tool, a parser can fall back to retrieval, an LLM can build the KG. The tuple forces you to say which part is doing the work.
08 / RecapWhat you should be able to do now.
Distinguish retrieval, semantic parsing, and reasoning over a KG by their outputs and guarantees.
Read a question as a graph pattern: variables, constants, relations, projected answer.
Explain why a knowledge graph is open-world, and why “no answer” is not “no.”
Name the KGQA query shapes: single-hop, multi-hop, conjunctive, filter, aggregation, negation, path.
State RAG’s limits: relevance is not entailment, and retrieval is not a join.
Recognize the four LLM + KG patterns and their directions.
Trace a triple from extraction to query, and find the stage where a wrong answer entered.
Evaluate a system against its claim: answer, query, retrieval recall, faithfulness, or entailment.
Exercises
- Write the query. Write the hook question’s SPARQL with directions, constants, and
DISTINCT. Remove one pattern; what question does the shorter query answer? - Separate the routes. Find one question a retriever answers well and one that needs a join. What evidence can each system show?
- Break the lab. Ask a question outside the templates. Read the fallback. Why is a ranked list of triples not an executed query, and where would it mislead a user?
- Add a fact. Add one triple and one template. What changes in the parse, query, and derivation? What breaks if the triple contradicts an existing one?
- Align two schemas. Write two small ontologies with different relation names. Propose three alignments, one a subproperty rather than an equivalence. How would you test them?
- Audit a RAG answer. For each citation, decide whether it entails the answer, merely mentions the entities, or contradicts it.
Check your understanding
Ten questions with explanations. The misses are the reading list.
Reading list
The first four are the spine; the rest are the LLM patterns and the extraction pipeline.
Knowledge Graphs
Hogan et al. · ACM Computing Surveys 2021 · data model, ontologies, querying
Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
Lewis et al. · NeurIPS 2020 · the retrieval interface
Complex Knowledge Base Question Answering: A Survey
Lan et al. · 2021 · query shapes and methods
A Survey on Semantic Parsing
Kamath & Das · 2018 · grammar, alignment, weak supervision
Unifying Large Language Models and Knowledge Graphs: A Roadmap
Pan et al. · 2023 · three directions
Think-on-Graph
Sun et al. · ICLR 2024 · LLM-guided search over a KG
Knowledge-Augmented Language Model Prompting for Zero-Shot KGQA
Baek et al. · 2023 · triples in the prompt
A Comprehensive Survey on Relation Extraction
Zhao et al. · 2023 · extraction and evaluation
BERTMap: A BERT-based Ontology Alignment System
He et al. · AAAI 2022 · contextual schema matching
Lost in the Middle: How Language Models Use Long Contexts
Liu et al. · TACL 2024 · more text is not more evidence
Both figures are schematic redrawings. The citations identify the systems and claims; the drawings are ours. No benchmark score is quoted: a score without its benchmark, split, and baseline is decoration. The lab graph is fictional, so every triple and answer can be checked by hand.