Object-Centric and Relational Worlds › Relations, Graphs, and Message Passing

Once the scene is a set of objects, the natural language for how they influence each other is a graph. Objects are nodes; relations, known or learned, are edges. Graph representations give us a principled way to write dynamics that depend on which objects interact, not just on the global scene. The move from sets to graphs is the move from "there are things" to "these things affect each other in these ways," and it is the second half of the structured bet.

Formally, a graph-structured scene is a tuple $(\mathcal{V}, \mathcal{E}, u)$: nodes $\mathcal{V}$ with per-object states $h_i$ (position, velocity, pose, appearance summary), edges $\mathcal{E}$ with per-relation attributes $e_{ij}$ (distance, contact type, spring rest length, relative velocity), and optionally a global attribute $u$ describing scene-level context (gravity, table friction). The three levels of the tuple are worth keeping separate in your head, because different physical regularities live at different levels: forces between objects live on edges, intrinsic object behavior and damping live on nodes, and uniform fields and shared environment properties live in the global attribute. Battaglia and colleagues (2018) made the influential argument that this "graph network" block generalizes a large family of models, from interaction networks to transformers, and that the choice of graph is a statement of relational inductive bias: an assumption about which interactions can matter.

The bias is a commitment. A fully connected graph assumes any object may affect any other; a sparse spatial graph assumes locality. Getting this wrong can waste computation or omit relevant interactions. With $n$ objects, a complete graph has $O(n^2)$ edge activations, so memory and compute grow quadratically even though a shared edge function keeps parameter count fixed. Sparse graphs are useful when their construction covers the interaction support.

The quadratic cost of the dense choice is easy to state and easy to see.

At forty objects the dense graph carries nearly twenty times the edges of this ideal 2-regular graph. This analytic line is not the exact count of the union-symmetrized $k$-nearest-neighbor builder used later: that data-dependent construction can contain between $nk/2$ and $nk$ undirected edges depending on reciprocal choices.

For systems whose direct interactions are local in space, a $k$-nearest-neighbor or radius graph can be a cheap approximation when its edges cover the true interaction support. The risk is explicit: $k$-nearest neighbors can omit contacts in dense regions or add irrelevant neighbors in sparse ones, while fixed-radius graphs omit long-range effects and cannot express mediated influence in one hop.

Many graph-based dynamics models use a variant of one update, applied one or more times. The recipe has three stages: compute a message per edge, aggregate messages per node, and update each node's state. For every edge from sender $j$ to receiver $i$, an edge function computes a message:

$$m_{ji} = \phi_e\big(h_j,\; h_i,\; e_{ji}\big).$$

Each node aggregates its incoming messages with a permutation-invariant reduction $\square$ (sum, mean, max, or set attention with shared order-independent scoring):

$$\bar{m}_i = \square_{j \in \mathcal{N}(i)}\, m_{ji},$$

and a node function produces the next node state:

$$h_i' = \phi_v\big(h_i,\; \bar{m}_i\big),$$

where:

• $h_j$, $h_i$: the current states of sender node $j$ and receiver node $i$
• $e_{ji}$: the attributes of the edge from sender $j$ to receiver $i$
• $\phi_e$: the learned edge function, shared across all edges
• $m_{ji}$: the message computed on the edge from sender $j$ to receiver $i$
• $\mathcal{N}(i)$: the set of nodes with an edge into node $i$, the in-neighborhood of $i$
• $\square$: a permutation-invariant reduction, including sum, mean, max, or order-independent set attention
• $\bar{m}_i$: node $i$'s aggregated incoming message
• $\phi_v$: the learned node function, shared across all nodes
• $h_i'$: the next state of node $i$, one message-passing round later

A global update $\phi_u$ over aggregated node and edge summaries can weave in scene-level context. Three properties of this recipe carry the real weight:

• Permutation invariance of aggregation. Sum, mean, and max do not depend on neighbor order, so the same parameters can be applied to variable-size compatible graphs. Sum preserves the vector total: six equal, co-directed forces yield six times one force, while general force vectors can differ or cancel. Mean instead normalizes by degree.
• Parameter sharing across edges and nodes. One edge function is applied everywhere. A learned rule can transfer across pairs when relation types, feature semantics, and physical regimes match.
• Composition. After $L$ synchronous local rounds, information can travel up to $L$ hops. Dependence across a path requires at least its graph distance in rounds unless a global solver or nonlocal edge supplies a shortcut.

Transformer self-attention can also be viewed as message passing on a complete graph with attention-weighted aggregation. Key differences include initialization, normalization, iterative recurrent slot updates, exchangeability, and the decoder and training objective. Slot Attention allocates each input's unit weight across slots, creating competition that encourages a partition; standard attention normally lets each query normalize independently over keys. We develop the transformer side in Transformers and Neural State-Space Architectures.

Finally, a symmetry note. Absolute position can often be replaced by relative position $\Delta x=x_j-x_i$ and relative velocity $\Delta v=v_j-v_i$, while retaining necessary invariant attributes such as mass, type, and spring rest length. When all inputs and operations respect translation symmetry and there are no position-dependent fields or boundaries, this makes translation invariance automatic. Rotation-equivariant architectures such as the equivariant graph networks of Satorras and colleagues (2021) further restrict the hypothesis class and can improve sample efficiency when that symmetry is valid on the evaluated task.