## 3 Preliminaries
### General GNN Framework  
The key idea of GNNs is to transform information at the neighbors and combine it. In Figure 5, we show a typical architecture and the working mechanism of GNN. As can be seen, the aggregate function consists of two steps. The first step is message passing. And the second step is the formal aggregate operation (e.g., mean, pool, and long short-term memory). For a simplest GNN, the message passing function could be a constant and the aggregate operation could be a summary (i.e., we do nothing but simply adding neighboring information together). It is not hard to find that we can improve GNN's performance from at least three aspects: selecting strategy, aggregate function, and stacking multiple layers. For instance, if the importance of neighbors to central node is inconsistent, we can apply attention mechanism at the first step of aggregate function. Now, we can give the general formulation of GNNs:  
\[h_{out}^{(k)}=Update(Aggregate(\{h_{u}^{(k-1)},\forall u\in N(u)\},W_{agg}^{(k )}),h_{in}^{(k)},W_{update}^{(k)}) \tag{1}\]  
where \(h_{in}^{(k)}\) and \(h_{out}^{(k)}\) denote input and updated node embedding at \(k\)-th layer, respectively. \(h_{u}^{(k-1)}\) are neighbors' embeddings from previous layer. \(W_{agg}^{(k)}\) and \(W_{update}^{(k)}\) denote trainable matrices in aggregate function and update function at \(k\)-th layer, respectively. Moreover, \(W_{update}^{(k)}\) usually denotes the \(k\)-th layer's trainable parameters of neural networks after the aggregate function. We show the general architecture of GNN in Figure 5.  
The research of GraphSAGE [21] proposed a general framework for inductive node embedding:  
Figure 4: The encoder–decoder framework. The encoder is a function that maps nodes to low-dimension vectors (i.e., node embeddings). The decoder reconstructs certain graph statistics from the node embeddings that generated by encoder, e.g., predicting \(u\)’s category on node classification task.  
Figure 5: A typical and basic architecture and processing procedures of GNN. First, GNN selects neighbors with a certain strategy. Then, an aggregate function is applied to extract information around the central node. At last, the aggregated information passes through a neural network to be performed nonlinear transformation. The output is updated representation of central node.  
\[h_{v}^{(k)}=\sigma([A_{k}\cdot AGG(\{h_{u}^{(k-1)},\forall u\in N(u)\}),B_{k}h_{v}^ {(k-1)}]) \tag{2}\]  
where \(h_{v}^{(k)}\) and \(h_{v}^{(k-1)}\) denote the representation of node \(v\) at current layer \(k\) and previous layer \((k-1)\), respectively. Moreover, \(h_{u}^{(k-1)}\) indicates the node embeddings of the neighbors from previous layer. \(A_{k}\) and \(B_{k}\) are the trainable weight matrices. \(\sigma\) is a nonlinear activation function. AGG is the aggregator. \(h_{v}^{(k)}\) is generated by the following steps. First, each node aggregates features from its local neighborhood with the AGG aggregator into a single vector \(h_{N(v)}^{(k)}\). After the aggregate of neighbors' features, GraphSAGE concatenates the node's previous representation with its neighborhood feature vector. Then, the concatenated vector is fed through a multi-layer perceptron (MLP) with ReLU activation function, and the output is the new representation of node \(v\) which will be used as the input at next layer.  
Like classic deep learning, for supervised learning (i.e., we are given input \(\mathbf{x}\), and the goal is to predict label \(\mathbf{y}\)), a graph learning task is also formulated as an optimization problem:  
\[\min_{\Theta}\mathcal{L}(\mathbf{y},f(\mathbf{x})) \tag{3}\]  
where \(\Theta\) is a set of parameters we optimize and \(\mathcal{L}\) is a loss function. \(f\) denotes graph neural network function which can be very complex. The output of \(f\) is predictions of nodes. Our goal is to make the loss which measures the gap between predictions and actual labels as lower as possible.