\section{Introduction}\label{sec:intro}}
\IEEEPARstart{G}{raph} Convolutional Networks (GCNs) can capture the dependence in graphs through message passing between nodes. Due to the excellent ability for graph representation learning, GCNs have shown remarkable breakthroughs in numerous applications~\cite{zhou2020graph,wu2020comprehensive,inter,soft}, including node classification~\cite{kipf2016semi, xu2018representation,chien2021adaptive,klicpera2018predict,chen2020simple,feng2020graph, wan2019multiscale}, object detection~\cite{Yao_2018_ECCV,9102838,10.1007/978-3-030-58610-2_21}, and visual question answering~\cite{Li_2019_ICCV}. However, despite the widespread success, current GCNs still suffer from a severe problem, i.e., the performance seriously degenerates with the increasing number of layers. 

The performance degradation problem is widely believed to be caused by the over-smoothing issue~\cite{li2018deeper,chen2020measuring,yan2021two, wang2019improving, wu2019simplifying, yang2020revisiting, zhao2019pairnorm, oono2019graph, cai2020note, rong2019dropedge, chien2021adaptive}. Specifically, each graph convolutional operation tends to mix the features of connected nodes through message propagation. The features between connected nodes quickly become indistinguishable when stacking too many graph convolutional operations. This phenomenon is referred to as the \textit{over-smoothing} issue. \cite{oono2019graph} also investigated the asymptotic behaviors of GCNs and found that the node representations will approach an invariant space when the number of layers goes to infinity. Considering that deeper neural networks usually show better expressive and reasoning ability~\cite{raghu2017expressive}, how to devise deeper GCNs by addressing the over-smoothing issue has received increasing attention from the community~\cite{li2019deepgcns,rong2019dropedge}. However, over-smoothing is not the sole reason for the performance degradation when deepening GCNs. Another important issue is the well-known gradient vanishing for deep models. In this study, we demonstrate that the story for GCNs is a bit different: over-smoothing and gradient vanishing mutually reinforce each other, making the performance degrading more rapidly compared to ordinary deep models. Specifically, we show that over-smoothing pushes the gradient of the classification loss w.r.t the output layer towards 0 at the very beginning of the training process (after the first forward-propagation). This not only aggravates the traditional back-propagation-induced gradient vanishing issue, but also triggers the \textit{weight over-decaying} issue due to the dominating effect of regularization. The gradient vanishing and weight over-decaying issues in turn encourage the output features to further approach 0 (weight matrices with small values were multiplied repeatedly), thus worsening the over-smoothing issue and making the output trivial.


To cope with the performance degradation problem, several GCN variants were proposed recently for alleviating the over-smoothing issue~\cite{xu2018representation, kazi2019inceptiongcn, chien2021adaptive, klicpera2018predict, chen2020simple, feng2020graph,zhang2021evaluating,liu2020towards,wang2021dissecting,cong2021provable}. However, these methods still suffer from the following drawbacks: (1) most of these models tried to alleviate over-smoothing by sacrificing the expressiveness merit of deep learning, e.g., emphasizing low-level features when over-smoothing happens~\cite{xu2018representation, kazi2019inceptiongcn, chien2021adaptive}, removing nonlinearity in middle layers~\cite{klicpera2018predict}, and aggregating neighborhoods of different orders in one layer of computation~\cite{feng2020graph}; (2) some methods only dealt with the gradient vanishing issue~\cite{he2016deep}, which was proved in~\cite{oono2019graph} to be ineffective for the over-smoothing issue; and (3) all of these methods proposed ad-hoc GCN models for addressing the over-smoothing issue. The techniques proposed are not general enough to be applied to various GCN models. Considering the rapid development of the graph neural network field, a general technique that can be applied to different GCN models would be more beneficial to the research community. DropEdge~\cite{rong2019dropedge}, DropNode~\cite{do2021graph}, and PairNorm~\cite{zhao2019pairnorm} are three such general modules against the over-smoothing issue. However, they mainly focused on improving feature diversity among different nodes by modifying the graph topology or adjusting the intermediate features, leaving other issues such as gradient vanishing poorly investigated.

More importantly, all the previous anti-over-smoothing methods still require performing $L$ full convolutional operations for each node, where $L$ is the model depth of a GCN-based model. Each convolutional operation multiplies the current node feature matrix by the normalized adjacency matrix and a weight matrix. Let $\lambda$ be the second largest magnitude of the eigenvalues of the normalized adjacency matrix and $s$ be the maximum singular value of weight matrices. Theorem 2 from~\cite{oono2019graph} shows that the node feature matrix will \textit{exponentially} become over-smoothing as $L$ increases with convergence speed as $O((s\lambda)^{L})$, since usually $s\lambda < 1$. Although the previous methods tried to alleviate over-smoothing with various ideas, none of them got out of the curse of $(s\lambda)^L$. As $L$ increases, the feature matrix still tends to degenerate due to the exponential effect of $(s\lambda)^L$.

A straightforward idea for simultaneously alleviating over-smoothing and gradient vanishing is to combine an existing anti-over-smoothing method with Skip Connection~\cite{residual}, a well-known strategy for the gradient vanishing issue. Nevertheless, although this simple combination is effective for gradient vanishing, it could not well cope with the over-smoothing issue, since $L$ full convolutions are still required. Previous work~\cite{oono2019graph} has also proved Skip Connection contributes little to addressing over-smoothing.


From the above analysis, we can see the key underlying issue of over-smoothing is the exponential effect of $(s\lambda)^{L}$ which is hard to break. In this paper, we take a different route to cope with the over-smoothing issue: rather than trying to increase $s$ or $\lambda$, we propose to decrease the exponent part, i.e., $L$. In particular, we devise a new plug-and-play module, dubbed SkipNode, to better train deep GCN-based models. SkipNode samples nodes in each convolutional layer to completely skip this layer's calculation. In other words, the features of those selected nodes are kept unchanged during the convolutional operation. SkipNode is analogous to Dropout~\cite{dropout}, where the difference is that we randomly drop layers, rather than features. Intuitively, this training strategy could effectively reduce $L$ for those selected nodes, and consequently would significantly alleviate the exponential effect of $(s\lambda)^{L}$; the skip operation naturally facilitates gradient back-passing, which means it could also well cope with gradient vanishing. We further show that even for one layer's calculation, SkipNode can generate better anti-over-smoothing results in expectation than vanilla GCN. The main contributions are specified as follows:



\textbullet\
\textbf{We provide a more complete view of the causes of performance degradation in deep GCNs.} We analyze in detail two additional issues, gradient vanishing and model weights over-decaying, and their relationships with over-smoothing. The interplay between them is responsible for the terrible performance when deepening GCNs.


\textbullet\
\textbf{We devise a novel plug-and-play module, dubbed SkipNode, for addressing performance degradation in deep GCNs.} In each middle layer of a GCN model, SkipNode samples nodes either uniformly or based on node degrees to skip the convolutional operation completely. For unselected nodes, they can still receive information from these selected (skipped) ones. We analyze the effectiveness of SkipNode towards alleviating the above three issues, and prove that it can better resist over-smoothing even considering one layer's calculation (i.e., it can improve both exponent part and base part of $(s\lambda)^{L}$).



\textbullet\
\textbf{Extensive experiments are conducted to verify the generalizability and effectiveness of SkipNode.} 
The experimental results on various datasets demonstrate the good capability of our SkipNode to alleviate performance degradation in deep GCNs. Specifically, (1) SkipNode has strong generalizability to improve GCN-based methods (including those designed for the over-smoothing issue) on various graphs and tasks; and (2) SkipNode consistently outperforms the commonly-used plug-and-play strategies, DropEdge, DropNode, and PairNorm, in different settings.


\section{Related Work}
\label{sec:related-work}
In this section, we first briefly review the development of graph convolution networks, and then introduce existing works targeting the over-smoothing issue. Finally, we discuss the differences between our SkipNode and three closely related strategies, i.e., DropEdge~\cite{rong2019dropedge}, DropNode~\cite{do2021graph}, and Skip Connection~\cite{residual}. 

\subsection{Graph Convolutional Networks} \cite{bruna2013spectral} first devised a graph convolution operation based on the graph spectral theory. However, considering the high computational cost, it is very difficult to apply spectral-based models~\cite{bruna2013spectral,henaff2015deep, defferrard2016convolutional,kipf2016semi} to very large graphs. Spatial-based models~\cite{hamilton2017inductive,monti2017geometric,velivckovic2017graph,niepert2016learning} exhibit great scalability since their convolutional operations can be directly applied to spatial neighborhoods of unseen graphs. \cite{kipf2016semi} simplified previous works and proposed the current commonly-used graph convolutional network, i.e., GCN. Based on~\cite{kipf2016semi}, many works~\cite{xu2018powerful,you2019position,9336270,wu2019simplifying,abu2020n} toward improving the graph learning have been proposed. \cite{xu2018powerful} investigated the expressive power of different aggregations and proposed a simple model, GIN. P-GNNs~\cite{you2019position} incorporated positional information into GCN. SGC~\cite{wu2019simplifying} reduced the complexity of GCN by discarding the nonlinear function and weight matrices. Despite performance improvement, deepening GCNs remains an challenging problem.

\subsection{Over-smoothing}
Over-smoothing is a basic issue of deep GCNs~\cite{li2018deeper}. \cite{yang2020revisiting, chien2021adaptive, wu2019simplifying} found that the node representation becomes linearly dependent after using infinite number of layers. \cite{oono2019graph,cai2020note} further proved that the output of deep GCN with a ReLU activation function converges to zero. \cite{yan2021two} investigated the over-smoothing issue in heterophilic and homophilic graphs. In general, current solutions to the over-smoothing issue fall into two categories:

\vspace{2mm} \noindent \textbf{Specific GCNs-based models for over-smoothing}:
\cite{kipf2016semi} attempted to construct a multi-layer GCN by adding residual connections \cite{he2016deep}. JKNet~\cite{xu2018representation} combined the outputs of different layers for the final representation. InceptGCN~\cite{kazi2019inceptiongcn} integrated different outputs from multiple GCN with various layers. GCNII~\cite{chen2020simple} obtained remarkable performance over many benchmarks by utilizing initial residual connection and identity mapping. APPNP~\cite{klicpera2018predict} incorporated the PageRank algorithm into GCN to derive a novel propagation schema instead of the Laplacian smoothing. \cite{chien2021adaptive} followed PageRank-style propagation and added adaptive weights to escape from over-smoothing guided by label information.~\cite{zhang2021evaluating,liu2020towards,wang2021dissecting,cong2021provable} decoupled feature transformation from propagation to avoid over-smoothing (and model degeneration). However, the above models are precisely designed and the proposed techniques are difficult to be used on various GCNs-based models.
    
\vspace{2mm} \noindent \textbf{Plug-and-play techniques for over-smoothing}: \cite{yang2020revisiting}, \cite{oono2019graph}, and \cite{zhao2019pairnorm} proposed several normalization-based methods, i.e., mean-subtraction, node representations/weight scaling, and center-and-scale normalization to prevent features from becoming indistinguishable as propagating. Other methods focused on modifying the graph structure.~\cite{rong2019dropedge} proposed DropEdge to alleviate both over-smoothing and over-fitting issues by randomly deleting a part of edges.~\cite{oono2019graph} also agreed that sampling edges can be the remedy for over-smoothing. Additionally, DropNode~\cite{do2021graph} focused on sampling nodes. ~\cite{zeng2020deep} designed a shallow sampler for obtaining subgraphs for deep GCNs to reduce noise for representation learning. Unfortunately, these works excessively emphasized on maintaining feature diversity but ignored other issues beyond over-smoothing. The most recent work~\cite{zhou2021dirichlet} proposed a novel framework, consisting of orthogonal weight controlling, lower-bounded residual connection, and shifted ReLU activation, to trained deep GCNs by regularizing Dirichlet energy. However, the extra efforts on weight regularization increase the complexity of optimization.

In summary, none of the previous methods dealing with deep GCNs' performance degradation tried to alleviate both over-smoothing and gradient vanishing. Moreover, they still performed graph convolutions up to the model depth, which could not well resist the exponential smoothing effect of model depth. 


\subsection{Detailed Comparison to DropEdge, DropNode and Skip Connection}

Figure~\ref{fig:model} illustrates the key differences of the four plug-and-play strategies when applied to one layer of GCNs. It depicts how they manipulate the input node features $x$'s and the graph structure (the first row of Figure~\ref{fig:model}) to obtain the output features $z$'s (the second row). The last column shows that SkipNode replaces the sampled (skipped) nodes' outputs ($z_{1}$ and $z_{2}$) by the respective input node features ($x_{1}$ and $x_{2}$). As a result, this ``skip'' operation not only well resists the exponential smoothing effect of model depth by skipping some convolutional operations for the sampled nodes, but also enables the gradient to be transferred via the sampled nodes, hence alleviating gradient vanishing. Finally, because the above two issues have been well alleviated, the weights norm will not degrade excessively. In the following, we discuss the intrinsic differences between SkipNode and DropEdge, DropNode and Skip Connection. In Table~\ref{tab:comparison}, we also summarize their ability to deal with the three issues, namely, over-smoothing, gradient vanishing, and weight over-decaying.


\begin{table}[h]
    \centering
    \caption{Comparison to DropEdge, DropNode and Skip Connection in terms of the ability to deal with the three issues when deepening GCNs. OS, GV, and WD represent over-smoothing, gradient vanishing, and weight over-decaying, respectively.}
    \begin{tabular}{c | c c c}
    \toprule
    Methods  &  OS & GV & WD \\
    \midrule
    DropEdge & \checkmark & $\times$ & $\times$ \\
    DropNode & \checkmark & $\times$ & $\times$ \\
    Skip Connection & $\times$ & \checkmark & \checkmark \\
    SkipNode & \checkmark & \checkmark & \checkmark \\
    \bottomrule
    \end{tabular}
    \label{tab:comparison}
\end{table}

\begin{figure*}[ht]
    \centering
    \includegraphics[width=0.8\textwidth]{fig/SkipNode_model.pdf}
    \caption{The sketch of how Vanilla GCN and GCN with DropEdge/DropNode/Skip Connection/SkipNode perform on a graph. We use $x$'s to represent a node and its corresponding input feature and regard $z$'s as the output feature. Vanilla GCN enables each connected node to exchange information. DropEdge deletes the edge between $x_{1}$ and $x_{2}$ to make the graph sparser. DropNode removes the $x_{3}$ by down-sampling technique. Skip Connection directly adds the input on the output. SkipNode maintains the selected node's information ($x_{1}$ and $x_{2}$) and updates the unselected node's ($x_{3}$).}
    \label{fig:model}
\end{figure*}



\subsubsection{SkipNode \textit{vs.} DropEdge}
As shown in the second column of Figure~\ref{fig:model}, DropEdge~\cite{rong2019dropedge} randomly deletes the edge between $x_{1}$ and $x_{2}$ during training to keep them from being too similar. The key idea of DropEdge is that more sparsity of the graph results in less over-smoothing. However, randomly deleting too much edges may compromise critical structural information, while removing too few edges cannot effectively relieve over-smoothing. As a result, determining the dropping ratio when DropEdge is applied to various graphs is not a simple task. DropEdge primarily concentrates on over-smoothing, ignoring gradient vanishing and weight over-decaying issues since the gradient still need to go through the model layer by layer and inevitably end up vanishing. Moreover, DropEdge re-normalizes the adjacent matrix in each epoch, which is time-consuming when dealing with large graphs.


\subsubsection{SkipNode \textit{vs.} DropNode}
There are two works~\cite{feng2020graph,do2021graph} which proposed the DropNode technique. In~\cite{feng2020graph}, DropNode is used as a data augmentation method to randomly mask nodes' features before propagation. In addition, it requires extra regularization on the outputs from different augmentations to maintain the robustness of the model. \textbf{Therefore, it is not a plugin for alleviating over-smoothing and we do not regard~\cite{feng2020graph} as a comparing strategy.} In~\cite{do2021graph}, a DropNode scheme targeting at over-smoothing is proposed to down-samples the graph between GCN layers. The third column in Figure~\ref{fig:model} shows that the graph with $x_{3}$ removed is used as the input for the current layer. Similarly to DropEdge, DropNode only tries to ease the over-smoothing issue. It has to normalize the new adjacency matrix in each layer since the selected nodes are dropped. Besides, it is not easy to implement DropNode in some models that require concatenating intermediate node representations or using skip connection in implementation since the nodes from different layers might not be readily aligned. Our SkipNode differs from DropNode by its simplicity to be easily applied to various models, and the theoretically guaranteed effectiveness to alleviate all the three issues (cf. Sec.~\ref{sec:SkipNode}). 

\subsubsection{SkipNode \textit{vs.} Skip Connection} 
Skip (or Residual) connection~\cite{residual} has been widely used to prevent gradient vanishing. As shown by the fourth column in Figure~\ref{fig:model}, Skip Connection adds the (less smooth) inputs to the (smoother) convolution outputs. However, \cite{oono2019graph, wang2019improving} proved that GCN with skip connections acts similarly to a lazy random walk in a graph and eventually converges to a stationary distribution. As a result, the final outputs still tend to contain smooth features. In contrast, our SkipNode improves feature diversity by directly replacing the smoother features ($z_{1}$ and $z_{2}$) with the less smooth ones ($x_{1}$ and $x_{2}$) so that the outputs could better resist over-smoothing. In addition, by allowing some nodes to bypass the multiplication with weight matrices, the node-wise ``skip'' operation also prevents deep GCNs from gradient vanishing because the gradient can pass through the ``skipped'' nodes to shallow layers.


\section{Preliminaries}
\label{sec:preliminaries}
This section presents background contents, including vanilla GCN~\cite{kipf2016semi} and existing studies about over-smoothing. We first define the common notations used in this paper.


\subsection{Notations}
Assuming that $\mathbb N_{+}$ is the set of positive integers, we denote $[M] := \{1, \cdots, M\}$ for $M \in \mathbb N_{+}$. Let $\mathcal{G}=\{\mathcal{V}, \mathcal{E}\}$ denote an undirected graph, $\mathcal{V}=\{v_1, v_2, ..., v_N \}$ denote the node set, where $N$ is the number of all nodes. Let $\mathcal{E}=\{e_{ij}\}, i,j\in [N]$ denote the edge set, where $e_{ij}$ indicates the edge between nodes $v_i$ and $v_j$. The adjacency matrix is defined as $A \in \mathbb{R}^{N\times N}$, where $A_{ij} = 1$ if $e_{ij}\in \mathcal{E}$ otherwise $A_{ij} = 0$. Let $D$ denote the diagonal degree matrix, where $D_{ii} = \sum_{j=0}^{N}A_{ij}$. Suppose that $X^{(l)} \in \mathbb R^{N \times d_{l}}$ is the output feature matrix of the $l$-th layer, and $d_{l}$ is the feature dimensionality of the $l$-th layer, where $l \in [L]$ and $L \geq 2$. The raw node feature matrix is defined as $X^{(0)} \in \mathbb{R}^{N\times d_{0}}$. Given $v \in \mathbb R^{d}$ and $w \in \mathbb R^{d}$, the Kronecker product operation $v \otimes w$ results in a $\mathbb R^{d \times d}$ matrix, where $(v \otimes w)_{ij} := v_{i}w_{j}$. 

\subsection{Vanilla GCN}
The vanilla GCN~\cite{kipf2016semi} defines the graph convolution operation as $g_{\theta} \star x \approx \theta(I + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})\boldsymbol{x}$, where $\boldsymbol{x} \in {{\mathbb R}^{N}}$ indicates the graph signal, $\star$ is the convolutional operation, and $\theta$ is a learnable parameter. To avoid exploding filter coefficients, ~\cite{kipf2016semi} further adopted re-normalization trick. The final GCN formulation can thus be written as
\begin{equation}
    X^{(l)} = ReLU(\tilde{A}X^{(l-1)}W^{(l)}),
    \label{eq:gcn}   
\end{equation}
where $\tilde{A} = (D + I)^{-\frac{1}{2}}(A + I)(D + I)^{-\frac{1}{2}}$ is a normalized adjacency matrix and $W^{(l)} \in \mathbb{R}^{d_{l-1} \times d_{l}}$ indicates the $l$-th learnable weight matrix. Accordingly, the symmetrical augmented graph Laplacian is defined as $\tilde{L} = I - \tilde{A}$.

\subsection{Over-smoothing of GCNs}
\label{subsec:over-smoothing-def}
Over-smoothing is an issue where node representations lose their diversities, which hinders the learning of graph neural networks. Many prior works~\cite{oono2019graph,xu2018representation,cai2020note,chien2021adaptive,li2018deeper} have been devoted to exploring what is over-smoothing and they can be roughly divided into two groups.  

On the one hand, from the perspective of linear feature propagation, \cite{li2018deeper,xu2018representation,chien2021adaptive} proved that GCNs can be regarded as low-pass filters retaining low frequency signals in graph signal processing. Regardless of the weight matrix, the output features of nodes from a connected $\mathcal{G}$ become linearly dependent after multiple propagation. It can be explained by 

\begin{equation}
\lim_{k \to \infty}\tilde{A}^{k}X^{(0)} = \boldsymbol{\pi}\boldsymbol{\pi^{T}}X^{(0)},
\end{equation}
where $\pi_{i} = \frac{\sqrt{{D_{ii}} + 1}}{\sum_{v \in N}\sqrt{(D_{vv} + 1)}}$ and $i \in [N]$. This equation can be derived by diagonalization of $\tilde{A}$ and the fact that $\tilde{A}$'s eigenvalues lie in $(-1, 1]$. 

On the other hand, \cite{oono2019graph,cai2020note} investigated over-smoothing in the general graph convolutional networks architecture. \cite{oono2019graph} offered a more comprehensive understanding of over-smoothing by explaining it as the decreasing distance between the node feature matrix and a lower-information subspace $\mathcal{M} \subset \mathbb R^{N \times d}$ after multiple convolutions\footnote{\cite{oono2019graph} assumes all the output feature matrices share the same feature dimensionality $d$ to facilitate derivation.}. Assuming that the eigenvalues of $\tilde{A}$ are sorted in ascending order as: $\lambda_{1} \leq \cdots \leq \lambda_{N}$, we have $-1 < \lambda_{1} < \cdots < \lambda_{N-M}$ and $\lambda_{N - M + 1} = \cdots = \lambda_{N} = 1$ ($0 < M < N$). Let $U$ be a $M$-dimensional subspace of $\mathbb R^{N}$, which is the eigenspace corresponding to the smallest eigenvalue of augmented normalized graph Laplacian $\tilde{L}$ (that is the eigenspace associated with the eigenvalue 1 of $\tilde{A}$). $U$ is assumed to have the following properties~\cite{oono2019graph}. 

\begin{assumption}
\label{asp1}
$U$ has an orthonormal basis $(e_{m})_{m \in [M]}$ that consists of non-negative vectors.
\end{assumption} 

\begin{assumption} 
\label{asp2}
$U$ is invariant under $\tilde{A}$, i.e., if $u \in U$, then $\tilde{A}u \in U$.
\end{assumption} 

Based on Assumption~\ref{asp1}, we can construct the subspace $\mathcal{M}$ that only contains information about connected components and node degrees. That is, for any $X \in \mathcal{M}$, nodes with equal degrees from a same connected component have identical row vectors in $X$.

\begin{definition}
(Subspace $\mathcal{M}$) Let $\mathcal{M} := U \otimes \mathbb R^{d} = \{\sum_{m=1}^{M} e_{m} \otimes w_{m} | w_{m} \in \mathbb R^{d}\}$ be a subspace of $\mathbb R^{N \times d}$, where $(e_{m})_{m \in [M]}$ is the orthonormal basis of $U$.
\end{definition}
The distance between subspace $\mathcal{M}$ and $X$ is denoted as $\DMone{X} := inf\{\lVert X - H\rVert_{F}|H \in \mathcal{M}\}$, where $\lVert \cdot \rVert_{F}$ is the Frobenius norm of a matrix. Then, for a GCN model with $L$ layers defined by Eq.~(\ref{eq:gcn}), its final output $X^{(L)}$ will exponentially approach the subspace $\mathcal{M}$. And the convergence can be written as:
\begin{equation}
    \label{eq:shrinking_distance}
    \DMone{X^{(L)}} \leq s_{L-1}\lambda \DMone{X^{(L-1)}} \leq \cdots \leq \prod_{l=1}^{L}(s_{l}\lambda)\DMone{X^{(0)}},
\end{equation}
where $s_{l}$ is the maximum singular value of $W^{(l)}$ and $\lambda := max_{n \in [N - M]} |\lambda_{n}|$. In addition, the Proposition 3 from~\cite{oono2019graph} also notes that $X^{(l)}$ will exponentially approach 0 as $l \to \infty$ if $s\lambda < 1$ and the operator norm of $\tilde{A}$ is no larger than $\lambda$, where $s := sup_{l \in [L]} s_{l}$. 


However, they simply attributed the performance degradation to over-smoothing. In this paper, we show that there are two other issues responsible for the failure of deep GCNs, i.e., gradient vanishing and model weights over-decaying. 

\section{Why Deep GCNs Fail?}
\label{sec:over-smoothing}
Numerous works~\cite{oono2019graph,xu2018representation,cai2020note,chien2021adaptive,li2018deeper} have explained the over-smoothing phenomenon as the sole reason that induces the performance degradation. However, few methods have comprehensively analyzed the specific reasons for degrading performance of deep GCNs beyond over-smoothing, i.e., gradient vanishing and weight over-decaying.


\begin{figure*}[ht]
        \centering
        \subfigure[Over-smoothing]{ 
        \includegraphics[height=3.5cm]{fig/fig_diversity_cora_new.pdf}
        }
        \hfil
        \subfigure[Gradient Vanishing]{
        \includegraphics[height=3.5cm]{fig/fig_gradients_cora_new.pdf}
        }
        \hfil
        \subfigure[Model Weights Over-decaying]{
        \includegraphics[height=3.5cm]{fig/fig_norm_cora_new.pdf}
        }
        \caption{Three issues on a $9$-layer GCN using Cora dataset. GCN (SkipNode-U)/GCN (SkipNode-B) stands for GCN with our SkipNode using uniform/biased sampling strategy. In (a), the features get more indistinguishable as the MAD~\cite{chen2020measuring} value (the mean of the average cosine distance from nodes to their connected nodes) becomes smaller. In (b), only SkipNode alleviates the gradient vanishing issue. (c) shows the sum of the L2 norm of all the model weights. Note that some curves coincide in (b) and (c).}
        \label{fig:negative_effects_on_cora}
\end{figure*}

\subsection{Gradient Vanishing}
\label{subsec:gradient-vanishing}
Gradient vanishing is a common issue existing in deep neural networks~\cite{gradient-vanishing}. However, there are very limited works analyzing the relationships between gradient vanishing and over-smoothing in detail. Here, we prove that the gradient would be reduced to zero at the classification layer as the model becomes deeper.

\begin{theorem}
\label{thm_gradient_vanishing}
Let $\mathcal{L}$ denote the cross-entropy loss function, $\mathcal{V}_{train}$ be the training set that contains $B$ nodes and $Z \in \mathbb{R}^{N \times C}$ be the output of the classification layer, where $C$ is the number of class. Assuming there are same samples in each category ($\frac{B}{C}$ samples per class), the gradient at the classification layer $\sum_{i \in \mathcal{V}_{train}} \sum_{j=1}^{C} \frac{\partial \mathcal{L}}{\partial Z_{ij}}$ gets close to 0 when the model's output converges to 0, the trivial fixed point introduced by the Proposition 3 from~\cite{oono2019graph}.
\end{theorem}

\begin{proof}
Let $\tilde{Y} = softmax(Z)$ denote the prediction score, $Y \in \mathbb R^{N \times C}$ denote the ground truth indicator, and $\mathcal{L}$ denote the cross-entropy loss function. Then, we have:
\begin{small}
    \begin{align*}
    \mathcal{L} &= -\frac{1}{B}\sum_{v_i \in \mathcal{V}_{train}} \sum_{j=1}^{C} Y_{ij}\log\tilde{Y}_{ij}\\
      &= -\frac{1}{B}\sum_{v_i \in \mathcal{V}_{train}} \sum_{j=1}^{C} Y_{ij}\log\frac{exp(Z_{ij})}{\sum_{k=1}^{C} exp(Z_{ik})},
\end{align*}
\end{small}
where $\mathcal{V}_{train}$ indicates the training set. 

For a node $v_i \in \mathcal{V}_{train}$ that belongs to the $c$-th class, we have $Y_{ic} = 1$ and $Y_{ij} = 0, \forall j \ne c$. Then, the gradient of $Z_{ic}$ is calculated as:
\begin{small}
\begin{align*}
    \frac{\partial \mathcal{L}}{\partial Z_{ic}} &= 
    -\frac{1}{B} \frac{1}{\tilde{Y}_{ic}}\left(\frac{exp(Z_{ic})\sum_{k=1}^{C} exp(Z_{ik}) - exp(Z_{ic})^{2} }{[\sum_{k=1}^{C} exp(Z_{ik})]^{2}}\right)\\
    &= -\frac{1}{B}\frac{1}{\tilde{Y}_{ic}}\left(\tilde{Y}_{ic} - \tilde{Y}_{ic}^{2}\right)\\
    &= \frac{\tilde{Y}_{ic} - 1}{B},
\end{align*}
\end{small}
and the gradient of $Z_{ij}, \forall j \ne c$ is calculated as:
\begin{small}
    \begin{align*}
    \frac{\partial \mathcal{L}}{\partial Z_{ij}} &= 
    \frac{1}{B} \frac{1}{\tilde{Y}_{ic}}\frac{exp(Z_{ic})exp(Z_{ij})}{\left(\sum_{k=1}^{C} exp(Z_{ik})\right)^{2}}\\
    &= \frac{1}{B}\frac{1}{\tilde{Y}_{ic}}\tilde{Y}_{ic}\tilde{Y}_{ij}\\
    &= \frac{\tilde{Y}_{ij}}{B}.
\end{align*}
\end{small}

Under the assumption in the Proposition 3 from~\cite{oono2019graph}, $Z$ converges to 0 as $l \to \infty$. Then, we have $\tilde{Y}_{ij} \approx \frac{1}{C}$. Accordingly, we can further derive the gradient as follows:

\begin{footnotesize}
\begin{align*}
    \sum_{i \in \mathcal{V}_{train}}\frac{\partial \mathcal{L}}{\partial Z_{ij}} &= \sum_{i \in \mathcal{V}_{train}} \left(\frac{Y_{ij}\left(\tilde{Y}_{ij} - 1\right)}{B} + \frac{\left(1 - Y_{ij}\right)\tilde{Y}_{ij}}{B}\right)\\
    &\approx \frac{1}{B} \sum_{i \in \mathcal{V}_{train}} \left(Y_{ij}\left(\frac{1}{C} - 1\right) + \left(1 - Y_{ij}\right)\frac{1}{C}\right)\\
    &= \frac{1}{B} \sum_{i \in \mathcal{V}_{train}}\left(\frac{Y_{ij}}{C} - Y_{ij} + \frac{1}{C} - \frac{Y_{ij}}{C}\right)\\
    &= \frac{1}{B} \sum_{i \in \mathcal{V}_{train}}\left(\frac{1}{C} - Y_{ij}\right)\\
    &= \frac{1}{B} \left(\frac{B}{C} - \sum_{i \in \mathcal{V}_{train}}Y_{ij}\right)\\
    &= \frac{1}{B} \left(\frac{B}{C} - \frac{B}{C}\right)\\
    &= 0.
\end{align*}
\end{footnotesize}
As a result, the gradient at the classification layer $\sum_{i \in \mathcal{V}_{train}} \sum_{j=1}^{C} \frac{\partial \mathcal{L}}{\partial Z_{ij}} = 0$. 
\end{proof}

Theorem~\ref{thm_gradient_vanishing} indicates if we generate class-balanced mini-batches to train a deep GCN model, the gradient at the output layer will be near 0 at the very beginning of the training process.

\subsection{Model Weights Over-decaying}
\label{subsec:weight-over-decaying}
When the gradient at the classification layer gets to 0, model weights over-decaying would occur if weight regularization (e.g., L2 loss) is used during training. Assume that regularization loss and classification loss are both included in the total loss. Theorem~\ref{thm_gradient_vanishing} points out that the over-smoothing issue causes the gradient to vanish, thus disabling the classification objective. As a result, the regularization objective plays a dominant role during training. The over-smoothing issue might be made worse by the regularization objective which decreases the norm of the weight matrices without control. Smaller weights make the output features more quickly approach zero.

\begin{remark}
In deep GCNs, over-smoothing, gradient vanishing, and weights over-decaying together cause the performance degradation problem. Over-smoothing and gradient vanishing mutually exacerbate each other, leading to more serious performance degradation. At the beginning of the training process, the gradient at the classification layer is close to zero due to the near-zero output features caused by over-smoothing. The model weights would thus drastically decrease due to the regularization objective's dominating influence when the classification objective is disabled by the zero gradient. Over-smoothing would then become worse because the successive multiplication of the input by weight matrices with small values would more easily produce zero output features. Consequently, the above issues seriously hinder the training of deep GCNs. We further provide visualizations of the three issues using GCNs with $9$ layers on Cora in Figure~\ref{fig:negative_effects_on_cora}. We can observe that (1) the vanilla GCN with and without DropNode/PairNorm still suffer from all the three issues; (2) DropEdge can only ease over-smoothing; (3) GCNs with SkipNode using uniform sampling (SkipNode-U) and biased sampling (SkipNode-B) are capable of alleviating all the issues.
\end{remark}

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.35\textwidth]{fig/SkipNode_algorithm.pdf}
    \caption{The forward propagation scheme of SkipNode. $X^{(l)}_{tmp} = \tilde{A}X^{(l-1)}W^{(l)}$. For simplicity, we omit the nonlinear function in this figure.}
    \label{fig:skip_procedure}
\end{figure}

\section{Method}
\label{sec:SkipNode}
In this section, we present the methodological details of SkipNode and explain how SkipNode alleviates all the three issues. 

\subsection{SkipNode}
\label{subsec:Methodology}

Suppose a deep GCN contains $L$ layers. Then, for each middle layer, the SkipNode generates a mask matrix $P^{(l)} \in \mathbb{R}^{N \times N}$, which is a diagonal matrix whose diagonal consists of $1$ or $0$. $P_{ii} = 1$ indicates that node $i$ is a sampled node; otherwise, it is not. Then, the $l$-th GCN layer with SkipNode can be defined as follows:
\begin{equation}
\label{eq:SkipNode}
X^{(l)} = \sigma\left((I - P^{(l)})\tilde{A}X^{(l-1)}W^{(l)} + P^{(l)}X^{(l-1)}\right),
\end{equation}
where $\sigma$ is a nonlinear function, i.e., ReLU function. The mask matrix $P^{(l)}$ is determined by the sampling strategy and sampling rate $\rho$. For those selected nodes, the ``skip'' operation suppresses the exponential smoothing effect of model depth by keeping their features unchanged in the current layer. Here, we propose two sampling strategies: \textbf{Uniform Sampling} samples the mask matrix $P$ with $P_{ii} \sim Bernoulli(\rho)$; \textbf{Biased Sampling} samples $\rho N$ ``skipped nodes'' with sampling probabilities proportional to nodes' degrees because \cite{chen2020simple} points out that nodes with higher degrees are more likely to suffer from over-smoothing in deep GCNs. We only employ SkipNode during training for each middle layer. Figure~\ref{fig:skip_procedure} describes the forward propagation scheme of SkipNode.


\begin{figure*}[ht]
        \centering
        \subfigure[Log distance ratio between each layer's output and the initial feature input.]{ 
        \includegraphics[width=0.75\linewidth]{fig/fig_log_relative_distance.pdf}
        }
        \subfigure[Log distance ratio between one layer's output with/without SkipNode.]{
        \includegraphics[width=0.75\linewidth]{fig/fig_ratio.pdf}
        }
        \caption{The effectiveness of alleviating over-smoothing. We explore (a) the log distance ratio $\log(\frac{\DMone{X^{(l)}_{2}}}{\DMone{X^{(0)}}})$ for each layer $l$ with varying $\rho$ and $s$ ($\rho=0$ is equivalent to vanilla GCN), and (b) the log distance ratio $\log(\frac{\DMone{X_{2}}}{\DMone{X_{1}}})$ for one layer calculation. All the results are averaged from $100$ runs on the same graph for each fixed combination of $\rho$ and $s$.}
        \label{fig:allievat_over_smoothing}
\end{figure*}

\subsection{Toward Alleviating Performance Degradation}
Here, we provide theoretical and empirical analysis of SkipNode's ability\footnote{For simplicity, the analysis is based on uniform sampling.} to alleviate the over-smoothing issue (recall that over-smoothing is described by the \textbf{exponentially decreasing upper bound} of the distance between output features and the lower-information subspace $\mathcal{M}$, as shown in Eq.~(\ref{eq:shrinking_distance})). Then its beneficial impact on relieving gradient vanishing and weight over-decaying is discussed.


\subsubsection{Alleviating over-smoothing}
SkipNode can naturally alleviate the exponentially decreasing upper bound issue. This is because this issue is caused by performing too many graph convolutions, and SkipNode reduces the number of convolution operations for randomly selected nodes. In the next, we further theoretically analyze the anti-over-smoothing effects of SkipNode in expectation for \textit{one layer's calculation}. We first prove that SkipNode can, in comparison to vanilla GCN, improve the upper bound coefficient $(s_l \lambda)$ (Theorem~\ref{thm1}). We then demonstrate that the output of a layer with SkipNode is, in expectation, farther away from $\mathcal{M}$ than the output of a vanilla GCN layer (Theorem~\ref{thm2}).

For clarity, we focus on an arbitrary middle layer and omit the layer index $l$ in notations; following \cite{oono2019graph}, both input and output dimensionalities are set to $d$. Let $X \in \mathbb{R}^{N \times d}$ be the input feature matrix. We denote the output of a GCN layer as $X_{1} = ReLU(\tilde{A}XW)$ and the output of a GCN layer with SkipNode as $X_{2} = (I - P)X_{1} + PX$ (since $X$ is the output of the previous layer and consequently only contains non-negative values, it is easy to verify Eq.~(\ref{eq:SkipNode}) can be written in this form). Since the layer index is removed, we abuse the notation $s$ a bit to denote it as the maximum singular value of the weight matrix $W$. Recall that $\lambda$ is the second largest magnitude of $\tilde{A}$'s eigenvalues, and $\rho \in (0, 1)$ is the sampling rate of SkipNode. The two theorems and a necessary lemma are presented as follows. 

\begin{lemma}
\label{lem1}
For any $Z$, $Y \in \mathbb{R}^{N \times d}$, we have $\DMtwo{Z + Y} \leq \DMtwo{Z} + \DMtwo{Y} + 2\DMone{Z}\DMone{Y}$ and $\DMtwo{Z - Y} \geq \DMtwo{Z} + \DMtwo{Y} - 2\DMone{Z}\DMone{Y}$.
\end{lemma}

\begin{theorem}[Higher Upper Bound]
\label{thm1}
Under Assumptions~\ref{asp1} and \ref{asp2}, for any $\rho \in (0,1)$, we have $\DMone{\mathbb{E}[X_{2}]} \leq \left(s\lambda + \rho(1 - s\lambda)\right)\DMone{X}$ compared to $\DMone{X_{1}} \leq s\lambda\DMone{X}$ (cf. Theorem 1 of \cite{oono2019graph}). In particular, when $s\lambda < 1$, SkipNode can achieve a higher upper bound, i.e., $s\lambda + \rho(1 - s\lambda) > s\lambda$.
\end{theorem}

\begin{theorem}[Longer Distance from $\mathcal{M}$]
\label{thm2}
Under Assumptions~\ref{asp1} and \ref{asp2}, when $\rho(\frac{1}{s\lambda} + 1) - 1 > 0$, SkipNode can guarantee a lower bound as $\DMone{\mathbb{E}[X_{2}]} \geq \left( \rho(\frac{1}{s\lambda} + 1) - 1\right)\DMone{X_{1}}$. In particular, when $\rho(\frac{1}{s\lambda} + 1) > 2$, the output of SkipNode is farther away from $\mathcal{M}$, i.e., $\frac{d_{\mathcal{M}}(\mathbb{E}[X_{2}])}{d_{\mathcal{M}}(X_{1})} > 1$.
\end{theorem}

\begin{proof}[Proof of Lemma~\ref{lem1}]
\label{proof_of_lemma2}
Let $(e_{m})_{m\in[N]}$ denote the orthonormal basis of $\mathbb R^{N}$, where $e_{m}$'s are the eigenvectors of $\tilde{A}$. Accordingly, we have $Z = \sum_{m=1}^{N} e_{m} \otimes w^{Z}_{m}$ and $Y =\sum_{m=1}^{N} e_{m} \otimes w^{Y}_{m}$ for some $w^{Z}_{m}, w^{Y}_{m} \in \mathbb{R}^{d}$. Then, we have
\begin{small}
\begin{align*}
    \DMtwo{Z} 
        &= inf\{\lVert Z - H \rVert^{2}_{F} | H \in \mathcal{M}\} \\
        &= inf\{\lVert \sum_{m=1}^{N} e_{m} \otimes w^{Z}_{m} - \sum_{m=1}^{M} e_{m} \otimes \tilde{w}_{m} \rVert^{2}_{F} | \tilde{w}_{m} \in \mathbb{R}^{d}\} \\
        &= inf\{\lVert \sum_{m=1}^{M} e_{m} \otimes \left(w^{Z}_{m} - \tilde{w}_{m}\right) + \sum_{m=M+1}^{N} e_{m} \otimes w^{Z}_{m} \rVert^{2}_{F} | \tilde{w}_{m} \in \mathbb{R}^{d}\} \\
        &= \lVert \sum_{m=M+1}^{N} e_{m} \otimes w^{Z}_{m} \rVert^{2}_{F} \\
        &= \sum_{m=M+1}^{N} \lVert e_{m} \otimes w^{Z}_{m} \rVert^{2}_{F} \quad (\because e_m \perp e_n, \forall m \neq n) \\
        &= \sum_{m=M+1}^{N} \lVert w_{m}^{Z}\rVert^{2}.
\end{align*}
\end{small}
Accordingly, we have $\DMtwo{Y} = \sum_{m=M+1}^{N} \lVert w_{m}^{Y}\rVert^{2}$. Then, with the help of Cauchy–Schwarz inequality, we can derive
\begin{small}
\begin{align*}
    \DMtwo{Z+Y} 
        &= \sum_{m=M+1}^{N} \lVert w_{m}^{Z} + w_{m}^{Y} \rVert^{2} \\
        &= \sum_{m=M+1}^{N} \left(\lVert w_{m}^{Z}\rVert^{2} + \lVert w_{m}^{Y} \rVert^{2} + 2 (w_{m}^{Z})^T (w_{m}^{Y}) \right)\\
        &\leq \sum_{m=M+1}^{N} \lVert w_{m}^{Z}\rVert^{2} + \sum_{m=M+1}^{N} \lVert w_{m}^{Y} \rVert^{2} \\
        &\quad + 2 \sum_{m=M+1}^{N} \lVert w_{m}^{Z}\rVert \lVert w_{m}^{Y} \rVert\\
        &\leq \DMtwo{Z} + \DMtwo{Y} + 2\sqrt{\sum_{m=M+1}^{N} \lVert w_{m}^{Z}\rVert^{2} \sum_{m=M+1}^{N} \lVert w_{m}^{Y}\rVert^{2}} \\
        &= \DMtwo{Z} + \DMtwo{Y} + 2\DMone{Z}\DMone{Y},
\end{align*}
\end{small}
and
\begin{footnotesize}
\begin{align*}
    \DMtwo{Z-Y}
        &= \sum_{m=M+1}^{N} \lVert w_{m}^{Z} - w_{m}^{Y} \rVert^{2} \\
        &\geq \sum_{m=M+1}^{N} \lVert w_{m}^{Z}\rVert^{2} + \sum_{m=M+1}^{N} \lVert w_{m}^{Y} \rVert^{2} \\
        &\quad- 2 \sum_{m=M+1}^{N} \lVert w_{m}^{Z}\rVert \lVert w_{m}^{Y} \rVert\\
       
        &\geq \DMtwo{Z} + \DMtwo{Y} - 2\DMone{Z}\DMone{Y}.
\end{align*}
\end{footnotesize}
\end{proof}


\begin{proof}[Proof of Theorem \ref{thm1}]
\label{proof1}
Since $P_{ii}$ is a Bernoulli random variable such that $P_{ii} \sim Bernoulli(\rho)$, we have $\mathbb{E}[X_{2}] = (1-\rho)X_{1} + \rho X$. Following the decomposition scheme used in Lemma~\ref{lem1}, we let $X = \sum_{m=1}^{N} e_{m} \otimes w_{m}$ and $X_{1} = \sum_{m=1}^{N} e_{m} \otimes w^{\prime}_{m}$ for some $w_{m}, w^{\prime}_{m} \in \mathbb R^{d}$. Then, we have
\begin{small}
\begin{align*}
    \DMtwo{\mathbb{E}[X_{2}]} 
        &= \DMtwo{(1-\rho)X_{1} + \rho X} \\
        &\leq \DMtwo{(1-\rho)X_{1}} + \DMtwo{\rho X} \\
        &\quad+ 2\DMone{(1-\rho)X_{1}}\DMone{\rho X} \quad (\because Lemma~\ref{lem1})\\
        &= (1-\rho)^{2}\DMtwo{X_{1}} + \rho^{2}\DMtwo{X} \\
        &\quad+ 2\rho(1-\rho)\DMone{X_{1}}\DMone{X}\\
        &\leq (1-\rho)^{2}s^{2}\lambda^{2}\DMtwo{X} + \rho^{2}\DMtwo{X}\\
        &\quad+ 2\rho(1-\rho)s\lambda \DMtwo{X} \quad (\because \DMone{X_{1}} \leq s\lambda\DMone{X})\\
        &= \left((1-\rho)s\lambda + \rho\right)^{2}\DMtwo{X}.
\end{align*}
\end{small}





Since $\rho \in (0,1)$ and $s\lambda > 0$, we have
\begin{small}
\begin{align*}
    \DMone{\mathbb{E}[X_{2}]}  &\leq \left((1-\rho)s\lambda + \rho\right)\DMone{X} \\
    &= \left(s\lambda + \rho(1 - s\lambda)\right)\DMone{X}.
\end{align*}
\end{small}
Especially, when $s\lambda < 1$, we have $s\lambda + \rho (1- s\lambda) > s\lambda$ indicating that SkipNode can achieve a higher upper bound (in expectation) than the vanilla GCN.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm2}]
\label{proof2}
Similar to Theorem~\ref{thm1}, we have
\begin{small}
    \begin{align*}
    \DMtwo{\mathbb{E}[X_{2}]} &= d^{2}\left((1-\rho)X_{1} + \rho X\right) \\
    &= \DMtwo{\rho X - (\rho - 1)X_{1}} \\
    &\geq \DMtwo{\rho X} + \DMtwo{(\rho-1)X_{1}} \\
    &\quad- 2\DMone{\rho X} \DMone{(\rho-1)X_{1}} \quad (\because Lemma~\ref{lem1})\\
    &= \rho^{2}\DMtwo{X} + (\rho - 1)^{2}\DMtwo{X_{1}} \\
    &\quad- 2|\rho (\rho - 1)| \DMone{X}\DMone{X_{1}} \\
    &= \left(\rho\DMone{X} - (1 - \rho) \DMone{X_{1}}\right)^{2}.
    \end{align*}
\end{small}

Since the operand of the square could be negative, we consider the following two cases (the ``='' case is not considered since it results in a trivial lower bound, i.e., 0).

\textbullet\
\textbf{CASE 1:} $\rho\DMone{X} < (1 - \rho) \DMone{X_{1}}$

It implies $\frac{1}{s\lambda} \leq \frac{\DMone{X}}{\DMone{X_{1}}} < \frac{1-\rho}{\rho}$. Therefore, $\frac{1-\rho}{\rho} > \frac{1}{s\lambda}$ is the necessary condition for this case. The lower bound becomes $\DMone{\mathbb{E}[X_{2}]} \geq (1 - \rho)\DMone{X_{1}} - \rho \DMone{X} = \DMone{X_{1}} -\rho (\DMone{X_{1}} + \DMone{X})$, which is definitely less than $\DMone{X_{1}}$. Hence, this case cannot guarantee $\DMone{\mathbb{E}[X_{2}]} \geq \DMone{X_{1}}$, no matter how we set $\rho$.


\textbullet\
\textbf{CASE 2:} $\rho\DMone{X} > (1 - \rho) \DMone{X_{1}}$

It indicates $\frac{\DMone{X}}{\DMone{X_{1}}} > \frac{1 - \rho}{\rho}$. Since $\frac{\DMone{X}}{\DMone{X_{1}}} \geq \frac{1}{s\lambda}$, $\frac{1}{s\lambda} > \frac{1 - \rho}{\rho}$ is a sufficient condition for this case. This condition is also required to assure the following lower bound nontrivial (i.e., with simple transformation, we have $\rho(\frac{1}{s\lambda} + 1) - 1 > 0$):
\begin{small}
    \begin{align*}
    \DMone{\mathbb{E}[X_{2}]} 
        &\geq \rho\DMone{X} - (1 - \rho) \DMone{X_{1}} \\
        &\geq \left( \rho(\frac{1}{s\lambda} + 1) - 1\right)\DMone{X_{1}}.
    \end{align*}
\end{small}
In particular, when $\rho(\frac{1}{s\lambda} + 1) > 2$, we can guarantee $\DMone{\mathbb{E}[X_{2}]} \geq \DMone{X_{1}}$ because:
\begin{small}
    \begin{align*}
    \frac{\DMone{\mathbb{E}[X_{2}]}}{\DMone{X_{1}}} \geq \rho(\frac{1}{s\lambda} + 1) - 1 > 1.
\end{align*}
\end{small}
\end{proof}


\begin{remark}
Theorem~\ref{thm1} indicates that SkipNode can help GCN increase the upper bound of the distance between output features and $\mathcal{M}$ in expectation when $s\lambda < 1$. This bound is better than $\DMone{X_{1}} \leq s\lambda\DMone{X}$ in theory since the Cauchy-Schwarz inequality could be tight when $\{w_m\}$ and $\{w^{\prime}_{m}\}$ have a (nearly) scaling relationship. Theorem~\ref{thm2} underlines SkipNode can enhance GCN to obtain the output that is, in expectation, farther away from $\mathcal{M}$ in the case of $\rho(\frac{1}{s\lambda} + 1) > 2$. The conditions $s\lambda < 1$ (Theorem~\ref{thm1}) and $\rho(\frac{1}{s\lambda} + 1) > 2$ (Theorem~\ref{thm2}) could be easily satisfied in practice: $s < 1$ since the weight matrices are often initialized with small values and norm-constrained to avoid over-fitting; $\lambda < 1$ always holds. Taking the GCN model in Cora dataset as a typical example, we have $\lambda \approx 0.996$ and $s \approx 0.2$, leading to $s\lambda \approx 0.199 < 1$. In this case, $\rho > 0.34$ suffices to secure $\DMone{\mathbb{E}[X_{2}]} \geq \DMone{X_{1}}$ in Theorem~\ref{thm2}. Besides, keeping $s$ fixed, the larger and denser the graph is ($\lambda$ decreases), the higher the upper bound in Theorem~\ref{thm1} becomes, and the wider the range of $\rho$ satisfying Theorem~\ref{thm2}'s condition goes.
\end{remark}

To further empirically validate the effectiveness of SkipNode, we generate an Erd\H{o}s -- R\'{e}nyi graph~\cite{erdos1959random,gilbert1959random} with $500$ nodes and edge generation probability $0.5$. Then, we vary $s$ and $\rho$ to investigate the performance of SkipNode for alleviating over-smoothing. We conduct $100$ runs for each $(\rho,s)$ combination where the input features and weight matrices are initialized randomly for each run. The averaged results are shown in Figure~\ref{fig:allievat_over_smoothing}. Figure~\ref{fig:allievat_over_smoothing}(a) shows that the log distance ratio $ \log(\frac{\DMone{X^{(l)}_{2}}}{\DMone{X^{(0)}}})$ of SkipNode ($\rho > 0$) is vastly larger than that of vanilla GCN ($\rho = 0$) at all the middle layers. This should be because SkipNode can improve both exponent and base parts of the convergence speed coefficient $(s\lambda)^L$. Moreover, it demonstrates that the convergence speed decreases with $\rho$ increasing, which is consistent with the upper bound analysis in Theorem~\ref{thm1}, i.e., the base part of the coefficient $(s\lambda)^L$ is increased by $\rho(1-s\lambda)$. Figure~\ref{fig:allievat_over_smoothing}(b) explores the log distance ratio $ \log(\frac{\DMone{X_{2}}}{\DMone{X_{1}}})$ for one layer calculation. We can see the log ratio is always larger than 0 (that is $\log 1$), and on average $\DMone{X_{2}}$ is around 50 times ($e^4$) farther away from $\mathcal{M}$ than $\DMone{X_{1}}$. Figure~\ref{fig:allievat_over_smoothing}(b) also indicates that increasing $\rho$ or decreasing $s$ can expand the gap between $\DMone{X_{2}}$ and $\DMone{X_{1}}$, which is consistent with the obtained lower bound of the ratio in expectation in Theorem~\ref{thm2}, i.e., $\rho(\frac{1}{s\lambda} + 1) - 1$. 


The above analysis supports the effectiveness of the ``skipping'' operation for alleviating over-smoothing. Unlike uniform sampling that samples nodes with equal probability, biased sampling tends to choose high-degree nodes which suffer more from being smoothed. It can be analogous to using different $\rho$ for different $P_{ii}$ according to $v_{i}$'s degree. Therefore, we could still maintain the effectiveness of SkipNode with biased sampling. 

\subsubsection{Alleviating gradient vanishing and weight over-decaying}
Here we explain why SkipNode can alleviate the back-propagation-induced and over-smoothing-induced gradient vanishing issues. Assume that the graph signal $\boldsymbol{x}$ is transformed by $\theta_{l}, l \in [L]$ and we have $\boldsymbol{x}^{(l)} = \theta_{l}\boldsymbol{x}^{(l-1)}$ (we omit the feature propagation step since transformation is the main cause of back-propagation-induced gradient vanishing). Therefore, the gradient from the classification loss function $f(\boldsymbol{x}^{(L)})$ to $\boldsymbol{x}^{(0)}$ is
\begin{small}
    \begin{align*}
    \frac{\partial f(\boldsymbol{x}^{(L)})}{\partial \boldsymbol{x}^{(0)}} &= \frac{\partial f(\boldsymbol{x}^{(L)})}{\partial \boldsymbol{x}^{(L)}} \frac{\partial \boldsymbol{x}^{(L)}}{\partial \boldsymbol{x}^{(L-1)}}\cdots\frac{\partial \boldsymbol{x}^{(1)}}{\partial \boldsymbol{x}^{(0)}}\\
    &=  (\prod_{l=1}^{L}\theta_{l})\frac{\partial f(\boldsymbol{x}^{(L)})}{\partial \boldsymbol{x}^{(L)}}.
\end{align*}
\end{small}
If $|\theta_{l}| <1 $, the successive multiplication of $\theta_{l}$ will converge to zero, leading to (nearly) zero gradient. SkipNode can reduce the times of successive multiplication by letting randomly selected nodes skip several transformations to slow down the convergence speed. The over-smoothing-induced gradient vanishing issue (Theorem~\ref{thm_gradient_vanishing}) is caused by (nearly) zero output which is in turn caused by over-smoothing (cf. Proposition 3 of~\cite{oono2019graph}). SkipNode can also effectively relieve this issue by skipping several layers' calculation in the forward phase of GCNs.

As we have analyzed in Sec.~\ref{subsec:weight-over-decaying}, the model weights over-decaying issue is triggered by gradient vanishing when regularization is used. Since SkipNode can alleviate both over-smoothing and gradient vanishing, the model weights are thus updated by the gradient passed from the classification layer. In contrast to vanilla deep GCNs, SkipNode can keep model weights at reasonable levels.

\begin{table}[ht]
    \caption{Dataset Statistics.}
    \label{tab:data_sta}
    \centering
    \begin{tabular}{c c c c c c}
        \toprule
        Category & Dataset &  \#Nodes & \#Edges & \#Features\\
        \midrule
        \multirow{3}{*}{Homophilic} & Cora & $2,708$ & $5,429$ & $1,433$\\ 
        ~ & Citeseer & $3,327$ & $4,732$ & $3,703$\\
        ~ & Pubmed & $19,717$ & $44,338$ & $500$\\
        \midrule
        \multirow{4}{*}{Heterophilic} & Chameleon & $2,277$ & $36,101$ & $2,325$\\
        ~ & Cornell & $183$ & $295$ & $1,703$\\
        ~ & Texas & $183$ & $309$ & $1,703$\\
        ~ & Wisconsin & $251$ & $499$ & $1,703$\\
        \midrule
        \multirow{2}{*}{Large-scale} & ogbn-arxiv & $169,343$ & $1,166,243$ & $128$ \\
        ~ & ogbl-ppa & $ 576,289$ & $ 30,326,273$ & $58$\\
        \bottomrule
    \end{tabular}
\end{table}

\begin{table*}[ht]
    \centering
    \caption{\centering{Full-supervised Classification Accuracy (\%) on Different Graphs. Wisconsin is not a supported datatset in the code of GPRGNN and APPNP.}}
    \begin{tabular}{c c | c c c c c c c | c}
         \toprule 
         Backbone & Strategy & Cora & Citeseer & Pubmed & Chameleon & Cornell & Texas & Wisconsin & Avg. Gain\\
        \midrule
         \multirow{4}{*}{GCN}  & -
          & 86.1 & 79.1 & 86.2 & 42.1 & 70.2 & 67.5 & 60.7 & -\\
          
         ~ & DropEdge
         & 88.9 & 79.2 & 86.9 & 42.3 & 73.9 & 70.2 & 62.7 & 2.5\%\\
         ~ & \textbf{SkipNode-U}
         & \textbf{89.7} & \textbf{79.4} & 87.0 & \textbf{43.2} & 75.6 & \textbf{72.9} & 62.7 & 3.9\%\\
         
         ~ & \textbf{SkipNode-B} & \textbf{89.7} & 79.2 & \textbf{87.3} & \textbf{43.2} & \textbf{78.3} & 70.2 & \textbf{68.6} & \textbf5.2\%\\
         
         \midrule
         \multirow{4}{*}{JKNet} & - & 88.4 & 77.1 & 87.2 & 40.5 & 70.2 & 72.2 & 62.7 & -\\

         ~ & DropEdge & 88.4 & 78.3 & 87.9 & 41.2 & 71.3 & 72.9 & 64.7 & 1.4\%\\

         ~ & \textbf{SkipNode-U}
         & 89.3 & \textbf{79.4} & \textbf{88.0} & 41.0 & \textbf{75.6} & \textbf{75.6} & \textbf{66.6} & 3.5\%\\

         ~ & \textbf{SkipNode-B}
         & \textbf{89.7} & 79.0 & 87.7 & \textbf{42.3} & \textbf{75.6} & \textbf{75.6} & \textbf{66.6} & \textbf{3.9\%} \\

        \midrule
         \multirow{4}{*}{Incep.} & - & 88.0 & 76.6 & \textbf{87.9} & 41.6 & 75.6 & 70.2 & 60.7 & -\\

         ~ & DropEdge & \textbf{88.3} & 77.1 & 87.5 & 42.0 & \textbf{78.3} & 70.2 & 62.7 & 1.1\%\\

         ~ & \textbf{SkipNode-U} & 87.5 & \textbf{77.3} & 87.2 & \textbf{42.1} & 78.0 & 70.2 & 62.7 & 1.0\%\\

         ~ & \textbf{SkipNode-B} & 87.5 & \textbf{77.3} & 87.6 & 40.5 & \textbf{78.3} & \textbf{72.9} & \textbf{64.7} & \textbf{1.6\%}\\

        \midrule
         \multirow{4}{*}{GCNII} & - & 88.4 & 77.0 & 89.5 & 60.2 & 74.8 & 69.4 & \textbf{74.1} & -\\

         ~ & DropEdge & 88.0 & 76.8 & 87.8 & 59.6 & 75.0 & 72.9 & 73.3 & 0.1\%\\

         ~ & \textbf{SkipNode-U} & \textbf{88.6} & 77.3 & \textbf{89.7} & \textbf{60.9} & \textbf{75.4} & \textbf{77.6} & 73.7 & \textbf{2.0\%}\\

         ~ & \textbf{SkipNode-B} & 88.4 & \textbf{77.8} & 88.8 & 60.2 & \textbf{75.4} & 70.5 & 73.1 & 0.2\%\\
         
         \midrule
         \multirow{4}{*}{GRAND} & -
         & 87.4 & 76.2 & 86.2 & 42.3 & 58.9 & 58.9 & 56.4 & -\\
         
         ~ & DropEdge
         & 87.5 &  76.2 &  86.1 &  \textbf{44.2} &  58.1 &  57.5 &  56.8 & 0.2\%\\
         ~ & \textbf{SkipNode-U} &  \textbf{88.4} & 76.1 & 86.1 & 43.2 & 58.9 & 58.9 & 56.0 & 0.3\%\\
         
         ~ & \textbf{SkipNode-B} &  88.1 & \textbf{76.6} & \textbf{86.3} & \textbf{44.2} & \textbf{60.0} & \textbf{59.4} & \textbf{57.2} & \textbf{1.4\%}\\
         
         \midrule
         \multirow{4}{*}{GPRGNN} & - &  88.0 & 78.9 & 86.9 & 54.7 & 69.0 & 57.2 & - & -\\
         ~ & DropEdge &  88.1 &  78.6 &  86.6 &  54.4 &  69.1 &  57.3 &  - & -0.1\% \\
         
         ~ & \textbf{SkipNode-U} & \textbf{88.6} & \textbf{79.6} & \textbf{87.5} & \textbf{55.0} & \textbf{69.8} & 57.0 & - & 0.6\% \\
         
         ~ & \textbf{SkipNode-B} &  88.4 & 79.1 & 87.0 & 54.6 & 69.3 & \textbf{64.5} & - & \textbf{2.3\%} \\
         
         \midrule
         \multirow{4}{*}{APPNP}& - &  86.4 &  78.4 &  84.3 &  50.0 &  55.4 &  56.0 &  - & -\\
         
          ~ & DropEdge &  87.1 &  79.6 &  83.6 &  \textbf{51.2} &  55.7 &  57.4 &  - & 1.2\%\\
          
         ~ & \textbf{SkipNode-U} & \textbf{87.8} & \textbf{80.6} & 84.5 & \textbf{51.2} & \textbf{56.5} & \textbf{58.3} & - & \textbf{2.2\%}\\
         
         ~ & \textbf{SkipNode-B} & 87.5 & 80.2 & \textbf{84.8} & 51.1 & 56.4 & 56.7 & - & 1.6\%\\
         \bottomrule
    \end{tabular}

    \label{table:full-accuracy} 
\end{table*}

\begin{table}[ht]
    \centering
    \caption{\centering{Node Classification Accuracy (\%) on A Large Graph, i.e., ogbn-arxiv. $L = n$ indicates a n-layer model.}} 
    \begin{tabular}{c c | c c c c}
         \toprule
         Backbone & Strategy & L = 10 & L = 12 & L = 14 & L = 16 \\
         \midrule
         \multirow{4}{*}{GCN} & -
         & 66.5 & 62.3 & 58.7 & 53.2\\

         ~ & DropEdge
          & 66.7 & 62.8 & 60.3 & 55.1 \\

         ~ & \textbf{SkipNode-U}
         & \textbf{67.3} & \textbf{65.6} & 62.0 & 56.3\\
       
         ~ & \textbf{SkipNode-B} & 67.0 & 65.4 & \textbf{62.1} & \textbf{58.5} \\
         \bottomrule
    \end{tabular}
    \label{table:ogbn-arxiv-accuray} 
\end{table} 

\section{Experiments}
In this section, we evaluate our SkipNode on various graph datasets and tasks to validate its generalizability and effectiveness.

\subsection{Datasets}
We use 9 graph datasets, and their detailed statistics are described in Table~\ref{tab:data_sta}. These datasets fall into three categories as follows.

\vspace{2mm} \noindent \textbf{Homophilic Graphs}: 

\textbullet\ 
\textbf{Cora}\footnotemark[3] is a citation network in which each publication is defined by a 0/1-valued word vector indicating the presence or absence of the corresponding dictionary word. Each publication falls under one of seven categories. There are 2708 nodes and 5429 edges in the dataset.

\textbullet\ 
\textbf{Citeseer}\footnotemark[3] is a citation network with 3327 nodes and 4732 edges connecting them. There are six classes in total.

\textbullet\ 
\textbf{Pubmed}\footnotemark[3] collects 19717 publications from PubMed database. A TF/IDF weighted word vector from a vocabulary of 500 unique terms is used to describe each publication in the dataset. There are three clusters.

\footnotetext[3]{\url{https://linqs.soe.ucsc.edu/data}}

\begin{table}[ht]
    \centering
     \caption{Link Prediction Results of GCN on ogbl-ppa.}
     \begin{tabular}{c c c | c c c}
         \toprule
         Metric & Backbone & Strategy & L = 4 & L = 6 & L = 8 \\
         \midrule
         \multirow{3}{*}{Hits@10} & \multirow{3}{*}{GCN} & - & 3.19 & 5.29 & 3.68\\
         ~ & ~ & \textbf{SkipNode-U} & 3.11 & \textbf{5.86} & \textbf{7.25}\\
         ~ & ~ & \textbf{SkipNode-B} & \textbf{3.48} & 5.72 & 5.86\\
         
         \midrule
         \multirow{3}{*}{Hits@50} & \multirow{3}{*}{GCN} & - & 11.92 & 13.61 & 12.83\\
         ~ & ~ & \textbf{SkipNode-U} & 12.01 & \textbf{14.95} & 14.39\\
         ~ & ~ & \textbf{SkipNode-B} & \textbf{13.31} & 14.17 & \textbf{14.95}\\
         
         \midrule
         \multirow{3}{*}{Hits@100} & \multirow{3}{*}{GCN} & - & 17.11 & 18.54 & 16.50\\
         ~ & ~ & \textbf{SkipNode-U} & \textbf{17.57} & \textbf{18.92} & \textbf{19.08}\\
         ~ & ~ & \textbf{SkipNode-B} & 17.54 & 18.74 & 18.92\\
         
         \bottomrule
    \end{tabular}
    \label{tab:ogbl-ppa-accuracy}
\end{table}

\vspace{2mm} \noindent \textbf{Heterophilic Graphs}:

\textbullet\ 
\textbf{Chameleon}\footnotemark[4] is a page-to-page network dedicated to the topic of chameleon. The information was gathered from the English Wikipedia. Articles are represented by nodes, and mutual links between them are represented by edges. Each article is described by a 0/1-valued vector, with 1 indicating the presence of an informative noun in the Wikipedia article's text.

\footnotetext[4]{\url{http://snap.stanford.edu/data/wikipedia-article-networks.html}}
\textbullet\ 
\textbf{Cornell}, \textbf{Texas}, and \textbf{Wisconsin}\footnotemark[5] are the subdatasets from the webpage dataset collected from computer science departments of various universities. Each page (node) is represented by the bag-of-words representation and can be classified into one of five categories. The edges between nodes represent web page hyperlinks.

\footnotetext[5]{\url{http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/}}

\vspace{2mm} \noindent \textbf{Large-scale Graphs}:

\textbullet\ 
\textbf{ogbn-arxiv}\footnotemark[6] is a paper citation network of arXiv papers and the dataset is extracted from the Microsoft Academic Graph. A 128-dimensional feature vector is generated for each paper (node) in the dataset by averaging the embeddings of words in the title and abstract.

\textbullet\ 
\textbf{ogbl-ppa}\footnotemark[6] is a protein-protein association network. Nodes represent proteins from 58 different species, and edges indicate biologically meaningful associations between proteins.

\footnotetext[6]{\url{https://github.com/snap-stanford/ogb}}


\begin{table*}[!ht]
    \centering
    \caption{\centering{Semi-supervised Classification Accuracy (\%) w.r.t Different Depth. OOM indicates Out-Of-Memory on a 16 GB GPU.}}
    \resizebox{1.0\textwidth}{!}{
    \begin{tabular}{c c | c c c c c | c c c c c | c c c c c}
    \toprule
    \multirow{2}{*}{Backbone} & \multirow{2}{*}{Strategy} & \multicolumn{5}{c|}{Cora} & \multicolumn{5}{c|}{Citeseer} & \multicolumn{5}{c}{Pubmed} \\

    ~ & ~ &L = 4 &L = 8 &L = 16 &L = 32 &L = 64 &L = 4 &L = 8 &L = 16 &L = 32 &L = 64 &L = 4 &L = 8 &L = 16 &L = 32 &L = 64 \\
    \midrule
    \multirow{4}{*}{GCN} & - & 82.3 & 79.9 & 32.5 & 33.8 & 31.9 & 69.6 & 63.2 & 24.2 & 24.5 & 23.1 & \textbf{79.0} & 78.5 & 40.7 & 41.3 & 43.7 \\

    ~ & DropEdge
    & 80.1 & 79.8 & 32.4 & 35.6 & 31.9 & 68.5 & 64.5 & 23.1 & 24.1 & 23.3 & 78.4 & 77.7 & 41.3 & 41.3 & 41.3 \\
    
    ~ & \textbf{SkipNode-U}
    & 82.5 & 80.6 & \textbf{72.3} & \textbf{52.9} & 31.9 & \textbf{72.4} & 69.8& 53.0 &32.9& \textbf{26.8} & 78.9 &79.4& \textbf{78.3} & 56.9&45.7\\

    ~ & \textbf{SkipNode-B}
    & \textbf{83.3} & \textbf{81.3} & 59.9 & 42.4 & \textbf{33.4} & 72.1 & \textbf{71.3} & \textbf{60.6} &\textbf{34.3} & 25.7&78.9& \textbf{80.1} &73.0& \textbf{68.3} & \textbf{48.2}\\
    
    \midrule
    \multirow{4}{*}{ResGCN} & - 
    & 82.1 & 76.3 & 64.4 & 33.5 & 31.9 & 67.9  & 60.8  & 58.6  & 39.4  & 29.5  & 79.3 & 77.2 & 46.6 & 41.3 & 43.5\\
    
    ~ & DropEdge 
    & 81.7 & 78.2 & 61.3 & 54.3 & 31.9 & 67.2  & 61.8  & 57.0  & 29.3  & 23.2  & 77.5 & 76.9 & 72.3 & 41.3 & 42.6\\

    ~ & \textbf{SkipNode-U}
    & 83.3 & \textbf{79.8} & 66.2 & 69.1 & \textbf{37.5} & \textbf{71.5}  & 70.0  & \textbf{60.3}  & \textbf{53.5}  & 51.9  & \textbf{81.1} & 79.4 & \textbf{76.6} & 41.3 & \textbf{52.4}\\

    ~ & \textbf{SkipNode-B}
    & \textbf{83.7} & 79.7 & \textbf{69.9}  & \textbf{76.6} & 31.9 & 71.3  & \textbf{71.1}  & 59.8  & 40.7  & \textbf{53.6}  & 79.7 & \textbf{79.7} & 74.2 & \textbf{43.4} & 49.4\\
    
    \midrule
    \multirow{4}{*}{JKNet} & - & 82.2 & 81.7 & 81.7 & \textbf{80.8} & 78.0 & 68.0 & 68.7 & 67.1 & 68.0 & 64.2 & 79.1 & 79.5 & 78.7 & 78.6 & 78.5\\
    
    ~ & DropEdge & 82.3 & 79.7 & 79.8 & 80.0 & \textbf{79.8} & 69.7 & 67.9 & 67.0 & 65.5 & 62.9 & 79.1 & 77.8 & 76.7 & 77.6 & 77.8\\

    ~ & \textbf{SkipNode-U}
    & 83.3 & \textbf{82.1} & 81.7 & 79.6 & 79.2 & 72.9 & \textbf{70.8} & 67.6 & 68.7 & 63.1 & \textbf{80.6} & \textbf{80.2} & 79.0 & 79.7 & \textbf{80.2}\\

    ~ & \textbf{SkipNode-B}
    & \textbf{83.7} & 81.4 & \textbf{81.8} & 79.2 & 79.3 & \textbf{74.0} & 70.5 & \textbf{68.6} & \textbf{68.9} & \textbf{64.9} & 80.4 & 80.1 & \textbf{79.3} & \textbf{79.8} & 78.9\\
    
    \midrule
    \multirow{4}{*}{Incep.}& - & 82.8 & 82.4 & 82.7 & 79.3 & 78.8 & 71.0 & 70.2 & 68.3 & 64.0 & 63.9 & 79.3 & 78.7 & 78.6 & OOM & OOM\\
    ~ & DropEdge & 82.5 & 81.5 & 79.4 & 77.3 & 78.2 & 70.3 & 69.2 & 70.6  & 65.9 & 64.2 & 78.8 & 78.0  & 77.3 & - & -\\

    ~ & \textbf{SkipNode-U}
    & \textbf{83.2} & \textbf{83.7} & \textbf{83.8} & \textbf{81.9} & 78.4 & 71.5 & \textbf{70.8} & 71.8 & 66.7 & \textbf{65.5} & \textbf{80.2} & \textbf{79.0}  & 79.1 & - & -\\

    ~ & \textbf{SkipNode-B}
    & 83.0 & 82.5 & 82.1 & 80.1 & \textbf{79.8} & \textbf{71.6} & 70.4 & \textbf{72.6} & \textbf{68.0} & 64.6 & 79.6 & 78.9 & \textbf{79.9} & - & -\\
    
    \midrule
    \multirow{4}{*}{GCNII} & - & 82.6 & 84.2 & \textbf{84.6} & 85.4 & 85.9 & 68.9 & 70.6 & 72.9 & 72.3 & 73.4 & 78.8 & 79.3 & 80.2 & 79.8 & 79.7\\

    ~ & DropEdge & 82.2 & 82.5 & 83.3 & 83.4 & 78.6 & 66.1 & 69.2 & 72.5 & 71.8 & 73.1 & 77.6 & 78.4 & 79.4 & 78.1 & 79.2\\
    
    ~ & \textbf{SkipNode-U}
    &\textbf{83.7}&\textbf{84.6}&\textbf{84.6}&\textbf{85.5}&\textbf{86.3}&\textbf{72.8}&73.1&\textbf{73.7}&\textbf{74.2}&\textbf{73.7}&78.9&80.4&81.5&80.1&\textbf{80.6}\\

    ~ & \textbf{SkipNode-B}
    &83.5&83.9&84.1&85.1&85.0&72.6&\textbf{73.3}&73.2&73.5&73.4&\textbf{79.4}&\textbf{80.7}&\textbf{81.9}&\textbf{81.0}&80.4\\
   
    \bottomrule
    \end{tabular}
    }
  \label{table:semi-accuracy} 
\end{table*}

\subsection{Tasks}
We evaluate our SkipNode on various graph datasets through different tasks as follows:

\textbullet\
\textbf{Semi-supervised node classification task:} We use three widely-used graphs, including Cora, Citeseer, and Pubmed under public splits~\cite{yang2016revisiting} (20 nodes per class as training data, 500/1000 nodes as validation/test data).

\textbullet\ 
\textbf{Full-supervised node classification task:} We use Cora, Citeseer, Pubmed, Chameleon, Cornell, Texas, and Wisconsin under ten different splits ($60\%$, $20\%$ and $20\%$ for training, validation, and test). 

\textbullet\
\textbf{Node classification task on a large-scale graph:} We choose a challenging dataset, ogbn-arxiv. Papers published until 2017 are used as training data, those published in 2018 are used as validation data, and those published since 2019 are used as test set.

\textbullet\ 
\textbf{Link prediction task}: We evaluate SkipNode on ogbl-ppa and the evaluation metric is the ratio of predicted positive edges that are ranked at the K-th place or above (Hits@K).

\subsection{Implementation Details}

\vspace{2mm} \noindent \textbf{Hardware}. All the experiments are conducted on a single NVIDIA Tesla V100 4096 Ti with 16 GB memory. The CPU is Intel Xeon E5-2650 v4 with 200 GB main memory.

\vspace{2mm} \noindent \textbf{Backbones Models}. We adopt GCN~\cite{kipf2016semi}, JKNet~\cite{xu2018representation}, InceptGCN~\cite{kazi2019inceptiongcn}, ResGCN~\cite{kipf2016semi}, GCNII~\cite{chen2020simple}, GPRGNN~\cite{chien2021adaptive}, APPNP~\cite{klicpera2018predict}, and GRAND~\cite{feng2020graph} as backbone models. 

\vspace{2mm} \noindent \textbf{Strategies}. We adopt DropEdge~\cite{rong2019dropedge}, PairNorm~\cite{zhao2019pairnorm}, and DropNode~\cite{do2021graph} as comparing anti-over-smoothing strategies against our SkipNode\footnotemark[7].

\footnotetext[7]{\url{https://github.com/WeigangLu/SkipNode}}

\vspace{2mm} \noindent \textbf{Hyperparameters}. For a fair comparison, we first perform grid hyper-parameter searching for each backbone model and obtain all the hyperparameters based on the best accuracy of the validation set of each benchmark. Then, we adopt SkipNode and other comparing strategies by only tuning the new strategy-related hyperparameter and dropout rate while fixing the other hyperparameters.
For all the backbone models, we search dropout rate in $\{0, 0.05, 0.1, \cdots, 0.8\}$, weight decay rate in $\{5e-4, 5e-7, 5e-9\}$, learning rate in $\{0.01, 0.05, 0.1\}$ and set hidden dimensionality to 64. 
For SkipNode, DropEdge, and DropNode, we search their sampling rates in $\{0, 0.05, 0.1, \cdots, 0.8, 0.9\}$. For PairNorm, we directly use the suggested hyperparameters in its source code. We use \textbf{SkipNode-U} and \textbf{SkipNode-B} to denote SkipNode with \textit{uniform sampling} and \textit{biased sampling}, respectively.


\subsection{Performance Studies}

\subsubsection{Generalizability}
To demonstrate the generalizability of SkipNode, we evaluate it on two common tasks, i.e., full-supervised node classification and link prediction, on various graphs with different homophily and scales. 

Table~\ref{table:full-accuracy} summarizes the accuracy of full-supervised node classification on seven graphs, including three homophilic and four heterophilic graphs. We can observe that SkipNode obtains better performance in the most cases, indicating that SkipNode is a model- and graph-agnostic strategy. 
We further validate SkipNode's generalizability on larger-scale graphs. 
Specifically, we evaluate GCN with SkipNode on ogbn-arxiv. The results are recorded in Table~\ref{table:ogbn-arxiv-accuray} (considering the computational cost, we only use GCN as the backbone). We can see that SkipNode is able to achieve better performance with various depth, implying its good generalizability.
Besides, we conduct link prediction of GCN with SkipNode, which can also reflect the quality of node representations. The results in Table~\ref{tab:ogbl-ppa-accuracy} demonstrate that SkipNode is also useful for GCN to alleviate performance degradation in link prediction task. With the help of SkipNode, the performance of GCN increases as the model goes deeper.

\begin{figure*}[ht]
        \centering
        \subfigure[Accuracy]{               
        \includegraphics[width=0.58\linewidth]{fig/fig_rho.pdf}
        }
        \hspace{0.2in}
        \subfigure[MAD value]{
        \includegraphics[width=0.2\linewidth]{fig/fig_smoothness.pdf}
        }
        \caption{Hyperparameter Studies: Accuracy and MAD Value of GCN, GCN (SkipNode-U), and GCN (SkipNode-B) with 32 Layers w.r.t Various $\rho$.}
        \label{fig:rho_analysis}
\end{figure*}

\subsubsection{Effectiveness}
To verify the effectiveness of SkipNode for alleviating performance degradation in deep GCNs, we apply it on different models with various depth. 

We first evaluate our SkipNode for the semi-supervised node classification task on three popular graphs, i.e., Cora, Citeseer, and Pubmed. Specifically, all the models are trained with various depth $L \in \{4, 8, 16, 32, 64\}$. Table~\ref{table:semi-accuracy} presents the results. The best performance w.r.t. mode depth of each baseline is highlighted by boldface. We can observe that SkipNode effectively enhances most models with different depth. 
To further compare SkipNode with other strategies, we use GCN and InceptGCN with SkipNode, DropEdge, DropNode, and PairNorm in Table~\ref{table:accuracyofDropNodeDropEdge} (we choose $L \in \{3,5,7,9\}$ since DropNode scheme requires odd model depth). SkipNode shows significant improvement against the comparing strategies, indicating its superior effectiveness.


\begin{table}[ht]
    \centering
    \caption{\centering{Performance Comparison with DropEdge/DropNode/PairNorm on Cora.}}
    \begin{tabular}{c c |c c c c}
    \toprule
    Backbone & Strategy  & L = 3 & L = 5 & L = 7 & L = 9\\
    \midrule
    \multirow{6}{*}{GCN} & - & 82.3 & 80.6 & 79.1 & 78.4 \\
    ~ & DropEdge & 81.3 & 79.9 & 77.3 & 78.7 \\
    ~ & DropNode & 82.5 & 79.4 & 44.2 & 33.1 \\
    ~ & PairNorm & 81.9 & 79.1 & 79.8 & 78.6   \\
    ~ & \textbf{SkipNode-U} & \textbf{82.9} & \textbf{82.7} & \textbf{82.1} & \textbf{81.2} \\
    ~ & \textbf{SkipNode-B} & 82.8 & 82.3 & 81.4 & 80.2 \\
    \midrule
    \multirow{6}{*}{Incep.}& - & 82.0 & 82.3 & 80.4 & 82.2 \\
    ~ & DropEdge & 81.7 & 82.0 & 79.8 & 81.9 \\
    ~ & DropNode & 81.5 & 81.7 & 78.2 & 80.5 \\
    ~ & PairNorm & 82.3 & 80.3 & 80.5 & 80.0 \\
    ~ & \textbf{SkipNode-U} & 82.4 & \textbf{82.7} & \textbf{81.0} & 82.5 \\
    ~ & \textbf{SkipNode-B} & \textbf{82.5} & 82.5 & 80.8 & \textbf{82.7} \\
    \bottomrule
    \end{tabular}
    \label{table:accuracyofDropNodeDropEdge} 
\end{table}

\subsection{Hyperparameter Studies}
The sampling rate $\rho$ is the only one parameter of our SkipNode. Therefore, in this experiment, we investigate its sensitivity. Specifically, we fix the number of model depth, the hidden dimensionality, the learning rate, and the weight decay at $32$, $64$, $0.01$, and $0.0005$, respectively. The range of $\rho$ is $\{0.1, 0.2, \cdots, 0.9\}$, and each trail is conducted with $500$ epochs. 
We use the best performance of GCN as the baseline and apply SkipNode by tuning different $\rho$. The results are illustrated in Figure~\ref{fig:rho_analysis}(a). We can observe that SkipNode achieves better performance with a larger sampling rate since the over-smoothing issue is much serious in such deep GCN. 
Besides, we further explore the smoothness of the learned features (output from the second-to-last layer) by MAD metric~\cite{chen2020measuring}, which is the mean of the average cosine distance from nodes to their connected nodes. In Figure~\ref{fig:rho_analysis}(b), we show the MAD value of the learned features after $500$ training epochs. We can see, on each dataset, the MAD value returned by GCN is always zero, indicating its poor feature diversity. In comparison, SkipNode successfully maintains information diversities as feature propagating.


\subsection{Efficiency Study}
We also examine the computational cost of SkipNode compared to other comparing strategies. The detailed time cost (average running time per epoch) of DropNode, DropEdge, PairNorm, and SkipNode on Cora are shown in Table~\ref{tab:efficency-analysis}. We can observe that DropEdge and DropNode lead to the overburden of training GCN. This may be because that they need to re-normalize adjacency matrices after each sampling operation. Our SkipNode and PairNorm show better efficiency. For SkipNode, its major computational cost depends on the masking operation, and the masking matrix is a very sparse diagonal matrix. Therefore, the involved matrix multiplication operations are quite efficient.

\begin{table}[ht]
    \centering
    \caption{\centering{Efficiency Evaluation on Cora: Average Running Time Per Epoch(ms) w.r.t Different Depth.}}
    \begin{tabular}{c c | c c c c}
        \toprule
        Backbone & Strategy & L = 3 & L = 5 & L = 7 & L = 9 \\
        \midrule
        \multirow{6}{*}{GCN} & - & 6.5 & 8.7 & 12.6 & 14.0\\

        ~ & DropEdge & 23.4 & 29.5 & 36.6 & 41.2\\
        
        ~ & DropNode & 13.4 & 23.6 & 34.1 & 40.6\\
        
        ~ & PairNorm & 8.9 & 12.8 & 20.1 & 24.4\\
        
        ~ & \textbf{SkipNode-U} & 8.4  & 14.3 & 20.4 & 26.0\\
       
        ~ & \textbf{SkipNode-B} & 8.3  & 14.5 & 20.7 & 24.6 \\
        \bottomrule
    \end{tabular}
    \label{tab:efficency-analysis} 
\end{table}


\section{Conclusion}
In this study, we explore the fundamental causes of performance degradation in deep GCNs from a novel perspective: over-smoothing and gradient vanishing intensify each other, further degrading the performance. Based on theoretical and empirical analysis, we propose an effective and general framework to address this problem by reducing the convergence speed of over-smoothing and gradient vanishing. Besides, extensive experiments demonstrate that it is beneficial to apply SkipNode to deep GCNs.


\section*{Acknowledgments}
This research was supported by the National Natural Science Foundation of China (Grant Nos. 62133012, 61936006, 62103314, 62203354, 61876144, 61876145, 62073255) and the Key Research and Development Program of Shaanxi (Program No. 2020ZDLGY04-07).

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi


\bibliographystyle{IEEEtran}
