Course / Lecture 04 / Lab Lab 04

Message passing, in your hands.

A five-node graph, fixed weights, three rounds. Click a node and watch the messages arrive; then run a Datalog query and a 1-WL comparison on the same graph. The point is not the numbers. It is the locality — and the ceiling that locality creates.

5 nodes 3 rounds 2 engines No install · deterministic · runs in the browser

The message-passing lab

Part 1 · Run the message passing

The graph is undirected: edges are A–B, A–C, B–D, C–D, and D–E. The initial node vectors are A = [1,0], B = [0,1], C = [1,1], D = [0,1], E = [1,0]. The layer is hand-written and fixed:

mu→v = W hu,   av = (1/|N(v)|) Σu∈N(v) mu→v,   hv′ = ReLU(hv + av)
(L.1)

W = [[1, 1], [0, 1]]  ·  no bias  ·  mean over in-neighbours  ·  residual sum  ·  ReLU  ·  not trained

Click a node or use the buttons below. The selected node is orange; its incident edges are highlighted. The number under each node is its current vector.
Round 0. Select a node to see the messages that would update it.

Selected node

A = [1.00, 0.00]

Incoming messages for the next round

Each message is W hu; the aggregate is their mean.
FromhuW hu

Aggregate and update

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

History for this node

t = 0 is the input; each row is the state after that many rounds.
thv(t)cos to A

The cosine column is a smoothing probe: it compares the selected node to node A. At t = 0, B is orthogonal to A; after a few rounds the vectors point in a similar direction. That is over-smoothing in miniature. The lab stops at three rounds so the arithmetic stays inspectable.

Part 2 · The same graph as a logic program

The five nodes and five edges are now Datalog facts: each undirected edge becomes two directed facts. reach is the transitive closure; the first rule seeds it with edges, the second composes a reachable pair with an edge. The engine computes the least fixpoint and returns a derivation.

The same graph, read as undirected facts. Tick “Cut D–E” to remove the tail and watch the query fail; the facts, not the drawing, decide the answer.
Choose a source and target, then run the query.

The program

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

Least-fixpoint rounds

Each round adds pairs reachable by one more edge.
RoundNew pairsTotal
—Run the query.—

Derivation

Run the query to see the proof tree.

Result

reach(1,5) = ?

The Datalog semantics is the least fixpoint: every derived fact has a finite proof. If the facts are incomplete, the engine cannot know; it answers relative to what it has. That is the closed-world assumption, and it is why the cut edge matters.

Part 3 · The ceiling: two graphs 1-WL cannot tell apart

Both graphs below are 2-regular on six nodes: a six-cycle C6 and two disjoint triangles K3 ∪ K3. Give every node the same feature and run color refinement. If the color multisets stay identical, no message-passing GNN can distinguish the graphs.

C6 · one component · girth 6
K3 ∪ K3 · two components · girth 3
Round 0. Every node starts in class A.

Color classes by round

Class counts after each refinement round.
RoundC6K3 ∪ K3Same?
0A×6A×6Yes

Invariants that do distinguish them

InvariantC6K3 ∪ K3
Nodes66
Edges66
Degree sequence2,2,2,2,2,22,2,2,2,2,2
Components12
Triangles02
Girth63
Bipartiteyesno

The colors never split because every node has exactly two neighbours of the same color. The global invariants — components, triangles, girth — are not visible to a local aggregation. A GNN could see them only if you give it a feature that already encodes them, or if you change the architecture. That is the 1-WL ceiling, and it is why a symbolic closure is sometimes the right feature to add.

WHAT TO NOTICE

What this shows — and what it does not.

What this shows

Message passing is local averaging: each round is one more hop, and the vectors become more similar as the neighbourhoods overlap. The Datalog engine is the opposite profile: it recurses to a least fixpoint, so it reaches any distance, and every answer comes with a derivation. The 1-WL pair shows the ceiling of the neural side: identical local color multisets, different global structure. The same graph supports both a vector computation and a symbolic one; the bridge is the shared object, not a shared semantics.

What this does not show

The weights are arbitrary and fixed; nothing is trained. The graph has five nodes, so three rounds already see most of it, and the smoothing probe is a toy. The 1-WL ceiling applies to anonymous graphs without unique identifiers or positional features; real systems often add such features, and then the ceiling moves. The lab does not measure over-squashing on a real task, does not evaluate a benchmark, and does not prove that a Datalog program is correct. A symbolic engine is exact relative to its facts and rules — and the facts can be wrong.

Read §2 again · Read §4 again · Open the slides