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.
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:
W = [[1, 1], [0, 1]] · no bias · mean over in-neighbours · residual sum · ReLU · not trained
Selected node
A = [1.00, 0.00]
Incoming messages for the next round
| From | hu | W 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 | hv(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 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
| Round | New pairs | Total |
|---|---|---|
| — | 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 6K3 ∪ K3 · two components · girth 3Color classes by round
| Round | C6 | K3 ∪ K3 | Same? |
|---|---|---|---|
| 0 | A×6 | A×6 | Yes |
Invariants that do distinguish them
| Invariant | C6 | K3 ∪ K3 |
|---|---|---|
| Nodes | 6 | 6 |
| Edges | 6 | 6 |
| Degree sequence | 2,2,2,2,2,2 | 2,2,2,2,2,2 |
| Components | 1 | 2 |
| Triangles | 0 | 2 |
| Girth | 6 | 3 |
| Bipartite | yes | no |
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 this shows — and what it does not.
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.
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.