Permutation equivariance makes a graph model respect equivalent node orderings: reordering a graph’s nodes should reorder its outputs correspondingly, not change the represented result arbitrarily. This matters because multiple adjacency matrices can describe the same graph, unlike a fixed image grid. section 3.4.1
Message passing builds this property with order-independent aggregation. It collects neighboring features or messages using operations such as sum, mean, or maximum, then transforms the aggregate with a neural network and activation function before updating node embeddings. Subtraction and division are unsuitable because they depend on ordering. section 3.4.2
A practical message-passing layer follows this sequence:
- Aggregate node or edge data with an order-independent operator. section 3.4.2
- Transform the aggregated messages with learnable weights, a neural network, and a nonlinear activation. section 3.4.2
- Combine the transformed messages with node or edge data and previous embeddings; pool afterward only when graph-level output requires it. section 3.4.2
Adjacency-matrix ordering
Swap two rows and the corresponding columns of an adjacency matrix. The matrix changes, but it still represents the same graph. A suitable graph layer therefore produces equivalent outputs under this reordering, whereas a conventional CNN applied directly to the matrix would not reliably do so. section 3.4.1
Figure 3.15 Elements of our message-passing layer. Each message-passing layer consists of an aggregation, a transformation, and an update step.
Use the layer diagram to track how aggregation, transformation, and update steps preserve graph-structured representations. section 3.4.2
