Provable Training for Graph Contrastive Learning
Authors: Yue Yu
Xiao Wang
Mengmei Zhang
Nian Liu
Chuan Shi
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Graph Contrastive Learning
Graph Neural Networks
Bound Propagation
TL;DR: We investigate the intrinsic property of nodes in GCL and improve the training of GCL provably upon that property.

Abstract: Graph Contrastive Learning (GCL) has emerged as a popular training approach for learning node embeddings from augmented graphs without labels. Despite the key principle that maximizing the similarity between positive node pairs while minimizing it between negative node pairs is well established, some fundamental problems are still unclear. Considering the complex graph structure, are some nodes consistently well-trained and following this principle even with different graph augmentations? Or are there some nodes more likely to be untrained across graph augmentations and violate the principle? How to distinguish these nodes and further guide the training of GCL? To answer these questions, we first present experimental evidence showing that the training of GCL is indeed imbalanced across all nodes. To address this problem, we propose the metric "node compactness", which is the lower bound of how a node follows the GCL principle related to the range of augmentations. We further derive the form of node compactness theoretically through bound propagation, which can be integrated into binary cross-entropy as a regularization. To this end, we propose the PrOvable Training (POT) for GCL, which regularizes the training of GCL to encode node embeddings that follows the GCL principle better. Through extensive experiments on various benchmarks, POT consistently improves the existing GCL approaches, serving as a friendly plugin.

Provable Training for Graph Contrastive Learning
Yue Yu', Xiao Wang"*, Mengmei Zhang', Nian Liu', Chuan Shi
Beijing University of Posts and Telecommunications, China Beihang University, China
yuyue1218@bupt. edu. en, xiao_ aala__wag@buaa edu. en, {zhangmm, nianliu, shi shichuan/@bupt. edu cn
Abstract
Graph Contrastive Learning (GCL) has emerged as a popular training approach for learning node embeddings from augmented graphs without labels. Despite the key principle that maximizing the similarity between positive node pairs while minimizing it between negative node pairs is well established, some fundamental problems are still unclear. Considering the complex graph structure, are some nodes consistently well-trained and following this principle even with different graph augmentations? Or are there some nodes more likely to be untrained across graph augmentations and violate the principle? How to distinguish these nodes and further guide the training of GCL? To answer these questions, we first present experimental evidence showing that the training of GCL is indeed imbalanced across all nodes, To address this problem, we propose the metric "node compactness", which the lower bound of how a node follows the GCL principle related to the range of augmentations. We further derive the form of node compactness theoretically through bound propagation, which can be integrated into binary cross-entropy
regularization. To this end, we propose the PrOvable Training (POTT) for GCL, which regularizes the training of GCL encode node embeddings that follows the GCL principle better. Through extensive experiments on various benchmarks, POT consistently improves the existing GCL approaches, serving as friendly plugin.
1 Introduction
Graph Neural Networks (GNNs) are successful in many graph-related applications, e.g., node classification [10 20 and link prediction [33] 27). Traditional GNNs follow a semi-supervised
learning paradigm requiring task-specific high-quality labels, which are expensive obtain [9]. To alleviate the dependence on labels, graph contrastive learning (GCL) is proposed and has received considerable attention recently B5 31
21 29]. As typical graph self- celf-supervised learning technique, GCL shows promising results on many downstream tasks
23
30
The learning process of GCL usually consists of the following steps: generate two graph augmen- tations 355; feed these augmented graphs into graph encoder to learn the node embeddings, and then optimize the whole training process based on the InfoNCE principle [15 35 36), where the positive and negative node pairs are selected from the two augmentations. With this principle ("GCL. principle" for short), GCL learns the node embeddings where the similarities between the positive node pairs are maximized while the similarities between the negative node pairs are minimized.
However, it well known that the real-world graph structure is complex and different nodes may have different properties [ 36. When generating augmentations and training on the complex graph
"Corresponding authors.
'Code available at http:///ghhbbccmmollllaaiiooooo
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

structure in GCL, it may be hard for all nodes to follow the GCL principle well enough. This naturally gives rise to the following questions: are some of the nodes always well-trained and following the principle of GCL. given differeni graph augmentations? Or are there some nodes more likely not to be well trained and violate the principle? If so, implies that each node should not be treated equally in the training process. Specifically, GCL. should pay less attention to those well-trained nodes that already satisty the InfoNCE principle. Instead, GCL should focus more on those nodes that are sensitive to the graph augmentations and hard to be well trained. The answer to these questions can not only deepen our understanding of the learning mechanism but also improve the current GCL. We start with an experimental analysis (Section B) and find that the training of GCL is severely imbalanced, iee the averaged InfoNCE loss values across the nodes have a fairly high variance, especially for the not well-trained nodes, indicating that not all the nodes follow the GCL principle well enough.
Once the weakness of GCL is identified, another two questions naturally arise: how to distinguish these nodes given so many possible graph augmentations? How to utilize these findings to further improve the existing GCL? Usually, given specific graph augmentation, it is easy to check how different nodes are trained to be. However, the result may change with respect to different graph augmentations, since the graph augmentations are proposed from different views and the graph structure can be changed in a very diverse manner. Therefore, it is technically challenging to discover the sensitivity of nodes to all these possible augmentations.
In this paper, we theoretically analyze the property of different nodes in GCL. We propose a novel concept "node compactness", measuring how worse different nodes follow the GCL principle in all possible graph augmentations. We use bound propagation process [ 32 to theoretically derive the node compactness, which depends on node embeddings and network parameters during training. We finally propose a novel PrOvable Training model for GCL (POT) to improve the training of GCL, which utilizes node compactness as a regularization term. The proposed POT encourages the nodes to follow the GCL principle better. Moreover, because our provable training model is not specifically designed for some graph augmentation, it can be used friendly plug-in to improve current different GCL methods. To conclude, our contributions are summarized as follows:
We theoretically analyze the properties of different nodes in GCL given different graph augmentations, and discover that the training of GCL methods is severely imbalanced, i.e., not all the nodes follow the principle of GCL well enough and many nodes are always not well trained in GCL.
We propose the concept of "node compactness" that measures how each node follows the GCL principle. We derive the node compactness as regularization using the bound propagation method and propose PrOvable Training for GCL (POT), which improves the training process of GCL provably.
POT is a general plug-in and can be easily combined with existing GCL methods. We evaluate our POT method various benchmarks, well showing that POT consistently improves the current GCL baselines.
2 Preliminaries
Let G (V,E) denote a graph, where V is the set of nodes and È C V x V is the set of edges, respectively. X E RN XxF and A = {0, N are the feature matrix and the adjacency matrix. D = diag(d, (d1, d2................. ...., dN} } is the degree matrix, where each element d, | = Σjev di denotes the degree of node i, A; is the i-th row of A. Additionally, A Asym = D (A + 11/2 is the degree normalized adjacency matrix with self-loop (also called the message-passing matrix).
GCN [O0 is one of the most common encoders for graph data. A graph convolution layer can (Asgm.((k ((#-)) where (k) and (ik) are the embedding and the weight matrix of the k-th layer respectively, ())) X, and a represents the non-linear activation
be described as (A)
function. A GCN encoder so with K layers takes graph (X, A) as input and returns the embedding
Z = A))
Graph Contrastive learning (GCL). GCL learns the embeddings of the nodes in a self-supervised manner. We consider a popular setting as follows. First, two graph augmentations G. (X, A and G2 (X, Ag) are sampled from G. which is the set of all possible augmentations. In this paper,

---

we focus on the augmentations to graph topology (e.g. edge dropping [35 Then the embeddings
2 f,, A1) and Z2 fo(X, A2) are learned with two-layer GCN 35 36 InfoNCE [5 35 the training objective as follows:
(2..// [Z21,1 22,1) (0 Ejts (2)
(I)
Eigs (1,.
where ((a, b) = s(g(a). g(b)), $ is a similarity measure, 9 is a projector, and T is the tempera- ture hyperparameter. For node the positive pair is (Zi,i 22,i), where 21,; and Z2 denote the embedding of node in the two augmentations, {(z1,;: Z2,5) 1 + i} and {(z Z1,1) + i} the negative pairs. The overall loss function of the two augmentations is LIMEONCE Z1, Z2) E (I(z),) 22,1) 1(22,1 31,)))
EN
The Imbalanced Training of GCL: an Experimental Study
As mentioned in Section 1 due to
the complex graph structure, we aim to investigate whether all the nodes are trained to follow the principle of GCL. Specifically, we design an experiment by plotting the distribu- tion of InfoNCE loss values of the nodes. To illustrate the result of GCL method, we sample 500 pairs of augmented graphs with the same aug- mentation strategy the GCL method and obtain the average values of In-
2500
2500
HUnCE
(a) GRACE
(b) GCA
(c) ProGCL
Figure 1: The imbalance of GCL training
foNCE loss. We show the results GRACE (35, GCA [36, and ProGCL 25 on WikiCS [4] in Figure[ histograms. The vertical red lines represent 1/4-quantile, median, and 3/4-quantile from left to right. The results imply that the nodes do not follow the GCL principle well enough in two aspects: 1) the InfoNCE loss of the nodes has high variance; 2) is shown that the untrained nodes (with higher InfoNCE loss values) are much further away from the median than the well-trained nodes (with lower InfoNCE loss values), indicating an imbalanced training the untrained nodes. GCL methods should focus more on those untrained nodes. Therefore, it is highly desired that we should closely examine the property of different nodes so that the nodes can be trained as we expected in provable way. Results on more datasets can be found in Appendix D
4 Methodology
4.1 Evaluating How the Nodes Follow the GCL Principle
In this section, we aim to define a metric that measures the extent of node following the GCL princi- ple. Since how the nodes follow the GCL principle relies the complex graph structure generated by augmentation, the metric should be related to the set of all possible augmentations. Because InfoNCE loss only measure the training of node under two pre-determined augmentations, which does not meet the requirement, we propose a new metric as follows:
Definition 1 (Node Compactness). Let denote the encoder of Graph Contrastive Learning. The compactness of node is defined as
L. min ( N-1 G:=(X.A,) (2=(X
E(2 (21,5-70 21,5 22.5) Z So So(X, A2)). (2)
J+1
where z z/ |zl|| |g is the normalized vector.
Definition measures how worse node i follows the GCL principle in all possible augmentations. f, is greater than zero, on average, the node embedding 21,5 is closer to the embedding of the positive sample 22,; than the embedding of the negative sample Z2,; in the worst case of augmentation; otherwise, the embeddings of negative samples are closer. Note that normalization is used to eliminate
3

---

the effect of a vector's ss scale. In Definition 1 the anchor node is node in G1, so similarly we can define L if the anchor node is node i in G2.
We can just take of G1 and G2 the variable, for example, set G2 to be specific sampled augmentation and G1 to be an augmentation within the set g. From this perspective, based on Definition L can also obtain a metric, which has only one variable:
Definition (Go-Node Compactness). Under Definition) 7 if G2 the augmentation sampled in an epoch of GCL training, then the G2-Node Compaciness i8
La
min G1 G)=fo(X,Ai)EG
(Zi
W.L Zi fo((,
1 where W = Z2, N-1 Ejzt 22.j is constant vector.
Usually we have La.," Lz. and La., 2 Lis" i... G1 -nddd compactness and G--node compactness are upper bounds of node compactness.
Similarly, we can define -nonde compactness Lor
4.2 Provable Training of GCL
To enforce the nodes to better follow the GCL principle, we optimize G1-node compactness and Go-node compactness in Definition[] Designing the objective can be viewed as implicitly performing a "binary classification": the "prediction" is ming, 21,; W and the "label" is 1, which means that expect the embedding of the anchor more likely to be classified a positive sample in the worst case. To conclude, we propose the PrOvable Training (POT) for GCL, which provably enforces the nodes to be trained more aligned with the GCL principle. Specifically, we use binary cross-entropy as regularization term:
G Gz) (CBCE(fo, 1n) + LoCE(fa,) In));
where CECE (I, 3) E log (I;) ) + (1- y1) log(1 (x:))), a is the sigmoid activation, In [1,1...., E R and LG. = (L... Lo. Le,, the vector of the lower bounds in Eq. Overall, we add this term to the original InfoNCE objective and the loss function is
C= (1 (1- LI (1, 22) + (C G2).
(5)
where is the hyperparameter balancing the InfoNCE loss and the compactness loss. Since G1- node compactness and Gz-node compactness are related to the network parameter 0, Lvor can be naturally integrated into the loss function, which can regularize the network parameters to encode node embeddings more likely to follow the GCL principle better.
4.3 Deriving the Lower Bounds
In Section 4.2 we have proposed the formation of our loss function, but the lower bounds fa, and Lo are still to solved. In fact, to see Eq. from another perspective, Le,, (or Lo.. is the lower bound of the output of the neural network concatenating GCN encoder and linear projection with parameter W (or W ). It is difficult to find the particular G1 which minimizes Eq. 3 since finding that exact solution G1 can be NP-hard problem considering the discreteness of graph augmentations. Therefore, inspired by the bound propagation methods [5] 32] 38), we derive the output lower bounds of that concatenated network in bound propagation manner, i.e.,
derive the lower bounds fa, and fa, by propagating the bounds of the augmented adjacency matrix A1-
However, there still two challenges when applying bound propagation Eq.3ii not defined as continuous values with element-wise bounds; 2) to do the propagation process, the nonlinearities in the GCN encoder fo should be relaxed.
problem: 1) A₃ in
Defining the adjacency matrix with continuous values First, we define the set of augmented adjaceney matrices as follows:

---

Definition 3 (Augmented adjacency matrix). The set of augmented adjacency matrices is A A= (0, 1 I aij A = A
A A Allo S 2Q A A. Aol, S sq SasissNs
where A denotes the augmented adjacency matrix, Q and qu the global and local budgets of edge dropped, which are determined by the specific GCL model.
The first constraint restricts the augmentation to only edge dropping, which is a common setting in existing GCL models(35) 36 8 25 (see discussions in Appendix B). The second constraint is the symmetric constraint of topology augmentations.
Since the message-passing matrix is used in GNN instead of the original adjacency matrix, we further relax Definition 3 and define the set of all possible message- message-passing matrices, which are matrices with continuous entries expected, inspired by [3]]
Definition (Augmented message-passinn pasaagg matrix). The set of augmented message-pussing matrices
is
À = {A E [0 NxN = A AVi, Lis S 0ij S Uish:
dij _i=j {
((d, - (d; 9;)) minfar,, ((d: - (d; ,;)) -))) ,i
i
Tig
Un
jijj"
where Å denotes the augmented message-passing matrix.
Under Definition the augmented message-passing matrices are non-discrete matrices with element- wise bounds Lij and Uzy- Lij is āsg when i = j. since there is no edge added and the self-loop can not be dropped; Lij is 0 when i J. which implies the potential dropping of each edge. Usy is set to ((d, (dg 4))) when = because âæ is the largest when its adjacent edges are dropped as much as possible, and U.j = min(arj. ((d: - (:) +4)) when +f j since there is only edge dropping, Uij cannot exceed duj-
Relaxing the nonlinearities in the GCN encoder The GCN encoder in our problem has non-linear activation functions as the nonlinearities in the network, which is not suitable for bound propagation. Therefore, we relax the activations with linear bounds [32
Definition 5 (Linear bounds of non-linesd activation function), For node i and the m-th neuron in (k)
the k-th layer, the input of the neuron is Pi,mo and a is the activation function of the neuron. With the lower bound and upper bound of the input denoted as PL.,m and Pu..m. the output of the neuron is Uuam E ER, i.e.
(k)
bounded by linear functions with parameters 1,i,m Uiim Liim
(k) (R) 3(R)
(k) L.s. (pi + (/h) S (v( S auAm
(k)
( P...m).
(K) 2(k)
2/5) The values of L.5. U.am B(k) 2.smo P.a.m depend on the activation a and the pre-activation bounds (k)
(k)
(k)
PL.mm and (k)
Pu.im
To further obtain and B, compute the pre-activation bounds /// and P follows, which is (k)
the matrix with elements PL,i.m and Pú.i..
Theorem I (Pre-activation bounds of each layer 161
the two-layer GCN encoder, given the element-wist bounds of A in Definition H (k) the imput embedding of t-th layer, then the pre-activation bounds of t-th layer are
((A)
(k) L = L L
wy (k) + U[H (()) + (k).
( kk) UH w [+) + L w(b) (A)
where []+ max X, 0) and [ min
5

---

Therefore, PL and Pus. are known with Theorem D given, then the values of and 3 can be obtained by referring to Table In the table, (k)
The detailed proof is provided in Appendix A.1
(k)
(k)
(k) we denote iu. as and PL..m for short. Y is the slope parameter of ReLU-like activation functions that are usually used in GCL, such as ReLU, PReLUU and RReLU. For example, y is zero for ReLU.
To this end, all the parameters to derive the lower bounds for
and fo. are known: the bounds of the variable Å in our prob- lem, which are L and defined in Definition 4 the parameters of the linear bounds for non-linear activations, which are and /3 defined in Definition Jand and obtained by Theorem] and Table To conclude, the whole process is summarized in the following theorem, where we apply bound propagation to our problem with those parameters:
Table 1: Values of a and
1
0
u S
0
else
(k)
L...m
1
Y
U.s.m
1
7
u 7
0
L,t.m
Theorem 2 (The lower bound of neural network output). the encoder is defined as [ Å is the augmented message-passing matrix and a is the non-linear activation function, for G1
3
U.i.
(K)
0
{-- Dla
1- y
(I, E G. A = D-112((1)) + +I)D-11 1/2 E A, then
Logh
Σ àgvil
Σ
Ojan J/ W
+ BB0 +6(2)
(6)
)EV(1)
12EN(()
where
wel = 22
2,
N
22.j.
N(1) = (j ai > -ila:)
jo =)],
(7)
(2)
Lism
(2)
iSWCL
2 0
(2))
3 L.j.
if iWWC
2.3.m
2 0
(8)
1.
U,i.m
iWWCL
2,1m < <0
km
U
((2)
if WWWLL
2,2,m <0
de Σ
(
WCL
A
(2)
W
0
(2)
Σ
(2) (b
+ +A (2)
(
mm
m.m m
(1)
(f
i 2
(1)
Liim
4
(10)
1m
U,im
<0
111
U.I
iWW 1,
<0
dg Σ 10 + +
A = ( @ (11) W(()
Σ
1 (1)
6 12
(11)
(2) (2) ( E Rd; X0) (1)
A E RA; w w E , 600 E R: dj and
d2 are the dimension of the embedding of layer and layer 2 respectively.
We provide detailed proof in Appendix A.2 Theorem 2 demonstrates the process of deriving the node compactness f f... in bound propagation manner. Before Theorem 2 we obtain all the parameters needed, and we apply the bound propagation method [32] to our problem, which is the concatenated network of the GCN encoder fa and a linear transformation W .As the form of Eq. 6 the node
compactness [ can be also seen as the output of a new "GCN" encoder with network parameters
W(2) b(1), [(2), which is encoder constructed from the GCN encoder in GCL.Adiitinnally, present the whole process of our POT method inAlgorithm] [
Time Complexity The computation of the weight matrices in Theorem 2 dominates the time complexity of POT. Thus, the time complexity of our algorithm is O + Edg) for the k-th layer, which is the same the message- nessage-passing 4 10] in the GNN encoders.
5
Experiments
5.1 Experimental Setup
We choose four GCL baseline models for evaluation: GRACE 35
GCA 36 ProGCL 25), and COSTA [34]. Since POT is plugin for InfoNCE loss, integrate POT with the baselines and

---

Algorithm 1: Provable Training for GCL
Input :Graph G (X, A), the set of all possible augmentations g Output : Node embeddings Z and Zz
Initialize GNN encoder paramenters {Wa), b(), w b
2 while not converge do
Generate graph augmentations G1 = (X, A1) and G2 = (X, A2);
Do forward pass, obtain Z₁ - =fo(X, A) and Z2 fx(X, A2), calculate LIsONCEE
Obtain the pre-activation bounds {P/,)
(k) P P(), }. k 1, as in Theorem
Set {aL (k)
(k) (8(4) -
1.2 according to Table 1
: 20 Derive f Loz, in Theorem 2 for 1 to N and calculate Cor in Equation 4
Do backward propagation with C (1 x) LInONCE (Z, Z2) + (
9 end
return Z₁, Ze for downstream tasks;
construct four models: GRACE-POT, GCA-POT, ProGCI--POT, and COSTA-POT. Additionally, we report the results of two supervised baselines: GCN and GAT (20. For the benchmarks, we choose 8 common datasets: Cora, CiteSeer, PubMed (28). Flickr, BlogCatalog [3], Computers, Photo [8], and WikiCS [14]. Details of the datasets and baselines are presented in Appendix C.2 For datasets with public split available (28), including Cora, CiteSeer, and PubMed, we follow the public split; For other datasets with no public split, we generate random splits, where each of the training set and validation set contains 10% nodes of the graph and the rest 80% nodes of the graph is used for testing.
5.2
Node Classification
Table 2: Performance (% = o) on Node Classification
GRACE
GCA
ProGCL
COSTA
Datascts
Metries
GCN
GAT
w/o POT
w/ POT
w/o POT
w/ POT
w/o POT
w/
w/o POT
w/ POT
81.9
828105
78.2
7922112
79.6 7.
79.9 7.
7.7
Cora
Ma-FI
80.6 1.1
818403 76. 0.6 77.8 14 77.7 101 77. 78.8 79.5 80.1 + 0.8
Mi.FI
71.6+ 0.6
72.1
66.8
1.0
68.7 + 0.6 05.0 69.0 + 0.8 65.9 0.9 67.7 + 0.9
06.5
67.9 0.7
CiteSeer
68.2
0.5
63.2
64.0
0.7
L.9
63.4
1.2
Mi-FI
79.3 0.1
81.6 0.7
820 1.3 80 82. 2.0 81. 1.1 81.9 80.0 1.5 80.6
PubMed
Ma-FI
79.0 0.1 0..6 81.7 - 0.5 82.4+ 1.2 2.15 82.9 2.0 81.3 1.0 82 0.4 79.3 1.4 80.3 1.5
Mi-F1
48.8 1.9 37.3 1.0.0..
46.5 1 1.8 48.4 1.3 47.4 1 0.8 50.3 1 0.3 46.4 1 1.4 49.7 1. 0.5 52.6 11 1.2 53.8 1 1.2
Flickr
Ma.Fi
45.8 1
2.4 35.2 0.7 45.1 + 1.4 47.0 1.6 46.2 + 0.8 49.3 + 0.4 45.4 1.1 48.9 + 0.3 51.2 + 0.9 55.6 + 1.3
Mi-FI
72.4 2.5 2.1 70.5 - 1.3 72.4 14 0.6 76.5 0.5 74.1 4.0. 76.0 + 0.7 73.3 + 3.4 75.1
BlogCatalog
Ma-Fl
71.9 2.4 67.6 1.8 70.2 = 1.3 71.8 144 7.7 76.1 0.5
75.7 2..6
0.9 73.0 33. 74.9 1.6
Mi-F1
87.6 0.6 88.7 3.7:13 1.3 85. 0.4 86.9 0.7 $8.7 89.1 = 0.3 88. 89.0
0.5
82. 0.4
0.7
Computers
Ma-Fl
83.1 1 2.3 79.3 1 1.4
83.9 1 0.8 84.5 1.4 87.1 0.7 87.6 1 0.5 86.9 87.4 1 0.9 78.6
1.7
79.0
Mi-F1
91.7 1 0.7
91.2
L..
0.3
0.3
Photo
Ma-FI
68.8 2.0 88.9 80.2
90.0 + 0.6 0.5 90.0 + 0.6 90.6 90.9 + 0.6 80.3 1.3 90.1
Mi-FI
81.2 1.2 8..2 80.3 0.3 80.6 0.3 7..7
80.7 = 0.3 78.8 80.0 0.5 70.2 79.1 0.9
WikiCS
Ma-FI
78.7 78.3 7.36 78.0 0.3 78.1 78.0 0.3 7..6 77.2
0.8
We test the performance of POT on node classification. For the evaluation process, we follow the as follows: the encoder trained in a contrastive learning manner without supervision, then we obtain the node embedding and use the fixed embeddings to train and evaluate a logistic regression classifier on the downstream node classification task. We choose two measures: Micro-Fl score and Macro-Fl score. The results with error bars are reported in Table 2
setting in baselines [35 36 25 34
7

---

Bolded results mean that POT outperforms the baseline, with a t-test level of 0. As it shows. our POT method improves the performance of all the base models consistently on all datasets, which verifies the effectiveness of our model. Moreover, POT gains significant improvements over baseline models on BlogCatalog and Flickr. These two datasets are the graphs with the highest average node degree, therefore there are more possible graph augmentations in these datasets (the higher node degrees are, the more edges are dropped [35] 36J). This result illustrates our motivation that POT improves existing GCL methods when faced with complex graph augmentations.
5.3 Analyzing the Node Compactness
To illusttrtee how POT improves the training of GCL, we conduct experiments to show some interesting properties of POT by visualizing the node compactness in Definition 2
More experiments can be
found in Appendix D
POT Improves Node Compactness. We illustrate that our POT does improve the node compactness, which the goal of InfoNCE. The result on Cora is shown Figure 2 The x-axis the epoch number, and the y-axis is the average compactness of all nodes. We can that the node compactness of the model with POT is almost always higher than the model without POT, indicating that POT increases node compactness in the training of GCL, i.c. how the nodes follow the GCL principle is improved in the worst-case. Therefore, our POT promotes nodes to follow the GCL principle better. More results on BlogCatalog shown in Appendix D
Node Compactness
0.2
GRACE
Node Compactriss
GCA
Node Comgactnies
0.3
ProGCL
Rode Compactned S1
0.6
COSTA
GRACE POT
0.3
GCA POT
ProGCL POT
COSTA POT
0.2
0.4
0.1
0.1
0.1
0.2
0.0
100
200
500 Epoch
1000
0.0
500
1000
0.0
500
Epoch
Epoch
Epoch
(a) GRACE
(b) GCA
(c) ProGCL
(d) COSTA
Figure Node compactness in the training process
Node Compactness Reflects Different Properties Different Augmentation Strategies. There are two types of augmentation strategies: GRACE adapts uniform edge dropping rate, in other words, the dropping rate does not change among different nodes; GCA, however, adapts a larger dropping rate on edges with higher-degree nodes, then higher-degree nodes have a larger proportion of edges dropped. Since node compactness is how node follows the GCL principle in the worst case, a higher degree results in larger node compactness, while a higher dropping rate results in lower node compactness because worse augmentations can be taken. To see whether node compactness can plot the average node compactness
reflect those properties of different augmentation expected, of the nodes with the same degree as scatters in Figure 3 on BlogCatalog and Flickr. For GRACE, positively correlated, since the dropping rate does not change the
node degree and compactness degree increases; For GCA, node compactness reflects a trade-off between dropping rate and degree: the former dominates in the low-degree stage then the latter dominates later, resulting the curve drop then slightly rise.
1.2
Mode Compaet
1.0
0.8
Node: Compartrics
0.15
0.20
Modic Compartness
0.30
20.20
0.15
0.6
0.05
6.10
0.4
Mode
0.05
0.05
0.00
0.00
200
400
1000
200
400
1000
Degree
Degree
Degree
Degree
(a) GRACE, BlogCatalog
(b) GRACE, Flickr
(c) GCA, BlogCatalog
(d) GCA, Flickr
Figure 3: Degree and node compactness score
8

---

5,4 Hyperparameter Analysis
In this subsection, we investigate the sensitivity of the hyperparameter POT, R: in Eq. 5 In our experiments, we tune ranging from (0.5, 0.4, 0.3, 0.2, 0.1, 0.05). The hyperparameter balances between InfoNCE loss and POT, i.e. the importance of POT is strengthened when > 0.5 while the InfoNCE is more important when K < 0.5. We report the Micro-Fl score on node classification of BlogCatalog in Figure 4 Although the performance is sensitive to the choice of K, the models with POT can still outperform the corresponding base models in many cases, especially where POT outperforms the base models whichever x is selected. The result on Cora is in Appendix D
BlogCatalog
0.75
0.800
0.800
0.800
0.775
Nigo-F1
0.775
0.70
0.750
0.750
0.65
0.725
0.725
0.725
0,700
0.700
0.5 044
0.3 0.2 0.1 0.05
0.5 0.4
0.3
0.2
01 0.05
0.5
0.4
0.3
0.2
0.1 0.05
0.5
0.4
0.3
0.2
0.1 0.05
(a) GRACE-POT
(b) GCA-POT
(c) ProGCL-POT
(d) COSTA-POT
Figure 4: Hyperparamenter analysis on K
Related Work
Graph Contrastive Learning. Graph Contrastive Learning (GCL) methods are proposed to learn the node embeddings without the supervision of labels. GRACE [35] firstly proposes GCL with random edge dropping and feature masking as data augmentations and takes InfoNCE as the objective. Based on GRACE. GCA [36] improves the data augmentation with adaptive masking and dropping rate related to node centrality. COSTA (34] proposes feature augmentation in embedding space to
reduce sampling bias. ProGCL (2 reweights the negatives and empowers GCL with hard negative
mining. There are also node-to -o-gaph GCL methods, like DGI [21 and MVGRL [ Inspired by
BYOL o there are also several GCL methods that do not need negative samples 19 or use BCE
objectives 31
Bound Propagation. Bound Propagation methods derive the output bounds directly from input bounds. Interval Bound Propagation (5) defines the input adversarial polytope as a 4o0 -norm ball, and it deforms being propagated through affine layers and monotonic activations. (16) proposes a relaxation on nonlinearity via Semidefinite Programming but is restricted to one hidden layer. 24 relaxes ReLU via convex outer adversarial polytope. [32 can be applied to general activations bounded by linear functions. For GNN, 37) and (38 study the bound propagation on GNN with feature and topology perturbations respectively. One step further, [17] proposes a Mixed Integer Linear Programming based method to relax GNN certification with a shared perturbation as input. However, almost all the previous works require solving an optimization problem with some specific solver, which is time-consuming and impossible to be integrated into training process as we expected.
7 Conclusion
In this paper, investigate whether the nodes follow the GCL principle well enough in GCL training, and the answer is no. Therefore, to address this issue, we design the metric "node compactness" to measure the training of each node, and we propose POT as regularizer optimize node compactness, which can be plugged into the existing InfoNCE objective of GCL. Additionally, we provide a bound propagation-inspiee method to derive POT theoretically. Extensive experiments and insightful visualizations verify the effectiveness of POT on various GCL methods.
Limitations and broader impacts. One limitation of our work is the restriction the settings of
GCL. To extend our work to more types of GCL settings and graph-level GCL, one can define the set of augmentations and network structure properly, then follow the proof in Appendix A.2 to derive the
node compactness in a new setting. The detailed discussion can be found in Appendix B We leave them for future work. Moreover, there are no negative social impacts foreseen.

---

Acknowledgments and Disclosure of Funding
This work is supported in part by the National Natural Science Foundation of China (No. U20B2045. 62192784, U22B2038, 62002029, 62172052, 62322203).
References
[1] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3950-3957, 2021.
[2] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint AXiv:2006.079888, 2020.
[3] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Gruphs and Manifolds, 2019.
[4] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263 1272. PMLR, 2017.
[5] Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4842-4851, 2019.
[6] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in neural information processsin systems, 13:21271-221 212244, 2020.
[7] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[8] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International conference on machine learning, pages 41 16-4626. PMLR, 2020.
[9] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks, arXiv preprint arXiv: 1905. 12265, 2019.
[10] Thomas N. Kipf and Max Welling. Semi sumi-super classification with graph convolutional networks. In Sth International Conference on Learning Representations, ICLR 2017. OpenRe- view.net, 2017.
[11] Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma. Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. Advances in Neural Information Processing Systems, 34:9720-9727 9733, 2021.
[12] Yaogi Liu, Cheng Yang. Tianyu Zhao, Hui Han, Siyuan Zhang, Jing Wu, Guangyu Zhou, Hai Huang, Hui Wang, and Chuan Shi. Gammagl: A multi- balkinbbckedd library for graph neural networks. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Information Retrieval, pages 2861-2870. ACM, 2023.
[13] Zaiqiao Meng, Shangsong Liang, Hongyan Bao, and Xiangliang Zhang. Co-embedding attributed networks. In Proceedings of the twelfth ACM international conference on web search and data mining, pages 393-401, 2019.
[14] Péter Mernyei and Cătälina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv.2007.02901, 2020.
[15] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint 88X.v.1807.03748, 2018
10

---

[16] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness adversarial examples. Advances in neural information processing systems, 31, 2018.
[17] Jan Schuchardt, Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Col- lective robustness certificates: Exploiting interdependence in graph neural networks, arXiv preprint 1rXiv:2332.02282) 2023.
[18) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1. 2018.
[19] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. In ICLR 2021 Workshop Geometrical and Topological Representation Learning, 2021.
[20] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua 2017
Bengio. Graph attention networks. arXiv preprint
[21] Petar Velickovic, William Fedus, William I. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
[22] Xiao Wang. Nian Liu, Hui Han, and Chuan Shi. Self-supervised heterogeneous graph neural network with co-contrastive learning. In Proceedings of the 27th ACM SIGKDD conference knowledge discovery & data mining, pages 173661136, 2021.
[23] Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learning of representations via graph neural networks. Nature Machine Intelligence, 4(3):279- 2022.
[24] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning, pages 5286-5295. PMLR, 2018
[25] Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z Li. Progel: Rethinking hard negative mining in graph contrastive learning. In International Conference on Machine Learning, pages 24332-24346. PMLR. 2022.
[26] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1XX.:18100000266 2018
[27] Siyong Xu, Cheng Yang, Chuan Shi, Yuan Fang, Yuxin Guo, Tianchi Yang, Luhao Zhang, and Maodi Hu. Topic-aware heterogeneous graph neural network for link prediction. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2261-2270, 2021.
(28) Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMIR, 2016.
[29] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5823 2020.
[30] Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoe Viet Hung Nguyen. Are graph augmentations necessary? simple graph contrastive learning for recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1294-1303, 2022.
[31] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. Advances in Neural Information Processing Systems, 34:76-46660 89, 2021.
[32] Huan Zhang, Tsui-Wei Weng, Pin- Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in Neural Information Processing Systems 31, pages 4944-4953, 2018.

---

[33] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems. 31, 2018.
[34] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Costa: Covariance- preserving feature augmentation for graph contrastive learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2524 2534,, 2022.
[35] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv: 04166. 2020.
[36] Yangiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pages 2069-2080, 2021.
[37] Daniel Zügner and Stephan Günneeann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 246-256, 2019.
[38] Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1656-1665, ACM, 2020.
12

---

A Proofs and Derivations
A.1 Proof of Theorem
1
Proof. We mainly make use of a conclusion in [16 and express it as the lemma below:
Lemma 1 (Bound propagation of affine layers (T6]. In an affine layer x* W x--1 ba_ the lower bound 1x and upper bound u of k-th layer after affine transformation can be obtained by
+ 1s [W - [WK-]] 11- k- + b-- u
[W -wik'l-uu -i_uu=1 + [W + b 8-1
where [W*]+ max 0) and [W min (W* 0), Wh is the weights of affine transforma- tion the k-th layer.
In our problem, since A is variable, we take (k) (())) as the weights of the affine transformation and replace 1s and u with the bounds L and U. To this end, Theorem is proved.
A.2 Proof of Theorem
Proof. Since (k) is the output embedding of the k-th layer, which implies that ( is the input embedding of k-th layer. p(k is the pre-activation embedding in Theorem | fo(X, A1) (P(2)), P(2) Ao (P()) + b(2), p(1) Axw()) + b(1), With the parameters a, B, L, U obtained, as well as the parameters of the GCN encoder (W(), b w b(2) given, we can derive the lower bound fog in a bound propagation
332 manner, by taking Á as a variable with element-wise upper and lower bound in Definitio
Lons = (P W
(12)
= min Σ
o ( CLL
1.m 2
(13)
m=1
Σ
(a L.dm ( + (),))) ))
WCL +
Σ
(o
(2 +
+00 (l)
WCI.
2,
woL 20
WCL X0 2,
2,
(14)
Σ
WCL (2) (p.2) + +
2.1m i.m
(15)
dg
i,m (p + (2))
(16)
a (P.") w( :.m + +6(2) + + (2)
+
k,m)
(17)
(EN(()
( ((2)
(18)
1)N()
dj 2 (1)
Σ HEN()
+
(19)
if
d
Σ
(1)
+ ( +7.00
(20)
HEN(
1=1
Σ djie( Σ
JJ (1( + T()) + 6
(21)
ЛEN(
heN(()
13

---

is the equivalent form of 12. and (4 is because: since a Lidm Pimm + 3 L.sm S so(
(R)
13
D,imm (p + B U.amm. then if W 2, is multiplied to the inequality, have
L.i.m
(k) (ptt) + L W S <o(p W S Sov (rim + - W
if WC
2,3m
2 0,
(22)
(k) Usim (p + Pusm) W
(K) W.r. (K) (k) W 2,am S (p W 2, I a + 1 L.im 2 2,
W if W.CL 0. (23)
2,1
(2) In 15 we combine a and oi into a single parameter , and similarly for ( In 16).
(2)
and W combined to be A, We expand the expression of p to get (17). Since is not related to j1. we move the outer sum into the inner sum, and the parameters can be further combined,
therefore get (18). With the ideas above, the following equations can be derived, and finally,
get 21 which is exactly the form in Theorem 2
B A Detailed Discussion on the Limitations
The definition of augmented adjacency matrix. In Definition 3 we present the definitions and theorems under the condition of edge dropping since it is the most common topology augmentation in GCL [35 31 19.. The proposed POT is suitable for various augmentation strategies including edge dropping and adding. POT is applicable as long as the range of augmentation is well-defined in Definition 3 For example, if edge addition is allowed, the first constraint in Definition 3 can be removed, resulting the change of the element-wise bound Definition [5] After the element-wise bound is defined, the other computation steps are the same, then the POT loss with edge addition can be derived. Since edge addition is not a common practice and all the baselines use edge dropping only, we set the first constraint in Definition 3 to obtain a tighter bound.
Applying POT graph-level GCL. If the downstream task requires graph embeddings, POT still stands. First, related concepts like "graph compactness" can be defined similarly to node compactness. Second, the pooling operators like "MEAN", "SUM", and "MAX" are linear, therefore the form of "graph compactness" can be derived with some modifications on the steps in Appendix A.2
Generalizing to Other Types of Encoders. Definition and Theorem 2 are based on the assumption that the encoder is GCN since GCN is the most common choice in GCL. However, other encoders are possible be equipped with POT. GraphSAGE (7) has a similar form GCN, then the derivation steps are similar. For Graph Isomorphism Network [26] and its form is
h (1+1) MLP((1 + +))(()
Σ
h())).
(EN(N)
We can first relax the nonlinear activation functions in MLP with Definition 5 then obtain the pre-activation bounds with Theorem 1, and finally follow the steps in Appendix A.2 to derive the form of node compactness when GIN encoder is applied.
The provable training of feature augmentation this paper, we focus on topology augmentations. However, we have mentioned in the limitation, feature augmentation is also common class of augmentations. We explore the provable training for feature augmentation as follows. Unlike topology augmentation, the augmented feature is only the input of the first layer, so it is easier to deal with. Inspired by [37], we can relax the discrete manipulation into / constraints, then the node compactness is related to the feasible solution of the dual form. A similar binary cross-entropy loss can be designed. More detailed derivations are still working in progress.
However, more efforts are still to be made to deal with some subtle parts. Future works are in process.
C Experimental Details
C.1 Source Code
The complete implementation can be found at hhtts:/giiibooom//ooaaaaa////.. We also pro- vide an implementation based on GammaGL [2 altne//ghhhloocm///PP//GGMMAAAA
14

---

C.2 Datasets and Baselines
We choose common datasets for evaluations: Cora, CiteSeer, and PubMed[228,, which are the most common graph datasets, where nodes are paper and edges are citations; BlogCatalog and Flickr, which are social network datasets proposed in [33, where nodes represent users and edges represent social connections; Computers and Photo [8] which are Amazon co- co-purchase datasets with products as nodes and co-purchase relations as edges; WikiCS 14,, which graph dataset based on Wikipedia in Computer Science domain. The statistics of the datasets are listed in Table A percentage in the last columms means the percentage of nodes used in the training/valian saaiingg/alidattiontsstigg phase.
Table 3: The statistics datasets
Datasets
Nodes
Edges
Features
Classes
Training
Validation
Test
Cora
2708
10556
1433
140
500
1000
CiteSeer
3327
9104
3703
120
500
1000
PubMed
19717
88648
500
60
500
1000
BlogCatalog
5196
343486
8189
10%
10%
80%
Flickr
7575
479476
12047
10%
10%
80%
Computers
13752
491722
767
10
10%
10%
80%
Photo
7650
238162
645
10%
10%
80%
WikiCS 11701
216123
300
10
10%
10%
80%
We obtain the datasets from PyG 33.
Although the datasets are available for public use, we cannot
find their licenses. The datasets can be found the URLs below:
Cora, CiteSeer, PubMed:
BlogCatalog: https://docs..oogg///////oo SuRiiDDoBiiskuS//Scccoimm http://wwgggoooooooo/o/ooooooooa
Flickr: ottp://ogggg...ooooooo//ooooo/op x66 8uGssU662Xccommmmm--
Computers, Photo: http:////wha.haaoaa//////////a/a
WikiCS: ,
For the implementations of baselines, we use PyG to implement GCN and GAT. For other GCL
baselines, we use their original code. The sources are listed as follows:
GCN: ChinrS/ihhhhhhonnnnnnnnnnnnooooo
GAT: Gtl.l//hhhhooooyyyaayoooooooooom GRACE: hhApa//h...ggggoooooooCCCCC///na GCA: http::/s/ggihbbbcoooooccccccccco
ProGCL: http:h/:hggggiibboooo//////////p COSTA: https://ggituubboooyyllaa///C/Ct
We implement our POT based on the GCL baselines with Porch..
C.3
Hyperparameter Settings
To make fair comparison, we set the drop rate be consistent when testing the performance gained by our proposed POT. The drop rates of edges (p2. p²) are given in Table
Table 4: Hyperparameters: (p..p2)
Models
Cora
CiteSeer
PubMed
Flickr
BlogCatalog
Computers
Photo
WikiCS
GRACE
(0.4, 0.3)
(0.3, 0.1)
(0.4, 0.1)
(0.4, 0.1)
(0.4, 0.3)
(0.6, 0.4)
(0.5, 0.3)
(0.2, 0.3)
GCA
(0.3, 0.1)
(0.2, 0.2)
(0.4, 0.1)
(0.3, 0.1)
(0.3, 0.1)
(0.6, 0.3)
(0.3, 0.5)
(0.2,
ProGCL
(0.3, 0.1)
(0.4, 0.3)
(0.4, 0.1)
(0.4, 0.1)
(0.4, 0.2)
(0.6. 0.3)
(0.6. 0.3)
(0.2, 0.3)
COSTA
(0.2, 0.4)
(0.3, 0.1)
(0.4, 0.1)
(0.4, 0.1)
(0.4, 0.2)
(0.6, 0.3)
(0.3, 0.5)
(..3,
15

---

Additionally, we provide the values of the hyperparameter in our POT, as well as the temperature Table
Table 5: Hyperparameters: (T, k)
Models
Cora
CiteScer
PubMed
Flickr
BlogCatalog
Computers
Photo
WikiCS
GRACE-POT
(0.7, 0.4)
(0.9, 0.5)
(0.5,011) 0.1)
(0.3, 0.1)
(0.5, 0.3)
0.3)
(0.3, 0.1)
(0.2, 0.4)
(0.3, 0.05)
GCA-POT
(0.6, 0.3)
(0.7,0a 0.5)
0.130.1)
0.5)
(0.3, 0.3)
(0.2, 0.2) 0.2)
(0.6, 0.2)
(0.3, 0.1)
ProGCL-POT
(0.4, 0.4)
(0.5.0.2
0.33
(0.3,
(0.3, 0.2)
(0.3.
(0.2.
(0.4. 0.1)
COSTA-POT
(0.4, 0.1)
(0.3, 0.05)
(0.4,
(0.2.011)
(0.05, 0.4)
(0.1.
(0.2,
(0.4, 0.3)
We provide more hyperparameters which may also have effects the performance. In Table 6
"num_ saam__epchs"" is the epoch number for training, and "pot_batch" is the batch size of POT, "-1" means
full batch is used.
Table Hyperparameters: (pot_batch, num_epochs)
Models
Cora
CiteSeer
PubMed
Flickr
BlogCatalog
Computers
Photo
WikiCS
GRACE-POT
(-1, 200)
(-1, 200)
(256, 2500)
(512, 1000)
(-1, 1000)
(512, 2500)
(512, 0.4)
(512, 4000)
GCA-POT
(-1. 700)
(-1. 1000)
(256. 2500)
(1024. 2500)
(1024, 1500)
(256. 2500)
(1024, 2500)
(1024,3500)
ProGCL-POT
(1, 1000)
(-1, 700)
(256, 2000)
(512, 2000)
(1024, 1500)
(256, 3000)
(1024, 2500)
(256, 3000)
COSTA-POT
(-1, 600)
(-1, 1500)
(512, 2000)
(1024, 2500)
(1024, 2500)
(256. 2500)
(512, 3500)
(256, 3000)
C.4 Environment
The environment where our codes run is as follows:
OS: Linux 5.4.0-131 --gneeric
CPU: Intel(R) Xeon(R) Gold 6348 CPU @ 2.60GHz
GPU: GeForce RTX 3090
D More Experimental Results
D.1 More Results for Section
We present more results of the imbalance of GCL training on Cora and Flickr shown in Figure 5 The conclusion is similar: it can be observed that the training of GCL on more datasets is also imbalanced on the untrained nodes.
D.2 More Results for Section 53
We provide more results of the experiments Section 5.3
the node compactness score during training on BlogCatalog in Figure From the results, we can see that the conclusion in Section 5.3 the same on more datasets: our POT can promote node compactness compared to the original GCL methods, which can enforce the nodes to follow the GCL principle better.
D.3 More Results of Hyperparameter Analysis
The result of the hyperparameter analysis of on Cora is shown in Figure 7 POT outperforms the baseline models with most of the choices 6, which implies that the proposed POT robust the change of K.
16

---

600
500
500
400
400
Nodes
400
Nodes
300
300
200
200
100
100
0
7.2
7.4 InfoNCE
7.20
7.25
7.30
7.0
7.1
7.2
InfoNCE
InfoNCE
(a) GRACE- Cora
(b) GCA-Cora
(c) ProGCL-Cora
1500
1000
800
800
Nodes
1000
Nodes
600
# Nodes
600
500
400
400
200
200
0
0
InfoNCE
InfoNCE
InfoNCE
(d) GRACE-Flickr
(e) GCA-Flickr
(f) ProGCL-Flickr
Figure More results showing the imbalance of GCL training
Node Compactness
0.4
GRACE GRACE-POT
Nodo Compactiess
0.2
GCA GCA-POT
Node Compactness
ProGCL ProGCL-POT
Node Compactness:
COSTA COSTA-POT
0.15
0.2
0.10
0.1
0.05
0.0
500 Epoch
1000
0.0
1000 Epoch
2000
0.00
1000
0.0
1000 Epoch
2000
Epoch
(a) GRACE
(b) GCA
(c) ProGCL
(d) COSTA
Figure 6: Node compactness in the training process on BlogCatalog
0.850
0.825
0.825
0.000
0.800
Mere
Hirro
0.775
0.75
0.75
0.775
0.750
0. 6.750
(a) GRACE-POT
(b) GCA-POT
(c) ProGCL-POT
(d) COSTA-POT
Figure 7: Hyperparamenter analysis of is on Cora
D.4 More Insights and Explanations of Experiments on Node Compactness
we observe that the node compactness of traditional GCL methods may decreases with the increase of epoch. We think the "false negative" issue may contribute to the drop the curves in Figure Since GCL uses all samples, there are many false negatives, i.e., some nodes with the same class as the anchor node are treated as negative samples in the contrastive loss. in the definition, the node compactness measures the worst case of how well node behaves across all possible augmentations. Therefore, as
Node Compactness during training. In Figure 2nd Figure
1 nodes as negative
17

---

the epoch increases and some false negative information is captured, that "worst case" value may decrease. As a result, we observe a drop node compactness in traditional GCL methods. There are some existing methods alleviating this, called "hard negative mining", including the baseline method ProGCI. From Figure 2
we see that the curve of ProGCI almost does not drop, while the average node compactness of other methods decreases. Since our POT method explicitly optimizes the node compactness, the curve will continue to rise as the epoch increases. It is an open question and may be related to fundamental issues in contrastive learning.
Understanding the result in Figure 3 First, edges are randomly dropped with a uniform rate in GRACE. Since there are fewer unimportant edges around a low-degree node, those informative edges are more easily dropped, which prevents the contrastive loss from learning useful semanties, therefore those low-degree nodes are hard to be well-trained in GRACE. This is also the motivation of GCA. To alleviate this, GCA sets the dropping rate of edges by node centrality, keeping important edges around low-degree nodes. That's 's why we observe a high node compactness in low-degree nodes. However, the augmentation strategy of GCA puts a higher dropping rate for high-degree nodes. This may explain why node compactness drops the degree increases at first. When the degree comes to relatively large, the node is "strong" " enough for this augmentation strategy and is prone to be well-trained. To conclude, the node degree and node compactness are positively correlated in GRACE, however, there is a trade-off between degree and node compactness in GCA. This may explain why the result in Figure 3 is reasonable.
D.5 More Experimental Results
POT can improve the InfoNCE loss. In Section 2 we investigate the problem of existing GCL training with InfoNCE, since is the only metric we have, After that, we propose "node compactness" as a more appropriate and intrinsic metric to evaluate the training of a node in GCL. Therefore, we conduct experiments properties. That is the reason why we did not provide further analysis of InfoNCE. However, it is still inspiring to investigate whether POT can improve InfoNCE. Intuitively, POT can improve the InfoNCE loss. POT has larger regularization on the nodes that are not well-trained across all possible augmentations, as a result, the training of nodes under two specific augmentations is also improved. To illustrate this, we conduct an experiment comparing the InfoNCE loss values of the nodes with/without using POT, similar to the experiment in Section We choose GRACE and GCA as baselines and show the result of Cora in Figure 8 It can be seen that InfoNCE is improved by POT in two aspects: the average InfoNCE of the nodes is reduced, and the distribution of InfoNCE values becomes more centralized and balanced.
the Figures to show the validity of node compactness as well as some
250
GRACE
400
GCA
GRACE+ POT
GCA+POT
200
350
300
#icdes
150
250
200
100
150
100
50
0
0
7.50
7.55
7.60
7.65
7.70
7.75
7.80
7,450 7.475 7,500 7.525 7,550 7.575 7.603 7.625 7.650 Avg InfoNCE
Avg InfoNCE
(a) GRACE
(b) GCA
Figure 8: POT improves InfoNCE. The average of InfoNCE values is reduced and the loss values are more balanced.
The applicability of POT to different augmentation strategies. To investigate whether our POT applies to various graph augmentations, we evaluate the performance of POT under four types of topology augmentation: random edge dropping proposed in GRACE; node centrality-based topology
18

---

augmentations proposed in GCA, including degree centrality, eigenvector centrality, and PageRank centrality. The backbone of the GCL baseline is GRACE. The result on Cora and Flickr is given in Table 7 POT consistently outperforms the baseline models with different graph augmentations. stated in the Limitation section, since more theoretical verifications are needed, POT of other augmentations, including feature augmentations, are working in progress. We are looking forward to more capability of POT.
Table 7: POT improves existing GCL with different augmentations (Random: random edge dropping with a uniform rate: Degree: degree-centrality dropping rate; Eigenvector: cigenvector-centraliy dropping rate; PageRank: PageRank-centrality dropping rate).
Dataset
Method
Random
Degree
Figenvector
PageRank
FIMi
FIMa
FIMI
FIMa
FIMi
FIMa
FIMi
FIMa
Cora
GCL
78.2=00
76,8 0.6 77.8
73.6 0.2
77.7 0.1
08
0.6
7788
77.0 1.2 77.8
GCL+POT
+
79.6 1.4
79.1 + 1.4
79.1 1.2
78.3 1.5
79.1 1.0
Flickr
GCL
46.5 1.8
1..1
46.2
17.7 1.2
46.6 13
18.4
47.3 1.2
GCL+POT
49.8
48.7
50.3
49.3 0.4
49.7
48.8
5..
49.3
Node compactness can reflect the nodes' sensitivity to aug- mentations. We conduct experiment to show the relationship between a node's compactness and the standard error of its In- foNCE loss under different graph augmentations. Specifically, we first train GCL model, then fix the network parameters and sample 500 pairs of different augmentations. After encoding these augmentations, 500 InfoNCE loss values are obtained for each node. We choose calculate the standard error of these 500 values of each node to reflect its sensitivity to different augmentations. We also compute each node's compactness as Theorem 2nn in the paper, which is not related to specific aug- mentations. With the process above, we have a data sample InfoNCE_ std) for each node. We divide these samples into several bins by value node compact- ness and calculate the average of InfoNCE_stt std in each bin. Finally, we show the result as a scatter plot in Figure 9 It can be seen that less sensitive nodes have higher node compactness values. To conclude, this experiment shows that our proposed node compactness can be proxy of the node's 's sensitivity to different graph augmentations, as the motivation stated.
0.06
InfoNCE Std
0.04
0.02
0.00
0.2 node compactnesss
0.1
Figure Node compactness and the standard error of InfoNCE loss under different augmentations. More sensitive nodes have lower node compactness as expected.
19


Reviews:
[{"review_id": "fB9bVslmnX", "reviewer": "Reviewer_ynwF", "summary": "The paper aims at studying the node properties given different graph augmentations in graph contrastive learning. It has the following contributions. 1) It discovers the training of GCL methods is severely imbalanced. 2) It proposes a novel concept of “node compactness”, and the provable training for GCL with the concept. 3) Besides the theoretical analysis, the paper uses extensive numerical results to show the effectiveness of the proposed method. Generally, the paper is interesting and easy to follow. ", "questions": "- In Section 3, the authors observe the training imbalance in GCL and propose to address it using POT. Although they present node compactness results, they do not show the InfoNCE loss in the experiments, unlike in Figure 3. It would be helpful to include the InfoNCE loss in the experiment to provide a comprehensive evaluation. Additionally, it would be interesting to investigate if POT can also improve the InfoNCE loss.\n\n- The paper discusses various graph augmentations, and it would be valuable for the authors to provide a more specific discussion on how the proposed POT method can enhance existing GCL methods with different graph augmentations. Exploring the applicability of POT to different augmentation strategies would contribute to a more thorough understanding of its potential benefits.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper addresses an important problem in the GCL community and is engaging to read.\n- The technical contribution of the paper is novel and brings a fresh perspective to the field.\n- The proposed model is thoroughly evaluated on various benchmarks, demonstrating its effectiveness and providing strong evidence for its performance.\n", "weaknesses": "- The experiment section may lack some essential components or details, and therefore it could be considered insufficient.\n- The discussion on the limitations of the proposed method is relatively brief. It would be beneficial to expand on this section and provide a more comprehensive analysis of the limitations and potential challenges associated with the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive comments and valuable feedback on our paper. To further address your concerns, we provide additional experiments as well as a more detailed discussion of the limitations.\n\n1. > In Section 3, the authors observe the training imbalance in GCL and propose to address it using POT. Although they present node compactness results, they do not show the InfoNCE loss in the experiments, unlike in Figure 3. It would be helpful to include the InfoNCE loss in the experiment to provide a comprehensive evaluation. Additionally, it would be interesting to investigate if POT can also improve the InfoNCE loss.\n  \n    **Response**: Thanks for pointing this out. In Section 3, we investigate the problem of existing GCL training with InfoNCE, since it is the only metric we have. After that, we propose \"node compactness\" as a more appropriate and intrinsic metric to evaluate the training of a node in GCL. Therefore, we conduct experiments in the Figures to show the validity of node compactness as well as some properties. That is the reason why we did not provide further analysis of InfoNCE.\n    However, it is still inspiring to investigate whether POT can improve InfoNCE. Intuitively, POT can improve the InfoNCE loss. POT has a larger regularization on the nodes that are not well-trained across all possible augmentations, as a result, the training of nodes under two specific augmentations is also improved. To illustrate this, we conduct an experiment comparing the InfoNCE loss values of the nodes with/without using POT, similar to the experiment in Section 3. We choose GRACE and GCA as baselines and show the result of Cora in Figure 1 of the rebuttal PDF. It can be seen that InfoNCE is improved by POT in two aspects: the average InfoNCE of the nodes is reduced, and the distribution of InfoNCE values becomes more centralized and balanced. Those results and discussions will be added to the Appendix in the revision.\n\n2. > The paper discusses various graph augmentations, and it would be valuable for the authors to provide a more specific discussion on how the proposed POT method can enhance existing GCL methods with different graph augmentations. Exploring the applicability of POT to different augmentation strategies would contribute to a more thorough understanding of its potential benefits.\n   \n    **Response**: Thank you for suggesting improving the experiment. To investigate whether our POT applies to various graph augmentations, we evaluate the performance of POT under four types of topology augmentation: random edge dropping proposed in GRACE; node centrality-based topology augmentations proposed in GCA, including degree centrality, eigenvector centrality, and PageRank centrality. The backbone of the GCL baseline is GRACE. The result on Cora and Flickr is given in Table 1 in the rebuttal PDF. POT consistently outperforms the baseline models with different graph augmentations.\n    As stated in the Limitation section, since more theoretical verifications are needed, POT of other augmentations, including feature augmentations, are working in progress. We are looking forward to more capability of POT.\n\n3. > The discussion on the limitations of the proposed method is relatively brief. It would be beneficial to expand on this section and provide a more comprehensive analysis of the limitations and potential challenges associated with the proposed approach.\n\n    **Response**: Thanks for your suggestion. We have expanded the limitation section accordingly. Please refer to the \"global\" rebuttal."}, {"review_id": "cAxZwMjWtt", "reviewer": "Reviewer_QmjC", "summary": "Graph augmentation is a fundamental component for graph contrastive learning. When augmenting graph structures, how the change of structures affects the GCL is an interesting problem. In this work, the paper proposes the “node compactness” to describe the behavior of different nodes, i.e., whether there are some nodes consistently stable enough to the training process with different graph augmentations. With this concept, the paper designs a new POT regularization term as a plug-in, which enables the training process of nodes to follow the GCL principle, so as to improve the performance of GCL finally.", "questions": "1.\tThe first constraint in Definition 3 requires the graph augmentation is edge dropping. Does that mean the proposed provable training is only suitable for edge dropping?\n2.\tThe experiment analyzes the relationship between the node compactness with the properties of different augmentation strategies, while some statements are not well explained, which may be hard to understand. Specifically, why does a higher degree result in larger node compactness? Why the results in Fig.3 are reasonable? More details should be provided.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1.\tThe paper studies an important and challenging problem. The idea of node compactness is novel.\n2.\tUsing bound propagation to derive node compactness in GCL is also interesting and technically sound.\n3.\tThorough experiments are conducted to validate how the proposed model works.\n", "weaknesses": "1.\tSome techniques are not introduced clearly (see comments below).\n2.\tSome experimental results are also not clearly explained (see comments below).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank the reviewer for your interest in our paper and constructive suggestions. To make further clarification on the techniques and experimental details, we respond to the reviewer's questions one by one. We look forward to assisting to have a better understanding of our paper.\n1. > The first constraint in Definition 3 requires the graph augmentation is edge dropping. Does that mean the proposed provable training is only suitable for edge dropping?\n\n    **Response**: Thanks. We present the definitions and theorems under the condition of edge dropping since it is the most common topology augmentation in GCL[1, 2, 3]. The proposed POT is suitable for various augmentation strategies including edge dropping and adding. POT is applicable as long as the range of augmentation is well-defined in Definition 4. For example, if edge addition is allowed, the first constraint in Definition 3 can be removed, resulting in the change of the element-wise bound in Definition 4. After the element-wise bound is defined, the other computation steps are the same, then the POT loss with edge addition can be derived. Since edge addition is not a common practice and all the baselines use edge dropping only, we set the first constraint in Definition 3 to obtain a tighter bound. This discussion will be added to the revision.\n\n2. > The experiment analyzes the relationship between the node compactness with the properties of different augmentation strategies, while some statements are not well explained, which may be hard to understand. Specifically, why does a higher degree result in larger node compactness? Why the results in Fig.3 are reasonable? More details should be provided.\n\n    **Response**: Sorry for the confusion. First, edges are randomly dropped with a uniform rate in GRACE. Since there are fewer unimportant edges around a low-degree node, those informative edges are more easily dropped, which prevents the contrastive loss from learning useful semantics, therefore those low-degree nodes are hard to be well-trained in GRACE. This is also the motivation of GCA. To alleviate this, GCA sets the dropping rate of edges by node centrality, keeping important edges around low-degree nodes. That's why we observe a high node compactness in low-degree nodes. However, the augmentation strategy of GCA puts a higher dropping rate for high-degree nodes. This may explain why node compactness drops as the degree increases at first. When the degree comes to relatively large, the node is \"strong\" enough for this augmentation strategy and is prone to be well-trained.\n    To conclude, the node degree and node compactness are positively correlated in GRACE, however, there is a trade-off between degree and node compactness in GCA. This may explain why the result in Figure 3 is reasonable.\n\nReferences:\n\n[1] Zhu, Yanqiao, et al. \"Deep graph contrastive representation learning.\" arXiv preprint arXiv:2006.04131 (2020).\n\n[2] Zhang, Hengrui, et al. \"From canonical correlation analysis to self-supervised graph neural networks.\" Advances in Neural Information Processing Systems 34 (2021): 76-89.\n\n[3] Thakoor, Shantanu, et al. \"Bootstrapped representation learning on graphs.\" ICLR 2021 Workshop on Geometrical and Topological Representation Learning. 2021."}, {"review_id": "c8oeOexdMz", "reviewer": "Reviewer_Kesd", "summary": "The paper considers an important problem in graph contrastive learning, i.e., the relationship between the node property with the graph augmentations. The main takeaway is that the training of GCL on different nodes is imbalanced, and the concept “node compactness” is introduced to guarantee the training of GCL is provable. This is demonstrated on eight benchmarks. ", "questions": "See the above weakness.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "S1. The paper topic is interesting.\nS2. The theoretical foundation is solid.\nS3. The paper is relatively well-written and well-organized.", "weaknesses": "The experiments section could be strengthened. I’m not sure that whether the following experiment needs to be conducted. Specifically, the paper aims to discover the nodes that are not sensitive to different graph augmentations. However, there is no experiment to analyze this, i.e., maybe we can generate different graph augmentations to check whether some nodes are always well trained, or not well trained? Moreover, some notations are not described, e.g., [ ]+ and [ ]- in Theorem 1. Also, why the curve of traditional GCL methods decreases with the increase of Epoch in Fig.2? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the precious time spent reading through the paper and giving constructive suggestions. To address the concerns, we clarify the experiment section and some notations as follows.\n1. > The experiments section could be strengthened. I’m not sure whether the following experiment needs to be conducted. Specifically, the paper aims to discover the nodes that are not sensitive to different graph augmentations. However, there is no experiment to analyze this, i.e., maybe we can generate different graph augmentations to check whether some nodes are always well trained, or not well trained? \n\n    **Response**: We greatly thank the reviewer for this suggestion. To investigate whether our proposed node compactness can reflect the nodes' sensitivity to augmentations, we conduct an experiment to show the relationship between a node's compactness and the standard error of its InfoNCE loss under different graph augmentations. Specifically, we first train a GCL model, then fix the network parameters and sample 500 pairs of different augmentations. After encoding these augmentations, 500 InfoNCE loss values are obtained for each node. We choose to calculate the standard error of these 500 values of each node to reflect its sensitivity to different augmentations. We also compute each node's compactness as Theorem 2 in the paper, which is not related to specific augmentations. With the process above, we have a data sample (node_compactness, InfoNCE_std) for each node. We divide these samples into several bins by the value of node compactness and calculate the average of InfoNCE_std in each bin. Finally, we show the result as a scatter plot in Figure 2 in the rebuttal PDF. It can be seen that less sensitive nodes have higher node compactness values. To conclude, this experiment shows that our proposed node compactness can be a proxy of the node's sensitivity to different graph augmentations, as the motivation stated. I hope this experiment can make the paper more self-contained.\n2. > Moreover, some notations are not described, e.g., [ ]+ and [ ]- in Theorem 1.\n   \n   **Response**: Sorry for the confusion in the notations. Here $[X]\\_+$ denotes $\\max(X,0)$ and $[X]\\_-$ denotes $\\min(X,0)$. We will check the description of the notations in the revision thoroughly.\n\n3. > Also, why the curve of traditional GCL methods decreases with the increase of Epoch in Fig.2?\n   \n   **Response**: Thanks for pointing this out. We think the \"false negative\" issue may contribute to the drop in the curves in Figure 2. Since GCL uses all $N-1$ nodes as negative samples, there are many false negatives, i.e., some nodes with the same class as the anchor node are treated as negative samples in the contrastive loss. As in the definition, the node compactness measures the worst case of how well a node behaves across all possible augmentations. Therefore, as the epoch increases and some false negative information is captured, that \"worst case\" value may decrease. As a result, we observe a drop in node compactness in traditional GCL methods.\n   There are some existing methods alleviating this, called \"hard negative mining\", including the baseline method ProGCL. From Figure 2, we see that the curve of ProGCL almost does not drop, while the average node compactness of other methods decreases. Since our POT method explicitly optimizes the node compactness, the curve will continue to rise as the epoch increases.\n   It is an open question and may be related to fundamental issues in contrastive learning. We look forward to further discussions."}, {"review_id": "qLi4ek5N0h", "reviewer": "Reviewer_AXri", "summary": "The goal of this paper is to investigate the properties of different nodes in GCL with different graph augmentations. The paper discovers the imbalanced training issue of GCL methods, and proposes the concept “node compactness”, measuring how each node follows the GCL principle. Finally, the paper proposes the node compactness regularization, and shows its effectiveness by combining it with existing GCL methods.", "questions": "See Weaknesses", "limitations": "The discussion section of the paper is concise but unsatisfactory in addressing the main points.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper is well motivated with both theoretical and empirical analysis.\n- The paper provides some interesting insights on the node properties in GCL.\n- The effectiveness of the proposed model is well demonstrated by the empirical results.", "weaknesses": "- One of the motivations is that “how to distinguish these nodes”, while it seems that the paper doesn’t distinguish these nodes?\n- Although the presentation is good enough, I’m not very clear with the whole training process because of the math-heavy part in the technique part. Do we need to compute the POT first, and then train InfoNCE loss? Or do we need to train the model with the two steps iteratively? \n- In theorem 1, the conclusion is obtained under the condition that AXW+b, so if the GCN process is not AXW+b, can we still use POT regularization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the positive comments and valuable feedback from the reviewer. Below, we address the reviewer's concerns one by one, hoping that a better understanding of every point can be delivered.\n1. > One of the motivations is that “how to distinguish these nodes”, while it seems that the paper doesn’t distinguish these nodes?\n   \n    **Response**: Thanks. Specifically, the value of node compactness serves as a good metric to distinguish all the nodes in a graph by how much they are prone to be well-trained. It is a relative measure, instead of giving an explicit bound of discrimination. In Figure 3, nodes with different properties are distinguished by the node compactness, directly addressing this motivation.\n    \n2. > Although the presentation is good enough, I’m not very clear with the whole training process because of the math-heavy part in the technique part. Do we need to compute the POT first, and then train InfoNCE loss? Or do we need to train the model with the two steps iteratively?\n   \n    **Response**: Sorry for the confusion. We describe the whole process of graph contrastive learning with the provable training as follows:\n\n    (1) Generate two augmented graphs $G_1$ and $G_2$ from $G$;\n\n    (2) Perform the forward pass and the node embeddings $Z_1$ and $Z_2$ are obtained. Compute the InfoNCE loss $\\mathcal L_{\\text{InfoNCE}}(Z_1. Z_2)$;\n\n    (3) Compute the POT loss as Algorithm 1 in our paper described;\n\n    (4) Combine the two losses as in Equation 5, then do the backward propagation to update the network parameters;\n\n    (5) Iteratively do steps (1)-(4) until stop.\n   \n   In these steps, step (1)-(2) is the same as traditional GCL. We will improve the presentation of Algorithm 1 as above in the revision. \n3. > In theorem 1, the conclusion is obtained under the condition that AXW+b, so if the GCN process is not AXW+b, can we still use POT regularization?\n   \n    **Response**: Yes, POT is capable of various graph encoders. Since GCN is the most common encoder in GCL methods, we mainly provided the derivation of the form of node compactness for GCN. For other types of encoders, the form of node compactness can be derived similarly using Definition 5 and Theorem 1. For example, if the encoder is Graph Isomorphism Network, and its form is \n    $$\n    h_v^{(k+1)}=\\text{MLP}((1+\\epsilon)h_v^{(k)}+\\sum_{u\\in \\mathcal N(v)}h_u^{(k)}).\n    $$\n    We can first relax the nonlinear activation functions in MLP with Definition 5, then obtain the pre-activation bounds with Theorem 1, and finally follow the steps in Appendix A.2 to derive the form of node compactness when a GIN encoder is applied.\n    We will add this discussion in the revision to improve the \"Limitation\" section. \n4. > The discussion section of the paper is concise but unsatisfactory in addressing the main points.\n   \n   **Response**: We have expanded the discussion of limitations. Please refer to the \"global\" rebuttal."}]

Author rebuttal:
We sincerely thank all reviewers for the acknowledgment of our paper and for many constructive comments. Since some reviewers mentioned that the discussion of limitations may be relatively brief, we expand that part as follows. Due to the limited time, we have tried our best to explore different aspects of possible limitations. A more detailed discussion will be added in the revision.

1. Applying POT to graph-level GCL

   If the downstream task requires graph embeddings, POT still stands. First, related concepts like "graph compactness" can be defined similarly to node compactness. Second, the pooling operators like "MEAN", "SUM", and "MAX" are linear, therefore the form of "graph compactness" can be derived with some modifications on the steps in Appendix A.2.

2. The limitation on the network structure of the encoder

   Definition 5 and Theorem 2 are based on the assumption that the encoder is GCN since GCN is the most common choice in GCL. However, other encoders are possible to be equipped with POT. GraphSAGE[1] has a similar form to GCN, then the derivation steps are similar. For Graph Isomorphism Network[2] and its form is 
   $$
   h_v^{(k+1)}=\text{MLP}((1+\epsilon)h_v^{(k)}+\sum_{u\in \mathcal N(v)}h_u^{(k)}).
   $$
   We can first relax the nonlinear activation functions in MLP with Definition 5, then obtain the pre-activation bounds with Theorem 1, and finally follow the steps in Appendix A.2 to derive the form of node compactness when a GIN encoder is applied.

3. The provable training of feature augmentation

   In this paper, we focus on topology augmentations. However, as we have mentioned in the limitation, feature augmentation is also a common class of augmentations. We explore the provable training for feature augmentation as follows. Unlike topology augmentation, the augmented feature is only the input of the first layer, so it is easier to deal with. Inspired by [3], we can relax the discrete manipulation into $l$-1 constraints, then the node compactness is related to the feasible solution of the dual form. A similar binary cross-entropy loss can be designed. More detailed derivations are still working in progress.

However, more efforts are still to be made to deal with some subtle parts.

We greatly thank you again for the reviewers' precious time in reading our paper and rebuttal. We hope that the rebuttal phase can be informative and pleasant for all reviewers.   

References:

[1] Hamilton, Will, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs." Advances in neural information processing systems 30 (2017).

[2] Xu, Keyulu, et al. "How powerful are graph neural networks?." arXiv preprint arXiv:1810.00826 (2018).

[3] Zügner, Daniel, and Stephan Günnemann. "Certifiable robustness and robust training for graph convolutional networks." Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.

Meta-review: The paper studies the node properties given different graph augmentations in graph contrastive learning. The paper presents a solid idea and nice presentation. All the reviewers agree to accept this paper.
Decision: Accept (spotlight)