Before you start: review of the earlier sessions
The thread so far. Session 10 built per-KG embeddings; session 15 closes the loop by making them transferable, with the equivariance thinking of sessions 6–8.
What this session takes from earlier ones
- Lecture 10: shallow KG embeddings: the bottom rung of the inductiveness ladder
- Lecture 9: R-GCN, inductive over entities but not relations
- Lecture 14: foundation models and in-context learning as the goal
Those sessions in one minute each
Lecture 14 · Advanced Topics in GNNs — In-Context Learning and Relational Foundation Models
Foundation models for graphs need a universal input format: PRODIGY turns any few-shot graph task into link prediction on a prompt graph; the Relational Transformer turns any database task into masked-cell prediction over (value, column, table) tokens — and both are pretrained on self-generated tasks in that same format.
Lecture 10 · Knowledge Graph Embeddings
A KG embedding turns each relation into a geometric operation; the algebra of that operation (commutative or not, invertible or not, composable or not) decides which logical patterns of relations the model can represent.
Lecture 9 · Heterogeneous Graphs
Treat each relation type (source type, edge type, target type) as its own channel of messages, aggregate within and then across channels — and share or factorise weights so the parameter count doesn't grow with every new relation.
Warm-up: answer these before you read on
How does PRODIGY turn classification into link prediction? from Lecture 14
Label nodes are added to the task graph; a query node is classified by predicting which label node it should be linked to.
Why can TransE not model symmetric relations? from Lecture 10
h + r ≈ t and t + r ≈ h together force r ≈ 0, which makes h ≈ t for every pair.
Why can one-hot node types fail as a substitute for a heterogeneous model? from Lecture 9
When node types have different feature dimensions, or when the same message operator cannot express that "writes" and "cites" should transform the neighbour differently.
Why pretrain in the prompt-graph format rather than with ordinary supervised tasks? from Lecture 14
So that the model learns to read examples from the prompt; a model pretrained on fixed labels has no mechanism for using in-context examples.
More questions from every session you have reached, with spaced repetition: the cumulative review.
In short
Foundation models (LLMs, vision models, protein models like ESM, cell models like UCE) are large pretrained models that work zero- or few-shot and generalise to entities never seen in training. Graphs are harder: many graph types and many task types. Here we target knowledge graphs: one model that embeds entities and relations of any KG, trained unsupervised (KG completion), transferring between KGs.
The lecture is a ladder of inductiveness. Shallow KG embeddings (Lecture 10): both entities and relations are free vectors — retrain for a new drug. R-GCN: entity embeddings come from a GNN over structure, so new entities are fine — but relations are still learned weight matrices, so a KG with new relation types is out of reach. InGram (and ULTRA): build a relation graph from how relations share head/tail entities, run a GNN over it to get relation embeddings, then run an entity-level GNN conditioned on them. Now both entities and relations are computed from structure — double equivariance — enabling link prediction on KGs with entirely new entities and relations.
The picture: the inductiveness ladder
How to read it (hover a step)
- Shallow: entity and relation embeddings are trainable weights; structure appears only in the loss. Usable on one KG only.
- R-GCN: structure-aware GNN encoder for entities (inductive over new entities), but structure-agnostic relation weights — can't transfer to KGs with different relation types.
- InGram: relations also get structure-aware embeddings, computed by a GNN over a relation graph; entity message passing uses those relation embeddings. Nothing is tied to a specific ID → transfer to new entities and new relations.
1 · Foundation models, and why graphs are different
Examples across fields: LLMs (few-shot learners), vision (SAM, DALL·E), relational foundation models (Lectures 13–14), biology (ESM protein language models), cell biology (UCE — universal cell embeddings from RNA expression), generalist medical AI. Common characteristics: pretrained at scale, usable zero/few-shot, generalise to unseen entities.
Graph foundation models face two challenges: many graph types and many task types. PRODIGY (Lecture 14) unified tasks; this lecture unifies KGs with different vocabularies.
Why is "a foundation model for KGs" harder than for text, even though both are about facts?
In text, everything is a token from one shared vocabulary, connected sequentially. In KGs there are two modalities (entities and relations), each KG has its own vocabulary of both (Wikidata's "P19" vs a biomedical "has_func"), and entities sit in complex graph structure, not a sequence. A model whose parameters are indexed by vocabulary items (embedding tables, \(W_r\)) cannot transfer. The fix must make every parameter vocabulary-free — structural.
2 · Transductive link prediction (recap)
KG completion: for (head, relation), predict missing tails — e.g. (J.K. Rowling, genre, ?) → Science Fiction. Shallow models (TransE, TransR, DistMult, ComplEx, RotatE) embed entities and relations as lookup tables; the expressiveness table from Lecture 10 applies.
Limitations: structure-agnostic encoders; structure used only in the loss; one KG only. If a new drug enters a biomedical KG, you must retrain. If you want to move from one e-commerce KG (books) to another (video games), the shallow tables are useless.
3 · Inductive over new entities: heterogeneous GNNs
If two KGs share the same relation types (e.g. two shops with user–item–query and the same "search / click / guide" relations), treat the KG as a heterogeneous graph and use R-GCN or HGT. Entity embeddings come from neighbourhood structure, so new entities are handled. Score triples with a relation-specific function \(f_r(\mathbf h_E,\mathbf h_A)=\mathbf h_E^\top\mathbf W_r\mathbf h_A\).
But: relation embeddings are still structure-agnostic trainable weights. A KG with different relations (e.g. movie KG with "acted in", "directed", "born in", "profession") can't use a model trained on a bibliographic KG.
4 · InGram: inductive over new relations (ICML 2023)
Key move: do for relations what GNNs did for entities — move the structure of relations from the loss into the model. Build a relation graph whose nodes are relations and whose weighted edges say how strongly two relations share entities.
Building the relation graph
- \(E_h\): entities × relations; \(E_h[i,j]=1\) if entity \(i\) is a head in relation \(j\). \(E_t\): same for tails.
- \(D_h, D_t\): diagonal entity × entity matrices of head/tail degrees.
Entry \(A[r,r']\) sums, over entities that serve as heads (or tails) of both relations, \(1/\deg^2\) — shared low-degree entities count more (they're more specific evidence). Example from the slides: "born in" and "acted in" share heads with weight \(\beta=(1/3)^2+(1/7)^2=0.13\); "acted in" and "costarred" get 0.38; "costarred" and "directed" share no entity: \(\beta=0\).
Relation-level then entity-level message passing
- Relation-level aggregation: GAT-style attention over the relation graph, with the structural weight added as a bias: \(\alpha_{vu}=\text{softmax}_u(e_{vu}+\beta_{vu})\), producing relation embeddings \(\mathbf z_r\). The relation-graph weights are binned and each bin gets a learnable bias.
- Entity-level aggregation: combine a standard term \(\mathbf h_v^{\dagger}=\sigma(\sum_r\sum_{u\in N_v^r}\mathbf W_1\mathbf h_u+\mathbf W_0\mathbf h_v)\) with a relation-aware attention term \(\mathbf h_v^{*}=\sigma(\sum_r\sum_u\alpha_{urv}(\mathbf W_3\mathbf z_r+\mathbf W_2\mathbf h_u))\); \(\mathbf h_v=\mathbf h_v^\dagger+\mathbf h_v^*\). The entity update depends on the relation update.
- Link-prediction head: \(\mathbf z_k=\mathbf M\mathbf z_k^{(L)},\ \mathbf h_i=\hat{\mathbf M}\mathbf h_i^{(L)}\); score \(f(v_i,r_k,v_j)=\mathbf h_i^\top\mathrm{diag}(\bar{\mathbf W}\mathbf z_k)\mathbf h_j\) (a DistMult-style decoder with a computed relation vector); margin loss against corrupted triples.
Results: datasets built from NELL, Wikidata and Freebase where test KGs contain new entities and new relations (e.g. NL-100, WK-100, FB-100). InGram outperforms rule-based (GraIL, CoMPILE, NBFNet, RED-GNN…) and embedding baselines in inductive link prediction — a step towards KG foundation models.
5 · Double equivariance: the principle behind it
A KG model is doubly equivariant if relabelling entities by a permutation \(\pi\) and relabelling relations by a permutation \(\sigma\) relabels its predictions accordingly: \(f(\pi\circ\sigma\cdot G)=\pi\circ\sigma\cdot f(G)\). Then no parameter can depend on a particular entity or relation ID — exactly what's needed to apply the model to a KG with a different vocabulary.
- Shallow embeddings: neither (parameters indexed by entity and relation IDs).
- R-GCN: equivariant in entities, not in relations (\(W_r\) indexed by relation ID).
- InGram, ISDEA, ULTRA: equivariant in both.
ULTRA (Galkin et al., ICLR 2024) refines the idea: the relation graph has four fundamental interaction types — head-to-head, head-to-tail, tail-to-head, tail-to-tail — which exist in every KG, so the parameters of the relation-graph GNN are shared across all KGs. It uses conditional message passing (NBFNet-style, conditioned on the query relation). A single pretrained ULTRA performs zero-shot on dozens of unseen KGs, often matching or beating models trained on each.
The mathematics, step by step
Lecture 10 learned one vector per entity and per relation, so nothing transferred to a new knowledge graph. This session removes every parameter that is tied to a name. The mathematics is a chain: build a graph whose nodes are the relations, embed relations from it, embed entities using those, and check that the whole map commutes with renaming entities and relations.
Symbols used in this session
| symbol | meaning | what kind of object |
|---|---|---|
| \(n,\ m\) | number of entities and number of relations | whole numbers |
| \(E_h,\ E_t\) | \(E_h[i,j]\) = how often entity \(i\) is the head of relation \(j\); \(E_t\) the same for tails | \(n\times m\) matrices of counts |
| \(D_h,\ D_t\) | diagonal matrices with the row sums of \(E_h\), \(E_t\): how many triples entity \(i\) heads (or ends) | \(n\times n\) matrices |
| \(A_{\text{rel}}\) | weighted adjacency matrix of the relation graph: affinity between two relations | \(m\times m\) symmetric matrix |
| \(\mathbf z_r\) | embedding of relation \(r\), computed (not looked up) | vector |
| \(\mathbf h_v\) | embedding of entity \(v\), computed | vector |
| \((h,q,?)\) | a query: head entity \(h\), query relation \(q\), tail unknown | incomplete triple |
| \(\pi_e,\ \pi_r\) | a renaming (permutation) of the entities, and one of the relations | permutations |
1Why transductive models cannot transfer
In words. A model of Lecture 10 is two lookup tables. Every row belongs to one named entity or relation of the training graph.
Why it has this form. A new entity has no row; a new graph has no rows at all. Inductive models for new entities (GraIL, NBFNet) drop the entity table and compute an entity's representation from the relations around it, but still look up relation vectors, so they need the same relations at test time. A foundation model must drop the relation table as well: the relation embeddings must be computed from the structure of the new graph.
Watch out. 'Inductive' is used for two different things: new entities with known relations, and new entities with new relations. Only the second allows transfer across graphs.
2The relation graph
In words. Two relations are close if the same entities tend to be heads of both, or tails of both. The matrix counts these shared entities, down-weighting entities that take part in many triples.
Why it has this form. \((E_h^\top E_h)_{jk}=\sum_iE_h[i,j]E_h[i,k]\) counts, over entities \(i\), the co-occurrences of relations \(j\) and \(k\) as head relations, exactly like the bipartite projection of Lecture 1. Inserting \(D_h^{-2}\) divides entity \(i\)'s contribution by the square of its number of triples, so that a hub entity, which co-occurs with every relation, does not link all relations to each other. The second term does the same for tails. Nothing here uses the names of relations: only how they share entities.
Watch out. This is InGram's construction. ULTRA instead keeps four separate kinds of edges between relations (head–head, head–tail, tail–head, tail–tail), which preserves direction information that the sum above merges.
3Relation embeddings first, entity embeddings second
In words. Run a GNN on the relation graph to get a vector for every relation. Then run a GNN on the original graph in which each message is built from the neighbour's vector together with the vector of the connecting relation.
Why it has this form. The weights \(\mathbf W^{(l)}\) and the attention are shared across all entities and relations, so the parameter count does not depend on \(n\) or \(m\). A relation is characterised by its position among the other relations (step 1), an entity by the relations around it (step 2). Both steps can be run on a graph never seen in training. InGram starts each GNN from random vectors that are re-drawn at every epoch, so the network cannot memorise any particular initial vector and must rely on structure.
Watch out. Random initial features make the output random too; predictions are stable only because scores compare entities within the same run.
4Conditioning on the query (ULTRA)
In words. To answer the query \((h,q,?)\), start message passing with the query relation's vector on the head entity and zeros everywhere else. After \(L\) layers, each entity's vector says how it relates to \(h\) with respect to \(q\); a small network turns it into a score.
Why it has this form. With this initialisation, what reaches entity \(t\) after \(L\) layers is a sum over all paths of length up to \(L\) from \(h\) to \(t\), each path contributing according to the relations along it. The representation is of the pair \((h,t)\) under relation \(q\), not of \(t\) alone, which is what link prediction needs (two entities with the same neighbourhood can stand in different relations to \(h\)). The relation vectors themselves are produced the same way on the relation graph, starting from the query relation, so they are relative to \(q\) as well.
Watch out. One full message-passing run is needed per query (per head and relation), which costs more than a lookup; in return a single run scores all candidate tails at once.
5Double equivariance
In words. Rename the entities and, independently, rename the relations: the model's predictions must be the same predictions under the new names.
Why it has this form. Lecture 3 required equivariance to renaming nodes. A knowledge graph has a second set of arbitrary names, the relation identifiers. A model with a relation table breaks the second symmetry: swap the identifiers of two relations and it reads the wrong rows. A model that builds everything from the relation graph and shared weights satisfies both, and a model with this property can be moved to a graph whose relation names it has never seen, because names never entered the computation.
Watch out. Equivariance to relation renaming means the model cannot use what a relation's name means. Combining it with text embeddings of relation names gives up exact symmetry in exchange for that knowledge.
Check yourself
Questions from the lecture, in order. Answer each one in your head (or on paper) before you open it. If one stumps you, follow the link to the walkthrough block it comes from.
Check yourself: why is "relations of any KG" the hard part? show answer
A new KG may use relation types that never appeared in training, like "costarred" when the model was trained on "genre" and "influence". A model with one weight per relation has nothing to use for them.
from Towards graph and KG foundation models
Check yourself: Lanthimos is the head of both "directed" and "Born in" and also of "Profession". Why is the weight directed–Born in small (0.06)? show answer
Only one shared head, and each shared entity adds \(1/\deg^2\); a few shared entities give a small weight.
Lecture walkthrough reference · slide by slide · opens on demand
The whole lecture in order, grouped by topic. Every drawing on the slides is redrawn here as a clean figure (click the step buttons where a figure has them), the heading of each block links to the matching pages of the official PDF, and the Review section after the walkthrough ties this session to the earlier ones. Read this and you do not need the deck.
- Foundation models everywhere
- Towards graph and KG foundation models
- KG representation, examples, and KGs vs natural language
- Transductive link prediction: shallow KG embeddings and their limits
- Same relations, new entities: heterogeneous GNNs and R-GCN
- R-GCN for link prediction, and what it still cannot do
- New entities and new relations: double equivariance
- InGram overview and the relation graph definition
- Relation graph construction: a worked example
- Relation-level message passing: attention with relation-graph weights
- Entity-level message passing
- Link-prediction head, InGram summary
- Experiments and summary of the lecture
Foundation models everywhere slides 4-10 ↗
The lecture opens with a tour of foundation models in different fields, to set the goal: can we build one for knowledge graphs?
- Large language models (slide 4). Left: an Economist piece, "How does ChatGPT actually work?", which says LLMs are "a giant exercise in statistics". Right: the GPT-3 paper, "Language Models are Few-Shot Learners" (Brown et al., OpenAI). Its Figure 1.2 plots accuracy against the number of examples in the context (zero-shot, one-shot, few-shot) for models of 1.3B, 13B and 175B parameters. Larger models use in-context examples much more efficiently: the 175B curve climbs steeply, the 1.3B curve stays near zero.
- Computer vision (slide 5): an image of a building with regions labelled by "DALLE 2 + SAM" and "DALLE 2": a generative model (DALL·E 2) combined with a general segmentation model (Segment Anything).
- Relational foundation model (slide 6): one frozen model answers questions over many databases: "What will user 123 buy next?", "Will user 321 churn soon?", "Is transaction 557 fraudulent?", "Will clinic 987 have high appointment demand?", "Is patient 234 at risk of hospital readmission?". The figure shows three schemas, (a) e-commerce, (b) finance, (c) health care, and the model outputs predictions, explanations and evaluation. The caption lists the key capabilities: apply to new, unseen databases and schemas; any predictive task type; new tasks without task-specific tuning; explanations. (This is the topic of Lectures 13–14.)
- Biology (slide 7): a New York Times article, "A.I. Is Learning What It Means to Be Alive", and the architecture of ESM (EvolutionaryScale): protein tracks (sequence, structure tokens, secondary structure SS8, solvent accessibility SASA, function) are embedded and summed, passed through transformer blocks with geometric attention, and projected back to logits for each track.
- Cell biology (slide 8): UCE (Universal Cell Embeddings) creates universal representations of cells. Input: the RNA expression of a single cell or nucleus. Output: a cell embedding. The figure shows genes sampled by expression, represented by protein language-model tokens, and fed to a transformer.
- Medicine (slide 9): "Foundation models for generalist medical artificial intelligence" (GMAI). One model is trained self-supervised on many modalities (text, audio, images, EHRs, signals, omics, graphs), uses medical knowledge sources (literature, clinical notes, knowledge graphs), and supports flexible interactions and applications (chatbots, note-taking, radiology reports, bedside decision support).
Slide 10 gives a definition (the answer of a chatbot to "define a foundation model"): a large-scale model trained on broad data that serves as a general-purpose model across many tasks (GPT-3, BERT, CLIP). It is characterized by:
- Pretraining on large datasets with self-supervised or unsupervised learning.
- Scalability: large architectures with billions or trillions of parameters.
- Adaptability: after pretraining, fine-tuned or adapted to many downstream tasks with little task-specific data.
- Transfer learning: knowledge from pretraining transfers to new domains.
Notice that graphs and knowledge graphs already appear inside the medical foundation model of slide 9 as one modality. This lecture asks whether graphs can have their own foundation model.
Towards graph and KG foundation models slides 11-14 ↗
Slide 11 lists four characteristics of foundation models:
- They are pretrained architectures.
- Modern AI trains very large models on a huge amount of data.
- They can be used as zero-shot or few-shot learners.
- They generalize to new entities that were not observed during training.
The last point is the key one for this lecture. A shallow KG embedding (Lecture 10) has one learned vector per entity, so it cannot handle an entity it never saw.
Slide 12, graph foundation models: the challenges are multiple types of graphs (social networks, knowledge graphs, molecules in the pictures) and multiple types of tasks.
Slide 13 recalls PRODIGY (Lecture 14): a unified framework to learn graph tasks at multiple levels (node, edge, graph), agnostic of the graph type. Pipeline: pretraining data → data generation (Prompt Graphs) → model → optimize loss.
Slide 14 sets today's goal, towards foundation models for KGs:
- Build a model that learns embeddings for entities and relations of any KG.
- Train it in an unsupervised fashion.
- It should transfer knowledge between different KGs.
- Scalability of the training data and of the model is not discussed.
Check yourself: why is "relations of any KG" the hard part? show answer
A new KG may use relation types that never appeared in training, like "costarred" when the model was trained on "genre" and "influence". A model with one weight per relation has nothing to use for them.
KG representation, examples, and KGs vs natural language slides 16-22 ↗
Slide 16 recalls the representation from Lecture 10. Edges in a KG are triples \((h, r, t)\): head \(h\) has relation \(r\) with tail \(t\). Key idea:
- Model entities and relations in an embedding space \(\mathbb{R}^k\), with shallow embeddings (note: no GNN is learned here).
- Given a true triple \((h, r, t)\), the embedding of \((h, r)\) should be close to the embedding of \(t\).
- Design questions: how to embed \((h, r)\)? How to define the score \(f_r(h, t)\)? The score should be high if \((h, r, t)\) exists and low otherwise.
Examples of KGs:
- Slide 17, bio KG. Node types: drug, disease, adverse event, protein, pathways. Relation types: has_func, causes, assoc, treats, is_a.
- Slide 18, bibliographic network. Node types: paper, title, author, conference, year. Relation types: pubWhere, pubYear, hasTitle, hasAuthor, cite (Paper is in the centre of the schema).
- Slide 19, e-commerce graph. Node types: User, Item, Query, Location, … Edge types: Purchase, Visit, Guide, Search, … Different node types can have different feature spaces. The figure links three users to items (shoes, a handbag) and queries ("Shoes", "Ladies Bag", "Hand Bag") with Search, Click and Guide edges.
Slides 20–22 compare a KG with natural language, using the sentence "User searches for shoes, User buys hand-bag":
- In language, all items are words or tokens of the same type: a homogeneous vocabulary. In the KG, "User", "shoes", "hand-bag" are entities and "searches", "buys" are relations: two modalities, a heterogeneous vocabulary.
- In language, tokens are connected sequentially. In a KG, entities have an underlying complex graph structure.
Why this matters: an LLM's vocabulary is fixed and shared across all texts, so transfer is natural. A new KG brings a new vocabulary of entities and relations, with no fixed order. A KG foundation model must handle a vocabulary it has never seen.
Transductive link prediction: shallow KG embeddings and their limits slides 23,25-30 ↗
Slide 23 gives the recipe for a KG foundation model, which the rest of the lecture fills in:
- Learn embeddings for entities and relations of any KG → double equivariant architectures.
- Process the graph structure between entities → use graph neural networks.
- Find a canonical task for unsupervised training → knowledge graph completion.
Slide 25 recalls the KG completion task: given an enormous KG, for a given (head, relation), predict the missing tails. The example graph has authors (J.R.R. Tolkien, Stephen King, J.K. Rowling, Alan Poe, C.S. Lewis, Lloyd Alexander), genres (Science Fiction, Fantasy, Tragicomedy) and relations genre and Influence; the task is to predict "Science Fiction" for ("J.K. Rowling", "genre").
Slide 26: the simplest encoder is an embedding lookup. The matrix \(\mathbf{Z}\) has one column per node; its height is the embedding dimension.
Slide 27 recalls the KG embedding models and which relation patterns each can express:
| Model | Score | Embedding | Sym. | Antisym. | Inv. | Compos. | 1-to-N |
|---|---|---|---|---|---|---|---|
| TransE | \(-\lVert \mathbf{h}+\mathbf{r}-\mathbf{t}\rVert\) | \(\mathbb{R}^k\) | no | yes | yes | yes | no |
| TransR | \(-\lVert M_r\mathbf{h}+\mathbf{r}-M_r\mathbf{t}\rVert\) | \(\mathbf{h},\mathbf{t}\in\mathbb{R}^k, \mathbf{r}\in\mathbb{R}^d, M_r\in\mathbb{R}^{d\times k}\) | yes | yes | yes | yes | yes |
| DistMult | \(\langle \mathbf{h},\mathbf{r},\mathbf{t}\rangle\) | \(\mathbb{R}^k\) | yes | no | no | no | yes |
| ComplEx | \(\mathrm{Re}\langle \mathbf{h},\mathbf{r},\bar{\mathbf{t}}\rangle\) | \(\mathbb{C}^k\) | yes | yes | yes | no | yes |
| RotatE | \(-\lVert \mathbf{h}\circ\mathbf{r}-\mathbf{t}\rVert\) | \(\mathbb{C}^k\) | yes | yes | yes | yes | no |
Slide 28 summarizes KG embedding methods:
- Structure-agnostic shallow encoders learn embeddings for entities and relations; these embeddings are the trainable weights.
- The structure of the KG is used only in the loss function (which triples are positive).
- They can be used on a single KG only; they cannot transfer knowledge between KGs.
Slides 29–30 make the limits concrete. Slide 29: in a bio KG, what if a new drug comes in? It has no learned vector, so we need to retrain the shallow encoder. Slide 30: what if we want to transfer knowledge from one KG to another, when the KGs have the same relations? The two e-commerce graphs share Search/Click/Guide, but the second one has new items (books, an Xbox, the game NBA2K). Shallow embeddings of the first graph say nothing about these new items.
This is transductive link prediction: train and test on the same set of entities.
Same relations, new entities: heterogeneous GNNs and R-GCN slides 32-38 ↗
Slide 32 solves the case of slide 30 (transfer between KGs with the same relations). Observe that a KG is a heterogeneous graph, and use a heterogeneous GNN, for example R-GCN or the Heterogeneous Graph Transformer. A GNN computes an entity's embedding from its neighbourhood, so a new entity gets an embedding as soon as it has edges.
Slides 33–35 recall R-GCN (Lecture 9) on the example graph with nodes A–F and relations \(r_1, r_2, r_3\) (A is the target node). What if the graph has multiple relation types? Use different neural network weights for different relation types: \(\mathbf{W}_{r_1}\), \(\mathbf{W}_{r_2}\), \(\mathbf{W}_{r_3}\) (coloured boxes on slide 34). Slide 35 draws A's computation graph: each neighbour's message passes through the box of its relation, then all messages are aggregated into A.
Slide 36 recalls the GCN layer (Kipf and Welling, ICLR 2017): \[ \mathbf{h}_v^{(l)} = \sigma\Big( \sum_{u\in N(v)} \mathbf{W}^{(l)} \frac{\mathbf{h}_u^{(l-1)}}{|N(v)|} \Big), \] and with a self-loop: \[ \mathbf{h}_v^{(l)} = \sigma\Big( \sum_{u\in N(v)} \mathbf{W}^{(l)} \frac{\mathbf{h}_u^{(l-1)}}{|N(v)|} + \mathbf{W}^{(l)} \mathbf{h}_v^{(l-1)} \Big). \]
Slide 37: introduce one set of weights for each relation type (rel_1 … rel_N) plus a weight for the self-loop. Slide 38 gives the R-GCN definition: \[ \mathbf{h}_v^{(l+1)} = \sigma\Big( \sum_{r\in R} \sum_{u\in N_v^r} \frac{1}{c_{v,r}} \mathbf{W}_r^{(l)} \mathbf{h}_u^{(l)} + \mathbf{W}_0^{(l)} \mathbf{h}_v^{(l)} \Big). \] As message + aggregation:
- Message from each neighbour of a given relation, normalized by the node's degree for that relation, \(c_{v,r} = |N_v^r|\): \(\mathbf{m}_{u,r}^{(l)} = \frac{1}{c_{v,r}} \mathbf{W}_r^{(l)} \mathbf{h}_u^{(l)}\).
- Self-loop message: \(\mathbf{m}_v^{(l)} = \mathbf{W}_0^{(l)} \mathbf{h}_v^{(l)}\).
- Aggregation: sum the messages from neighbours and the self-loop, then apply the activation: \(\mathbf{h}_v^{(l+1)} = \sigma\big(\mathrm{Sum}(\{\mathbf{m}_{u,r}^{(l)}, u\in N(v)\} \cup \{\mathbf{m}_v^{(l)}\})\big)\).
R-GCN for link prediction, and what it still cannot do slides 39-40 ↗
Slide 39 recalls how R-GCN does link prediction. Assume \((E, r_3, A)\) is a training supervision edge and all other edges are training message edges. Use R-GCN to score \((E, r_3, A)\):
- Take the final-layer embeddings of E and A: \(\mathbf{h}_E^{(L)}, \mathbf{h}_A^{(L)} \in \mathbb{R}^d\).
- Use a relation-specific score function \(f_r: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}\). One example: \(f_{r_3}(\mathbf{h}_E, \mathbf{h}_A) = \mathbf{h}_E^\top \mathbf{W}_{r_3} \mathbf{h}_A\), with \(\mathbf{W}_{r_3} \in \mathbb{R}^{d\times d}\).
Slide 40 summarizes heterogeneous GNNs:
- Structure-aware GNN encoders learn embeddings for entities.
- Structure-agnostic shallow encoders still learn embeddings for relations: the relation embeddings (\(\mathbf{W}_r\)) are trainable weights.
- The structure of the KG is also used in the loss function.
- R-GCN can do inductive link prediction across new entities.
- But it cannot transfer knowledge between KGs with different relation types.
So we have climbed one step. Entities moved from "trainable weights" to "computed from structure". Relations have not moved yet. Check yourself: in R-GCN, what happens at test time if an edge has a relation type \(r_{\text{new}}\) never seen in training? (There is no \(\mathbf{W}_{r_{\text{new}}}\), neither for message passing nor for scoring.)
New entities and new relations: double equivariance slides 42-45,47-48 ↗
Slide 42 poses the hardest case: transfer knowledge from one KG to another when the KGs have different entities and different relations.
Slides 43–44 show it on examples. Slide 43: we train a model on one KG (the authors-and-genres graph of slide 25: genre, Influence). Slide 44: given the trained model, we want to do completion on a completely different KG: a movie graph with Olivia Colman, Emma Stone, Ryan Gosling, Yorgos Lanthimos, films (The Favorite, Poor Things, LaLa Land), countries (UK, Greece, USA, Canada), professions (actor, director), and relations Born in, Acted in, directed, costarred, Profession. The task: predict the tail "actor" for ("R. Gosling", "profession"). None of these entities or relations appeared in training.
Slide 45 recalls the easier case (same relations, slide 30), solved by heterogeneous GNNs. Slide 47 gives the solution for the hard case: build double equivariant models, for example InGram (Lee, Chung, Whang, "InGram: Inductive Knowledge Graph Embedding via Relation Graphs", ICML 2023).
What does "double equivariant" mean? If you rename (permute) the entities, the outputs are renamed the same way; and if you rename (permute) the relation types, the outputs are also renamed the same way. A model with a weight per named relation is not equivariant to renaming relations, because the name picks the weight. A model that treats relations only through their pattern of use is.
Slide 48 gives the idea by analogy:
- We achieved inductive link prediction on new entities by going from structure-agnostic shallow encoders to structure-aware GNN encoders that learn embeddings for entities.
- The structure of the KG moved from the loss function only to the loss function and the model.
- Let's do the same for relations: use the structure of relations to generate relation embeddings.
Intuition: in the movie KG, the model has never seen the word "costarred". But it can see that "costarred" connects people who both "Acted in" the same films. How a relation sits among other relations is information that transfers.
InGram overview and the relation graph definition slides 49-51 ↗
Slide 49 shows the InGram pipeline (figure from the authors' slides). Training time, left to right:
- Training graph: a KG with relations \(r_1, \dots, r_5\).
- Build the relation graph of the training graph: one node per relation (r1–r5), edges between related relations.
- Relation-level aggregation: a GNN over the relation graph computes relation embeddings.
- Entity-level aggregation: a GNN over the original KG computes entity embeddings, using the relation embeddings.
- Loss optimization: score (head, relation, tail).
Inference time: a new graph with different relations (\(r_6, \dots, r_9\)). Build its relation graph, then apply the same learned weights (blue arrows) for relation-level aggregation, entity-level aggregation and scoring, and predict missing links (dashed orange edges r7, r8, r9). The new component is the relation graph.
Slide 50 defines three kinds of matrices (the slide says "tree", meaning three):
- \(E_h\): head-entities × relations adjacency, \(E_h[i,j] = 1\) if entity \(i\) is a head in relation \(j\).
- \(E_t\): tail-entities × relations adjacency, \(E_t[i,j] = 1\) if entity \(i\) is a tail in relation \(j\).
- \(D_h, D_t\): diagonal entity × entity matrices with the entity degrees as heads and as tails.
Slide 51: the adjacency matrix of relations is \[ A = E_h^\top D_h^{-2} E_h + E_t^\top D_t^{-2} E_t . \] \(A\) is a weighted adjacency matrix: each edge has a weight that tells how important it is. In practice we are looking for entities that serve as heads and/or tails for relation pairs.
Read the formula entry by entry: \(A[r_i, r_j] = \sum_{e} \frac{E_h[e,r_i]E_h[e,r_j]}{\deg_h(e)^2} + \sum_{e} \frac{E_t[e,r_i]E_t[e,r_j]}{\deg_t(e)^2}\). Two relations are close if many entities are heads of both or tails of both. Each shared entity contributes \(1/\deg^2\), so a hub entity that touches every relation adds almost nothing, while a specific entity adds a lot (the same idea as down-weighting common words in TF-IDF).
Relation graph construction: a worked example slides 52-57 ↗
Slides 52–56 compute relation-graph weights \(\beta\) on the movie KG of slide 44. For each pair of relations, keep only the edges of those two relations and look for entities that serve as heads and/or tails for both.
- Slide 53, Born in and Acted in: the shared heads are Olivia Colman and Emma Stone. Their contributions give \[ \beta = \left(\tfrac{1}{3}\right)^2 + \left(\tfrac{1}{7}\right)^2 = 0.13 . \] (Olivia Colman has 3 outgoing edges in the full graph: Born in, Acted in, Profession; Emma Stone is a hub with 7.)
- Slide 54, Acted in and costarred: three entities contribute, \[ \beta = \left(\tfrac{1}{3}\right)^2 + \left(\tfrac{1}{7}\right)^2 + \left(\tfrac{1}{2}\right)^2 = 0.38 . \]
- Slide 55, directed and Acted in: the shared tails are the films The Favorite (3 incoming edges: two "Acted in", one "directed") and Poor Things (2 incoming edges), \[ \beta = \left(\tfrac{1}{3}\right)^2 + \left(\tfrac{1}{2}\right)^2 = 0.36 . \]
- Slide 56, costarred and directed: no entity plays the same role in both, so \(\beta = 0\).
Slide 57 shows the resulting relation graph: five nodes (directed, costarred, Acted in, Profession, Born in) with weighted edges. It encodes the proximity between relations. The weights shown: costarred–Acted in 0.38, directed–Acted in 0.36, Born in–costarred 0.27, Born in–Profession 0.17, Born in–Acted in 0.13, Profession–Acted in 0.13, Profession–costarred 0.13, and 0.06 for directed–Born in and directed–Profession.
Notice that the relation graph does not depend on the names of relations, only on how entities connect to them. That is exactly why a model built on it can handle a KG whose relations it never saw.
Check yourself: Lanthimos is the head of both "directed" and "Born in" and also of "Profession". Why is the weight directed–Born in small (0.06)? show answer
Only one shared head, and each shared entity adds \(1/\deg^2\); a few shared entities give a small weight.
Relation-level message passing: attention with relation-graph weights slides 58-63 ↗
Slide 58 repeats the InGram pipeline: next is relation-level message passing on the relation graph. It uses graph attention, so slides 59–62 recall GAT (Lecture 4).
Slide 59: the GAT layer is \[ \mathbf{h}_v^{(l)} = \sigma\Big( \sum_{u\in N(v)} \alpha_{vu} \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \Big), \] with attention weights \(\alpha_{vu}\). Not all of a node's neighbours are equally important. Attention is inspired by cognitive attention: \(\alpha_{vu}\) focuses on the important parts of the input and fades out the rest. The network should devote more computing power to that small but important part, and which part matters depends on the context and is learned in training.
Slide 60: let \(\alpha_{vu}\) be a byproduct of an attention mechanism \(a\). First, \(a\) computes attention coefficients across pairs of nodes from their messages: \[ e_{vu} = a\big(\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}, \mathbf{W}^{(l)}\mathbf{h}_v^{(l-1)}\big). \] \(e_{vu}\) indicates the importance of \(u\)'s message to \(v\).
Slide 61: the approach is agnostic to the choice of \(a\). For example, a single-layer network: concatenate the two messages and apply a linear layer, \(e_{AB} = \mathrm{Linear}(\mathrm{Concat}(\mathbf{W}^{(l)}\mathbf{h}_A^{(l-1)}, \mathbf{W}^{(l)}\mathbf{h}_B^{(l-1)}))\). The parameters of \(a\) are trained jointly with the weight matrices, end to end.
Slide 62: normalize with a softmax so that \(\sum_{u\in N(v)} \alpha_{vu} = 1\): \[ \alpha_{vu} = \frac{\exp(e_{vu})}{\sum_{k\in N(v)} \exp(e_{vk})}, \] then take the weighted sum. For node A with neighbours B, C, D: \(\mathbf{h}_A^{(l)} = \sigma(\alpha_{AB}\mathbf{W}^{(l)}\mathbf{h}_B^{(l-1)} + \alpha_{AC}\mathbf{W}^{(l)}\mathbf{h}_C^{(l-1)} + \alpha_{AD}\mathbf{W}^{(l)}\mathbf{h}_D^{(l-1)})\).
Slide 63, InGram's relation attention mechanism. The nodes are now relations, with embeddings \(\mathbf{z}\). The only change is a term \(\beta_{vu}\) inside the softmax: \[ \alpha_{vu} = \frac{\exp(e_{vu} + \beta_{vu})}{\sum_{k\in N(v)} \exp(e_{vk} + \beta_{vk})}, \qquad \mathbf{z}_v^{(l)} = \sigma\Big(\sum_{u\in N(v)} \alpha_{vu} \mathbf{W}^{(l)} \mathbf{z}_u^{(l-1)}\Big). \] \(\beta_{vu}\) comes from the relation-graph weight between relations \(v\) and \(u\) (slides 52–57). So a relation listens more to relations that share many specific entities with it.
In the InGram paper, the affinity values are grouped into bins and each bin gets a learnable bias; the slides simplify this to "add \(\beta\)". Either way, the structural affinity steers the attention.
Entity-level message passing slides 64-65 ↗
Slide 64 repeats the pipeline: next is entity-level message passing on the original KG, now that every relation \(r\) has an embedding \(\mathbf{z}_r\).
Slide 65, the entity attention mechanism. Two terms are computed and added: \[ \mathbf{h}_v^{\dagger(l+1)} = \sigma\Big( \sum_{r\in R} \sum_{u\in N_v^r} \mathbf{W}_1^{(l)} \mathbf{h}_u^{(l)} + \mathbf{W}_0^{(l)} \mathbf{h}_v^{(l)} \Big), \] \[ \mathbf{h}_v^{*(l+1)} = \sigma\Big( \sum_{r\in R} \sum_{u\in N_v^r} \alpha_{urv} \big( \mathbf{W}_3^{(l)} \mathbf{z}_r^{(l)} + \mathbf{W}_2^{(l)} \mathbf{h}_u^{(l)} \big) \Big), \] \[ \mathbf{h}_v^{(l+1)} = \mathbf{h}_v^{\dagger(l+1)} + \mathbf{h}_v^{*(l+1)} . \]
- The first term looks like R-GCN, but with one shared \(\mathbf{W}_1\) for all relations instead of a \(\mathbf{W}_r\) per relation. That is what makes it work for unseen relations.
- The second term brings in the relation: each message from neighbour \(u\) via relation \(r\) contains the relation embedding \(\mathbf{z}_r\), and is weighted by an attention \(\alpha_{urv}\) that depends on the triple.
So the entity update depends on the relation update: the relation-level GNN runs first, and its output feeds every entity message. All weights (\(\mathbf{W}_0, \dots, \mathbf{W}_3\), attention) are shared across relations, so the model never needs a parameter tied to a relation's name.
Link-prediction head, InGram summary slides 66-69 ↗
Slide 66 repeats the pipeline: next is the link-prediction head. Slides 67–68 (the same content) define it:
- Final embeddings: \(\mathbf{z}_k = \mathbf{M}\mathbf{z}_k^{(L)}\) for relation \(k\), and \(\mathbf{h}_i = \hat{\mathbf{M}}\mathbf{h}_i^{(\hat{L})}\) for entity \(i\) (a linear map of the last layer of each GNN; \(L\) and \(\hat L\) are the numbers of relation and entity layers).
- Scoring function, a DistMult-style score whose relation vector is computed, not looked up: \[ f(v_i, r_k, v_j) = \mathbf{h}_i^\top \,\mathrm{diag}(\overline{\mathbf{W}}\mathbf{z}_k)\, \mathbf{h}_j . \] The small figure shows head and tail vectors combined with the relation vector into one score.
- Loss, a margin (hinge) loss over true triples \((v_i, r_k, v_j) \in \mathcal{T}_{\text{tr}}\) and corrupted triples \((\mathring{v}_i, r_k, \mathring{v}_j) \in \mathring{\mathcal{T}}_{\text{tr}}\): \[ \sum_{(v_i,r_k,v_j)\in\mathcal{T}_{\text{tr}}} \ \sum_{(\mathring{v}_i,r_k,\mathring{v}_j)\in\mathring{\mathcal{T}}_{\text{tr}}} \max\big(0,\ \gamma - f(v_i,r_k,v_j) + f(\mathring{v}_i,r_k,\mathring{v}_j)\big). \] A true triple should score at least \(\gamma\) higher than a corrupted one (head or tail replaced).
Slide 69 summarizes InGram, completing the ladder of slides 28 and 40:
- Structure-aware GNN encoders learn embeddings for entities.
- Structure-aware GNN encoders learn embeddings for relations.
- The structure of the KG is also used in the loss function.
- InGram can do inductive link prediction across new entities and new relations. It is a model we can use to train a foundation model.
Check yourself: fill the table. Shallow embeddings: entities = weights, relations = weights. R-GCN: entities = computed, relations = weights. InGram: entities = computed, relations = computed.
Experiments and summary of the lecture slides 70-73 ↗
Slide 70, the experiments: create different datasets from NELL, Wikidata and Freebase, and test InGram in transductive and inductive link prediction. The metric is MRR (mean reciprocal rank of the true tail; higher is better).
Slide 71 (titled "Transductive Link Prediction"): bar charts of MRR on NL-0 and NELL-995-v1 for 14 methods, grouped by colour (GraIL, CoMPILE, SNRI, INDIGO, RMPI in orange; BLP, QBLP, RAILD in yellow; NeuralLP, DRUM, NBFNet, RED-GNN in green; CompGCN, NodePiece in grey) and InGram in blue. InGram has the highest MRR on both: about 0.27 on NL-0 (NBFNet is next at about 0.26) and about 0.73 on NELL-995-v1 (NodePiece is next at about 0.67).
Slide 72, "Inductive Link Prediction", on NL-100, WK-100 and FB-100, where the test KG has new entities and new relations:
- NL-100: InGram about 0.31; the best baseline, RMPI, about 0.22.
- WK-100: InGram about 0.11; RED-GNN about 0.10; most others near zero. Several subgraph-based methods (GraIL, CoMPILE, SNRI, INDIGO, RMPI) have no bar.
- FB-100: InGram about 0.22; RED-GNN about 0.12.
(Values are read from the bar charts.) The gap is largest exactly in the setting InGram was designed for.
Slide 73, summary:
- We introduced a model that learns embeddings for entities and relations of any KG.
- The model (InGram) is trained in an unsupervised fashion for KG completion.
- The model can transfer knowledge between different KGs.
- This is a step towards foundation models for KGs.
Remember slide 14: scalability was left out. Pretraining one InGram-style model on many KGs at once, and testing zero-shot on new ones, is the next step (this is what later work such as ULTRA does).
Not shown (no new content): slides 1,2,3,15,24,31,41,46 — title slides, announcements, and section-divider title pages.
Review: what to keep from this session
Carried forward. Lectures 16–17 use KGs as structured memory for LLM agents; Lecture 19 reviews the whole course.
Quick self-check
Why can R-GCN not handle an unseen relation?
Each relation has its own weight matrix learned in training; a new relation has no matrix.
What is the relation graph and why does it help?
A graph whose nodes are relations, connected when they share heads or tails; a GNN over it gives each relation an embedding from its structural role, so unseen relations get embeddings too.
State double equivariance in words.
Permute the entity labels or the relation labels and the model's predictions permute the same way; nothing depends on the names.
Key idea
Transfer across knowledge graphs requires that no parameter is tied to a specific entity or relation: build a relation graph from shared heads and tails, compute relation embeddings with a GNN on it, and compute entity embeddings with a GNN that uses them — a doubly equivariant model.
Worked example: one relation-graph weight
A tiny movie KG. Head occurrences: Emma is head of 3 triples (actedIn ×2, costarred ×1); Olivia is head of 2 (actedIn, bornIn); Yorgos is head of 2 (directed ×2).
- Relations sharing a head: (actedIn, costarred) via Emma; (actedIn, bornIn) via Olivia; (directed, directed) via Yorgos — no cross-relation pair.
- Head-part weights: \(A_h[\text{actedIn},\text{costarred}]=1/3^2=0.111\); \(A_h[\text{actedIn},\text{bornIn}]=1/2^2=0.25\); \(A_h[\text{costarred},\text{directed}]=0\).
- Add the tail part similarly (e.g. films as tails of actedIn and directed link those two relations).
- Interpretation: "bornIn" is close to "actedIn" because the same (rare, low-degree) entities do both — a structural signature that also exists in a completely different KG, so the GNN learned on one KG can read it in another.
Strictly speaking: \(E_h\) as defined is binary per (entity, relation); degree normalisation by \(D^{-2}\) is a design choice (inverse square of degree) that damps hubs. ULTRA instead uses the four unweighted interaction types.
Proof workshop: A relation graph does not care what you call your relations
One problem in olympiad style. Give it fifteen minutes on paper before you open the first hint; the hints are graded, so open them one at a time.
Problem. For a KG with relation set \(\mathcal R\), the relation graph \(G_{\mathcal R}\) has a node per relation and an edge \(r\xrightarrow{\ \kappa\ }r'\), for \(\kappa\in\{\)head-head, head-tail, tail-head, tail-tail\(\}\), whenever some entity plays the stated roles in a triple of \(r\) and a triple of \(r'\). Let \(\pi\) be any renaming of relations. Prove that \(\pi\) is an isomorphism from \(G_{\mathcal R}\) to the relation graph of the renamed KG. Conclude that any GNN on \(G_{\mathcal R}\) gives renamed predictions for renamed queries, and show by a two-relation example that a learned embedding table indexed by relation ID does not.
Hint 1
Hint 2
Solution
Why it matters. This is "double equivariance": equivariant in entities (by labelling trick and message passing) and in relations (by the relation graph). It is a symmetry argument, not a scale argument, and it is why ULTRA can be applied to a KG it has never seen. The open question in the frontier block is whether node classification has any invariance this clean.
Sharper lens: why pairs, and what symmetry cannot see
Not on the slides. Three or four points where the lecture rounds something off: the exact statement, a second way to see it, and where it stops being true. Each is short and has a pointer for going further.
Why a triple must be scored from a pair representation
Take any model that gives each entity one structural embedding and scores \((h,r,t)\) from \(\mathbf z_h\) and \(\mathbf z_t\). Nodes that an automorphism of the graph maps to each other get equal embeddings, so the model gives the same score to \((h,t)\) and \((h,t')\) whenever \(t\) and \(t'\) are automorphic, even if \(t\) is next to \(h\) and \(t'\) is far away. On a 6-cycle every node looks the same, so the pair at distance 1 and the pair at distance 3 are indistinguishable. Structural node embeddings cannot do link prediction (Srinivasan and Ribeiro, ICLR 2020).
The fix is the labelling trick (Zhang et al., NeurIPS 2021): mark the head node, then run message passing, so every other node's state is a function of its relation to the head. NBFNet does this as a generalised Bellman–Ford: one run from \((h,r)\) yields scores for all tails at cost \(O(|E|d+|V|d^2)\). A model with no entity embeddings, which double equivariance requires, has nothing but structure to work with, so ULTRA must be conditional. Huang et al. (NeurIPS 2023) pin down the power of such conditional MPNNs with a relational, asymmetric form of the 2-WL test.
The relation graph is Lecture 1's folding, with a hub penalty
\(E_h\) is a bipartite incidence matrix between entities and relations. InGram's \(E_h^\top D_h^{-2}E_h\) is that bipartite graph folded onto the relations, \(B^\top B\) from Lecture 1's worked example, with each shared entity down-weighted by the square of its degree. Lecture 1's proof workshop explains why the weight is needed: folding turns every entity into a clique among all the relations it takes part in, and a hub entity would connect almost every pair of relations. The penalty plays the role of \(1/\log k\) in Adamic–Adar (Lecture 20).
The general principle, which Lecture 14's Relational Transformer and Lecture 8's PEARL share: to transfer across vocabularies, no parameter may be indexed by a vocabulary item, so the only admissible description of an item is how it co-occurs with the others. Build that co-occurrence graph and run an equivariant network on it.
What double equivariance cannot tell apart
The invariance that makes transfer possible is also a blind spot. If some relabelling of relations maps the KG to itself, the model must treat those relations identically. Two relations with the same pattern of interactions, "likes" and "dislikes" recorded for the same kinds of users and items, or "retweets" and "quotes" on a platform where both connect the same account types, are exchangeable to a doubly equivariant model, and their difference in meaning is invisible. Names, text or a few labelled examples are then the only source of the distinction, which is the open question at the end of this page.
There is also a resolution limit inside the structure: ULTRA's relation graph records only pairs of relations that share an entity. Relation graphs built from richer motifs (three relations along a path) are strictly more expressive (Huang et al. 2025). The choice of which co-occurrences to record is the new design space.
Lab: hands-on and practical tips
Try it live. In the Graph Explorer: see the transductive embedding models this lecture generalises, on a small knowledge graph. Each lesson has predict-then-check questions.
notebook · L15 KG foundation models builds relation graphs from a KG and implements an ULTRA-lite model that transfers zero-shot to a KG with new entities and relations.
Readings & lookup guide
lecture notes CS224W course notes (Leni Aniva, Autumn 2024 — in your course folder)
- Ch. 15 — Foundation models for KGs (InGram) (pp. 82–85)
Order: InGram (the lecture's model) → Gao et al. (the theory: double equivariance) → ULTRA (the foundation model).
read first Lee, Chung, Whang — InGram: Inductive Knowledge Graph Embedding via Relation Graphs (ICML 2023)
- Read: §4.1 (relation graph and the \(D^{-2}\) normalisation), §4.2–4.3 (relation- and entity-level aggregation with binned relation-graph bias), §4.4 (decoder and training with dynamic split of facts), dataset construction §5.
theory Gao, Zhou, Ribeiro — Double Equivariance for Inductive Link Prediction for Both New Nodes and New Relation Types (2023)
- Read: the definition of double equivariance and why it is necessary for "doubly inductive" tasks; the ISDEA framework that turns any GNN into a doubly equivariant one. Very much in your mathematical wheelhouse.
foundation model Galkin, Yuan, Mostafa, Tang, Zhu — Towards Foundation Models for Knowledge Graph Reasoning (ULTRA, ICLR 2024)
- Read: §3 (relation graph with 4 interaction types; conditional relation and entity representations), Fig. 2, zero-shot results on 50+ KGs (§5).
- Try: run the pretrained ULTRA checkpoint zero-shot on a small KG you build from your own data.
Homework & deadlines
Colab 5 out Thu 11/12 · due Thu 12/3 · Colab 4 due Tue 12/1
Save both notebooks into the course folder when you open them. Exam: Wed 11/18 (Lectures 1–16, focus 1–13).
Self-check
Why can't R-GCN transfer to a KG with new relation types?
- It can't handle new entities
- It has no attention
- Its relation weights W_r are tied to specific relation IDs
- It uses DistMult
Structure-agnostic relation parameters.
InGram's relation graph connects two relations when …
- they share head or tail entities
- they have similar names
- they appear in the same query
- they are inverses
\(A=E_h^\top D_h^{-2}E_h+E_t^\top D_t^{-2}E_t\).
Double equivariance means the model is equivariant to …
- node permutations only
- edge direction
- time shifts
- permutations of both entity IDs and relation IDs
Necessary for transferring across vocabularies.
Why weight shared entities by \(1/\deg^2\)?
- To make A symmetric
- To down-weight hub entities that co-occur with everything
- To normalise rows to 1
- It's required by GAT
Rare shared entities are more specific evidence of relatedness.
ULTRA's relation graph uses which universal edge types?
- The KG's own relation types
- Entity types
- Head-to-head, head-to-tail, tail-to-head, tail-to-tail
- Symmetric and antisymmetric
These four exist in every KG, so parameters transfer.
Flashcards (click to flip)
History & the bigger picture
- 2013–2019 — transductive KG embeddings (Lecture 10).
- 2020 — GraIL (Teru et al.): inductive link prediction from enclosing subgraphs — first step to new entities. 2021 — NBFNet: path-based, conditional message passing.
- 2023 — InGram, ISDEA/double equivariance: new relations. 2024 — ULTRA: one model, zero-shot on 50+ KGs. Since then, "graph foundation models" became a major research programme.
InGram defines a relation by which entities it connects and how it co-occurs with other relations — not by its name. That is Wittgenstein's "meaning is use" and the distributional hypothesis (Lecture 2), now applied to predicates instead of words. It also echoes structuralism in mathematics: an object is determined up to isomorphism by its relations — exactly the symmetry double equivariance respects.
Classic SNA bridge
| In this lecture | Classic SNA counterpart | What carried over, what changed |
|---|---|---|
| Relation graph: relations linked by shared entities | Role algebras and the "relational composition" tables (Boorman & White 1976; Pattison 1993) | The semigroup of a multirelational network records which compositions of relations coincide. InGram's relation graph records which relations chain and co-occur, the quantitative shadow of the role algebra. |
| Double equivariance (entities and relations) | Structural equivalence applied to relations themselves: "regular" relations | White's programme asked when two relations play the same structural role. Double equivariance is the architectural commitment that only such structural role matters. |
| Transfer to a KG with new entities and relations | Comparative network analysis across cultures with different tie vocabularies (kinship terminologies) | Anthropologists compared kinship systems with different relation names by their algebraic structure (Lévi-Strauss via Weil; White 1963). A KG foundation model does the same by construction. |
| Conditional (source-anchored) message passing | Ego-centred path analysis; reachability from a focal actor | Starting the computation from the query head is an ego-centred analysis; it is why NBFNet-style models can express path patterns that node embeddings cannot. |
| Foundation model trained on many KGs | Meta-analysis across network datasets (e.g. 1,000 real networks in Broido & Clauset 2019) | Both learn regularities that hold across networks rather than within one. SNA found scale-free networks are rare; a KG foundation model finds which relation patterns are universal. |
Compute the role-algebra semigroup (compositions of follow, retweet, reply, mention and which coincide) for a small X dataset, and the InGram relation graph for the same data. Check whether relations the semigroup identifies as structurally similar end up close in the learned relation embedding. If yes, you have an interpretable validation of a foundation model's inner representation using a 1976 method.
Go deeper in the SNA course. The twelve-unit course on social network analysis in this repository gives the classic side of this lecture in full, with labs and real-data analyses: Unit 12 · The new frontier: data, platforms & LLM agents (foundation models for knowledge graphs: what transfers between graphs).
Connecting to your research
- Symbolic transfer: relation graphs are a structural ontology learned from data. Comparing learned relation-graph neighbourhoods with hand-written ontologies (Wikidata properties, schema.org) is a neat neuro-symbolic evaluation.
- Cross-platform transfer: a KG from X/Twitter and one from Telegram or Instagram have different relation vocabularies (retweet vs forward vs share). A doubly equivariant model could transfer bot-detection or influence-prediction across platforms — valuable where labelled data exists for only one platform.
Frontier 2025–26: what changed since the slides
Frontiers · the obstacle is heterogeneity · KG embeddings and NBFNet
Words & phrases
| Term | Simple meaning | Persian | In context |
|---|---|---|---|
| equivariantadj. | changes in the same way as the input when the input is transformed (e.g. relabelled) | هموردا | "double equivariance" |
| vocabularyn. | (here) the set of entity and relation names a particular KG uses | واژگان | "KGs with different vocabularies" |
| inductiveadj. | able to handle nodes, edges or relations not seen during training | استقرایی | "inductive over new entities and new relations" |
| relation graphn. | a graph whose nodes are relations, linked when they share entities in some roles | گراف روابط | "ULTRA runs a GNN on the relation graph" |
| labelling trickn. | marking the query node so the GNN computes features relative to it | ترفند برچسبگذاری | "NBFNet uses the labelling trick" |
| pre-trainingn. | training on broad data first, so the model can be reused on new tasks | پیشآموزش | "pre-training on three KGs" |
Go deeper
- Next: Lecture 16 — LLMs + GNNs: combining language understanding with relational structure.
- Path-based reasoning: Zhu et al. (NeurIPS 2021), NBFNet — generalised Bellman-Ford on graphs; the engine inside ULTRA.
- Open question: double equivariance throws away relation names. When names carry crucial semantics (e.g. "treats" vs "causes"), how should a foundation model combine structural and textual identity? (Lecture 16 is one answer.)