Lecture 04 · The two worlds

Graphs, relations, and structures.

A molecule, a scene graph, and a social network ask the same question: what does a node’s neighbourhood imply? A graph is the data structure both camps can share — and the place where their semantics diverge.

9 sections 2 engines 1 interactive lab Self-paced
00 · Learning objectivesLecture 04 · Graphs and structures

By the end of this lecture

Four things you can do.

01

Explain why graphs are shared

A relation without an order: permutation invariance, variable size, and the matrix view.

02

Trace message passing

The MPNN template, over-smoothing, over-squashing, and the 1-WL ceiling.

03

Compare embeddings

Random walks, spectral coordinates, and TransE / ComplEx / RotatE on knowledge graphs.

04

Connect queries and GNNs

Datalog recursion, logical expressivity, and where the guarantee comes from.

S/V · Lecture 04
00 · The hookLecture 04 · Graphs and structures

Three graphs, one question

What does a neighbourhood imply?

Molecule

Atoms and bonds

An atom’s local environment decides its reactivity. Nodes are atoms; edges are bonds; the question is a property of a local pattern.

C–O · ring · charge

Scene graph

Objects and relations

A cup on a table is graspable; a cup held by a person is not. Nodes are objects; edges are spatial and functional relations.

on(cup, table) · holding(p, cup)

Social network

Accounts and interactions

A fraud label depends on accounts two or three hops away. Nodes are accounts; edges are follows, mentions, and payments.

2-hop · 3-hop · noisy

The symbolic side writes the pattern as a query. The neural side writes it as an aggregation. The graph is the object they share — and the reason this lecture can be a bridge rather than a comparison.

S/V · Lecture 04
00 · The hookLecture 04 · Graphs and structures

The shared object

A relation without an order.

A graph is G = (V, E): a finite node set and a set of edges. Node features are vectors; edge features carry a type or weight. A knowledge graph labels each edge with a relation; a scene graph labels each edge with a spatial or functional relation.

Aij = 1  iff  (i,j) ∈ E

R(a,b)  ≡  a → b

The symbolic atom and the neural edge are two notations for the same constraint. The graph is the shared syntax; the meaning is still supplied by each side.

AB CDE [1,0][0,1][1,1] [0,1][1,0] A = adjacency · X = features · no canonical order
The same five nodes the lab uses. The numbers under each node are its feature vector.
S/V · Lecture 04
01 · Why graphsLecture 04 · Graphs and structures
01 / 08

Relations without an order.

Permutation invariance, the Laplacian, and the pattern query. Why the graph is the right data structure before it is a neural architecture.

S/V · Lecture 04
01 · Why graphsLecture 04 · Graphs and structures

The symmetry

No first node.

A graph has no canonical node order. A graph-level function must be invariant to relabeling; a node-level function must be equivariant. For any permutation matrix P:

f(PAP⊤, PX) = f(A, X)

f(PAP⊤, PX) = P f(A, X)

Flattening fails. An MLP on a flattened adjacency changes its input when the nodes are renumbered. Augmentation or a canonical order can repair it, but both are expensive. A local aggregation over a set of neighbours is invariant by construction, and the same function works for any graph size.

12345 numbering A relabel 35124 numbering B · same graph
Two numberings of one graph. A graph-level answer must be identical; node-level answers must be permuted.
S/V · Lecture 04
01 · Why graphsLecture 04 · Graphs and structures

The matrix view

A graph is a matrix with a spectrum.

L = D − A

Lsym = I − D−1/2 A D−1/2

x⊤Lx = ½ Σij Aij(xi − xj)2 ≥ 0

A constant signal scores zero: it is perfectly smooth. An alternating signal scores high: it is rough. The eigenvectors of L are the graph’s frequencies; the smallest non-zero eigenvalues are the smoothest variations. This is why local averaging is a sensible prior — and why a stack of averaging layers eventually erases the signal.

Worked example · path 1—2—3

A = [[0,1,0],[1,0,1],[0,1,0]]

D = diag(1,2,1)

L = [[1,−1,0],[−1,2,−1],[0,−1,1]]

x = (1,0,0)

Lx = (1,−1,0)

x⊤Lx = 1

The edge differences are 1 and 0; half their sum is 1. The algebra and the intuition agree.

S/V · Lecture 04
01 · Why graphsLecture 04 · Graphs and structures

Queries are patterns

Find this shape in the graph.

abc pattern P h ABCDE host G
A homomorphism maps every pattern edge to an edge of the host. Here a→A, b→B, c→D.

A conjunctive query is a pattern with variables. Evaluating it asks for a homomorphism into the data graph: each pattern node is a variable, each pattern edge is a binary constraint. A subgraph isomorphism is an injective homomorphism.

The cost is real. Subgraph isomorphism is NP-complete, and Boolean conjunctive query evaluation is NP-complete in combined complexity. Acyclic queries, bounded treewidth, and fixed templates are tractable. A symbolic engine is exact and can be slow; a neural model is fast and has no guarantee.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures
02 / 08

A local, differentiable query engine.

The MPNN template, four aggregators, and the two pathologies that come with depth: smoothing and squashing.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

The template

Every layer is a local update.

mv(t) = AGGu∈N(v) M(hv(t−1), hu(t−1), euv)

hv(t) = U(hv(t−1), mv(t))

y = R({hv(K) : v ∈ V})

M and U are shared across nodes; AGG and R must be permutation-invariant, because a neighbourhood is a set. Stack K layers and each node has seen its K-hop neighbourhood.

u1u2u3 hu1 hu2 hu3 AGG sum / mean / max U update h(t)v messages from N(v) the same M and U at every node
The template. The only non-negotiable constraint is that AGG does not depend on the order of the neighbours.
S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

Four choices

Same template, different aggregators.

LayerAggregationWhat it addsCostCeiling
GCNNormalized sum with self-loopsA cheap spectral prior; stable trainingLow1-WL
GraphSAGEMean / LSTM / pooling over sampled neighboursInductive inference on unseen graphsSampling variance1-WL (sum variant attains it)
GATLearned attention weightsEdge importance; multi-head routingExtra parameters1-WL
GINSum + MLPInjective multiset aggregationNo normalization1-WL, attained

The sum is not arbitrary. Mean and max are not injective on multisets: mean{1,1,2} = mean{1,2,2}. A sum plus an expressive MLP can distinguish any two multisets of a countable feature space, which is why GIN reaches the 1-WL ceiling.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

Interactive · one round at a time

Watch a message arrive.

Click a node, or use the letters. The number under each node is its current vector. W = [[1,1],[0,1]]; mean aggregation; residual; ReLU.

A = [1.00, 0.00]

FromhuW hu
mean—[0.00, 0.00]

h′ = ReLU([1.00, 0.00] + [0.00, 0.00]) = [1.00, 0.00]

Round 0. Select a node, then run a round.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

Depth

More layers, less difference.

A K-layer GNN sees K hops. On a path of length n, an endpoint needs n−1 layers to see the other end. But repeated averaging drives the vectors together. This is over-smoothing: the depth that buys a long-range view is the depth that erases the local signal.

RoundValuesVariance
0(1, 2, 3)0.667
1(1.5, 2, 2.5)0.167
2(1.75, 2, 2.25)0.042

Three-node path, mean aggregation with the node included. Each round divides the variance by about four.

t=0t=1t=2 0.6670.1670.042 variance of node values
The same path example, drawn as a decay. The values are population variance across the three nodes.

Oono & Suzuki (arXiv:1905.10947): deep GCNs can lose expressive power exponentially with depth. Residuals slow the collapse; they do not remove the trade-off.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

The other bottleneck

The receptive field grows; the message does not.

fixed width v target many distant nodes bottleneck
A schematic of over-squashing. The receptive field is large, but the message that reaches v has fixed size.

The receptive field grows exponentially with depth, but every message is a fixed-size vector. Information from many distant nodes must pass through a few edges and be compressed into the same width. The representation becomes insensitive to distant inputs — not because they are irrelevant, but because there is no room.

Mitigations: virtual nodes, graph rewiring, multi-hop neighbourhoods, wider messages. Each costs memory, compute, or structural fidelity. Alon & Yahav (arXiv:2006.05205) show the bottleneck can dominate long-range tasks.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

The ceiling

Two graphs, one color.

AAA AAA C6 · 1 component
AAA AAA K3 ∪ K3 · 2 components
InvariantC6K3 ∪ K31-WL sees it?
Degree sequence2,2,2,2,2,22,2,2,2,2,2No
Components12No
Triangles02No
Girth63No

Every node has degree two, so color refinement never splits the class. No anonymous message-passing GNN can tell the graphs apart.

S/V · Lecture 04
02 · Message passingLecture 04 · Graphs and structures

Beyond 1-WL

You can raise the ceiling — at a cost.

Higher order

k-WL / k-GNN

Color tuples instead of nodes. Strictly stronger for k ≥ 2.

cost: O(nk)

Subgraphs

Subgraph GNNs

Run message passing on subgraphs or rooted subgraphs to break symmetry.

cost: enumeration

Positions

Positional encodings

Laplacian eigenvectors, landing probabilities, or unique identifiers.

cost: stability · generalization

The caveat that matters

Expressivity is not learnability. A model can be below the ceiling and still be right for a task; a more expressive model can fail to learn the distinction from finite data. The ceiling tells you what can be represented, not what will be learned.

S/V · Lecture 04
03 · Graph representationsLecture 04 · Graphs and structures
03 / 08

From walks to rotations — and then to queries.

Node and knowledge-graph embeddings, link prediction, and the point where the symbolic side takes over.

S/V · Lecture 04
03 · Graph representationsLecture 04 · Graphs and structures

Random walks

A corpus from the graph.

DeepWalk (Perozzi et al., arXiv:1403.6652) generates random walks, treats each as a sentence, and trains Skip-gram to predict a node from its walk neighbours. node2vec (Grover & Leskovec, arXiv:1607.00653) biases the walk with p and q: a small q explores further (DFS-like), a large q stays near the start (BFS-like).

Both are transductive: a new node needs retraining. GraphSAGE is the inductive alternative — it learns a function from features and neighbourhood, so it can embed an unseen node.

ABC DEFG A → B → D → E → G
A walk is the supervision. The embedding is a by-product of predicting a node from its walk context.
S/V · Lecture 04
03 · Graph representationsLecture 04 · Graphs and structures

Knowledge-graph embeddings

Translations, then rotations.

TransE: h + r ≈ t

With h = (1,0), r = (−1,1), t = (0,1), the score is zero. A symmetric relation requires r = 0 and h = t; a one-to-many relation is impossible. The limit is in the geometry.

ComplEx moves to complex numbers and a bilinear score, so symmetric and antisymmetric relations can coexist. RotatE makes the relation a rotation.

h = 1 r = i · t = i r = −1 · t = −1 |r| = 1 · composition is rotation product
RotatE in one complex dimension. A 90° rotation and a 180° rotation; the 180° relation is symmetric.
ModelScoreSymmetryComposition
TransE−‖h + r − t‖No (r = 0)Yes
ComplExcomplex bilinearYesLimited
RotatE−‖h ∘ r − t‖Yes (r = ±1)Yes
S/V · Lecture 04
03 · Graph representationsLecture 04 · Graphs and structures

Link prediction

A ranking, not a truth.

Given (h, r, ?), score every candidate tail and rank them. The filtered setting removes the other true triples from the list. The summary metrics are MRR and Hits@k.

The number is easy to over-read. A random split can leak a test triple’s inverse into training; high-degree entities make popularity a strong baseline; a filtered ranking can still reward dataset artifacts.

The questions to ask

What split? Random, temporal, or new-entity.

What filters? Are the other true triples removed?

What baseline? Popularity is strong.

What does it mean? Similarity is not entailment. A high score can contradict a rule.

The limit

An embedding compresses proximity. It does not preserve proof. If the task needs entailment, the embedding must be paired with a symbolic check, a rule, or a constraint — the next section’s subject.

S/V · Lecture 04
04 · Logic on graphsLecture 04 · Graphs and structures

Logic on graphs

A proof, not an attention map.

edge(1,2). edge(2,1). edge(1,3). edge(3,1).
edge(2,4). edge(4,2). edge(3,4). edge(4,3).
edge(4,5). edge(5,4).

reach(X,Y) :- edge(X,Y).
reach(X,Y) :- reach(X,Z), edge(Z,Y).

The first rule seeds the relation with the edges; the second composes a reachable pair with an edge. The least fixpoint is the transitive closure. Data complexity is PTIME.

reach(1,5)
├─ reach(1,4)          [rule 2]
│  ├─ reach(1,2)       [rule 2]
│  │  └─ edge(1,2)     [fact]
│  └─ edge(2,4)        [fact]
└─ edge(4,5)           [fact]

Every step is licensed by a rule and a fact. If the facts are wrong, the proof is still valid relative to them — the closed-world assumption.

S/V · Lecture 04
04 · Logic on graphsLecture 04 · Graphs and structures

The expressivity comparison

Local logic vs unbounded recursion.

PropertyMessage-passing GNNDatalog / CSP
RepresentationVectors, learned weightsFacts, rules, substitutions
RecursionBounded by depthUnbounded, to a least fixpoint
ComplexityPolynomial for fixed depthPTIME data complexity (Datalog); NP-hard in general (CSP)
DifferentiableYesNo (unless relaxed)
GuaranteeEmpiricalSound and complete relative to the facts and rules

The logical statement: under anonymous nodes, shared weights, and a permutation-invariant readout, a GNN expresses the two-variable counting logic C2 — the graded modal logic whose distinguishing power is 1-WL. Reachability is not in C2. The theorem is about the architecture class, not a training run.

S/V · Lecture 04
05 · Structured predictionLecture 04 · Graphs and structures

Structured prediction

The output is a graph.

Vision

Scene graph

Objects and relations. The planner queries the graph instead of re-reading pixels. A missing edge can be worse than a wrong label.

ConceptGraphs · arXiv:2309.16650

Chemistry

Molecule

Atoms and bonds. Valence, rings, and stereochemistry are constraints; validity, uniqueness, and novelty must be reported together.

MPNN · arXiv:1704.01212

Programs

AST / CFG

Syntax, control flow, and data flow. A grammar or a type checker supplies the constraint the neural model cannot.

grammar · types

Likelihood is not validity. A generative model can assign high probability to a graph that violates a hard constraint. If the constraint matters, it must be enforced — by masking, projection, a grammar, or a verifier — and evaluated separately.

S/V · Lecture 04
06 · The bridgeLecture 04 · Graphs and structures

The bridge

Same syntax, different semantics.

SymbolicGraph / neuralPreservedLost
Relation R(a,b)Edge a → b, type RThe pair and the typeArity > 2, negation
Rule R(x,y) ← P(x,z), Q(z,y)Two-hop path patternThe compositionBinding, recursion
Query ?- R(a,Y)Subgraph pattern / readoutThe patternExactness, cost bound
Constraint degree ≤ kMask or penaltyThe preferenceThe guarantee
Derivation / proofMessage trace or attentionA pathLogical validity
The one idea

A message-passing GNN is a bounded, differentiable, feature-valued query engine. A Datalog or CSP engine is unbounded, exact, symbol-valued. They share the graph; they do not share the semantics. The bridge is the discipline of choosing which side supplies the guarantee.

S/V · Lecture 04
06 · The bridgeLecture 04 · Graphs and structures

Three couplings

Where the two sides meet.

01 · Shared input

One graph, two engines

A knowledge graph or scene graph feeds a GNN and a query engine. If the graph is wrong, both sides are wrong in the same way.

buys: simplicity · costs: no independent check

02 · Symbolic feature

Closure as an input

Compute a closure, distance, WL colour, or centrality and add it to the node features. The GNN stays local; its inputs do not.

buys: global signal · costs: leakage, drift

03 · Proposal + check

Neural propose, symbolic dispose

The GNN proposes a path, edges, or a scene graph; a symbolic engine checks it and returns a counterexample or a repair.

buys: guarantee · costs: search, specification

The three are not interchangeable. A feature changes what the model can see; a loss changes what it prefers; a verifier changes what it is allowed to output. Choose the coupling that matches the guarantee you actually need.

S/V · Lecture 04
07 · LimitsLecture 04 · Graphs and structures

Limits and open problems

What the bridge does not fix.

LimitSymptomMitigationCost
Long rangePrediction ignores distant nodesVirtual node, rewiring, global attention, symbolic featureMemory or structure
Over-smoothingNode vectors collapse with depthResiduals, jumping knowledge, shallow depthLess global view
HeterophilyAveraging mixes incompatible neighboursRelation-specific weights, signed edgesMore parameters
Systematic generalizationFails on larger or recombined graphsAlgorithmic alignment, recursion, symbolic featuresDesign effort

Graphs make the interface explicit; they do not erase the semantic gap. A GNN is not a logic, and a logic is not a perception system. The bridge is useful because it lets you see where each side ends.

S/V · Lecture 04
08 · RecapLecture 04 · Graphs and structures

What you should be able to do

Four moves.

Explain

Why a graph is a relation without an order, and why that makes it a shared structure.

Trace

Message passing, over-smoothing, over-squashing, and the 1-WL ceiling.

Compare

DeepWalk, node2vec, TransE, ComplEx, RotatE — and one limit of each.

Connect

Datalog recursion, logical expressivity, and where the guarantee comes from.

S/V · Lecture 04
08 · RecapLecture 04 · Graphs and structures

Next · hands-on

Run the messages yourself.

Open the lab. Click a node, run three rounds, then run the Datalog query and the 1-WL comparison on the same graph.

Lab 04 · message passing → open the lab

S/V · Lecture 04
Speaker notes