§ DEEP GRAPH EMBEDDING

In recent years, a great number of deep embedding approaches have been proposed to handle some of the limitations discussed in Section <ref>. It should be emphasized that these deep embedding approaches differ from the shallow embedding approaches explained in Section <ref> in that a much more complex encoder, which is often based on deep neural networks (DNN) <cit.>, is constructed and employed. In this manner, the encoder module would incorporate both the structural and attribute information of the graph. For SSL tasks, a top-level classifier needs to be trained to predict class labels for unlabelled nodes under the transductive setting, based on the node embeddings generated by these deep learning models.
Figure <ref> illustrates the outline of the reviewed approaches in Section <ref>.

Deep graph embedding methods in GSSL.

§.§ AutoEncoder-based methods

Apart from the use of deep learning models, autoencoder-based methods also vary from the shallow embedding methods in that a unary decoder is employed instead of a pairwise one. Under the framework of autoencoder-based methods, every node, ${i}$, is represented by a high-dimensional vector extracted from a row in the similarity matrix, namely, $\mathbf{s}_{i} = {i}^{\text{th}} \text{ row of } \mathbf{S}$, where $\mathbf{S}_{i, j}=s_{\mathcal{G}}\left({i}, {j}\right)$. The autoencoder-based methods aims to first encode each node based on the corresponding vector $\mathbf{s}_{i}$ and then reconstruct it again from the embedding results, subject to the constraint that the reconstructed one should be as close to the original one as possible (Figure <ref>):

\begin{equation}
\label{autoencoder_embedding_goal}
\operatorname{Dec}\left(\operatorname{Enc}\left(\mathbf{s}_{i}\right)\right)=\operatorname{Dec}\left(\mathbf{z}_{i}\right) \approx \mathbf{s}_{i}.
\end{equation}

From the perspective of the loss function for autoencoder-based methods, it commonly keeps the following form:

\begin{equation}
\mathcal{L}=\sum_{{i} \in {V}}\left\|\operatorname{Dec}\left(\mathbf{z}_{i}\right)-\mathbf{s}_{i}\right\|_{2}^{2}.
\end{equation}

For AutoEncoder-based methods, a high-dimensional vector $\mathbf{s}_i$ is extracted and fed into the AutoEncoder for generating a low-dimensional $\mathbf{z}_i$ embedding

From Eq. (<ref>), it should be pointed out that the encoder module actually depends on the given $ \mathbf{s}_{i}$ vector. This allows autoencoder-based deep embedding approaches to incorporate local structural information into the encoder, while it is simply impossible for the shallow embedding approaches to do so. The primary components of these methods are summarized as Table <ref>, and the architectures of them are compared as Figure <ref>.

Summary on the architectures of AutoEncoder-based methods

Summary on AutoEncoder-based Deep Graph Embedding Methods

Similarity measure
Loss function
Time complexity

SDNE <cit.>
$\sum_{{u} \in {V}}\left\|\operatorname{Dec}\left(\mathbf{z}_{u}\right)-\mathbf{s}_{u}\right\|_{2}^{2}$
${O}(|V \| E|)$

DNGR <cit.>
$\sum_{{u} \in {V}}\left\|\operatorname{Dec}\left(\mathbf{z}_{u}\right)-\mathbf{s}_{u}\right\|_{2}^{2}$

S2S-AE <cit.>
$\sum_{{u} \in {V}}\left\|\operatorname{Dec}\left(\mathbf{z}_{u}\right)-\mathbf{s}_{u}\right\|_{2}^{2}$

DRNE <cit.>
$\sum_{{u} \in {V}}\left\|\left(\mathbf{z}_{u}\right)-\sum_{v \in \mathcal{N}(u)} \operatorname{LSTM}\left(\mathbf{z}_{v}\right)\right\|_{2}^{2}$
${O}(|V \| E|)$

GAE <cit.>
$\mathbf{z}_{u}^{\top} \mathbf{z}_{v}$
$\sum_{{u} \in {V}}\left\|\operatorname{Dec}\left(\mathbf{z}_{u}\right)-{A}_{u}\right\|_{2}^{2}$
${O}(|V \| E|)$

VGAE <cit.>
$\mathbf{z}_{u}^{\top} \mathbf{z}_{v}$
$\mathbb{E}_{q(\mathbf{Z} \mid {X}, {A})}[\log p({A} \mid \mathbf{Z})]-\operatorname{KL}[q(\mathbf{Z} \mid {X}, {A}) \| p(\mathbf{Z})]$
${O}(|V \| E|)$

ARGA <cit.>
$\mathbf{z}_{u}^{\top} \mathbf{z}_{v}$
$\min _{\mathcal{G}} \max _{\mathcal{D}} \mathbb{E}_{\mathbf{z} \sim p_{z}}[\log \mathcal{D}(\mathbf{Z})]+\mathbb{E}_{{x} \sim p({x})}[\log (1-\mathcal{D}(\mathcal{G}({X}, {A})))]$
${O}(|V \| E|)$

ARVGA <cit.>
$\mathbf{z}_{u}^{\top} \mathbf{z}_{v}$
$\min _{\mathcal{G}} \max _{\mathcal{D}} \mathbb{E}_{\mathbf{z} \sim p_{z}}[\log \mathcal{D}(\mathbf{Z})]+\mathbb{E}_{{x} \sim p({x})}[\log (1-\mathcal{D}(\mathcal{G}({X}, {A})))]$
${O}(|V \| E|)$

Despite this noticeable enhancement, the autoencoder-based methods may still suffer from some problems. Particularly, the computational cost of it is still intolerable for large scale graphs. Moreover, the structure of the autoencoder is predefined and unchanged during the training, so it is strictly transductive and thus fails to cope with evolving graphs. The up-to-date, relevant representative works to tackle these issues are <cit.> <cit.>.

§.§.§ SDNE

Wang  <cit.> proposes Structural deep network integration (SDNE) with the help of deep autoencoders to preserve the proximity for first and second orders. The first-order proximity describes the similarity between each node pair, while the second-order proximity between each node pair describes the proximity of their neighborhood structure. The method takes advantage of non-linear functions to acquire the embedding results. It actually contains two modules: 1) the unsupervised part and 2) the supervised part. The former is an autoencoder designed to produce an embedding result for each node that can be used to rebuild its corresponding vector $\mathbf{s}_{i}$. For the latter part, Laplacian Eigenmaps is utilized so that penalty is imposed if connected nodes are encoded far away in the embedding space.

§.§.§ DNGR

Deep neural networks for learning graph representations (DNGR) <cit.> integrates random surfing with autoencoders to generate node embeddings. This model has three components: 1) random surfing, 2) estimation of positive pointwise mutual information (PPMI) matrix and 3) stacked denoising autoencoders. For the input graph, random surfing is first applied to produce a co-occurrence probability matrix similar to HOPE. This probabilistic matrix is then converted into a PPMI matrix and fed into a stacked denoising autoencoder to generate the final embedding result. The feedback of the PPMI matrix guarantees the high order proximity is captured and maintained by the autoencoder. Moreover, the introduction of stacked denoising autoencoders enhances the model's robustness when the noise is present and the model's capability to detect the underlying structure required for some downstream tasks like node classification.

§.§.§ S2S-AE

Unlike previous methods whose encoders are all based on MLP, Taheri  <cit.> extend the form of the encoder to RNN models. S2S-AE <cit.> uses long short-term memory (LSTM) <cit.> autoencoders to embed the graph sequences generated from random walks into a continuous vector space. The final representation is computed by averaging its graph sequence representations. The advantage of S2S-AE is that it can support arbitrary-length sequences, unlike others, which often suffer from the limitation of the fixed-length inputs.

§.§.§ DRNE

Deep recursive network embedding (DRNE) <cit.> holds an assumption that the embedding of a node needs to approximate the aggregation of the embeddings of nodes within its neighborhood. It also uses LSTM <cit.> to aggregate a node's neighbors, so the reconstruction loss is different from the one in S2S-AE <cit.> as suggested in Table <ref>. In this way, DRNE can solve the issue that the LSTM model is not invariant when the given nodes' sequence permutes in different ways.

§.§.§ GAE & VGAE

Both MLP-based and RNN-based methods only consider structural information and ignore the nodes' feature information. GAE <cit.> leverages GCN <cit.> to encode both. The encoder takes the form that,

\begin{equation}
\label{vae_enc}
\operatorname{Enc}({A},{X}) = \operatorname{GraphConv}\left(\sigma (\operatorname{GraphConv} ({A},{X}))\right),
\end{equation}

where $\operatorname{GraphConv}(\cdot)$ is a graph convolutional layer defined in <cit.>, $\sigma(\cdot)$ is the activation function, $A$ is the adjacency matrix, and $X$ is the attribute matrix. The decoder of GAE is defined as

\begin{equation}
\label{vae_dec}
\operatorname{Dec}{(\mathbf{z}_{u},\mathbf{z}_{v})} = \mathbf{z}_{u}^T \mathbf{z}_{v}.
\end{equation}

It may have some overfitting issue when the adjacency matrix is reconstructed in a direct way. Variational GAE (VGAE) <cit.> learns the distribution of data, in which the variational lower bound $\mathcal{L}$ is optimized.

\begin{equation}
\label{vgae}
\mathcal{L}=\mathbb{E}_{q(\mathbf{Z} \mid {X}, {A})}[\log p({A} \mid \mathbf{Z})]-\operatorname{KL}[q(\mathbf{Z} \mid {X}, {A}) \| p(\mathbf{Z})],
\end{equation}

where $\operatorname{KL}[q(\cdot) \| p(\cdot)]$ is the Kullback-Leibler divergence between $q(\cdot)$ and $p(\cdot)$. Moreover, we have

\begin{equation}
q(\mathbf{Z} \mid {X}, {A})=\prod_{i=1}^{N} \mathcal{N}\left(\mathbf{z}_{i} \mid {\mu}_{i}, \operatorname{diag}\left({\sigma}_{i}^{2}\right)\right),
\end{equation}

\begin{equation}
p({A} \mid \mathbf{Z})=\prod_{i=1}^{N} A_{ij}\sigma\left(\mathbf{z}_{i}^{\top} \mathbf{z}_{j}\right) + \left(1-A_{ij}\right)\left(1-\sigma\left(\mathbf{z}_{i}^{\top} \mathbf{z}_{j}\right)\right).
\end{equation}

The most recent follow-up work are RWR-GAE <cit.> which adds a random walk regularizer for GAE and achieves noticeable performance improvement and DGVAE <cit.> which combines with graph cluster memberships as latent factors to further improve the internal mechanism of VAEs based graph generation.

§.§.§ ARGA & ARVGA

To further improve the empirical distribution, $q(\mathbf{Z} \mid \mathbf{X}, \mathbf{A})$ in accordance with the prior distribution $p(\mathbf{A} \mid \mathbf{Z})$ in GAE and VGAE, Pan  <cit.> propose ARGA and ARVGA with the help of the generative adversarial networks (GANs) <cit.>, in which they take GAE and VGAE as encoder respectively.

§.§ GNN-based methods

Several up-to-date deep embedding approaches are designed to overcome the shallow embedding approaches' main drawbacks by constructing some specific functions that depend on a node's neighborhood (Figure <ref>). Graph neural network (GNN), which is heavily utilized in state-of-the-art deep embedding approaches, is considered as a general scheme for defining deep neural networks in the graph structure data.

GNN-based methods can generate node embeddings by aggregating embeddings from its neighbors

The main idea is that the representation vectors of nodes can depend not only on the structure of the graph but also on any feature information associated with the nodes. Dissimilar to the previously reviewed methods, graph neural networks use the node features, e.g., node information for a citation network or even simple statistics such as node degree, one-hot vectors, etc., to generate the desired node embeddings.

Like other deep node embedding methods, a classifier is trained on top of the node embeddings generated by the final hidden state in GNN-based models explicitly or implicitly. Afterward, it can be applied to the unlabeled nodes for SSL tasks.

Since GNN consists of two main operations: Aggregate operation and Update operation, these methods will be reviewed from the perspective of the specific operation changed and improved compared with the basic GNN. The main techniques employed in these methods are also listed in Table <ref> and some representative models.

Summary on GNN-based Deep Graph Embedding Methods

Improvement     Technique                         Model
Basic GNN (Baseline)                                 Neural Message Passing             Basic GNN <cit.>
4*Generalized Aggregate Operation     Neighborhood Normalization         GCN <cit.> MixHop <cit.> SGC <cit.> DGN <cit.>

2*Pooling           Set Pooling <cit.>

Janossy pooling <cit.>

Neighborhood Attention             GAT <cit.> AGNN <cit.>
5*Generalized Update Operation        2*Concatenation     Column networks <cit.> Scattering GCN <cit.>

GraphSAGE <cit.> DropEdge <cit.>

2*Gated Updates     GGNN <cit.>

NeuroSAT <cit.>

JK connections                     JK Networks <cit.>  InfoGraph* <cit.>

§.§ Basic GNN

As Gilmer  <cit.> point out, the fundamental feature of a basic GNN is that it takes advantages of neural message passing in which messages are exchanged and updated between each pair of the nodes by using neural networks.

More specifically, during each neural message passing iteration in a basic GNN, a hidden embedding $\mathbf{h}_{u}^{(k)}$ corresponding to each node $u$ is updated according to message or information aggregated from $u$'s neighborhood $\mathcal{N}(u)$. This general message passing update rule can be expressed as follows:

\begin{align}
\label{message_passing_update_rule}
&\mathbf{h}_{u}^{(k+1)} \nonumber \\
&=\texttt{Update}^{(k)}\left(\mathbf{h}_{u}^{(k)}, \texttt{Aggregate}^{(k)}\left(\left\{\mathbf{h}_{v}^{(k)}, \forall v \in \mathcal{N}(u)\right\}\right)\right), \nonumber \\
&=\texttt{Update}^{(k)}\left(\mathbf{h}_{u}^{(k)}, \mathbf{m}_{\mathcal{N}(u)}^{(k)}\right).
\end{align}

It is noteworthy that in Eq. (<ref>), both the operation $\texttt{\textbf{Update}}$ and $\texttt{\textbf{Aggregate}}$ must be differentiable functions, typically, neural networks. Moreover, $\mathbf{m}_{\mathcal{N}(u)}$ is the exact message that is aggregated from node $u$'s neighborhood $\mathcal{N}(u)$ and tends to encode useful local structure information. Combining the message from neighbourhood with the previous hidden embedding state, the new state is generated according to Eq. (<ref>). After a certain preset number of iterative steps, the last hidden embedding state converges so that this final state is regarded as the embedding output for each node. Formally, we have,

\begin{equation}\mathbf{z}_{u}=\mathbf{h}_{u}^{(K)}, \forall u \in \mathcal{V}.\end{equation}

It should be stressed that both the basic GNN and many of its variants strictly follow this generalized framework. The relationship among them is summarized as Table <ref>.

Before the review on some of the GNN-based methods designed for SSL tasks, the basic version of GNN is introduced, which is a simplification of the original GNN model proposed by Scarselli  <cit.>.

The basic GNN message passing is defined as:

\begin{equation}
\label{basic_gnn}\mathbf{h}_{u}^{(k)}=\sigma\left(\mathbf{W}_{\text {self }}^{(k)} \mathbf{h}_{u}^{(k-1)}+\mathbf{W}_{\text {neigh }}^{(k)} \sum_{v \in \mathcal{N}(u)} \mathbf{h}_{v}^{(k-1)}+\mathbf{b}^{(k)}\right),\end{equation}

where $\mathbf{W}_{\text {self }}^{(k)}, \mathbf{W}_{\text {neigh }}^{(k)}$ are trainable parameters and $\sigma$ is the activation function.
The messages from the neighbors are firstly summarized. Then, the neighborhood information is combined together with the node's previous hidden embedding results by using a basic linear combination. Finally, a non-linearity activation function is applied on the combined information. From the perspective of the key components of the GNN framework, the Aggregation operation is and the Update operation is defined as shown in Eq. (<ref>) and Eq. (<ref>).

\begin{equation}
\label{aggregate_gnn}\texttt{Aggregate}^{(k)}\left(\left\{\mathbf{h}_{v}^{(k)}, \forall v \in \mathcal{N}(u)\right\}\right) =\sum_{v \in \mathcal{N}(u)} \mathbf{h}_{v},\end{equation}

\begin{equation}
\label{update_gnn}\texttt{Update}\left(\mathbf{h}_{u}, \mathbf{m}_{\mathcal{N}(u)}\right)=\sigma\left(\mathbf{W}_{\text {self }} \mathbf{h}_{u}+\mathbf{W}_{\text {neigh }} \mathbf{m}_{\mathcal{N}(u)}\right).\end{equation}

Furthermore, it is not uncommon to add some self-loop tricks to the input graph so as to shut out the explicit update step, which can be considered as a straightforward simplification of the neural message passing method used in the basic GNN. To be a little more specific, the message passing process can now be simply defined as shown in Eq. (<ref>).

\begin{equation}
\label{self-loop-gnn}\mathbf{h}_{u}^{(k)}=\texttt{Aggregate}\left(\left\{\mathbf{h}_{v}^{(k-1)}, \forall v \in \mathcal{N}(u) \cup\{u\}\right\}\right).\end{equation}

As mentioned before, GNN models have all kinds of variants, which try to improve its performance and robustness to some extent. However, regardless of the variant of GNN, they all follow the neural message passing framework for Eq. (<ref>) examined earlier. In the following two sections, Section <ref> and <ref>, some representative improvements on the two main components of basic GNN, aggregation operation and update operation, are reviewed in detail.

§.§ Generalized aggregation operation

In general, the Aggregation operation in GNN models has received the most attention from the literature as a large number of researchers have proposed novel architectures or variations based on the original GNN model.

§.§.§ Neighborhood normalization

As previously stated, the most basic neighborhood aggregation operation, shown in Eq. (<ref>), solely computes the sum of the neighborhood's embedding states. The main problem with this approach is that it could be unstable and susceptible to the node's degree since nodes with a large degree tend to receive a large total value from more neighbors than those with fewer neighbors.

One typical and simple solution to this issue is to just normalize the aggregation operation based on the degree of the central nodes. The simplest approach is to just take an average rather than the sum by Eq. (<ref>)

\begin{equation}
\label{neighbor_norm_basic}\mathbf{m}_{\mathcal{N}(u)}=\frac{\sum_{v \in \mathcal{N}(u)} \mathbf{h}_{v}}{|\mathcal{N}(u)|},\end{equation}

but methods with other normalization factors with similar ideas were proposed and achieved remarkable performance gain, such as the following symmetric normalization employed by Kipf  <cit.> in the GCN model as shown in Eq. (<ref>).

\begin{equation}
\label{gcn_neighbor_norm}
\mathbf{m}_{\mathcal{N}(u)}=\sum_{v \in \mathcal{N}(u)} \frac{\mathbf{h}_{v}}{\sqrt{|\mathcal{N}(u)| \mid \mathcal{N}(v)\mid}}.\end{equation}

Graph convolutional networks (GCNs).
One of the most popular and effective baseline GNN variants is the graph convolutional network (GCN) <cit.>, which is inspired by <cit.> and <cit.>. GCN makes full use of the neighborhood normalized aggregation techniques as well as the self-loop update operation. Therefore, the GCN model defines the update operation function as shown in Eq. (<ref>). No aggregation operation is defined since it has been implicitly defined within the update operation function as

\begin{equation}
\label{GCN}
\mathbf{h}_{u}^{(k)}=\sigma\left(\mathbf{W}^{(k)} \sum_{v \in \mathcal{N}(u) \cup\{u\}} \frac{\mathbf{h}_{v}}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}}\right).\end{equation}

There exist a great number of GCN variants to enhance SSL performance from different aspects. Li  <cit.> are the first to provide deep insights into GCN's success and failure on SSL tasks. Later on, extensions to GCN for SSL begin to proliferate. Jiang  <cit.> explore the way to do graph construction based on GCN. Yang  <cit.> combine the classic graph regularization methods with GCN. Abu  <cit.> present a novel N-GCN which marries the random walk with GCN, and a follow-up work GIL <cit.> with similar ideas is proposed as well. Other research work on GCN extensions can be found in <cit.> <cit.> <cit.> <cit.> <cit.> <cit.> <cit.> <cit.> <cit.>.

GCN often fails to learn a generalized class of neighborhood with various mixing relationships. In order to overcome this limitation, MixHop <cit.> is proposed to learn these relationships by repeatedly mixing feature representations of neighbors at various distances. Unlike GCN whose aggregation operator in the matrix form is defined as

\begin{equation}
\label{GCN_matrix}
\mathbf{H}^{(k)}=\sigma\left(A\mathbf{H}^{(k-1)}\mathbf{W}^{(k)}\right),
\end{equation}

where $\mathbf{H}^{(k-1)}$ and $\mathbf{H}^{(k)}$ are the input and output hidden embedding matrix for layer $k$.
MixHop replaces the Graph Convolution (GC) layer
defined in Eq. (<ref>) with

\begin{equation}
\label{MixHop_matrix}
\mathbf{H}^{(k)}=\|_{j \in P} \sigma\left({A}^{j} \mathbf{H}^{(k-1)} \mathbf{W}_{j}^{(i)}\right),
\end{equation}

where the hyper-parameter $P$ is a set of integer adjacency powers and $\|$ denotes column-wise concatenation. Specifically, by setting $P = \{1\}$, it exactly recovers the original GC layer. In fact, MixHop is interested in higher-order message passing, where each node receives latent representations from their immediate (one-hop) neighbors and from further N-hot neighbors.

Simple graph convolution networks (SGC).
GCNs inherit unnecessary complexity and redundant computation cost in nature as it derives inspiration from deep learning methods. Wu  <cit.> reduce this excess complexity by eliminating the nonlinearities among every GCN layer and collapsing the original nonlinear function into a simple linear mapping function defined in Eq. (<ref>). More importantly, these simplifications do not harm the prediction performance in many downstream applications.

\begin{equation}
\label{SGC}
\mathbf{h}_{u}^{(k)}=\sigma\left(\sum_{v \in \mathcal{N}(u) \cup\{u\}} \frac{\mathbf{h}_{v}}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}}\right).
\end{equation}

Differentiable group normalization (DGN).
To further mitigate the over-smoothing issue in GCN, DGN <cit.> also applies a new operation between the successive graph convolutional layers. Taking each embedding matrix $H^{(k)}$ generated from the $k^{th}$ graph convolutional layer as the input, DGN assigns each node into different groups and normalizes them independently to output a new embedding matrix for the next layer. Formally, we have,

\begin{equation}
\label{DGN}
\mathbf{H}^{(k+1)} = \mathbf{H}^{(k)} + \lambda \sum_{i=1}^{g}\left(\gamma_i(\frac{\mathbf{s}_{i}^{(k)}\circ\mathbf{H}^{(k)} - \mu_i}{\delta_i})+\beta_i\right),
\end{equation}

where $\mathbf{H}^{(k)}$ is the $k^{th}$ layer of the hidden embedding matrix, $\mathbf{s}_{i}$ is the similarity measure and $g$ is the total number of groups. In particular, $\mu_i$ and $\delta_i$ denote the vectors of running mean of group $i$, respectively, and $\gamma_i$ and $\beta_i$ denote the trainable scale and shift vectors, respectively.

§.§.§ Pooling

Aggregation operation is essentially a mapping from a set of neighborhood embedding results to a single vector with encoded information about the local structure and the feature of neighbor nodes' feature. In the previously reviewed settings of GNN models, the mapping function in the aggregation operation is simply the basic summation or linear functions over neighbor embeddings. Some more sophisticated and successful mapping functions used in the aggregation setting are reviewed in this section.

Set pooling.
In fact, according to Wu  <cit.>, one principal approach for designing an aggregation function is focused on the theory of permutation invariant neural networks. Generally, the permutation invariance property deals with problems concerning a set of objects: the target value for a given set is the same regardless of the order of the objects in the set. A typical example of an invariant permutation model is a convolutional neural network which performs the pooling operation over embedding extracted from a set's elements. Permutation invariance on graphs in general means that the aggregation function does not depend on the arbitrary order of the rows/columns in the adjacency matrix. For example, Zaheer  <cit.> show that an aggregation function with the following form can be considered as a universal set function approximator:

\begin{equation}
\label{mlp_set_pooling}\mathbf{m}_{\mathcal{N}(u)}=\operatorname{MLP}_{\theta}\left(\sum_{v \in N(u)} \operatorname{MLP}_{\phi}\left(\mathbf{h}_{v}\right)\right).\end{equation}

Janossy pooling.
Another alternative method, called Janossy pooling, is to enhance the aggregation operation, which is also possibly more efficient than simply taking a sum or mean of the neighbor embeddings used in basic GNN. Janossy pooling <cit.> uses a completely different approach. Instead of using a permutation invariant reduction (e.g., a sum or a mean), a permutation-sensitive function is applied, and the outcome is averaged over many potential permutations.

Let $\pi_{i} \in \Pi$ denotes a permutation function that maps the set $\left\{\mathbf{h}_{v}, \forall v \in \mathcal{N}(u)\right\}$ to a specific sequence $\left(\mathbf{h}_{v_{1}}, \mathbf{h}_{v_{2}}, \ldots, \mathbf{h}_{v_{|\mathcal{N}(u)|}}\right)_{\pi_{i}}$. Namely, $\pi_{i} \in \Pi$ takes the unordered set of embedding states from the neighbors and puts them in a sequence dependent on some random ordering arbitrarily. The Janossy pooling approach then performs neighborhood aggregation operation by Eq. (<ref>).

\begin{equation}
\label{janossy_pooling}
\mathbf{m}_{\mathcal{N}(u)}=\operatorname{MLP}_{\theta}\left(\frac{1}{|\Pi|} \sum_{\pi \in \Pi} \rho_{\phi}\left(\mathbf{h}_{v_{1}}, \mathbf{h}_{v_{2}}, \mathbf{h}_{v_{|\mathcal{N}(u)|}}\right)_{\pi_{i}}\right),\end{equation}

where $\Pi$ denotes a collection of permutations and $\rho_{\phi}$ is a permutation-sensitive function, e.g., a neural network that operates on sequential data. Usually $\rho_{\phi}$ is represented as an LSTM in operation, since LSTMs are known to be a powerful architecture for sequences in the neural network.

§.§.§ Neighborhood attention

A common approach for enhancing the aggregation layer in GNNs is to implement some attention mechanisms <cit.>, in addition to more general forms of set aggregation. The basic principle is to assign a weight or value of importance to each neighbor, which is used during the aggregation phase to weigh this neighbor's effect.

The first GNN model to apply this style of attention was Cucurull 's Graph Attention Network (GAT) <cit.>, which uses attention weights to define a weighted sum of the neighbors:

\begin{equation}\mathbf{m}_{\mathcal{N}(u)}=\sum_{v \in \mathcal{N}(u)} \alpha_{u, v} \mathbf{h}_{v},\end{equation}

where $\alpha_{u, v}$ denotes the attention on neighbor $v \in \mathcal{N}(u)$ when we are aggregating information at node $u$. In the original GAT paper, the attention weights are defined as

\begin{equation}\alpha_{u, v}=\frac{\exp \left(\mathbf{a}^{\top}\left[\mathbf{W} \mathbf{h}_{u} \oplus \mathbf{W} \mathbf{h}_{v}\right]\right)}{\sum_{v^{\prime} \in \mathcal{N}(u)} \exp \left(\mathbf{a}^{\top}\left[\mathbf{W h}_{u} \oplus \mathbf{W h}_{v^{\prime}}\right]\right)},\end{equation}

where $\mathbf{a}$ is a trainable attention vector, $\mathbf{W}$ is a trainable matrix, and denotes the concatenation operation. A similar parallel work is AGNN <cit.> which reduces the number of parameters in GNN with the help of attention mechanisms.
Moreover, although it is less common in the GNN literature, the famous transformer <cit.> may also have several “heads“ for attention.
In this approach, one computes $K$ distinct attention weights $\alpha_{u, v, k}$ by using attention layers with independent parameters. The messages attached with the varying weights of attention are then transformed and combined with a linear projection, typically followed by a concatenation operation. Formally, we have,

\begin{equation}
\mathbf{m}_{\mathcal{N}}(u) =\left[\mathbf{a}_{1} \oplus \mathbf{a}_{2} \oplus \ldots \oplus \mathbf{a}_{K}\right],
\end{equation}

\begin{equation}
\mathbf{a}_{k} =\mathbf{W}_{i} \sum_{v \in \mathcal{N}(u)} \alpha_{u, v, k} \mathbf{h}_{v},
\end{equation}

where the attention weights $\alpha_{u, v, k}$ for each of the $K$ attention heads can be computed using some of the above mentioned attention mechanisms.

To sum up, a good strategic approach is incorporating the attention mechanism, particularly when some prior knowledge is available, as certain neighbors could be more knowledgeable than others, which may help increase the representational capacity of a GNN model.

§.§ Generalized update operation

As already noted in Section <ref>, lots of research papers focus on generalized aggregate operation. This was especially the case after the GraphSAGE Framework <cit.>, which implements the idea of generalized neighborhood aggregation. This section concentrates on the more diversified Update operation, which also makes the embeddings more suitable for SSL tasks.

§.§.§ Concatenation and skip-connections

Over-smoothing is a major issue for GNN. The over-smoothing is almost inevitable after many message iterations when the node-specific information becomes washed away. In such cases, the modified node representations are too highly dependent on the incoming message aggregated by the neighbors at the cost of previous layers' node hidden states. One reasonable way to mitigate this problem is to use vector concatenations or skip connections, which aim to retain information directly from previous rounds of the update.

These techniques can actually be used in combination with several other update operation methods for the GNN. For general purposes, $\texttt{Update}_{\texttt{base}}$ denotes the simple update rule that will be built on. For instance, the $\texttt{Update}_{\texttt{base}}$ function can be presumed as shown in Eq. (<ref>) in the basic GNN.

One of the simplest updates for skip connection is GraphSAGE <cit.> which uses a concatenation vector to hold more information from node level during message passing process:

\begin{equation}\texttt{Update}\left(\mathbf{h}_{u}, \mathbf{m}_{\mathcal{N}}(u)\right)=\left[\texttt {Update}_{\texttt{base}}\left(\mathbf{h}_{u}, \mathbf{m}_{\mathcal{N}(u)}\right) \oplus \mathbf{h}_{u}\right],\end{equation}

where the output from the simple update function is concatenated with the node 's previous layer representation. The core intuition is that the model is encouraged to dissociate information during the message passing.

Column Network (CLN).
Besides concatenation methods, some other forms of skip-connections can also be applied, such as the linear interpolation method proposed by Pham  <cit.>,

\begin{equation}
\begin{aligned}
\texttt{Update}\left(\mathbf{h}_{u}, \mathbf{m}_{\mathcal{N}}(u)\right)&=\boldsymbol{\alpha}_{1} \circ \texttt{Update}_{\texttt {base}}\left(\mathbf{h}_{u}, \mathbf{m}_{\mathcal{N}}(u)\right)\\
&+\boldsymbol{\alpha}_{2} \circ \mathbf{h}_{u},
\end{aligned}
\end{equation}

where $\boldsymbol{\alpha}_{1},\boldsymbol{\alpha}_{2} \in [0,1]^d$ are gating vectors with $\boldsymbol{\alpha}_{1}+\boldsymbol{\alpha}_{2}=1$ and $\circ$ denotes Hadamard product.
In this method the final update is a linear interpolation between the previous output and the current output and is modified depending on the information in the neighborhood.
In general, with the introduction of these concatenation and skip-connections techniques, not only the over-smoothing issue in GNN can be alleviated to some extent, but also the numerical stability of optimization is greatly improved. Indeed, similar to the functionality of residual connections in convolutional neural networks (CNNs), it is effective to apply these approaches to GNNs in which the training process of much deeper models could be facilitated.

Scattering GCN.
The most recent work on tackling the problem of over-smoothing in GNN is Scattering GCN <cit.> with the geometric scattering transformation that enables band-pass filtering of graph signals. Geometric scattering is originally introduced in the context of whole-graph classification and consisted of aggregating scattering features. Similar and concurrent work is DropEdge <cit.> which removes a certain portion of edges from the given graph at each training epoch, acting like a data augmenter and thus alleviate both over-smoothing and over-fitting issues at the same time.

These strategies are also beneficial for node classification tasks with relatively deep GNNs, in a semi-supervised setting, and they are excellent for these SSL tasks where the prediction in each node is closely correlated with the characteristics of the local neighborhood.

§.§.§ Gated updates

Parallel to the above-mentioned work, the researchers have also taken inspiration from the approaches used by recurrent neural networks (RNNs) to strengthen stability. One way to interpret the GNN message passing algorithm is to collect an observation from the neighbors from the aggregation operation, which then updates the hidden state of each node. From this perspective, some methods for updating the hidden status of RNN architectures can be directly applied based on the observation.

For example, one of the earliest GNN variants which put this idea into practice is proposed by Li  <cit.>, in which the update operation is defined as shown in Eq. (<ref>) as,

\begin{equation}
\label{gatedGNN}
\mathbf{h}_{u}^{(k)}=\operatorname{GRU}\left(\mathbf{h}_{u}^{(k-1)}, \mathbf{m}_{\mathcal{N}(u)}^{(k)}\right),\end{equation}

where GRU is a gating mechanism function in recurrent neural networks, introduced by Kyunghyun Cho  <cit.>. Another approach called NeuroSAT <cit.> has employed updates based on the LSTM architecture as well.
Typically every RNN update function can be used in the GNN setting.  Importantly, the RNN-style update parameters are also exchanged across nodes when updating each node based on the same LSTM or GRU cell. In reality, the model typically shares the parameters of the update operation function across the message passing layers.

§.§.§ Jumping knowledge (JK) connections

In the previous sections, it is implicitly assumed that the last layer's output is considered as the final embedding result. In other words, the node representations used for a downstream job, such as SSL tasks, are identical to the final layer's node embedding in the GNN. Formally, it is presumed that

\begin{equation}\mathbf{z}_{u}=\mathbf{h}_{u}^{(K)}, \forall u \in \mathcal{V}.\end{equation}

JK Net.
A complementary approach to increase the effectiveness of final node representations is to use the combination on each layer of the message passing, rather than merely the final layer's output. In a more formal way,

\begin{equation}\mathbf{z}_{u}=f_{J K}\left(\mathbf{h}_{u}^{(0)} \oplus \mathbf{h}_{u}^{(1)} \oplus \ldots \oplus \mathbf{h}_{u}^{(K)}\right),\end{equation}

This technique is originally introduced and tested by Xu  <cit.>, called the idea of jumping knowledge connections. The $f_{JK}$ function can be used as the identity function for various applications, meaning that a simple concatenation is essentially performed among the node embeddings from each layer, but Xu  <cit.> also think about other possibilities such as max pooling. This method also leads to significant progress over a wide range of tasks like SSL classification and is usually regarded as an effective strategy.

Previous GNN models appear to have low generalization performance because of the model's crafted styles. To lessen the downgrade of generalization performance in the testing phase, InfoGraph* <cit.> maximizes the mutual information between the embeddings learned by popular supervised learning methods and unsupervised representations learned by InfoGraph, where the given graph is encoded to produce its corresponding feature map by jumping knowledge concatenation. The encoder then learns from unlabeled samples while preserving the implicit semantic information that the downstream task favors.

GNN-based methods are perceived as the most advanced approach and current trends for GSSL research. The most prominent advantage of GNN-based methods over others is that they consider nodes' attributes for generating embeddings so that the inconsistency in the proceeding graph construction step can be alleviated to some extent. Recent research work <cit.> shows that GNN can be jointly trained with MLP based on a newly designed regularizer to boost SSL performance. Other related works focus on how to combine GNN with other models, like Markov model <cit.>, GAN <cit.> and metric learning <cit.>.

Finally, it is worth noting that the latest work on the GSSL method is GRAND <cit.>, which is considered as the state-of-the-art method by incorporating graph embedding with graph regularization. The key technique of GRAND is to introduce the classic data augmentation method on graph level into the GNN training as a pre-processing step so that the consistency regularization can be leveraged to optimize the prediction consistency of unlabeled data. GRAND is also able to mitigate the issues of over-smoothing and non-robustness further.