Two triangles and a hexagon

STATEMENT

Exhibit two graphs that differ in structure but that every message-passing network maps to the same output, and name a quantity that tells them apart.

GIVEN

Graph $G_1$ is two disjoint triangles; $G_2$ is a cycle of six nodes. Every node starts with the same feature vector. A message-passing network has any number of layers of the form (I.14.2), any aggregator, and a sum readout.

FIND

The colour-refinement colours of both graphs; the network’s outputs; the number of triangles and of connected components in each.

STRATEGY

Run colour refinement by hand: it stalls after one round. Then apply the induction of I.14.T4.

SOLUTION

Refinement. All nodes start with one colour. In both graphs every node has two neighbours, each with that colour, so every node receives the same signature, (one colour, two neighbours of that colour), and one new colour. The next round sees the same thing. The colour counts, six nodes of one colour, agree at every round.

The network. By the induction in proposition 4, a node’s state after layer $t$ is a function of its colour after round $t$. All twelve nodes share a colour at every round, so all twelve have the same state at every layer, whatever the weights. The sum readout returns six times that state for both graphs. The outputs are identical.

The check script confirms it for three randomly weighted sum networks of three layers: the sorted node states of $G_1$ and $G_2$ agree to twelve decimal places.

What differs. The number of triangles is $\operatorname{tr}(\mat A^3)/6$, because each triangle gives six closed walks of length three: $2$ for $G_1$ and $0$ for $G_2$. $G_1$ has two connected components and $G_2$ one. A molecule-property model could hardly be indifferent to either.

Check — sanity

Both graphs have six nodes and six edges and are $2$-regular, so any statistic built from degrees alone must agree. The difference is in cycles, which no fixed number of local averaging steps can count here.