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.
| Domain | Nodes | Edges | Question | Symbolic view | Neural view |
|---|---|---|---|---|---|
| Molecule | Atoms | Bonds, bond order | Property of an atom environment | Predicates, graph patterns | Atom features, bond messages |
| Scene graph | Objects | Spatial and functional relations | What is graspable or true | Relations, rules, queries | Object and relation embeddings |
| Social network | Accounts | Follows, mentions, payments | Label of an account or a link | Rules, reachability, communities | Node embeddings, aggregation |
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.
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:
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 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:
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.
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.
Euler, the Königsberg bridges
A problem about connectivity, not geometry. The graph becomes an object of study.
Semantic networks, frames, description logics
Memory as concepts and labelled links; structured knowledge with inheritance and roles. Relations become a formal language.
Scarselli et al., graph neural networks
A fixed-point formulation of message passing. The neural side gets a graph-native architecture.
TransE
Knowledge-graph embeddings as translations. Link prediction becomes a vector-space problem.
GCN, MPNN, GraphSAGE, GAT
The modern message-passing toolbox: spectral approximations, edge messages, sampling, attention.
Expressivity, smoothing, squashing
GIN and the 1-WL bound; depth pathologies; the limits of local aggregation become a research program.
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.
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 Ã:
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.
| Layer | Aggregation | What it adds | Cost | Ceiling |
|---|---|---|---|---|
| GCN | Normalized sum with self-loops | A cheap spectral prior; stable training | Low | 1-WL |
| GraphSAGE | Mean / LSTM / pooling over sampled neighbours | Inductive inference on unseen graphs | Sampling variance | 1-WL (sum variant attains it) |
| GAT | Learned attention weights | Edge importance; multi-head routing | Extra parameters and memory | 1-WL |
| GIN | Sum + MLP | Injective multiset aggregation | More parameters; no normalization | 1-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.
| Round | Node values | Variance | What is left |
|---|---|---|---|
| 0 | (1, 2, 3) | 0.667 | Three distinct values |
| 1 | (1.5, 2, 2.5) | 0.167 | Contrast reduced by 4× |
| 2 | (1.75, 2, 2.25) | 0.042 | Contrast 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.
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).
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.
| Invariant | C6 | K3 ∪ K3 | 1-WL distinguishes? |
|---|---|---|---|
| Degree sequence | 2,2,2,2,2,2 | 2,2,2,2,2,2 | No |
| Color multiset | {A×6} | {A×6} | No |
| Components | 1 | 2 | No |
| Triangles | 0 | 2 | No |
| Girth | 6 | 3 | No |
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:
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:
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.
| Method | Object | Score | Symmetry | Composition | Inductive? |
|---|---|---|---|---|---|
| DeepWalk | Node | Skip-gram over random walks | n/a | No explicit | No |
| node2vec | Node | Skip-gram over biased walks | n/a | No explicit | No |
| TransE | Entity + relation | −‖h + r − t‖ | No (r = 0) | Yes (r1 + r2) | No |
| ComplEx | Entity + relation | Bilinear in complex space | Yes | Limited | No |
| RotatE | Entity + 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).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]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.
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.
| Coupling | Mechanism | What it buys | What it costs |
|---|---|---|---|
| Query as feature | Closure, distance, centrality, WL colour | Global information inside a local model | Precomputation; leakage; distribution shift |
| Query as loss | Penalty for violating a graph property | End-to-end training; soft guidance | No hard guarantee; fragile weighting |
| Query as verifier | Symbolic check, rejection, repair | Exact guarantee on the checked property | Search 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.
Scene graph
Objects become nodes, relations become edges. The planner queries the graph instead of re-reading the pixels.
Molecule
Atoms and bonds are a graph; valence and rings are constraints. A model that ignores them produces shapes, not chemistry.
Program
An AST or a control-flow graph makes syntax and reachability explicit. A grammar or a type checker supplies the constraint.
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.
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.
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.
| Symbolic concept | Graph / neural counterpart | What is preserved | What is lost |
|---|---|---|---|
Binary relation R(a,b) | Edge a → b with type R | The pair and the type | Arity > 2, negation, uncertainty |
Rule R(x,y) ← P(x,z), Q(z,y) | Two-hop path pattern | The composition | Variable binding, recursion, negation |
Query ?- R(a,Y) | Subgraph pattern / readout | The pattern | Exactness, completeness, cost bound |
Constraint degree(v) ≤ k | Mask or penalty | The preference | The guarantee (a soft penalty can be violated) |
| Derivation / proof | Message trace or attention path | A path through the computation | Logical 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.
| Property | Message-passing GNN | Datalog / CSP engine |
|---|---|---|
| Representation | Vectors, learned weights | Facts, rules, substitutions |
| Recursion | Bounded by depth | Unbounded, to a least fixpoint |
| Complexity | Polynomial for fixed depth | PTIME data complexity (Datalog); NP-hard in general (CSP) |
| Differentiable | Yes | No (unless relaxed) |
| Guarantee | Empirical | Sound and complete relative to the facts and rules |
| Generalization | Across graphs, if the distribution is right | Across 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.
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.
| Limit | Symptom | Mitigation | Cost |
|---|---|---|---|
| Long range | Prediction ignores distant nodes | Virtual node, rewiring, global attention, symbolic feature | Memory, quadratic cost, or a feature pipeline |
| Over-smoothing | Node vectors collapse as depth grows | Residuals, jumping knowledge, normalization, shallow depth | Less global view; architecture complexity |
| Heterophily | Averaging mixes incompatible neighbours | Relation-specific weights, signed/directed edges | More parameters; schema work |
| Systematic generalization | Fails on larger or recombined graphs | Algorithmic alignment, recursion, symbolic features | Design 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.
Explain why a graph is a relation without an order, and why that makes it a shared data structure.
State permutation invariance and equivariance, and explain why a flattened adjacency needs augmentation.
Write the MPNN template and name the four choices: message, aggregation, update, readout.
Compare GCN, GraphSAGE, GAT, and GIN on aggregation, cost, and expressive ceiling.
Explain over-smoothing and over-squashing, and why depth is both necessary and dangerous.
State the 1-WL ceiling and use C6 versus K3 ∪ K3 as a counterexample.
Compare DeepWalk, node2vec, TransE, ComplEx, and RotatE, and name one limit of each.
Explain why Datalog reachability escapes the local ceiling, and where the guarantee comes from.
Exercises
- 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. - 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 within0.1of each other? - 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?
- Prove the TransE limit. Show that a symmetric relation forces
r = 0andh = t. Then show that a one-to-many relation cannot be represented exactly. Which assumption would you change to fix each failure? - 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
Neural Message Passing for Quantum Chemistry
Gilmer et al. · ICML 2017 · the MPNN template
Inductive Representation Learning on Large Graphs
Hamilton, Ying & Leskovec · NeurIPS 2017 · GraphSAGE and sampling
Graph Attention Networks
Veličković et al. · ICLR 2018 · learned edge weights
How Powerful are Graph Neural Networks?
Xu et al. · ICLR 2019 · GIN and the 1-WL bound
Weisfeiler and Leman Go Neural
Morris et al. · AAAI 2019 · higher-order GNNs and the WL hierarchy
On the Bottleneck of Graph Neural Networks and its Practical Implications
Alon & Yahav · ICLR 2021 · over-squashing
Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
Oono & Suzuki · ICLR 2020 · depth and smoothing
node2vec: Scalable Feature Learning for Networks
Grover & Leskovec · KDD 2016 · biased walks and the p/q trade-off
Translating Embeddings for Modeling Multi-relational Data
Bordes et al. · NeurIPS 2013 · TransE, cited by title and venue; no arXiv ID
RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
Sun et al. · ICLR 2019 · rotations and composition
ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planning
Gu et al. · ICRA 2024 · structured perception for planning
The Logic of Graph Neural Networks
Grohe · LICS 2021 · the logical expressivity survey; cited by title and venue
Logical Expressiveness of Graph Neural Networks
Barceló et al. · ICLR 2020 · GNNs and guarded/graded modal logic; cited by title and venue
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.