graph attention model

[[concept]]

Graph Attention (GAT)

$(x_{\ell }{)}_i=\sigma \left({\sum }_{j\in N(i)}{\alpha }_{ij}(x_{\ell -1}{)}_j{H}_{\ell }\right)$ Where the ${\alpha }_{ij}$ are the ==learned== graph attention coefficients, computed as

e_{ij} = \frac{\rho(\vec{a}(x_{i}H' \lvert \rvert x_{j} H'))}{\sum_{j' \in N(i)} \rho(\vec{a} (x_{i}H' \lvert \rvert x_{j'}H' ))}$$ Here, we are learning the [[Concept Wiki/graph]] [[Concept Wiki/unweighted graph\|weight matrix]] $E$ via learning $H'$. 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\lvert \rvert\cdot)$ is the row-wise concatenation operation. - so $\vec{a} \in \mathbb{R}^{1 \times 2d}$ - and each $x_{i}H' \in \mathbb{R}^d$ - $\rho$ is a pointwise nonlinearity, typically [[Concept Wiki/leaky ReLU]] The learnable parameters for this model are $\vec{a}, H_{\ell}, H'$ for $1 \leq \ell \leq L$. ^definition

Notes

• 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

Note

We can think of the GAT layer $(x_{\ell }{)}_i=\sigma \left({\sum }_{j\in N(i)}{\alpha }_{ij}(x_{\ell -1}{)}_j{H}_{\ell }\right)$ 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)

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source