Interactive demo · Foundations of Deep Learning · Chapter 13

Reorder the nodes, compare the outputs

Writing a graph down as a matrix forces a node order, and the order is arbitrary. Reordering by a permutation matrix P turns the node data X into PX (13.4) and the adjacency matrix A into PAPT (13.5). A layer that aggregates each node's neighbours with a symmetric function and applies the same update at every node is equivariant: the outputs are the old outputs in the new order, Y(PX, PAPT) = P Y(X, A) (13.7), and a sum over the nodes is invariant (13.6). Shuffle the nodes and try layers that break the rule.

Graph

Layer hn ← tanh(Wselfxn + Wneighzn + b)

Node order

Weights and features (seed)

Try these

Each node has D = 2 features drawn from the seeded generator, and the layer maps them to 2 outputs. Aggregations: sum (13.12), mean (13.13), the Kipf–Welling weights 1/√(|N(n)||N(m)|) (13.14), the GCN matrix with self-loops D̃−1/2(A + I)D̃−1/2, element-wise max, bilinear attention (13.27), and a deliberately broken one, "position", which multiplies neighbour m by a weight tied to its index m, like the filter weights wj of (13.8). The last line of the table is a one-hidden-layer network applied to the flattened matrix A.

In the lecture notes