Over-Smoothing and Depth

### The phenomenon A message-passing graph network updates every node by combining that node's own vector with an aggregate of its neighbours' vectors, then applies a learned transform and a nonlinearity. Stack `k` such layers and every node has mixed information from a widening neighbourhood. **Over-smoothing** is what happens when that mixing goes too far: the node representations stop differing from one another. After enough layers, two nodes in the same connected component carry nearly the same vector, and no classifier sitting on top can tell them apart. The cause is that neighbourhood averaging is a **low-pass filter on the graph**. Each round damps the components of the signal that vary sharply between adjacent nodes and preserves the component that is nearly constant across the graph. Repeat it and only the smooth component survives. ### The linear picture Take the common degree-normalized propagation: with self-loops added, node `v` receives `sum over u in N(v) of h_u / sqrt(d_v * d_u)`, where `d` is the degree including the self-loop. Strip out the nonlinearity and the learned weights for a moment and you are just applying the same normalized-adjacency operator over and over. That operator's largest eigenvalue is 1, and repeated application drives any starting signal toward the corresponding eigenvector — whose entries within a connected component are proportional to `sqrt(d_v)`. So in the limit, embeddings differ only by a degree-dependent scale factor and point in the same direction. Two nodes with the same degree become exactly indistinguishable; every node's angle in embedding space becomes the same. Nonlinearities and learned weights slow this down and complicate it, but they do not change the direction of travel. ### Detecting it You do not need to guess. Instrument the forward pass at each depth and measure how different the node embeddings still are: - **Mean pairwise cosine similarity** between node embeddings. On a healthy 2-layer model this sits well below 1. Train the same architecture at 2, 4, 8 and 12 layers and log the number for each: the over-smoothing signature is that mean similarity climbing monotonically toward 1.0 while validation accuracy peaks at 2 layers and falls from there. - **Dirichlet energy** — the sum over edges of the squared difference between the two endpoint embeddings (usually degree-normalized). It measures how much the signal varies along edges, and it decays toward zero as the stack deepens. - **A layer-wise probe**: freeze the trained model, take the hidden states from each layer, and fit a cheap linear classifier on each. If accuracy rises to layer 2 and then falls, the deeper layers are destroying information rather than adding it. ### What it is not Over-smoothing is **not** vanishing gradients. A deep graph network can train perfectly well — the training loss goes down, gradients are healthy — and still be useless, because the collapse happens in the *forward* pass. Repeated averaging destroys the information before the classifier ever sees it. The tell is the pair of measurements: healthy gradient norms plus rising embedding similarity. It is also not simply overfitting. Overfitting shows as a widening train/validation gap; over-smoothing usually depresses **training** accuracy too, because the representations feeding the head genuinely cannot separate the classes. And it is not a claim that depth is useless in general. It is specific to repeatedly averaging over a fixed graph. Deep stacks that mix in the original features at each layer, or that keep every layer's output available to the readout, remain usable much deeper. ### Why the shallow baseline usually wins This is the practical consequence interviewers want you to state: on standard node-classification benchmarks the strongest plain message-passing model is typically two layers, sometimes three. Two rounds already give each node a two-hop view, which for homophilous graphs — where neighbours tend to share the label — carries most of the usable signal. A third and fourth round add a lot of mixing and very little new evidence, so the smoothing cost overtakes the reach benefit almost immediately. If someone proposes "let's go deeper for more capacity", the right response is that in a plain stack, depth buys *reach*, not capacity, and reach past the useful radius is actively harmful. ### First moves when you see it Widen rather than deepen; keep the shallow model and add width or better features. If depth is genuinely required, use an architecture that resists the collapse — keep the layer-0 representation alive at every layer with an initial-residual term, or let the readout see all layers rather than only the last. Some graph-specific normalizations exist that explicitly re-separate embeddings after each round by rescaling pairwise distances. Whichever route you pick, keep logging the similarity curve: it tells you whether the fix actually worked, which accuracy alone will not.