DrGNN: Deep Residual Graph Neural Network with Contrastive Learning
Authors: Lecheng Zheng
Dongqi Fu
Ross Maciejewski
Jingrui He
Venue: Accepted by TMLR ()

Abstract: Recent studies reveal that deep representation learning models without proper regularization can suffer from the dimensional collapse problem, i.e., representation vectors span over a lower dimensional space. In the domain of graph deep representation learning, the phenomenon that the node representations are indistinguishable and even shrink to a constant vector is called oversmoothing. Based on the analysis of the rank of node representations, we find that representation oversmoothing and dimensional collapse are highly related to each other in deep graph neural networks, and the oversmoothing problem can be interpreted by the dimensional collapse of the node representation matrix. Then, to address the dimensional collapse and the oversmoothing together in deep graph neural networks, we first find vanilla residual connections and contrastive learning producing sub-optimal outcomes by ignoring the structured constraints of graph data. Motivated by this, we propose a novel graph neural network named DrGNN to alleviate the oversmoothing issue from the perspective of addressing dimensional collapse. Specifically, in DrGNN, we design a topology-preserving residual connection for graph neural networks to force the low-rank of hidden representations close to the full-rank input features. Also, we propose the structure-guided contrastive learning to ensure only close neighbors who share similar local connections can have similar representations. Empirical experiments on multiple real-world datasets demonstrate that DrGNN outperforms state-of-the-art deep graph representation baseline algorithms. The code of our method is available at the GitHub link: https://github.com/zhenglecheng/DrGNN.

Published in Transactions on Machine Learning Research (10/2024)
DrGNN: Deep Residual Graph Neural Network with Contrastive Learning
Lecheng Zheng"
lecheng4 @illinois. edu
University of Blinois Urbana- Chanpiig
Dongqi Fu' Meta AI
donggifu@mmeta. com
Ross Maciejewski Arizona State University
rmaciejeBasu.ede edu
Jingrui He
jingri@@illinois.omm edu
University of Ilinois Urbuna- Chaona--aaapaiggr
Reviewed on OpenReview: optp::///pperevveel net/ forum? id- frd6sLdACS
Abstract
Recent studies reveal that deep representation learning models without proper regularization suffer from the dimensional collopse problem, ie., representation vectors span lower dimensional space. In the domain of graph deep represcntation lcarning, the phenomenon that the node representations are indistinguishable and even shrink to a constant vector is called oversmoothing. Based on the analysis of the rank of node representations, we find that representation oversmoothing and dimensional collapse are highly related to each other in deep graph neural networks, and the oversmoothing problem can be interpreted by the dimensional collapse of the node representation matrix. Then, to address the dimensional collapse and the oversmoothing together in deep graph neural networks, first find vanilla. residual connections and contrastive learning producing sub-optimal outcomes by ignoring the structured constraints of graph data. Motivated by this, we propose novel graph neural network named DrGNN to alleviate the oversmoothing issue from the perspective of addressing dimensional collapse. Specifically, in DrGNN, we design a topology-preservingg residual connection for graph neural networks force the low-rank of hidden representations close to the full-rank input features. Also, we propose the structure-guided contrastive learning to ensure only close neighbors who share similar local connections have similar representations. Empirical experiments DrGNN outperforms state-of-the-are deep graph representation baseline algorithms. The code of our method is available at the GitHub link: htttps://gitee com www.c//hhwweechhnnnnniiiooe
multiple real-world datasets demonstrate that
1 Introduction
Representation learning models have achieved outstanding performance for various application domains by outputting informative hidden representations, such computer vision and natural language processing. Recent studies (Hua et al. 2021 Jing et al. 2022 Guo et al., 2023) show that the deep representation learning models without proper regularization tend to produce representations that collapse along certain directions, known as the dimensional collapse, which can be further interpreted by the visualization of the singularity ranking of the matrices of representations Hua et al. 2021
"Equal Contribution

---

Published in Transactions on Machine Learning Research (10/2024)
With the advent of big data, graph structures recently received increasing research attention for their ability to encode complex interactions (Fu et al. 2024a b 2022). Similarly, the deep representation learning models on graphs are also found affected by representation issues. Especially, the node representation vectors outputted by deeper graph neural networks are not discriminative from each other and directly hurt the performance of node classification and link prediction tasks and their corresponding applications. This phenomenon is called
oversmoothing the graph representation learning domain (Li et al. 2018 Oono Suzuki 2020; Rusch
et al. 2023).
To begin with, we find that the oversmoothing in graph deep learning be interpreted by dimensional collapse from the low rank of the representation matrix. A dctailed theoretical derivation can be found in Appendix A To empirically demonstrate the existence of dimensional collapse in deep graph neural networks, we conduct a toy experiment on the Cora benchmark dataset (Lu & Getoor 2003) by exploring the rank the covariance matrix of the node representations. The analysis visualized Figure where the r-axis the index of the sorted singular values of the covariance matrix of the representation matrix, and the y-axis the logarithm of the singular value. In Figure 1 can see that the number of non-zero singular values much smaller than the number of representation dimensions for deep Graph Convolutional Network (GCN) (Kipf) & Welling 2017 This suggests that the representation matrix is low-rank, and the discrimination of node representation vectors only relies on few dimensions, which naturally increases the difficulty of effectively discriminating node presentations and makes tasks (e.g., node classification and link prediction) groundless.
GCN
-5
WGResNet
1- GNN
Log of singuler value
H
Dyver
-10
Input
Output
-15
Residual
-20
1-th GNN layer
-25
H
Z'
0
50
100
150
200
250
300
Index of sinqular valuue (a)
Full Rank
Low Rank
Full Rank
(b)
Figure 1: (a). A toy example on the Cora dataset demonstrates the rank deficiency, where GCN is chosen the backbone, the number of layers is set to 64, and the dimension of representation is 100. WGR and SCL are two major components of our proposed DrGNN, which are model-agnostic and can be added on GCN for example. (b) The visualization about how vanilla residual connections of neural layers turn the low-rank representation into a full-rank representation Z'.
However, stacking more graph neural layers is indispensable: in some cases (e.g., heterophily, long-range interaction, etc.). For example, for a certain query node, the close neighbors can have missing features and labels; then, we may need the information from distant neighbors to represent the query node, two case studies show in Section 3.2. According to the message passing of graph neural networks (Xu et al. 2018), adding one graph neural network layer equals aggregating information from one-hop neighbors, such that we need to stack multiple graph neural network layers. Thus, how to stack more graph neural network layers to maintain and even boost the representation power motivates our paper.
Addressing the dimensional collapse problem for deep neural networks, previous study of residual connec- tions (He et al. 2016) among neural layers can be an effective manner, i.e., it has been discovered that residual connections across neural network layers force the low-rank of hidden representations close to the full-rank input features (Jing al. 2022), shown in Figure I (b). The residual connections pave the way for climinating the dimensional collapse for deep neural networks and indicate the de-oversmoothing probability for deep graph neural welworks, but for non-IID graph data, the vanilla residual connections ignore the topological assumption of homophilous graph data that closer neighbors are more important during the embedding process. Formally, adding vanilla residual connection can induce the drawback of what we call the "shading neighbors" effects, i.c., close neighbors become less important during the neural representation process. The details discussed in Section 2.2
2

---

Published in Transactions on Machine Learning Research (10/2024)
Structure- Guided Contrastive Learning (SCL)
Weight Weight-Decaying Graph Residual Connection
Attract Repel
(WG-ResNet)
HOLD)
XOL:)
V
x(2.)
GNN Hidden Layer #1
H(3.:)
GNN Hidden Layer #l-2
x(3.))
GNN Hidden Layer #i-1
GNN Hidden Layer
X(6.)
H(6.))
H(A.)
X(4.)
x(S.)
(
Input Graph Features
Arbitrary GNN
Output Graph Representations
Figure& 2: An Arbitrary GNN Backbone with the Proposed DrGNN.
Moreover, for the oversmoothing phenomenon in the graph representation learning domain, the direct result is that individual representations are indistinguishable. Hence, contrastive learning serves as viable solution, but the existing work (Guo et al. 2023 simply introduces vanilla contrastive loss as a regularization while lailing to consider the topological relationship of positive and negative pairs.
Facing the latent dimensional collapse problem (i.e., non-sufficient singular values of covariance matrix of representations) and observable oversmoothing problem (i.c., non-discriminative node embedding vectors), propose two effective solutions, i.e., Weight-Decayingg Graph Residual Connection (WG-ResNel) and Sauucture-Guidee Contrastive Learning (SCL) for deep graph neural networks. In brief, WG-ResNet applies weighted residual connections to preserve the input graph topology, and SCL also weighs different positive and negative pairs based on their topological relations. Besides the theoretical analysis, a visualization of SCL, and We-ResNet addressing dimensional collapse is also shown Figure [ (a). Moreover, can be observed that SCL itself can alleviate the dimensional collapse to some extent, i.e., alleviating oversmoothing by contrastive learning alleviate the dimensional collapse, which suggests the close relationship between dimensional collapse and oversmoothing.
Hence, we propose an end-to-end graph neural network model DrGNN, which encloses SCL and WG-ResNet in a model-agnostic manner to help arbitrary graph neural networks go deeper elfectively compared to state- of-the-art baselines, supported by theoretical and empirical analysis. Furthermore, we designed extensive ablation studics to show that SCL and WG-ResNet both contribute to boosting the representation power, and their combination reach optimal results in terms of node classification.
2 The Proposed DrGNN
In this section, we begin with the overview of DrGNN and then provide the details of the Weight-decaying Graph Residual Connection (WG-ResNet) and Struclure-guided Contrastive Learning (SCL.. We formalize the problem of graph embedding within the context of an undirected graph G = (V, where V consists of nodes, & consists of m edges, X Rxd denotes the feature matrix and d is the fcature dimension. We let A E R= denote the adjacency matrix and denote A, E R" as the adjacency vector for node is the hidden representation vector of U;.
H; E R
2.1 Overview
The overview of our proposed DrGNN is shown in Figure 2 and DrGNN consists of two parts, including the graph architecture WG-ResNet and contrastive loss SCL. Specifically, the green dash line stands for WG-ResNet, where (1) the I-th layer will be adjustod by its second last layer (l-2) and the first layer H with proper weights. The red dash line in Figure 2 stands for SCL, where we sample positive node pairs and negative node pairs based the input graph topology such that the hidden representations of
3

---

Published in Transactions on Machine Learning Research (10/2024)
positive node pairs get closer and negative ones are pushed farther apart. The overall of DrGNN in terms of loss functions and architectures is expressed as follows.
LDIGNN = LONN + aLscL
(1)
where NGNN denotes the loss the downstream task (e.g., node classification) using an arbitrary GNN model (e.g., GCN (Kipf & Welling, 2017)) equipped with WD-ResNet,, LSCL the structure-guided contrastive loss function, and a is a constant hyperparameter. The details of WG-ResNet (Section 2.2) and SCL (Section 2.3
are introduced below.
2.2 Weight-Decaylnn Graph Residual Connection (WG-ResNet)
As shown in Figure (b), the vanilla residual connections (e.g., ResNet (He et al.] 2016) ) have the potential to alleviate the dimensional collapse of deep neural networks. But for deep graph neural networks, discover that simply adding residual connections leads the sub-optimal solution. As the way of ResNet stacking graph neural network layers, the importance of close neighbors' features gradually decreases during the GNN information aggregation process, and the faraway neighbor information becomes dominant. More concretely speaking, bocause the residual connection of ResNet connects the current neural layer with its second last layer, taking graph convolutional network (GCN) (Kipl Welling 2017 as an example, the vanilla residual connection of ResNet is expressed as follows.
H (1) (ABLU(AH" (M w(())) + (
(2)
where 1(2 2) denotes the index of layers, (1 and (1-2) are the hidden reprosentations at corresponding
layers, RELU is the activation function, ((1-)) is the learnable weight matrix, and Å is the re-normalized self-looped adjacency matrix with Å D- Á and Á = A + I, where D is the degree matrix. Without. loss of generality, we can assume the last layer of GNNs | is divisible by 2. Then, just by extending the dangling (( iteratively (e.g., first substituting ( with its previous residual blocks), the above Eq. 2 for the standard residual connection (i.e., the way of ResNet (He et al., 2016)) could be rewritten as follows.
H
(- ((-1)) + + (H
+ (1-4)
+...+ RELU (A ( + + "
Information aggregated from the faraway neighbors
Information aggregated from the uearest neighbors
According to (Xu et al. 2019; stacking / layers in GNNs and obtaining (()) can be interpreted as aggregating information from 1-hop neighbors for node hidden representations. As shown in Eq. B when we stack more layers in GNNs, the information collected from faraway neighbors becomes dominant (as there are more terms regarding the information from faraway neighbors), and dilutes the information collected from the nearest neighbors (e.g. I-hop or 2-hop neighbors). This phenomenon contradicts the general intuition on homophilous graph that the close neighbors of node carry the most important information, and the importance degrades shading neighbors effect when stacking
with faraway neighbors. Formally, describe this phenomenon graph neural layers, as the importance of the nearest neighbors is diminishing, As the enlarging the field of information aggregation, this way cannot essentially get rid of the overshooting problem. We empirically demonstrate that the shading neighbors effect degrades GNN performance in downstream tasks in Section F Specifically, we show that (1) vanilla residual connection of Ros exhibits the shading neighbors effect in graph representation ation learning; (2) jumping knowledge {Xu el al. 2018 can be a viable solution to miligate the shading neighbors effect to some extent; (3) our proposed We-ResNet achieves the best effectiveness in addressing the shading neighbors effect.
To formally introduce our proposed generic graph architecture, i.e., Weight-Decaying Graph Residual Connection (WG-ResNet), we first introduce the formulation and then provide insights regarding why it can work. Specifically, our WG-ResNet introduces the layer similarity and weight decaying factor as follows.
H ()) 11/ 0 + (-2) and O (
(4)
4

---

Published in Transactions on Machine Learning Research (10/2024)
where cos(H())
( " measures the similarity between the (-th layer and the 1-st layer, and we use the exponential function e(-) to map the cosine similarity ranging from [-1, to [e et] to avoid the negative similarity weights. Moreover, the term e e-//A is the decaying factor to further adjust the similarity weight of H where X is a constant hyperparameter.
--) (
Our introduced similarity (o -11 is not fixed but dynamic during each training iteration to reflect the optimized similarity of different layers, which also expands the hypothesis space of deeper GNNs. More importantly, the introduced decaying factor e -I/A aims to mitigate the shading neighbor effect by strengthening layer-wise dependency and preserving topology information in deeper GNNs. As X is positive constant, the value of e-I/A is decreasing as increases, such that the later stacked layers become less influential than the previously stacked ones due to the decaying weight. In contrast, without the decaying factor, the layer-wise weights remain independent, and the shading neighbors effect persists. Moreover, we visualize the layer-wise weight distribution of different residual connection methods and their effectiveness in Appendix B. From another perspoctive, the hyperparameter X of the docaying factor actually controls the number of effective neural layers in deeper GNNs, i.e., after the effeclive layer, slacking more loyers jusl maintains the performance or brings marginal upgrade. We find its value directly related to the diameter of the input graph, and this finding is quite important to avoid heavy hyperparameter tuning. The detailed discussion can be found in Section 3.4
2.3 Gurddd Contrastive Learning (SCL)
According to (Hua el al. 2021 Jing el al. 2022), ivvtrastive representation learning met hods show success in preventing dimensional collapse for image recognition. For graph data, the contrastive methods are able to construct the positive and negative sets and minimize the similarity of the negative pairs (Wang & Isola 2020: Guo et al. 2023). However, simply adopting the idea of contrastive regularization in deep graph neural networks could not fully alleviate the oversmoothing issue due to ignoring the topological relation of non-IID graph data. To address this issue with the geometry consideration, we propose the peructure-guided Contrastive Learning (SCL) as follows. Intuitively, for anchor node 84 its positive sample (i.e., connected node) should have close node representations, and its negative sample (i.e., disconnected node) should have discriminative node representations. Moreover, we propose a and to distinguish the importance of positive and negative samples based on the input structure.
LSCL = BB, EV EA, (ory (og(((znzz))) - E
BEMEN, lou - fzzs11-(zi,000 zx))]] + dist (A,, Ac)/n
1 - dist A,)/n Oij m EepEEvee (1- dist Av, Ag)nn)
2
n²
n² nm EoreVoweN, (1+ dist (Ar, Aw)/n) and Yik
(5)
where the connected odge (e,, 2yy) forms the positive pair, and the disconnected edge (u), 02) forms the negative ab
pair. 2, "(H,,),, g()) is an encoder mapping H f(-) is similarity function (e.g., f(a, b) ( ) (.) is a distance measurement function (e.g., hamming distance (Norouzi et al. 2012)), Nr is the set containing one-hop neighbors of node U. Ni is the complement of the set Ni, m is the number of edges and n is the number of vertices. Morcover, (Dy, 1y.) iterates over all connected edges in the input graph, and (uy, (gr) iterates over all disconnected edges in the input graph.
The intuition of Eq. is to maximize the similarity of the representations of the positive pairs and to minimize the similarity of the representations of the negative pairs, such that the node representations become discriminative. In which process, some previous research works (Perozzi et al. 2014 Grover & Leskovee 2016 Le 2021) would first assume that the importance of cach edge is identical. However, such an assumption does not always get satisfied in many applications (Velickovic et al. 2017 Faisal el al. 2015). To address this issue, we reweigh the importance of edges by considering the graph topological structure via importance scores o and 7. Therefore, for a positive pair, if two nodes have similar topological structures (c.g., ogo-networks), the importance score a of this node pair should be large; but for negative pair, two nodes also have similar topological structures, the importance score y of this negative pair should be small.
5

---

Published in Transactions on Machine Learning Research (10/2024)
Next, we show how our proposed SCL mitigates the oversmoothing issue with the theoretical analysis. Note that, in the following ien,vation, we refer the edge to any possible connection, which can be either an existing edge or a non-existing edge. To be specific, if node and node k do not connect in the input graph, then Eis represents the non-cxisting edge between node i and node k, denoted as a negative edge.
To begin with, we denote the probability of sampling a connection Faj and it is a positive connection as Pe Ppos (Biz) x P(Eij, y = 1), i.e., the sampled pair of two nodes v, and Vj connect in the input undirected graph. Then, (E,g) can be further expressed prior probability that the sampling is positive, and ozj is the conditional probability for the joint probability Note that positive connection (e.g., Exy) stands for two connected nodes and by forming a positive pair. Similarly, for disconnected two nodes es and Uh (i.e., the negative pair or negative connection Ex). we denote ( = Yu. Pney ( (Ex), where (x)) = - 2m is the prior probability of sampling a negative connection, and we interpret Yik as the conditional probability for the joint probability Pneg(Eas, Finally, we denote 0 to be the parameters of the multi-layer GNN model Go(-), i.e., Z = Go (, X), such that we can prove that SCL could alleviate the oversmoothing issue from the perspective of generative adversarial network (GAN) [Goodfellow et al. 2014 as follows.
(
o.gPpox (Eig), where Paaa
x= is the
Proposition 2.1. LSCL, the loss function based on contrastive learning, can be interpreted as the objective function of a generalive adversarial network (GAN) [Goodfellow el al. 2014),
min Lscr. max [ (F) + Pang (B) log(1 D(E)))dE 8
where D(E)= 2,), is the discriminator of GAN with edge F. = (v,, Uj) being connected or not, by node representations z; and 2z. Probabilities P Pooe = o oPpos (F)) and (E) = Pneg(E)) are defined above. (Proof in Appendio (
[(,;,)
According to Proposition 2.1 the proposed LSCI. can be interpreted as distinguishing the existence of a certain edge based on the representation vectors of two nodes. Next, we then derive how this design helps, as regularizer, alleviate the oversmoothing problem [Rusch al.) 2023) (i.e., hidden representation vectors of different nodes are similar given selected distance function) based positive and negative samples.
Theorem 2.2. Given an optimized discriminator (F.,,, to achieve the oplimization process of Proposi- tion 2. regularization term LSCL enforces that connected nodes have different representation vectors than disconnected nodes. The theoretical optimun 1 of (E) is Pg))(E) PncclE) (Proof in Appendia C
3 Experiments
In this section, we design comprehensive experiments to answer the following research questions.
RQI: When do we need more layers of graph neural networks? (Answered in Section 3.2
RQ2: When it is necessary to be deep, can DrGNN alleviate dimensional collapse and maintain or even boost task performance for deeper architecture? (Answered in Section 3.3 and Section 3.4)
RQ3: In practice, can DrGNN be agnostic to help various off-the-shelf graph neural network architectures? (Answered in Section 3.5
RQ4: Is every component of DrGNN helpful and irreplaceable? (Answered in Appendic F
3.1 Experiment Setup
Datasets. Com LL & Getoor 2003) dataset is a citation network consisting of 5,429 edges and 2,708 scientific publications from 7 classes. The edge in the graph represents the citation of one paper by another. CiteSeer [L & Getoor 2003) dataset. consists of 3,327 scientific publications which could be categorized into 6 classes, and this citation network has 9,228 edges. PubMed (Namata et al. 2012) is a citation network consisting of 88,651 edges and 19,717 scientific publications from classes, Reddit (Hamilton et al. 2017b)
In practice, the optimum discriminator usually approximated by the converged neural network.
6

---

Published in Transactions on Machine Learning Research (10/2024)
dataset is extracted from Reddit posts, which consists of 4,584 nodes and 19,460 edges. Notice that we follow the splitting strategy used in (Zhao & Akoglu 2020) by randomly sampling 3% of the nodes as the training samples, 10% of the nodes as the validation samples, and the remaining 87% as the test samples. Moreover, we follow the OGB benchmark (Hu et al. 2020 for the largo-scale dataset OGB-arXiv (Wang et all 2020
which is a citation network and consists of 1,166,24, 243 edges and 169,343 nodes from 40 classes. Also, we adopt. the non-homophilous benchmark (Lim et al. 2021) for the heterophilous version of OGB-arXiv, which is denoted as Xrvvv-year and the edge homophily is just 0.222.
Baselines. We compare the performance of our method with the following baselines: (1) GCN (Kipf & Welling 2017 the vanilla graph convolutional network; (2) GCNII (Chen et al., 2020): an extension of GCN with skip connections and additional identity matrices; (3) DGN (Zoou et al. 2020): the differentiable group normalization for GNNs to normalize nodes within the same group and separate nodes among different groups; (4) PairNorm (Zhao & Akoglu 2020): a GNN normalization layer designed to prevent node representations from becoming too similar; (5) DropEdge (Rong ct al., 2020 : a GNN-agnostic framework that randomly
removes a certain number of edges from the inpul graph; (6) RevGCNDeeep (Li et al.] (021]: equilibrium
model based deep graph neural networks; (7) EGNN (Zhou et al. 2021 Dirichlet energy constrained deep
graph neural networks; (8) ContraNrom (Guo et al. 2023 : a contrastive learning-based layer normalization
method. Detailed reproducibility with released code can be found in Appendix
3.2 When do need more layers of graph neural networks?
Case 1: Missing Features. We first consider a scenario where some altribute values are missing in the input graph. In such cases, shallow GNNs may not perform well because they cannot gather enough information from close neighbors due to the presence of numerous missing values. By increasing the number of layers, GNNs can gather more information and capture latent knowledge to compensate for missing features. To verify this, we conducted the following experiment: we randomly masked p% of attributes (i.e., setting the masked attributes to be 0), gradually increased the number of layers, and recorded the accuracy for each setting. In this case study, we selected the number of layers from the set f2, 4,5, 6, 7,8, 9, 10, 15, 20, 25, 30, 40, 50, 60), and the backbone model used was GCN. For a fair comparison, we added residual connection of ResNet (He) et al. 2016) to baselines if adding it could enhance the baseline's performance, denoted as (+RC). We repeated the experiments five times and recorded the mcan accuracy and standard deviation.
Table 1: Node Classification by Masking p% of Input Node Attributes (L denotes the number of layers that achieves the best performance).
Node Feature Missing Rate
== 25%
p p= 50%
P 75%
Dataset
Method
Accuracy
L
Accuracy
L.
Accuracy
L
GCN (+RC)
0.7503 1 0.0101
7
0.7435
0.0048
10
0.7226
0.0099
10
PairNorm (+RC)
0.7529 1 0.0129
10
0.7482
+ 0.0172
20
0.7262
1: 0.0178
40
Cora
DropEdge (+RC)
0.7634 1 0.0112
15
0.7611
= 0.0102
20
0.7297
0.0168
8
GCNII (+RC)
0.2667 + 0.0063
25
0.3351 = 0.0066
25
0.2914
1: 0.0106
40
DGN
0.6850 = 0.0184
30
0.6846
= 0.0147
50
0.6717
0.0156
25
ContraNorm (+RC)
0.7319 - 0.0099
2
0.7189
= 0.0091
3
0.6902
+ 0.0107
3
DEGNN
0.7915 = 0.0060
10
0.7848
0.0043
20
0.7598
0.0081
60
GCN (+ RC)
0.6141 + 0.0080
4
0.5811
- 0.0093
10
0.5141 + 0.0173
9
PairNorm (+ RC)
0.6184 + 0.0087
0.5947
0.0083
20
0.5176
0.0075
10
CiteSeer
DropEdge (+RC)
0.6348 - 0.0156
4
0.6083
= 0.0128
0.5240 6
_ 0.0128
10
GCNII (+RC)
0.2453 = 0.0045
40
0.2338
0.0028
20
0.2403
0.0046
25
DGN
0.4560 _ 0.0162
20
0.4593
= 0.0117
15
0.4498
- 0.0292
15
ContraNorm (+RC)
0.5893 = 0.0114
0.5621
0.0111
0.4646
+ 0.0076
4
DrGNN
0.6524 + 0.0087
20
0.6169 = 0.0063
60
0.5576 + 0.0070
50
From Table 1. we find that when the missing rate is 25% shallow GCN with residual connections has enough capacity to achieve the best performance. Given that, our proposed method further improves the performance by more than 3.83% on the CiterSeer dataset and 4.08% on the Cora dataset by stacking a few layers. However, when we incrcase the missing rate to 50% and 75%, we observe that most methods tend to achieve the best performance by stacking more layers. Specifically, PairNorm achieves the best performance at 10 layers when 25% features are missing, while it has the best performance at 40 layers when 75% features
7

---

Published in Transactions on Machine Learning Research (10/2024)
missing. A similar observation could also be found with GCNII on the Cora dataset, DropEdge the CiteSeer dataset well as our proposed methods in both datasets. Overall, the experimental results verily that the more features a dataset are missing, the more layers GNNs need to be stacked to achieve better performance. Our explanation for this observation that the number of layers increases, more information will be collected from the distant neighbors to recover the missing information of its close neighbors.
Case Missing Labels. We then conducted another case study using toy example demonstrate that nearby neighbors may not necessarily share similar contents. Initially, we utilized an existing package (specifically, the draw circle function in the Scikit-learn package) to generate synthetic dataset with 1,000 data points and a noise level set to 0.01. Subsequently, we computed the Euclidean distance between cach pair of data points. If the distance between two data points less than a predefined threshold, we connect them a graph, resulting in the derivation the adjacency matrix with added self-loops. Following this, we randomly sampled 1% of the data points as the training set, 9% as the validation set, and 90% as the test set. These data points are visualized in Figure 3a and the corresponding experimental results are presented in Figure 3b In Figure 3al we observed that the query node (i.e., the blue diamond within the dashed circle) could not just rely on its closest labeled neighbor (i..,, the red star within the dashed circle) to prodict its label (red or blue) correctly. Exploring longer paths consisting of more similar neighbors can help to accurately predict its label as blue (as indicated by the blue star within the dashed circle). Figure 3b compares the classification accuracy of shallow and deep GNNs with the same backbones. Notably, deeper GNNs exhibited a significant performance improvement of over 11% compared to shallow ones, contributing their capability of exploring longer paths in the graph.
Query
Node
0.6
0.4
SGC
DrGNN/SGC]
GCN
DIGNN(GCN)
(b)
Figure 3: A Toy Example to Demonstrate the Benefit of Deeper GNN Models: (a) Two groups of nodes in the semi-supervised setting. Stars are labeled, dots are unlabeled, and the diamond is the query node. Euclidean distance between two nodes determines the edge connection. (b) Comparison of node classification accuracy between shallow and deeper GNN models using data on the left. The deeper GNNs are realized by DrGNN with the corresponding same backbones.
Case 3: Heterophilous Graphs. In this section, we evaluate the performance of DrGNN on a large heterophilous graph (i.e., arXiv-year) from the benchmark [Lim et al. 2021 brief, heterophily means the connected two nodes do not share the same label.
Table 2: Node Classification on the arXiv-year dataset.
Method
arXiv-year
Method
arXiv-year
GCN
0.4602 + 0.0026
GAT
0.4605 + 0.0051
GCNJK
0.4628 + 0.0029
GATJK
0.4580 + 0.0072
APPNP
0.3815 + 0.0026
H₂GCN
0.4909 + 0.0010
MixHop
0.5181 + 0.0017
GPR-GNN
0.4507 + 0.0021
GCNII
0.4721 + 0.0028
DrGNN (10 layers)
0.4816 + 0.0008
DrGNN (20 layers)
0.4835 + 0.0008
DrGNN (30 layers)
0.4871 + 0.0007
DrGNN (50 layers)
0.4995 + 0.0006

---

Published in Transactions on Machine Learning Research (10/2024)
As shown in Table 2 our DrGNN achieves the second place performance in terms of node classification accuracy, among other state-of-the-art graph neural network methods. Also, we can observe that stacking more layers can increase the performance of DrGNN, because multi-hop neighbor information is aggregated for the message passing in hoterphilous graphs. The reason why DrGNN can not achieve the best is that, although stacking layers can aggregate information from multi-hop neighbors, the loss SCL is still regulating that close neighbors should share similar representations, which is generally based on the homophilous condition for more common settings. Note that our design of DrGNN is not solely for heterphilous graphs but for how to stack layers wisely for upgrading performance when the stacking operation is necessary and unavoidable. Heterophily is not the only reason for stacking graph neural layers; at least, the reasoning can also originate from missing features and labels, as shown above, where we need to stack more graph neural layers to mitigate the missing features by incorporating more neighbors.
3.3 Effectiveness Analysis of DrGNN
Motivated by the above subsection, we then aim to answer the question: whether our DrGNN can perform if stacking more layers is inevitable? Therefore, we prepare different deep settings to test if DrGNN can always outperform bascline methods.
In Table 3 for a fair comparison, the backbone model for all methods we used in these experiments is GCN, and we set the dimension of the hidden layer to 50 and vary the number of hidden layers from 2 to 16, 32, and 64 for all methods. Additionally, in Table 4 we test DrGNN
the largo-scale dataset OGB-arXiv, where we fix the feature dimension of the hidden layer as 100, set the total iteration to 3000, and choose GCN as the backbone model. Due to memory limitations, we set the number of layers to 2, 10, and 20. The experiments are repeated 5 times, and we record the mean accuracy as well as the standard deviation.
Table 3: Node Classification on Small Datasets with Varying Layers L (GCN as the Backbone).
Dataset
Method
L
L 16
L 32
=
GCN
0.7643
0.0040
0.5262 + 0.0732
0.3284 + 0.0066
0.3274 + 0.0189
PairNorm
0.7818 + 0.0027
0.6080 + 0.0310
0.5138 + 0.0299
0.2932 + 0.0120
DropEdge
0.7828 0.0075
0.7557 1 0.0072
0.7306 + 0.0134
0.2685 + 0.0647
Cora
GONII
0.6778 0.0065
0.7237 + 0.0055
0.7142 + 0.0015
0.7107 + 0.0047
DGN
0.7545 + 0.0003
0.6785 + 0.0169
0.7067 + 0.0190
0.7104 + 0.0192
ContraNorm
0.7682
0.0044
0.6590 + 0.0291
0.5128 = 0.0241
0.4328
0,0320
DrGNN
0.7768 0.0057
0.8002 1 0.0058
0.7961
- 0.0055
0.8022
1 0.0061
GCN
0.6452 + 0.0072
0.4514 + 0.0987
0,2689 - 0.0099
0.2680 + 0.0093
PairNorm
0.6030 0.0153
0.2268 + 0.0398
0,2096
= 0.0029
0.2076 + 0.0033
DropEdge
0.6532 0.0068
0.6117 + 0.0229
0.5101
+ 0.0430
0.2138 + 0.0198
CiteSeer
GCNII
0.5912 + 0.0106
0.6180 + 0.0031
0.6159
+ 0.0019
0.6101 + 0.0017
DGN
0.4872
0.0168
0.4753 + 0.0591
0.4604
- 0.0162
0.4417
0.0219
ContraNorm
0.6263
0.0061
0.4621
+ 0.0237
0.3965
+ 0.0196
0.2128
+ 0.0208
DrGNN
0.6577 + 0.0065
0.6650
+ 0.0059
0.6655
+ 0.0031
0.
+ 0.0066
GCN
0.7990
0.0017
0.5383
+ 0.0200
0.5463
0.0391
0.5566
0.0086
PairNorm
0.8120
0.0076
0.4408 + 0.0683
0.3972
+ 0.0094
0.3960
+ 0.0097
DropEdge
0.8035 + 0.0020
0.7893 + 0.0042
0.7902
- 0.0032
0.3951 + 0.0108
PubMed
GCNII
0.8070 0.0009
0.8094 + 0.0010
0.8089
= 0.0007
0.8097 1 0.0009
DGN
0.7947 0.0358
0.7553 + 0.0295
0.7733
+ 0.0143
0.7632 + 0.0226
ContraNorm
0.8061 + 0.0020
0.5672 + 0.0684
0.4348
+ 0.0379
0.3971 + 0.0057
DrGNN
0.8175
0.0016
0.8097 + 0.0038
0.8098
- 0.0025
0.8109 + 0.0033
GCN
0.8757
0.0054
0.8540 + 0.0451
0.3655
+ 0.0251
0.3410 t 0.0288
PairNorn
0.7704 + 0.0052
0.8636 + 0,0448
0.6468
= 0.0429
0.1230 + 0.0299
DropEidge
0.8564 0.0059
0.8526 + 0.0046
0.5384
0.1099
O. 1013
0.0148
Reddit
GONII
0.6184 0.0108
0.7157 + 0.0016
0.6972
+ 0.0039
0.6963 + 0.0059
DGN
0.7829 + 0.0137
0.7397 + 0.0371
0.6806 - 0.0639
0.5058 + 0.0754
ContraNorm
0.6576 + 0.0094
0.2563
+ 0.0091
0.2547 - 0.0170
0.2664 + 0.0140
DrGNN
0.8762 + 0.0060
0.9676 + 0.0033
0.9693 + 0.0023
0.9721 + 0.0011
Basod on the obscrvation in Table Table 4 we find that existing SOTA graph dc-oversmoothing methods, e.g., DropEdge, PairNorm, ContraNorm, achieve the best performance with the shallow layer (i.e., L 2),
and their performance begins to decrease the number of layers increases. However, DrGNN can outperform
9

---

Published in Transactions on Machine Learning Research (10/2024)
Table Node Classification on Large Dataset with Varying Layers (GCN as the Backbone)
Dataset
Mothod
L =
= 10
20
GCN
0.7136 + 0.0044
0.7021 + 0.0018
0.5377 + 0.0756
PairNorm
0.7186 = 0.0008
0.7158 = 0.0035
0.5796 + 0.0090
DropEdge
0.7178 - 0.0012
0.6531 = 0.0056
0.2198 + 0.0097
OGB-arXiv
GCNII
0.5966 = 0.0013
0.6340 = 0.0017
0.6246 + 0.0015
DGN
0.6039 = 0.0037
0.5746 = 0.0033
0,5027 = 0.0056
ContraNorm
0.7294 = 0.0025
0.6941
= 0.0030
0.5821
= 0.0324
DrGNN
0.7369 + 0.0014
0.7386
+ 0.0006
0.7401 + 0.0009
robustly if the GNN becomes deep, and the performance gain is obvious. For example, al layer 16, in the Cora dataset, DrGNN can achieve 80.02% accuracy. Additional comparison with RevGCN-Deep and EGNN can be found in Appendix
To echo with Table and Table we visualize the corresponding number of the nonzero singular values on those datasets in Figure In Figure 4 taking Cora and OGB-arXiv as examples, we observe that (1) PairNorm and ContraNorın begin to suffer from the dimensional collapse issue on both datasets when the number of layers is greater than 10; (2) Dropedge, DGN, and GCNII perform well on the small dataset but fail to preserve the full-rank representation the large dataset; (3) node representations by DrGNN full-rank on both datasets, indicating that DrGNN effectively alleviates the dimensional collapse.
QCN
DropEdge
DGN
GCN Contralumm Jhamm
Dropädge
DGN
GCN
Drop6dge GENI
DSN BrCWN
Cantrularm
CCMI
2:50th
G2M1
D:GRtN
Cantinllaam
Perhoum
6D
PerNoom
20
rikarm
50
mun 20 1o
Rumber medeure
30-
30-
200
20
20
(a) Cora. Datasel
(b) CiteSeer DaLaset
(c) PubMed Datasel
320
CCN
Dropfidge
DCN
Contraborm Partkorm
52741
Mumber-t nyrrero shoplte
90
Number of
70
10
90
20
(d) Reddit Dataset
(e) OGB-arXiv Dataset
Figure 4: The r-axis is the number of layers and the y-axis is the number of the non-zero singular values of the covariance matrix of the node representations by different methods.
Although the above results have proven that DrGNN outperform robustly in different deep settings, also observe that there seems to be peak in terms of the number of graph neural network layers. In other words, after certain depth, the performance gain seems marginal or missing. For example, in the Cora datasel, the performance of our DrGNN increases from 77.68% to 80.02% from 2 layers to 16 layers. However, the performances are maintained when stacking to the 32nd layer or the 64th layer. Therefore, we may ask if there are a number of effective ncural layers? and if the number exists, how can we find it before the training to avoid the heavy hyperparameter tuning process? Luckily, we found the answer in the following subsection.
10

---

Published in Transactions on Machine Learning Research (10/2024)
3.4 Number of Effective Layers in Deep Graph Neural Networks
We conduct the hyperparameter analysis of DrGNN, regarding in the weight decaying function of Eq. For example, when 10, the decaying factor for the 10-th layer is 0.3679 (i.e., e e=)); but for the 30-th layer, it is 0.0049 (i.c., 9). This decay limits the effective information aggregation scope of deeper GNNs because the later stacked layers will become signilicantly less important. Based on this controlling property of X, a natural follow-up question is whether its value depends on the property of imput graphs. Basically, it suggests that initially stacking a few layers is effective, but more deeper layers do not help (or do not help much) boost performance.
Interestingly, through our experiments, we find that the optimal À is very close to the diameter of input graphs (if it is connected) or the largest component (if it does not have many separate components). This observation verifies our conjecture regarding the property of X (i.e., it controls the number of effective layers or the number of hops during the message passing aggregation schema of GNNs). Hence, the value of À can be searched around the diameter of the input graph.
0.9
0.7
0.85
Agouracy
0.8
Agcurao
0.8
Acouracy
Accuracy
0.8
0.9
0.7
0.5
0.6
0.4
0.75
0.8
10
60
40
18
20
30
20 30
60
Lambda
Lambda
Lambda
Lambda
(a) Cora
(b) CiteSeer
(c) PubMed
(d) Reddit
Figure 5: Hyperparameter Analysis, L.e, À vs Node Classification Accuracy on Four Datasets.
In details, to analyze the hyperparameter X, we fix the feature dimension of the hidden layer to be 50, the total iteration is set to be 3000, the number of layers is set to be 60, the sampling batch size for DrGNN is 10, and GCN is chosen as the backbone model. The experiment is repeated five times for each configuration. In each sub-figure of Figure 5 the x-axis the value of X, and the y-axis is the accuracy of 60-layer GCN in the above setting.
Specifically, find that the optimal À 20 the Cora dataset, the optimal X = 10 on the CiteSeer dataset, the optimal À = 18 on the PubMed dataset, and the optimal X = 20 on the Reddit dataset. Then, natural questions to ask are (1) what determines the optimal value of À in different datasets? (2) can we gather some heuristics to narrow down the hyperparameter search space to efficiently establish effective GNNs?
Thus, we provide our discovery. In Eq. 1 we have analyzed that the decaying factor À controls the number of effective layers in deeper GNNs by introducing the layer-wise dependency. It means that larger À slows down the weight decay and gives considerably large weights to more layers such that they can be effective, and the information aggregation scope of GNN extends as more multi-hop neighbor features are collected and aggregated. In graph theory, diameter represents the scope of the graph, which is the largest value of the shortest path between any node pairs in the graph. Therefore, the optimal À should be restricted by the input graph, ie., being close to the input graph diameter.
Table 5: Graph Statistics of Each Datasel.
Metric
Cora
Citeseer
PubMed
Reddit
Number of Nodes
2,708
3,327
19,717
4,854
Connected Graph
No
No
Yes
Yes
Number of Components
78
438
1
1
Diameter of the Graph (or the Largest Component)
19
28
18
17
Interestingly, our experiments reflect this observation. Combining the optimal À in Figure 5 and the diameter in Table 5 for connected graphs PubMed and Reddit, the optimal À is very close to the graph diameter. This also happens to Cora (even though Cora is not connected), because the number of components is not large. As for CiteScer, the optimal X is less than the diameter of its largest component. A possible reason is that CiteSeer has many (i.e., 438) small components, which shrinks the information propagation scope, such that do not need to stack many layers and we do not need to enlarge À to the largest diameter (i.e., 28). In
11

---

Published in Transactions on Machine Learning Research (10/2024)
general, based on the above analysis, we find the optimal value of X can be searched around the diameter of the input graph.
3.5
Different Backbones of DrGNN
Here, we show the performance of our proposed DrGNN cooperating with different backbone models (e.g.,
GAT (Velickovic et al. 2018) and GraphSage (Hamilton et al. 2017a ). In Figure G we set the numbers of the hidden layers as 60 for all methods and the dimension of the hidden layer 50. The total number of training iterations is 1500.
1.2
DrGNN(GAT)
DrGNN(Graphhagg)
GAT
GraphSage
1.0
0.6
0.4
0.2
0.0
Cora PubMed
Reddit CiteSeer
Figure 6: Accuracy Different Backbone Models with 64 Hidden Layers on Four Datasets.
By observation, we find that both GAT and GraphSage tend to have worse performance when the architecture becomes deeper, and our proposed method DrGNN greatly boosts the performance by 40%-60% on average over four datasets. Specifically, compared with the vanilla GraphSage, our DrGNN boosts its performance by 43% on the CiteSeer dataset and more than 67% the Reddit dataset.
3.6 Discussion and Limitation
The major assumption of our proposed method is that the close neighbors of a node carry the most important information, and the importance degrades with faraway neighbors. This assumption is mainly based on the characteristics of homophilous graphs. In the experiments, we show the great performance of DrGNN in several homophilous graphs. Despite the limited assumption the heterophilous graph, our proposed method can still achieve competitive performance compared to the state-of-the-art methods, as shown in Table
4 Conclusion
In this paper, we focus on building deeper graph neural networks to effectively model graph data and illustrate the oversmoothing cause from the perspective of dimensional collapse. To this end, we first provide insights regarding why the vanilla residual connection of ResNet is not best suited for many deeper graph neural network solutions, i.e., the shading neighbors effect. Then, we propose a new residual architecture, Weight-deeaying Graph Residual Connection (WG-ResNet), to alleviate this effect. In addition, we propose Structure-guided Contrastive Learning (SCL) to alleviate the problem from another viewpoint, where utilize graph topological information, pull the representations of connected node pairs closer, and push remole node pairs farther apart via contrastive learning regularization. Combining WG-ResNet with SCT, an end-to-end model DrGNN is proposed for deep graph neural networks. We provide the theoretical analysis of our proposed method and demonstrate the effectiveness of DrGNN by extensive experiment comparing with state-offthe-art methods.
Acknowledgments
This work was supported by National Science Foundation under Award No. IIS-2117902, and the U.S. Department of Homeland Security under Grant Award Number, 17STQAC00001008-0 The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies the government.
12

---

Published in Transactions on Machine Learning Research (10/2024)
References
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020.
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. JMLR, 2011.
S. M. Faisal, Georgios Triantzioulis, Ali Murat Gok, Nikolaos Hardavellas, Seda Ogrenci Memik, and Srinivasan Parthasarathy. Edge importance identification for energy efficient graph processing. In 2015 TEFE International Conference on Big Data (TEEF BigData 2015), Santa Clam, CA, USA, October 29- November 1, 2015, pp. 347 354. IEEE Computer Society, 2015.
Dongqi Fu, Liri Fang, Ross Maciejewski, Vetle I. Torvik, and Jingrui He. Meta-learned metrics over multi- evolution temporal graphs In Aidong Zhang and Huzefa Rangwala (eds.), KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washinglon, DC, USA, August 14 18, ACM, 2022. doi: 01114/3534678.3556
2022, pp.
URL https://aoi.oor/10.. 111p:///0..14533334577
3589813
Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. Ver-graphormer: A mini-batch graph transformer via virtual connections. CoRR, abs/2403.16600 2024a. doi: 10.48550/ ARXIV 16030
URL http:///dd...og/1...4855///////
Dongqi Fu, Yada Zhu, Hanghang Tong, Kommy Weldemariam, Onkar Bhardwaj, and Jingrui He. Gen- crating fino-grained causality in climate time series data for forecasting and anomaly detection. CoRR, 2024b. doi:
httpp:://ooi..rrr//00448885
2408.04254
Ian J.
Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial networks. CoRR, hbbs/140.22611 2014. URL
http://arxiv.org tabbs/140...o 2661
Aditya Grover and Jure Leskovee. node2vec: Scalable feature learning for networks. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (cds.), Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, Son Francisco, CA, USA, August 19-17, 2016, pp. 855-864. ACM, 2016.
Xiaojun Guo, Yifei Wang, Tianqi Du, and Yisen Wang. Contranorm: A contrastive learning perspective on oversmoothing and beyond. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL http::///ppeneeiie.eeee////////p
SMTXkJouWHm
Will Hamilton, Zhilao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017a.
William L. Hamilton, Justine Zhang, Cristian Danescu-Nieulescu-Miill Dan Jurafsky, and Jure Leskovec. Loyalty in online communities. In Proceedings of the Eleventh International Conference on Web and Social Media, ICWSM 2017, Montréal, Québec, Canada, May 15-18, 2017, pp. 540 543. AAAI Press, 2017b.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 39: Annual Conference on Newral Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL httpp::/ httts::/pproceeddnggs neurips.cc/ppapeeeee b200hhai//f000111a44/22222222223
13

---

Published in Transactions on Machine Learning Research (10/2024)
Tianyu Hua, Wenxiao Wang, Zihui Xue, Sucheng Ren, Yue Wang, and Hang Zhao. On feature decorrelation in self-supervised learning. In 2021 TEEE/CV /CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pp. 9578 9588. IEEE, 2021.
Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. In NewrIPS, 2020.
Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive self-supervised learning. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Can M. Le. Edge sampling using local network information. J. Mach. Learn. Res., 22:88:1 88:29, 2021.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 6437 6449. PMLR, 2021.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In AAAI, 2018.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887 20902, 2021.
Qing Lu and Lise Getoor. Link-based classification. In Tom Faweett and Nina Mishra (eds.), Machine Learning, Proceedings of the Twenticth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pp. 496 503. AAAI Press, 2003.
Galilco Namata, Ben London, Lisc Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Minning and Learning with Graphs, volume 8, 2012.
Mohammad Norouzi, David J Fleet, and Russ R Salakhutdinov. Hamming distance metric learning. Advances in neural information processing systems, 25, 2012.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani (eds.), The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA August 24- 27, 2014, pp- 701-710. ACM, 2014.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In ICLR, 2020.
T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey oversmoothing in graph neural networks. CoRR, abs/2308 10993, 2023. doi: 10.48550 /005500//XXiv... /iv 2ttt..2333.0090 10993. //doi.org/10.
URL https
wwwpoo.//....... 11//100.8555//rxx http://aaxiv.......... 2303. 10993
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio.
Graph attention networks. CoRR, abss/1710. 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propagation. CoRR, 2020.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich- Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-417 413,, 2020.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through aligmment and uniformity on the hypersphere. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 9929 9939. PMLR, 2020.
Keyulu Xu, Chenglao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi,, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Sloekholmesmsssnn, Slockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1449-5458 PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In JCLR, 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In NewrIPS, 2020.
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 21834-21846 2021.
A Similarity between Oversmoothing and Dimensional Collapse
In (Rusch et al. 2023); the authors describe oversmoothing phenomenon that the node representation vectors are indistinguishable from each other and thus deteriorate the performance of downstream tasks, Inspired by this, we could mcasure the magnitude of graph oversmoothing by the metric of covariance mean as follows:
cocariance(1) = Σ (hi- Ti)(h: h)
h Σ h;
where h; is the node representation for node and covariance(h) = 0 indicates that the learned representation is indistinguishable and the deep model suffers from oversmoothing issue. Notice that the dimensional collapse is observed when the covariance matrix of the node representations is not full-rank (i.e., the number of non-zero singular values is less than the dimension of the node representation in Figure D When covariance(h) = 0, it also indicates that h; = hy = for all i and j, and the rank of the covariance matrix of the node representation matrix is 0 (While a large value covariance(h) does not mean that the performance is ). In other words, the graph model suffers from complete collapse, where all node representations shrink single point. Thus, we could that the oversmoothing issue highly related to dimensional collapse.
B Visualization of the Weight of Each Layer With Different Weighting Functions
Here, we visualize the weight of each layer with different weighting functions on the Cora dataset. In this experiment, we fix the feature dimension of the hidden layer to be 50; the total iteration set to be 3000; the
15

---

Published in Transactions on Machine Learning Research (10/2024)
344
++ DOMB DOMB
DOWDD Ret
20
04-
04-
02-
20
20
30
30
Figure 7: Weight Visualization. The y-axis represents the weight of each layer, and the r-axis represents the index of each layer, in deeper models.
number of layers set to be 60; the sampling batch size for DrGNN is 10; GCN is chosen the backbone model; is to be 20. In Figure 7 The z-axis is the index of each layer, and the y-axis is the weight for each layer. DrGNN-S removes the similarity measurement (co((H (H))) in Eq. and DrGNN-D removes the decaying weight factor and only keeps the exponential cosine similarity ( () to measure the weight for each layer. DrGNN-S achieves the simplified WG-ResNet in DrGNN, which removes the exponential cosine similarity ( (() in DrGNN. By observation, we find that (1) ResNet sets the weight of each layer to be 1, which casily leads to shading neighbors effect when stacking more layers, because the faraway neighbor information becomes more dominant in the GCN information aggregation; (2) without weight decaying factor, the weight for each layer in DrGNN-D fluctuates because they are randomly independent. More specially, the weights for the last several layers (e-g., L=58 or L==0) are larger than the weights for the first several layers, which contradicts the intuition that the first several layers should be more important than the last several layers; (3) the weights for each layer in both DrGNN and DrGNN-S reduce as the number of layers increase, which suggests that both of them could address the shading neighbors effect to some extents; (4) combining the results from Table 8 DrGNN achieves better performance than DrGNN-S, as it imposes larger weights to the first several layers, which verifies that the learnable similarity sim (1), fr))) achieves better performance with the enlarged hypothesis space for neural networks.
C Theoretical Proof
LSCL, the loss function based on contrastive learning, can be interpreted as the objective function of a generalive adversarial network (GAN) (Goodfellow el al. 2014),
Proposition 2.1
min LSCL. max / J (E) + P Pang (E) log(1 D(E)))dE
where D(E)= - [(2,, 23) is the discriminator of GAN with edge Fij = (wz, Uz) being connected or not, by node
representations z; and z,. Probabilities Ppos(E.)) = oig (Eiz) and (neg(Exx) = Thk (Ex).
Proof. Represent D(E) by f(z,, we can have
min LSCL = -E Rr e Eeo (f 2,))) + F. (7Hk log(1 f(z,, 2x +x)))] 0
min S (P (P))) (D(F)) (F)) D(F))d
Since Ppos: Paegs and D(-) are independent of 0, then
max / (Ppos (E) log ((E)) + (E) D(E)))dE
16

---

Published in Transactions on Machine Learning Research (10/2024)
Theorem 2.2 Given an optimized discriminator D*) to achieve the oplimization process of Proposition 2.1 regularization term LSCL enforces that connected nodes have different representation vectors than disconnected nodes. The theoretical optimum of D*) is (p)
P
Proof. Based on Proposition 2.1 a free D(E) is replaced by D(F) f(z;, zz).
s,=! According to Eq f(z,, 2,) |. then, f(zi, 2j) E Ele-
Next, consider a function a log(()) + log((e z), where and b are two positive constants, e Euler's number,
and x is a variable. Suppose that - 2 E e1,,,, it is easy to prove that the function a log(z) + bog((e - x) has the maximum in je je'), at a+b
Hence, we first have (E)
Proo EE)
Pyee (B) Pneg
Second, given (E) Pros(E) (E) Puee (B)
(F)
and P Proo (Eis) PioPpos(Ess) and Pneg(Ess) Vex Pee (Eik) defined
in Proposition 2.1 we have
+ P (B)
(
P pos F.) + 7 P Paagl
P(E = 1) 1)P =
P(Ely =
= 1) P(E P 0(y
Ply 1[))
Therefore, towards (E), D(E) is maximizing the conditional log-likelihood P(y = 1|B), where = indicates edge E is a positive (i.c., exiting) edge.
In other words, the discriminator D(F) is defined on a node pair terms of their representation vectors, i.e., DEE) is able to distinguish whether node pair is positive or not, then the corresponding hidden representations of different nodes are different. For example, for a positive (i.e., existing) edge (0e, 2/) and a negative (i.e., non-existing) edge (v,, uk), f(zi 2j) is maximized and f(z;, zx:) is minimized, then zy and z are different. Back to Proposition 2.1 node vectors žj and 25 are obtained through 0. That's why optimizing loss CSCL. can alleviate the oversmoothing problem, according to the definition of oversmoothing (Rusch et al. 2023), the final layer node representation vectors are similar given a certain threshold and a certain similarity function, and the common functions can be Dirichlet energy and mean-average distance.
D Reproducibility
For fair comparison, set the dropout rate to 0.5, the weight. decay rate to 0.0005, and the total number of iterations to 1500 for all baseline methods in Table D and Table 3 if not specialized, GCN is chosen the backbone, and the dimension of each layer is set to 50 for all the graph neural network bascline methods.
In Section for DrGNN and DrGNN-S, we sample 10 instances and 5 neighbors for each class from the training set, dist(-) is the hamming distance, and f(-) is the cosine similarity measurement.
The experiments are repeated 10 times not otherwise specified. All of the real-world datasets are publicly Windows machine with 16GB RTX 5000 GPU.
available. The experiments are performed
The code of our algorithm is in an anonymous link We provide the detailed experimental setting for each experiment shown in Table
Morcover, we set the learning rate to be 0.001 and the optimizer is RMSProp, which is one variant of ADAGRAD DDuchi et al. 2011)
17

---

Published in Transactions on Machine Learning Research (10/2024)
Table 6: Hyperparameters for DrGNN shown in Table
Method
DrGNN
Cora
x = 20, a = 0.03
CiteSeer
X = 10, = 0.02
PubMed
A == 18, = 0.1
Reddit
A 20, = 0.02
E Additional Effectiveness Analysis
We conduct the additional experiments by comparing our proposed method with RevGCN-Deep (Li et al., 2021) and EGNN (Zhou et al. 2021). We set the number of layers for all baseline methods to 60 for Cora, Citescer, PubMed, and Reddit. For the OGB-arXiv dataset, we set the number of layers 10 for all methods.
Table 7: Additional Node Classification Comparison.
Method
Cora (L 60)
CiteSeer (L = 60)
PubMed (L = 60)
Reddit (L 60)
OGB-arXiv (L = 10)
RevGCN DeeGGN-DDep
0.7458 + 0.0084
0.5137 + 0.0099
0.8139 + 0.0015
0.8853 + 0.0383
0.7354 + 0.0009
EGNN
0.7961 0.0036
0.6566 + 0.0060
0.8138
0.0026
0.8772 + 0.0040
0.7247 + 0.0015
GearGNN
0.8059 + 0.0028
0.6655 + 0.0117
0.8185 + 0,0016
0.9721 + 0.0011
0.7401 + 0.0009
F Ablation Study of DrGNN
Here, we conduct the ablation study to show the effectiveness and irreplaceability of WG-ResNet and SCL in terms of node classification in Table g In this experiment, we fix the total iteration set as 3000, and GCN is chosen as the backbone model. For the Cora dataset, the feature dimension of the hidden layer is 50 and the number of layers 64; for the OGB-arXiv dataset the feature dimension of the hidden layer is 100 and the
DrGNN-T removes SCL, DrGNN-D removes the weight decaying factor in WG-ResNet and DrGNN-JK replaces the WG-ResNet by Jumping Knowledge (Xu et al. 2018).
number of layers 20. In Table @
Table 8: Ablation Study w.r.t. Node Classification Accuracy.
Method
Cora (L- = 64)
CiteSeer (L 64)
PubMed (L- = 64)
Reddit (L = 64)
OGB-arXiv (L = 20)
GCN (+RC)
0.7252
0.0176
0.6213 + 0.0056
0.7985
0.0068
0.9432 + 0.0087
0.7144
0.0013
DrGNN-D
0.7498 = 0.0139
0.6567 1 0.0052
0.8050
0.0031
0.9654 1 0.0028
0.7363
0.0011
DrGNN-T
0.7875 = 0.0092
0.5750 1 0.0244
0.8078 + 0.0047
0.9397 1 0.0042
0.7335 +: 0.0024
DrGNN-JK
0.7955
0.0078
0.6600 + 0.0085
0.8061 + 0.0038
0.9659 + 0.0046
0.7368 + 0.0012
DrGNN
0.8022 0.0061
0.6685 + 0.0066
0.8109
0.0033
0.9721 + 0.0011
0.7401 + 0.0009
In Table 8 we have the following observations (1) comparing DrGNN with DrGNN-T, we find that DrGNN boosts the performance by 1.84% on the Cora dataset after adding SCT., which demonstrates the effectiveness of SCL to alleviate the oversmoothing issue; (2) DrGNN outperforms DrGNN-D on Cora dataset by 5.61%, which shows that DrGNN could alleviate the shading neighbors effect by adding the weight decaying factor; (3) comparing DrGNN with DrGNN-JK, we verify that our proposed WG-ResNet is more effective than DrGNN-JK. Besides, one drawback of jumping knowledge is its high memory required as the number of layers increases, while our proposed WG-ResNet doesn't; (4) DrGNN outperforms GCN (+RC) by more than 7.7% the Cora dataset and 2.6% the OGB-arXiv dataset, which indicates that NG-ResNet could alleviate the shading neighbors effect.
Also, we conduct an additional ablation study to evaluate the performance of each component (i.e., the cosine similarity function in Eq. / and SCL formulated in Eq. 5). In Table 9 DrGNN-S denotes the variant of DrGNN after removing the cosine similarity function in Eq. and SCL denotes the variant of DrGNN by removing the We-ResNet. We have the following observations: (1). DrGNN outperforms DrGNN-S on most datasets except PubMed, which suggests that introducing the layer similarity (i.e., cosine similarity between
18

---

Published in Transactions on Machine Learning Research (10/2024)
the finst layer and the 1-th layer) can increase the performance of DrGNN(2). Compared to ContraNorm, proposed structure-guided contrastive learning (SCL) can further boost the performance by more than 29% on average, which demonstrates the effectiveness of SCL over ContraNorm.
Table Additional Ablation Study w.r.t. Node Classification Accuracy.
Method
Cora (7. 64)
CiteSeer (I= 64)
PubMed = 64)
Reddit (L. = 64)
OGB-arXiv
20)
DrGNN
0.8022
0.0061
0.6685 + 0.0066
0.8109 + 0.0033
0.9721 + 0.0011
0.7401 + 0.0009
DrGNN-S
0.7931 + 0.0153
0.6355 = 0.0085
0.8173 = 0.0030
0.9621 = 0.0035
0.7335 = 0.0021
ContraNorm
0.4328 + 0.0320
0.2128 + 0.0208
0.3971 + 0.0057
0.2664 + 0.0140
0.5821 + 0.0324
SCL
0.5751 0.0264
0.3933 = 0.0076
0.7601 + 0.0043
0.9305 + 0.0266
0.6952 = 0.0011
G Additional Hyperarameter Analysis
Here, we conduct additional hyperparameter analysis of DrGNN, i... in the overall loss function of Eq
0.85
Accuracy
0.75
0.7
0.65
0.6
0
0.001
0.01
0.03
0.05
0.1
Alpha
Figure 8: Hyperparameter Analysis, i.e., a Node Classification Accuracy.
To analyze the hyperparameter in DrGNN, we fix the feature dimension of the hidden layer to be 50, the total iteration is set to be 3000, the number of layers is set to be 60, the sampling batch size for DrGNN is 10, GCN is chosen as the backbone model, and the dataset is Cora. We gradually increase the value of a and record the accuracy. The experiment is repeated five times in each setting. In Figure S the x-axis is a and the y-axis the accuracy score. By observation, when a = 1, the performance is worst and the performance begins to increase by decreasing the value of It achieves the best accuracy when 0.03. The performance starts to decrease again if we further decrease the value of a. We conjecture that when is large, it will dominate the overall objective function, thus jeopardizing the classification performance. Besides, the performance also decreases if we set the value of a to be small number (i.e., 0.001). ). In addition, comparing with the performance without using SCL regularization (i.e., a = 0), our proposed method with a = 0.03 can boost the performance by more than 1.8%, which demonstrates that our proposed SCL alleviates the issue of oversmoothing to some extent.
H Efficiency Analysis
Here, we conduct an efficiency analysis regarding our proposed method in the Cora dataset. We fix the feature dimension of the hidden layer to be 50, the total iteration is set to be 1500, the sampling batch size for DrGNN and DrGNN-S is 10, and GCN is chosen as the backbone model. We gradually increase the number of layers and record the running time.
In Figure 9 the z-axis is the number of layers and the y-axis is the running time in seconds. We observe that the running time of both DrGNN and DrGNN-S linearly proportional the number of layers. Comparing the running time of DrGNN, the running time of DrGNN-S further reduced after the weighting function in DrGNN (e.g,, sim(.) replaced by constant.
19

---

Published in Transactions on Machine Learning Research (10/2024)
1000
DrGNN-S
GCN RC)
DrGNN
8000
Running time
600
400
200
10
20
40
50
60
Number layers
Figure 9: The Number of Layers vs Running Time (in seconds) on Cora.
Sampling Method for SCL
To realize SCL expressed in Eq. 5 we need to get the positive nodes vy and negative nodes eg towards the selected central node e/- To avoid iterating over all existing nodes or randomly sampling several nodes, we propose to sample positive nodes ūj and negative nodes va from the star subgraph S; of the central node v;- Moreover, to make the sampling scalable and to reduce the search space of negative nodes, we propose batch sampling method.
existing edge
non-existing edge (negative pair)
(positive pair)
Figure 10: Batch Sampling. Each star node in the figure corresponds to node 02 in Eq.
As shown in Figure 10 the batch size is controlled by the number of central nodes (i.e., star nodes in the figure). For each central node, the positive nodes are those 1-hop neighbors, and the negative nodes consist of unreachable nodes. In our batch sampling, we strictly constrain that the positive nodes are only from the 1-hop neighborhood for the following three reasons: (1) they are efficient to be accessod; (2) considering all k-hop neighbors as positive will enlarge the scope of positive nodes and further decrease the intimacy of the directly connected nodes; (3) I-hop positive nodes in the star subgraph can preserve enough useful information, compared to the positive nodes from the whole graph. For the third point, we prove it through the graph influence loss (Huang & Zitnik 2020) in Proposition I.1 and the formal definition of graph influence loss is given in the following paragraph after Proposition
Proposition I.1 (Bounded Graph Influence Loss for Sampling Positive Pairs Locally). Taking GCN as an example of GNN, the graph inffuence loss R(v.) on node v. w.r.t positive nodes from the whole graph against positive nodes from the 1-hop neighborhood star subgraph is bounded by R(ve) S where is the number of nodes, de the degree of node ve including the self-loop, P is a
(n dd) (D constant, P_ is the path from center node ve to 1-hop outside node v, which has the maximal node influence Tog,o, and [P.] denotes the number of nodes in path P..
20

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. According to the assumption of (Wang & Leskovec 2020 o()) can be identity function and W can be identity matrix. Then, the hidden node representation (of node va) in the last layer of GCN can be written as follows.
Σ A
Doo o,EN
Then, based on the above equation, we can iteratively replace h (0)))) with its neighbors until the representation hg (oo) of node is included. The extension procedure is written as follows.
h(0)
1
Σ
Actt
Σ As
Do,e
Ds.
veN
AyEN;
1
Σ
An.gh
DR.k
v.ENi
The above equation suggests that the influence from the positive node Us to the center node ve is through the path p = (Ve, ,y...., Uk, v.).
Following the above path formation and assuming the edge weight A(i, as the positive constant, according (Huang Zitnik 2020), we can obtain the node influence Te of Us on ve as follows.
To 100h /ah S (P
1
where is constant, DM is the geometric mean of the degree of nodes sitting in path P, and P is the path from the positive node v, to the center node ve that could generate the maximal multiplication of normalizod edge weight, [P] denotes the number of nodes path P.
The above analysis suggests that the node influence of positive long-distang nodes is decaying.
Hence, the graph inffuence loss about learning node ve from the whole graph positive nodes versus from the 1-hop localized positive nodes can be expressed as follows.
Ia(ve) (vec = Locio + Lo +... + Lueiaaddo
a
H4
(IP 1Pl
H+
S (n de)
(D
where Ic(v.) denotes global influence, (v,) is the inffuence for star subgraph, de is the degree of node (including self-loop), and (D UP. is the maximal among all (D
Specifically, the graph influence loss (Hang & Zitnik 2020) R(ve) can be expressed as R(ve) = (vc) ((((v))-4 In (we), which is determined by the global graph influence on ve (ie.. (a(v)) and the star subgraph influence on ve (i.e., lz Then, to compute the graph influence Ig (v,), we need to compute the node influence each node Vi to node Ve, where node vy is reachable from node Ve- Based on the final output node representation vectors, the node influence is expressed Luc.u, |0 (o0((o))an /ah,"),, [|, and the norm can be any subordinate norm (Wagg & Leskovee 2020). Then, (v.v.) is computed by the L1-norm of the following vector, i.c., (v())) = [[ Le.. ... Io |ll.. Similarly, we can compute the star subgraph influence (ve)) on node Ve. The only difference that we collect each reachable node vj in the star subgraph L (i.c., 1-hop neighbors we show why positive pairs can be locally sampled with the support from graph influence loss of a node representation vector output by the GCN final layer.
of v.). Overall, in Proposition
21


Reviews:
[{"review_id": "4s0xkQEigu", "reviewer": "Reviewer_xkjz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "== Comparison to previous work ==\n\nBoth methods, proposed in this paper, were introduced previously (Chen et al., 2022, Guo et al., 2023) for the similar problem and are proposed here in a slightly modified form. The combination of the proposed methods, to our knowledge, was not introduced elsewhere.\n\n==Theory==\n\nThe authors introduce the theoretical basis for the proposed method, including the proof of the propositions 2.1 and 2.2. The experiments are sufficient to show the performance of the model.\n\n==Method==\n\nThe method is well described and the notation is correct.\n\n=== Pros === \n\nSolid maths and detailed experiments.\n\n===Cons===\n\nThe experiments description is missing. It would be helpful to know, what we were predicting, what are the metrics etc. If the reader is unfamiliar with this type of GNNs, it would be difficult to understand the outcomes of the experiments.\n\nThe methods are not particularly novel by themselves, but the combination of methods is. It was shown that this combined approach surpasses the state-of-the-art methods.\nHowever, the experimental setup is unclear. \nAt the same time, in the appendix the authors show that this method does not produce the best solution for a different dataset (ArXiv). This message is important and this result, together with the discussion about the method limitations, should be included in the “Results and Discussion” section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Paper review for manuscript DrGNN: Deep Residual Graph Neural Network with Contrastive Learning\n\n=== Summary ====\n\nThe paper proposes a novel graph neural network named DrGNN, which includes two mechanisms to resolve a dimensional collapse problem. First mechanism is a topology-preserving residual connection for graph neural networks to force the low-rank of hidden representations close to the full-rank input features. The second proposed mechanism is structure-guided contrastive learning, which ensure that only close neighbours who share similar local connections can have similar representations.\n\nMain paper contributions are stated to be as following: the proposed combination of topology-preserving residual connections and structure-guided contrastive learning help to overcome the dimensional collapse problem and outperforms state-of-the-art deep graph representation baseline algorithms on the major public datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "=== Questions to address in the revision ===\n\nPlease extend the experiments section. Please add the ArXiv results and the discussion of the lower performance on a different type of the dataset in the main paper.\n\n=== Minor comments and additional feedback ===\n\nP.1. “Empirical experiments on multiple real-world datasets demonstrate that DrGNN outperforms state-of-the-art deep graph representation baseline algorithms.” Might be a strong phrase given that the proposed method does not outperform other methods on some of the datasets that you have explored.\nPlease provide the expanded form of the term when you first mention an abbreviation, e.g. graph convolutional networks (GCN). In contrast, later you introduce Weight-Decaying Graph Residual Connection (WG-ResNet) a few times.\nP2. On Fig.1 you demonstrate a problem in GCN. It would be interesting to see same/similar plot which shows how this problem is solved with the proposed approach for comparison.\nP. 6. It’s unclear why you present the proof of the proposition 2.2. in the body of the paper and move the proof of proposition 2.1. in the appendix. It would make more sense to move both proofs to the appendix. \nP.12. The structure of the paper is somewhat unconventional: the “discussion” section is missing. It wold be nice to see a discussion about the strengths and the weaknesses of the model.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lIa8s5CU38", "reviewer": "Reviewer_4DN8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- A method to tackle an interesting problem of GNNs. \n\n- This paper provides an interesting intuition to demonstrate over-smoothing using the concept of the reduction of the rank of the representation matrix.\n\nWeaknesses:\n\n- The introduction section is not clear. It has references to results and analysis, which are presented in subsequent sections, making claims based on them, which is hard for the reader to follow.\n\n- The claim about closer neighbors being more important for node embeddings generation is false. There exist heterophilic datasets, where the closest neighbors belong to different classes than the central node. I have also read the appendix, but further experimentation with heterophilic datasets is needed (e.g., Texas).\n\n- The proposed work is incremental and based on the combination of two existing methods, leading to concerns about its novelty.\n\n- The weight decay residual connection seems to cancel the proposed depth of each model. The value of $\\lambda$ plays crucial role on that, and, as the authors state, it restricts the number of active layers, hence the actual model's depth.\n\n- The authors analyze the effect of $\\sigma$ and $\\gamma$, but disregard the case of heterophilic graphs, where disconnected nodes might need to be mapped closely.\n\n- The proposed mathematical analysis is based on existing works, and it is not clear to me what is the contribution towards that direction. Can the authors further explain how their mathematical analysis further sheds light on the topic of the contrastive learning?\n\n- The selected hyper-parameters for all models seem to be suboptimal. Setting the hidden dimension to such a small value might lead to false results, in literature the common values of hidden dimension is 64 or 128. This observation is verified by the performance of GCNII, which is much less than the reported performance in [1]. Similar observations apply to other hyperparameters, such as dropout.\n\n- Since authors follow the proposed experimental setup of [2], why they did not perform experiments with p = 100\\% of missing features? Additionally, on that experimental setup, why do they add residual connections to GCNII, which is a model that inherently has residual connections?\n\n- There exist some typos (e.g., farther, in the conclusion section), and notation appears to be overloaded (e.g., the meaning of $\\sigma$ as both a weight and an activation). \n\n[1] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional\nnetworks. In ICML, 2020.\n\n[2] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In ICLR, 2020", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces DrGNN, a method combining weighted residual connections and contrastive learning loss for Graph Convolutional Networks, which aims to reduce oversmoothing. The proposed method aims to maintain the rank of node representations created by the model.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please kindly refer to the Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ileRyA3JFR", "reviewer": "Reviewer_gmqh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The experiments seem fairly thorough, having done experiments with 7 methods in several settings and for many variations of hyperparameters. I like the extra analysis with ablations and the study for the hyperparameter $\\lambda$. \n\nWeaknesses: I found the method section hard to understand and poorly motivated, and many details raised my eyebrows. A clearer motivation for the design would significantly improve the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study oversmoothing in GNNs (embeddings collapsing to one or a few directions as the number of layers increase). They introduce two innovations to prevent this: 1) A residual layer where the signal is weighted by an exponential decay and a similarity that prefers updates that stay close to the original node embedding 2) An extra contrastive loss function enforcing similarity between nodes in a neighbourhood and divergence between nodes outside.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Eq 2: Isn't the standard residual connection one that adds $H^ {(l-1)}$ instead of $H^{(l-2)}$? Your design assumes skipping over two layers, but I don't understand why that's needed. \n- Eq 4: Use a different font for functions (eg $\\text{sim}$). It's unclear that $sim(x, y) = \\exp(\\cos(x, y))$ from the equation. \n- Eq 4: What is the motivation for using an exponential scaling function? Can the GNN not just learn to ignore the scaling anyway by increasing the magnitude of the weights in later layers?\n- \"We introduce a learnable similarity term\": This confused me, I thought this was some neural network that takes two embeddings and compares them, but I think it's just the cosine similarity? \"Learnable\" makes it sound like the similarity is something you learn. \n- I found Section 2.3 very difficult to read. What does 'some nascent of ... obtained alleviation in alleviating' mean?\n- Correct $sigma$ to $\\sigma$. \n- Eq 5: I am not convinced by the motivation for this loss:\n  - $f(a, b)$ is in $[e^ {-1}, e]$, so not a distribution, yet your theoretical result in prop 2.2 using GANs only holds if it is a probability (ie in $[0, 1]$)\n  - The calculation of $\\sigma_{ij}$ is not well explained. What does $1-dist(x, y)/n$ represent? Note that, since $dist$ is the hamming distance, this is almost always around 1 (adjacency vectors are usually sparse, so the hamming distance will be small, and certainly much smaller than $n$ on most graphs). So it's not clear to me what this calculation is contributing.\n  - The derivation is difficult to understand in terms of notation. It also seems flawed. The 'prior probability that sampling is positive' is given by $m/n^ 2$, but this only holds for directed graphs. But the authors study undirected graphs, so it should be $0.5 m/n^ 2$ \n- Section 3.2: \"We added ResNet if it could enhance the models' performance\": What does it mean to add ResNet to a model? It's a vision model. Do you mean residual connections?\n- Section 3.3: point (4) is misleading, I think this only holds within hidden layer categories, but there is not such a drop when compared to $L=2$. \n- Figure 6: How many layers are used in this picture?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has plenty of good work and some ideas that are interesting to the audience, but it has been a bit of a struggle to express it clearly enough with adequate claims. Reviewers find the architecture and experiments at least interesting and well put together, but the theoretical justification and writing is not sufficiently clear. I think at this point the paper should be accepted with the minor revisions, to avoid another time-consuming round of reviews, but please note the revisions are on the far side of minor and I will check them. I kindly ask the authors to apply the below changes:

1. Reviewer 4DN8 points out that indeed it is not universally true that nearby neighbors are most important, and that a class of problems where this is not the case exists. The author's response and lack of revisions around this suggest some misunderstading. It is fine to have a method that is motivated by an assumption that might not always hold, but you should write about this explicitly and avoid suggesting universal claims that don't hold (e.g. "the general intuition that the close neighbors of a node carry the most important information"). Please qualify all such claims in the paper, and if you make claims about which case (homophilic/heterophilic) is more/less frequent please support them with references or data.

2. Reviewer xkjz points out a lack of a clear discussion of limitations. Please include a clear paragraph or section discussing the limitations of this method. This request overlaps with request (1) above, because applicability and scope of the theoretical motivation could be a limitation.

3. Reviewer gmqh has concerns about the theoretical results; some similar concerns were present in the previous version of this paper too about Theorem 2.2. Indeed, as it is written this is still not a rigorous verifiable theorem, as it is not clear what it claims and why the proof proves the claim. If the claim is supposed to be "the node hidden representation vectors are distinguishable based on their connection activities" we would need a clear definition and formalization of what "distinguishable" means, e.g. they are different under some distance metric by at least some threshold. The proof does not bring clarity, and uses ambiguous notation (when is e an edge and when is it the basis of the natural log?) and imprecise language (what does "is towards" mean? What does "successfully discriminate the difference of the hidden representation vectors" mean?)  I think the essence of the claim here seems reasonable (positive and negative classes can be discriminated; assuming separability in the first place), but the exact way this is written is confounding, the assumptions are unclear (can the optimum always be achieved?)  My requests here are the following:

    3.1. Clarify the proof of prop 2.1. The third step is not clear (replacing -min with max is not a valid step: for example -min_x exp(x) is not equal to max_x exp(x) over R.)

    3.2. Either 

        3.2.a) restate 3.2 mathematically with clear assumptions and verifiable claims, adjusting the proof, or

        3.2.b) change it to an informal remark. In this case the reasoning can use more intuition, and you should use more hedging for things that cannot be exactly shown) but the language needs to still be clarified further (ie clarify and expand the intuitive last paragraph in the current "proof").

    3.3. Change the notation to avoid the symbol "e" being ambiguous.
Decision: Accept (poster)