On which graphs does learned neighbour attention beat degree-normalized averaging, and where does it not help?

## The decision in one line Learned per-neighbour weighting earns its cost when **relevance varies inside a neighbourhood** and **the node features let a small scorer predict that variation**. Both halves are required. Miss the first and there is nothing to learn; miss the second and there is no way to learn it. ## Case one — relevance varies and features expose it Take a road-sensor graph for traffic forecasting. Node `S` sits on a highway with three edges: the junction 400 m upstream, a sensor on the opposite carriageway, and an adjacent side street. Next-hour speed at `S` is essentially a function of the upstream junction; the side street contributes almost nothing. A combiner whose weights are decided by degrees has no way to say that — its weights are a property of the graph's shape, and the three neighbours look structurally similar. A learned scorer reading the endpoint features (road class, current occupancy, relative direction) can put most of the mass on the upstream junction and drive the side street toward zero. The coefficients can even move with the state of the graph: the upstream junction matters more at rush hour than at 3 a.m., and the score depends on features that change hourly. ## Case two — adversarial or noisy edges A fraud graph is the sharper version. Accounts used for fraud deliberately connect to ordinary accounts: shared devices, small transfers to legitimate counterparties, one honest employer. Uniform or degree-based averaging blurs the fraud node into that innocent neighbourhood, and the more edges the fraudster builds, the more diluted the signal — the attack works *because* the aggregator is fixed. A learned coefficient can look at the endpoint features and suppress the edges that carry no evidence, keeping the node's representation from being averaged into innocence. Any setting where an adversary can add edges is a setting where fixed-weight aggregation is an attack surface. ## Where it does not help **Interchangeable neighbours.** On a strongly homophilous citation-style graph where a node's neighbours mostly share its label, the honest answer is that averaging is close to optimal. The learned coefficients converge to something near-uniform, and you paid for a scoring vector, a per-edge softmax and per-head coefficient storage to reproduce a mean. **Uninformative features.** The scorer reads only the transformed endpoint features. If those are near-constant one-hot identifiers or noise, no coefficient can be predicted from them; the layer will still fit *something* on the training graph, which usually means overfitting rather than insight. **Small graphs with few labels.** Extra parameters plus a sharpening nonlinearity in a low-label regime is a variance story. Attention can latch onto a handful of edges that happen to correlate with the training labels and transfer badly. **Strong heterophily, beyond a point.** This is the nuance that separates a good answer from a great one. Coefficients are non-negative and sum to one, so the layer forms a *convex combination* of neighbour vectors. It can reduce a misleading neighbour's contribution toward zero, but it cannot give that neighbour a negative weight, and it cannot make a node's representation move *away* from its neighbourhood. On graphs where connected nodes are systematically opposite, that ceiling is real, and the fixes people reach for — separating the self representation from the aggregated one, keeping signed or higher-order terms — are architectural, not a matter of tuning the attention. ## The cost you are trading against Per edge, per head, per layer, the model computes a score and stores a coefficient. On a graph with heavy-tailed degrees this is dominated by the hubs: a node with a hundred thousand edges materialises a hundred thousand coefficients for every head. Latency at serving time grows the same way, and the coefficients are not cacheable across feature updates because the score depends on the features. Fixed structural weights, by contrast, can be precomputed once and reused for the lifetime of the graph's topology. ## How to decide in practice Run the fixed-weight aggregator first; it is the cheaper baseline and on many graphs it is not beaten. Then measure two things. First, the *homophily* of your labels — the fraction of edges joining same-label nodes — which tells you whether neighbours are interchangeable. Second, after training an attention model, the distribution of the learned coefficients: if they sit near `1/degree` everywhere, the model is telling you that it found nothing to weight, and the extra machinery should come out. A model whose coefficients are sharply peaked on a minority of edges, and which beats the fixed baseline on a held-out subgraph, has earned its place. ## The trap answer "Attention is strictly more expressive, since uniform weights are a special case it can represent." That is true about the hypothesis space and irrelevant about the outcome. Being able to represent the mean is not the same as reliably learning it from limited labels, and the statement quietly ignores the memory, latency and overfitting costs that decide the question in production.