Year: 2021

Abstract:
Graph neural networks (GNNs) integrate the comprehensive relation of graph data and the representation learning capability of neural networks, which is one of the most popular deep learning methods and achieves state-of-the-art performance in many applications, such as natural language processing and computer vision. In real-world scenarios, increasing the depth (i.e., the number of layers) of GNNs is sometimes necessary to capture more latent knowledge of the input data to mitigate the uncertainty caused by missing values. However, involving more complex structures and more parameters will decrease the performance of GNN models. One reason called oversmoothing is recently introduced but the relevant research remains nascent. In general, oversmoothing makes the final representations of nodes indiscriminative, thus deteriorating the node classification and link prediction performance. In this paper, we first survey the current de-oversmoothing methods and propose three major metrics to evaluate a de-oversmoothing method, i.e., constant divergence indicator, easy-to-determine divergence indicator, and model-agnostic strategy. Then, we propose the Topology-guided Graph Contrastive Layer, named TGCL, which is the first de-oversmoothing method maintaining all three mentioned metrics. With the contrastive learning manner, we provide the theoretical analysis of the effectiveness of the proposed TGCL. Last but not least, we design extensive experiments to illustrate the empirical performance of TGCL comparing with state-of-the-art baselines.

heading: 1 INTRODUCTION
text: Combining the graph data comprehensive relations with the neural network models representation learning ability, graph neural networks (GNNs) achieve state-of-the-art performances in many realworld applications, such as document classification, natural language processing, computer vision, and recommender systems (Zhang et al., 2019). GNNs consist of many variant neural network models with different message-passing mechanisms, to name a few, such as GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018), GIN (Xu et al., 2019), and GMNN (Qu et al., 2019).
In the complex real-world settings of applying GNNs, not every node is lucky enough to have node labels and/or node features. Hence, increasing the depth (i.e., the number of layers) of GNNs is a viable solution to capture more latent knowledge to reduce the uncertainty caused by missing values (Zhao & Akoglu, 2020). However, as the number of layers increases, the performance of GNN will decrease to a large degree (Kipf & Welling, 2017). The reasons may come from many aspects after involving more parameters like vanishing gradient, overfitting, and oversmoothing. Compared with the first two reasons, oversmoothing of GNNs is recently introduced (Li et al., 2018; Oono & Suzuki, 2020) and widely discussed (Chen et al., 2020a; Zhao & Akoglu, 2020; Rong et al., 2020; Chen et al., 2020b; Liu et al., 2020; Zhou et al., 2020). It is the phenomenon that the learned node representations become indistinguishable as the number of the hidden layers increases, thus hurting the performance of down-streaming tasks like node classification and link prediction.
To tackle the oversmoothing problem of GNNs, some nascent research works are proposed (Klicpera et al., 2019; Chen et al., 2020a; Zhao & Akoglu, 2020; Rong et al., 2020; Chen et al., 2020b; Liu et al., 2020; Zhou et al., 2020). They share the same logic (i.e., keeping the divergence between nodes) but differ in specific methodologies (i.e., rescaling divergences of learned representa-
tions (Zhao & Akoglu, 2020), adding the divergence regularizer in the learning process (Chen et al., 2020a; Zhou et al., 2020), changing input graph structures (Chen et al., 2020a; Rong et al., 2020; Chen et al., 2020b), or personalizing the information aggregation for each specific node (Klicpera et al., 2019; Liu et al., 2020)). Despite of good performance, some drawbacks still exist in those mentioned solutions. By surveying these SOTA de-oversmoothing strategies, we summarize three major metrics to evaluate a de-oversmoothing strategy: 1) constant divergence indicator, 2) easyto-determine divergence indicator, and 3) model-agnostic de-oversmoothing strategy. (The detailed discussion could be found in Section 2). We find that no prevalent de-oversmoothing methods for GNNs could maintain all of them.
To bridge this gap, we propose a Topology-guided Graph Contrastive Layer (TGCL) with the inspiration from the contrastive learning concept (van den Oord et al., 2018), where we contrast node topological information to obtain discriminative node representations after many GNN layers. TGCL is the first de-oversmoothing strategy attempting to maintain all three mentioned metrics. Specifically, we set a constant and easy-to-determine divergence indicator between nodes, which is purely based on the topology of the input graph. With this divergence indicator, we aim to guide latent representations of neighbor node pairs closer and non-neighbor node pairs farther apart to mitigate the oversmoothing of GNNs. Last but not least, the proposed TGCL is model-agnostic, which means TGCL could be incorporated in multiple GNN models. With theoretical proof and empirical analysis, we show that the proposed TGCL could alleviate the oversmoothing problem of GNNs to a large extent.
Our contributions can be summarized as follows:
• We survey current de-oversmoothing methods by analyzing the advantages and the disadvantages of each method and summarize three metrics to evaluate a de-oversmoothing method for GNNs. • We propose a topology-guided graph contrastive layer named TGCL to tackle the oversmoothing problem of GNNs, which enjoys all three metrics simultaneously. • We show the effectiveness of the proposed TGCL from the theoretical proof and the empirical aspect with extensive experiments.
The rest of this paper is organized as follows. After a brief survey of de-oversmoothing methods in Section 2, we introduce the proposed TGCL in Section 3. The empirical evaluation of the proposed TGCL on real-world datasets is presented in Section 4. Then, we review the related work in Section 5 before we conclude the paper in Section 6.

heading: 2 BACKGROUND
text: As mentioned above, de-oversmoothing methods (Klicpera et al., 2019; Chen et al., 2020a; Zhao & Akoglu, 2020; Rong et al., 2020; Chen et al., 2020b; Liu et al., 2020; Zhou et al., 2020) share the same logic of keeping the divergence between node representations but differ in specific methodologies focusing on different merits. By taking the union of the metrics used in different state-of-thearts, we get three metrics to evaluate a de-oversmoothing algorithm comprehensively.
There are three metrics as shown in Table 1, including constant divergence indicator, easy-todetermine divergence indicator, and model-agnostic de-oversmoothing strategy. Divergence indicator is indispensable for guiding the final node representation similarity based on the specified distance measurement. Several de-oversmoothing methods like (Klicpera et al., 2019; Zhao & Akoglu, 2020; Chen et al., 2020b; Liu et al., 2020) achieve the constant divergence indicator, which means the guidance is much more robust and not dependent on the training process of GNNs. However, to guide the node representation similarity reasonably, the divergence indicator is not that easy to be determined. For example, PairNorm (Zhao & Akoglu, 2020) is proposed as a normalization layer to keep the divergence of node representation against the original node feature. Instead of adding this regularizer directly to the learning objective of GNN models, PairNorm takes an alternative by rescaling the learned node representations with a constant hyperparameter to keep the original node feature divergence. PairNorm achieves two metrics: constant divergence indicator (i.e., the constant hyperparameter) and model-agnostic strategy (i.e., PairNorm can be added on different GNN models as a layer). However, the selection of that constant hyperparameter heavily depends
on the prior knowledge of the input graph data, which is hard to determine. (The discussion of other de-oversmoothing methods can be found in Section 5.)
As shown in Table 1, PairNorm is an effective de-oversmoothing method that maintains two metrics but needs prior knowledge to scale divergence between node pairs. While our proposed TGCL transfers this hard-to-acquire prior knowledge into the topology information of the input graph, where the divergence guidance between nodes is constant and easy to be determined. To be specific, our TGCL is the first de-oversmoothing method attempting to maintain these three metrics at the same time. In the next section, we formally introduce the proposed TGCL with theoretical proof for the model effectiveness. Moreover, we prove that the objective of PairNorm is just a special case of our TGCL, which shows the effectiveness of our TGCL from another perspective.

heading: 3 PROPOSED METHOD
text: In this section, we begin with the notions used in this paper. Then, we prove that the objective of the de-oversmoothing model PairNorm (Zhao & Akoglu, 2020) is a just special case of our Topologyguided Graph Contrastive Layer (TGCL). After analyzing the limitations of PairNorm, we formally introduce our proposed TGCL and show why it could better alleviate the oversmoothing issue with the contrastive learning manner.

heading: 3.1 NOTION
text: Throughout this paper, we use regular letters to denote scalars (e.g., α), boldface lowercase letters to denote vectors (e.g., v), and boldface uppercase letters to denote matrices (e.g., A). We formalize the graph mining problem in the context of undirected graph G = (V ,E,X), where V consists of n vertices, E consists of m edges, X ∈ Rn×d denote the feature matrix and d is the feature dimension. We let A ∈ Rn×n denote the adjacency matrix, D ∈ Rn×n denote the diagonal matrix of vertex degrees, and I ∈ Rn×n denote the identity matrix. For ease explanation, we denote vi as node i, xi as the input feature of node i, zi as the embedding of node i by any type of GNNs and Ai as the adjacency vector for node i. Ni is a set that contains the neighbors of node i and N̄i is the complement of Ni, which contains the non-neighbor of node i.

heading: 3.2 PRELIMINARY
text: Each graph convolutional layer can be understood as a smoothing operation (Li et al., 2018) but stacking many layers renders the final representation of a node indistinguishable from others. Therefore, how to recover the divergence between node representations but preserving the shared information becomes a vital problem in graph mining. In PairNorm (Zhao & Akoglu, 2020), the divergence between node pairs is based on a hyper-parameter, which requires prior knowledge of the input graph data and is hard to acquire. More specifically, PairNorm is proposed as a novel normalization layer to prevent all node embeddings from becoming too similar by minimizing the following objective:
Lp = ∑ vi∈V ‖zi − xi‖2 + ∑ (i,j)∈E ‖zi − zj‖2 − ∑ (i,k) 6∈E ‖zi − zk‖2 (1)
where zi is the node embedding vector of node vi and xi is the original feature vector of node vi. In the equation above, the first term is the reconstruction error, the second term is responsible for min-
imizing the difference between two representations of a neighbor node pair, and the last term aims to maximize the difference between two representations of a remote node pair. By reformulating Eq. 1, we could derive a upper bound of Lp in the form of contrastive learning loss term as follows:
Lp = ∑ vi∈V ‖zi − xi‖2 + ∑ vi∈V ∑ vj∈Ni ‖zi − zj‖2 − ∑ vi∼V ∑ vk /∈Ni ‖zi − zk‖2
= ∑ vi∼V ‖zi − xi‖2 − ∑ vi∼V ∑ vj∈Ni log(e−‖zi−zj‖ 2 ) + ∑ vi∼V ∑ vk /∈Ni log(e−‖zi−zk‖ 2 ) (2)
≤ ∑ vi∼V ‖zi − xi‖2 − ∑ vi∼V ∑ vj∈Ni log(e−‖zi−zj‖ 2 ) + ∑ vi∼V log( ∑ vk /∈Ni e−‖zi−zk‖ 2 ) (3)
≤ ∑ vi∼V ‖zi − xi‖2 − ∑ vi∼V ∑ vj∈Ni log(e−‖zi−zj‖ 2 ) + ∑ vi∼V ∑ vj∈Ni log( ∑ vk /∈Ni e−‖zi−zk‖ 2 )
= ∑ vi∼V ‖zi − xi‖2 + ∑ vi∼V ∑ vj∈Ni log( ∑ vk /∈Ni e −‖zi−zk‖2 e−‖zi−zj‖ 2 )
≤ ∑ vi∼V ‖zi − xi‖2 + ∑ vi∼V ∑ vj∈Ni [log(1 + ∑ vk /∈Ni e −‖zi−zk‖2 e−‖zi−zj‖ 2 )]
= ∑ vi∼V ‖zi − xi‖2 − ∑ vi∼V ∑ vj∈Ni [log( e−‖zi−zj‖ 2 e−‖zi−zj‖ 2 + ∑ vk /∈Ni e −‖zi−zk‖2 )]
= ∑ vi∼V ‖zi − xi‖2 − ∑ vi∼V ∑ vj∈Ni [log( f(zi, zj) f(zi, zj) + ∑ vk /∈Ni f(zi, zk) )] = L1 (4)
where f(zi, zk) = e−‖zi−zk‖ 2
. Here, we apply Jensen’s inequality to derive Eq. 3 as a upper bound of Eq.2 since log(·) is concave. We observe that L1 is a upper bound of PairNorm and we could interpret two regularization terms ‖zi − zj‖2 and ‖zi − zk‖2 of PairNorm as a special case of a contrastive learning loss term in L1 by setting the similarity measurement function f(zi, zk) to be e−‖zi−zk‖ 2 .
However, both PairNorm (Eq. 1) and the upper bound of PairNorm (Eq. 4) only consider the firstorder neighbor information but neglect the K-hop neighbors information. For example, in a realworld scenario, we are given a remote pair (vk, vi). It is highly possible that vk and vi have the similar representations, if they share the same label information. However, simply minimizing the third term of PairNorm (i.e., −‖zi − zk‖2) will push zi away from zk, resulting in sub-optimal solution. In addition, if we are given two remote pairs (vk1 , vi) and (vk2 , vi) such that node vk1 is far from node vi and node vk2 is near node vi (e.g., 2-hop neighbor), the weight imposed on these two remote pairs should be different as we expect that zk1 should be more different from zi than zk2 due to the topological information in the graph. However, PairNorm and L1 (Eq. 4) assume that all unconnected node pairs (zi and zk) have the same weight by setting the weights to be 1 for neighbor pairs and remote pairs. Therefore, if the K-hop neighbors of zi share the same topological structure of zi or the same label information, pushing zi away from the representation of its K-hop neighbors (K > 1) and ignoring the different weights for different remote pairs will result in a sub-optimal solution. Motivated by these, we propose to utilize the similarity of two adjacency vectors of each node pair and embed the global topological structure information into the representation of each node such that GNNs can derive better discriminative representations for all nodes.

heading: 3.3 OVERVIEW OF TGCL
text: The structure of TGCL is shown in Figure 1. TGCL is model-agnostic, and it can be added before the final output layer of any GNN model. To recover the divergence between node representations, we first need to determine the divergence between different node pairs. In TGCL, we transfer this hard-to-acquire knowledge into the topology information of the input graph, which is a constant divergence indicator (i.e., not varying with the depth of GNNs), easy to obtain, and purely depends on the adjacency vector of each node. The main idea of TGCL is to encode the topological divergence
relationship of any pair of nodes into their final node representations. Specifically, we expect that the representations of two nodes are similar if their adjacency vectors are close enough. Otherwise, their representations should be discriminative. Thus, we propose the topology-guided contrastive loss formulated as follows:
LTGCL = −Evi∼V Evj∈Ni [log σijf(zi, zj) σijf(zi, zj) + ∑ vk∈N̄i γikf(zi, zk) ]
σij = 1− dist(Ai,Aj)/n, γik = 1 + dist(Ai,Ak)/n (5)
where f(·) is a similarity function, e.g., f(a, b) = exp(a T b τ ), τ is the temperature, dist(·) is a distance measurement function, e.g., hamming distance, and the set N̄i contains the non-neighbor nodes of the node i. The intuition of Eq. 5 is that if vi and vj are neighbors, then the similarity of their representations should be as large as possible, while if vi and vk are two remote nodes (not connected in the graph), the similarity of their representations should be as small as possible, and the magnitude of dissimilarity is determined by how many neighbors these two nodes don’t share. By adjusting the weights of both remote pairs and neighbor pairs based on the topological information, we aim to reduce the negative impact of remote nodes that have similar topological information.
To collaborate with different GNN models, the adaptive loss function Ltotal is expressed as follows.
Ltotal = Lagnostic + αLTGCL (6)
where Lagnostic denotes the loss function of an arbitrary GNN model such as GCN (Kipf & Welling, 2017), and α is a constant hyperpararmeter and LTGCL stands for the loss function of our TGCL, which can serve as a regularizer to alleviate the over-smoothing problem.

heading: 3.4 THEORETICAL ANALYSIS OF TOPOLOGY-GUIDED CONTRASTIVE LOSS
text: In this subsection, we provide an analysis regarding the properties of the proposed contrastive loss.
Lemma 1 Given a neighbor node pair sampled from the graph G = (V ,E,X), i.e., nodes vi and vj , we have I(zi, zj) ≥ −LTGCL +Evi∼V log(|N̄i|), where I(zi, zj) is the mutual information between two representations of the node pair vi and vj , and LTGCL is the topology-guided contrastive loss weighted by hamming distance measurement.
Proof: Following the theoretical analysis in (van den Oord et al., 2018), the optimal value of f(zi, zj) is given by
P (zj |zi) P (zj)
. Thus, the weighted supervised contrastive loss could be rewritten as follows:
LTGCL = −Evi∼V Evj∈Ni [log σijf(zi, zj) σijf(zi, zj) + ∑ vk∈N̄i γikf(zi, zk) ]
= Evi∼V Evj∈Ni [log σij
P (zj |zi) P (zj)
+ ∑
vk∈N̄i γik P (zk|zi) P (zk)
σij P (zj |zi) P (zj)
]
= Evi∼V Evj∈Ni [log(1 + P (zj) σijP (zj |zi) ∑
vk∈N̄i
γik P (zk|zi) P (zk) )]
Since (vi,vk) is defined as a remote node pair, it means that node vi and node vk are not connected in the graph, i.e., A(i, k) = A(k, i) = 0. Therefore, we have γik ∈ (1, 2] for all remote nodes vk and σij ∈ (0, 1] for all neighbor nodes vj with hamming distance measurement, which leads to
1 σij · P (zj)P (zj |zi) ≥ P (zj) P (zj |zi) and γik P (zk|zi) P (zk) ≥ P (zk|zi)P (zk) . Thus, we have
LTGCL ≥ Evi∼V Evj∈Ni [log( P (zj) P (zj |zi) ∑
vk∈N̄i
P (zk|zi) P (zk) )]
≈ Evi∼V Evj∈Ni [log( P (zj)
P (zj |zi) (|N̄i|Evk P (zk|zi) P (zk) ))]
= Evi∼V Evj∈Ni [log( P (zj)
P (zj |zi) |N̄i|)]
≥ Evi∼V Evj∈Ni [log( P (zj)
P (zj |zi) ) + log(|N̄i|)]
= −I(zi, zj) + Evi∼V log(|N̄i|)
Finally, we have I(zi, zj) ≥ −LTGCL + Evi∼V log(|N̄i|), which completes the proof.
Lemma 1 shows that the topology-guided contrastive loss for the graph is the lower bound of the mutual information between two representations of a neighbor node pair. Notice that Evi∼V log(|N̄i|) is the average logarithm of the number of unconnected edges for the nodes in the graph, which means that TGCL tends to be a better lower bound if imposed on a sparser graph.

heading: 4 EXPERIMENT
text: In this section, we demonstrate the performance of our proposed framework in terms of effectiveness by comparing it with state-of-the-art methods. In addition, we conduct a case study to show how the increase of the number of layers influences the performance of the proposed method.

heading: 4.1 EXPERIMENT SETUP
text: Datasets: Cora dataset is a citation network consisting of 2,708 scientific publications in seven classes and 5,429 edges. The edge in the graph represents the citation of one paper to another. CiteSeer dataset consists of 3,327 scientific publications which could be categorized into six classes and this citation network has 9,228 edges. PubMed is a diabetes dataset, which consists of 19,717 scientific publications in three classes and 88,651 edges. Reddit dataset is extracted from Reddit posts in September 2014, which consists of 4,584 nodes and 19,460 edges. In all experiments, 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 rest 87% of the nodes as the test samples.
Baselines: We compared the performance of our method with the following baselines: (1) GCN (Kipf & Welling, 2017): vanilla graph convolutional network; (2) GCNII (Chen et al., 2020b): an extension of vanilla GCN with skip connections and additional identity matrices; (3) DGN (Zhou et al., 2020): the differentiable group normalization to normalize nodes within the same group and separate nodes among different groups; (4) PairNorm (Zhao & Akoglu, 2020): a novel normalization layer designed to prevent all node embeddings from becoming too similar; (5) DropEdge (Rong et al., 2020): a novel framework that randomly removes a certain number of edges from the input graph at each training epoch to reduce the speed of over-fitting and to prevent the oversmoothing issue. The reason why we do not include the de-oversmoothing strategies APPNP (Klicpera et al., 2019) and DAGNN (Liu et al., 2020) here is that they replace stacking layers with stacking hops propagation.
Configuration: In all experiments, we set the learning rate to be 0.0005 and the optimizer is Adam (Kingma & Ba, 2014). The feature dimension of the hidden layer is 50. The experiments are repeated 5 times if not specified. dist(·) is the hamming distance and f(·) is the cosine similarity measurement. All of the real-world datasets are publicly available. The code of our algorithms could
be found in an anonymous link *. The experiments are performed on a Windows machine with a 16GB RTX 5000 GPU.

heading: 4.2 EXPERIMENTAL ANALYSIS
text: In this subsection, we evaluate the effectiveness of the proposed method on four benchmark datasets by comparing it with state-of-the-art methods. The base model for all methods we used in this experiment is graph convolutional neural network (GCN). For a fair comparison, we set the numbers of the hidden layers to be 10 for all methods and the dimension of the hidden layer to be 50. The experiments are repeated 5 times and we record the mean accuracy as well as the standard deviation in Table 2. By observation, we could find that our proposed method outperforms most baselines over these four datasets without adding ResNet. Though GCNII achieves the best performance in the CiteSeer dataset, it has worse performance in other datasets. When we further incorporate ResNet into the base model (GCN), PairNorm, and our proposed method, we observe the performance improvement for all methods. In addition, the gap of performance between GCN+ResNet and TGCL+ResNet becomes narrow. Our guess is that as we increase the number of layers, the vanishing gradient problem and the oversmoothing issue coexist in GCN based model. Adding ResNet into the base model somehow alleviates the issue of vanishing gradient, thus leading to great performance improvement for GNNs.
To further investigate the impact of oversmoothing issue, we conduct an experiment on the Cora dataset by increasing the number of layers. The x-axis of Figure 2 (a) is the number of layers and the y-axis is the accuracy on the test dataset. By observation, we find that without adding ResNet, the performance of GCN drops dramatically starting at 10 hidden layers. By comparing the performance of GCN and TGCL, we observe that after utilizing our proposed de-oversmoothing strategy, TGCL boosts the performance by more than 7.5% at 60 hidden layers. After adding ResNet, the performance of GCN+ResNet improves a lot due to the alleviation of the vanishing gradient problem, but we could still see more than 4% improvement at 60 hidden layers by our proposed method (TGCL+ResNet). Combining the experimental results in Table 2 and Figure 2 (a), we find that the oversmoothing issue slightly influences the performance of shallow GCN (when the number of layers is less than 10). However, GCN will suffer a lot from the oversmoothing issue, if we increase the number of layers to 20 or more (based on the results in Figure 2 (a)). To demonstrate the oversmoothing issue in other types of GNNs, we show the performance of our proposed with different base models (e.g., GAT (Velickovic et al., 2018) and SGC (Wu et al., 2019)) in Figure 2 (b). The experimental setting is the same as the setting in Table 2. Figure 2 (b) shows that our proposed method outperforms GAT and SGC and thus alleviates the oversmoothing issue.

heading: 4.3 CASE STUDY: A MISSING FEATURE SCENARIO
text: Why do we need a de-oversmoothing strategy, if increasing the number of the layers may result in a worse performance? To answer this question, let’s first imagine a scenario where some values of attributes are missing in the graph. In this scenario, the shallow GNNs may not work well because
*https://drive.google.com/file/d/1t9_-5Hb35K7Vx7nD9is9-JmYJRn9Vz_M/ view?usp=sharing
GNNs could not collect useful information from the neighbors due to the massive missing values. However, if we increase the number of layers, GNNs are able to gather more information from the K-hop neighbors and capture latent knowledge. To verify this, we conduct the following experiment: we randomly mask p% attributes in four datasets, gradually increase the number of layers, and report the performance. In this case study, the number of layers is selected from [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 25, 30, 40, 50, 60] and the base model is GCN. For a fair comparison, we add ResNet (He et al., 2016) to avoid the vanishing gradient issue. We repeat the experiments three times and record the mean accuracy and standard deviation.
Table 3 shows the performance of TGCL as well as the number of layers where the model achieves the best performance (denoted as #L). By observation, we can see that when the missing rate is 25%, 3 layers or 4 layers GCN has enough capability to achieve the best performance in all four datasets and our proposed method only slightly improves the performance. However, when we increase the missing rate to 50% and 75%, we observe that both GCN and TGCL achieve the best performance by stacking more layers and our proposed method improves the performance of GCN by 6.8% in the PubMed dataset when 75% attributes are missing. The experimental results verify that the more values a dataset is missing, the more layers GNNs need to stack to achieve better performance. Our guess for this observation is that if the number of layers increases, more information will be collected from the K-hop neighbors to recover the missing information of its 1-hop and 2-hop neighbors.

heading: 4.4 EFFICIENCY ANALYSIS
text: In this subsection, we conduct an efficiency analysis regarding our proposed method on Cora dataset. We fix the feature dimension of the hidden layer to be 50 and we choose GCN as the base model. We gradually increase the number of layers and record the running time. In Figure 2 (c), the x-axis is the number of layers and the y-axis is the running time in second. We could see that the running time of our proposed method is linearly proportional to the number of layers.

heading: 5 RELATED WORK
text: In this section, we briefly review the related work on the oversmoothing of GNNs and contrastive learning methods.

heading: 5.1 OVERSMOOTHING OF GNNS
text: Oversmoothing problem of GNNs is formally proposed by (Li et al., 2018) by demonstrating that node representations become indiscriminative after stacking many layers in GNN models. This problem is also analyzed by (Oono & Suzuki, 2020) showing how oversmoothing hurts the node classification performance. To quantify the degree of oversmoothing, different measurements are proposed (Chen et al., 2020a; Zhao & Akoglu, 2020; Liu et al., 2020; Zhou et al., 2020). For example, Mean Average Distance (Chen et al., 2020a) is proposed by calculating the divergences between learned node representations. To tackle the oversmoothing problem of GNNs, some nascent research works are proposed (Klicpera et al., 2019; Chen et al., 2020a; Zhao & Akoglu, 2020; Rong et al., 2020; Chen et al., 2020b; Liu et al., 2020; Zhou et al., 2020). They share the same logic of keeping the divergence between node representations but differ in specific methodologies like adding the divergence regularizer in the learning process and changing input graph structures. Taking the union set of these methods’ merits, we propose three metrics as shown in Table 1 to comprehensively evaluate a de-oversmoothing method. For example, APPNP (Klicpera et al., 2019) personalizes the information propagation for each specific node to tackle the oversmoothing problem. To be specific, APPNP uses the stationary distribution of random walks to propagate information, which is constant and not changing with the depth of GNN models. However, the number of power iterations to get the approximated stationary distribution is hard to determine and its effect on alleviating the oversmoothing is not clear. Also, in MADReg (Chen et al., 2020a), the divergence regularizer is built on the learned node representation, which is varying with the depth of GNN models, and may not be as robust as the constant divergence indicator. To the best of our knowledge, the proposed TGCL is the first de-oversmoothing method attempting to maintain three metrics at the same time.

heading: 5.2 CONTRASTIVE LEARNING
text: Recently, contrastive learning attracts researchers’ great attention due to its prominent performance for unsupervised data. (van den Oord et al., 2018) is one of the earliest works, which proposes a Contrastive Predictive Coding framework to extract useful information from high dimensional data with a theoretical guarantee. Based on this work, recent studies (Song & Ermon, 2020; Chuang et al., 2020; Khosla et al., 2020; Tian et al., 2020; Chen et al., 2020c) reveal a surge of research interest in contrastive learning. (You et al., 2020) propose a graph contrastive learning (GraphCL) framework utilize different types of augmentations method to incorporate various priors and to learn unsupervised representations of graph data. (Qiu et al., 2020) propose a Graph Contrastive pretraining model named GCC to capture the graph topological properties across multiple networks by utilizing contrastive learning to learn the intrinsic and transferable structural representations. (Hassani & Ahmadi, 2020) aims to learn node and graph level representations by contrasting structural views of graphs. In this paper, we leverage the topological structure information to contrast the node representations to maximize the similarity of two connected nodes and to minimize the similarity of two remote nodes.

heading: 6 CONCLUSION
text: In this paper, we first survey the current de-oversmoothing methods and take the union of their own merits to propose three metrics to evaluate a de-oversmoothing method, i.e., constant divergence indicator, easy-to-determine divergence indicator, alleviating-oversmoothing strategy, and modelagnostic strategy. Then, we propose the Topology-guided Graph Contrastive Layer, named TGCL, which is the first de-oversmoothing method maintaining the three mentioned metrics. With the contrastive learning manner, we provide the theoretical proof of our proposed TGCL and demonstrate the effectiveness of the proposed method by extensive experiments comparing with state-of-the-art de-oversmoothing algorithms.

Review summaries:
In this work, the author analyzed the oversmoothing issue in GNN learning. To compare with the related works, the author proposed three metrics: divergence indicator, the intuition to set its value, and the ease to adopt. The author proposed a new method Topology-guided Graph Conttrasive Layer which achieved de-oversmoothing and maintaining the proposed metrics. Lower bound analysis of the TGCL loss was analyzed and the empirical experiment showed an advantage on four graph datasets.

This paper proposes a method named TGCL which aims to deal with the over smoothing problem in GNN when a number of layers go deeper. Different from existing works, the proposed TGCL considers three different concepts which are Constant Divergence Indicator, Easy-to-Determine Divergence Indicator, and Model-Agnostic Strategy. Most of the existing works are only considered two of them. The proposed method can be recognized as an improvement of the PairNorm. 

The paper proposes a new layer TGCL for GNNs which is used to tackle the oversmoothing problem. This model satisfies three properties: constant divergence indicator, easy-to-determine divergence indicator, and model-agnostic strategy. They show their model alleviates the oversmoothing problem through experiments on 4 datasets.