Graph Attention Networks Explained

A graph convolution aggregates a node’s neighbours with weights fixed by the graph structure before training starts. A graph attention layer learns those weights from the node features instead. Everything else about the two is the same, and the whole difference is one softmax over a small learned score.

The coefficient a GCN cannot change

In a graph convolutional layer, the contribution of neighbour j to node i is scaled by a constant derived from the degrees:

GCN coefficient   c_ij = 1 / sqrt( d_i · d_j )

for a node i of degree 4 with neighbours of degree 4, 2, 9, 4:
  c = 1/sqrt(16)=0.250   1/sqrt(8)=0.354
      1/sqrt(36)=0.167   1/sqrt(16)=0.250

Those numbers are a function of the adjacency matrix alone. They are the same for every layer, every feature, every training step and every task. If one of those four neighbours is the informative one, the layer has no mechanism to say so — the only thing it knows about a neighbour is how many edges it has.

It also means the model cannot be applied to a graph it has not seen, because the coefficients are baked into a normalised adjacency matrix computed up front. Both limitations have the same fix.

The attention equation

Graph Attention Networks (Veličković et al., ICLR 2018) replaces the constant with a learned score. Every node is first transformed by a shared weight matrix W, then a shared attention mechanism a scores each pair:

e_ij = LeakyReLU( aᵀ [ W h_i || W h_j ] )       negative slope 0.2

alpha_ij = exp(e_ij) / Σ  exp(e_ik)            for k ∈ N(i)
                       k

h_i' = sigma( Σ  alpha_ij · W h_j )
               j ∈ N(i)

Three details in there decide the behaviour. The concatenation [W h_i || W h_j] means the score depends on both endpoints, not just the neighbour — the same neighbour gets different attention from different nodes. The softmax runs only over N(i), the neighbours of i, which is what keeps the layer sparse: no score is ever computed for a non-adjacent pair, so this is nothing like the all-pairs attention in a transformer. And N(i) includes i itself, via self-loops added to the graph, so a node can attend to its own features and is not forced to overwrite itself with its neighbourhood.

One node’s neighbourhood, computed

Take node 1 with self-loop, so N(1) = {1, 2, 3, 4}. Suppose the learned vector a dotted with each concatenated pair produces these raw scores:

raw score  aᵀ[Wh_1 || Wh_j]
  j = 1 (self):   0.4
  j = 2:          1.2
  j = 3:         −0.8
  j = 4:          0.1

LeakyReLU, negative slope 0.2  →  negative inputs are multiplied by 0.2
  e_11 =  0.4
  e_12 =  1.2
  e_13 = −0.8 × 0.2 = −0.16
  e_14 =  0.1

exponentiate
  exp( 0.4 ) = 1.4918
  exp( 1.2 ) = 3.3201
  exp(−0.16) = 0.8521
  exp( 0.1 ) = 1.1052
  sum        = 6.7692

normalise
  alpha_11 = 1.4918 / 6.7692 = 0.220
  alpha_12 = 3.3201 / 6.7692 = 0.490
  alpha_13 = 0.8521 / 6.7692 = 0.126
  alpha_14 = 1.1052 / 6.7692 = 0.163
                                -----
                                0.999

Node 2 receives nearly half the weight and node 3 about an eighth, entirely because of what their features are. Had this been a GCN layer with all four nodes at degree 4, every coefficient would have been 0.25 — flat, and identical on every graph with the same shape.

The negative slope is doing real work here. With a plain ReLU, every negative raw score would clamp to exactly 0 and become indistinguishable: a score of −0.8 and a score of −40 would both exponentiate to 1 and receive identical attention. The 0.2 slope keeps a compressed ordering among the neighbours the mechanism dislikes rather than flattening them together.

Multiple heads, and where they concatenate

One attention head is one set of {W, a} and one opinion about which neighbours matter. GAT runs K of them in parallel with independent parameters, which stabilises training in the same way multi-head attention does in a transformer, and combines them differently depending on the layer:

• Hidden layers concatenate. K heads each producing F' features give a KF'-dimensional output, so each head keeps its own subspace and nothing is averaged away.
• The final layer averages, then applies the nonlinearity. Concatenating at the output would multiply the number of classes by K, so the heads are averaged and the softmax or sigmoid is applied after.

The paper’s configurations are worth quoting because they show how modest this is in practice: on the citation benchmarks, a first layer of K = 8 heads computing 8 features each (64 total), then a single output layer. On the larger inductive protein-interaction task, two layers of K = 4 heads at 256 features, then a final layer of 6 heads averaged to produce 121 outputs.

Cost, and what the attention cannot express

The complexity of one head computing F' features from F inputs is O(|V| F F' + |E| F') — a transform per node plus a score per edge. That is linear in the number of edges, so a GAT layer is on the same order as a graph convolution, and the heads parallelise completely. The practical cost is memory rather than arithmetic: you hold a coefficient per edge per head, and on a dense graph with many heads that is the thing that runs out.

The more interesting limit is expressive. How Attentive are Graph Attention Networks? (Brody, Alon and Yahav, ICLR 2022) shows that because a is applied after the concatenation and before the nonlinearity, GAT computes what they call static attention: the ranking of neighbours by attention score is the same for every query node. A node can scale how much it attends overall but cannot reorder its own preferences relative to another node’s. Their GATv2 moves the nonlinearity inside — aᵀ LeakyReLU(W[h_i || h_j]) — which restores dynamic attention at essentially the same cost, and it is available in the main graph libraries as a drop-in alternative.

Attention does not exempt the model from the structural limits that apply to all message passing. A GAT is still bounded by the Weisfeiler-Lehman test discussed on graph classification with GNNs, and it still degrades with depth: learned weights that sum to one across a neighbourhood are still an averaging operation, so stacking layers still pushes representations together — the mechanism covered on GNN oversmoothing. Attention changes which neighbours dominate. It does not change the fact that repeated neighbourhood mixing converges.

One more expressive gap is worth naming because it catches people migrating from a weighted graph. The equation above scores a pair from the two node feature vectors only. There is no term for the edge, so an edge weight, an edge type or an edge feature vector is simply not an input, and a plain GAT layer on a weighted graph silently discards the weights. Architectures that need them add an edge embedding to the concatenation before the attention vector is applied, which most libraries expose as an explicit edge-dimension argument rather than doing by default.

Reading the attention weights

Because the coefficients are per-edge numbers that sum to one, the temptation to present them as an explanation is strong: this node was classified this way because it attended to that neighbour. Be careful with that claim. The argument in Attention is not Explanation (Jain and Wallace, NAACL 2019) is that attention distributions frequently correlate poorly with gradient-based measures of feature importance, and that on many trained models an adversarially different attention distribution can be found that leaves the prediction essentially unchanged. If two distributions produce the same answer, neither of them is the reason for it.

That does not make the weights useless. They are a genuine record of what the layer did, they are cheap to extract, and on a small graph they are a good debugging instrument — a layer whose attention is almost uniform across every neighbourhood has learned nothing a graph convolution would not have given you, and a layer whose attention has collapsed onto self-loops is telling you the neighbourhood carries no usable signal for the task. Both of those are diagnoses worth having. What they are not is an account of why a particular node received a particular label, and presenting them that way to a non-technical audience is a claim the mechanism does not support.