CS224W

Lecture 15 · Thu 11/12 · slides PDF · lecture notes

Towards Foundation Models for Knowledge Graphs

To transfer across knowledge graphs with different entities and different relations, stop learning a vector per relation — derive relation embeddings from how relations interact, with a model that is equivariant to renaming both nodes and relations.

25
sectionstick "got it" as you go
20
figuresredrawn from the slides
interactive figuresplay with the ideas
5
self-check questionsplus flashcards
17′
reading time3,730 words, walkthrough aside

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.

\[ \hat y_q=\arg\max_{c}\ \cos\big(\mathbf h_{\text{label }c},\ \mathbf h_{q}\big)\qquad\qquad \text{token}_{cell}=\phi_{\text{dtype}}(\text{value})+\text{LM}(\text{column of table}) \]

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.

\[ \text{TransE: } \mathbf h+\mathbf r\approx\mathbf t\qquad \text{DistMult: } \textstyle\sum_i h_ir_it_i\qquad \text{ComplEx: } \mathrm{Re}\sum_i h_ir_i\bar t_i\qquad \text{RotatE: } \mathbf h\circ e^{i\boldsymbol\theta_r}\approx\mathbf t \]

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.

\[ \mathbf{W}_r=\sum_{b=1}^{B}a_{rb}\,\mathbf{V}_b \qquad\text{(basis decomposition: } |R|\cdot B \text{ scalars} + B \text{ shared matrices)} \]

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

From shallow to doubly equivariant KG models shallow (TransE…) entities relations new entity ✗new relation ✗ structure only in the loss 1 R-GCN / HGT entity= GNN(G) W_r learnedper relation new entity ✓new relation ✗ structure in model + loss (entities) 2 InGram / ULTRA entity= GNN(G, z_r) z_r =GNN(rel.graph) new entity ✓new relation ✓ double equivariance 3

How to read it (hover a step)

  1. Shallow: entity and relation embeddings are trainable weights; structure appears only in the loss. Usable on one KG only.
  2. 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.
  3. 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.

Characteristics of foundation models. slide 11 ↗
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.

KG vs natural language: heterogeneous vocabulary. slide 21 ↗

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.

Heterogeneous GNNs: structure-aware entities, structure-agnostic relations. slide 40 ↗

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.

InGram pipeline at training and inference time. slide 64 ↗

Building the relation graph

Computing a relation-pair weight β. slide 53 ↗
  • \(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.
\[ A=E_h^\top D_h^{-2}E_h+E_t^\top D_t^{-2}E_t \]

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\).

The resulting relation graph. slide 57 ↗

Relation-level then entity-level message passing

  1. 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.
  2. 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.
  3. 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

symbolmeaningwhat kind of object
\(n,\ m\)number of entities and number of relationswhole 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\), computedvector
\((h,q,?)\)a query: head entity \(h\), query relation \(q\), tail unknownincomplete triple
\(\pi_e,\ \pi_r\)a renaming (permutation) of the entities, and one of the relationspermutations

1Why transductive models cannot transfer

\[ \#\text{parameters}=\underbrace{n\cdot d}_{\text{entity table}}+\underbrace{m\cdot d}_{\text{relation table}} \]

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.

With numbers. A graph with \(n=15{,}000\) entities, \(m=237\) relations, \(d=200\): \(3{,}000{,}000+47{,}400\) parameters, all of them useless on a medical graph with different entities and relations. ULTRA has about \(170{,}000\) parameters, none tied to a name.

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

\[ A_{\text{rel}}=E_h^\top D_h^{-2}E_h+E_t^\top D_t^{-2}E_t \]

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.

With numbers. One entity is the head of one triple with relation \(r_1\) and one with \(r_2\): its row of \(E_h\) is \((1,1)\), its degree 2. Its contribution to \(A_{\text{rel}}\) is \(\tfrac14\begin{pmatrix}1&1\\1&1\end{pmatrix}\): affinity \(0.25\) between \(r_1\) and \(r_2\). An entity heading ten triples, one of each of ten relations, contributes only \(1/100=0.01\) to each pair.

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

\[ \mathbf z_r=\text{GNN}_{\text{rel}}(A_{\text{rel}}),\qquad \mathbf h_v^{(l+1)}=\sigma\Big(\sum_{(u,r):(u,r,v)\in G}\alpha_{u,r,v}\,\mathbf W^{(l)}\big[\mathbf h_u^{(l)}\,\Vert\,\mathbf z_r\big]\Big) \]

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.

With numbers. Entity \(v\) has one incoming triple \((u,r,v)\) with \(\mathbf h_u=(1,2)\), \(\mathbf z_r=(0,1)\), attention weight 1 and \(\mathbf W=\begin{pmatrix}1&0&1&0\\0&1&0&1\end{pmatrix}\): the concatenation \((1,2,0,1)\) maps to \((1,3)\). With a different relation \(\mathbf z_{r'}=(5,0)\) the same neighbour would send \((6,2)\).

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)

\[ \mathbf h_v^{(0)}=\mathbb 1[v=h]\cdot\mathbf z_q,\qquad \text{score}(h,q,t)=\text{MLP}\big(\mathbf h_t^{(L)}\big) \]

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.

With numbers. Chain \(h\xrightarrow{r_1}a\xrightarrow{r_2}t\). Layer 0: only \(h\) is non-zero. Layer 1: \(a\) receives a message shaped by \(r_1\). Layer 2: \(t\) receives a message shaped by \(r_1\) then \(r_2\). An entity 3 hops away is still zero and scores as 'unrelated'.

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

\[ f\big(\pi_e\circ\pi_r\circ G\big)=\pi_e\circ\pi_r\circ f(G)\qquad\text{for all permutations } \pi_e \text{ of entities and } \pi_r \text{ of relations} \]

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.

With numbers. Two triples: (Ali, teaches, Sara), (Sara, studies, Maths). Rename teaches→R7, studies→R2 and the entities to E1, E2, E3. A doubly equivariant model that predicted (Ali, teaches, Reza) with score 0.8 in the first naming gives 0.8 to the correspondingly renamed triple.

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.

from Relation graph construction: a worked example

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.

  1. Foundation models everywhere
  2. Towards graph and KG foundation models
  3. KG representation, examples, and KGs vs natural language
  4. Transductive link prediction: shallow KG embeddings and their limits
  5. Same relations, new entities: heterogeneous GNNs and R-GCN
  6. R-GCN for link prediction, and what it still cannot do
  7. New entities and new relations: double equivariance
  8. InGram overview and the relation graph definition
  9. Relation graph construction: a worked example
  10. Relation-level message passing: attention with relation-graph weights
  11. Entity-level message passing
  12. Link-prediction head, InGram summary
  13. Experiments and summary of the lecture

Foundation models everywhere slides 4-10 ↗

Slides 4–10: the foundation-model pattern across fields. 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:

  1. Pretraining on large datasets with self-supervised or unsupervised learning.
  2. Scalability: large architectures with billions or trillions of parameters.
  3. Adaptability: after pretraining, fine-tuned or adapted to many downstream tasks with little task-specific data.
  4. 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 ↗

Slides 11–14: what makes a foundation model, and what a KG foundation model must do. 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 ↗

Slides 16–22: why a KG is harder than text for a foundation model: two kinds of vocabulary and a graph instead of a sequence. 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.

Lecture notes figure, page 83
Notes Figure 15.1: two knowledge graphs with the same relations (Search, Click, Guide) but different users, items and queries. notes p.83 ↗

Transductive link prediction: shallow KG embeddings and their limits slides 23,25-30 ↗

Slides 23–30: the recipe for a KG foundation model and the two failures of shallow embeddings it must fix. slides 23-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:

ModelScoreEmbeddingSym.Antisym.Inv.Compos.1-to-N
TransE\(-\lVert \mathbf{h}+\mathbf{r}-\mathbf{t}\rVert\)\(\mathbb{R}^k\)noyesyesyesno
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}\)yesyesyesyesyes
DistMult\(\langle \mathbf{h},\mathbf{r},\mathbf{t}\rangle\)\(\mathbb{R}^k\)yesnononoyes
ComplEx\(\mathrm{Re}\langle \mathbf{h},\mathbf{r},\bar{\mathbf{t}}\rangle\)\(\mathbb{C}^k\)yesyesyesnoyes
RotatE\(-\lVert \mathbf{h}\circ\mathbf{r}-\mathbf{t}\rVert\)\(\mathbb{C}^k\)yesyesyesyesno

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 ↗

Slides 32–38, R-GCN recap: a heterogeneous GNN handles new entities with the same relations. 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 ↗

Slides 39–40: R-GCN link prediction scores with relation-specific weights, so it cannot transfer to KGs with different relation types. 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 ↗

Slides 42–48: train on the authors KG, test on a movie KG with different entities and relations; the model must be equivariant in both. slides 42-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 ↗

Slides 49–51: InGram at training and at inference on a new KG; only the GNN weights are reused, the relation graph is rebuilt. slides 49-51 ↗

Slide 49 shows the InGram pipeline (figure from the authors' slides). Training time, left to right:

  1. Training graph: a KG with relations \(r_1, \dots, r_5\).
  2. Build the relation graph of the training graph: one node per relation (r1–r5), edges between related relations.
  3. Relation-level aggregation: a GNN over the relation graph computes relation embeddings.
  4. Entity-level aggregation: a GNN over the original KG computes entity embeddings, using the relation embeddings.
  5. 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).

Lecture notes figure, page 84
Notes Figure 15.2: the working principle of InGram. Training and inference graphs have different relations; the relation-level and entity-level aggregation weights are shared. notes p.84 ↗

Relation graph construction: a worked example slides 52-57 ↗

Slides 52–56: computing the relation-pair weights β on the movie KG; the slide's numbers. slides 52-56 ↗
Slide 57: the resulting weighted relation graph of the movie KG. slide 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 ↗

Slides 58–63: relation-level message passing is graph attention over the relation graph with β added to the attention logits. 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 ↗

Slides 64–65: entity-level message passing uses the relation embeddings produced by the relation graph. 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 ↗

Slides 66–69: the link-prediction head and loss; InGram uses the KG structure for entities and for relations alike. 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 ↗

Slides 70–72: InGram leads on transductive benchmarks and widens the gap exactly where test KGs have new entities and new relations. 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.

\[ A_{\text{rel}}=E_h^\top D_h^{-2}E_h+E_t^\top D_t^{-2}E_t,\qquad \mathbf z_r=\text{GNN}_{\text{rel}}(A_{\text{rel}}),\qquad \mathbf h_v=\text{GNN}_{\text{ent}}(G,\{\mathbf z_r\}) \]

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).

  1. Relations sharing a head: (actedIn, costarred) via Emma; (actedIn, bornIn) via Olivia; (directed, directed) via Yorgos — no cross-relation pair.
  2. 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\).
  3. Add the tail part similarly (e.g. films as tails of actedIn and directed link those two relations).
  4. 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
Edges of \(G_{\mathcal R}\) are defined only from which entities appear in which roles; renaming changes labels, not roles.
Hint 2
Equivariance of GNNs (Lecture 3) on \(G_{\mathcal R}\) does the rest. For the table, swap the IDs of parent_of and sibling_of.
Solution
Triple \((h,r,t)\) becomes \((h,\pi(r),t)\). An entity in role \(\rho\) of an \(r\)-triple and role \(\rho'\) of an \(r'\)-triple is in the same roles of \(\pi(r)\)- and \(\pi(r')\)-triples, so \(r\xrightarrow{\kappa}r'\) iff \(\pi(r)\xrightarrow{\kappa}\pi(r')\). A GNN over \(G_{\mathcal R}\) is equivariant to node relabelling, so the representation of \(\pi(r)\) in the renamed graph equals that of \(r\) in the original, and query \((h,\pi(r),?)\) is answered like \((h,r,?)\). An ID table keeps vector \(E[\text{id}]\) attached to the integer: after swapping IDs, the query "parent_of" reads the vector trained for "sibling_of" and answers the wrong relation (the notebook's MRR drop to about 0.1). \(\square\)

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.

precise statement

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.

second viewpoint

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.

where it breaks

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.

Four relation-graph edge types, not oneTwo relations can share a head (h–h), share a tail (t–t), or chain (tail of one is head of the other, both directions). Keep them as four typed edges (the figure above merges the two chain directions for display); ULTRA's relation-level GNN uses all four.
Zero-shot transfer is a test of the relation graphEvaluate on a KG whose relation names never appeared in training. If performance collapses, the model is memorising relation identities somewhere (a relation embedding table left in by mistake is the usual culprit).
Entity-level message passing is conditionalBoth InGram and ULTRA run the entity GNN conditioned on the query (NBFNet-style, starting from the head entity). Conditioning on the source is what makes link prediction expressive beyond what node embeddings allow.
Names still carry meaningDouble equivariance throws away relation names. When "treats" vs "causes" matters, combine the structural relation embedding with a text embedding of the name (Lecture 16); report which one the model relies on.

Readings & lookup guide

lecture notes CS224W course notes (Leni Aniva, Autumn 2024 — in your course folder)

Concise written version of the lectures; the walkthrough above cites it page by page.

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)

arXiv:2305.19987 · ~2 h · the authors' slides (bdi-lab.kaist.ac.kr) are what the lecture borrows
  • 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)

arXiv:2302.01313 · ~2 h · math-heavy
  • 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)

arXiv:2310.04562 · ~2 h · code + pretrained checkpoints on GitHub (DeepGraphLearning/ULTRA)
  • 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?

  1. It can't handle new entities
  2. It has no attention
  3. Its relation weights W_r are tied to specific relation IDs
  4. It uses DistMult

Structure-agnostic relation parameters.

InGram's relation graph connects two relations when …

  1. they share head or tail entities
  2. they have similar names
  3. they appear in the same query
  4. 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 …

  1. node permutations only
  2. edge direction
  3. time shifts
  4. permutations of both entity IDs and relation IDs

Necessary for transferring across vocabularies.

Why weight shared entities by \(1/\deg^2\)?

  1. To make A symmetric
  2. To down-weight hub entities that co-occur with everything
  3. To normalise rows to 1
  4. It's required by GAT

Rare shared entities are more specific evidence of relatedness.

ULTRA's relation graph uses which universal edge types?

  1. The KG's own relation types
  2. Entity types
  3. Head-to-head, head-to-tail, tail-to-head, tail-to-tail
  4. Symmetric and antisymmetric

These four exist in every KG, so parameters transfer.

Flashcards (click to flip)

The inductiveness ladder
Shallow (none) → R-GCN (new entities) → InGram/ULTRA (new entities + relations).
Relation graph adjacency
\(E_h^\top D_h^{-2}E_h+E_t^\top D_t^{-2}E_t\)
InGram pipeline
Relation graph → relation-level attention → entity-level aggregation → DistMult-like head.
Relation attention bias
\(\alpha_{vu}=\text{softmax}(e_{vu}+\beta_{vu})\), β from relation-graph weight bins.
Double equivariance
\(f(\pi\circ\sigma\cdot G)=\pi\circ\sigma\cdot f(G)\) for entity perm π and relation perm σ.
Foundation model traits
Pretrained at scale; zero/few-shot; generalise to unseen entities.

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.
Philosophy · meaning by use, again

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 lectureClassic SNA counterpartWhat carried over, what changed
Relation graph: relations linked by shared entitiesRole 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" relationsWhite'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 relationsComparative 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 passingEgo-centred path analysis; reachability from a focal actorStarting 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 KGsMeta-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.
Bridge idea

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

Neuro-symbolic and SNA
  • 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

ICML 2026 workshopFair evaluation of graph foundation models — ULTRA worked early because KG link prediction has a natural feature-free invariance: the graph of how relations interact. Node classification has no such invariance, which is why it remained the hard case until synthetic priors (GraphPFN). The double-equivariance idea of this lecture is the cleanest example of "generality comes from an invariance".sources: arXiv:2509.21489 · arXiv:2310.04562 · arXiv:2606.24509
NeurIPS 2025 oralRAG4GFM: graph retrieval to fill knowledge gaps in graph foundation models — Retrieval-augmented generation applied to graph foundation models themselves: when the pretrained model lacks knowledge of a new graph, retrieve structure instead of retraining. Lecture 16's GraphRAG meets this lecture's foundation models.
NeurIPS 2025 spotlightOn transferring transferability: a theory for size generalisation — Graphon-style limits (Ruiz et al. 2020; Lovász) give transfer across sizes a theory; this spotlight extends it. The question "what does one fixed network compute on graphs of every size" is also the uniform-expressivity question of the logic line.sources: arXiv:2505.23599
ICLR 2026KG foundation models for inductive link prediction — One of four threads in the 47-paper KG cluster. The others: when graphs help RAG, agentic KG exploration trained with RL, and KG construction from text by LLMs.
AtlasThe open question of the foundation-model cluster — "Is there a graph vocabulary as universal as tokens are for text, or is transfer fundamentally limited by structural heterogeneity?" The relation graph is a partial answer for KGs; nothing comparable exists yet for social networks with non-textual features and temporal dynamics.
Open question to carryDouble equivariance discards relation names. When names carry crucial semantics, how should a foundation model combine structural and textual identity, and can the structural part transfer bot or influence prediction across platforms whose relation vocabularies differ (retweet vs forward vs share)?
Frontiers · the obstacle is heterogeneity · KG embeddings and NBFNet

Words & phrases

TermSimple meaningPersianIn 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.)