Graph Attention Layer with Masked Softmax

MediumML Coding

Problem statement

Learn How Much to Listen to Each Neighbor

A graph attention layer weights each neighbour by a learned score instead of by degree. Implement the score, the neighbourhood-restricted softmax and the multi-head layer, following Velickovic et al.

leaky_relu(x, slope=0.2)

attention_logits(H, a_src, a_dst, slope=0.2)

  • H is (n, d') (already transformed features), a_src and a_dst are (d',) vectors. Return the (n, n) matrix with entry (i, j) equal to leaky_relu(H[i] @ a_src + H[j] @ a_dst), the raw score of node i attending to node j.

masked_softmax(E, mask)

  • mask is a boolean (n, n) matrix. Return the matrix whose row i is the softmax of E[i] restricted to the entries where mask[i] is true, with zeros elsewhere. Subtract the row's masked maximum before exponentiating for stability. Every row of mask has at least one true entry.

gat_layer(A, X, W, a_src, a_dst, slope=0.2)

  • Transform H = X @ W, compute the logits, mask them with A + I > 0 (a node always attends to itself), take the masked softmax to get the attention matrix alpha, and return (alpha, alpha @ H). No activation is applied.

multi_head_gat(A, X, Ws, a_srcs, a_dsts, concat=True, slope=0.2)

  • Run one head per element of the lists. With concat, return the heads' outputs concatenated along the feature axis; otherwise return their mean.

Example

Input:

A = [[0, 1], [1, 0]]; X = [[1, 0], [0, 1]]; W = I; a_src = [1, 0]; a_dst = [0, 1]; gat_layer(...)[0]

Output:

[[0.2689, 0.7311], [0.2689, 0.7311]]

Reasoning: The source term is H @ a_src = (1, 0) and the target term H @ a_dst = (0, 1). Node 0's logits are 1 for itself and 2 for node 1; node 1's are 0 for node 0 and 1 for itself. Both rows softmax to (0.2689, 0.7311).

Show hint

If the attention vector is split into a part applied to the attending node and a part applied to the neighbor, how can you build every pairwise score without looping over pairs?

Relevant roles: ML Engineer, Deep Learning Engineer, Research Scientist and Applied Scientist.

Related free problems