Calibrating and Improving Graph Contrastive Learning
Authors: MA KAILI
Garry YANG
Han Yang
Yongqiang Chen
James Cheng
Venue: Accepted by TMLR ()

Abstract: Graph contrastive learning algorithms have demonstrated remarkable success in various applications such as node classification, link prediction, and graph clustering. However, in unsupervised graph contrastive learning, some contrastive pairs may contradict the truths in downstream tasks and thus the decrease of losses on these pairs undesirably harms the performance in the downstream tasks. To assess the discrepancy between the prediction and the ground-truth in the downstream tasks for these contrastive pairs, we adapt expected calibration error (ECE) to graph contrastive learning. The analysis of ECE motivates us to propose a novel regularization method, Contrast-Reg, to ensure that decreasing the contrastive loss leads to better performance in the downstream tasks. As a plug-in regularizer, Contrast-Reg effectively improves the performance of existing graph contrastive learning algorithms. We provide both theoretical and empirical results to demonstrate the effectiveness of Contrast-Reg in enhancing the generalizability of the Graph Neural Network (GNN) model and improving the performance of graph contrastive algorithms with different similarity definitions and encoder backbones across various downstream tasks.

Published in Transactions on Machine Learning Research (07/2023)
Calibrating and Improving Graph Contrastive Learning
Kaili Ma
klma Bcseeese. culkk edu.
Deportment of Computer Science and Engineering, The Chinese University of Hong Kong
Garry Yang"
beyang@cse.cuhk.. edu.
Department of Compuler Science and Engineering, The Chinese University of Hong Kong
Han Yang
hyang cuhk. edu.hk
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Yongqiang Chen
yychen Desc. culkk edu.hk
Department of Computer Science and Engineering, The Chinese University of Hong Kong
James Cheng
jcheng Besee cuhk, edu. hk
Deporiment Compuler Science and Engineering, The Chinese University of Hong Kong
These authors contribuled equally to this work.
Reviewed on OpenReview: https: /t opw.reveen........ net/ per/form?? id= LdSSPccc
Abstract
Graph contrastive learning algorithms have demonstrated remarkable success in various ap- plications such as node classification, link prediction, and graph clustering. However, in unsupervised graph contrastive learning, some contrastive pairs may contradict the truths in downstream lasks and thus the decrease of losses on these pairs undesirably harms the performance in the downstream tasks. To assess the discrepancy between the prediction and the ground-truth in the downstream tasks for these contrastive pairs, we adapt expected calibration error (ECE) to graph contrastive learning. The analysis of ECE motivates us to propose novel regularization method, Contrast-Reg, to ensure that decreasing the contrastive loss leads to better performance in the downstream tasks. As plug-in reg- ularizer, Contrast-Rog effectively improves the performance of existing graph contrastive learning algorithms. We provide both theoretical and empirical results to demonstrale the effectiveness of Contrast-Ree in enhancing the generalizability of the Graph Neural Network (GNN) model and improving the performance graph contrastive angs with different similarity definitions and encoder backbones across various downstream tasks.
1 Introduction
Graph structures are widely used to capture abundant information, such as hierarchical configurations and community structures, present in data from various domains like social networks, e-commerce networks, knowledge graphs, the World Wide Web, and semantic webs. By incorporating graph topology along with node and edge attributes into machine learning frameworks, graph representation learning has demonstrated remarkable success numerous essential applications, such as node classification, link prediction, and graph clustering. Graph contrastive learning has emerged as an effective method for learning graph representations.
including algorithms such DGT (Velickovie al. 2019 GMT (Peng et al. 2020), GCC QQuu al.) 2020

---

Published in Transactions on Machine Learning Research (07/2023)
and PyGCL Zhuu al. 2021a). These algorithms use the noise contrastive estimation loss (NCEloss) to contrast the similarities of similar (or positive) node pairs against those of negative pairs. The algorithms differ in their definition of node similarity, hence the design of contrastive pairs. The design of the encoder
backbone can vary from Graph Neural Networks (GNNs) (Kipf & Welling) 2017: Hamilton et al., 2017
Velickovie et al. 2018; Xu et al. 2019 to skip-gram based model (Tang et al. 2015 Perozii el. al. 2014
Grover & Leskovee 2016). In this paper; we focus on employing graph contrastive learning algorithms in an unsupervised learning manner and utilize GNNs as the encoder. The learned node embeddings are directly
delivered to the downstream tasks.
Although graph contrastive algorithms have demonstrated strong performance in some downstream tasks, we have discovered that directly applying contrastive pairs and GNN models to new tasks or data is not always effective (as shown in Section 6). Nodes with different ground-truth labels can be selected as positive pairs during unsupervised training. Contrastive models that solely minimize the NCE loss can be misled by these pairs and learn certain spurious features that decrease the loss but are detrimental to downstream lasks. To address this issue, we adapt expected calibration error (ECE) to graph contrastive learning to assess the discrepancy between the predicted probability and the ground-truth in downstream tasks for the selected contrastive pairs. High ECE values indicate mis-calibration of the model. We identify two factors that contribute to the model's mis- calbbraiib:::o::: (a) the expectation of the prediction probability for randomly sampled pairs, B(v, (h, )), and (b) the probability gt of v4 sharing the same label as o in positive sampling. To address the mis-calibration in existing graph contrastive learning algorithms, we introduce a novel regularization method, denoted as Contrast-Reg. Contrast-Ree employs a regularization vector r, which consists of random vector with each entry within the range 10, By ensuring node representa- tions maintain similarity with and that pscudo-negative reprosentations, generated through shuffled node features, remain dissimilar to Contrast-Reg guarantees that minimizing the contrastive loss results in high- quality representations that improve accuracy in downstream tasks, rather than overfitting specific spurious features. We provide both theoretical evidence and empirical experiments to support the effectiveness of Contrast-Reg, First, we derive a generalization bound for our contrastive GNN framework, building upon the theoretical framework depending on Rademacher complexity (Saunshi et al., 2019), and demonstrate that Contrast-Reg Reg contributes to decrease in the upper bound. This result indicates that this term promotes better alignment with the performance of downstream tasks while simultancously minimizing the training loss, thereby improving the generalizability of the GNN model. Furthermore, we design experiments to ex- amine the empirical performance of Contrast-Reg Rerrastt-Rggaae by formulating the graph contrastive learning framework into four components: similarity definition, a GNN encoder, a contrastive loss function, and a downstream task. We apply Contrast-Reg to different compositions of these components and achieve superior results across various compositions.
The main contributions of this paper can be summarized as follows:
(Section 4.1) We adapt expected calibration error (ECE) to assess the discrepancy between the prediction and the ground-truth in the downstream tasks on contrastive pairs, and identify two key factors that influence the discrepancy.
(Section 4.2) We propose a novel regularization method, Contrast-Reg, to ensure that minimizing the con- trastive loss results in high-quality representations and improved accuracy in downstream tasks. Contrast- Reg plugin regularizer generally effective with respect to various graph contrastive learnings.
We provide both theoretical results and empirical results to demon- strate the effectiveness of Contrast- -eg in improving the generalizability of the GNN model and achieving superior performance across different existing graph contrastive learning algorithms.
(Section 4.2 & Section 5 & Section 6)
2
Related Work
Graph representation learning. Many graph representation learning models have been proposed.
Factorization- based models (Ahmed et al.) 2013 Cao et al., 22055] Qiu et al.) 2018) factorize an adjacency matrix to obtain node representations. Random walk-based models such as DeepWalk (Perozzi et al. 2014)
2

---

Published in Transactions on Machine Learning Research (07/2023)
sample node sequences as the imput to skip-gram models to compute the representation for each node. Node2vec (Grover & Leskovec, 2016] balances depth-first and breadth-first random walk when it samples node sequences. HARP (Chen et al. 2018) compresses nodes into super-nodes to obtain a hierarchical
graph to provide hicrarchical information to random walk. GNN models (Kipf & Welling 2017 Hamilton
et al. 2017 Velickovic el. al. 2018: Xu el al. 2019 Qu el al. 2019 Thomas et al.] 2023) have shown great capability in capturing both graph topology and node/edge feature information. Most GNN models fol-
low neighborhood aggregation schema, in which each node receives and aggregates the information from its neighbors in each GNN layer, ie., for the k-th layer, A aggregate(h,) .j neighborhood(i). and
A = combine(h, )) This work employs GNN models as the backbone and tests the representation across various downstream tasks, such as node classification, link prediction, and graph clustering.
Graph contrastive learning. Contrastive learning is self-supervised learning method that learns rep- resentations by contrasting positive pairs against negative pairs. Contrastive pairs can be constructed in various ways for different types of data and tasks, such as multi-view (Tian et al. 2020; 2019).
target-to-
noise (van den Oord et al.] 2018 Hénaff et al.
2019 mutual information (Belghaii et al.]
2018
Hjelm
ct al. 2019), instance discrimination (Wu et al. 2018/, context co-occurrence (Mikolov et al.
2013
clus-
tering (Asano et al.] 2020; Caron et al., 2018), multiple data augmentation (Chen et al. 2020).
known and
novel pairs (Sun & Li 2023), and contextually relevant (Neelakantan et al. 2022). Contrastive learning has
been successfulyy applied to numerous graph representation learning models (Velickovie et al.,
2019 Peng
et al. 2020 You et al. 2020 Qiu et al. 2020: Zeng et al. 2021] to pseudo subgraph instance discrimination
as a contrastive learning training objective and to leverage rontrastive learning to empower graph neural networks in learning node representations. We characterize different types of node-level similarity as follows:
Structural similarity: Structural similarity can be captured from various perspectives. From a graph theory viewpoint, GraphWave (Donnat et al.] 2018) leverages the diffusion of spectral graph wavelets to capture structural similarity, while struc2vec (Ribeiro et al. 2017 uses hierarchy to measure node similarity at different scales. From an induced subgraph perspective, GCC (Qiu et al.. 2020) treats the induced subgraphs of the same ego network as similar pairs and those from different ego networks as dissimilar pairs. To capture community structure, vGraph (Sun et al. 2019) utilizes the high correla- tion between communily delection and node representations to incorporate more community structure information into node representations. To capture global-local structure, DGI (Velickovie et al., 2019) maximizes the mutual information between node representations and graph representations to allow node representations to contain more global information. GDCL (Zhao et al. 2021 incorporates the results of graph clustering to decrease the false-negative samples. DIGCT, (Tong et al. 2021) generates rast pairs by Laplacian perturbations to retain more structural features of directed graphs. GCA (Zhu et al. 2021b) constructs contrastive pairs by designing adaptive augmentation schemes based on node contral- ity measures. AD-GCL (Suresh et al. 2021) adopts trainable edge-dropping graph augmentation and optimizes both adversarial graph augmentation strategies and contrastive objectives to avoid the model learning redundant graph features.
Attribute similarity: Nodes with similar attributes are likely to have similar representations. GMI (Peng et al. 2020) maximizes the mutual information between node attributes and high-level repre- sentations, and Pretrain GNN (Hu et al. 2020b) applies attribute masking to help capture domain-specific knowledge. GCA (Zhu et al.] 2021b) corrupts node features by adding more noise to unimportant node features, to enforce the model to recognize underlying semantic information.
Given the above subgraph instance discrimination objective with GNN backbones, NCEloss Gutmaan & Hyvärinen 2012 Dyer 2014 Mnih & Teh 2012 Yang et al. 2020) is applied to optimize the model's param- eters. In addition, Graph Autoencoder, which is another popular graph self-supervised approach by recon- structing useful graph information, has also been extensively studied. For example, GraphMAE (Hou et al., 2022) focuses on feature reconstruction with a masking strategy and scaled cosine crror. GraphMAE2 (Hou) et al. 2023) designs strategies of multi-view random re-mask decoding and latent representation prediction to regularize the reconstruction process. S2GAE (Tan et al. 2023) randomly masks portion of edges and
3

---

Published in Transactions on Machine Learning Research (07/2023)
learns to reconstruct these missing edges with novel masking strategy. SeeGera Li et al. 2023 adopts novel hierarchical variational framework.
Numerous studies have demonstrated the success of enhancing a model's generalizability by devising ad- vanced similarity functions. However, some designs may require extensive tuning, preventing these advanced techniques from adapting to settings beyond the scope of their experiments. This problem is especially prevalent in the unsupervised learning setting, where the ideal protocol is that the learned node embeddings, which are the output of the unsupervised contrastive model, should be applicable to downstream tasks upon convergence. The key difference between Contrast-Reg and other algorithms, such as GCA, GDCL, and DiGCL, lies in the fact that the latter methods are intended to incorporate structures that are critical to the performance of the downstream tasks, while Contrast- ensures that minimizing the contrastive loss results in high-quality representations that enhance the accuracy in downstream tasks. Moreover, Contrast- Reg can naturally function as a plugin to these advanced graph contrastive learning algorithms to improve their performance.
Expected Calibration Error. Expected Calibration Error (ECE) (Guo et al. 2017) is metric employed to quantify the calibration between confidence (largest predicted probability) and accuracy in a model. Calibration refers to the consistency between a model's predicted probabilities and the actual outcomes. When a model mis-calibrated, its generalization to unseen data in supervised learning lasks likely to be poor (uüller et a 2019 Pereyra et al. [2017] Guo et al.) 2017 Zhang et al.) (018)). We propose using ECE to evaluate the quality of node embeddings generated by unsupervised graph contrastive learning models. This calibration offers insights into addressing the challenge that applying graph contrastive learning algorithms to downstream tasks does not always yield optimal results.
Rogularization for graph representation learning. GraphAT (Feng et al., 2019 and BVAT (Deng et al. 2019) introduce adversarial perturbations of to the input data x as regularizers to obtain more robust models. GraphSGAN (Ding et al. 2018) generates fake input data in low-density regions by incorporating generative adversarial network as regularizer. P-reg (Yang et al. 2021) leverages the smoothness property in real-world graphs to enhance GNN models. Graphnorm (Cai et al. 2021 proposes a novel feature normalization method. ALS (Zhou et al. 2021 employs label propagation lo adaplively integrate label smoothing into GNN training. G-Mixup (Han et al. 2022
uses graphons as a surrogate to apply mixup
techniques to graph data.
The above regularizers are designed for general representation generalizability, while Contrast-Ree is specif- ically intended to address the mis-calibration problem in the unsupervised graph contrastive learning opti- mization process and its performance downstream tasks. It is worth noting that Contrast-Reg could be used in conjunction with the aforementioned regularization techniques.
3 Preliminaries
We begin by introducing the concepts and foundations of graph contrastive learning (GCL). Let a graph G (V,E) be denoted, where V U1, U2....,, 2nt and È represent the vertex set and edge set of G, and the node feature vector of node 2; be I;. Our objective is to learn node embeddings through unsupervised graph contrastive learning and subsequently apply simple classifiers leveraging these embeddings for various downstream tasks, such as node classification, link prediction, and graph clustering.
Graph contrastive learning Given graph G with node features X = (21, (2,, .2,... .. contrastive learning is to train encoder f (G - Rd for all input data points o; E V with node feature vector I; by constructing positive pairs (2,, and negative pairs (u,,",
.n), the aim of graph
" ... .(x)).
The encoder f is typically implemented using Graph Neural Networks (GNNs). Specifically, let h, represent the output embedding of the encoder f for node 0,, (k) the embedding at the k-th layer, and aς Iz.
4

---

Published in Transactions on Machine Learning Research (07 (07/2023) /023)
The output of the encoder f is then iteratively defined as:
m (k) = A ggregatez (f oy E EV(us)))
(1)
A = RELU (w* - Update (mm )
where (N;)) the set of nodes adjacent to Ui and Aggrogate and Update are the aggregation and update function of GNNs Giimmrr et al. 2017). h; is the last layer of (( for node vi-
Leveraging various types of similarity pseudo subgraph instance discrimination labels, graph contrastive learning constructs positive and negative pairs to train the embedding hę by optimizing the loss on these pairs. The most commonly employed loss is the NCEloss:
M
K
Ince
Σ
- log (h)
+ + log o (hT
(2)
M
M with M samples (1,0t Mir "* ,add 1=1 in empirical setting where a(.) is the sigmoid function.
Calibrating graph contrastive learning by the expected calibration error (ECE) Expected Cal- ibration error measures the degree which the model output probabilities match ground-truth accuracy in supervised tasks (Nacini et al. 2015 Guo et al.) 2017). It's defined as the expectation of absolute difference between the largest predicted probability (confidence) and its corresponding accuracy,
ECE = Es ll e²) - acc(o,
(3)
In this paper, we extend the use of ECE to evaluate the quality of graph contrastive learning. Specifically, we can compare the predicted probability of a positive pair (i.e., a pair of nodes with the same label) with the true probability that the pair belongs to the same class. We can also compare the predicted probability of negative pair (i.c., a pair of nodes with different labels) with the true probability that the pair belongs to different classes. By calculating the differences between the predicted and true probabilities for both positive and negative pairs, improvement. The formal definition is presented as follows. The largest predicted probability, p(u, v"), is determined as
quantify the overall mis-calibration of the model and identify areas for
p(u, = { ohh hy), ali hols
(v, v') as positive pair (v, v/) negative pair
(4)
where ftp and hy are the embeddings for the target node o and the selected sample v', respectively, and a(-) is the sigmoid function. The corresponding accuracy, acc(v, o'), is defined as follows:
aco(v, 0') { I(v, 1- 1', (", as negative pair
(v,v²) positive pair
where Il is an indicator function denoting whether and v' has the same label, the positive/negatee pairs are pseudo-labels for training the contrastive learning algorithm which may not equal to the true label. In this case, when two nodes are selected as positive pairs, ace(t, e') is equal to 1 if e' and v belong to the same class and equal to 0 otherwise; when the two nodes are selected as negative pairs, acc(v, = 1 - 1-l(,, e').
Using the ECE metric in this way allows us to evaluate the quality of the embeddings outputted by the model (a(h,r- h)))) and their accuracy in downstream tasks (ace(v, t")), such as node classification. We can improve the general performance and utility of graph contrastive learning algorithms by detecting regions of mis-calibration and developing novel techniques for enhancing calibration performance.
5

---

Published in Transactions on Machine Learning Research (07/2022 2022)
1.40
0.84
Positive sampling Accuracy q²
0.6
ECE
0.5
NCELoss
L vD]
NCELoss Loss
Enwnla(h h,)
0.70
0.5
0.82
0.4
0.35
0.80
0.3
50
100
150
200
250
100
150
200
250
Epoch
Epoch
(a) NCEloss and (o h.r)] over epochs
(b) ECE and qt over epochs
Figure 1: Calibrating Graph Contrastive Learning (T.C (Alg.
w/o Contrast-Reg on the Pubmed dataset)
4 Methodology
To calibrate the model, we first adapt the expected calibration error (ECE) formula for the graph contrastive learning setting (Section 4.1h. h. In order to ensure that minimizing the contrastive loss leads to high-quality representations that improve accuracy downstream tasks, we propose a regularization term designed lower the ECE value and enhance the model's generalizability (Section 4.2g We also provide theoretical evidence to support the effectiveness of the proposed regularization term.
4.1 Empirical Calibration Reveals Limitations of Existing Graph Contrastive Learning Algorithms
To calibrate the existing graph contrastive learning algorithms, we measure the degree of calibration using the expected calibration error (ECF) metric, which is defined by Equation
ECE aCt=rt- (1- (11- v441) a*
(brue posilive)
Execlar'' )=oop(e, (4)1 (1- σ-)
(false positive)
(6)
+r- (Baneew
(false negative)
+ ([-Baadoww (1- - (true negative),
where a- and q are the probabilities that the node v has the same label as node v in positive and negative sampling, respectively; r+ and r are the ratios of sampling positive and negative samples, with + +r- 1. In this study, we set r+ -- = 0.5.
Building upon this formulation, we propose the following claim that takes into account the positive and neg- ative pair construction assumptions to analyze the potential issues that lead to the mis-calibration between the decrease in graph contrastive learning training loss and the degradation of downstream task performance.
Claim 4.1. Under the assumption that negative sampling is uniformly sampled, and positive sampling is sampled based on the caleulated dislance belween pairwise embeddings, ECE is posilively correlated with the expectation of the prediction value for randomly sampled pairs Ee,y' her and negatively correlated with the probability qt of v'4 having the same label as v in positive sampling.
We provide a thorough analysis of this claim in Appendix A.1 To investigate the changes in these two factors and the ECE value over the process of minimizing the NCEloss (Equation 2 conduct illustrative

---

Published in Transactions on Machine Learning Research (07/2023)
experiment with an existing graph contrastive learning algorithm and present the relevant values in Figure 1 In Figure Ta we show that as the NCFloss (red solid line) is minimized over the epochs, the expectation of the prediction value for randomly sampled pairs E(v, (A)("(A, (blue dashed line) increases. Moreover, Figure 1b demonstrates the model's challenge in identifying genuine positive pairs, with the probability q² initially increasing before gradually declining (red solid line), and the ECE value first decreasing before rising (blue dashed line). These findings suggest that, as the epochs progress, merely reducing the NCEloss is insufficient to enhance the accuracy of downstream tasks. Our empirical calibration shows that the model learns certain spurious features that reduce the loss but are ultimately harmful to downstream tasks when solely minimizing the NCEloss. The above analysis emphasizes the need for graph contrastive learning algorithms to effectively quantify the relationships between learned embeddings and the accuracy of downstream tasks. In the next section, we present our approach to miligate the possible risks associated with spurious feature learning in graph contrastive learning algorithms and show its effectiveness through a number of experiments.
4.2 Proposed Regularization Term: Contrast-Res Reg
To ensure that minimizing the NCEloss aligns with downstream task accuracy, we propose a contrastive regularization term, denoted as Contrast-Reg, given by:
Lreg= = E (h, Wr)) + logo(-h[[wr) h.h
where r is a random vector uniformly sampled from (0, 1], W a trainable parameter, and the noisy fea- ture generated by different data augmentation techniques, such as those used in the previous literature (Chen et al. 2020 Velickovic et al. 2019). In Section [ we will discuss how we calculate the noisy features in the GNN setting. In the following, we will introduce the impact of Contrast-Reg the ECE value and the generalizability of the GNN model.
ECE decreases by incorporating Contrast-Reg In Claim 4.1 and Appendix A.1, it is proven that the ECE value is positively correlated with E(v, (h,,, h,))] and inversely correlated with g². In addition, Theorem 2 in Appendix A.3 shows that Contrast-Reg reduces the variance of the learned node embeddings norm ||b|], thereby preventing the loss from docrcasing due to exploding embedding norms. As a result, the norm values are lower than those obtained with the vanilla contrastive loss, leading to a reduction in E(v, (ho,, ]] and an increase in representation quality. With the improvement in the representation quality, B(u, (h), ]] decreases and gt incrcases, resulting in a decreased ECE value. Furthermore, we conducted an empirical study to examine the impact of Contrast-Reg on the ECE value and investigate the two factors that cause miscalibration. Figure 2a shows that the expectation of the prediction value for randomly sampled pairs (o,,, ) with Contrast-Reg increased much more slowly compared the red solid line). Figure 2b presents the changes
to the vanilla NCEloss (green solid line compared in positive sampling accuracy qt over the epochs of the vanilla NCEloss and NCEloss with Contrast-Reg, where Contrast-Reg helps q+ increase, while q+ trained by vanilla NCEloss decreased after the initial in- creases. These two factors contribute to the different ECE changes in the vanilla NCEloss and NCEloss with Contrast-Reg. The red dashed line indicates that the ECE value increases after the initial decreases, while the green dashed line shows that the ECE value decreases slightly. The comparison demonstrates that applying Contrast-Ri Renrr alleviates the miscalibration in reprosentation learning, ensuring that minimizing the contrastive loss results in high-quality attossentations with increased accuracy in downstream tasks, rather than overfitting certain spurious features. We provide detailed comparison of the impact on the ECE value between models with and without Contrast-Reg in Appendix A.2 across different datasets.
Generalizability improved by incorporating Contrast-Reg In Section 6.3 we present empirical ev- idence supporting the effectiveness of Contrast-Rog's ability to enhance the generalizability of the GNN model through an ablation study. Furthermore, we analyze the impact of Contrast-Rey on the generaliz- ability of graph contrastive learning algorithms using the Rademacher complexity (Saunshi et al. 2019). In Theorem [ we offer performance guarantecs for the learned graph embeddings outputted by the GNN function class F = f with the unsupervised loss function Luce on the downstream average classification task (f). Detailed settings can be found in Appendix A.4 Assume that ʃ is bounded, ie., ||,,|| < R
7

---

Published in Transactions on Machine Learning Research (07 (222)
1
0.50
0.50
0.50
12:04
Gaad MUL wib
5,00
Eroo, Pil wirnnng
1.. v/]
with
8.75
Foullefk 4,21 mol
0..00
KC:04
4.00
ECE wro
ECE wio reg
q'
reg
9.03
0.52
0.92
BCB reg
0.32
1E+84
2,00
ECE with
50
100
1.50
300
2.5
100
150
200
250
50
150
150
200
250
Spoch
Epoch
Ppoch
(a) Infiuence Contrast-Rea on ECE and B (orar) (h (h h
(b) Influence of Contrast- Reg on ECE and 9
Inffuence of Contrast- Reg on (c)
mmax (M(f, c)) and Ee,-D.Ilh.l]
Figure 2: Effects of Contrast- Reg (I.C (Alg. W/ & w/o Contrast-Reg on Pubmed)
with R > O. Let C, be two classes sampled independently from latent classes with distribution p. Let 7 = Ber'spill (c = d') be the probability that and e' come from the same class. Let L be the NCEloss when negative samples come from different classes. We have the following theorem.
Theorem 1. Vf F, with probobility least 1 1-
D' (f) S Ltt (f) BB({f) n/Gnss
(8)
where Genar (RR 8 Blog(o( /
log 1 2M
0
R (R IFV log 1
3 1- I- and s(f) =
4v ((wangiiDaammtv..) h.
In Equation 8 Genu represents the generalization error in terms Rademacher complexity and will converge 0 when the encoder function f is bounded and the number of samples M is sufficiently large. The theorem above indicates that only when Bs(f) + G converges as M increases, will the encoder f = arg min selected perform well in downstream tasks.
Next, will analyze the impact of Contrast-Reg on the condition in the aforementioned theorem, Bs(s)
Gens, by reformulating s(f) follows:
sf) -4
[ha hi hi] / Eawp [BENDD [hffEE, Ear, DD [ha hi]l
Say Bowp [IM(S,c)le B 11
where M(J,))= = =u, [/ah]]
The advantage of incorporating Contrast-Reg into graph contrastive learning lies in its ability to reduce both the largest singular value of matrix M(f.c) c) (omax (M c))) and the expectation of the embedding norm within the same class, Be,aD..llbaal" (as illustrated in Figure 2cp. This reduction leads to decrease in the upper bound of s(f), ultimately yiclding lower value for the term Bs(f) + +rGens compared to vanilla graph contrastive learning. The reduction in this term promotes better alignment with the performance of downstream tasks while simultaneously minimizing the training loss. Further experiments on the gener- alizability of the Contrast-Reg approach can be found Section 6.3. and more detailed explanation on lowering the term s(f) is provided in Appendix A.3 A.3
5 A Contrastive GNN Framework
Algorithm I presents the graph contrastive learning framework and how Contrast-Ree plugged into the framework. The framework employs GNN model, such GCN (Kipf & Welling 2017), GAT (Velickovic

---

Published in Transactions on Machine Learning Research (07 (023))
al. 2018 and GIN [Xu et al. 2019); to obtain node embeddings. To train the parameters of the GNN backbone, we generale contrastive pairs using the functions SeedSelect and Contrast. In addition, we incorporate the Contrast-Reg term into the optimization process, along with the contrastive loss on these pairs. After the model convergence, the embeddings are directly delivered to the downstream tasks.
Algorithm 1: Graph Contrastive Learning Framework
Input: Craph g (V,E), node attributes X, a GNN model f V. -> RR the number of epochs e; Output: A trained GNN model Initialize training parameters;
for epoch to do (- X. f, epoch);
3
P=Contrast(C, 9, X, f);
5 loss = NCEloss(P) + Contrast-Reg(S, X, f);
Back-propagation and update f;
end
The functions SeedSelect and Contrast are responsible for selecting the seed nodes and sampling the posi- tive/negative pairs for these sceds while incorporating various priors for both structural and attributc aspects of the graph. To ralustrate the graph contrastive learning framework, utilize two simple graph contrastive learning algorithms (ML and LC).
LC: Structural similarity We adopt clustering methods to detect communities in a graph and generate positive/negall pairs the node representation space (Newman 2006). The SeedSelect function implemented using curriculum learning, following the design of AND (Huang et al., 2019). Initially, SeedSelect utilizes node embeddings to select node set C with low entropy, re- ducing randomness and uncertainty during carly training stages. As training progresses, SeedSelect gradually expands C by adding more nodes. For each node x; in C, Contrast generates a positive node oet that is highly similar, and a randomly sampled negative node x7, returning a tuple of their representations: {(f(x)) f(x; ( f(,)) )) 2.E0'
ML: Attribute similarity In MI., we assume that nodes with similar attributes should have similar representations to preserve the attribute information. Following the design of DIM (Hjelm) lt al. 2019 and GMI (Peng et al. 2020), we adopt multi-level representation approach. Initially, SeedSelect includes all nodes in the node set G. For each seed node 24, Contrast uses the node itself as the positive node and randomly samples a negative node. The positive representation of the seed node x; is generated by adding an additional GNN layer upon J, denoted as g. The tuple containing the representations is denoted as {(f(x;) g(zs), g(f(=)).g(z)) f(x))) ))...
Advanced graph contrastive learning algorithms can also be easily implemented using this framework. As an example, Graph Contrastive Analysis (GCA) (Zhu et al.) 2021b) algorithm can be implemented by making a simple modification to the Contrast function found in Appendix B Overall, Contrast-Reg serves as a highly effective plugin regularizer for graph contrastive learning with various backbones, and with different Contrast and SeedSelect implementations.
6 Experimental Results
We begin by introducing the experimental scttings in Scction 6.1 Scction presents the main results across various downstream tasks. Moreover, we assess the benefits of Contrast- through ablation studies.
6.1 Experiment Settings
Downstream tasks We conduct our experiments on three distinct downstream tasks, namely node clas- sification, graph clustoring, and link prediction. The experimental procodure consists of two stages: first, we utilize positive and negative contrastive pairs to train the GNN models in an unsupervised manner, obtaining the node embeddings. Subsequently, we apply these embeddings to the ream tasks by integrating
9

---

Published in Transactions on Machine Learning Research (07/2023)
Table 1: Downstream task: node classification
Algoritho
Contrast-Io Reg
Cora
Citescer
Pubmed
Wiki
Computere
Photo
ogbv-arxiv
oghn-products
Reddie
GCN
81.5iauuu
71.25ac.ur
79.2640 as
72.40amm
70. 82
88. 88.75
71.74
75.01z021
91.02gum
71 0
17:37acmu
66.31g1 as
58. 70.7
75. 19
83-821 as
70.07=018
72.48ka to
93 26znn
DGL
S1 1..10.04
76.8910.55
63.7013.45
64 1.00
77. 19.2.00
09 0610011
77.00 77.0010.22
94.1410.03
GMI
50.0 50.9Gaso.s
77.97
63.35
79.27 L.0
87. 67.0641.2
68. 38.3644.1
76.56aam
94.194004
GCA
82.51
70.8320 on
85.09
70.38%21
87 17:0
92. 07 =1.0
0OM
00M
00M
CrophMAE
14,14.00.5
73.0610.31
50,98.10.4
77.40.0.16
80.77
88,93 11.58
714471077
0OM
00M
GCA
8S3 633.9022 m
72.30am as
87.00kg no
77.71 os
88. 21.
933. 13k s0
GOM
0OM
0OM
GoopMME
14.1810..0
19.52.0.32
51.43.1.44
78.22..0.3
S1. 11.1611130
90.71 11.20
71.66.0.19
OOM
0OM
Le
62.33
22.88
79.55
60. 10..9-4
81 1:0
87 87.50
60 10.9
76.96
94.48ac
ML
82 22.63:...00
7240880041
80.1011
07.20230.00
82:11:1.47
86 7843-77
70.05.20.0
76 16.2772030
30.3880000
Table 2: Downstream task: graph clustering
Algoridhm
Couteast-Reg
Cocs
Citesser
Wiki
Acc
NMI
Fl
NMI
Acc
NMI
node2vee
61 61.78.0330
44.47::0:11
62.65.0000 26
30.58:20337
24.23
37. 37
43:29110.88
37.30ao..0
30.00 51
DGI
54.90+:0.66
69.88
68 6.44077
43.75+0.50
64.64:0.41
44.37=0..2
42.20
40.16:20 72
AGC
68. 68.93:20.02
53.72+0.04
63.62=0.01
68.37=0002
12. 12.40
63, 63.73:00.22
19.5/140.07
47.02=0.00
42. 12:16:0.11
GMI
63.4423.18
50.3331.48
02:21
63. 03.76st
38.14
00.23
42.81
41.53a..0
LC
<
70.01=2.04
65.0840.75
67. 67.36:2..1
67. 0.7.007777
43.63+0.57
61.21:0.00
50.12+0.96
49.70=0.40
49.71==0.57
ML
71.59:1.07
56.01 20.64
68. 11
69.1740.43
44.47:u0.6
64.74420.1
53.18 ot
46.1140.03 61.81
additional straightforward models. For example, employ multiclass logistic regression for the node clas- sification, k-means for graph clustering, and single MLP layer for link prediction. Moreover, we conduct experiments in the protrain-finctune paradigm, as this approach constitutes significant component of graph contrastive learning (Qiu et al., 2020). We first employ a large graph to train the GNN models, followed by finetuning such models and train a simple downstream classifier on a separate graph.
Training details The datasets we employ encompass citation networks, web graphs, co-purchase networks, and social networks. Comprchensive statistics for these datasets can be found in Appendix D For Cora, Citeseer, Pubmed, ogbn-arxiv, ogbn-products, and Reddit, we adhere to the standard dataset splits and conduct 10 different runs with fixed random seeds ranging from 0 to 9. For Computers, Photo, and Wiki, we randomuly divide the train/van htt//vaiiaatio//eeee sets, allocating 20/30/ all remaining nodes per class, in accordance with the recommendations in the previous literature (Shchur et al. 2018). We measure performance across 25 (5x5) different runs, comprising random splits and fixed-soed runs (from 0 to 4) for each random split. The hyperparameter configurations can be found in Appendix D
6.2 Main Results
Our primary results involve comparing our proposed Contrast-Regs along with the chosen similarity defini- tions, against stato-of-the-art algorithms across various downstream tasks.
6.2.1 Node Classification
We evaluate node classification performance on all datasets, utilizing both full-batch training and stochastic mini-batch training. Our methods are compared with DGI (Velickovic et al. 2019), GMI (Peng et al. 2020). node2vec (Grover & Leskovee 2016), GCA (Zhu et al. 2021b), GraphMAE (Hou et al. 2022 and supervised GCN (Kipf & Welling) 2017). GCA, DGL, and GMI represent state-of-the-are algorithms in unsupervised graph contrastive learning. Node2vec is an exemplary algorithm for random walk-based graph represcntation algorithrs (Grover & Leskoved 2016 Tang el al.) 2015 Perozzi et al. 2014), while GCN is a classic semi- supervised GNN model. We incorporate the Contrast-Reg into ML, LC, GCA and GraphMAE models and compare them against the bascline models. The results, presented Table [ demonstrate that GCA and GraphMAE with Contrast-Ree achieve excellent performance across all the datasets that are trained in the full-batch mode and even surpass the performance of the supervised GCN.
10

---

Published in Transactions on Machine Learning Research (07/2023)
Table 3: Downstream task: link prediction
Algorithm
Contrast-Rec Reg
Cora
Citeseer
Pubmed
Wiki
GCN-neg
92.40=0.51
92.27=0
07.24
93.27=0.31
node2vec
86.33=0.87
79.60=1.b6 .88
81.74
92.41
DGI
93.62=0.98
95.03=1.73
97.24
95.55+0.33
GMI
91.31=0.88
92.23
95.14+0.25
95.30++0.29
ML-GGN
94.81 20.55
96.38-10.60
92.86110.26
89.84110.99
GRACE
0..8
93.14.0..
96.05:10.91
87.72.1..16
LC
94.61=0.61
95,63=0.0m
97.26++0.15
96.28+00.1
ML-GCN
95.18 10.31
96.83
95.10.10.2
92.70110.56
GRACE
/
93.60
93.2410.62
96.60.1..66
90.82.10.99
Table 4: Pretraining
Algorithm
Contrast-Ree
Reddit
oghn-products
No pretraining
90.44+1.62
84.69=0.79
DGI
92.0911.00
86.3710.19
GMI
92.13.1.16
86.1410.16
ML
92. 08+0.77
86.28=0.20
LC
92.52+0.55
86.45=0.13
6.2.2 Graph Clustering
We assess clustering performance using three metrics: accuracy (Acc), normalized mutual information (NMI). and F1-macro (F1), following the previous literature (Xia et al. 2014). Higher values indicate better clus- tering performance. We compare our methods with DGI, node2vec, GMI, and AGC (Zhang et al. 2019) on the Cora, Citeseer, and Wiki datasets. AGC is a -fate-of-the-art graph clustering algorithm that leverages high-order graph convolution for attribute graph clustering. For all models and datasets, we employ k-moans to cluster both the labels and representations of nodes. The clustering results of labels are considered as the ground truth. To reduce dimensionality, we apply PCA to the representations before using k-means, since high dimensionality can negatively impact clustering (Chen 2018). The random seed setting for model training is consistent with that in the node classification task. To minimize randomness, we set the clustering random seed from 0 to 4 and compute the average result. for each learned representation. Table 2 presents improved results with and without PCA for each cell. Our algorithms, particularly ours (ML), exhibit su- perior performance in all cases, demonstrating the effectiveness of Contrast-Reg, It worth noting that the superior results of ours (ML) compared to ours (LC) suggest that attributes play a crucial role in clustering, as graph clustering is applied to attribute graphs.
6.2.3 Link Prediction
In order to circumvent the data linkage issue in link prediction, we employ an inductive setting for graph representation learning. We randomly extract induced subgraphs (comprising 85% of the edges) from each original graph for training both the representation learning model and the link predictor, while reserving the remaining edges for validation and testing (10% for the test edge set and 5% for the validation edge set). We assess performance across 25 (5x5) different runs, utilizing fixed-seed random split scheme with five distinct induced subgraphs and five fixed-seed runs (ranging from 0 to 4). We compare our results with the bascline algorithms, including DGI, GMI, node2vec, ML-GCN (Shiao et al. 2022), GRACE (Zhu et al. 2020), and insupervised GCN (GCN-neg in Table 3h. In addition, we incorporate Contrast-Reg into LC, ML-GCN, and GRACE against the aforementioned baselines. Our results, presented in Table 3] demonstrate that Contrast-Reg consistently improves the performance of graph contrastive lcarning models, as evidenced by comparing the results of ML-GCN and GRACE with and without Contrast-Roo Furthermore, we achieve the state-of-the-art results with the algorithms incorporating Contrast-Reg.
11

---

Published in Transactions on Machine Learning Research (07/2023)
Table 5: Graph contrastive learning with regularization
Algorithm
Regularization
Cora
Wiki
Computers
Reddit
ML
73.22=0077
1.55
77. 77.0842.48
94.33+0.07
ML
fz-normalization
80.14+0.92
61.83:1..80
80.80+1.44 1.45
94.07:0.18 19
ML
Weight-decay
81.65:+0.44
63.67+1147
79.09:t0.32
94.34410.06
ML
Contrast-Reg 82.65=10.57
67.20++0.96
82.11+1147
94.38:t0.01
LC
79.73:10.75
65.1411.44
79.80+1..4 1.49
94.42400.3
LC
eg-oormalization
81.09=0.50
63.96++0.62
80. 1.33
94.20++0.06
LC
Weight-decay 81.94+0.45 14
65.17+1131
81.89+1.58
94.44++0.03
LC
Contrast-Reg
82.3310.41
69.1911113
81.98
94.43310.03
6.2.4 Pretraining
We further assess the performance of Contrast-Reg in the context of the pretrain-finctune paradigm. For the Reddit dataset, we naturally partition the data by time, pretraining the models using the first 20 days. We generate an induced subgraph based on the pretraining nodes and divide the remaining data into three parts: the first part produce a new subgraph for funi-tuning the pre-trained model and training the classifier, while the second and third parts are designated for validation and testing. For the boon-prouucts dataset, we split the data according to node ID,, pretraining the models using subgraph generated by the initial 70% of the nodes. The data splitting scheme for the remaining data mirrors that of the Reddit datasct. We conduct baseline experiments encoder as in our model. Table | reveals that pretraining the model facilitates convergence to a more robust representation model with reduced variance, and Contrast- Regg can enhance the transferability of the pre-trained model.
DGI and GMI, employing the same GraphSAGE with CCN-aggregation
6.3 Discussion of Contrast-Reg
To evaluate the benefits of Contrast-Reg, we conduct experiments comparing it to two approaches, specif- ically, ?z-ormaaization and weight decay, four networks from different domains, with a focus node classification task performance. It is important to note that some regularization techniques, such as those mentioned in Section 2 are not explicitly designed to address the miscalibration problem. fz-normalivation (Chen et al. 2020) mitigates the potential risk of the expectation of the prediction value for randomly sampled pairs (., (v (lu.v)) o')] exploding by explicitly climinating the embedding norm for each node's embeddings to tackle the miscalibration problem, while weight decay strives to achieve the same result by implicitly restricting the gradient descent step length. Table 5 presents a comparison of the accuracy achieved by different contrastive learning algorithms, ML and LC, when incorporating fz-normalization, weight de- cay, and Contrast-Reg, fg-ormalization, weight decay, and Contrast-Reg into graph contrastive learning algorithms improves the accuracy of downstream tasks, suggesting that addressing miscalibration enhances the generalization of learned embeddings for downstream tasks. However, the performance gains provided by Contrast-Res ex- ceed those of lg lg-oormalization and weight decay. This implies that while alternative algorithms exist to address miscalibration, Contrast-Reg emerges as the most effective mothod for improving the gencralization of learned embeddings for downstream lasks. It is crucial to ackuowledge the existence of other algorithms that may also contribute to mitigating the miscalibration problem, and further research is needed to explore and compare their effectiveness.
opposed to using the vanilla algorithms. The results indicate that integrating
6.4 Generality of Contrast-Ree
The ablation study of Contrast-Reg on the GAT and GIN backbone is presented in Table 6 The results demonstrate that Contrast-Rees consistently enhances graph contrastive learning performance across various backbones and graph contrastive learning algorithms. This conclusion further supported by the comparison of various models, including GCA with CeetraCtttstttte in Table D GRACE with TRACE+CContras Reg, well as ML-GCN with MT-GCN+Contraan in Table These experiments support that Contrast-
12

---

Published in Transactions on Machine Learning Research (07/2023)
Table 6: GAT/GLN as an encode backbone w/ and w/o Contrast-
Algorithm
Backbone
Contrast-Ree Reg
Cora
Citeseer
Pubmed
Wiki
Computers
ML
GAT
76.90+1.20
70.43+0.31
75.05+0.51
69.02=1.89
78.47=2.60
ML
GAT
81.56:10.94
72.73+0044
78.50+0.63
69.41
80.41
T.C
GAT
74.30+1.10
69.3041042
72.5040.49
61.55-1.56
73.27=5.08
LC
GAT
10.87:10.96
72.6940.52
78.50+0.63
69.92
80.28:12.09
ML
GIN
77.78:10.88
70.7810.68
80.12:10.50
63.50
70.69
ML
GIN
81.04100.94
71.17:1045
80.23
66.77 10.53
77.8511.00
LC
GIN
80.2310.61
71.4610.44
78.1610.51
61.95
70.61:1.000
LC
GIN
81.38100.58
71.59:10.36
78.5110046
67.1410.44
76.79:1.91
Reg serves as an effective regularization term for graph contrastive learning algorithms that utilize different similarity definitions and GNN encoder backboncs. Furthermore, we have also conducted experiments on a graph autoencoder algorithm, GraphMAE (Hou et al., 2022), which is also graph self-supervised learn- ing. The empirical results presented in Table [ reveal that when combined with Contrast- GraphMAE achieves superior empirical performance, thus highlighting the potential benefits of Contrast-Reg for graph graph autoencoder algo-
autoencoder methods. A comprehensive analysis of the impact of Contrast-Ree rithms is an interesting direction and will be left as future work, which includes the theoretical investigations
and empirical evaluations involving broader range of graph autocncoder algorithms (Hou et al.
2022 2023
Tan et al. 2023
et al. 2023
7 Conclusions
We adapted expected calibration error (ECE) to the graph contrastive learning framework and identified the key factors that influence the discrepancy between the prediction unsupervised training and the accuracy in downstream tasks. Motivatod by ECE, we proposod a novel regularization regularizer, Contrast- Reg, to ensure (hat decreasing the contrastive loss leads to better performance in the downstream tasks. Our theoretical and empirical results both demonstrate the effectiveness of Contrast-Reg in improving the gencralizability of the base graph contrastive learning model and achicving superior performance across different existing graph contrastive learning algorithms.
References
Amr Ahmed, Nino Shervashidze, Shravan M. Narayanamurthy, Vanja Josifovski, and Alexander J. Smola. Distributed large-scale natural graph factorization. WWW '13, pp. 37 37-48, 2013.
Yuki M. Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultaneous clustering and representation learning. In ICLR 120, 2020.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, R. Devon Hjelm, and Aaron C. Courville. Mutual information neural estimation. In TCML '18, pp. 530-539, 2018.
Stephen P. Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2014. ISBN 978-0-521-83378-3 doi: 10.0017/C009978051180848 URL https::/webb.tttffffeeee ord. edu/X7Eboyd/ cvxbook/
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tin-Yan Liu, and Liwei Wang. Graphnorm: A principled approach to accelerating graph neural network training. In ICML '21, volume 139 of Proceedings of Machine Learning Research, pp. 1205-1215. PMLR, 2021.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In CIKM '15, pp. 891-900, 2015.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In ECCV '18, pp. 156, 2018.
13

---

Published in Transactions on Machine Learning Research (07/2023)
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. Harp: Hierarchical representation learning for networks. In (AAAT) '18, (TAAT) '18, and (FAAT) '1, pp. 2127-2134, 2018.
Lei Chen. Curse of dimensionality. In Encyclopedia of Database Systems, Second Edition. Springer, 2018. doi: 10.1007/975---401--22-----
1-4614-8265-9/ 1333. URL http::://ooo..rg//0001/0//////// 1ttp://0000007777-----4---------
9_133
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for con- trastive learning of visual representations. CoRR, abs/ abs/2202.055009, 2020.
Zhijie Deng, Yinpeng Dong, and Jun Zhu. Batch virtual adversarial training for graph convolutional net- works. CoRR, abs/1902.09199 2019.
Ming Ding, Jie Tang, and Jie Zhang. Semi-supervised learning on graphs with generative adversarial nets. In CIKM '18 pp. 913 922, 2018
Claire Domnat, Marinka Zitnik, David Hallac, and Jure Leskovee. Learning structural node embeddings via diffusion wavelets. In KDD '18 pp. 1320 1329, 2018.
Chris Dyer. Notes noise contrastive estimation and negative sampling. CoRR, abs/ abbs/1410.8255 2014. URL http://arxiv org/ org/abs 1410. 8251
Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based graph structure. CoRR, abs/1902.00 2019.
Matthias Fey and Jan Eric Lensson. Fast graph representation learning with pytorch goometric. CoRR, abs/1903.02428, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML '17, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature lcarning for networks. In KDD '66 pp- 855-864, 2016.
Chuan Guo, Gcoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh (eds.), ICML '17, volume 70 of Proceedings of Machine Learning Research, pp.
PMLR, 2017.
Michael Gutmann and Aapo Hyvärinen. Noise-contrasten contrastive estimation of unnormalized statistical models, with applications to natural image statistics. J. Mach. Learn. Res., 13:307 361, 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NewrIPS '17 pp. 1024-1034, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), ICML '22, volume 162 of Proceedings of Machine Learning Research, pp. 8230 8248. PMLR, 2022.
Olivier J. Hénaff, Aravind Srinivas, Jeffrey De Fauw, Ali Razavi, Carl Doersch, S. M. Ali Eslami, and Aäron van den Oord. Data-efficient image recognition with contrastive predictive coding. CoRR, abs/1905.09272, 2019.
R. Devon Hjelm, Alex Fedorov, Samuel Gavoie-Marchildon. Karan Grewal, Philip Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In ICLR '19, 2019.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjic Wang, and Jie Tang. Graphmae: Sell-supervised masked graph autoencoders. In KDD '22, 2022.
Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A decondig-enhanneed masked self-supervised graph learner. In WWW '23, 2023.
14

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In NewrIPS '20, 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategics for pro-training graph neural networks. In ICLR 200 2020b.
Jiabo Huang, Qi Dong, Shaogang Gong, and Xiatian Zhu. Unsupervised deep learning by neighbourhood discovery. In ICML '19, pp. 2849 2858, 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
ICLR '17 2017.
Xiang Li, Tiandi Ye, Caihua Shan, Dongsheng Li, and Ming Gao. Seegera: Sell-supervised semi-implicit graph variational auto-encoders with masking. In WWW '23, 2023.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In ALT '16, pp. p 3-17, 2016.
Tomas Mikolov, Tlya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In NewrIPS '13, pp. 3111 3119, 2013.
Andriy Mnih and Yee Whye Tch. A fast and simple algorithm for training neural probabilistic language models. In ICML '2, 2012.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2nd edition, 2018. ISBN 0262039400.
Rafael Müller, Simon Kornblith, and Geoffrey E. Hinton. When does label smoothing help? In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alchh-BBuc Emily B. Fox, and Roman Garnett (eds.), NewrIPS '19, pp. 4696 4705, 2019.
Mahdi Pakdaman Nacini, Gregory F. Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In AAAI '15, pp. 2901 29072997.220 AAAI Press, 2015.
Arvind Neelakantan, Tao Xu, Raul Puri, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris Hallacy Johannes Heidecke, Pranav Shyam, Boris Power, Tyna Eloundou Nekoul, Girish Sastry, Gretchen Krueger, David Schnurr, Felipe Petroski Such, Kenny Hsu, Madeleine Thompson, Tabarak Khan, Toki Sherbakov, Joanne Jang, Peter Welinder, and Lilian Weng. Text and code embeddings by contrastive pro-training. CoRR, abs/2201.10000 2022. URL http://axxxvv..r/bbba////sa
M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-8582, 2006.
Zhen Peng, Wenbing Huang. Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In WWW '20, pp. 259 270, 2020.
Gabricl Percyra, George Tucker, Jan Chorowski, Lukasz Kaiser, and Geoffrey E. Hinton. Regularizing neural networks by penalizing confident output distributions. In ICLR '17, 2017.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena, Deepwalk: online learning of social representations. In KDD '14, pp. 701-710, 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM 2018, pp. 459 467. ACM, 2018
Jiczhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. GCC: graph contrastive coding for graph neural network pre-training. In KDD '0, pp. 1150-1160, 2020.
15

---

Published in Transactions on Machine Learning Research (07/2023)
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: graph markov neural networks. In ICML '19, volume 97, pp. 5241-5250 2019.
Leonardo Filipe Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. struc2vec: Learning node representations from structural identity. In KDD '17 pp. 385 394, 2017.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theo- retical analysis of contrastive unsupervised representation learning. In ICML '19, pp. 5628-5637, 2019.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, 0os/1811.058653 2018.
William Shiao, Zhichun Guo, Tong Zhao, Evangelos E. Papalexakis, Yozen Liu, and Neil Shah. Link predic- tion with non-contrastivee learning. CoRR, abs//211 22111.1494,, 2022. doi: 40.5500/arXi.2211...1.
URL
attp:///Xxvvv.... 2211. 14394
Fan-Yun Sun, Meng Qu, Jordan Hoffmann, Chin-War Wei Huang, and Jian Tang, vgraph: A generative model for joint community detection and node representation learning. In NeurIPS '19, pp- 512-522, 2019.
Yiyou Sun and Yixuan Li. Opencon: Open-world contrastive learning. TMLR, 2023. ISSN 2835-8856. URL
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. In NeurIPS 22,, 2021. URL https::/oppnrreveet http::/www.........oooooo//////a
Qiaoyu Tan, Ninghao Liu, Xiao Huang, Soo-Hyun Choi, Li Li, Rui Chen, and Xia Hu. S2GAE: self-supervised graph autoencoders are generalizable learners with graph masking, In WSDM '23, 2023.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE; large-scale information network embedding. Tn WWW '15, pp. 1067-1077, 2015.
Josephine Thomas, Alice Moallemy-Oureh, Silvia Beddar-Wieste Wiesin, and Clara Holzhüter. Graph neural networks designed for different graph types: A survey, TMLR, 2023. ISSN 2835-8856. URL https:
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding, CoRR, abs/ abs/1906.05549, 2019.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning. CoRR, abs/2005.10243, 2020.
Zekun Tong, Yuxuan Liang, Henghui Ding, Yongxing Dai, Xinke Li, and Changhu Wang. Directed graph contrastive learning. In NewrIPS '21, 2021. URL http:///oppeneeeeeeeeeeeerrrrrr/
_BS31
Aäron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. CoRR, abs/1807.03747 007448, 2018
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR '18, 2018
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In JCLR '19, 2019.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, pegfomaterfommant package for graph neural networks. arXiv preprint 2019.
Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised feature learning via non-paraectiic instance-level discrimination. CoRR, abs/1805, 11800019977 01978, 2018.
16

---

Published in Transactions on Machine Learning Research (07/2023)
Rongkai Xia, Yan Pan, Lei Du, and Jian Yin. Robust multi-view spectral clustering via. low-rank and sparse decompasition. In AAAT '14, pp. 2149-2155, 2014.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In TCLR '19, 2019.
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. Network representation learning with rich text information. In IJCAI '15, pp. 2111 2117, 2015.
Han Yang, Kaili Ma, and James Cheng. Rethinking graph regularization for graph neural networks. In AAAI 21, pp. 4573 4581. AAAI Press, 2021.
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning. In KDD '20, pp. 1666-1676, 2020.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML '16, volume 48 of JMLR Workshop and Conference Proceedings, pp. 40-48, 2016.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiees Lin (eds.), NewrIPS '20, 2020.
Liang Zeng, Jin Xu, Zijun Yao, Yanqiao Zhu, and Jian Li. Graph symbiosis learning. CoRR, abs 2b5.22106005455 2021. URL http:://aaxiv.oo/abb///////
Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR '18 2018.
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustoring via adaptive graph convolution. In IJCAI '19, pp. 4327 4333, 2019.
Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering. In Proceedings of the Thirtieth International Joint Conference on Artificial Intellgenne, IJCAT-21, pp. 4434-3440. IJCAI 221, 8 2021. doi: 2..24963/jcaai.22211 URL httpp://doi. org/ 10. 24963/1jcaiii 2021/473. Main Track.
Kaixiong Zhou, Ninghao Liu, Fan Yang, Zirui Liu, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Adaptive label smoothing to regularize large-scale graph training. CoRR, abs/2108 13555, 2021.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Repre- sentation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. Thirty-ffthh Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021a. CRL /ttps::/opperreviet wwt.:eeetouuue /ott/forrmmidddUUUUUUYYYK
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW '21, 2021b. doi: 10. 10.1145/3412381..44 3449802.
17

---

Published in Transactions on Machine Learning Research (07/2023)
Table 7: Impact of Contrast-Res on ECE Value
Contrast
Cora
Citeseer
Pubmed
ML
0.477
0.540
0.399
0.413
0.525
0.273
T.C
0..477
0.537
0.416
TCC
V
0.437
0.524
0.274
A Details of the analysis
A.1 A through analysis of Claim
Considering that positive sampling is based on the calculated distance between pairwise embeddings, we can express the following relationship:
Eaca(orv' )= (p(o,, 24 - 14 = Eeople o hw))
(9)
Here, Bropk o(..-),.)) (o hwr) represents the expectation of the top k pairs (v, v'). When the loss converges, Etopk (hhu- hw]] + 1.
Furthermore, by considcring the definition in Equation and the fact that nogative samples are uniforml sampled, we can write:
Be o' = v')] -i,,,,
(10)
Thus, Equation can be reformulated as:
ECE r 2.roop o(ho- hw 11)a +r 11-29 24 1Blo hv) +r
(11)
+ + +rokk ah, (,) la KG)].
When the loss converges, Etopk oth, h. lo (hv- - indicating that the ECE value is negatively correlated with the probability a+ of e4. In addition, negative samples uniformly sampled, so that q 1/K, where K represents the number of classes when K > 2. As result, ECE is positively correlated with the expectation of the confidence value for randomly sampled pairs [o (h,,))))).
A.2 Contrast-Reg Leads to a Decreased ECE Value
We empirically igves the impact of loss convergence on the ECF value, with and without Contrast-Reg, across various datasets and contrastive strategies, in Table 7 The results demonstrate that Contrast-Reg leads to a decrease in ECE values for all tested datasets and contrastive losses. This reduction ECE indicates that Contrast-Reg promotes better aligument. with the performance of downstream tasks while minimizing the training loss, ensuring that minimizing the contrastive loss with Contrast-Reg results high-quality representations.
A.3 Explanation of Contrast-Reps Impact on the Term s(f)
In this section, we provide an explanation for why Contrast-Reg leads a decrease in the upper bound of s(f). Firstly, will prove that minimizing Eq. 7 results in decrease in Var([ when h Wr > c, stated in Theorem 2 Then, based on the assumption that models with lower Var([[aa]) inherently favor lower values of E Il both [1bba]] and mea (M (f,c)) c)) will decrease. Consequently, the upper bound of s(f) decreases with the implementation of Contrast-Reg, In the subsequent proof, h, = f(x), and the notations h2 and f(z) may be used interchangeably for the sake of presentation clarity. Theorem 2. Minimizzng Eq. 7 induces the decrease in Var([(h;l) when h Wr c.
Proof. We minimize freg by gradient descent with learning rate 3.
0f(x) Creg = -o(-f(x) Wr)WT
(12)
18

---

for Published in Transactions on Machine Learning Research (07/2023)
The embedding of f(x) is updated as the following after adding L.eg:
f(z) + f(x) ((
(13)
Eq. 13 shows that in every optimization step, (a) extends by {o |Wrl along ro = Wr
[
If we do orthogonal decomposition for f(z) along To and its unit orthogonal hyperplain 11(ro), f(x) (o) ro (f())"(((ro) [((r)) Thus we have
IIf(x))l - v (f()))To))' (f
(14)
The projection of f(x along ro is f(x)"ra = Wr while the projection of f(x) plus the Contrast-Reg update along ro is
[Wwll
f(x)"Wr
(f(x)" (f(x)"ro)..=
||Wr|l +
1 ef(o) w. ||r]|
Note that (f(z)"I((ro) reg
I(x))II(ro).
Based on Lemma 1 and Eq.
14
when 3 ||] s and f(x) Wr > 15, we have
Var ((((())))r=)))) Var (Il)
(15)
Lemma For random variable E [1.5, +00), constant T E (0, 1] and a conslant c², we have
Var (Vix+ x ) x Var (vx2+
(16)
Proof. First, we consider
h(x)) V (1
1 )2
+
c
V x2 + c
where h(x)) is strictly decreasing in [ro, +oo) and strictly increasing in (-o0, mo), and xp is the solution of M(xx) dh(z) 0. Thus, we can approximate the range ao E (0, 1.5) by the fact that h ((00)/
all 7 and C
Thus, for y 1.5,
V (1 + T )2 ) c² + <
<
1+ T+
1 2
1
and since (x + T is monotonically increasing, we get
0 <<
1000 (0 1t 1 + c² - /V+ I+
T
When y > x 1.5,
V 22 - v + 22
(I+
T
)2 c²
(v+
T )2 + c² < 0.
It
1t ev
19

---

Published in Transactions on Machine Learning Research (07/2023)
Further, we assume that X and Y are ii.d. random variables sampled from [1.5, +o0),
Var (Wix+ 1tex x2xx+++
1
( I+x p )2 + 10+ T 1 1 +2
27
- x Ex.y
1
/
(V 10----1110 (ot It +2) p(z)p(y)dedy
100
2
Ite
1 2 x / Vx2+00 V +0) p(z)plv)dzdy
=Var(v (
Remark 1. 3 ||Wr|] 1 which the condition of Eq.. (5) not difficult to satisfy, since the magnitude, of could be tumed. In practice,
(0,1) can fit in all our experiments.
Remark 2. The range of fx) ur in Theorem 2 not a tight bound for zo Lemmal 1 Since when Eq. 7
converges, [wr)"Wr is much larger than 1.5 for almost all the samples empirically, we prove the case for (1)) wr E (1.5++00)
A.4 Comprehensive Explanation of Theorem Notations and Proof
To formally analyze the behavior of contrastive learning, we introduce the following concepts the previous literature (Saunshi al. 2019) docs.
Latent classes: Data are considered as drawn from latent classes C with distribution p. Further, distribution De is defined over feature space X' that associated with a class E C to measure the relevance between and c.
Semantic similarity: Positive samples are drawn from the same latent classes, with distribution
D Daim xx = Eeep (De(=)D(<x)))
(17)
while negative samples are drawn randomly from all possible data points, i.c., the marginal of Dims as
Dreg (x = Engp [Pa(a-]]
(18)
Supervised lasks: Denote K as the number of negative samples. The object of the supervised task, ie., feature-label pair (z, e), is sampled from
-(())c)=D(s)DDP(()
where Dy(c) p(c|c E T), and T S C with IT = + Mean classifier WH is naturally imposed to bridge the gap between the representation learning performance and lincar separability of learn representations, as
W = Me = (enDD.f(x)).
Empirical Rademacher complexity: Suppose F + [1.0]. Given a sample S,
Rs = Ee sup e" f(S)
feJ
where E (e,.". .mm) T, with e, are independent random variables taking values uniformly from (11,
20

---

Published in Transactions on Machine Learning Research (07/2023)
In addition, the thcoretical framework (Saunshi et al. 2019 makes assumption: encoder is bounded, T.e., max [s() I R², R R. IR.
To prove Theorem ! we first list some key lemmas. Lemma For all f F,
(f) S 1 1 (Crec(f) log 2).
(19)
This bound connects contrastive representation learning algorithms and its supervised counterpart. This lemma is achieved by Jensen's incquality. The details are given in Appendix A.6
Lemma 3. With probability at least 1 - å over the set S, for all f E F,
Lnce S Lace + Geny-
(20)
This bound guarantees that the chosen f = arg men Li cannot be too much worse than f arg men face. The proof applics Rademacher complexity of the function class (Mohri et al., 2018 and vector-contraction inequality [Maurer, 2016). More details are given in Appendix A.7
Lemma 4. L (f) < 4s( + 2o
This bound is derived by the loss caused by both positive and negative pairs that come from the same class, i.e., class collision. The proof uses Bernoulli's inequality (details in Appendix A.8
Proof to Theorem 7 Combining Lemma and Lemma 3 obtain with probability least 1 - 8 over the set S, for all FFF
fuup (f) T-7 (Lonce Gens)
(21)
Then, we decompose Lnce = T Tnce (f) + (1-)) (f), apply Lemma to Eq. 21 and obtain the result of Theorem
A.5 Contrastive Learning with NCEloss
The contrastive loss is
E Lun (z. Doosi (e .. 2x PDeng
where É can be the hinge loss as ((v) loga (1 + E, exp(-v:)) And its supervised counterpart is definod as
max {0, + max; [-vi}} the logistic loss as f(v)
[e (116)) f(x) pe }oqe)) Chap (e
A more powerful loss function. NCEloss, used in the previous literature Velickovic et al. 2019 Yang et al. 2020 Mnih & Teh 2012 Dyer 2014), can be framed as
Lnce =
K (ogo f(x+)(++++++++))+++))))+))) +(= logal- (f))) f(xx))
(22)
R ( Damms (e] yr we DDec
M (Ftk) and its empirical counterpart with M samples (1:.0t Pii
k-kk)= is given as
M
Ence
log oogo( f(x))) log logo(-((x)) f(()))
(23)
M
where (-.) is the sigmoid function.
For its supervised counterpart, it is exactly the cross entropy loss for the (K + 1)-way multi-class classificationn task:
L =-
E
[loga(((>) -oggooo(((e) p we)ld #c].
(24)
21

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
A.6 Proof of Lemma 2
First, prove that ((f(t), (((T)) [(ogo(((())((xt)) E log(o([(=)* f(x)) })) is convex w.i.t. f(**), f( (((z) Consider that (=) - lo) and (2(=) - logol are both convex fune- tions since E > 0 and & > 0 for 2 R. Given f(x) E R, z f(x)"f(x*) and =- = f(x)) are affine transformation w.r.t. f(x)) and ((=). Thus, when f(a) fixed, & (f((x))) = - logoo((())) ((=()))(()))))) and (e(f(x))) = log (f)f(x)" f(x )) are convex functions. As l > 0 and & > 0, we obtain {(f(=); (f(x; }}) - (log (f())((()"))))))) f(x }) + Dx (f)((( f(" )))) is convex since non-negative weighted sums preserve convex- ity (Boyd Vandenberghe 2014). By the definition of convexity,
Luea B
staD
NED
x IN
2 Ell ro D [(((())) (Not Me )}]
= (1 - (f) + TEotapReND [- ( mot) (osa(_(()''<-)
2 (1 - 7) Cuu (f) + 2r log2
A.7 Generalization bound
Denote
$ =f -x)=
((()) (E
Let qj h f, and its function class,
Q Q= --
Denote 2; = (I,, 23 -ij.'.. :.. TTR) suppose l is bounded by B, then we can decompose h = 1 Φ. Then have (z(2)) {z)((( where
o(f(z))) = Σ (a.)) Ma)ddea)a
Σ Manes(Ea
(25)
K
((x) - log (x))
log (og)(-2;))
From Eq. (25) we know that Φ IR (K+22) RK+1
Then we will prove that h is L-Lipschitz by proving that & and l are both Lipschitz continuity, First,
ao(f(=)) f(xx))
ffattble ==0
af(x:);
M(tte k= 11....., K ao(f(z)) f(z:).. f(aū))
do(F(z)) f(x:)e,
f(xtt)
If we assume Eim [La)) R² and E. f(x:) & R²,
K
||
Σ
(C + ΣΣ (a (K + 1) Σ f(x))
1=1 A=1
/ 2(K + 11R / + +1)R
22

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
Algorithm 2: ML
Parameter: Parameters of an (additional) GNN layer g- Function Contrast (C, G, X, f): Let g(xx) be the representation
æs by stacking g upon f: Randomly pick a negative node o7 from for each 3; return (()())) [(e)) ((T))) 2,00i 2,00
end
Function SeedSelect X, J, epoch):
return V;
end
|| we obtain that e /2(K + Lipscccct Similarly, e is /K + I- Since we assume that the inner product of embedding no more than R2. Thus, I is bounded by B
Combining || S
-KK + 1) log(a((RR)) Above all, h is L-Lipschitz with L <2 Applying vector-contraction
inequality (Maurer 2016
we have
Eg Ba-(t (supla, (h fis s V2LE o (sup fia)l. feF
fer
If we write it Rademacher complexity manner, we have
2(K + 1)R Rs(F).
Rs(2)
B
Applying generalization bounds based on Rademacher complexity Mohhri et al. 2018 to Q. For any 8 > 0, with the probability of at least
E'g(2]]
Σ
((x))
2Rs(2)
log
M
M
2M
Σ (2.))
4(K + 1)RR((F)
3/
log 4 2M
BM
Thus for any J,
Enee(f) S (f) + 4(K + L)HRs(F))
log 4 2M
3B
(26)
M
Let f = =arg minje Lnce (f) and f = arg migne Lace (f). By Hoeffding's incquality, with probability of 2:
log
Enor((") S Lnce BV 2M
(27)
Substituting into Eq. 26 most
combining Lncee (f) S Lfnc(ff) and applying union bound, with probability of
Cnce(f) Ennor() + 4(K + ()R
log 4
log 2
3B
x
+ B
M
2M
2M
< (nnce(""++ 4(K + (FF
+ +BB +4B
log 1
(28)
M
2M
4(K + 1)RRs(F)
log
S Lnoo +
4(K + ()oo(((--1)))
M
2M
fails. Thus, with probability of at least
Eq.
28 holds.
23

---

Published in Transactions on Machine Learning Research (07 (07/2023)
A.8 Class collision loss
Let Pj = ff fxx)] and p = ma., K] Pi. Considering
(f) (ogo([(x)) s(x)))
Σ
log (- f(0
= E log(1 + -(()))))
log(1 + ((0) s(o7)
(29)
(K 1]E [og + e²)] $ (K + 1) log 2 + (K + 1)E [p]
Since z, 2 : F k are sampled i..d. from the same class,
/
/ (1- Plpo x1) x)) dr.
Elpl
Plo x|d==
(30)
Applying Bernoulli's incquality, we have
Epp -
(1 - (1 (K + 1)ppp 2 dl))
-( + 1)P(po z|dr
(31)
(K + 1)E
(K + 1)
< (K + B((
Therefore,
C (
(5) S (K + log + (K+1)ss(0
(32)
24

---

Published in Transactions on Machine Learning Research (07 (072))23)
Algorithm 3: L.C
Hyperparameter: R: curriculum update epochs; k: the number of candidate posilive samples for seed node; Function Contrast (C, G, X, f):
For z; E C, let N be set of k nodes {ry e Neighbor(z:)) with largest f(x.)* (a,)) Randomly pick one positive node of from N for each xq Randomily pick uegalive node zy from for each x; C;
return {((a)) f(a) f(,7 })} z,eci end
Function SeedSelect(4) (9, X, f, epoch): if epoch % R. + then
return the same of seed nodes C' in the last epoch end 10
f(1
11
PLd Σ key f(i)* f(k) for i V;
12
H(i) + Ejev (P., log (P.,)) for i V;
return spock 1) [ nodes with smallest H;
13
end
Algorithm 4: GCA
Hyperparameter: two stochastic augmentation functions set T and T': Function Contrast 9, X, f):
2 Sample two stochastic augmentation functions i ~ T and i ~~ T';
Generate two graph views G₁ = t(G) and G2 = GGG) by performing corruption on G; p.
4 return
end
Function SeedSelect (G, X, f, epoch):
return V;
end
B Details of Graph Contrastive Algorithms
Algorithm I prosentss the graph contrastive learning framework and how Contrast-Reg is plugged into it. The functions SeedSelect and Contrast in the graph contrastive learning framework are responsible for selecting the seed nodes and sampling the Desitive/negative pairs for these seeds while incorporating various priors for both structural and attribute aspects of the graph. he detailod SeedSelect and Contrast implementations for ML, LC, GCA are referred to Algorithm and
C Supplementary Experiments
C.1 Plug Contrast-Red Reg into DiGCL and GDCL
We applied Contrast-Reg to two graph contrastive learning algorithms, namely DiGCL [Tong al., 2021 and GDCL (Zhao et al. 2021). GDCL employs graph clustering to reduce the number of false-negative samples, whercas DiGCL generates contrastive pairs using Laplacian perturbations to better preserve the structural altributes of directed graphs. In Table g we present a comparative analysis of the performance of Contrast-Rae Rerra applied to both algorithms, as well as their performance without Contrast-Res We used the official implementations and the parameters of both algorithms, and conducted experiments with random seeds ranging from 0 9. Our results demonstrate that Contrast-Reg serves an effective plugin these advanced graph contrastive learning algorithms, even when applied to directed graphs (DiGCT.).
25

---

Published in Transactions on Machine Learning Research (07/2023)
Table 8: DiGCL GDCL with and without Contrast-Reg
Algorithm Contrast-Reg
Cora-ml
Citeseer
Cora
DiGCL
76.62=1.23
65.54=1.39
DIGCI
79.74
68.7441.13
GDÖL
72.98=0.73
85.41+0.33
GDČL
76.39
85.80+0.46
Table 9: Datasets
Dataset
Node #
Edge #
Feature #
Class
Cora
Yang
2016
2,708
5,429
1,433
7
Citeseer
Yang et al.
2016
3,327
4,732
3,703
6
Pubmed
Yang et
2016
19,717
44,338
500
3
ogbn-arxiv Hu et al.
2020a
169,343
1,166,243
128
40
Wiki Yang et al.
2015
2,405
17,981
4,973
3
Computers [Shchur et a.. 2018
13,381
245,778
767
10
Photo (Shchur et al. 2018)
7,487
119,043
745
8
ogbn-products (Hu et
2020a
2,449,029
61,859,140
100
47
Reddit [Hamilton et al.
2017
232,965
114,615,892
602
41
D
Experiment details
Dataset statistics The datasets we employed encompass citation networks, web graphs, co-purchase networks, and social networks. The detailed dataset statistics are shown in Table g
Hardware Configuration: The experiments are conducted on Linux servers installed with an Intel(R) Xeon(R) Silver 4114 CPU @ 2.20GHz, 256GB RAM and NVIDIA 2080Ti GPUs.
Software Configuration: Our models, well the DGI, GMT and GCN baselines, were implemented in PyTorch Geometric (Fey & Lenssen 2019 version 1.4.3, DGL Waag et al., 2019) version 0.5.1 with CUDA version 10.2, scikit-learn version 0.23.1 and Python 3.6. Our codes and datasets will be made available.
Typer-parametern For full batch training, we used 1-layer GCN as the encoder with prelu activation, for mini- batch training, we used a 3-layer GCN with prelu activation. We conducted grid search of different learning rate (from 1c-2, 5c-3, 3e-3, 1e-3, 50-4, 3c-4, lc-4) and curriculum settings (including learning rate decay and curriculum rounds) on the fullbatch version. We used le-3 5e-4 the learning rate; 10,10,15 10, 10,25 the fanouts and 1024 512 the batch size for mini-batch training.
26


Reviews:
[{"review_id": "UkcCmYOF8i", "reviewer": "Reviewer_gyCv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The problem shown in Figure 1 seems to show that the NCEloss-based graph contrastive learning is problematic in some aspects.\n2. The proposed method is easy to implement and plugged into the current method.\n3. The provided Theoretical analysis seems sound to me.\n\n\n**Weaknesses**\n1. The citation of this paper is super random. Just cite the papers that relate to wide-range terms. such as in the Introduction (page 1), “graph representation learning algorithms Velickovic et al. (2019); Peng et al. (2020); Tang et al. (2015); Perozzi et al. (2014); Grover & Leskovec (2016); Ahmed et al. (2013); Cao et al. (2015); Qiu et al. (2018); Chen et al. (2018); Kipf & Welling (2017); Hamilton et al. (2017); Velickovic et al. (2018); Xu et al. (2019); Qu et al. (2019) have been proposed”. Such a way for citation is not an accurate and reasonable way for citation. (as well the citation is not in the correct formation, please use the \\citet{} and \\citep{} correctly.)\n2. The presentation is not clear. In the introduction, what is the meaning of “the quality of the embeddings generated by the model, $\\delta(h\\_v, h\\_{v’})$”? And how this influences the learned embedding? Please try to make the introduction self-contained. \n3. The motivation is not clear. This paper claims that “to new tasks or data has proven to be inconsistently effective” (in the abstract), However, there is no analysis or experimental evidence to support this point. \n4. This paper overall a bit hard to follow, mainly because of the unclear motivation, and unclear meaning/influence of ECE.\n5. The experiments can be improved. \n   - For node classification, only DGI and GMI, which are not new, are referenced as the most recent or relevant baselines. There are numerous unsupervised graph learning methods available. Furthermore, the performance is subpar. Some models cannot outperform the baseline, while others show only marginal improvements.\n   -  For link prediction, this paper neglects to consider link prediction methods.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on better graph contrastive learning.  This paper presents a regularization method called Contrast-Reg to improve the performance of graph contrastive learning algorithms and graph neural network models. It addresses calibration issues by maintaining high-quality node representations that improve accuracy in downstream tasks, avoiding overfitting to spurious features. Both theoretical and empirical evidence support the effectiveness of Contrast-Reg across various tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Correct Citations: Ensure only relevant citations are in the correct format.\n2. Clarify introduction: Clarify the meaning of the quality of embeddings in the introduction.\n3. Clarify the Motivation: Provide evidence for the claim in the abstract about inconsistent effectiveness.\n4. Improve readability by clarifying the motivation and influence of ECE.\n5. Experiments: Include more recent baselines for node classification and integrate link prediction methods.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1FfugN0kcI", "reviewer": "Reviewer_kYUe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I am not familiar with graph contrastive learning, so I will comment from the perspective of uncertainty calibration.\n\nStrengths:\n1. The analysis of why ECE can be high (claim 4.1) in existing graph contrastive learning methods is interesting.\n2. The authors theoretically justified why their method could potentially improve generalization in downstream tasks (Theorem 1).\n3. The method is simple and the empirical results look good.\n\nWeaknesses:\n1. The method is motivated to improve the calibration during contrastive learning, however, there is no direct explanation why adding Contrast-Reg term to the NCE loss will reduce ECE (they only show it empirically).\n2. ECE is a controversial calibration metric since it can only measure the population level calibration. Moreover, it is not guaranteed to be reduced with distribution shift. I am not sure whether the improvement in calibration in contrastive learning stage can be transferred to downstream tasks where there might be distribution shift (since the strategy of generating negative samples during contrastive learning stage seems to be artificial). \n3. Following the above point, the reason why reducing ECE in the contrastive learning stage can even \"enhance the accuracy of downstream tasks\" is unclear to me. Although the authors suggest the generalization may improve by using their method (Theorem 1), it seems to be unrelated to the improved calibration in contrastive learning stage.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors argue that existing graph contrastive learning methods suffer from uncertainty miscalibration. To mitigate the pathology, they proposed to add a regularization term \"Contrast-Reg\" to the standard NCE loss and they empirically show that it will reduce the expected calibration error (ECE) and thus improve the calibration. Moreover, they show that this strategy may improve the generalization in downstream tasks from a theoretical analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weaknesses above.", "broader_impact_concerns": "I have no concerns about the broader impacts and the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3fCmFDKInz", "reviewer": "Reviewer_mn1F", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The motivation of the proposed method is clearly explained. The mis-calibration is the key challenge of GCL indeed. Therefore, the proposed work makes a significant contribution to the community of GCL.\n\n2. The idea of designing an ECE-based regularizer for GCL is reasonable in my opinion. The authors demonstrate the rationality of the proposed method in both theoretical and empirical analysis.\n\n3. The authors consider various application scenarios of the proposed method, which covers the representative downstream tasks of GCL. \n\nDrawbacks:\n\n1. Although the authors consider multiple application scenarios in the experimental section. In each task, the baselines are insufficient and not so representative. In the field of graph contrastive learning, some recent works should be considered as the baselines, e.g., [a - d]. These methods also consider the limitations of existing GCL framework and propose different strategies to reduce the mis-calibration issue of GCL. The authors should i) take some of them as the baselines in the experimental section and ii) introduce the recent development of GCL in the related work part, highlight the differences between these methods and the proposed method.\n\n[a] Tong, Zekun, et al. \"Directed graph contrastive learning.\" Advances in Neural Information Processing Systems 34 (2021): 19580-19593.\n\n[b] Suresh, Susheel, et al. \"Adversarial graph augmentation to improve graph contrastive learning.\" Advances in Neural Information Processing Systems 34 (2021): 15920-15933.\n\n[c] Zhu, Yanqiao, et al. \"Graph contrastive learning with adaptive augmentation.\" Proceedings of the Web Conference 2021. 2021.\n\n[d] Zhao, Han, et al. \"Graph Debiased Contrastive Learning with Joint Representation Clustering.\" IJCAI. 2021.\n\n2. In Tables 1-4, if my understanding is correct, the proposed methods LC and ML have taken the proposed Contrast-Reg into account. However, in Table 5, the authors further introduce the methods “LC + Contrast-Reg” and “ML + Contrast-Reg”, which is confusing.\n\n3. Besides taking GCN as the backbone, the authors should consider other backbones like GIN in the experiments, such that the usefulness of the regularizer with respect to different model architectures can be verified.\n\nMinors:\n\n1. The captions of Figures 1 and 2 are oversimplified. The details of the analytic experiments should be given in the captions, e.g., the dataset, the model architecture and so on.\n\n2. Some citations are not normative. In particular, in some places, the citations should be formatted as “(Authors, Year)” rather than “Authors (Year)”. Try to use \\citep instead of \\cite.\n\n3. Page 7, line 6: The notations of L_nce and L_supp^mu are inconsistent with those shown in Theorem 1.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors proposed a new and effective regularizer to improve existing graph contrastive learning (GCL) framework. \nThe proposed regularizer is based on the expected calibration error (ECE) that measures the consistency between model confidence and model performance. \nBy imposing this regularizer, the authors empirically show that the mis-calibration/bias of GCL caused by the randomly sampled negative pairs can be suppressed. \nIn theory, the authors demonstrate that the proposed regularizer helps to reduce the expectation of the embeddings’ inner product and thus leads to a tighter generalization error bound of GCL.\nIn the aspect of methodology, the authors provide two implementations of the regularized GCL and verify their effectiveness in multiple downstream graph learning tasks.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the drawbacks and minors shown above", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agreed that the problem of calibration in graph contrastive learning is under-explored so they welcomed this study. 

In initial review stage, reviewers mainly raised two concerns:
1. Explanations on why ECE is related to contrastive learning performance, and how would the proposed regulariser help.
2. Benchmarks selected in the experiment section are outdated.

In revision the authors clarified their theory and added a few more experiments. The questions related to theory are largely addressed, but some reviewers are still unhappy about the selected baselines. In particular they suggested the following baselines to be considered:

- S2GAE: Self-Supervised Graph Autoencoders are Generalizable Learners with Graph Masking, WSDM2023

- GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner, TheWebConf2023

- SeeGera: Self-supervised Semi-implicit Graph Variational Auto-encoders with Masking, TheWebConf2023

- GraphMAE: Self-Supervised Masked Graph Autoencoders, KDD2022

From my point of view the 2023 papers can be viewed as concurrent works so it is OK not to consider them. But I agree that given the fast evolution of the graph NN field, it would make sense to include the latest (2022) graph contrastive learning methods (e.g., the last one above) in comparison.

Given that the paper's contributions are not solely based on empirical improvements, and the reviewers are welcoming the theory contributions, I recommend acceptance but conditioned on including one of the latest graph contrastive learning methods as baselines. 
Decision: Accept (poster)