graph attention model

$$(x_{\ell }{)}_i=\sigma (\sum _{j\in N(i)}{\alpha }_{ij}(x_{\ell -1}{)}_j{H}_{\ell })$$

Where the ${\alpha }_{ij}$ are the learned graph attention coefficients, computed as

Here, we are learning the graph weight matrix $E$ via learning $H^{\prime }$. We can think of this as calculating the "relative similarity" between transformed features of $i$ and $j$ vs the similarity of all neighbors of $i$.

• $(\cdot ||\cdot )$ is the row-wise concatenation operation.
  • so $\overrightarrow{a}\in {\mathbb{R}}^{1\times 2d}$
  • and each $x_i{H}^{\prime }\in {\mathbb{R}}^d$
• $\rho$ is a pointwise nonlinearity, typically leaky ReLU

The learnable parameters for this model are $\overrightarrow{a},H_{\ell },H^{\prime }$ for $1\le \ell \le L$.

• This architecture is local because it is still respecting the graph sparsity pattern, and learning the "similarities" of the transformed features at each layer of the network.
• This architecture does not depend on the size of the graph, only the dimension of the features
• It can still be expensive to compute however, if the graph is dense. We need to compute $|E|$ coefficients ${\alpha }_{ij}$, which can be up to $n^2$ in complete graphs.

This additional flexibility increases the capacity of the architecture (less likely to underfit to training data), and this has ben observed empirically. But this comes at the cost of a more expensive forward pass.

This architecture is available and implemented in PyTorch Geometric

We can think of the GAT layer $(x_{\ell }{)}_i=\sigma (\sum _{j\in N(i)}{\alpha }_{ij}(x_{\ell -1}{)}_j{H}_{\ell })$ as a convolutional layer where the GSO $S$, is learned

• however, this architecture is not convolutional since $S$ is changing at each step.
• But it can be useful to see how we can write/think about it as something that looks convolutional (if you squint)