Deep Graph Neural Networks via Flexible Subgraph Aggregation
Graph neural networks (GNNs), a type of neural network that can learn from
graph-structured data and learn the representation of nodes through aggregating
neighborhood information, have shown superior performance in various downstream
tasks. However, it is known that the performance of GNNs degrades gradually as
the number of layers increases. In this paper, we evaluate the expressive power
of GNNs from the perspective of subgraph aggregation. We reveal the potential
cause of performance degradation for traditional deep GNNs, i.e., aggregated
subgraph overlap, and we theoretically illustrate the fact that previous
residual-based GNNs exploit the aggregation results of 1 to $k$ hop subgraphs
to improve the effectiveness. Further, we find that the utilization of
different subgraphs by previous models is often inflexible. Based on this, we
propose a sampling-based node-level residual module (SNR) that can achieve a
more flexible utilization of different hops of subgraph aggregation by
introducing node-level parameters sampled from a learnable distribution.
Extensive experiments show that the performance of GNNs with our proposed SNR
module outperform a comprehensive set of baselines.
Jingbo Zhou, Yixuan Du, Ruqiong Zhang, Di Jin, Carl Yang, Rui Zhang
# Deep Graph Neural Networks

###### Abstract

Graph neural networks (GNNs), a type of neural network that can learn from graph-structured data and learn the representation of nodes through aggregating neighborhood information, have shown superior performance in various downstream tasks. However, it is known that the performance of GNNs degrades gradually as the number of layers increases. In this paper, we evaluate the expressive power of GNNs from the perspective of subgraph aggregation. We reveal the potential cause of performance degradation for traditional deep GNNs, i.e., aggregated subgraph overlap, and we theoretically illustrate the fact that previous residual-based GNNs exploit the aggregation results of 1 to \(k\) hop subgraphs to improve the effectiveness. Further, we find that the utilization of different subgraphs by previous models is often inflexible. Based on this, we propose a sampling-based node-level residual module (SNR) that can achieve a more flexible utilization of different hops of subgraph aggregation by introducing node-level parameters sampled from a learnable distribution. Extensive experiments show that the performance of GNNs with our proposed SNR module outperform a comprehensive set of baselines.

## 1 Introduction

GNNs have emerged in recent years as the most powerful model for processing graph-structured data and have performed very well in various fields, such as social networks (Perozzi et al. (2014)), recommender systems (Fan et al. (2019)), and drug discovery (Duvenaud et al. (2015)). Through the message-passing mechanism that propagates and aggregates representations of neighboring nodes, GNNs provide a general framework for learning information on graph structure.

Despite great success, according to previous studies (Li et al. (2018); Xu et al. (2018)), GNNs show significant performance degradation as the number of layers increases, which makes GNNs not able to take full advantage of the multi-hop neighbor structure of nodes to obtain better node representations.

The main reason for this situation is now widely believed to be oversmoothing (Li et al. (2018); Oono and Suzuki (2020); Xu et al. (2018); Klicpera et al. (2019)). However, since ResNet (He et al. (2016)) uses residual connection to solve a similar problem in computer vision and obtains good results, several new works have been inspired to apply the idea of residual connection to GNNs to alleviate oversmoothing and thus improve the expressive power. For example, JKNet (Xu et al. (2018)) learns node representations by aggregating the outputs of all previous layers at the last layer. DenseGCN (Li et al. (2019)) concatenates the results of the current layer and all previous layers as the node representations of this layer. APPNP (Klicpera et al. (2019)) uses the initial
residual connection to retain the initial feature information with probability \(\alpha\), and utilizes the feature information aggregated at the current layer with probability \(1-\alpha\).

In this paper, we evaluate the expressive power of GNNs from the perspective of subgraph aggregation. Based on this perspective, we show that the single high-hop subgraph aggregation of message-passing GNNs is limited by the fact that high-hop subgraphs are prone to information overlap, which makes the node representations obtained from k-hop subgraph aggregation indistinguishable, i.e., oversmoothing occurs.

Based on this perspective, we conduct a theoretical analysis of previous residual-based models and find that previous methods are in fact able to utilize multiple subgraph aggregations to improve the expressiveness of the model. However, most methods tend to utilize subgraph information by fixed coefficients, which assumes that the information from the subgraph of the same hop are equally important for different nodes, which leads to inflexibility in the model's exploitation of subgraph information and thus limits further improvement of the expressive power. Some existing methods try to overcome this inflexibility but lead to overfitting by introducing more parameters, which in turn affects the effectiveness of the model, which is demonstrated by the experiment.

Considering these limitations, we propose a **S**ampling-based **N**ode-level **R**esidual module (**SNR**). Specifically, we adopt a more fine-grained node-level residual module to achieve a more flexible exploitation of subgraph aggregation, which is proved by the theoretical analysis. On the other hand, to avoid overfitting due to the introduction of more parameters, instead of learning the specific parameters directly, we first learn a correlation distribution through reparameterization trick and obtain the specific residual coefficients by sampling. Experiments verify that this sampling-based approach can significantly alleviate overfitting.

**Our Contributions.** (1) We reinterpret the phenomenon that the effectiveness of traditional message-passing GNNs decreases as the number of layers increases from the perspective of _k_-hop subgraph overlap. (2) Based on the idea of subgraph aggregation, we theoretically analyze the previous residual-based methods and find that they actually utilize multiple hop subgraph aggregation in different ways to improve the expressive power of the model, and we point out the limitations of inflexibility and overfitting in previous residual-based methods. (3) We propose a sampling-based node-level residual module that allows more flexible exploitation of different _k_-hop subgraph aggregations while alleviating overfitting due to more parameters. (4) Extensive experiments show that GNNs with the proposed SNR module achieve better performance than other methods, as well as with higher training efficiency, on semi-supervised tasks as well as on tasks requiring deep GNNs.

## 2 Preliminaries

### Notations

A connected undirected graph is represented by \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}=\{v_{1},v_{2},\ldots,v_{N}\}\) is the set of \(N\) nodes and \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) is the set of edges. The feature of nodes is given in matrix \(\mathbf{H}\in\mathbb{R}^{N\times d}\) where \(d\) indicates the length of feature. Let \(\mathbf{A}\in\{0,1\}^{N\times N}\) denotes the adjacency matrix and \(\mathbf{A}_{ij}=1\) only if an edge exists between nodes \(v_{i}\) and \(v_{j}\). \(\mathbf{D}\in\mathbb{R}^{N\times N}\) is the diagonal degree matrix whose elements \(d_{i}\) computes the number of edges connected to node \(v_{i}\). \(\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}\) is the adjacency matrix with self loop and \(\tilde{\mathbf{D}}=\mathbf{D}+\mathbf{I}\).

### Graph Neural Networks

A GNNs layer updates the representation of each node via aggregating itself and its neighbors' representations. Specifically, a layer's output \(\mathbf{H}^{\prime}\) consists of new representations \(\mathbf{h}^{\prime}\) of each node computed as:

\[\mathbf{h}^{\prime}_{i}=\mathbf{f}_{\theta}\left(\mathbf{h}_{i},\ \mathbf{AGGREGATE}\left(\{\mathbf{h}_{j}\mid v_{j}\in\mathcal{V},(v_{i},v_{j} )\in\mathcal{E}\}\right)\right)\]

where \(\mathbf{h}^{\prime}_{i}\) indicates the new representation of node \(v_{i}\) and \(\mathbf{f}_{\theta}\) denotes the update function. The key to the performance of different GNNs is in the design of the \(\mathbf{f}_{\theta}\) and **AGGREGATE** function. Graph Convolutional Network (GCN)(Kipf and Welling (2017)) is a classical massage-passing GNNs follows layer-wise propagation rule:

\[\mathbf{H}_{k+1}=\sigma\left(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{ A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}_{k}\mathbf{W}_{k}\right) \tag{1}\]
where \(\mathbf{H}_{k}\) is the feature matrix of the \(k^{\text{th}}\) layer, \(\mathbf{W}_{k}\) is a layer-specific learnable weight matrix, \(\sigma(\cdot)\) denotes an activation function.

### Residual Connection

Several works have used residual connection to solve the problem of oversmoothing. Common residual connection for GNNs are summarized below. Details are explained in Appendix A.

## 3 Motivation

Message-passing GNNs recursively update the features of each node by aggregating information from its neighbors, allowing them to capture both the graph topology and node features. For a message-passing GNNs without a residual structure, the information domain of each node after \(k\)-layer aggregation is a related \(k\)-hop subgraph. Figure 1 shows that, after two aggregation operations, nodes on layer 2 obtain 1-hop neighbor and 2-hop neighbor information in layer 0, respectively. According to the definition of the \(k\)-hop subgraph, the information of the node on layer 2 in the figure is composed of all reachable nodes information shown on layer 0. We can consider the result of \(k\)-layer residual-free message-passing GNNs is equivalent to \(k\)-time aggregation of each node on its \(k\)-hop subgraph, which we call \(k\)-hop subgraph aggregation.

It is evident that as the number of aggregation operations increases, the reachable information range of a node expands rapidly, that is, the size of its \(k\)-hop subgraph grows exponentially as \(k\) increases, leading to a significant increase in the overlap between the \(k\)-hop subgraphs of different nodes. As a result, the aggregation result of different nodes on their respective \(k\)-hop subgraphs becomes indistinguishable. Furthermore, in a specific graph dataset, nodes with higher degrees tend to have a larger range of \(k\)-hop subgraphs compared to nodes with lower degrees. As a result, the subgraphs are more likely to overlap between nodes with higher degrees, making their aggregation results more likely to become similar and indistinguishable.

To verify this point, we conduct experiments on three graph datasets, Cora, Citeseer, and Pubmed. First, we group the nodes according to their degrees by assigning nodes with degrees in the range of \([2^{i},2^{i+1})\) to the \(i\)-th group. Subsequently, we perform aggregation with different layers of GCN and GAT, then calculate the degree of smoothing of the node representations within each group separately. We use the metric proposed in (Jin et al. (2022)) to measure the smoothness of the node representations within each group, namely **SMV**, which calculates the average of the distances between the nodes within the group:

\[\mathbf{SMV}(\mathbf{X})=\frac{1}{\mathbf{N}(\mathbf{N}-\mathbf{1})}\sum_{i \neq j}\mathbf{D}\left(\mathbf{X}_{i,:},\mathbf{X}_{j,:}\right) \tag{2}\]

where \(\mathbf{D}(\cdot,\cdot)\) denotes the normalized Euclidean distance between two vectors:

\[\mathbf{D}(\mathbf{x},\mathbf{y})=\frac{1}{2}\left\|\frac{\mathbf{x}}{\| \mathbf{x}\|}-\frac{\mathbf{y}}{\|\mathbf{y}\|}\right\|_{2} \tag{3}\]

\begin{table}
\begin{tabular}{c|c|c} \hline \hline
**Residual Connection** & **Corresponding GCN** & **Formula** \\ \hline Res & ResGCN & \(\mathbf{H}_{k}=\mathbf{H}_{k-1}+\sigma\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}_{k-1}\mathbf{W} _{k-1}\right)\) \\ \hline InitialRes & APPNP & \(\mathbf{H}_{k}=(1-\alpha)\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}_{k-1}+\alpha\mathbf{H}\) \\ \hline Dense & DenseGCN & \(\mathbf{H}_{k}=\mathbf{AGG}_{dense}(\mathbf{H},\mathbf{H}_{1},\ldots, \mathbf{H}_{k-1})\) \\ \hline JK & JKNet & \(\mathbf{H}_{output}=\mathbf{AGG}_{jk}(\mathbf{H}_{1},\ldots,\mathbf{H}_{k-1})\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Common residual connection for GNNs.

Figure 1: \(k\)-hop subgraph.
A smaller value of **SMV** indicates a greater similarity in node representations.

We select the most representative result illustrated in Figure 2, which shows the result of GAT on Pubmed. The rest of the results are shown in the Appendix B. It can be seen that the groups of nodes with higher degree tend to be more likely to have high similarity in the representation of nodes within the group in different layers of the model. This finding supports our claim.

After verifying the conclusion that subgraph overlap leads to oversmoothing through experiments, a natural idea is to alleviate the problem of large overlap of single subgraph by utilizing multiple hop subgraph aggregations, thereby alleviating oversmoothing. In the following section, we will demonstrate that the previous \(k\)-layer residual-based GNNs are actually different forms of integration of 1 to \(k\) hop subgraph aggregations.

### Revisiting Previous Models in a New Perspective

In the rest of this paper we will uniformly take GCN, a classical residual-free message-passing GNNs, as an example. We assume that **H** is non-negative, so the ELU function can be ignored. In addition, the weight matrix is ignored for simplicity. Combined with the formula of GCN given in Equation 1, we can formulate the specific result of \(k\)-hop subgraph aggregation as \(\mathbf{N}^{k}\mathbf{H}\), where \(\mathbf{N}=\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D }}^{-\frac{1}{2}}\). To show more intuitively how different \(k\)-layer-based residual models utilize \(\mathbf{N}^{j}\mathbf{H}\), \(j=0,1,\cdots,k\). We derive the general term formulas of their final outputs, and the results are shown in Table 2. Details of the derivation of the formula in this part are given in Appendix C.

From the formula in the table, we can see that, in comparison to message-passing GNNs, residual-based variants of GNNs can utilize multiple \(k\)-hop subgraphs. There are two methods to exploit them: **(1)** Summation, such as ResGCN and APPNP. Such methods employ linear summation over the aggregation of different hop subgraphs; **(2)** Aggregation functions, such as DenseNet and JKNet. Such methods make direct and explicit exploitation of different hop subgraph aggregations through methods such as concatenation.

However, for the first type of methods, they all employ a fixed, layer-level coefficient for linear summation of the subgraph aggregation, which assumes that the information from the subgraph of the same hop are equally important for different nodes. It will limit the expressive power of GNNs, which reveals the need to design a more fine-grained node-level residual module that can more flexibly utilize information from different \(k\)-hop subgraphs. For another type of method, they can achieve finer-grained subgraph aggregation, but the experiment find that their performance is not improved because of the more finer-grained structure, mainly because the introduction of more parameters leads to overfitting Phenomenon. In general, neither of these two types of methods has achieved a more effective improvement in the expressive power of GNNs.

\begin{table}
\begin{tabular}{c|c} \hline \hline
**Model Name** & **General Term Formula** \\ \hline ResGCN & \(\mathbf{H}_{k}=\sum_{j=0}^{k}\mathbf{C}_{k}^{j}\mathbf{N}^{j}\mathbf{H}\) \\ \hline APPNP & \(\mathbf{H}_{k}=\left(1-\alpha\right)^{k}\mathbf{N}^{k}\mathbf{H}+\alpha\sum \limits_{j=0}^{k-1}\sum\limits_{i=0}^{j}\left(-1\right)^{j-i}\left(1-\alpha \right)^{i}\mathbf{N}^{i}\mathbf{H}\) \\ \hline JKNet & \(\mathbf{H}_{k}=\mathbf{AGG}_{jk}(\mathbf{NH},\ldots,\mathbf{N}^{k-1}\mathbf{H})\) \\ \hline DenseGCN & — \\ \hline \hline \end{tabular}
\end{table}
Table 2: General term formulas of residual models.

Figure 2: SMV for node groups of different degrees.
The Proposed Method

In order to solve the two limitations of flexibility and overfitting encountered by previous residual-based models, we try to propose a node-level, more flexible, general residual module, which can alleviate overfitting caused by more parameters at the same time. Based on this, we propose a sampling-based node-level generic residual module SNR. We define SNR module as:

\[\mathbf{h}_{k-1}^{(i)}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \
It is worth noting that GCNII and SNR-GCN share a similar architecture, so both can be viewed approximately as more refined APPNP-style models. However, when faced with the problem of overfitting due to more parameters, GCNII adds an identity matrix to mitigate the issue. Later experiment results have shown that SNR-GCN's learning distribution-sampling approach is more effective in alleviating overfitting.

### Complexity Analysis

Taking vanilla GCN as an example, we analyzed the additional complexity of SNR in model and time. We assume that the number of nodes in the graph is \(n\) and hidden dimension is \(d\).

**Model Complexity.** As described in Section 4, at each layer the SNR module learns a mean and standard deviation of the corresponding distribution for each node, so the complexity can be calculated as \(O(n)\), and thus the additional complexity of the \(k\)-layer model equipped with SNR is \(O(kn)\).

**Time Complexity.** The time complexity of a vanilla GCN layer mainly comes from the matrix multiplication of \(\mathbf{N}\) and \(\mathbf{H}\), hence its complexity is \(O(n^{2}d)\). And the main computational parts of a SNR module are the sampling of \(p_{k}^{(i)}\), scalar multiplication and matrix addition, which correspond to a complexity of \(O(n)\), \(O(nd)\), and \(O(nd)\), respectively. Thus the time complexity of the SNR module is \(O(nd)\) and the time complexity of a GCN layer equipped the SNR module is \(O(n^{2}d+nd)\). Therefore, the introduction of the SNR module does not significantly affect the computational efficiency.

## 5 Experiment

In this section, we aim to experimentally evaluate the effectiveness of SNR on real datasets. To achieve this, we will compare the performance of SNR with other methods and answer the following research questions. **Q1:** How effective is SNR on classical tasks that prefer shallow models? **Q2:** Can SNR help overcome oversmoothing in GNNs and enable the training of deeper models? **Q3:** How effective is SNR on tasks that require deep GNNs? **Q4:** How efficient is the training of SNR?

### Experiment Setup

In our study, we conduct experiments on four tasks: semi-supervised node classification **(Q1)**, alleviating performance drop in deeper GNNs **(Q2)**, semi-supervised node classification with missing vectors **(Q3)**, and efficiency evaluation **(Q4)**.

**Datasets.** To assess the effectiveness of our proposed module, we have used four data sets that are widely used in the field of GNN, including Cora, Citeseer, Pubmed (Sen et al. (2008)), and CoraFull (Bojchevski and Gunnemann (2018)) for testing purposes. In addition, we also use two webpage datasets collected from Wikipedia: Chameleon and Squirrel (Rozemberczki et al. (2021)). Details on the characteristics of these datasets and the specific data-splitting procedures used can be found in Appendix F.1.

**Models.** We consider two fundamental GNNs, GCN (Kipf and Welling (2017)) and GAT (Velickovic et al. (2017)). For GCN, we test the performance of SNR-GCN and its residual variant models, including ResGCN (Li et al. (2019)), APPNP (Klicpera et al. (2019)), DenseGCN (Li et al. (2019)), GCNII (Chen et al. (2020)) and JKNet (Xu et al. (2018)). For GAT, we directly equip it with the following residual module: Res, InitialRes, Dense, JK and SNR and test the performance. Additionally, for the SSNC-MV task, we compare our proposed module with several classical oversmoothing mitigation techniques, including BatchNorm (Ioffe and Szegedy (2015)), PairNorm (Zhao and Akoglu (2019)), DGN (Zhou et al. (2020)), Decorr (Jin et al. (2022)), DropEdge (Rong et al. (2019)) and other residual-based methods. Further details on these models and techniques can be found in the following sections.

**Implementations.** For all benchmark and variant models, the linear layers in the models are initialized with a standard normal distribution, and the convolutional layers are initialized with Xavier initialization. The Adam optimizer (Kingma and Ba (2015)) is used for all models. Further details on the specific parameter settings used can be found in Appendix F.2. All models and datasets used in this paper are implemented using the Deep Graph Library (DGL) (Wang et al. (2019)). All experiments are conducted on a server with 15 vCPU Intel(R) Xeon(R) Platinum 8358P CPU @ 2.60GHz, A40 with 48GB GPU memory, and 56GB main memory.
### Semi-supervised Node Classification

To validate the performance of SNR, we apply the module to two fundamental GNNs, GCN and GAT, and test the accuracy according to the mentioned experimental setup, and compare it with four classic residual modules, DenseNet, ResNet, InitialResNet and JKNet. We vary the number of layers in the range of \(\{1,2,3,\cdots,10\}\) and select the best result among all layers. Specifically, we run 10 times for each number of layers to obtain the mean accuracy along with the standard deviation. We select the best results among all layers and report them in the Table 3. We find that GNNs with the SNR module consistently achieve the best performance in all cases **(Q1)**. However, from the experimental results, many models with residual modules have not achieved the expected results. In many cases, compared with the basic model, the accuracy is even reduced. According to previous research (Zhao and Akoglu (2019)), we speculate that overfitting may have contributed to this phenomenon. To verify our hypothesis, we conduct further experiments. Given that most models in the previous experiments achieve their best performance with shallow models, we select models with two layers, train 500 epochs, and report their accuracy on the training and validation sets at each epoch. The results are shown in Appendix G. Most models show signs of overfitting and SNR module demonstrates the best ability to alleviate overfitting. Specifically, in shallow GNNs with limited subgraph aggregation, most models have similar expressive abilities, and overfitting is the main factor affecting their performance. Our proposed method effectively alleviates overfitting by learning a more representative distribution, resulting in a better performance than the base models.

### Alleviating Performance Drop in Deeper GNNs

As the number of layers in GNNs increases, oversmoothing occurs, resulting in performance degradation. Our objective is to investigate the performance of deep GNNs equipped with SNR and observe the impact of oversmoothing on their performance. We evaluate the performance of GNNs with different residual modules on 2, 16, and 32 layers using the Cora, Citeseer, and Pubmed datasets. The "None" column represents vanilla GNNs without any additional modules. According to (Chen et al. (2020)), APPNP is a shallow model, hence we use GCNII to represent GCN with initial residual connection instead. The same settings are used in section 5.4. The experimental results are presented in Table 4.

From Table 4, we can observe that GNNs with SNR consistently outperform other residual methods and the base models in most of cases when given the same number of layers. SNR can significantly improve the performance of deep GNNs **(Q2)**. For instance, on the Cora dataset, SNR improves the performance of 32-layer GCN and GAT by **53.69%** and **56.20%**, respectively. By flexibly utilizing multiple subgraph aggregation results with our SNR module, we can enhance the expressive power of the model and produce more distinctive node representations than those of regular GNNs, thereby overcoming the oversmoothing problem. These results suggest that we can train deep GNNs based on SNR, making them suitable for tasks that require the use of deep GNNs.

\begin{table}
\begin{tabular}{c|c c c c c c} \hline \hline
**Method** & **Cora** & **Citeseer** & **Pubmed** & **CoraFull** & **Chameleon** & **Squirrel** \\ \hline GCN & 80.16\(\pm\)1.15 & 70.20\(\pm\)0.62 & 78.26\(\pm\)0.61 & 68.40\(\pm\)0.33 & 68.00\(\pm\)2.30 & 51.69\(\pm\)1.83 \\ ResGCN & 79.01\(\pm\)1.26 & 69.27\(\pm\)0.66 & 78.08\(\pm\)0.51 & 67.98\(\pm\)0.51 & 65.26\(\pm\)2.47 & 47.43\(\pm\)1.14 \\ APPNP & 79.04\(\pm\)0.84 & 69.64\(\pm\)0.49 & 76.38\(\pm\)0.12 & 37.77\(\pm\)0.43 & 59.80\(\pm\)2.68 & 43.17\(\pm\)1.01 \\ GCNII & 78.53\(\pm\)0.67 & 69.55\(\pm\)1.14 & 76.17\(\pm\)0.70 & 68.30\(\pm\)0.26 & 64.76\(\pm\)2.43 & 52.83\(\pm\)1.51 \\ DenseGCN & 77.24\(\pm\)1.12 & 65.03\(\pm\)1.58 & 76.93\(\pm\)0.78 & 64.52\(\pm\)0.71 & 59.04\(\pm\)2.07 & 38.98\(\pm\)1.25 \\ JKNet & 78.16\(\pm\)1.21 & 65.33\(\pm\)1.66 & 78.10\(\pm\)0.55 & 66.11\(\pm\)0.49 & 55.75\(\pm\)2.93 & 35.95\(\pm\)1.10 \\
**SNR-GCN (Ours)** & **81.17\(\pm\)0.72** & **70.39\(\pm\)1.01** & **78.34\(\pm\)0.62** & **69.80\(\pm\)0.28** & **72.04\(\pm\)1.89** & **58.35\(\pm\)1.55** \\ \hline GAT & 79.24\(\pm\)1.18 & 69.51\(\pm\)1.07 & 77.59\(\pm\)0.80 & 67.39\(\pm\)0.32 & 65.81\(\pm\)2.13 & 50.16\(\pm\)2.42 \\ Res-GAT & 78.43\(\pm\)0.99 & 68.15\(\pm\)1.25 & 77.27\(\pm\)0.52 & 67.67\(\pm\)0.32 & 69.08\(\pm\)2.50 & 49.77\(\pm\)1.72 \\ InitialRes-GAT & 77.77\(\pm\)1.51 & 67.48\(\pm\)2.15 & 77.46\(\pm\)1.17 & 65.49\(\pm\)0.42 & 65.90\(\pm\)2.98 & 52.83\(\pm\)2.39 \\ Dense-GAT & 78.27\(\pm\)2.22 & 64.92\(\pm\)1.94 & 76.84\(\pm\)0.64 & 66.61\(\pm\)0.63 & 63.86\(\pm\)3.03 & 43.01\(\pm\)1.34 \\ JK-GAT & 78.91\(\pm\)1.71 & 65.59\(\pm\)2.62 & 77.70\(\pm\)0.64 & 67.69\(\pm\)0.65 & 56.14\(\pm\)2.68 & 37.25\(\pm\)1.01 \\
**SNR-GAT (Ours)** & **79.65\(\pm\)0.84** & **69.85\(\pm\)0.67** & **77.76\(\pm\)0.93** & **68.00\(\pm\)0.27** & **69.54\(\pm\)2.22** & **55.14\(\pm\)1.78** \\ \hline \hline \end{tabular}
\end{table}
Table 3: Summary of classification accuracy (%) results with various depths. The best results are in bold and the second best results are underlined.
### Semi-supervised Node Classification with Missing Vectors

When do we need deep GNNs? (Zhao and Akoglu (2019)) first proposed semi-supervised node classification with missing vectors (SSNC-MV), where nodes' features are missing. SSNC-MV is a practical problem with various real-world applications. For example, new users on social networks usually lack personal information (Rashid et al. (2008)). Obviously, we need more propagation steps to effectively aggregate information associated with existing users so that we can obtain representations of these new users. In this scenario, GNNs with more layers clearly perform better.

Previous research has shown that normalization techniques can be effective in mitigating oversmoothing, and further, exploring deeper architectures. Therefore, we apply several techniques that can overcome oversmoothing and residual modules to GCN and GAT to compare their performance on tasks that require deep GNNs.

We remove the node features in the validation and test set following the idea in (Jin et al. (2022); Zhao and Akoglu (2019); Zhou et al. (2020)). We reuse the metrics that already reported in (Jin et al. (2022)) for None, BatchNorm (Ioffe and Szegedy (2015)), PairNorm (Zhao and Akoglu (2019)), DGN (Zhou et al. (2020)), DeCorr (Jin et al. (2022)), and DropEdge (Rong et al. (2019)). For all residual-based models, the results are obtained by varying the number of layers in \(\{1,2,3,\cdots,10,15,\cdots,30\}\) and running five times for each number of layers. We select the layer #K that achieves the best

\begin{table}
\begin{tabular}{c|c|c c c|c c c} \hline \hline \multirow{2}{*}{Dataset} & \multirow{2}{*}{Method} & \multicolumn{4}{c|}{GCN} & \multicolumn{4}{c}{GAT} \\  & & L2 & L16 & L32 & L2 & L16 & L32 \\ \hline \multirow{6}{*}{Cora} & None & 79.50\(\pm\)0.84 & 69.83\(\pm\)2.47 & 25.31\(\pm\)12.49 & 79.11\(\pm\)1.55 & 75.44\(\pm\)1.08 & 22.74\(\pm\)7.47 \\  & Res & 78.73\(\pm\)1.27 & 78.46\(\pm\)0.79 & 38.70\(\pm\)8.20 & 78.36\(\pm\)1.42 & 34.80\(\pm\)6.26 & 32.06\(\pm\)0.54 \\  & InitialRes & 77.67\(\pm\)0.51 & 77.74\(\pm\)0.73 & 77.92\(\pm\)0.56 & 77.20\(\pm\)1.54 & 74.99\(\pm\)0.75 & 25.08\(\pm\)7.27 \\  & Dense & 75.24\(\pm\)1.73 & 71.34\(\pm\)1.51 & 75.43\(\pm\)2.49 & 76.80\(\pm\)1.71 & 74.75\(\pm\)2.22 & 75.70\(\pm\)2.20 \\  & JK & 76.28\(\pm\)1.73 & 72.39\(\pm\)3.20 & 75.03\(\pm\)1.11 & 78.06\(\pm\)0.51 & 76.66\(\pm\)1.39 & 23.29\(\pm\)8.45 \\  & **SNR (Ours)** & **80.58\(\pm\)0.82** & **78.55\(\pm\)0.92** & **79.00\(\pm\)1.43** & **79.69\(\pm\)0.55** & **77.92\(\pm\)1.54** & **78.94\(\pm\)0.80** \\ \hline \multirow{6}{*}{Citeseer} & None & 68.31\(\pm\)1.40 & 54.07\(\pm\)2.48 & 34.84\(\pm\)1.60 & 68.64\(\pm\)1.20 & 59.16\(\pm\)2.44 & 24.37\(\pm\)3.59 \\  & Res & 67.68\(\pm\)1.36 & 63.99\(\pm\)1.12 & 52.96\(\pm\)4.27 & 67.55\(\pm\)1.10 & 28.53\(\pm\)4.93 & 24.70\(\pm\)4.12 \\  & InitialRes & 68.23\(\pm\)0.95 & **68.29\(\pm\)0.92** & **68.74\(\pm\)0.61** & 66.86\(\pm\)1.60 & 62.42\(\pm\)2.29 & 73.84\(\pm\)8.7 \\  & Dense & 64.83\(\pm\)0.94 & 58.42\(\pm\)2.96 & 58.75\(\pm\)3.37 & 64.58\(\pm\)2.07 & 61.17\(\pm\)1.78 & 61.87\(\pm\)2.91 \\  & JK & 64.69\(\pm\)1.44 & 58.38\(\pm\)3.36 & 58.63\(\pm\)4.76 & 65.84\(\pm\)2.02 & 62.64\(\pm\)1.66 & 23.09\(\pm\)4.02 \\  & **SNR (Ours)** & **70.18\(\pm\)0.61** & 67.07\(\pm\)1.78 & 66.27\(\pm\)2.00 & **69.71\(\pm\)0.92** & **67.51\(\pm\)2.28** & **66.53\(\pm\)2.48** \\ \hline \multirow{6}{*}{Pubmed} & None & 77.53\(\pm\)0.73 & 76.16\(\pm\)0.96 & 51.29\(\pm\)11.71 & 77.07\(\pm\)0.52 & 77.49\(\pm\)0.65 & 53.20\(\pm\)9.18 \\  & Res & 77.64\(\pm\)1.01 & 77.65\(\pm\)0.78 & 73.31\(\pm\)7.15 & 77.36\(\pm\)0.60 & 50.16\(\pm\)7.65 & 43.46\(\pm\)3.30 \\  & InitialRes & 75.66\(\pm\)0.82 & 75.15\(\pm\)0.48 & 75.31\(\pm\)0.55 & 77.42\(\pm\)0.79 & 77.42\(\pm\)0.82 & 44.96\(\pm\)5.91 \\  & Dense & 76.81\(\pm\)1.06 & 74.01\(\pm\)2.36 & 76.33\(\pm\)1.17 & 76.66\(\pm\)0.61 & 76.38\(\pm\)1.26 & 76.50\(\pm\)1.47 \\  & JK & 77.61\(\pm\)0.78 & 76.31\(\pm\)1.45 & 76.59\(\pm\)1.53 & 77.48\(\pm\)0.84 & 77.75\(\pm\)0.77 & 40.84\(\pm\)0.23 \\  & **SNR (Ours)** & **77.84\(\pm\)0.51** & **78.02\(\pm\)0.71** & **77.36\(\pm\)0.78** & **77.51\(\pm\)0.62** & **78.17\(\pm\)0.85** & **77.77\(\pm\)0.46** \\ \hline \hline \end{tabular}
\end{table}
Table 4: Node classification accuracy (%) on different number of layers. The best results are in bold and the second best results are underlined.

\begin{table}
\begin{tabular}{c|c c|c c|c c|c c|c c} \hline \hline  & \multicolumn{4}{c|}{GCN} & \multicolumn{4}{c}{GAT} \\ \hline \multirow{2}{*}{Method} & \multicolumn{2}{c|}{Cora} & \multicolumn{2}{c|}{Citeseer} & \multicolumn{2}{c|}{Pubmed} & \multicolumn{2}{c|}{Cora} & \multicolumn{2}{c|}{Citeseer} & \multicolumn{2}{c|}{Pubmed} \\  & Acc & \#K & Acc & \#K & Acc & \#K & Acc & \#K & Acc & \#K & Acc & \#K \\ \hline None & 57.3 & 3 & 44.0 & 6 & 36.4 & 4 & 50.1 & 2 & 40.8 & 4 & 38.5 & 4 \\ BatchNorm & 71.8 & 20 & 45.1 & 25 & 70.4 & 30 & 72.7 & 5 & 48.7 & 5 & 60.7 & 4 \\ PairNorm & 65.6 & 20 & 43.6 & 25 & 63.1 & 30 & 68.8 & 8 & 50.3 & 6 & 63.2 & 20 \\ DGN & 76.3 & 20 & 50.2 & 30 & 72.0 & 30 & 75.8 & 8 & 54.5 & 5 & 72.3 & 20 \\ DeCorr & 73.8 & 20 & 49.1 & 30 & 73.3 & 15 & 72.8 & 15 & 46.5 & 6 & 72.4 & 15 \\ DropEdge & 67.0 & 6 & 44.2 & 8 & 69.3 & 6 & 67.2 & 6 & 48.2 & 6 & 67.2 & 6 \\ Res & 74.06\(\pm\)1.10 & 7 & 57.52\(\pm\)1.30 & 67.36\(\pm\)2.01 & 84 & 74.86\(\pm\)1.25 & 6 & 57.88\(
performance and report its average accuracy along with the standard deviation. The results are reported in Table 5.

Our experiments show that GNNs with the SNR module outperform all previous methods **(Q3)**. Additionally, we find that for most models, the number of layers to reach the best accuracy is relatively large, which indicates that it is necessary to perform more propagation to gather information from further nodes so that we can obtain effective representations of nodes with missing features.

### Efficiency Experiment

In real-world tasks, the rate at which a model achieves optimal performance through training is often important, and this affects the true effectiveness and time consumption of the model in real-world applications. To enable concrete measurement and comparison, here we define the following metrics for model training efficiency:

\[\textbf{Efficiency}\ =\ \frac{\textbf{Accuracy}}{\textbf{Time}} \tag{8}\]

where **Accuracy** denotes the accuracy of the model when it reaches its optimal performance and **Time** denotes the time when the model reaches its optimal performance. The definition of this formula shows that a larger **Efficiency** represents a higher performance per unit time improvement, and therefore a higher training efficiency.

Based on the above equation, we evaluate the training efficiency of vanilla GNNs and SNR-GNNs. We use the 2, 4, 8, 16, 32, and 64-layer and average five **Efficiency** calculated for each layer of the model. Specifically, each **Efficiency** is calculated based on the time for the model to reach the highest accuracy on the validation set after 100 epochs of training and the accuracy achieved on the test set at that time. Figure 3 shows the models' **Efficiency** on Cora. The results on other datasets are shown in the Appendix H.

It can be noticed that the training efficiency decreases as the number of layers increases, which is due to the increase in training time caused by the rise in the number of model parameters. However, in most cases, compared to vanilla GNNs, our SNR module is able to maintain the highest training efficiency **(Q4)**.

## 6 Conclusion

Our work proposes a new perspective for understanding the expressive power of GNNs: the \(k\)-hop subgraph aggregation theory. From this perspective, we have reinterpreted and experimentally validated the reason why the performance of message-passing GNNs decreases as the number of layers increases. Furthermore, we have evaluated the expressive power of previous residual-based GNNs based on this perspective. Building on these insights, we propose a new sampling-based generalized residual module SNR and show theoretically that SNR enables GNNs to more flexibly utilize information from multiple \(k\)-hop subgraphs, thus further improving the expressive power of GNNs. Extensive experiments demonstrate that the proposed SNR can effectively address the issues of overfitting in shallow layers and oversmoothing in deep layers that are commonly encountered in message-passing GNNs, and significantly improves the performance, particularly in SSNC-MV tasks.

Figure 3: Efficiency for different models at different layers.
Our research will facilitate a deeper exploration of deep GNNs and enable a wider range of potential applications.
