graph SAGE

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

Aggregate

Concatenate

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

where $A$ is the binary adjacency matrix, which is equivalent to a GCN with nodewise normalization $\frac{(x_{\ell }{)}_i}{||(x_{\ell }{)}_i|{|}_2}$. This normalization helps in some cases (empirically).

• 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

$S{x}_{\ell }$ is the "aggregate" and $\sigma (\dots H_{\ell })$ is the "update"