Graph Attention Networks: Learning on Graphs

An account on a UPI-style payments network sends and receives money from a handful of other accounts. Say account A has exactly four neighbours in the transaction graph: itself (through a self-loop, a standard GNN convention so a node never forgets its own features), a merchant it pays every week, a peer with a near-identical spending pattern, and one account that was flagged last month for cycling small amounts through a chain of wallets before cashing out — a classic mule-account signature. A fraud-detection model built on this graph has to decide, for account A, how much of each neighbour's information to fold into A's own representation before deciding whether A itself looks suspicious.

A plain Graph Convolutional Network (GCN) answers that question with arithmetic that never looks at the neighbours' actual behaviour: it normalises by degree — how many edges a node has — and nothing else. If A has four neighbours, each one contributes a fixed share of roughly a quarter of the aggregated signal, whether that neighbour is a boring, reliable merchant or the flagged mule account. GraphSAGE's mean aggregator is even blunter: literally one-fourth each, full stop. The single most informative edge in the whole neighbourhood — the one connecting A to a known bad actor — gets diluted down to the same weight as the least informative one. This is the precise gap Graph Attention Networks (GAT), introduced by Veličković et al. in 2018, were built to close: instead of a structural weight fixed by degree, GAT computes a content-dependent weight, learned from the node features themselves, for every edge in the graph.

From message passing to a fixed aggregation rule

Every GNN layer, regardless of flavour, follows the same message-passing template. Node i holds a feature vector h_i ∈ ℝ^F. A layer produces an updated vector h_i′ ∈ ℝ^F′ by combining h_i with the features of i's neighbourhood N(i):

h_i' = σ( Σ_{j ∈ N(i)} w_ij · W h_j )

where W ∈ ℝ^F′×F is a learned linear map shared across every node, and σ is a nonlinearity (typically ELU or LeakyReLU in GAT). Everything about a GNN architecture reduces to one design choice: how is w_ij, the weight given to neighbour j when updating node i, determined?

GCN sets w_ij = 1/√(deg(i)·deg(j)), a symmetric normalisation computed once from the adjacency matrix before any training happens. GraphSAGE-mean sets w_ij = 1/|N(i)|, an unweighted average. Both are functions of graph topology alone — they are fixed the moment the graph is built, and stay fixed regardless of what the node features say. GAT instead makes w_ij a function of the features of i and j, learned jointly with W during training. That single change is the entire idea.

The attention mechanism, term by term

GAT computes an unnormalised attention score for every edge (i, j) where j ∈ N(i):

e_ij = LeakyReLU( a^T [ W h_i ‖ W h_j ] )

Here W h_i and W h_j are both projected into the F′-dimensional output space first, then concatenated (‖) into a single 2F′-length vector. A single learned attention vector a ∈ ℝ^2F′ reduces that concatenation to one scalar, and LeakyReLU (negative slope 0.2 in the original paper) is applied to it. In practice, a is split into two halves — a_src ∈ ℝ^F′ acting on Wh_i and a_dst ∈ ℝ^F′ acting on Wh_j — because a^T[Wh_i ‖ Wh_j] is algebraically identical to (a_src·Wh_i) + (a_dst·Wh_j), and the split form is what every real implementation computes, since it turns an O(|V|²) all-pairs concatenation into two O(|V|) projections added pairwise only across existing edges.

The raw score e_ij is not yet a usable weight — it is unbounded and not comparable across nodes with different neighbourhood sizes. GAT normalises it with softmax, but critically, only over i's actual neighbours, never over every node in the graph:

α_ij = softmax_j(e_ij) = exp(e_ij) / Σ_{k ∈ N(i)} exp(e_ik)

The α_ij values now sum to 1 across N(i) and become the w_ij in the message-passing template: h_i′ = σ(Σ_j∈N(i) α_ij W h_j). Every step here — the linear map, the score, the mask, the softmax, the weighted sum — is differentiable, so a and W are trained end to end by backpropagating the downstream loss (fraud / not-fraud, node classification, whatever the task is) straight through the attention weights.

Common misconception

Students who have just finished a Transformer chapter often assume GAT is "a Transformer dropped onto a graph," meaning full attention computed over every pair of nodes, with the graph edges used only as an afterthought or a soft bias. That is backwards. GAT's softmax in the equation above runs strictly over N(i) — the neighbours i is actually connected to — never over all |V| nodes. The adjacency structure is not a suggestion GAT can override; it is a hard mask applied before the softmax, via e_ik = −∞ for every k that is not a real neighbour of i, which forces α_ik = 0 for every non-edge. This is precisely why GAT costs O(|V|·F·F′ + |E|·F′) — linear in the number of edges — rather than the O(|V|²·F′) a dense Transformer encoder would pay if it treated the same node set as fully connected. A sparse citation graph with 3 million papers and an average of 10 references each is completely tractable for GAT; the same 3 million tokens as a dense Transformer attention matrix would need to score 9×10¹² pairs. GAT keeps the graph's actual topology as a hard structural prior and only learns how to weight it — it does not discover the graph from scratch the way self-attention discovers relevance between arbitrary tokens.

Multi-head attention

A single attention head can specialise on only one notion of "relevance" — a is one vector, so e_ij is one scalar function of the concatenated features. Real GAT layers run K independent heads in parallel, each with its own W^(k) and a^(k), producing K separate weighted aggregates for every node. In hidden layers these are concatenated:

h_i' = ‖_{k=1}^{K} σ( Σ_{j∈N(i)} α_ij^(k) W^(k) h_j )

so the output dimension is K·F′. In the final layer, concatenation would keep inflating the dimension every layer, so GAT averages the heads instead of concatenating them: h_i′ = σ((1/K) Σ_k Σ_j α_ij^(k) W^(k) h_j). In the fraud-graph setting, one head might learn to key on transaction-amount similarity, another on account-age or frequency patterns — each head is free to build a different notion of "which neighbour matters," and concatenation lets the next layer combine all of those notions rather than forcing one head to represent everything. This also stabilises training: a single softmax over a small neighbourhood is a high-variance estimator early in training, and averaging several independently-initialised heads reduces that variance, the same reason ensembles generalise better than one model.

Worked example: scoring account A's neighbourhood

Take the four-node situation from the opening: node 0 is account A under review, node 1 is a legitimate merchant with a similar transaction profile, node 2 is the flagged mule account, node 3 is a legitimate peer, and node 0 has a self-loop so N(0) = {0, 1, 2, 3}. Each node carries a 2-dimensional feature vector (say, [normalised transaction frequency, normalised amount volatility]):

h0 = [1.00, 0.20]   # account under review
h1 = [0.90, 0.30]   # legit merchant, similar profile
h2 = [0.10, 0.90]   # flagged mule account, divergent profile
h3 = [0.95, 0.25]   # legit peer, similar profile

To isolate the attention mechanism from the linear projection, fix W to the 2×2 identity for this example (in a trained network W would itself be learned, so Wh_i = h_i here only as a simplification, not a general property of GAT). Fix the split attention vector to a_src = [0.4, −0.9] and a_dst = [−0.3, 0.9] — arbitrary but fixed values, exactly as they would be at some point during training. Step 1, compute the source term s₀ = a_src·Wh₀ = 0.4(1.00) + (−0.9)(0.20) = 0.40 − 0.18 = 0.22. Step 2, compute the destination term d_j = a_dst·Wh_j for each neighbour:

d0 = -0.3(1.00) + 0.9(0.20) = -0.30 + 0.18 = -0.12
d1 = -0.3(0.90) + 0.9(0.30) = -0.27 + 0.27 =  0.00
d2 = -0.3(0.10) + 0.9(0.90) = -0.03 + 0.81 =  0.78
d3 = -0.3(0.95) + 0.9(0.25) = -0.285 + 0.225 = -0.06

Step 3, add and apply LeakyReLU (e_0j = s₀ + d_j; all four values below come out positive, so LeakyReLU passes them through unchanged — had any been negative, say −0.05, LeakyReLU with the standard 0.2 slope would have rescaled it to −0.05 × 0.2 = −0.01):

e00 = 0.22 + (-0.12) = 0.10
e01 = 0.22 +   0.00  = 0.22
e02 = 0.22 +   0.78  = 1.00
e03 = 0.22 + (-0.06) = 0.16

Step 4, exponentiate and normalise with softmax over N(0):

exp(0.10)=1.1052  exp(0.22)=1.2461  exp(1.00)=2.7183  exp(0.16)=1.1735
Z = 1.1052+1.2461+2.7183+1.1735 = 6.2430

α00 = 1.1052/6.2430 = 0.1770
α01 = 1.2461/6.2430 = 0.1996
α02 = 2.7183/6.2430 = 0.4354
α03 = 1.1735/6.2430 = 0.1880   (sum = 1.0000 ✓)

The mule account, node 2, receives α₀₂ = 0.4354 — nearly 44% of the total attention mass, despite being exactly one of four neighbours. A uniform GCN/GraphSAGE aggregator would have handed it the same 0.25 as everyone else. Step 5, form the weighted sum: h₀′ = 0.1770·[1.00,0.20] + 0.1996·[0.90,0.30] + 0.4354·[0.10,0.90] + 0.1880·[0.95,0.25] = [0.5788, 0.5341]. Compare this against what a plain mean aggregator would have produced on the identical features: [1.00+0.90+0.10+0.95, 0.20+0.30+0.90+0.25]/4 = [0.7375, 0.4125]. The GAT output sits noticeably further from the "typical account" region and closer to the mule account's own feature vector — its frequency component is 0.16 lower and its volatility component is 0.12 higher than the uniform average produces. That shift is exactly the signal a downstream fraud classifier needs: GAT let the one suspicious edge pull account A's representation toward the fraud-like region instead of averaging that signal away across three boring neighbours.

A verified single-head GAT layer

The following PyTorch layer reproduces the worked example exactly — it was executed to confirm the printed values before being placed in this chapter, so you can trust every number without re-deriving it by hand.

import torch
import torch.nn as nn
import torch.nn.functional as F

class GATLayer(nn.Module):
    def __init__(self, in_f, out_f):
        super().__init__()
        self.W = nn.Linear(in_f, out_f, bias=False)
        self.a_src = nn.Linear(out_f, 1, bias=False)
        self.a_dst = nn.Linear(out_f, 1, bias=False)
        self.leaky = nn.LeakyReLU(0.2)

    def forward(self, h, adj):
        Wh = self.W(h)                     # (N, out_f)
        s = self.a_src(Wh)                 # (N, 1)  -- a_src . Wh_i, one per node
        d = self.a_dst(Wh)                 # (N, 1)  -- a_dst . Wh_j, one per node
        e = self.leaky(s + d.T)            # (N, N)  -- e[i,j] = s_i + d_j
        e_masked = e.masked_fill(adj == 0, float("-inf"))
        alpha = F.softmax(e_masked, dim=1) # row i normalised over N(i) only
        return alpha @ Wh, alpha

h = torch.tensor([[1.00, 0.20],
                   [0.90, 0.30],
                   [0.10, 0.90],
                   [0.95, 0.25]])
adj = torch.ones(4, 4)   # this toy graph is fully connected + self-loops

layer = GATLayer(2, 2)
with torch.no_grad():
    layer.W.weight.copy_(torch.eye(2))
    layer.a_src.weight.copy_(torch.tensor([[0.4, -0.9]]))
    layer.a_dst.weight.copy_(torch.tensor([[-0.3, 0.9]]))

h_prime, alpha = layer(h, adj)
print(alpha[0])   # tensor([0.1770, 0.1996, 0.4354, 0.1880])
print(h_prime[0]) # tensor([0.5788, 0.5341])

Two implementation details matter beyond the mechanism itself. First, e.masked_fill(adj == 0, float("-inf")) is what turns a dense (N, N) score matrix into a graph-respecting one — set the score for every non-edge to −∞ before the softmax, and exp(−∞) = 0, so non-neighbours receive exactly zero attention no matter what their features say. Second, this dense-adjacency form is only practical for small graphs (or a batch of small graphs, e.g. one molecule at a time); production GAT implementations (PyTorch Geometric's GATConv, DGL's GATConv) index directly by edge list and never materialise the full N×N matrix, which is what keeps the real complexity at O(|E|) rather than O(|V|²).

How the pieces fit together

Active recall

Attempt every question before reading the answer beneath it.

1. Why does GAT mask attention scores by the adjacency matrix instead of computing attention over every pair of nodes, the way a Transformer encoder computes attention over every pair of tokens?

2. In the worked example, the flagged mule account (node 2) received α₀₂ = 0.4354 even though it is only one of four neighbours in N(0). Why did the mechanism assign it more than the uniform 0.25 share, and what effect did that have on account 0's updated embedding compared to a plain mean aggregator?

3. Given a_src = [0.4, −0.9], a_dst = [−0.3, 0.9], Wh_i = [0.5, 0.5], and Wh_j = [0.2, 0.8], compute the raw (pre-LeakyReLU) attention score e_ij.

4. Why do GAT layers typically concatenate the outputs of multiple attention heads in hidden layers but average them in the final output layer?

5. State the time complexity of a single GAT layer in terms of |V|, |E|, F, and F′, and explain in one sentence why that is cheaper than treating the same |V| nodes as a fully-connected Transformer.

6. A graph contains an isolated node with no edges and no self-loop added. What breaks in GAT's softmax step for that node, and what is the standard fix?

Answers

1. The graph's edges already encode a strong prior about which relationships are real and meaningful — an account's transaction history genuinely only involves the accounts it has actually transacted with. Masking every non-edge score to −∞ before the softmax (so its post-softmax weight is exactly 0) preserves that structural prior exactly, while still letting the model learn how much each real edge should matter. Removing the mask would let the model "attend" to unconnected nodes it has no factual relationship with, discard the graph structure, and blow the cost up from O(|E|) to O(|V|²).

2. The attention score e₀₂ = 1.00 was the largest of the four raw scores because node 2's projected features (via the fixed a_src/a_dst vectors in this example) produced the largest destination term d₂ = 0.78 — a direct function of node 2's divergent feature values [0.10, 0.90]. After softmax, that translated into α₀₂ = 0.4354, nearly 1.74× the uniform 0.25 a GCN or GraphSAGE-mean aggregator would have assigned. The resulting h₀′ = [0.5788, 0.5341] sits noticeably closer to node 2's own feature vector than the uniform-mean output [0.7375, 0.4125] does — the suspicious neighbour's signal dominated account 0's updated representation instead of being diluted across the boring neighbours, which is exactly the behaviour a fraud classifier downstream benefits from.

3. s = (0.4)(0.5) + (−0.9)(0.5) = 0.20 − 0.45 = −0.25. d = (−0.3)(0.2) + (0.9)(0.8) = −0.06 + 0.72 = 0.66. e_ij = s + d = −0.25 + 0.66 = 0.41. Since 0.41 > 0, LeakyReLU leaves it unchanged, so the final score is also 0.41.

4. Concatenation in hidden layers preserves each head's independent "view" of the neighbourhood — one head might weight by feature similarity, another by a different combination of dimensions — and passes all of those views forward undiminished for the next layer to combine. If the final layer also concatenated, the output dimension would keep multiplying by K every layer and no longer correspond to a fixed embedding size or a fixed number of output classes. Averaging in the final layer collapses the K heads back into one F′-dimensional vector (or one score per class), while still benefiting from the variance reduction of having trained K independent estimators.

5. A single GAT layer costs O(|V|·F·F′ + |E|·F′): the first term is projecting every node's features through W once, the second is computing and normalising one attention score per directed edge. This is linear in the number of edges. A dense Transformer self-attention layer over the same |V| nodes with no graph structure would need to score every pair, costing O(|V|²·F′) — quadratic in the node count, and for a large sparse graph (|E| ≪ |V|²) that is dramatically more expensive.

6. With no edges and no self-loop, N(i) is empty, so the softmax denominator Σ_k∈N(i) exp(e_ik) sums over an empty set and is 0 — division by zero, . The standard fix, used in essentially every GAT implementation, is to always add a self-loop to every node before running the layer, guaranteeing N(i) contains at least i itself, so the node's own projected features become its output when it truly has no neighbours.

Think About It

Think about this: How would you explain graph attention networks: learning on graphs to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind graph attention networks: learning on graphs, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.