graph SAGE

[[concept]]

Graph SAGE

Introduced by Hamilton-Ying-Leskovee in 2017, each Graph SAGE layer implements the following 2 operations:

Aggregate $(U_{\ell }{)}_i={\text{AGGREGATE}}_{\ell }(\{(x_{\ell }{)}_j,j\in N(i)\})$

Concatenate $(x_{\ell }{)}_i=\sigma (\text{CONCAT}((x_{\ell -1}{)}_i,(U_{\ell }{)}_i))$

The standard $\text{AGGREGATE}$ operation is an average over $N(i)$. Letting $H=[H_0{H}_1{]}^T$, we get

(U_{\ell})_{i} &= \frac{1}{\lvert N(i) \rvert} \sum_{j \in N(i)} (x_{\ell-1})_{j} \\ \implies U_{\ell} &= SX_{\ell-1},\,\,\,\,\,\,\,\, S=D^{-1/2}AD^{-1/2}\\ x_{\ell} = \sigma([x_{\ell-1} \;\; U_{\ell}] H) &= \sigma(x_{\ell-1}H_{0} + SX_{\ell-1}H_{1}) \end{aligned}$$ where $A$ is the binary [[Concept Wiki/adjacency matrix]], which is equivalent to a [[Concept Wiki/graph convolutional network\|GCN]] with nodewise normalization $\frac{(x_{\ell})_{i}}{\lvert \lvert (x_{\ell})_{i} \rvert \rvert_{2}}$. This normalization helps in some cases (empirically).

notes

• SAGE implementations allow for a variety of $\text{AGGREGATE}$ functions, including $\max$ and LSTMs (which look at $N(i)$ as a sequence, losing permutation equivariance). In these cases, SAGE is no longer a graph convolution.
  • There are both advantages and disadvantages of staying a GCN and using other functions.
• the authors of SAGE popularized the $\text{AGGREGATE}=\text{UPDATE}$ representation of GNNs (with $K=2$) meaning

$x_{\ell }=\sigma (S{X}_{\ell -1}{H}_{\ell })$ $S{x}_{\ell }$ is the “aggregate” and $\sigma (\dots H_{\ell })$ is the “update”

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