A 50-node graph flattened to a 2,500-dim MLP input trains well but fails on held-out graphs. Why?

## What actually went wrong The design flattens a 50-by-50 adjacency matrix into one 2,500-dimensional vector and hands it to a fully connected network. Input dimension `k` of that vector corresponds to a fixed cell `(i, j)` of the matrix — and `i` and `j` are node numbers that came from whatever order the loader emitted. The first-layer weight attached to input `k` therefore encodes a statement about *positions*, not about the graph. Training accuracy is high because the training set is internally consistent: each graph was written down once, and the network memorises those particular position patterns. Held-out graphs are written down in their own arbitrary order, so the same structural motif appears in different cells and the memorised weights do not fire. The failure is not ordinary overfitting to noise; it is fitting a convention that carries no information. ## Three separate defects **1. No permutation symmetry.** Renumbering the nodes yields the same graph and a different input vector — up to 50 factorial of them for a 50-node graph (fewer only when the graph has symmetries of its own). No amount of data covers that space. You could sample random relabellings as augmentation, and the model would learn an approximate invariance, but you are spending capacity and examples on a property that a suitable architecture has exactly and for free. **2. No weight sharing across nodes.** A useful pattern learned about node 12 tells the network nothing about node 40, because they are wired to different weights. Contrast this with the reason a convolution works on images: the same small filter is applied at every location, so a pattern learned in one place transfers everywhere. The flattened graph model has thrown away the analogous sharing, so its sample complexity is enormous — and the first layer alone needs 2,500 times the hidden width in weights. **3. Fixed width against a variable, unbounded structure.** The vector has a slot for every node pair up to 50 nodes. A graph with 60 nodes cannot be fed; a graph with 12 must be padded with zeros that the model must learn to ignore. Worse, at the node level, a node's neighbourhood is an unordered collection whose size is not bounded in advance: on a power-law follower graph, accounts range from two neighbours to millions. There is no honest way to reserve "neighbour 1, neighbour 2, ..., neighbour k" columns in a feature vector — you would need a k that fits the largest hub, would waste almost all of it on typical nodes, and would still have to choose an order for the neighbours you did list, reintroducing exactly the arbitrary ordering that broke the model in the first place. ## Fixes that do not work **Canonical ordering.** Sorting nodes by degree before flattening sounds like it removes the arbitrariness. It does not: ties are common and must be broken by something, and any tie-break on continuous features is unstable, so a small perturbation reshuffles the entire input vector and the model sees a discontinuity. True graph canonicalisation is expensive and equally brittle to tiny changes. **More capacity or more regularisation.** Dropout, weight decay and a bigger network address variance around a sensible hypothesis class. Here the hypothesis class itself is wrong — the model is being asked to learn a symmetry group by rote. **Padding to a global maximum.** Padding lets everything run, but it caps the graph size you can ever serve, wastes most of the input on typical graphs, and leaves the ordering problem completely untouched. ## What replaces it Keep the graph as it naturally is: a node feature matrix plus an edge list. Then build a layer with two properties. - **A shared per-node transform.** Every node's feature vector goes through the *same* weights. Nothing is addressed by position, so a pattern learned anywhere applies everywhere, and the layer is automatically equivariant. - **An order-free combination of neighbours.** For each node, gather the feature vectors of its neighbours through the edge list and combine them with an operation that does not care what order they arrived in, then use the result to update the node's own vector. Stack a few such rounds and information reaches nodes several hops away. Because the layer reads the edge list rather than fixed cells, it accepts any number of nodes and any degree — the hub with millions of neighbours and the leaf with two are both handled by the same weights. For a graph-level prediction, one order-free pooling step over the final node vectors produces a fixed-size summary regardless of N, which is what the earlier design was trying and failing to obtain by flattening. ## The general lesson When the data has a symmetry, you can build it into the architecture or spend data teaching the model to approximate it. On graphs the symmetry group is factorially large, which makes the second option hopeless — and the diagnostic signature is exactly the one in this scenario: excellent training numbers, collapse on data that is structurally identical but written down differently.