Course / Act II · The two worlds Lecture 04

Graphs, relations, and structures: the bridge.

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

~45 min read Lecture 02 recommended first 9 sections 1 interactive lab Updated 2026-11-16

Put a molecule, a scene graph, and a social network side by side: atoms, objects, people. The similarity is more useful than the difference. In each case the data is entities plus relations, and the question is what a node’s neighbourhood implies about the node. A graph makes it precise, one object both a symbolic reasoner and a neural network can consume.

00 / The hookThree graphs, one question.

A molecule is atoms joined by bonds. The question is whether an atom environment makes the molecule reactive or toxic, and a chemist answers by reading the neighbourhood: a carbon double-bonded to oxygen, an aromatic ring, a charged group.

A scene graph is objects joined by relations: on(cup, table), left_of(cup, person), holding(person, cup). The question is what the robot can do next: a cup on a table is graspable; a cup held by a person is not.

A social network is accounts joined by follows, mentions, and payments. The question is whether an account is fraudulent, and the relevant neighbourhood may be two or three hops away — noisy, incomplete, and adversarial.

Three vocabularies, one shape: entities, relations, features, and a prediction that depends on a pattern. The symbolic side writes the relation as a predicate and the pattern as a query; the neural side writes the entity as a vector and the pattern as an aggregation.

Table 0.1 · Three graphs, one question. The symbolic and neural columns are two views of the same structure.
DomainNodesEdgesQuestionSymbolic viewNeural view
MoleculeAtomsBonds, bond orderProperty of an atom environmentPredicates, graph patternsAtom features, bond messages
Scene graphObjectsSpatial and functional relationsWhat is graspable or trueRelations, rules, queriesObject and relation embeddings
Social networkAccountsFollows, mentions, paymentsLabel of an account or a linkRules, reachability, communitiesNode embeddings, aggregation
Three domains drawn as graphs: a molecule, a scene graph, and a social network Three panels. The molecule has atoms as circles and bonds as lines. The scene graph has object nodes and labelled relation edges. The social network has account nodes and directed follow edges. A line under the panels says “one question: what does a node’s neighbourhood imply?” MOLECULE O C C atoms · bonds · local environment SCENE GRAPH cup table person bowl plate shelf on left_of holding near objects · relations · affordances SOCIAL NETWORK accounts · follows · multi-hop structure one question: what does a node’s neighbourhood imply about the node?
Fig. 0.1 Three domains, one abstraction. The drawings are schematics. A graph keeps entities and relations and throws away geometry, order, and time unless they are encoded as features.
Definition · the object we will use

A graph is a pair G = (V, E) with V a finite node set and E ⊆ V × V. Node features are vectors; edge features carry a type or weight. A knowledge graph has labelled triples (head, relation, tail) as edges; a scene graph has objects as nodes and spatial or functional relations as edges.

A graph is not a picture of data. It is a commitment about what can influence what.

That is why the graph is a bridge: both sides consume the same edges. But shared syntax is not shared meaning, and the rest of this lecture is about where the semantics diverge.

Caveat · the abstraction has a cost

A simple graph loses edge order, time, multiplicity, hyperedges, and the “no edge” vs “unknown edge” distinction. Encoding is a modeling decision, and can be wrong.

01 / Why graphsRelations without an order.

Relations are edges

A binary relation R ⊆ V × V is an adjacency matrix: Aij = 1 iff (i,j) ∈ R. The symbolic atom R(a,b) and the neural edge a → b are two notations for the same constraint. This is the simplest bridge.

Higher arity hurts. A ternary relation between(a,b,c) is not an edge: a hypergraph lets an edge contain many nodes, and reification turns the instance into a node with subject, predicate, and object edges. RDF uses reification, so every triple is a fact. The cost is extra nodes; the benefit is one structure.

The permutation problem

There is no first node. Any numbering is an artifact of how we wrote the graph down. A graph-level function must be invariant to relabeling; a node-level function must be equivariant. For any permutation matrix P:

f(P A P⊤, P X) = f(A, X)    (invariance)     f(P A P⊤, P X) = P f(A, X)    (equivariance)
(1.1)

A multilayer perceptron on a flattened adjacency vector is not invariant: permute the nodes and the input changes. Augmentation or a canonical order can repair it, but both are expensive. A permutation-invariant aggregation computes a function of a set of neighbour vectors, so one shared local function works for five nodes or five million.

The same graph under two node numberings Two drawings of a five-node graph. The left drawing labels the nodes 1 to 5 in one order; the right drawing labels the same nodes in a different order. A graph-level function must return the same value for both; a node-level function must permute its outputs. 12345 numbering A relabel 35124 numbering B · same graph
Fig. 1.1 Two numberings of one graph. A graph-level function must return the same value for both; a node-level function must return the node vectors permuted. The symmetry is the inductive bias that makes a graph model a graph model.

The matrix view

The degree is di = Σj Aij, the degree matrix D is diagonal, and the Laplacian is L = D − A; its normalized form is Lsym = I − D−1/2 A D−1/2. It is positive semidefinite, and its quadratic form measures how much a signal changes across edges:

x⊤ L x = ½ Σi,j Aij (xi − xj)2 ≥ 0
(1.2)

A constant signal scores zero; an alternating one scores high. The eigenvectors of L are the graph’s frequencies, and the smallest non-zero eigenvalues are the smoothest variations. That is the spectral view, and it explains why local averaging is a sensible prior; the graph neural network of §2 is a localized first-order approximation. Typed graphs use one adjacency matrix Ar per relation.

Worked example · a path of three nodes

For 1—2—3, A = [[0,1,0],[1,0,1],[0,1,0]], D = diag(1,2,1), and L = [[1,−1,0],[−1,2,−1],[0,−1,1]]. Take x = (1,0,0). Then Lx = (1,−1,0) and x⊤Lx = 1. The edge differences are (1−0)2 = 1 and (0−0)2 = 0; half their sum is 1. The algebra and the intuition agree.

Queries on graphs

A pattern is a small graph P. A homomorphism from P to G maps every pattern edge to an edge of G; a subgraph isomorphism is an injective homomorphism. A conjunctive query is a pattern with variables, so evaluating it is graph matching — and a constraint satisfaction problem, with a variable per pattern node and a binary constraint per edge.

Subgraph isomorphism and Boolean conjunctive query evaluation are NP-complete in combined complexity; acyclic queries, bounded treewidth, and fixed templates are tractable. A symbolic engine answers exactly at a cost that can be exponential; a neural model approximates without a guarantee.

A short history

Euler’s 1736 Königsberg argument was about connections, not distances; chemists treated molecules as graphs long before computer science did.

1736

Euler, the Königsberg bridges

A problem about connectivity, not geometry. The graph becomes an object of study.

1968–80s

Semantic networks, frames, description logics

Memory as concepts and labelled links; structured knowledge with inheritance and roles. Relations become a formal language.

2009

Scarselli et al., graph neural networks

A fixed-point formulation of message passing. The neural side gets a graph-native architecture.

2013

TransE

Knowledge-graph embeddings as translations. Link prediction becomes a vector-space problem.

2016–17

GCN, MPNN, GraphSAGE, GAT

The modern message-passing toolbox: spectral approximations, edge messages, sampling, attention.

2018–21

Expressivity, smoothing, squashing

GIN and the 1-WL bound; depth pathologies; the limits of local aggregation become a research program.

Caveat · what the matrix view hides

The adjacency matrix describes a simple graph, not a relational dataset: no edge labels, timestamps, uncertainty, or distinction between a missing edge and a false one. Treat it as an interface, not as the world.

02 / Message passingA local, differentiable query engine.

The central neural operation is message passing. Each node keeps a vector; at each layer it receives a message from every neighbour, aggregates them, and updates. Stack K layers and a node has seen its K-hop neighbourhood. Local, parameter-shared, differentiable: those three properties are the whole story of its power and its limits.

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

The message function M and the update U are shared across nodes, usually small MLPs. The aggregation and a graph-level readout must be permutation-invariant, because N(v) is a set. Sum, mean, max, and masked attention qualify; a concatenation over an arbitrary list does not.

The GCN of Kipf and Welling is the canonical local averaging layer. With a self-loop added to every node, Ã = A + I, and D̃ the degree matrix of Ã:

H(t) = σ( D̃−1/2 Ã D̃−1/2 H(t−1) W(t) )
(2.2)

The symmetric normalization stops high-degree nodes from dominating, and the self-loop keeps the node’s own state. Kipf and Welling derive it as a first-order approximation of a localized spectral filter (arXiv:1609.02907); that is a motivation, not a theorem of optimality.

GraphSAGE (Hamilton, Ying, and Leskovec, arXiv:1706.02216) is inductive: sample a fixed number of neighbours, aggregate, concatenate with the node’s vector, and apply a linear map. Sampling makes cost independent of degree but adds variance. The graph attention network (Veličković et al., arXiv:1710.10903) learns an edge weight with a masked softmax; attention is not global, and a high weight is not causation.

GIN (Xu et al., arXiv:1810.00826) is the expressivity benchmark: a sum aggregator followed by an MLP. Mean and max are not injective on multisets — mean{1,1,2} = mean{1,2,2} — while sums differ, so a sum plus an expressive MLP distinguishes any two multisets of a countable feature space. That is why GIN reaches the 1-WL ceiling.

Table 2.1 · Four message-passing layers. The expressive ceiling refers to anonymous graphs; positional features can change it.
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 parameters and memory1-WL
GINSum + MLPInjective multiset aggregationMore parameters; no normalization1-WL, attained

Depth, receptive fields, and over-smoothing

After K layers a node depends on its K-hop neighbourhood; on a path of length n, an endpoint needs n−1 layers. Depth makes a local operation global, but it is not free. On a three-node path with features (1,2,3) and mean aggregation including the node itself, one round gives (1.5,2,2.5), two give (1.75,2,2.25), and the values converge to (2,2,2); variance falls from 2/3 to 1/6 to 1/24. This is over-smoothing: averaging destroys the differences between nodes.

Table 2.2 · Over-smoothing on a three-node path with mean aggregation. Variance is population variance across the three values.
RoundNode valuesVarianceWhat is left
0(1, 2, 3)0.667Three distinct values
1(1.5, 2, 2.5)0.167Contrast reduced by 4×
2(1.75, 2, 2.25)0.042Contrast reduced by 16×

Over-smoothing is a consequence of stacking averaging operators, not a bug. Oono and Suzuki show that deep graph convolutional networks can lose expressive power exponentially with depth (arXiv:1905.10947); Li, Han, and Wu describe the mechanism directly (“Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning”, AAAI 2018). Residuals slow the collapse but do not remove the tension: the depth you need for a long-range dependency is the depth that smooths away the signal.

The dual pathology is over-squashing. The receptive field grows exponentially with depth, but each message is a fixed-size vector: distant information 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. Alon and Yahav show this bottleneck can dominate long-range tasks (arXiv:2006.05205). Virtual nodes, rewiring, and wider messages mitigate it at a cost.

The 1-WL ceiling

The expressivity of message passing has a precise ceiling, inherited from a 1968 isomorphism test: Weisfeiler–Leman color refinement. Start each node with a color from its features; each round, give it a new color hashed from its old color and its neighbours’ color multiset. Repeat until the partition stops changing. Two graphs are 1-WL-equivalent if they have the same color multiset at every round.

cv(0) = feature(v)     cv(t+1) = HASH( cv(t), {{ cu(t) : u ∈ N(v) }} )
(2.3)

A message-passing layer has the same shape, with vectors instead of colors. If two nodes share a color at round t, they share a neighbour multiset and get the same new color; by induction, 1-WL-equivalent graphs give any MPNN the same representations and readout. No message-passing GNN beats 1-WL at distinguishing graphs (Morris et al., arXiv:1810.02244; Xu et al., arXiv:1810.00826).

Proof sketch · why the ceiling holds

At round 0 the color multisets agree. If they agree at round t, a layer maps a color and a neighbour multiset to a vector; the inputs agree, so the outputs agree as multisets. Induction covers every layer, and an invariant readout gives the same answer. The argument assumes anonymous nodes, shared weights, and no unique identifiers.

The smallest counterexample is a pair of 2-regular graphs on six nodes: a six-cycle C6 and two disjoint triangles K3 ∪ K3. Every node has degree two, so every node has the same color after every round. The graphs are 1-WL-equivalent but not isomorphic: C6 is connected with girth six; K3 ∪ K3 has two components and two triangles.

A six-cycle and two disjoint triangles: 1-WL-equivalent but not isomorphic Left: a hexagon of six nodes, all degree two. Right: two triangles, each of three nodes, all degree two. Every node in both graphs has the same degree, so color refinement assigns one color to every node in both graphs. The graphs differ in connected components and triangle count. C6 · one component · girth 6 K3 ∪ K3 · two components · girth 3
Fig. 2.1 Two 2-regular graphs on six nodes. Color refinement cannot distinguish them: every node has the same color at every round. Component count, triangle count, and girth are global properties a local layer cannot compute.
Table 2.3 · What 1-WL sees and what it misses. The first two invariants agree; the last four do not.
InvariantC6K3 ∪ K31-WL distinguishes?
Degree sequence2,2,2,2,2,22,2,2,2,2,2No
Color multiset{A×6}{A×6}No
Components12No
Triangles02No
Girth63No
The small puzzle

Cover one node of C6 and one node of K3 ∪ K3. Can you tell which graph you are looking at from the remaining five? A local view cannot. The missing node is exactly the global information message passing does not carry; the lab runs the comparison.

The ceiling can be raised: k-WL colours k-tuples and is strictly stronger for k ≥ 2, and positional encodings can break the symmetry. Every fix has a cost — higher-order methods scale poorly, and encodings can be unstable. A model below the ceiling can still be right; the ceiling is about representation, not learning.

03 / Graph representationsFrom walks to rotations.

Message passing produces a node vector from a local neighbourhood. Another tradition looks at the whole graph: random walks, spectral decomposition, or a knowledge graph’s triples. Both are called “graph embeddings”, but they answer different questions.

A node embedding maps v ↦ zv ∈ Rd so proximity becomes similarity. DeepWalk (Perozzi, Al-Rfou, and Skiena, arXiv:1403.6652) generates walks and trains Skip-gram to predict a node from its context. node2vec (Grover and Leskovec, arXiv:1607.00653) biases the walks with p and q: small q explores further, large q stays near the start. Both are transductive; GraphSAGE is the inductive alternative.

A spectral embedding uses the Laplacian eigenvectors: the smallest non-zero ones give a smooth layout. Laplacian eigenmaps minimize Σij Aij ||zi − zj||2 subject to orthonormality, but eigenvectors are defined up to sign and rotation, dense eigendecomposition costs O(n3), and the result is transductive.

A knowledge-graph embedding assigns vectors to entities and relations so that a score fr(h,t) is high for true triples. Link prediction is the test: given (h,r,?), rank the candidate tails. TransE (Bordes et al., NeurIPS 2013) treats a relation as a translation:

fr(h, t) = − ‖ h + r − t ‖     so the ideal is   h + r ≈ t
(3.1)

In two dimensions, h = (1,0), r = (−1,1), t = (0,1) gives h + r = t and score zero; t = (1,1) gives −1. A symmetric relation needs h + r = t and t + r = h, so r = 0 and h = t: symmetry only by collapsing entities. A one-to-many relation needs one h + r to equal several tails, which is impossible. This is a property of the scoring function, not a training issue.

ComplEx (Trouillon et al., arXiv:1606.06357) moves to complex numbers and a bilinear score, so symmetric and antisymmetric relations can coexist without collapsing entities. RotatE (Sun et al., arXiv:1902.10197) treats a relation as a rotation:

t = h ∘ r,   |ri| = 1,     fr(h,t) = − ‖ h ∘ r − t ‖
(3.2)

In one complex dimension, h = 1 and r = i give t = i; r = −1 maps 1 to −1 and back, so it is symmetric. Composition is the product: i · (−1) = −i. RotatE models symmetry, antisymmetry, inversion, and composition in one framework.

Table 3.1 · Five embedding families. “Handles symmetry” means the scoring function can represent it without collapsing entities; it does not mean the model learns it from data.
MethodObjectScoreSymmetryCompositionInductive?
DeepWalkNodeSkip-gram over random walksn/aNo explicitNo
node2vecNodeSkip-gram over biased walksn/aNo explicitNo
TransEEntity + relation−‖h + r − t‖No (r = 0)Yes (r1 + r2)No
ComplExEntity + relationBilinear in complex spaceYesLimitedNo
RotatEEntity + relation−‖h ∘ r − t‖Yes (r = ±1)Yes (rotation product)No

Evaluation is a filtered ranking: score every tail, remove the other true triples, and rank the true tail; the metrics are MRR and Hits@k. Numbers are easy to over-read: a random split can leak a test triple’s inverse into training, and high-degree entities make popularity a strong baseline. Ask “what split, what filters, and what baseline?”

For a whole graph, the embedding is a readout or a graph kernel; the Weisfeiler–Lehman subtree kernel has the same 1-WL limit as a message-passing GNN. An embedding can place two entities close because they appear in similar contexts, not because one entails the other: TransE can score a triple highly that contradicts a rule. Similarity is not reasoning; if a task needs entailment, pair the embedding with a symbolic check.

04 / Logic on graphsQueries, recursion, and the limits of locality.

The symbolic side is a query language with a semantics. The central query is a pattern — does this graph map into the big one? — and the central recursive query is reachability. The first is a CSP, the second closure. Both expose the difference between a local neural computation and a global symbolic one.

A conjunctive query is a pattern P with variables and atoms; evaluating it asks for a homomorphism into G, with a variable per pattern node and a binary constraint per atom. A Boolean query asks whether one assignment satisfies all constraints. The problem is NP-complete in general — 3-colouring is a CSP — but acyclic queries, bounded treewidth, and fixed templates are tractable.

A Datalog program adds recursion. Facts and rules define a logic program; its meaning is the least fixpoint, the smallest set of facts closed under the rules. For the lecture’s graph, with undirected edges written as symmetric facts:

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

The first rule seeds the relation with the edges; the second composes a reachable pair with an edge, growing one hop per round. The least fixpoint is the transitive closure. For ?- reach(1,5), the engine returns a derivation:

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]
(4.2)

The derivation is a proof tree, not an attention map: every step is licensed by a rule and a fact. If the facts are wrong, the proof is still valid relative to them; that is the closed-world assumption. With symmetric edges, the program also derives reach(1,1), because the closure of a symmetric relation is reflexive on non-isolated nodes.

The data complexity of Datalog is PTIME: for a fixed program, evaluation is polynomial in the database size. That is a real guarantee, stronger than anything a GNN offers.

GNNs, 1-WL, and logical expressivity

The neural side has a narrower matching theory. Under anonymous nodes, shared weights, and a permutation-invariant readout, a message-passing GNN expresses the two-variable counting logic C2 — the logic whose distinguishing power is 1-WL. Barceló et al. establish the correspondence (“Logical Expressiveness of Graph Neural Networks”, ICLR 2020); Grohe surveys it (“The Logic of Graph Neural Networks”, LICS 2021).

Reachability is not in that logic. It is not first-order definable on finite graphs, and no fixed-depth message-passing network expresses it: a K-layer GNN detects paths of length at most K, and on unbounded diameter no fixed K suffices. An unbounded-depth MPNN does not escape, because the ceiling applies at every depth.

What the theorem does and does not say

A model with unique identifiers, a distance encoding, or a symbolic transitive-closure bit can distinguish graphs that 1-WL cannot. The theorem says the standard template has a ceiling, not that GNNs are useless. Adding a non-local feature changes the model class — and you owe an argument for why it generalizes.

If a task has an algorithm — dynamic programming, shortest paths, matching — a network whose computation mirrors the algorithm’s steps can learn it with less data. Xu et al. call this algorithmic alignment (“What Can Neural Networks Reason About?”, ICLR 2020). A GNN is aligned with dynamic programming: each layer is a local relaxation. Alignment is a design principle, not a guarantee: it still needs enough layers.

A query can enter a neural system as a feature (a closure, distance, or WL colour), a loss (a penalty for a violation), or a verifier (a check that rejects or repairs a proposal). They are not equivalent: a feature changes what the model sees, a loss what it prefers, and a verifier what it may output.

Table 4.1 · Three ways to put a graph query into a neural system.
CouplingMechanismWhat it buysWhat it costs
Query as featureClosure, distance, centrality, WL colourGlobal information inside a local modelPrecomputation; leakage; distribution shift
Query as lossPenalty for violating a graph propertyEnd-to-end training; soft guidanceNo hard guarantee; fragile weighting
Query as verifierSymbolic check, rejection, repairExact guarantee on the checked propertySearch cost; specification must be right

The bridge in one sentence: a GNN is a bounded, differentiable, feature-valued message-passing engine; a Datalog engine is an unbounded, exact, symbol-valued one. They share the graph, and they do not share the semantics.

05 / Structured predictionThe output is a structure.

Most tasks predict a label, an answer, or an action. A graph-native task often predicts a structure — a scene graph, a molecule, a program, a plan. The output has internal relations, and those relations are part of the answer.

A scene graph represents an image or a 3D scene as objects and relations: nodes carry category, colour, material, and pose; edges carry on, left_of, holding, near. It says what is related to what — exactly what a planner needs. ConceptGraphs (Gu et al., arXiv:2309.16650) builds open-vocabulary 3D scene graphs from multi-view images, then plans over the graph with a language model. A missing edge can be worse than a wrong label.

A molecule is atoms joined by bonds. Property prediction is graph-level regression, and message passing fits because a local chemical environment is a neighbourhood. Generation is harder: the model must produce a valid molecule, not a plausible adjacency matrix. Valence and ring rules are constraints; validity, uniqueness, and novelty are reported together.

A program has several graph views: the abstract syntax tree, the control-flow graph, and the data-flow graph. Each makes a different question natural — syntax, reachability, taint analysis. The syntax is a grammar, a symbolic constraint. A GNN over an AST can learn a pattern; a parser or type checker can guarantee the output is well formed.

A graph generator can be autoregressive, diffusion-based, or grammar-based. Each enforces validity differently: masking invalid actions, repairing after denoising, or constructing only legal structures. Evaluation is hard: exact matching is too strict, graph edit distance is NP-hard, and validity, uniqueness, novelty, and downstream score each have a failure mode.

Likelihood is not validity

A model can assign high probability to a graph that violates a hard constraint: probability is a statement about the training distribution, not the world. If the constraint matters, enforce it — by masking, projection, a grammar, or a verifier — and evaluate the enforcement separately.

06 / The bridgeSame syntax, different semantics.

A graph is a shared data structure, not a shared meaning. The symbolic side reads an edge as a relation and a pattern as a query; the neural side reads an edge as an adjacency and a pattern as an aggregation. The guarantee comes from the symbolic side, and only when the graph and rules are right.

The one idea

A message-passing GNN is a bounded, differentiable, feature-valued query engine. A Datalog or CSP engine is an unbounded, exact, symbol-valued one. They share the graph; they do not share the semantics. The bridge is the engineering discipline of deciding which side supplies the syntax, which side supplies the guarantee, and where the two meet.

Table 6.1 · The bridge as a translation table. The right column names a structural role, not an equivalence.
Symbolic conceptGraph / neural counterpartWhat is preservedWhat is lost
Binary relation R(a,b)Edge a → b with type RThe pair and the typeArity > 2, negation, uncertainty
Rule R(x,y) ← P(x,z), Q(z,y)Two-hop path patternThe compositionVariable binding, recursion, negation
Query ?- R(a,Y)Subgraph pattern / readoutThe patternExactness, completeness, cost bound
Constraint degree(v) ≤ kMask or penaltyThe preferenceThe guarantee (a soft penalty can be violated)
Derivation / proofMessage trace or attention pathA path through the computationLogical validity; attention is not a proof

Three coupling patterns

The first pattern is a shared input: a knowledge graph or scene graph feeds both a GNN and a query engine. If the graph is wrong, both sides are wrong in the same way.

The second is a symbolic feature: compute a closure, distance, WL colour, or centrality and add it to the node features. The GNN stays local, but its inputs carry information from outside the neighbourhood; the risks are cost, leakage, and a feature computed on a different graph.

The third is a proposal-and-check loop: the GNN proposes a path, a set of edges, or a scene graph, and a symbolic engine checks it. The symbolic side supplies the guarantee; the neural side supplies the generalization.

Table 6.2 · Two engines on the same graph. The comparison is about semantics and guarantees, not about which one is “better”.
PropertyMessage-passing GNNDatalog / CSP engine
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
GeneralizationAcross graphs, if the distribution is rightAcross instances of the same program, not across programs

Worked example: reachability, twice

The Datalog program in §4 computes the closure exactly; a three-layer GNN sees three hops — enough for the five-node graph, not for a path of length one hundred. For a path query, the GNN approximates and the engine is exact; for link prediction, the GNN generalizes and the engine cannot. The useful system combines them: closure as a feature, the GNN as a proposal, the engine as a check.

Differentiable is not sound

A differentiable relaxation of a constraint is a soft preference. It can be violated, and a model can satisfy the penalty on average while violating it on the cases that matter. A verifier cannot be talked out of a counterexample. If the product needs a guarantee, it must come from a check, not a loss curve.

Semantic networks, frames, and description logics were graph-based before neural networks were competitive; knowledge graphs made the graph a web-scale artifact; GNNs made it differentiable. Both communities chose the same structure because relations are local, composition is powerful, and order is irrelevant. The bridge is real because the data is shared; it is limited because the semantics is not.

07 / Limits & open problemsWhat the bridge does not fix.

Long range. A K-layer GNN sees K hops; a dependency a hundred hops away needs a hundred layers — which over-smooths — or a global readout, virtual node, rewiring, or symbolic feature. Every option costs memory or structure.

Dynamic graphs. Real graphs change: edges appear and disappear, features drift, new nodes arrive. A temporal GNN adds time; the symbolic side has event logs and temporal logic. Evaluation is harder because a random split can leak the future into the past.

Heterophily. Message passing assumes neighbours are informative about each other. In a heterophilous graph — fraud linked to merchants, a user–product bipartite graph, definitions linked to uses — averaging destroys the signal. Relation-specific weights and signed or directed edges help. The first step is to measure homophily, not assume it.

Systematic generalization. A GNN trained on small graphs often fails on larger ones, even when the rule is the same: it learned a pattern at a scale, not the algorithm. Alignment, recursion, and symbolic features help, but there is no general fix. This is a compositional generalization failure, not specific to graphs.

Expressivity beyond 1-WL. Higher-order GNNs, subgraph GNNs, and positional encodings can distinguish graphs that 1-WL cannot, at a cost in scaling, enumeration, or stability. Whether the extra power buys generalization is open.

The symbolic limits. Graph queries are NP-hard; knowledge graphs are incomplete; the closed-world assumption can be wrong; rules can be mis-specified. A Datalog engine is only as good as its facts. The guarantee is relative to the specification, not the world. Benchmarks are easy to leak: use an out-of-distribution split.

Table 7.1 · Four limits, their symptoms, and the cost of the usual mitigation.
LimitSymptomMitigationCost
Long rangePrediction ignores distant nodesVirtual node, rewiring, global attention, symbolic featureMemory, quadratic cost, or a feature pipeline
Over-smoothingNode vectors collapse as depth growsResiduals, jumping knowledge, normalization, shallow depthLess global view; architecture complexity
HeterophilyAveraging mixes incompatible neighboursRelation-specific weights, signed/directed edgesMore parameters; schema work
Systematic generalizationFails on larger or recombined graphsAlgorithmic alignment, recursion, symbolic featuresDesign effort; dependence on the feature

Graphs make the interface explicit: they tell you what can influence what and give both camps the same object to argue about. They do not erase the semantic gap. A GNN is not a logic, and a logic is not a perception system.

08 / RecapWhat you should be able to do now.

01

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

02

State permutation invariance and equivariance, and explain why a flattened adjacency needs augmentation.

03

Write the MPNN template and name the four choices: message, aggregation, update, readout.

04

Compare GCN, GraphSAGE, GAT, and GIN on aggregation, cost, and expressive ceiling.

05

Explain over-smoothing and over-squashing, and why depth is both necessary and dangerous.

06

State the 1-WL ceiling and use C6 versus K3 ∪ K3 as a counterexample.

07

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

08

Explain why Datalog reachability escapes the local ceiling, and where the guarantee comes from.

Exercises

  1. Relabel and check. Take the five-node graph in the lab. Apply the permutation (1 3)(2 5) to the node order, run one MPNN round, and verify that the outputs are the same vectors in the permuted order.
  2. Hand-run the path. Compute three rounds of mean aggregation on a four-node path with features (0,1,2,3). Compute the variance at each round. How many rounds before the values are within 0.1 of each other?
  3. Build a 1-WL pair. Construct two non-isomorphic 3-regular graphs on six nodes. Run color refinement by hand. Do they have the same colour multiset? What invariant distinguishes them?
  4. Prove the TransE limit. Show that a symmetric relation forces r = 0 and h = t. Then show that a one-to-many relation cannot be represented exactly. Which assumption would you change to fix each failure?
  5. Design a bridge. Take a scene graph and a task planner. Specify what is neural, what is symbolic, where the interface is, and what guarantee the symbolic side provides. Name one failure mode of the interface and one way to detect it.

Check your understanding

Ten questions, with explanations. The score is not the point; the questions you cannot answer are the reading list.

Reading list

Semi-Supervised Classification with Graph Convolutional Networks

Kipf & Welling · ICLR 2017 · the canonical local averaging layer

GCN

Neural Message Passing for Quantum Chemistry

Gilmer et al. · ICML 2017 · the MPNN template

MPNN

Inductive Representation Learning on Large Graphs

Hamilton, Ying & Leskovec · NeurIPS 2017 · GraphSAGE and sampling

Inductive

Graph Attention Networks

Veličković et al. · ICLR 2018 · learned edge weights

Attention

How Powerful are Graph Neural Networks?

Xu et al. · ICLR 2019 · GIN and the 1-WL bound

Expressivity

Weisfeiler and Leman Go Neural

Morris et al. · AAAI 2019 · higher-order GNNs and the WL hierarchy

1-WL
Limits
Depth

node2vec: Scalable Feature Learning for Networks

Grover & Leskovec · KDD 2016 · biased walks and the p/q trade-off

Embeddings

Translating Embeddings for Modeling Multi-relational Data

Bordes et al. · NeurIPS 2013 · TransE, cited by title and venue; no arXiv ID

KG

RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space

Sun et al. · ICLR 2019 · rotations and composition

KG

ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planning

Gu et al. · ICRA 2024 · structured perception for planning

Robotics

The Logic of Graph Neural Networks

Grohe · LICS 2021 · the logical expressivity survey; cited by title and venue

Theory

Logical Expressiveness of Graph Neural Networks

Barceló et al. · ICLR 2020 · GNNs and guarded/graded modal logic; cited by title and venue

Theory
Source note · what is redrawn

All figures are schematic redrawings, not reproductions. The citations identify the systems and the claims; the drawings are ours. The numerical examples (the path, the mean aggregation, the TransE and RotatE vectors) are worked calculations, not benchmark results. Abstract numbers are deliberately absent: this lecture does not report a score it did not compute.