Graph Attention Networks (GAT)

While Graph Convolutional Networks (GCNs) provide a powerful framework for learning on graphs, their aggregation mechanism often treats all neighbors with uniform importance (adjusted only by node degrees). Consider a social network graph where you want to predict a user's interests. Some friends might be much more influential or share more similar interests than others. A standard GCN might struggle to capture these nuances effectively because its convolution kernel weights are fixed based on the graph structure (specifically, the normalized adjacency or Laplacian matrix).

Graph Attention Networks (GATs) introduce a way to overcome this limitation by incorporating self-attention mechanisms, inspired by their success in sequence-based tasks. The central idea is to allow nodes to assign different levels of importance, or attention, to different nodes within their neighborhood during the aggregation process. These attention weights are not fixed; they are computed dynamically based on the features of the interacting nodes.

The Attention Mechanism in GAT

Instead of using pre-defined weights like $1/\sqrt{deg(i)deg(j)}$ found in GCN, GAT computes attention coefficients, denoted as $a_{ij}$, for each edge $(j, i)$ indicating the importance of node $j$'s features to node $i$. This process typically involves three steps within a GAT layer:

1. Linear Transformation: First, the input features $h_i \in \mathbb{R}^F$ for each node $i$ are transformed by a learnable weight matrix $W \in \mathbb{R}^{F' \times F}$, resulting in higher-level features $z_i = W h_i \in \mathbb{R}^{F'}$. This initial transformation increases the model's capacity to learn relevant representations.

2. Attention Coefficient Calculation: For each edge connecting node $j$ to node $i$, an attention score $e_{ij}$ is computed. This score signifies the un-normalized importance of node $j$'s features to node $i$. A common way to compute $e_{ij}$ is using a shared attention mechanism, typically a single-layer feedforward neural network parameterized by a learnable weight vector $a \in \mathbb{R}^{2F'}$. The input to this mechanism is the concatenation of the transformed features of the two nodes, $z_i$ and $z_j$:

   $$e_{ij} = \text{LeakyReLU}(a^T [W h_i || W h_j])$$

   Here, $||$ denotes concatenation, and LeakyReLU is often used as the non-linearity. This mechanism is shared across all edges, meaning the same $a$ and $W$ are used to compute attention scores for all node pairs.

3. Normalization via Softmax: The raw attention scores $e_{ij}$ are not directly comparable across different nodes. To make them comparable and obtain normalized attention coefficients $a_{ij}$, a softmax function is applied across all neighbors $j$ of node $i$ (including the node $i$ itself, usually):

   $$a_{ij} = \text{softmax}_j(e_{ij}) = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}_i \cup \{i\}} \exp(e_{ik})}$$

   where $\mathcal{N}_i$ represents the neighborhood of node $i$. These normalized coefficients $a_{ij}$ now sum to 1 for each node $i$ across all its neighbors $j$, forming a weighted distribution of attention.

4. Weighted Aggregation: Finally, the output features $h'_i \in \mathbb{R}^{F'}$ for node $i$ are computed as a weighted sum of the transformed features of its neighbors, using the normalized attention coefficients $a_{ij}$ as the weights. A non-linear activation function $\sigma$ (like ReLU or ELU) is typically applied afterward:

   $$h'_i = \sigma \left( \sum_{j \in \mathcal{N}_i \cup \{i\}} a_{ij} W h_j \right)$$

This process effectively allows each node to selectively focus on its most relevant neighbors when updating its representation.

A view of the GAT aggregation process for node 'i'. Attention coefficients $a_{ij}$ determine the weight of messages passed from neighbors (including self) to update the node's feature vector $h'_i$.

Advantages of GAT

Graph Attention Networks offer several benefits compared to simpler convolutional approaches:

• Adaptive Receptive Fields: GAT learns to assign importance dynamically. Nodes learn which neighbors to pay more attention to, tailoring the aggregation process based on node features rather than solely on graph structure.
• Implicit Weighting: The attention coefficients $a_{ij}$ are computed implicitly as part of the learning process, eliminating the need for explicit graph structural information like degrees or costly matrix operations (like Laplacian eigen-decomposition) during forward passes.
• Efficiency: Computing attention coefficients involves operations over edges (pairs of nodes), which can be parallelized efficiently, especially on sparse graphs. The computation per layer doesn't directly depend on the total number of nodes in the graph, unlike some spectral methods.
• Inductive Capability: Because the attention mechanism relies on node features and is shared across all nodes, GATs can readily be applied to graphs not seen during training (inductive learning), provided the nodes have features.

While a single GAT layer computes one set of attention weights, this mechanism can be extended. A common practice is to use multi-head attention, where multiple independent attention mechanisms are computed in parallel, and their results are combined. This technique, discussed in the next section, often leads to more stable training and allows the model to capture different types of relationships within the neighborhood simultaneously.