Keep the relations in view

Suppose five buses in a small power-grid sketch each carry a feature. You want a model that can combine a bus's own information with information from connected buses. A table can store the features, but the table's row order does not say who is connected to whom. The graph supplies that missing relation.

We will use the shape of a grid to make message passing inspectable. The values are invented, dimensionless features. They are not voltage, power, fault probabilities, or calibrated stress readings. No electrical equation runs underneath the picture.

A graph is a set of nodes and a set of edges. Here the nodes are A, B, C, D and E. The five undirected edges are AB, AC, BC, CD and DE. Undirected means that our model permits messages in both directions along each listed connection. It says nothing about the direction of electrical flow.

A's neighbors are B and C. C's neighbors are A, B and D. E has only D. Move the circles around on the page and those neighbor sets stay the same: a graph's drawn position is different from its connectivity.

CL-001 · Gilmer et al., §2: attributed graph inputs

A number attached to a node

A feature is a recorded input attached to an entity. Write the input at node $i$ as $x_i$. In A–E order, our input is:

The superscript $\top$ indicates a column: five rows, one feature per node. A richer input could give each node a vector—an ordered list of several features. We start with a scalar, one number, so every operation fits on paper.

A hidden state is the representation carried between layers. We write it as $h_i^{(\ell)}$, where $\ell$ counts layers. At the start, set $h_i^{(0)}=x_i$. The network will change states while the input remains the original record.

Edges can also carry features. We assign each edge a synthetic gate $e_{ij}=1$. Later we will halve the C–D gate. This multiplier scales a model message; it is not a measured property of an electrical line.

CL-007 · Toy assumption: all five values, edge gates and the graph itself were chosen for this lesson.

A representation is a starting point

So far, we have a graph and features. We have not specified what to predict, what counts as a good prediction, or how to learn parameters. Those are separate modeling choices.

The immediate task is smaller: compute a new state for every node using the same local rule. If you can explain what C receives, you can reconstruct the main mechanism of a message-passing layer. Then we can ask how far a local change travels.

CL-014 · Model boundary: topology chooses communication paths. This toy contains no physical power-balance or conservation equation.

Start with C

C begins at 1. Its neighbors A, B and D begin at 2, 0 and 3. Imagine that each neighbor sends its current value along the connecting edge. With all gates equal to one, C receives three messages: 2, 0 and 3.

Our toy rule keeps half of C's own value and adds half of the mean incoming message. The mean is the sum divided by the number of neighbors:

The arithmetic at every other node follows the same rule. D uses old C=1 and old E=0, so D's neighbor mean is 1/2 and its new state is 7/4. D does not read the newly computed C=4/3 in this round.

This is a synchronous update: everyone reads the same old snapshot, then all new states replace it together. Updating an array in place as you walk through the nodes would make later nodes read earlier results and create a different computation.

CL-009 · Derived from the toy rule. Fractions are exact; tables round only for display.

Give the operations names

Let $N(i)$ be the neighbor set of node $i$, and let $d_i=|N(i)|$ be its degree, the count of neighbors. The index $j$ runs through that set. The gate $e_{ij}$ multiplies the sender's state.

The first line aggregates messages into $q_i^{(\ell)}$. The second combines the aggregate with the node's own state. We stipulate $a=b=1/2$ for every node and every round. An isolated node has no neighbors; our declared convention sets its aggregate to zero, giving $h_i^{(\ell+1)}=a h_i^{(\ell)}$.

Degree counts present edges, even if a gate reduces a message. It does not sum the gate values. That detail will matter when we edit C–D. Self information is carried by the $a h_i$ term; there are no self-edges in our edge list.

CL-008 · Toy assumption: this exact averaging rule and isolated-node convention are choices for an inspectable model.

Where the neural part enters

A learned message-passing network replaces these simple operations with parameterized functions. A message function $M_{\theta_\ell}$ can use the receiver's state, sender's state and edge attributes. An update function $U_{\theta_\ell}$ combines the aggregate with the receiver. The symbol $\theta_\ell$ denotes the learnable parameters at layer $\ell$.

AGG means an aggregation such as sum or mean. Our toy uses $M(h_i,h_j,e)=e h_j$, a mean aggregate, and $U(h,q)=a h+bq$. Practical functions can transform vectors and use nonlinearities. The small arithmetic example exposes the same message–aggregate–update structure.

The functions are shared across nodes within a layer. C and E use the same parameters but receive different inputs. General networks may use different parameters in different layers; we additionally tie our two coefficients across rounds.

CL-002 · Gilmer et al., §2, equations (1)–(3)

Nothing in this guide fits those coefficients. A forward pass computes states with supplied parameters. Training would require an objective and an optimizer to change parameters. Advancing the layer control is another stage of the forward computation, not another training step.

CL-015 · Derived distinction: the canonical lab contains no loss, gradient calculation or parameter update.

Can E notice A?

Keep the graph and weights fixed. Raise only A's initial feature from 2 to 4. Before trying the lab, predict: can E's state change after one layer? After two?

In the first layer, B and C read A directly. A also retains part of its own change. D reads C's old state, which is still 1 in both runs. E reads D's old state, which is still 3. Neither D nor E can notice A yet.

In the second layer, D can receive C's changed state from layer one. E still reads D's unchanged layer-one state. The earliest path from A to E is A–C–D–E: three edges, hence three local layers.

CL-004 · Battaglia et al., §4.3 and Figure 7: local propagation without a global channel

Trace the two forward passes

The lab compares a baseline A=2 with your selected A value. Both runs use the same selected connection setting and the same weights. This isolates the effect of A's feature. Double rings and signed differences mark a numerical change; a connected node may still have zero difference at the current layer.

Try A=4 at layers 0, 1, 2 and 3. Then return A to 2: every difference vanishes, even though paths still exist. The graph gives a set of possible dependencies. An actual change also requires a different input and a computation that responds to it.

For this positive linear toy and a nonzero change at A, every node within the selected number of hops responds. For a general learned GNN, zero weights, cancellation or a nonlinearity can suppress a reachable input. “Within k hops” is a dependency bound, not a promise that every reachable feature changes every output.

CL-010 · Derived for the stipulated positive self and neighbor coefficients. Displayed differences use a 10⁻¹² threshold; computation uses full precision.

An edge edit changes the rule locally

Reset, then remove C–D. A's change can now reach only A, B and C, however many local layers you apply. The graph has split into two connected components. D and E still update their own states; they simply have no computational path from A.

Removing C–D also changes the neighbor count at its endpoints. At the original input, C now averages A=2 and B=0: the mean is 1, and the new C is 1. D now averages only E=0, so its new state is 3/2.

Now keep C–D but halve its gate. C still has three neighbors and D still has two; their messages across this edge are multiplied by 1/2. C's new value becomes 13/12 and D's becomes 13/8. A weaker message and a missing edge are different interventions in this model.

The lesson is not that a particular normalization is correct for a grid. It is that you must inspect the normalization actually used. Here a half gate attenuates a message without renormalizing the mean. It does not simulate an electrical line change.

CL-011 · Derived. The table holds A at its original value 2 to isolate the edge intervention. Later effects can spread from both edited endpoints.

Reorder everything consistently

Our arrays use A, B, C, D, E. Another program might store E, C, A, D, B. If the features and edge references move consistently with their nodes, this is the same graph in a different storage order.

The output attached to C remains 4/3. It simply occupies a different array row. This is permutation equivariance: permuting the input representation permutes the node outputs in the same way.

That is different from invariance, where an output stays exactly the same under a permutation. A sum of incoming messages is invariant to their list order. The collection of per-node outputs is equivariant to reordering the nodes. Neither property says that all nodes must have equal states.

CL-003 · Battaglia et al., §3.2.2–3.2.4: shared functions and invariant aggregation

Why the update follows the node

C still receives the same three values on the same three edges. A sum or mean does not care whether those messages are listed as A, B, D or D, A, B. The update uses the same coefficients at every receiver. Therefore C gets the same answer.

For a compact statement, let $P$ mean a consistent reordering, and let $F_G$ mean one update on graph $G$. If $PG$ is the graph with node records and edge references reordered together, then:

Read the equality as: reorder then compute, or compute then reorder—the result agrees. This is a derivation from shared functions and an order-independent reducer. Floating-point summation order may introduce tiny rounding differences in an implementation; our tests compare with an explicit absolute tolerance.

Shuffling only the feature values is a different experiment. Giving A the old value of E while leaving the edges fixed changes which entity has which input. Equivariance does not require that change to leave predictions alone.

CL-012 · Derived equivariance. A node ID is a stable reference here, not a special learned parameter or an extra numerical input.

A state still needs a job

A readout maps the resulting states to a desired output. A shared node head could produce one output for each node. A graph head might first sum node states and then produce one output for the whole graph. A graph-level output can be invariant to node order while node-level outputs remain equivariant.

Here $L$ is the last layer, $R_\phi$ is a parameterized node readout, and $\widehat{y}_i$ is a proposed prediction. A supervised objective would compare those predictions with targets and adjust $\theta$ and $\phi$. The symbols locate where learning would happen; the toy has no fitted readout.

CL-016 · Gilmer et al., §2, equation (3) and output-level examples

For document intelligence, nodes could represent text regions and edges could represent a chosen spatial relation. For a grid study, nodes could represent buses with suitably defined features. Those are possible problem formulations, not evidence of useful accuracy. The graph construction, target, loss and held-out evaluation would need their own justification.

A useful local aggregation can also discard a distinction that the target needs. The next chapter examines a case where repeated mixing erases almost everything that distinguishes our five starting values.

Repeat this exact average

Return to the original connected graph, all gates 1 and $a=b=1/2$. Each new state is a convex average: nonnegative coefficients sum to one. It stays between the previous smallest and largest values. The overall range therefore cannot increase under this exact rule.

Keep applying the same operator. The node values approach a common value. The bars below show a deterministic computation from the original input; they are not a training curve and report no prediction accuracy.

Why 1.3? This neighbor-mean rule preserves a degree-weighted average. A and B each have degree 2, C degree 3, D degree 2, E degree 1. Thus the limit is:

The ordinary mean is 6/5, a different number. The denominator used in the update determines which weighted quantity is preserved. On this finite connected undirected graph, the self term makes the averaging walk lazy, avoiding an alternating two-cycle. Repeated application converges to its unique degree-weighted consensus.

CL-013 · Derived for this fixed, connected, undirected, unit-gate toy. Removing C–D gives separate limits 1 on ABC and 1.5 on DE. Halving a gate while retaining the old degree breaks the convex-average premise.

What this says about oversmoothing

Initially, A=2 and E=0 were easy to distinguish by their state. At consensus they both carry 1.3. A downstream head that sees only this scalar has lost the distinction. This illustrates a mechanism behind oversmoothing: repeated neighborhood mixing can make node representations less discriminative.

The scope matters. Li, Han and Wu analyze smoothing in graph convolutional networks; Oono and Suzuki give conditions under which particular GNNs approach a restricted representation subspace. These analyses do not establish that every deep GNN makes every vector identical or that an extra layer always reduces task accuracy.

CL-006 · Li, Han & Wu: “When GCNs Fail,” Figure 2 and Theorem 1

CL-006 · Oono & Suzuki, §3.3 and §4: conditions on expressive-power loss

Nor is our update the exact Kipf–Welling GCN layer. That layer uses added self-connections, symmetric degree normalization, a trainable matrix and a nonlinearity. Our neighbor mean and separate half-self term are deliberately simpler. Do not transfer the number 1.3, or our scalar consensus shape, to another normalization.

CL-005 · Kipf & Welling, §2, equation (2)

A second limitation is already visible at one layer: a mean of messages [0,2] equals a mean of [1,1]. This toy cannot recover which pair produced that aggregate if all other inputs agree. Aggregation is a modeling decision about which distinctions to retain.

Derived counterexample from CL-008: equal means do not imply equal neighbor multisets. This is a limitation of the chosen mean, not every possible GNN.

Try a graph that is not a grid

A document relation graph has five text regions P, Q, R, S, T. Its undirected edges are PQ, QR, QS and ST. Imagine the same positive self-plus-neighbor rule and unit gates. Increase only R's initial scalar feature by 2.

Which regions must change after two synchronous rounds? Can T change yet? If Q–S is removed, can R's change ever reach T?

You do not need an OCR model to answer. Use the relation graph and the computation, not the apparent closeness or meaning of the text regions.

Back at the grid, the same discipline applies. Choose what nodes and edges mean, define message and update functions, locate any learned parameters, and check the output against the intended task. A graph-shaped model supplies a pattern of information access. Physical validity comes only from additional modeling and evidence that this toy does not provide.

CL-014 · No physical simulation or real-grid recommendation. The transfer answer is derived from CL-004/010's local-dependency argument.