31:Te2e,function get_params_statement(tag){ if(tag == 'gcn'){ return md`For each step ${tex`k`}, the function ${tex`${param_col} f^{(k)}`}, matrices ${tex`${param_col} W^{(k)}`} and ${tex`${param_col} B^{(k)}`} are shared across all nodes. This allows the GCN model to scale well, because the number of parameters in the model is not tied to the size of the graph. The variant we discuss here is the 2-parameter model from the original paper , which is more expressive. We also consider the following normalization (iteration subscripts omitted): ${tex.block` {${param_col} f}\left({${param_col} W} \cdot \sum_{u \in \mathcal{N}(v)} \frac{${neigh_col} h_u}{|\mathcal{N}(v)|} + {${param_col} B} \cdot {${main_col} h_v} \right)` } instead of the normalization defined in the original paper: ${tex.block` {${param_col} f}\left({${param_col} W} \cdot \sum_{u \in \mathcal{N}(v)} \frac{${neigh_col} h_u}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}} + {${param_col} B} \cdot {${main_col} h_v} \right)` } for ease of exposition. ` } else if(tag == 'gat'){ return md`For each step ${tex`k`}, the function ${tex`${param_col} f^{(k)}`}, matrices ${tex`${param_col} W^{(k)}`} and attention mechanism ${tex`${param_col} A^{(k)}`} (generally, another neural network) are shared across all nodes. This allows the GAT model to scale well, because the number of parameters in the model is not tied to the size of the graph. Here, we discuss the GAT variant with single-headed attention only. The multi-headed attention variant is similar. We are also free to choose any attention mechanism above: our choice below is intended to keep equations simple. ` } else if(tag == 'graphsage'){ return md`For each step ${tex`k`}, the function ${tex`${param_col} f^{(k)}`}, ${tex`${param_col} \text{AGG}`} and matrix ${tex`${param_col} W^{(k)}`} are shared across all nodes. This allows the GraphSAGE model to scale well, because the number of parameters in the model is not tied to the size of the graph. The original GraphSAGE paper considers the following choices for ${tex`\underset{{u \in \mathcal{N}(v)}}{${param_col} \text{AGG}}(\{ {${neigh_col} h_u^{(k - 1)}} \})`}: * Mean (similar to the GCN): ${tex.block` {${param_col} W_{\text{pool}}^{(k)}} \cdot \frac{{${main_col} h_v^{(k - 1)}} + \sum\limits_{u \in \mathcal{N}(v)} {${neigh_col} h_u^{(k - 1)}}}{1 + |\mathcal{N}(v)|}` } * Dimension-wise Maximum: ${tex.block` \max\limits_{u \in \mathcal{N}(v)} \{ σ({${param_col} W_{\text{pool}}^{(k)}} {${neigh_col} h_u^{(k - 1)}} + {${param_col} b}) \}` } * LSTM (after ordering the sequence of neighbours). Here, we will consider an RNN aggregator, since it's easier to explain than the LSTM aggregator but is built on the same ideas. Further, the original GraphSAGE paper performs 'neighbourhood sampling': irrespective of how large the actual neighbourhood around a node is, a fixed-size random sample of the neighbourhood is taken. This increases the variance in the computed embeddings, but allows GraphSAGE to be used on very large graphs. In our visualizations below, we will sample the entire neighbourhood, since we work on small graphs. ` } else if(tag == 'gin'){ return md`For each step ${tex`k`}, the function ${tex`${param_col} f^{(k)}`} and real-valued parameter ${tex`${param_col} \epsilon^{(k)}`} are shared across all nodes. This allows the GIN model to scale well, because the number of parameters in the model is not tied to the size of the graph. ` } else { return 'parameters'; } }32:T938,gcn_figure = html`

${tex.block`${main_col} h_v^{(0)}`} ${tex.block`=`} ${tex.block`x_v`}

Node ${tex`v`}'s initial embedding.

... is just node ${tex`v`}'s original features.

for all ${tex`v \in V.`}

and for ${tex`k = 1, 2, \ldots `} upto ${tex` K`}:

${tex.block`${main_col} h_v^{(k)}`} ${tex.block`=`} ${tex.block`{${param_col} f^{(k)}}\left({${param_col} W^{(k)}} \cdot \frac{\sum\limits_{u \in \mathcal{N}(v)} {${neigh_col} h_u^{(k - 1)}}}{|\mathcal{N}(v)|} + {${param_col} B^{(k)}} \cdot {${main_col} h_v^{(k - 1)}}\right)`}

Node ${tex`v`}'s embedding at step ${tex`k`}.

Mean of ${tex`v`}'s neighbour's embeddings at step ${tex`k - 1`}.

Node ${tex`v`}'s embedding at step ${tex`k - 1`}.

for all ${tex`v \in V.`}

Color Codes:

Embedding of node ${tex`v`}.
Embedding of a neighbour of node ${tex`v`}.
(Potentially) Learnable parameters.

`33:Tcc0,gat_figure = html`

${tex.block`${main_col} h_v^{(0)}`} ${tex.block`=`} ${tex.block`x_v`}

Node ${tex`v`}'s initial embedding.

... is just node ${tex`v`}'s original features.

for all ${tex`v \in V.`}

and for ${tex`k = 1, 2, \ldots `} upto ${tex` K`}:

${tex.block`${main_col} h_v^{(k)}`} ${tex.block`=`} ${tex.block`{${param_col} f^{(k)}}\left({${param_col} W^{(k)}} \cdot \left[\sum\limits_{u \in \mathcal{N}(v)} \alpha_{vu}^{(k - 1)} {${neigh_col} h_u^{(k - 1)}} + \alpha_{vv}^{(k - 1)} {${main_col} h_v^{(k - 1)}}\right]\right)`}

Node ${tex`v`}'s embedding at step ${tex`k`}.

Weighted mean of ${tex`v`}'s neighbour's embeddings at step ${tex`k - 1`}.

Node ${tex`v`}'s embedding at step ${tex`k - 1`}.

for all ${tex`v \in V.`}

where the attention weights ${tex`\alpha^{(k)}`} are generated by an attention mechanism ${tex`{${param_col} A^{(k)}}`}, normalized such that the sum over all neighbours of each node ${tex`v`} is ${tex`1`}:

${tex.block`\alpha_{vu}^{(k)}`} ${tex.block`=`} ${tex.block`\frac{{${param_col} A^{(k)}}({${main_col} h_v^{(k)}}, {${neigh_col} h_u^{(k)}})}{\sum\limits_{w \in \mathcal{N}(v)}{${param_col} A^{(k)}}({${main_col} h_v^{(k)}}, {${neigh_col} h_w^{(k)}})}`}

for all ${tex`(v, u) \in E.`}

Color Codes:

Embedding of node ${tex`v`}.
Embedding of a neighbour of node ${tex`v`}.
(Potentially) Learnable parameters.

`34:T9ca,graphsage_figure = html`

${tex.block`${main_col} h_v^{(0)}`} ${tex.block`=`} ${tex.block`x_v`}

Node ${tex`v`}'s initial embedding.

... is just node ${tex`v`}'s original features.

for all ${tex`v \in V.`}

and for ${tex`k = 1, 2, \ldots `} upto ${tex` K`}:

${tex.block`${main_col} h_v^{(k)}`} ${tex.block`=`} ${tex.block`{${param_col} f^{(k)}}\left({${param_col} W^{(k)}} \cdot \left[\underset{{u \in \mathcal{N}(v)}}{${param_col} \text{AGG}}(\{ {${neigh_col} h_u^{(k - 1)}} \}), \ {${main_col} h_v^{(k - 1)}}\right]\right)`}

Node ${tex`v`}'s embedding at step ${tex`k`}.

Aggregation of ${tex`v`}'s neighbour's embeddings at step ${tex`k - 1`} ...

... concatenated with ...

... Node ${tex`v`}'s embedding at step ${tex`k - 1`}.

for all ${tex`v \in V.`}

Color Codes:

Embedding of node ${tex`v`}.
Embedding of a neighbour of node ${tex`v`}.
(Potentially) Learnable parameters.

`35:T90f,gin_figure = html`

${tex.block`${main_col} h_v^{(0)}`} ${tex.block`=`} ${tex.block`x_v`}

Node ${tex`v`}'s initial embedding.

... is just node ${tex`v`}'s original features.

for all ${tex`v \in V.`}

and for ${tex`k = 1, 2, \ldots `} upto ${tex` K`}:

${tex.block`${main_col} h_v^{(k)}`} ${tex.block`=`} ${tex.block`{${param_col} f^{(k)}}\left(\sum\limits_{u \in \mathcal{N}(v)} {${neigh_col} h_u^{(k - 1)}} + (1 + {${param_col} \epsilon^{(k)}}) \cdot {${main_col} h_v^{(k - 1)}}\right)`}

Node ${tex`v`}'s embedding at step ${tex`k`}.

Sum of ${tex`v`}'s neighbour's embeddings at step ${tex`k - 1`}.

Node ${tex`v`}'s embedding at step ${tex`k - 1`}.

for all ${tex`v \in V.`}

Color Codes:

Embedding of node ${tex`v`}.
Embedding of a neighbour of node ${tex`v`}.
(Potentially) Learnable parameters.

`36:T5ac,style = html` `37:[] 2f:{"title":"Interactive GNN Equations","cells":[{"id":0,"value":"md`# Interactive GNN Equations`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"fig_div = html`\n ${fig}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":377,"value":"text_div = html`\n ${final_predictions_statement}\n ${get_params_statement(selected_model.tag)}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"fig = html`\n

\n ${eqn_list}\n ${gcn_figure}\n ${gat_figure}\n ${gin_figure}\n ${graphsage_figure}\n\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":349,"value":"eqn_list = html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"interactive_list = {\n d3.select(fig).style('height', get_figure_height(d3.select(fig).attr('data-show')));\n d3.select(eqn_list)\n .selectAll('li')\n .data(gnn_models)\n .join(\n enter => enter.append('li')\n .text(d => d.descr)\n .classed('selected', (d) => (d.tag == d3.select(fig).attr('data-show')))\n .on('click', handle_click),\n update => update,\n exit => exit.remove(),\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"function select_fig(tag){\n mutable selected_model = gnn_models.find((model) => (model.tag == tag));\n d3.select(fig).attr('data-show', tag);\n d3.select(fig).style('height', get_figure_height(tag));\n d3.select(fig).selectAll('li').classed('selected', (d) => (d ? d.tag == tag : false));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":59,"value":"function handle_click(event, d) {\n select_fig(d.tag);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":33,"value":"gnn_models = [\n {'descr': 'GCN', 'tag': 'gcn'},\n {'descr': 'GAT', 'tag': 'gat'},\n {'descr': 'GraphSAGE', 'tag': 'graphsage'},\n {'descr': 'GIN', 'tag': 'gin'}\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":268,"value":"mutable selected_model = gnn_models.find((model) => model.tag == d3.select(fig).attr('data-show'))","pinned":true,"hidden":false,"mode":"ojs"},{"id":508,"value":"function get_figure_height(tag) {\n if(tag == 'gcn'){\n return '510px';\n }\n else if(tag == 'gat'){\n return '710px';\n }\n else if(tag == 'graphsage'){\n return '540px';\n }\n else if(tag == 'gin'){\n return '510px';\n }\n else {\n return '510px';\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":371,"value":"final_predictions_statement = md`\nPredictions can be made at each node by using the final computed embedding:\n${tex.block`\n\\hat{y_v} = \\text{PREDICT}({${main_col}h_v^{(K)}})\n`}\nwhere ${tex`\\text{PREDICT}`} is generally another neural network, learnt together with the ${selected_model.descr} model.\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":274,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":271,"value":"weights_statement = md`This allows the ${selected_model.descr} model to scale well, because the number of parameters in the model is not tied to the size of the graph.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":45,"value":"md`## Figures`","pinned":true,"hidden":false,"mode":"ojs"},{"id":90,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":152,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":154,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"md`# Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"import {param_col_rgb, param_col, main_col_rgb, main_col, neigh_col_rgb, neigh_col} from \"@ameyasd/gnn-styles\";","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"d3 = require('d3@6')","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}