Certifiably Robust Graph Contrastive Learning
Authors: Minhua Lin
Teng Xiao
Enyan Dai
Xiang Zhang
Suhang Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Certifiable Robustness
Graph Contrastive Learning

Abstract: Graph Contrastive Learning (GCL) has emerged as a popular unsupervised graph representation learning method. However, it has been shown that GCL is vulnerable to adversarial attacks on both the graph structure and node attributes. Although empirical approaches have been proposed to enhance the robustness of GCL, the certifiable robustness of GCL is still remain unexplored. In this paper, we develop the first certifiably robust framework in GCL. Specifically, we first propose a unified criteria to evaluate and certify the robustness of GCL. We then introduce a novel technique, RES (Randomized Edgedrop Smoothing), to ensure certifiable robustness for any GCL model, and this certified robustness can be provably preserved in downstream tasks. Furthermore, an effective training method is proposed for robust GCL. Extensive experiments on real-world datasets demonstrate the effectiveness of our proposed method in providing effective certifiable robustness and enhancing the robustness of any GCL model. The source code of RES is available at https://github.com/ventr1c/RES-GCL.

Certifiably Robust Graph Contrastive Learning
Minhua Lin, Teng Xiao, Enyan Dai, Xiang Zhang, Suhang Wang The Pennsylvania State University 1mf15681, tengxiao, emd5759, xzhang, szw494) (aw444)ppsu... @psu. edu
Abstract
Graph Contrastive Learning (GCL) has emerged popular unsupervised graph representation learning method. However, it has been shown that GCL is vulnerable to adversarial attacks both the graph structure and node attributes. Although empirical approaches have been proposed to enhance the robustness of GCL., the certifiable robustness of GCL is still remain unexplored. In this paper, develop the first certifiably robust framework GCL. Specifically, we first propose a uni- fied criteria evaluate and certify the robustness of GCL. We then introduce novel technique, RES (Randomized Edgedrop Smoothing), to ensure certifiable robustness for any GCL model, and this certified robustness can provably pre- served in downstream tasks. Furthermore, an effective training method is proposed for robust GCL. Extensive experiments on real-worle datasets demonstrate the effectiveness of our proposed method in providing effective certifiable robustness and enhancing the robustness of any GCL model. The source code of RES is available at https:://// thub. wwwccomm/ttteeeeeeeee wtt.//eeeetteeeeeeeeeeeeee
Introduction
Graph structured data ubiquitous in real-world applications such social networks [.] finance systems [2). and molecular graphs [3]. Graph Neural Networks (GNNs) have emerged as a popular approach to learn graph representations by adopting message passing scheme [4] 5 6 which updates a node's representation by aggregating information from its neighbors. Recently, graph unsupervised approach to learn node graph contrastive learning has gained popularity learning creates augmented views and minimizes representations 7 [8) 9]. The graph contrastive
the distances among positive pairs while maximizing the distances among negative pairs in the embedding space.
Despite the great success of GNNs, some existing works [10 are vulnerable to adversarial attacks where the attackers can deliberately manipulate the graph structures and/or node features degrade the model's performance. The representations learned by Graph Contrastive Learning (GCL) are also susceptible to such attacks, which can lead to poor performance in downstream tasks with small amount of perturbations [14 against graph adversarial attacks, several empirical-
have shown that GNNs
1. 16
To defend
works have been conducted in robust GNNs for classification tasks [17] [8] and representation learning with contrastive learning [14 15]. Nevertheless, with the advancement of new defense strategies, new attacks may be developed to
invalidate the defense methods [19 20 21 22). leading to an endless arms race. Therefore, is important to develop a certifiably robust GNNs under contrastive learning, which can provide certificates nodes/graphs that are robust to potential perturbations in considered space. There are several efforts in certifiable robustness of GNNs under supervised learning, which requires labels for
the certifiable robustness analysis 23 24 25 26. For instance, (3] firstly analyze the certifiable
robustness against the perturbation node features. Some following works [24] 25 26 further study
the certified robustness of GNN under graph topology attacks. However, the certifiable robustness of GCL, which is in unsupervised setting, is still rarely explored.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Certifying the robustness of GCL is rather challenging. First, quantifying the robustness of GCL consistently and reliably is a difficult task. Existing GCL methods [27 14 [3] often use empirical robustness metrics (e.g., robust accuracy) that rely on the knowledge of specific downstream tasks (e.g., task types, node/graph labels) for evaluating GCL robustness. However, these criteria may not be universally applicable across different downstream tasks. The lack of clarity in defining and assessing robustness within GCL further compounds the difficulty of developing certifiably robust GCL methods. Second, the absence of labels in GCL makes it challenging to study certifiable
robustness. Existing works (2 28 29, 25] 24 on certifiable robustness of GNNs are designed for supervised or semi-supervised settings, which are not applicable to GCL. They typically try to provide certificates by analyzing the worst-case attack on labeled nodes. However, it is difficult to conduct such analyses due to the absence of labels in GCL. Additionally, some works (29] 24 that rely on randomized smoothing to obtain robustness certificates can not be directly applied to GCL as they may require injecting noise into the whole graph during data augmentation, introducing too many spurious edges and hurting downstream task performance, particularly for large and sparse graphs. Third, it is unclear whether certifiable robustness of GCL can be converted into robust performance in downstream tasks. The challenge arises due to the misalignment of objectives between GCL and downstream tasks. For instance, GCL usually focuses on discriminating between different instances, while some downstream tasks may also require understanding the relations among instances, This discrepancy engenders a divide between unsupervised GCL and its downstream tasks, making difficult to prove the robust performance of the certified robust GNN encoder in downstream tasks.
In this work, we propose the first certifiably robust GCL framework, RES (Randomized Edgedrop Smoothing). (i) To address the ambiguity in evaluating and certifying robustness of GCL, we propose unified criteria based on the semantic similarity between node or graph representations in the latent space. (ii) To address the label absence challenges and avoid adding too many noisy edges for certifying the robustness in GCL, we employ the robustness defined at (i) for unlabeled data and introduce a novel technique called randomized edgedrop smoothing, which can transform any base GNN encoder trained by GCL into a certifiably robust encoder. Therein, some randomized edgedrop noises are injected into the graphs by stochastically dropping observed edges with certain probability, preventing the introduction of excessive noisy edges and yielding effective and efficient performance. (iii) We theoretically demonstrate that the representations learned by our robust encoder can achieve provably robust performance in downstream tasks. (iv) Moreover, we present an effective training method that enhances the robustness of GCL by incorporating randomized edgedrop noise. Our experimental results show that GRACE (30) with our RES can outperform the state-of state-of-the of-t baselines against several structural attacks and also achieve 43.96% certified accuracy in OGB-arxiv dataset when the attacker arbitrarily adds at most 10 edges.
Our main contributions are: (i) We study a novel problem of certifying the robustness of GCL to various perturbations. We introduce a unified definition of robustness in GCL and design a novel framework RES to certify the robustness; (ii) Theoretical analysis demonstrates that the representations learned by our robust encoder can achieve provably robust performance in downstream tasks; (iii) We design an effective training method for robust GCL by incorporating randomize edgedrop noise; and (iv) Extensive empirical evaluations show that our method can provide certifiable robustness for downstream tasks (i.e., node and graph classifications) on real-world datasets, and also enhance the robust performance of any GNN encoder through GCL.
2
Related Work
Graph Contrastive Learning. GCL has recently gained significant attention and shows promise for improving graph representations in scenarios where labeled data is scarce [31 32 g 30 27
15
35). Generally, GCL creates two views through data augmentation and contrasts representations between two views. Several recent works [6. 36 show that GCL is vulnerable robustness of GCL, there are no existing works studying the certified robustness of GCL. In contrast, we propose to provide robustness certificates for GCL by using randomized edgedrop smoothing. More details are shown in Appendix I To the best of our knowledge, our method is the first work to study the certified robustness of GCL.
33 32
34
to adversarial attacks. Despite very few empirical works 9 15
Certifiable Robustness of GNNs. Several recent studies investigate the certified robustness of GNNs 25 37). Zunger et al. [23] are the first to explore
in the (semm)--suerriii setting 23 28 29
26
24

---

certifiable robustness with respect to node feature perturbations. Subsequent works 26 29 24] 38 extend the analysis to certifiable robustness under topological attacks. More details are shown in Appendix A.2 Our work is inherently different from them: (i) we provide an unified definition to evalute and certify the robustness of GCL: (ii) we theoretically provide the certified robustness for GCL in the absence of labeled data, and this certified robustness can provably sustained in downstream tasks; (iii we design an effective training method to enhance the robustness of GCL.
3 Backgrounds and Preliminaries
3.1 Graph Contrastive Learning
Notations. Let = (V, &, X) denote a graph, where V = {vi....,, Uy} is the set of N nodes, _ V V is the set of edges, and X [x1,...,xx] is the set of node attributes with x; being the node attribute of i. A E RNNN is the adjacency matrix of G, where Aij = 1 if nodes e and vg are connected; otherwise Aij O. In this paper, we focus on unsupervised graph contrastive learning, where label information of nodes and graphs are unavailable during training for both node- and graph-level tasks. For the node-level task, given graph G. the goal to produce representation Zy for v, which can be used to conduct prediction for node v in downstream tasks. For the graph-level task, given a set of graph G {G1.92.. f2.... }. the goal is to learn the latent representation Zg for each graph G, which can be used to predict downstream label yg of G. For simplicity and clarity, in this paper, we uniformly denote node or graph as a concatenation vector v. The representation of v from encoder h is denoted as h(v). More details are shown in Appendix E.2
learn GNN encoder h
Graph Contrastive Learning. Generally, GCL consists of three steps: (i) multiple views generated for each instance through stochastic data augmentation. Positive pairs are defined as two views generated from the same instance; while negative pairs are sampled from different instances; (ii) these views are fed into a set of GNN encoders /2,,, ... which may share weights; (iii) a contrastive loss is applied to minimize the distance between positive pairs and maximize the distance between negative pairs in latent space. To achieve the certified robustness of GCL to downstream tasks, we introduce latent class to formalize the contrastive loss for GCL, which is inspired by [39 40)
Definition 1 (Latent Class). We utilize the latent class to formalize semantic similarity of positive and negative pairs in GCL. (39] Consider GNN encoder h learnt by GCL. Let V denote the set of all possible nodes/graphs in the input space. There exists a set of latent class, denoted as C, where each sample E V is associated with a latent class c E C. Each class c C is associated with distribution De over the latent space of samples belonging to class under h. The distribution on C is denoted as ry. Intuitively, (v) captures how relevant v is to class e in the latent space under h, similar to the meaning of class in supervised settings. The latent class is related to the specific downstream task. For instance, when the downstream task is a classification problem, the latent class can be interpreted as the specific class to which the instances belong.
Typically, GCL is based on the label-invariant augmentation intuition: the augmented operations preserve the nature of graphs and make the augmented positive views have consistent latent classes with the original ones [1.. Let et.c E C denote the positive and negative latent classes drawn from n, De+ and D.- are the distributions to sample positive and negative samples, respectively. For each positive pair (v, v+) ~ D2, associated with n negative samples {v, ~ D. İ E [n]], the widely-used loss for GCL, which is also known as InfoNCE loss [2), can be written as follows:
h(v) Tiv
~D_ |- log( ch(() T k(+t) + ( k(v, 01].
Loer
E et.e map vott N
E
(I)
3.2 Threat Model
Attacker's Goal. We consider an attacker conducts an evasion attack in GCL, Given well-trained GNN encoder h on a clean graph g via GCL, an attacker aims to degrade the performance of h in downstream tasks by injecting noise into the graph. For instance, an attacker may attempt to manipulate social network by injecting fake edges, which could affect the performance of a well- trained h in tasks such as community detection, node classification, or link prediction. The noise can take different forms, including adding/deleting nodes/edges or augmenting node features.
3

---

Attacker's Knowledge and Capability, We assume that the attacker follows the grey-bos setting to conduct an evasion attack. Specifically, the attacker has access to a benign GNN encoder h trained on clean dataset through GCI., and the training data to train downstream classifier is available to the attacker. The model architecture and other related information of the GNN encoder are unknown to the attacker. During inference phase, the attacker is capable of injecting noises to the graph within a given budget to degrade the performance of target nodes/graphs in downstream tasks. In this paper, we focus perturbations on the graph structure A, i.e, only structural noises such as adding new edges/nodes are injected into the graph as structure attack is more effective than feature attack III 24 43], We leave the extension to feature attack and defense of GCL as future work. We denote 8 E {0, 1 as the structural noise to node/graph v, where N denote the number of nodes on the graph v or K K--opp subgraph of node v and 6; = 1 indicates the addition of a noisy edge to v in the i-th entry, and its Lo-norm |1ōl|o indicates the number of noisy edges. We then have the perturbed version of by the attacker, denoted v' v 3 8.
3.3 Problem Statement
Our objective is to develop a certifiably robust GCL. We aim to train a GNN encoder that exhibits provably benign behaviors in downstream tasks. The problem can be formulated as follows:
Problem 1. Given a GNN encoder h, a node or graph V. Let v' v @ 6 denote the perturbed version of v by the attacker, where the structural noise 5 with ||8llo S k is injected into v. Suppose that ex is the latent class of and f is the downstream classifier. Our goal is to develop a certifiably robust GCL for h such that for any + c², the representation of under can satisfy the following requirement in downstream tasks:
mnl',c': min esc*
= = -() c)) 0.
(2)
where mly', :h: is the worst-case margin of h((')) between et and y in the downstream task for any c + c², and (P((((())) = c) denotes the probability of the representation h(v') being classified into class by f in the downstream task. Eq. 2 implies that f(h(v') = c² for any d within the budget k i.e., h is a certifiably robust at (v,c*) when perturbing at most k edges.
Certifying Robustness for GCL
In this section, present the details of our RES, which aims to provide certifiable robustness for GCL models. There are mainly three challenges: (i) how to define the certified robustness of GCL; (ii) how to derive the certified robustness; and (iii) how transfer the certified robustness of GCL to downstream tasks. To address these challenges, we first define certified robustness for GCL in Sec. 4.1 We then propose the RES method to derive the certificates and theoretically guarantee certifiable robustness in Sec. 4.2 Finally, we show that the certifiably robust representations learned from our approach are still provably robust in downstream tasks in Sec. 4.3
4.1 Certified Robustness of GCL.
To give the definition of certified robustness of GCL, we first give the conditions for successfully attacking the GNN encoder. The core idea behind it comes from supervised learning. where the objec- tive is to judge whether the predictions of target nodes/graphs are altered under specific perturbations. Inspired by 40, consider the following scenario of a successful attack against the GNN encoder.
Given a clean input v, with positive and negative samples + and v used in the learning process of GCL, respectively, we consider v' = @ 6, where å represents structural noise v and v is the attack target v. The attacker's ' goal is to produce an adversarial example v' that can deceive the model into classifying GCL, we say that h has been successfully attacked at v if the cosine similarity s (h(v'). ).h(v") +)) is less than s (h(v"), h(vv)))) )). This indicates that v' is more similar to v than to v in the latent space. Otherwise, we conclude that h has not been successfully attacked. This definition of successful attack provides the basis for the definition of certified robustness of GCL. The formal definition of certified robustness problem for GCL is then given as
as similar v Formally, given a well-trained GNN encoder h via
Definition (Certified Robustness of GCL.). Given a well trained GNN encoder via GCL. Let v be clean input. t is the positive sample of v and V- [[V , . denotes all possible negative

---

samples of v²,, which are sampled as discussed in Sec. 3.1 Suppose that v' is a perturbed sample obtained by adding structural noise to v, where ||óllo S k. and -)) is cosine similarity function. Then, is certifiably 16- lk-robust at (v, vt) if the following inequality is satisfied:
(3) Similar to the supervised certified robustness, this problem is to prove that the point v' = 4B 6 under the perturbation within budget & is still the positive sample of v-_ However, unlike the supervised learning, where we can estimate the prediction distribution of v by leveraging the labels of the training data, it is difficult to estimate such distribution in GCL because the label information is unavailable. To address this issue, we first consider space IB for a sample vt, where each sample within it is the positive sample of v+. Formally, given a sample v with the latent class et from the probability distribution D. [By' )) is defined as
((h(v")h((")) > max h,(v)) vo ||6||o S k. v EV
(4) GCL maximizes the agreement of the positive pair in the latent space and assume access to similar data in the form of pairs v.) that comes from distribution D. given the latent class ct. Thus, it is natural to connect the latent class and the similarity between representations. The probability that v is the positive sample of vt can be given by the following theorem.
BBv = (vlv
Theorem 1. Let B(v") be space around vt as defined in Eq. ( Given an input sample v and GNN encoder h learnt by GCL in Eq. ① the probability of v being the positive sample of vt is:
Pr(v E B(y h; = exp [ [-(- s(h(vv,hi(v) 1) yo).
(5)
a
where s(s,)) is the cosine similarity function. a, a > 0 are Weibull shape and scale parameters 44
The proof is in Appendix C.I Theorem D manifests that we can derive the probability of v being the positive sample of vt based on the cosine similarity under h, providing feasible way study the certified robustness problem for GCL without the label information.
4.2 Certifying Robustness by the Proposed Randomized EdgeDrop Smoothing (RES)
With the definition of certifiable robustness of GCL, we introduce our proposed Randomized Edgedrop Smoothing (RES), which provides certifiable robustness for GCL. RES injects randomized edgedrop noise by randomly dropping each edge of the input sample with a certain probability. We will also demonstrate the theoretical basis for the certifiable robustness of GCL achieved by RES.
Firstly, we define an randomized edgedrop noise for v that remove each edge of v with the probability 3. Formally, given a sample v. the probability distribution of e for is given as:
(6) where v; denotes the connection status of i-th entry of Given a well-trained GNN encoder via GCL and noise with the distribution in Eq. (6). the smoothed GNN encoder g is defined as:
P(e: 0lv: = 0) = 1, P(G: = 0jv, = 1) 3, and F(e: = 1|v; 1) = 1 3,
g(v) = lu(v @ c). where v e E B(arg max IP(v @ c E B))):
GEV
Here V is the set of all nodes/graphs in the dataset. It implies y will return the representation of @ d whose latent class is the same as that of the most probable instance that v $ e is its positive sample. Therefore, consider the scenario where some noisy edges are injected into a clean input v. resulting in perturbed sample v'. With a smoothed GNN encoder g learnt through our method, if we set / to a large value, it is highly probable that the noisy edges will be eliminated from v'. Consequently, by running multiple randomized edgedrop on and v', majority of them will possess identical structural vectors, that is, v O v' @ G, which implies v and v' will have the same latent class and the robust performance of v' in downstream tasks. We can then derive upper bound on the expected difference in vote count for each class between v and v'. With this, we can theoretically demonstrate that is certifiably robust at v against any perturbation within specific attack budget. Specifically, let Pv+ A (v) = IP(v E B(y+); h) for simplicity of notation, Pv+ (v ( e) denotes a lower bound on Pvt (v @ c) with (1 - a:) confidence and Pv, (v $ c) denotes a similar upper bound, the formal theorem is presented as follows:
Theorem 2. Let v be a clean input and v' = v 8 be its perturbed version, where | s k. V- ( .. } is the set of negative samples of v. ffror all v. E V
Pot a (v @ t) max Py; d (v @ 2A,
(8)
v.
5

---

Dropped edge
Augmented Graph G
Edge-drop Graph Ø
Representations Z
Unlabeled
GNN Encoder
Maximize
Agreement
GNN Encoder
Input Graph
Augmented Graph G
Representations Z
Figure 1: General Framework of training GNN encoder via RES.
where (*)
3 and e = ||v @ ello denotes the number of remaining edges of v after injecting E. Then, with a confidence level of at least a, we have:
(
P @ +) max Pv, ,n (v' @e..
vTEV-
The proof is in Appendix C.2 Theorem theoretically guarantees that of v' is still the positive sample of v with (1 confidence if the worst-case margin of v O under h is larger than 2A, which indicates that the certified robustness of h at (v, (v.v*) is holds in this case. Moreover, it also paves us efficient way to compute the certified perturbation size in practical (See in Sec. 5.2)
2
4.3 Transfer the Certified Robustness to Downstream Tasks
Though we have theoretically shown the capability of learning lý-certifiably robust node/graph representations with RES, it is unclear whether the certified robustness of the smoothed GNN encoder can be preserved downstream tasks. To address this concern, we propose a theorem that establishes a direct relationship between the certified robustness of GCL and that of downstream tasks.
Theorem 3. Given GNN encoder h trained via GCL and an clean input v. vt and V
{Vi.... . are the positive sample and the set of negative samples v. respectively. Let et and G denote the latent classes of and v; respectively. Suppose is the downstream classifier that classify a data point into one of the classes in C. Then, we have
P(f(h(v)) c+ max P(S(((v)) = =
(10)
vT C.3 By applying Theorem
The proof is in Appendix
3 we can prove given v's perturbed version
v' 5, where |0 S k. if and v' satisfy Eq. and Eq. (9h in Theorem 2 we have
P(f(h(v' @ e)) = =c+)> max v7 vTeV
P(F(h(v' @ +e)) o )
A |o S k,
(11)
which implies provable 1 -ertifiie robustness retention of h at (v, ct) in downstream tasks.
5 Practical Algorithms
In this section, we first propose simple yet effective GCL method to train the GNN encoder h robustly. Then we introduce the practical algorithms for the prediction and robustness certification.
5.1 Training Robust Base Encoder
Theorem holds regardless how the base GNN encoder h is trained. However, introducing random- ized edgedrop noise solely to test samples during the inference phase could potentially compromise performance in downstream tasks, which further negatively impact the certified robustness perfor- mance based on Eq. In order to make can classify and certify (v.ct) c+)) correctly and robustly, inspire by [45] we propose train the base GNN encoder h via GCL with randomized edgedrop noise. Our key idea is to inject randomized edgedrop noise to one augmented view and maximize the probability in Eq. by using GCL maximize the agreement between two views. Fig. [ gives an illustration of general process of training the base GNN encoder via our RES. Given an input graph g, two contrasting views Gj and Gj are generated from through stochastic data augmentations. Specifically, two views generated from the same instance are usually considered as positive pair, while two views constructed from different instances are considered as negative pair. After that, we inject the randomized edgedrop noise to one of the two views G: and obtain G.'. Finally, two GNN encoders are used to generate embeddings of the views and contrastive loss applied to maximize the agreement between G,' and Gy. The training algorithm is summarized in Appendix D

---

5.2 Prediction & Certification
Following 44, 24), we then present the algorithm to use the smoothed GNN encoder g(v) in the downstream tasks and derive the robustness certificates through Monte Carlo algorithms.
Prediction on Downstream Tasks. We draw j samples of h(v + e). corrupted by randomized edgedrop noises. Then we obtain their predictions via the downstream classifier. If ca is the class which has the largest frequency Hea among the μ predictions, CA is returned as the final prediction.
Compute Robustness Certificates. One of robustness certificates is the certified perturbation size, which is the maximum attack budget that do not change the prediction of an instance no matter what perturbations within the budget are used. To derive the certified perturbation size of an instance v, we need to estimate the lower bound Pv+.N (v @ e) and upper bound Pv. _n (V @ ( E)in Eq. Since challenging to directly estimate them in GCL, inspired by Theorem if the prediction of h(v @ c) in downstream tasks correct, v 3 will also be the positive sample of v under h, which indicates the connection between Pv+.A (v @ e) and the probability of correctly classified in the downstream tasks. Formally, given label set C for the downstream task, let PA denotes the lower bound of the probability that h(v @ c) is correctly classified as сд in the downstream task, pg is the upper bound of the probability that h(v @ e) is classified for c E C\(a)). we have the following probability bound by a confidence level at least O::
Put (v @ c) = PA B
cci Me Mea + 1), Pv. +6) PB = min (max Pe, 1, - 1-p)) (12) opes
where Pe- B(1 :e + 1, Me), Vc # CA. and B(q; u, w) is the g-th quantile of a beta distribution with shape parameter u and w. After that, we calculate A based Theorem 2 and the maximum i that satisfies Eq. Bls the certified perturbation size.
6 Experiments
In this section, we conduct experiments to answer the following research questions: (Q1) How robust RES under various adversarial attacks? (Q2) Can RES effectively provide certifiable robustness for various GCL methods? (Q3) How does RES contribute to the robustness in GCL?
6.1 Experimental Setup
Datasets. We conduct experiments on 4 public benchmark datasets for node classification, i.e., Cora, Pubmed [47) Coauthor- Phathhs-PPhyics (48) and OGB-arxi [49], and widely used dataset for graph classification i.e., MUTAG, PROTEINS (50) and DGB-molhiv [4]. We use public splits for Cora and Pubmed, and for five other datasets, we perform 10/10/80 random split for training, validation, and testing, respectively. The details and splits of these datasets are summarized in Appendix G.1
Attack Methods. To demonstrate the robustness of RES to various structural noises, evaluate RES on 4 types of structural attacks in an evasion setting, i.c., Random attack, Nettack [TI. PRBCD (51]. CLGA [16] for both node and graph classification. In our evaluation, we first train GNN encoder on a clean dataset using GCL, and then subject RES to attacks during the inference phase by employing perturbed graphs in downstream tasks. Especially, CLGA is poisoning attack methods for GCL. To align it with our evasion setting, we directly employ the poisoned graph generated by CLGA in downstream tasks for evaluation. The details of these attacks given in Appendix G.2
Compared Methods. We employ 4 state-of-the-ard GCL methods, i.e., GRACE 30), BGRL 52 DGI (31) and GraphCI. (9, as baselines. More specifically, GRACE, BGRL and DGI are for node classification, GraphCL and BGRL are for graph classification. We apply our RES on them to train the smoothed GNN encoders. Recall one of our goal is to validate that method can enhance the robustness of GCL against structural noises, we also consider two robust GCL methods (i.c., Ariel [15] and GCL-Jaccard [12) and two unsupervised methods (i.c., Node2Vec [53] and GAE (54)) as the baselines. All hyperparameters of the baselines are tuned based on the validation set to make fair comparisons. The detailed descriptions of the baselines given in Appendix G.3
Evaluation Protocol. this paper, we conduct experiments on both transductive node classification and inductive graph classification tasks. For each experiment, a 2-layer GCN is employed as the backbone GNN encoder. We adopt the common used linear evaluation scheme [II, where each model is firstly trained via GCL and then the resulting embeddings are used to train and test
7

---

Table 1: Robust accuracy results for node classification.
Dataset
Graph
Node2Vec
GAE
GCL-Jac.
Ariel
GRACE
RES-GRACE
Raw
67.6+1.0
76.8+10.9
76.1=2.0
79.8-1.6
17.141.6
79.7+10
Cora
Random
57.7+0077
74.2+00.9
74.1=2.0
76.3+0.6
74.5+2.11
79.1=:1.2
CL.GA
64.7+00.7
72.7+1.3
73.7-1.2
76.6+0.4
74.9+2.0
78.2++1.0
PRBCD
63.31:3.
75.642.11
75.3=
75,610.2
75.8:2.55
1.7
Raw
66,4422.0
78.440.4
78.2-2.7
78.041.1
79.542.9
79.5
Pubmed
Random
56,8+1.4
718++0
75.8-2.4
75.9+0.2
75.0=110
78.2-+0.9
CLGA
1.29+1.2
77.6+0.5
76.2-2.8
77.5+1.11
76.6+2.5
7..3++1.1
PRBCD
5..911
74.812.5
73.1=2.0
73.51:..
73.242.3
18.8
Raw
92.910.1
95.2-10.1
94.1-0.3
95,310.3
94.0410.4
94,7110.2
Physics
Random
85.7+:0.3
93.7=:0.1
93.4=0.3
93.8+0.11
92.6+0.5
94.2--0.3
PRBCD
81,8+0.66
91.1+0.7
91.6=0.2
91,0+0.9
89.2+0.6
94.1+002
Raw
64.610.1
61.5
64.7-0.2
64.7
65.1
65.2.0.1
OGB-arxiv
Random
52.4:0.1
57.410.5
59.0-0.1
59,4004
59.0+0.2
60.0-1.11
PRBCD
56,510.5
54.1
56.5
$7.010.9
58.710.4
1.44
0.8g
0.7
Certined Accurscy
$=0.1
Certiba Accuracy
Gettiee Mcqurayy
0.6
p-0:1
$m0.95
5-0 9
p-0.1
0.5
f-0.1
f=0.9
6=0.9
f-0.9
0.4
p-0.95
0.3
3e0
03
6-0.95
0.3
6-0.96
p=0.999
P- 9.09999
0.2
0.1
0.1
0.00
Perturbation Size
Porturbation Size
Perturbation Size
Perturbation Size
(a) Cora
(h) OGB-arxiv
(c) MUTAG
(d) PROTEINS
Figure 2: Certified accuracy of smoothed GCL
l2 regularized logistic regression classifier. The certified accuracy and robust accuracy test nodes are used to evaluate the robustness performance. Specifically, certified accuracy [46] [4] denotes the fraction of correctly predicted test nodes/graphs whose certified perturbation size is smaller than the given perturbation size. Each experiment is conduct times and the average results are reported.
6.2 Performance of Robustness
To answer Q1, we compare RES with the baselines on various noisy graphs. We also conduct experiments to demonstrate that RES can improve the robustness against different noisy levels, which can be found in Appendix I.2 We focus on node classification as the downstream task on four types of noisy graphs, i.e., raw graphs, random attack perturbed graphs, CLGA perturbed graphs and PRBCD perturbed graphs. The perturbation rate of noisy graphs is 0.1. The details of the noisy graphs are presented in Appendix G.2 GRACE is used the target GCL method to train GCN encoder. The smoothed version of GRACE is denoted as RES-GRACE. The results on Cora, Coauthor-Physiee and OGB-arxiv are given in Table From the table, we observe: (i) When attack is applied on achieve state-of-the-art performance, especially on large-scale
the clean graph, our RES-GRAS datasets, which indicates RES is beneficial to learn good representation by injecting random edgedrop noise to the graph. (ii) The structural noises degrade the performances of all baselines. However, its impact RES-GRACE is negligible. RES-GRACE outperforms all baselines including two robust GCL methods, which indicates RES could eliminate the effects of the noisy edges. More results on graph classification are shown Appendix
6.3 Performance of Certificates
To answer Q2, use certified accuracy the metric evaluate the performance of robustness certificates. We choose GCN as the GNN encoder and employ our method on GRACE (30) and GraphCL [9] for node classification and graph classification, respectively. We select the overall test nodes as the target nodes and set μ = 200, (1 a) = 99.9% to compute the certified accuracy. The results for various / are shown in Fig. where the x-axis denotes the given perturbation size. From the figures, we can observe that 3 controls the tradeoff between robustness and model utility. When B larger, the certified accuracy on clean graph is larger, but drops more quickly as the perturbation size increases. Especially, when 3 0.999, the certified accuracy is nearly independent of the perturbation size. Our analysis reveals that when on the graph, which benefits the performance of RES under no attack, but also results in more noisy edges being retained on the noisy graph, leading to lower certified accuracy. Conversely, when large, less structural information is retained the graph, which may affect the performance of RES
low, more structural information is retained

---

Robust Accuracy (%)
Robose Accuracn acy (86
Robust Accuracy (%)
80
Base
80
60
FLIP
Base
Robust Accuracy
100
RES
RES.a
RES..5
RCS
R2S
Our
100
RES-0915
RBS
RES-JK5
Ours
FLIP
Ours
80
80
60
40
Ours
20
40
20
Cora
Pubmed
Cora (b) Noisy
Pubmed
Cora
OGB-arxiv
Cora (d) Noisy
OGB-arxiv
(a) Clean
(c) Clean
Figure 3: Ablation Study Results: Comparisons (a) and (b) with FLIP, (c) and (d) with RES
under no attack, but also results in fewer noisy edges remaining on the noisy graph, leading to higher
certified accuracy for larger perturbation sizes.
6.4 Ablation Study
To answer Q3, we conduct several ablation studies to investigate the effects of our proposed RES method. More results of ablation studies are shown in Appendix We also investigate how hyperpa- rameters (1 a. and y affect the performance of our RES, which can be found in Appendix K
Our first goal is to demonstrate RES is more effective in GCL compared with vanilla binary ran- domized smoothing in [24]. We implement a variant of our model, FLIP,, which replaces the random edgedrop noise with binary random noise (24), thereby flipping the connection status within the graph with the probability B. For our method, we set 3 0.9, a 99%, and µ 50. For FLIP, to ensure a fair comparison, we set a = 99% and 50, and vary 3 over (0.1, 0.2, 0.9) and select the value which yields the best performance on the validation set of clean graphs. The target GCL method is selected as GRACE. We compare the robust accuracy of the two methods on the clean graph and noisy graph under Nettack with attack budget 3. The average robust accuracy and standard deviation on Cora and Pubmed are reported in Fig. 3 (a) and (b). We observe: (i) RES achieves better results on various graphs (i.e., clean and noisy graph) compared to FLIP and the base GCL method. (ii) FLIP performs much worse than the base GCL method and RES on the clean graph, suggesting that vanilla binary randomized smoothing ineffective in GCL. That is because FL.PP introduces excessive noisy edges, which in turn makes it challenging for GCL to learn accurate representations.
Second goal is understand how RES contributes the robustness of GCL. We implement several variants of our model by removing structural information in the training and testing phases, which are named RES ssys. where E 1, and j E {0, 1} denote the number of removed structures in the training and testing phases, respectively. For our method, we set 8 = 0.9, 1 a 99% and = 50. We compare the robust accuracy on clean and noisy graphs and use PRBCD to perturb 10% of the total number of edges in the graph (before attack) for noisy graphs. The overall test set was selected as the target nodes. The results on Cora and OGB-arxiv are shown Fig. (c) and (d). We observe: (i) Our method significantly outperforms the ablative methods on various graphs, corroborating the effectiveness of randomized edgedrop smoothing for GCL. (ii) Our method and RES isoS achieve better robust accuracy on various graphs compared to other ablative methods. This is because dropping edges in only one augmented view during training both alleviates over-fitting and increases the worst-case margin, which is helpful for robustness and model utility. (iii) RES2s/s and RES,st perform worse than other methods because the absence of structural information in training and test phases, highlighting the importance of structural information in GCL. Moreover, the ablation studies on the effectiveness of our approach for training the GNN encoder are Appendix J.I
7 Conclusion
In this paper, we present the first work to study the certifiable robustness of GCL. We address the existing ambiguity in quantifying the robustness of GCL to perturbations by introducing unified definition for robustness in GCL. Our proposed approach, Randomized Edgedrop Smoothing, injects randomized edgedrop noise into graphs to provide certified robustness for GCL on unlabeled data, while minimizing the introduction of spurious edges. Theoretical analysis establishes the provable robust performance of our encoder in downstream tasks. Additionally, we present an effective training method for robust GCL Extensive empirical evaluations on various real-world datasets show that our method guarantees certifiable robustness and enhances the robustness of any GCL model.

---

8 Acknowledgements
This material is based upon work supported by, or in part by, the National Science Foundation (NSF) under grant number IIS-1909709 the Army Research Office (ARO) under grant number W911NF21: 1-0198, and Department of Homeland Security (DNS) CINA under grant number E205949D. The findings in this paper do not necessarily reflect the view of the funding agencies.
References
[1] Will Hamilton, Zhitao Ying, and Jure Leskovec, Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
[2] Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang. Quan Yu, Jun Zhou, Shuang Yang. and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In IEEE International Conference on Data Mining, pages 598-607, 2019.
[3] Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learning of representations via graph neural networks. Nature Machine Intelligence, 4(3):799- 287, 2022.
[4] Thomas N. Kipf and Max Welling. semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[5] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[6] Teng Xiao, Zhengyu Chen, Donglin Wang, and Suhang Wang. Learning how to propagate messages in graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1894-1903, 2021.
[7] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
[8] Fan-Yun Yun Sun, Jordan Hoffmann Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In International Conference Learning Representations, 2020.
[9] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang. and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, pages 5812-5823, 2020.
[10] Hanjun Dai, Hui Li, Tian Tian, Xin Huang. Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. International Conference on Machine Learning, 2018.
[11] Daniel Züggner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847-2856, 2018
[12] Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Pin-Yu Chen, Teui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In IJCAI, pages 3961-3961 2019.
[13] Binghui Wang. Tianxiang Zhou, Minhua Lin, Pan Zhou, Ang Li, Meng Pang, Cai Fu, Hai Li, and Yiran Chen. Evasion attacks to graph neural networks via influence function. arXiv preprint 00Xi0:2009.00203, 2020.
[14] Nikola Jovanović, Zhao Meng. Lukas Faber, and Roger Wattenhofer. Towards robust graph contrastive learning. arXiv preprint arXiv:2 10.220022/30 13085, 2021.
[15] Shengyu Feng, Baoyu Jing. Yada Zhu, and Hanghang Tong. Adversarial graph contrastive learning with information regularization. Proceedings of The Web Conference, pages 1362- 1371, 2022.
10

---

[16] Sixiao Zhang, Hongxu Chen, Xiangguo Sun, Yicong Li, and Guandong Xu. Unsupervised graph poisoning attack via contrastive loss back propagatag,,iion In Proceedings of The Web Conference, pages 1322-1330, 2022.
[17] Enyan Dai, Wei Jin, Hui Liu, and Suhang Wang. Towards robust graph neural networks for noisy graphs with sparse labels. In WSDM, pages 181-191, 2022.
[18] Enyan Dai, Limeng Cui, Zhengyang Wang. Xianfeng Tang. Yinghan Wang, Monica Cheng, Bing Yin, and Suhang Wang. A unified framework of graph information bottleneck for robustness and membership privacy. arXiv preprint arXiv:2306.08604 2023.
[19] Yongqiang Chen, Han Yang, Yonggang Zhang, MA KAILI, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In Interaational Conference on Learning Representations, 2022.
[20] Enyan Dai, Minhua Lin, Xiang Zhang, and Suhang Wang. Unnoticeable backdoor attacks on graph neural networks. In Proceedings of the ACM Web Conference 2023, pages 2263-2273, 2023.
[21] Zhenting Wang, Hailun Ding, Juan Zhai, and Shiqing Ma. Training with more confidence: Mitigating injected and natural backdoors during training. Advances Neural Information Processing Systems, 11:66396-34410 2022.
[22] Zhenting Wang, Kai Mei, Hailun Ding, Juan Zhai, and Shiqing Ma. Rethinking the reverse- engineering of trojan triggers. Advances in Neural Information Processing Systems, 35:9738- 9753, 2022.
[23] Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In the ACM SIGKDD International Conference on Knowledge Discov- ery & Data Mining, pages 246 256, 2019.
[24] Binghui Wang, Jinyuan Jia Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 1645-1653, 2021.
[25] Zhidong Gao, Rui Hu, and Yanmin Gong. Certified robustness of graph classification against topology attack with randomized smoothing. In GLOBECOM 2020-2020 IEEE Global Commu- nications Conference, pages 1-6. IEEE, 2020.
[26] Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. In 2020.
Advances Neural Information Processing Systems, pages
[27] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pages 2069-2080, 2021.
[28] Aleksandar Bojchevski and Stephan Günnemann. Certifialle robustness to graph perturbations. Advances in Neural Information Processing Systems, 32, 2019.
[29] Aleksandar Bojehevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pages 1003-1013, 2020.
[30] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
[31] Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2(3):4, 2019.
[32] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference Machine Learning, pages 4116-4126, 2020.
11

---

[33] Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. Simple unsupervised graph representation learning. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 36, pages 7797-7805, 2022.
[34] Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for graphs. Advances in Neural Information Processing Systems, 35:620-633 2022.
[35] Enyan Dai and Suhang Wang. Towards self-explainable graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2021.
[36] Hangfan Zhang, Jinghui Chen, Lu Lin, Jinyuan Jia, and Dinghao Wu. Graph contrastive backdoor attacks. In Proceedings of the 40th International Conference on Machine Learning. 2023.
[37] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairnsss, and explainability. arXiv preprint arXiv:2204.08570 08570, 2022.
[38] Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional net- works under structure perturbations. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1656-1665, 2020.
[39] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khande- parkar. A theoretical analysis of contrastive unsupervised representation learning. In Interna- tional Conference on Learning Representationss pages 0628-563,,22 2019.
[40] Zekai Wang and Weiwei Liu. Robustness verification for contrastive learning. In International Conference Machine Learning, pages 22865-22883, 2022.
[41] Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi-supervised graph classification. In Advances in Neural Information Processing Systems.
[42] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint 1r07iv8807.000
2018
[43] Binghui Wang. Meng Pang, and Yun Dong. Turning strengths into weaknesses: A certified robustness inspired attack framework against graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
[44] Stuart Coles, Joanna Bawa, Lesley Trenner, and Pat Dorazio. An introduction to statistical modeling of extreme values, volume 208. Springer, 2001.
[45] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEEE, 2019.
[46] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, volume 97, pages 1310-1320, 2019.
[47] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[48] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1 2018.
[49] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, volume 33, pages 221 18-18-220 18-22133,, 2020.
[50] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. ICMI. 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
12

---

[51] Simon Geisler, Tobias Schmidt, Hakan Şirin. Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34:7637-7649, 2021.
[52] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representationss 2022.
[53] Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2016.
[54] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
[55] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020.
[56] Ralph Linsker. celf-organization in a perceptual network. Computer, 21(3):105-1177 1988.
[57] Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. arXiv preprini urXiv:2106. 09943, 2021.
[58] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. In Advances in Neural Information Processing Systems, 2021.
[59] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513-330, 2018.
[60] Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang, Tdgia: Effective injection attacks on graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2461-2471, 2021.
[61] Yongqiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In International Conference on Learning Representations, 2022.
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena [62] Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to sulf-supervised learning. In Advances in neural information processing systems, pages 21271-212844 2020.
[63] R Devon Hjelm, Alex Fedorov, Samuel Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Karan Grewal, Phil Bachman,
[64] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Ad- versarial examples for graph data: Deep insights into attack and defense. In IJCAL, pages 4816-4823, 7 2019.
[65] Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An Empirical Study of Graph Contrastive Learning arXiv.org, September 2021.
[66] Sihang Li, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In Proceedings of the 39th International Conference on Machine Learning, 2022.
13

---

A Details of Related Works
A.1 Graph Contrastive Learning
GCL has recently gained significant attention and shows promise for improving graph representations
in scenarios where labeled data scarce [31 32
9 30
27
15 33 32]. Generally, GCL creates two
views through data augmentation and contrasts representations between two views. GraphCL [9] focuses on graph classification by exploring four types of augmentations including node dropping. edge perturbation, attribute masking and subgraph sampling. GRACE [30] and GCA (27) adapt SimCLR [55] to graphs to maximize the mutual information between two views for each node through a variety of data augmentation. DGI [31] applied InfoMax principle [56] to train GNN encoder by maximizing the mutual information between node-level and graph-level representations. MVGRL 32 proposes to learn representations by maximizing the mutual information between the cross-view representations of nodes and graphs. Several recent works [16] 36) show that GCL is vulnerable to adversarial attacks. CL.GA [16] is an unsupervised poisoning attacks for attack graph contrastive learning. In detail, the gradients of the adjacency matrices for both views are computed. and edge flipping is performed using gradient ascent to maximize the contrastive loss. Despite very few empirical works 19, 15 |4 on robustness of GCL, there are no existing works studying the certified robustness of GCL. In contrast, we propose to provide robustness certificates for GCL by using randomized edgedrop smoothing. To the best of our knowledge, our method is the first work to study the certified robustness of GCL.
A.2
Certifiable Robustness of Graph Neural Networks
Several recent studies investigate the certified robustness of GNNs in the supervised setting 23
29
26
24
25
37 Zügner et al. 23 are the first to explore certifiable robustness with respect to
38 extend the analysis to certifiable robustness under topological attacks. For instance, Bojchevski et al. 28 propose a aaacchhand-buund algorithm to achieve tight bounds on the global optimum of certificates for topological attacks. Bojchevski et al. [29] further adapt the randomized smoothing technique sparse settings, deriving certified robustness for GNNs. This approach involves injecting random noise into test samples to mitigate the negative effects of adversarial perturbations. Wang et al. [24] further refine this technique to provide theoretically tight robust certificates. Our work is inherently different from setting; while we provide a unified definition to evaluate and certify the robustness of GCL for unsupervised representation learning. (ii) theoretically provide the certified robustness for GCL in the absence of labeled data, and this certified robustness can provably sustained in downstream tasks. (iii) we design an effective training method to enhance the robustness of GCL.
node feature perturbations. Subsequent works [28 26 29 24
them: (i) existing work focues on the certified robustness of GNN under
B Preliminary of Randomized Smoothing
One potential solution for achieving certified robustness in GNNs is binary randomized smoothing presented in (24] Specifically, consider a noisy vector e in the discrete space {0, 1
P(e. = 0) 3, 1)= 3,
(B.1)
where 1, 2, 2, ... .N. This indicates that the connection status of the i-th entry of will be flipped with probability - 3 and preserved with probability 3. Given a base node or graph classifier f(v) that returns the class label with highest label probability, the smoothed classifier g is defined as:
arg max IF [[[(v D = v),
(B.2)
yEY
where D' denotes the label set, and T represents the XOR operation between two binary variables. which combines the structural information of both variables. P(f(v @ e) = y) is the probability that the base classifier I predicts class y when random noise is added to v. According to (24), by injecting multiple to and returning the most likely class Ya (the majority vote), if it is holds that:
min P([(v e) = ya) > max P(ʃ(v @ E) v), s.t. ||e|lo < k, ツサリA
(B.3)
where yA is the class with the highest label probability. Then we can guarantee there exists certified perturbation size A such that for any perturbation 8 with ||ō]|o k. the predictions of $ d will
14

---

remain unchanged. that is, 9(v + 08 (v,yA) when perturbing at most & edges. For more deatils of the proof, please refer [24].
VA- Thus, f is certifiably robust
However, directly applying the vanilla randomized smoothing approach to certify robustness in GCL inapplicable. This approach may require injecting random noise into the entire graph during data augmentation, resulting in an excessive number of noisy/spurious edges that can significantly harm downstream task performance, particularly for large and sparse graphs. In contrast, our proposed method, Randomized Edgedrop Smoothing (RES), aims to prevent the introduction of excessive spurious edges in graphs. RES achieves this by injecting randomized edgedrop noises, where observed edges are randomly removed from the graphs with a certain probability. Additionally, we propose an effective training method for robust GCL. Our experimental results in Sec. demonstttt that our method significantly outperforms the ablative method, FLIP, that directly applies vanilla randomized smoothing [24] in GCL.. Specifically, on the clean Cora and Pubmed graphs, our method achieves accuracies of 82% and 85.6% respectively. On the Nettack perturbed [1]] Cora and Pubmed graphs, our method achieves robust accuracies of 79.4% and 82.5%, respectively. In contrast, FLIP achieves only up to 27% and 42% robust accuracies on the Cora and Pubmed datasets, respectively. These results strongly validate the effectiveness our RES approach,
C Detailed Proofs
C.1 Proof of Theorem 1
To begin, we provide a formalization of similarity in relation the latent class.
Given a GNN encoder h and an input sample v, which consists of a positive sample v+ and a negative sample v input sample v with positive sample v and negative sample v according to Def. 1 we assume that ct, c E C represent the latent classes of v and v in the latent space of h, respectively. These latent classes are based on the distribution r over C. we assume that ct, e E C are the latent class of v and v in the latent space of h, respectively, which are randomly determined based on the distribution v on C. Similar data h(vv,, h(v+) are i.i.d. draws from the same class distribution Dat, whereas negative samples originate from the marginal of Dsim. which are formalized as follow:
D Deim (v, E Det (v)D.: (v+). C7
(C.4)
(v== De (v").
cm
Since classes are allowed overlap and/or be fine-grained 39, this is plausible formalization of "similarity". The formalization connects similarity with latent class, thereby offering a viable way to employ the similarity between samples under the latent space h for defining the probability of being the positive sample of v..
Lemma 1 (The Generalized Extreme Value Distribution 44]). Let VI, V2, be a sequence of i..d samples from common distribution function F. Let Mx max(vi,""- vN }. indicting the maximum of "v J. Then if (aN > 0} and (by E IR are sequences of constants such that
[M - bN)/aN S x} + G(z),
(C.5)
where G is non-degenerate distribution function. It is member of the generalized extreme value family of distributions, which belongs to either the Gumbel family (Type I), the Fréchet family (Type II) or the Reverse Weibull family (Type III) with their CDFs as follows:
G(z) exp(- expl- b
Gumbel family (Type I):
E R,
a
0,
zeb,
Fréchet family (Type II::
G(z)
eep - ((ا Jo}, z2b,
(C.6)
(expl((brs (1-=-)--a) z<b,
Reverse Weibull family (Type III):
G(z)=
1,
z2b,
where > 0, 6 R. and a > 0 are the scale, location and shape parameters, respectively.
15

---

Theorem 1
Let B(v+) ) be space around v as defined in Eq. 4 Given an input sample v and GNN encoder h learnt by GCL in Eq. [ the probability v being the positive sample of vt is:
E E B(vT) exp [- - 1) )9]
(C.7)
where s(;,-) is the cosine similarity function. a, d > 0 are Weibull shape and scale parameters 44
Proof. We first assume (h(v1). h(v2)).... are i.dd samples under the latent space h. Then, suppose V i vn is the set of negative samples of v. We assume there exists a continuous non-degenerate margin distribution M, which is denoted as follows:
M = min D;, with D; = (1 s(h(v(),, (allvt),,vvy N(v, )))
(C.8)
xE(n]
where M, D, E [0, 1], and s(:,)) is the cosine similarity function. M indicates the half of the minimum distance between hivT)) and h(v;).
According to Lemma [ we know that there exists G(2) in the three types of generalized extreme value family. And since Lemma| iss applied to the maximum, refer to Eq. (C.8), we transfer the variable to M == maX4e[n] -D,, Since -D; D; is bounded (-D; < 0). let = O, the marginal distribution of D; series, for i 1, 2, ..., can be Reverse Weibull family. Therefore, the asymptotic marginal distribution of M fits into the Reverse Weibull distribution:
G(z) 11, [exp(-(=))0))
z<0,
z20
where a >> 0 is the shape parameter and a the scale parameter. Compared to Eq. (C.6) here, b = 0 because - D; is bound D2 O). We use margin distances Dj of the À closest samples with v to estimate the parameters a and a, which means to estimate W of the distribution function W.
(/l(vv))((t))) A(v+)) is larger, v is more possible to be from the same latent class vt, which implies v is the positive sample of vt. Since the distance between h(v)) and ((v+)) can be denoted as - s(h((v),,(v )), the probability of v is the positive sample of + can be written as:
Following Eq. (C.4). if the similarity s(h(v),
P(v BB)
=P(L - -P(L-s(h(v)) s(h(v), ((v+)) min(D1,.... ,D.))
-P(s(h(v),hN( 1) > max(- maxt-Di,.". - -Da))
(C.9)
-P(M < s(b(v),h(v+)) 1)
= -W(s(h(v), 1).
Let 6n 0, an and s(h(v), h(v h(v+))(++))))))))))))))) since =
0, we rewrite
Eq. (C.9) as (C.7 according to Lemma
C.2 Proof of Theorem
For simplicity of notation, let Pv- i (v) = P(v E B)v+);h). Then, given a randomized edgedrop noise D. with the following probability distribution:
Ple, 0/v, 0) = 1, P(e+ 0lv, 1) 3, and (P(e, 1/v, 1) 1 3, where e is the i-entry of noisy vector and v; the connection status of i-th entry v. Then, we let
(C.10)
inf P.- (v @ e),, Pv +e) = sup (v @e,, P 2 e) eED,
(C.11)
<ED.
where Put (v @ e) and Pv, A @ e) denote the lower bound and the upper bound on Pvt (( $ e).
respectively. The formal theorem is presented follows:
Theorem 2 Let be clean input and v'
8 be its perturbed version, where |10|| < k. V- [V .... Vo } is the set of negative samples of for all v, V
Put @ 6)
Py; a (v @ e) 2A,
(C.12)
-V-
16

---

where
A
3
(C.13)
and l|v denotes the number of remaining edges of after injecting 6, then with confidence level of at least 1 we have:
P O6)> max P PV (V (c).
(C.14)
v; EV
Proof. Suppose V [vt, VI Vn is the set of positive and negative samples of v. For any V; E let (v) = P(v B(v;); h) for simplicity, we have:
Pv,,i(V (v @ c) = P(v B())
(C.15)
Pv, (v' +c) = IP(v' Dc (v:):
As stated by the law of total probability, have:
(v (v @ é) P([v te E BBvs): A [V (c)
+ P([v B(v.): [Vv #c)
(C.16)
Pv, (v 0 6) = P([v
0])
P((v' B B(v:); [[V @6) 0)),
where (v' @ E) n å represent the intersection of the edge sets (v' @e) and 6, that is, the set of edges shared in the two structure vectors. Therefore, for v' eend = 0, it means that noisy edge of exists in (v' @ c), which indicates that O e and v' O are structural identical at all indices, i.e., v +
@ Therefore, we can then derive the following equality:
P([v e (Bv.)): || [(v 4e) no = 0)) P([v' @ e E B(v;); [[v [(v' -e (C.17)
By multiplying P((v' @ () 8 0) in both sides of Eq. (C.17). we have:
P[[v + B(v)); A [[v' @ e) n 0) P((v' + E B(v,); [[V' Be) = 0)) (C.18)
Combining Eq. C.16) with Eq. C.18 results in:
Pv..ilV's @ Pv.. @
=P([v' e A (V @c) P([v Bev: A [(v' n #
(C.19)
Since probabilities are non-negative, we can rewrite Eq. C.19) into the following inequality:
PP(veCC A ((V +c) ( (vc) 0c B(.) 0e) 0))
(C.20)
Applying the conjunction rule, have:
Pv.. (v 2 c) - P((v @6) S Pv. (v +c)
(C.21)
(v. 0 + P @ +
Since (P((' @ @c) = 1- 1 e -= 0), and (v' + @ no implies that remaining edges of @ and v' identical after injecting the random masking noise, we derive the following probability:
P((v' @c) nd
1
(C.22)
d
where denotes the number of remaining edges, and 1: |6| denotes the certified perturbation size. 8d 3)d-++166 represents the probability that (o) noise edges are all dropped and edges of are retained in v' e. Therefore, we have:
P((v' (6
3151 <
A.
(C.23)
(d+10))
17

---

Substituting Eq. (C23 into Eq. (C.21 then Eq. CC.1 can be rewritten as
Pv @e) A bv (v' @e) S ( (e))
(C.24)
Referring to Eq. (C.24). for any vt and corresponding Vi E V we have
Pu+ @c) Pvt P +c) A. Pv, a (v + e) + P (v @c).
(C.25)
Thus, we can derive the following inequality based on Eq. C.25
Pu+aa(V + Put a A2P 0c) A
2 max P P., + ( (v0c) l (v
(C.26)
v7 Vee
2Pv7 Oc),
which can be restated Eq. (.14).
This completes our proof.
C.3 Proof of Theorem
3
In order to transfer the certified robustness of GCL to downstream tasks, we first introduce two loss functions, namely, unsupervised loss and supervised loss. Subsequently, introduce lemma to establish the relationship between GCL and downstream tasks. Finally, theorem is proposed to prove that the certified robustness of GCL is provably preserved in downstream tasks.
Given input sample with its positive sample v and negative samples {vī ..... Vx }. Let h {0, 1]"h - Rd be the GNN encoder based on GCL to obtain representations. The unsupervised loss for h at point is defined as:
Unsupervised Loss
Lun (v:(v:))= = Σ
))),
(C.27)
where logistic loss I(v) = log (1 Σn exp v:)) according to (57 [3]. Note that this loss
essentially equivalent to the InfoNCE loss 42 57 shown in Eq. which is widely-used for GCL.
Linear evaluation, which learns downstream linear layer after the base encoder, a common way to evaluate the performance of GCL model in downstream tasks. Let C be denoted the of latent classes, where C m. We consider the standard supervised learning tasks that classify a data point into one of the classes in C. To connect the GCL task with the downstream classification task, the supervised loss of downstream classitier f at (x, y) defined as:
Supervised Loss
T.sup (x, y: f) = E((((), - )
(C.28)
where / is the same the loss function used in the unsupervised loss in Eq. (C.27) To evaluate the learned representations on downstream tasks, we typically fix and train a linear classifier W E Rxd on the top of the encoder h. Therefore, the supervised loss of h at at (x, y) is defined as:
Leup (x, y: h) = inf
Leup( y; Wh),
(C.29)
WeRmxd
Lemma 2 (Connection between GCL and Downstream Tasks (39 ). Given input sample v with
its positive sample + and the set of negative samples V {v ...., .
.......... C is the set of latent
class with distribution The latent class of v is denoted as ct E C. Suppose any v E V has the latent class E C. Then we have
Lun (v; h) 2 (1 - Lup (v,ctv ct;h)) +
(C.30)
where T
E c0
1lct c. which indicates the expectation that ct CT.
18

---

Proof. Based on the definitions of Lun (v: h) and (v:h) in Eq. (C.27) and Eq. CC.29) we have
Lun(Vi = E
ct DtN ((h(v) (1((v)((((v)) (h(v+) llv )))
E
2 E
((h(v)
[h(v+)] E v--D--
[h(v )
ct xp
VinD
(C.31)
= (1 -T] E
fflctt *c
mnp
(1 - T) Loup (v, (v, 1h) +
This completes proof.
Note that the above bound is similar to Lemma 4.3 in 39 By leveraging our Theorem 2 we can establish the connection between GCL and downstream tasks, and this connection to prove the transferability of the certified robustness of GCL to downstream tasks.
3 Given GNN encoder h trained via GCL and an clean input V. v and V (VI,.... .vn are the positive sample and the set of negative samples of v, respectively, Let et and v- C denote the latent classes v+ and V respectively, Suppose the downstream classifier that classify data point into one of the classes in C. Then, we have
Theorem
P(f(h(v)) ct) max P(f(h(v)) veeV
=c
(C.32)
Proof. Since v is a clean input, according to Eq. C.4 and Sec. 4.1 the positive pair (v. v*) pair of similar data that come from the same class distribution De+ and they have the following relationship:
IP(v E (Bv+t();) h) max PPvv (V)))):
(C.33)
Then, based on Theorem know that PP(v E (B(+));)) is monotonically increasing as s(h(v), ()) increases. Therefore, we have
s(h(v), h(v+)) max (((v),
(C.34)
According to Eq. C.34 we can obtain that:
(ss(h()), A -((())
(C.35)
and the equivalent form of Eq. C.35
given as:
()(h(v+)) s(h(v ))) h(v) 0, Vv E (VT,.... where 5 is the l2 nommaaaliztiion operation on vector v. Then, we can obtain:
(C.36)
(5(h(v*)) s(h(v s(((v))))))))))))))))))))))))))) 0, Vv (VT,
(C.37)
To relate the robustness of GCL that of downstream tasks, we select the negative samples whose latent class e, is different from ct and obtain the following relationship:
> [((((h(+t))
s(h(v))) # # O.
(C.38)
Substitute the left side of Eq. know that:
CC38 into Eq C.27 we have Lun (v: < According to Lemma
Trun (on h)
Lyup (v, ct; h)
<1
(C.39)
Hence, according to the definition of Tosup in Eq. C.29 we have:
F(f(h(v)) = P(f = ) Ve E (GT 5
(C.40)
which means that the logit output the positive latent class et is always larger than any negative latent class e, for Thus, we can rewrite Eq. (C.40) to Eq. C.32 and conclude the proof. D
19

---

Algorithm The Training Algorithm of RES.
Input: G -V, E E).
Output: Trained GNN encoder hgg
1: Randomly initialize 0 for hg;
2: for epoch=1, ...... do
3: Generate two augmented graphs G, and 9j by (:()) ~ T and q3( T;
4: Inject randomized edgedrop noise to Gü
5: Obtain node or graph representation Z, and 2 from 9; and 9j by using he:
6: Update 9 by applying gradient descent to minimize Eq.
7: end for
8:
return ho:
By applying Theorem 3 we can demonstrate that given v's perturbed version v' V + 6, where we have
| lo S k, if and v' satisfy Eq. (8) and Eq. (9) in Theorem 2
P(f(h(v' @ e)) = c max P(f(h(v' +c)) = ) A |o S k
(C.41)
v, eV-
which implies provable 1/ certified robustness retention of h at (v,ct) in downstream tasks. The proof is completed.
D Training Algorithms
We summarize the training method of Sec. 5.1 for training smoothed GNN encoders in Algorithm Specifically, at each training epoch, we first generate two augmented graphs G; and 9j via qi(9) and g, (9), respectively, where (9) and qj (g) are two graph augmentations sampled from an augmentation pool T. The graph augmentation includes edge perturbation, feature masking, node dropping, etc. (line 3). Then we inject randomized edgedrop noise to one of the augmented graphs 9; (line 4). From line to line 10, we train the GNN encoder hg through GCL by maximizing the agreement of representations in these two views. In detail, we apply ha to obtain node graph representations Z, and Zj from G, and Gj, respectively (line 5), then we do gradient descent on based on Eq.
E Discussions
E.1 Difference between RES and Edge-dropping Augmentations in and (58
Our RES is inherently different from the random edge-dropping augmentation GraphCL. and the learnable edge-dropping augmentation in ADGCL [58]: (i) Random edge-dropping is augmentation method to generate different augmented views and maximize the agreement between
9
views, and the learnable edge-dropping (58) is also an augmentation method enhance downstream task performance. However, RES is devised from the robustness perspective, providing certifiable robustness and enhaneing the robustness of any GCL method.
(ii) While random edge-dropping
and learnable edge-drope adge-dropping are only applied to augment graphs for GCL, RES extends beyond this.
Following the generation of two augmented views as shown in Sec. [..1 RES injects randomized edgedrop noise into one augmented view during GCL training. Then, it performs randomized edgedrop smoothing in the inference phase through Monte Carlo, as shown in Sec. 5.2 Specifically, for inference using RES, y samples of hivv @ e) are drawn by injecting randomized edge-drop noise e to v y times. The final prediction is from Monte Carlo, selecting the la predictions with the highest frequency in j samples.
To demonstrate the effectiveness of RES, we further compare ADGCL with RES-GraphCL on MUTAG and PROTEINS. We also add RES-ADGCL into comparisons. More details are shown in Appendix.
E.2 Additional Details of Concatenation Vector
The concatenation vector v is vector to depict the structure of the node/graph for learning represen- tations. For node-level tasks, it represents the connection status of any pair of nodes in the K-hop
20

---

subgraph of the node v. For graph-level tasks, it represents the connection status of any pair of nodes the graph G. To construct such a vector, we select the upper triangular part of the adjacency matrix of the K-hop subgraph of u or the graph 9 and flatten it into the vector, where each item in this vector can denote the connection status of any pair of nodes in the K-hop subgraph of the node e or the graph g.
The motivation for using this notation is that since we focus on perturbations on the graph structure A in this paper, we treat the feature vector of v as constant and use the adjacency matrix of the K-hop subgraph of the node or the adjacency matrix of the graph to represent the structure of the node or graph. For simplicity and clarity, given GNN encoder h and the concatenation vector v of the node the graph G as above, we then omit the node feature matrix X and simply write the node v's representation h, (A, X) and the graph G's representation h(g) as h(v). Therefore, we use a unified notation v to denote the node v or the graph 9, and further facilitate our theoretical derivations.
E.3
Definition of Well-trained GNN encoders
The well-trained GNN encoder is defined as an encoder that can extract meaningful and discriminative representations by mapping the positive pairs closer in the latent space while pushing dissimilar samples away.
To evaluate whether GNN encoder h is well trained not mathematically, we introduce criteria based on the similarity between node/graph representations in the latent space. For each positive pair (v, v+) with its negative samples V (Vi.". Vn clarify that h is well-trained at (v, v+) the following inequality is satisfied:
((l(v,,(v+t)) max -
s(h(v),h(yT)
(E.42)
where s(,,) .) is a cosine similarity function. This implies that h can effectively discriminate from all its negative samples in V and learn the meaningful representations for v in the latent space. Therefore, based on Eq. (F.42), we can further extend the criteria for certifying robustness GCL, which is shown in Definition
E.4 Rationale behind Setting High Values for 3
The proposed robust encoder training method in Sec. 5.1 improves the model utility of GCL. Even setting large 3 for RES, we can still obtain high robust accuracy on clean graphs, further leading to high certified accuracies.
Specifically, as shown in Sec. 6.T certified accuracy denotes the fraction of correctly predicted test nodes/graphs whose certified perturbation size is not smaller than the given perturbation size. It implies that these certified robust samples should also be correctly predicted by RES in the clean datasets. However, the reviewer said, introducing randomized edgedrop solely to test samples during the inference could potentially hurt downstream task performance and further negatively impact the certified robustness based (8. Thus, propose robust encoder training for RES in Sec.55.1jb injecting randomized edgedrop noise into one augmented view during GCL It ensures the samples with randomized edgedrop noises align in latent class with clean samples under the encoder, thereby mitigating the negative impacts of such noises and further benefiting the robustness and certification RES.
F Code
Our code is available at abttppr//ggtubb.co//ettttttssS--
G
Additonal Details of Experiment Settings
G.1
Dataset Statistics
For node classification, we conduct experiments on 4 public benchmark datasets: Cora, Pubmed 47 Amazon-Computers [48] and OGB-arxiv [49), Cora and Pubmed are small citation networks.
Amazon-Computes is network of goods represented nodes, and edges between nodes represent
21

---

that the two goods are frequently bought together. OGB-arxi arxiv is a large-scale citation network. For graph classification, we use 3 well-known dataset: MUTAG. PROTEINS [50] and OGB-molhin [49] MUTAG is a collection of nitroaromatic compounds. PROTEINS is set of proteins that are classified as enzymes or non-enzymes. DGB-molhin a dataset contains molecules, which is adopted from MoleculeNet [59]. Among these datasets, for Cora and Pubmed, we evaluate the models on the public splits. Regarding to the other datasets, Seauthor-Physicee OGB-arxiv, MUTAG, PROTEINS and OGB-molhiv, we instead randomly select 10%, 10%. and 80% nodes/graphs for the training, validation and test, respectively. The statistics details of these datasets are summarized in Table 2
Table 2: Dataset Statistics
Datasets
#Graphs
#Avg. Nodes
#Avg. Edges
#Avg. Feature
#Classes
Cora
2,708
5,429
1,443
7
Pubmed
19,717
44,338
500
3
Seauthor-Physiee
34,493
495,924
8415
5
OGB-arxiv
169,343
1,166,243
128
40
MUTAG
188
17.9
39.6
2
PROTEINS
1,113
39.1
145.6
3
2
OGB-molliv
41,127
25.5
27.5
9
2
G.2
Attack Methods
One of our goals to show RES robust to various structural noises, we evaluate RES on types of structural attacks in evasion setting, i.e., Random attack, Nettack [11], PRBCD [51), CLGA [16] for both node and graph classification. The procedure of the evasion attack against GCL in transductive node classification is shown Algorithm The details of these attacks described following:
1. Random Attack:
We randomly add some noisy edges to the graphs for node classification and graph classification, respectively, until the attack budget is satisfied. Specifically, we consider two kinds of attack settings for node classification, that is, global random attack and targeted random attack. For global random attack, which used in Sec. 6.2] randomly inject some fake edges (10% in our setting) into the whole graph. For targeted attack, we randomly connect some fake edges to the direct neighbors of target nodes.
2. Nettack [I]] It is targeted attacks for node classification that manipulate the graph structure to mislead the prediction of target nodes.
3. PRBCD [T:: It is a scalable global attack for node classification that aims to decrease the overall accuracy of the graph.
4. CLGA [6: It is an unsupervised gradient-based poisoning attack targeting graph contrastive learning for node classification. Since focus on evasion attacks, we directly use the poisoned graph generated by CLGA in the downstream tasks to evaluate the performance and regard it as an evasion global attack.
Moreover, we further consider two graph injection attack methods, i.e., TDGIA 60 and AGIA 61
as baselines to demonstrate the robustness of RES. The details of experimental results are shown in Sec. I.3
G.3 Compared Methods
We select four state-of-ther GCL methods and employ RES on them to train smoothed GNN encoders:
1. GRACE [30
It node-level GCL method which creates multiple augmented views by perturbing graph structure and masking node features. Then it encourages consistency between the same nodes in different views.
2. BGRL 12 Insipred by BYOL 62 is performs graph contrastive learning that does not require negative samples. Specifically, it applies two graph encoders (i.e., online and targeted encoders), and update them iteratively make the predicted representations closer the true representations for each node.
22

---

Algorithm 2 The Evasion Attack Procedure against GCL in Transductive Node Classification
Input: Clean graph G (V. E.V,EX) GNN encoder he, target node with class label perturbation
6, downstream classifier /.
Output: success (i.e., attack successfully or not)
1: Train he on 9 via GCL;
2: Obtain perturbed node o' by adding perturbation å to v;
3: Generate the representation v' as h(v');
4: if f(h(v")) then
5: return success f- false;
6: else
7: return success +- true;
8: end if
3. DGI (31] It state-of-the-art GCL method which adapted from Deep InfoMax maximize the mutual information between local and global features.
63 to
4. GraphCL [9]: is the first work to study GCL at graph-level. Specifically, it constructs four types of graph augmentations and adapts SimCLR [55] to learn graph-level embeddings.
Moreover, we also compare RES-GG with several representative and state-of-the-ar graph represen- tation learning methods and robust GCLs against structural noises:
1. Vec [53]:
It is a traditional unsupervised methods. Its key idea is to perform random walks the graph generate sequences of nodes that capture both the local and global structure of the graph.
2. GAE [54]: It a representative unsupervised learning method which learns now-dimensional representation of graph by encoding its nodes and edges into vector space, and then decoding this representation back into graph structure. It is trained to minimize the reconstruction error between the original graph and the reconstructed graph.
3. GCI--Jaccard: It is implemented by removing dissimilar edges based on Jaccard similarity before and after the training phase, respectively, which is inspired from GCN-Jaccard [64]
4. Ariel 15 It robust GCL method which uses an additional adversarial graph view in graph contrastive learning to improve the robustness. An information regularizer is also applied to stabilize its performance.
G.4 Implementation details
2-layer GCN is employed as the backbone GNN encoder and a common used linear evaluation scheme (31) is adopt in the downstream tasks. More specifically, each GNN encoder firstly trained via GCL method and then the resulting embeddings are used to train and test a lz-regularized logistic regression classifier. GRACE is implemented based the source code published by authors BGRL and DGI methods are implemented based on PyGCL library (65). All hyperparameters of all methods tuned based on the validation for fair comparison. All models are trained on an A6000 GPU with 48G memory.
G.5 Attack Settings
In this paper, assume that the attacker conduct attack in two settings: transductive node classification and inductive graph classification. These two settings are described below:
Transductive Setting: In this setting, test instances (nodes/graphs) are visible during both training the GNN encoder and inference in downstream tasks. Specifically, we first train a GNN encoder h via GCL on clean dataset that includes test nodes to generate node representations. Then, an attacker adds perturbations to the test nodes, causing h to produce poor representations that degrade performance on downstream tasks. For example, an attacker may attempt to manipulate a social network by injecting fake edges, which could affect the performance of
23

---

well-trained h in tasks such community detection, influential node identification, or link prediction.
Inductive Setting: In this setting, test instances only appear in downstream tasks and are invisible during the training phase. This setting is similar to the transductive setting, but the test nodes/graphs are not seen during training. This scenario commonly arises real-world applications such as new drug discovery, where an attacker may attempt to manipulate new molecular graph in the test set to mislead the model, resulting incorrect predictions in downstream tasks.
H Additional Results of the Performance of Certificates
In this section, we extend the experiments in Sec. 6.3 and present comprehensive results on the performance of robustness certificates. Our aim is demonstrate that RES can effectively provide certifiable robustness for various GCL methods. We select GRACE, BGRL, DGI, and GraphCL as the target GCL methods and integrate them with RES. We perform experiments Coauthor- PeauthorPhyysics, and OGB arxiv for node classification tasks, as well as MUTAG, PROTEINS, and OGB-molhiv for graph classification tasks. Certified accuracy selected as the evaluation metric. Specifically, certified accuracy [46] (24) denotes the fraction of correctly predicted test nodes/graphs whose certified perturbation size is no smaller than the given perturbation size. The complete results are reported in Fig. to Fig. 8
Cora, Pubmed,
Certified Accuracy
0.88
Certified Accuracy
0.8
0..8 0.88
Certified Accuracy,
0.6
B=0.1
0.6
B=0.1
0.6
B=0.1
8=0.9
8=0.9
ß=0.9
0.4
B=0.95
0.4
8=0.95
0.4
$=0.95
0.2
8=0.99
0.2
8=0.999
0.2
8=0.999
0.0
2
0.0
2
6
8
0.0
8
10
Perturbation Size
Perturbation Size
Perturbation Size
(a) GRACE
(b) BGRL
(c) DGI
Figure 4: Certified accuracy of RES-GCL on Cora
Certified Accuracy 0.08880.8
Certified Accuracy
Certified Accuracy
-0.8
0.6
B=0.1
0.6
B=0.1
0.6
B=0.1
8=0.9
6=0.9
6=0.9
0.4
0.4
0.4
8=0.95
B=0.95
B=0.95
0.2
0.999
B 0.999
0.2
B 0.999
0.0
0.0
0.0
10
2
4
Perturbation Size
Perturbation Size
Perturbation Size
(a) GRACE
(b) BGRL
(c) DGI
Figure 5: Certified accuracy of RES-GCL on Pubmed
Certified Accuracy 1
Certified Accuracy
Certified Accuracy
11.0
11.0
0.8
8=0.1
0.8
B=0.1
0.8
8=0.1
0.6
8=0,9
0.6
8=0.9
0.6
8=0.9
0.4
8=0.95
0.4
8=0.95
0.4
8=0.95
0.999
0.999
B 0.999
0.2
0.2
0.2
0.0
0.0
0.0
2
4
8
10
2
4
6
8
10
8 10
Perturbation Size
Perturbation Size
Perturbation Size
(a) GRACE Figure 6: Certified accuracy of RES-GCL on Coauthor-Physies
(b) BGRL
(c) DGI
I
Additional Results of the Performance of Robustness
In this section, we provide additional experimental results to further showcase the effectiveness of the RES in enhancing the robustness of GCL against various ad adversarial attacks. More specifically,

---

Cartified Accurarty
0.7
Cestitte Accusscy
0.6
Certiffed Acourao 6
1.0
Cortified Accurscy
1.0
0.5
8-0.1
B=0.9
0.4
B=0.9
6=0.1
0.6
0.8
8-0.1
B=0.9
0.6
0.8
0=0
0.3
8-0.999
9=0,95
0.2
B-0,35
B-0.999
0.4
B
8=0.95
B-0.999
0095
0.1
0.2-
0.2
0.00
10
0.0
10
0.0g
0.0g
Perturbation Size
Perturbation Size
Perturbation Size
Perturbation Size
(a) GR ACE, OGB-arxiv
(b) DGL, OGB-arxiv
(c) GraphCI. OGB-molhiv (d) BGRI, OGB-molliv,
Figure Certified accuracy smoothed
GCL on OGB-arxiv and OGB-molliv
Certified Anturacy
0.8
Cercilted Accuracy
0.7
Certifted Accuracy
0077
Ceraiied Accuracy
00.6
0.6
p=0.9
p=0.1
0.5
B-0.1
8-0.9
0.5-
8-0.9
8-0.1
0.4
8=0.1
8m0.9
0.4
8-0 0.95
0.3
8=0.95
0.3-
8=0.95
8=0.95
0.2
B- 999
p=999
p=0.999
0.2
0=9.999
0.1
0.1
0.0
10
0.0
10
0.0
0.0g
Porturbation
Perturbation
Perturbation
Perturbation
(a) GraphCL, MUTAG (b) BGRL, MUTAG (c) GraphCL, PROTEINS (d) BGRL, PROTEINS
Figure 8: Certified accuracy of smoothed GCL on MUTAG and PROTEINS
in Sec. we show the comparison results of RES with the baselines on graph classification. In Sec. we conduct experiments to demonstrate GCL with RES is resistant to different levels of structural noises. In Sec. I.3 we present the comparison results of three target GCL methods (i.e., GRACE, BGRL, DGI) against three types of structural attacks (i.e., Random, CLGA and PRBCD) on node classification. Sec. [.4] we present additional experimental results of two advanced GCL methods (i.e., ADGCL, (58) and RGCL. (66]) graph classification.
I.1 Robust Performance on Graph Classification
In this subsection, we conduct experiments on graph classification to demonstrate the effectiveness of our method in this downstream task. Due to the limited availability of open-source attack methods specifically designed for graph classification, we utilize random attacks as the attack method. However, we believe that our method is robust against other attack methods as well. Specifically, we select GraphCL as the target GCL methods. The perturbation rate of random attack is 0.1. The smoothed version of GraphCI. is denoted as RES- FES-GGrahCIL. The results on MUTAG and PROTEINS are given Fig. From the figure, we observe: (i) When no attack is applied to the raw graphs, GES-GG achieves comparable performance to the baseline GraphCI. (ii) When attacks are conducted on the noisy graphs, GES-GraphCLL consistently outperforms the baseline on both the MUTAG and PROTEINS datasets. This result demonstrates the effectiveness of our method in enhancing the robustness of GraphCL against adversarial attacks.
Robust Accuracy (%)
Robust Accuracy (%)
90
GraphCL
GraphCL
RES-GraphCL
100
RES-GraphCL.
80
80
60-
60
MUTAG PROTEINS
MUTAGG PROTEINS
Clean Figure 9: Robust accuracy of GraphCL for graph classification against random attack
(b) Noisy
I.2 Robustness Under Different Noisy Levels.
To demonstrate the ability of our method improve the robustness of Graph Contrastive Learning (GCL) against different levels of structural noise, we compare the robust accuracy of the GCL methods w/o applying our RES under evasion attacks for node classification. Specifically, we select GRACE, BGRL and DGI as target GCL methods. We set (1 3) = 0.05 and 50. We consider two targeted attack method, random attack and Nettack [ to conduct targeted attacks. The attack budget is set from 0 to 5. We randomly select 15% of the test nodes as the target nodes to compute the robust accuracy. The results on the Cora and Pubmed datasets are reported in Fig. and Fig. [T] We observe: (i) The robust accuracies of the bascline methods exhibit significant drop as the
25

---

Robust Accuracy (%)
Robust Accuracy (%)
85
80
Base GRACE RES-CRACE
Robust CC
80
80
78
78
76
Bese-BCRL
75
Base- DGT
76
74
RES BGRL
70
RES- DGG
74
72
65
720
7%
60
1
2
3
4
1
2
4
5
2
3
4
Perturbation Size
Perturbation Size
Perturbation Size
(a) Cora, GRACE
(b) Cora, BGRL
(c) Cora, DGI
Robust Accuracy (%)
Robust Accuracy (%)
Robust Accuracy (%)
80
Base-CRACE RES-GRACE
82
80
78
78
RCR.
76
Rase- DGT DEG
RES BGRL
76
74
72
740
7%
6
1
2
4
2
2
3
Perturbation Size
Perturbation Size
Perturbation Size
(d) Pubmed. GRACE
(e) Pubmed, BGRL
(1) Pubmed, DGI
Figure 10: Robust accuracy under different perturbation sizes of random attack
Robust Accuracy (%)
Robust Accuracy (%)
Robust Accuracy (%)
80
80
80
60
60
60
BaseGGRACE
Rare-BGTL
Bave DG]
40
RES-GRACE
40
AES-BGRL
40
RES DGL
20
20
20
0
%
0
1
4
2
3
3
Perturbation Size
Perturbation Size
Perturbation Size
(a) Cora, GRACE
(b) Cora, BGRL
(c) Cora, DGI
Robust Accuracy (%)
Robust Accuracy (%)
Robust Accuracy (%)
80
80
80
60
60
60
Rase-GRAcK RES-GRACE
Rase-Bin BCRL RES-BGRL BGRL
Base-DT
40
40
40
DGS
20
20
20
%
%
%
2
4
2
2
3
Perturbation Size
Perturbation Size
Perturbation Size
(d) Pubmed. GRACE
(e) Pubmed, BGRL
(1) Pubmed, DGI
Figure 11: Robust accuracy under different perturbation sizes of Nettack
perturbation sizes increase, which is expected. In contrast, the performances RES are much more stable and consistently outperform the baselines. This demonstrates the robustness of GCL with RES against various levels of structural noise. (ii) The high robust accuracies of the three GCL models demonstrate that our RES is effectively applicable to various GCL method.
1.3 Additonal Results of Robust Performance on Node Classification
In this subsection, we provide additional experimental results from Section 6.2 focusing node classification. We select GRACE, BGRL, and DGI as the target GCL methods and evaluate their performance on four types of graphs: raw graphs, random attack perturbed graphs, CLGA perturbed graphs, and PRBCD perturbed graphs. The perturbation ratio set to 0.1. Table presents results of these experiments. The highlighted results denote the best performance for each pair of GCL and RES-GCL Note that BGRL,, implemented based on PyGCI, 65), encounters out-of-memory (OOM) errors in our platform, and hence the results for BGRL OGB-arxin are left blank. From
26

---

the table, we observe that all three GCL methods, when combined with RES, achieve state-of-the-art performance. This demonstrates the effectiveness of our method in enhancing the robustness of various GCL methods. By incorporating RES, the GCL models are more resilient to adversarial attacks and exhibit improved performance across different types of perturbed graphs.
Moreover, we further consider two graph injection attack methods, i.c. TDGIA [60] and AGIA [61], baselines demonstrate the robustness of RES, Specificially, we select GRACE the target GCL methods and evaluate them on three types of graphs: raw graphs, TDGIA perturbed graphs and AGIA perturbed graphs. We insert the same number of fake nodes the target nodes. We set (1
0.1 and μr 50. The comparison results on four datasets are shown in Table. 4 From the results, we observe that RES- GRACE consistently outperforms the baselines across datasets in defending graph injection attacks. (ii) Both TDGIA and AGIA are much more powerful than the structural attack methods in Table lagansst GCL.
Table 3: Robust accuracy results of GCL methods for node classification.
Dataset
Graph
GRACE
RES GRACE
BGRL
RES BGRL
DGI
RES-DGI
Raw
77.1=1.66
79.7-11.0
7.651
79.9-1..2
81.3:0.77
81.4-0.8
Random
74.5=2.1
79.7+110
76.2+1.2
79.6=11.1
17.5+110
79.2=0.6
Cora
CLGA
74.9+22.0
78.2+1.0
1..8+116
79.4++0.9
79.5+0.55
80.9-1.0
PRBCD
75.812..5
78.5
76.4
7..5
1..61
80.9
Raw
79.5422.9
79.5-11.2
79.91114
81.5-10.6
80.1100.9
80.0-0.8
Pubmed
Random
75.0=1.0
78.2+00.9
74.0=100
81.0=20.7
76.7+00.7
78.8=0.6
CLGGA
76.6+2.5
78.3+1.1
77.9+0.3
81.6+0.22
79.6+:0.6
80.0-1.2
PRBCD
73.2+2..3
788811.7
71.61244
80.9
75.4:0.99
7.60
Raw
94.0-104
94.7-10.2
95.310.1
95.610.11
93.5.10.6
94.1-0.3
Physics
Random
92.6=0.5
94.2-10.3
94.0--022
95.5-10.2
91.5+099
92.2-0.4
PRBCD
89.2+0066
94.++0.2
92.3+002
95.4++0.2
88.8+0.5
90.0=004
Raw 65.110055
65.2.10.1
65.0:10.2
6.8
OGB-arxiv Random
59.0-0.2
60.0
58.010.11
58.9-0.1
PRBCD
55.710.4
58.310.4
56.9100.9
0..
Table 4: Robust accuracy results of GCL methods against injection attacks.
Dutaset
Graph
GRACE
BES-GRACE
Raw
77.1+16
79.7+1.0
Cora
TDGIA
12.4+1.5
7..
AGIA
21.1=1.4
78,4=0.9
Raw
79.5+3,1
79,5+1.2
Pubmed
TDGIA
50.6+1.2
77.0=0.4
AGIA
50.2+1.6
1..
Raw
94.0=0.4
94.7=0.2
Physics
IDGIA
52.2=1.0
93.820.1
AGIA
52.3+0.5
94.020.2
Raw
65.5
15.1.
OGB-arxiv
TDGIA
40.3+0.4
46.9+0.1
AGIA
40.4=0.3
47,0=0.1
L.4
Additional Results of RES for Advanced GCLs
Robust Accuracy (90
Robust Mecuracy (%)
Robust Accuracy (%)
Robust Accuracy (%)
1
ADGCL
100
ADCCL
100
RES-ADGCL
RES-ADGCL
RES RES-ADGCL.
RES-ADGCL
80
80.
90
80-
80
20
76.
60.
704
MUTAG PROTEINS
MUTAG PROTEINS
MUTAG PROTEINS
MUTAG PROTEINS
(a) ADGCL, Clean
(b) ADGCL, Noisy
(c) RGCL, Clean
(d) RGCL, Noisy
Figure 12: Robust accuracy ADGCL and RGCL for graph classification against random attack
To further demonstrate the effectiveness of RES, we further add ADGCL 58 and RGCL [66]
as baselines and implement RES-ADGCL and RES-RGCL. We set graph classification as downstream task. The hyperparameter is tuned based on the performance of the validation set. We use random attack to get the noisy graphs and the perturbation rate O. Fach experiment conducted 5 times and the average results reported. Comparison results MUTAG and PROTEINS are
27

---

Certmea Accuracy
Certinee Accuracy
0.5
8-0.1
0.5
8=0.1
B-0.9
8-0.9
0.3
B-0.95
0.3
0.9.5
B 3-09999
3 0.999
0.1
0.11
Perturbation Size
Perturbation Size
(a) MUTAG
(b) PROTEINS
Figure 13: Certified accuracy of RGCL on MUTAG and PROTEINS
shown in Fig. 12 From this figure, observe that all RES-GCL methods achieve comparable performances to the baselines on raw graphs and consistently outperform the baselines the noisy graphs of two datasets, which validates the effectiveness of RES in any GCL model.
We also report the certified accuracy Fig. L From the figure, we can observe there is tradeoff between certified robustness and model utility, which is similar to that of Sec. 6.3
RGS- on the two datasets. The results are shown in
Robust Accuracy (%)
Robust Accuracy (%)
82
NoRES Raw
66
NoRES Raw NORES-PH Pth
NoRES-Ptb
64
RES-RAW RES:Ptb
78
RES-Ptb
62
74
58
56
0..5
0.6
0.7
0.8
0.9
0.5
0.6
0.7
0.8
0.9
B
B
(a) Cora
(b) OGB-arxiv
Figure 14: Ablation Studies of Training with RES on Cora and OGB-arxiv
Robust Accuracy (96)
Robust Accuracy
80
FLIP/T
60
FLIP/T
60
FLIP
FLIP
Ours
Ours
40-
20
Cora
Pubmed
Cora
Pubmed
(a) Clean
(b) Noisy
Figure 15: Ablation Studies of Comparisons RES with FLIP
Additional Results of Ablation Studies
J.1 Ablation Studies on Training with RES
In this subsection, we conduct ablation studies to investigate the effect of our training method for robust GCL. To demonstrate that training method improves the robustness of GCL, do inject random edgedrop noise during the training phase and obtain a variant called NoRES. We select PRBCD as the attack method to generate noisy graphs, and set µ 50. We vary the value of B as (0.5, 0.6, 0.7, 0.8, 0.9} and compare the robust accuracy of RES and NoRES on both raw graphs and PRBCD-perie peettrredd graphs. The results of the variant NoRES on raw and PRBCD-perturbed graphs are denoted as NoRES-BER Raw and NoRES- -tbR,,, respectively. We report the results on the Cora and OGB- arxiv datasets in Fig. 14 From the figure, we observe the following: (i) RES consistently outperforms NoRES on both raw and perturbed graphs in all settings, implying the effectiveness of our training method for robust GCL. (ii) The variance of RES lower than that NoRES. This is because inject randomized edgedrop noise into the graphs during the training phase, helping the models better understand and generalize from the data with randomized edgedrop noise, thereby ensuring the robustness and utility of the models.
28

---

Certified Accuracy (%)
70
Certified Accuracy (%
70
20
90%
50-
50
50
95%
200
99%
500
99.9%
30-
1000
30
99.99%
10
4
8
2
8
10
Perturbation Size
Perturbation Size
(a)
(b) (1 a)
Figure 16: Hyperparameter Sensitivity Analysis on Cora
Certified Accuracy (%)
90
Certified Accuracy (%)
90
20
90%
70
50
70
95%
200
99%
50
50
500
99.9%
30
1000
30
99.99%
10
10
10
Perturbation Size
Perturbation Size
(a) /
(b) (1-a)
Figure 17: Hyperparameter Sensitivity Analysis on Coauthor-Physic.
J.2 Additional Results of Comparisons RES with FLIP
In this subsection, we present additional experimental results in Sec. effective in GCL compared vanilla randomized smoothing (24). We introduce two variants of our model, namely FL.IP and FL,P/TT, which replace the randomized edgedrop noise with binary random noise (24). This noise flips the connection status within the graph with probability of 3. The key difference between FLIP and FLIP/T is that FLIP injects binary random noise into the graphs during both the training and inference phases, while FLIP/T only injects binary random noise during the inference phase. For our RES method, we set 5 = 0.9, and μ 50. For FLIP and FLIP/T, ensure a fair comparison, we set μ = 50, and vary / over (0.1, 0.2. ... 0.9} and select the value that yields the best performance on the validation set of clean graphs. We select GRACE as the targeted GCL method and compare the robust accuracy our RES with FLIP and FL.IP/T on the clean and noisy graph under Nettack with an attack budget of 3. The average robust accuracy and standard deviation on Cora and Pubmed datasets are reported in Fig. [5] We observe: (i) RES consistently outperforms FLIP and FLIP/T on clean and noisy graphs of Cora and Pubmed datasets, further validating the effectiveness RES in providing certified robustness for GCL. (ii) FLIP and FLIP/T exhibit comparable performance on all graphs, but significantly lower than RES. This finding confirms our analysis that vanilla randomized smoothing introduces numerous spurious/noisy edges to the graph, resulting in poor representation learning by the GNN encoder and compromising downstream task performance.
S 6.4 further demonstrate that our
RES method is significantly
K Hyperparameter Sensitivity Analysis
We further investigate how hyperparameter (1 - a)) and μ affect the performance of robustness certificates of our RES, where (1 ( a) and μ control the confidence level and the number of Monte Carlo samples used to compute the certified accuracy. We vary the value (1 - a) as (90%, 95%, 99%, 99.9%, 99.99%) and fix μ 200, vary μ {20, 50, 200, 500, 1000) and fix (1 a)) as 99%, respectively. B3 is set as 0.9. We report the certified accuracy of RES-GRACE on Cora and Coauthor- the certified accuracy curve becomes higher. The reason for this is that a larger value of makes the estimated probability bound pv+ (v e) and Py, A @ e) in Eq. (8) tighter, resulting in higher certified perturbation size of test sample. (ii) As (1 - a) increases, the certified accuracy curve becomes slightly lower. This is because a higher confidence level leads
dataset in Fig. 16 and Fig. 17 From the figures,
observe: (i) As μ increases,
looser estimation of Pvt.A (v @ e) and Py; (v @ E) in Eq. (8), meaning that fewer nodes satisfy Theorem under the
same perturbation size, resulting in smaller certified perturbation size of test sample.

---

L Limitations
In this paper, we propose a unified criteria evaluate and certify the robustness of GCL. Our proposed approach, Randomized Edgedrop Smoothing (RES). injects randomized edgedrop noise into graphs to provide certified robustness for GCL on unlabeled data. Moreover, we design an effective training method for robust GCL by incorporating randomized edgedrop noise during the training phase. The theoretical analysis and extensive experiments show the effectiveness of our proposed RES.
Limitation & future work: Our current results are limited mainly to GCL while we believe is also interesting develop and neighborhood prediction methods based on our framework, which we leave for immediate future work. We hope that this work could inspire future certifiably defense algorithms of adversarial attacks. Additionally, in this paper, we only focus on the graph-structured data. Thus, it is also interesting to investigate how extend it to other domains, e.g., images and texts. Furthermore, this paper, we utilize Monte Carlo algorithms to calculate robustness certificates for GCL, potentially increasing the computational demands. Therefore, is also worthwhile to investigate methods improve the efficiency of the robustness certification for GCL. Due to the nature of this work, there may not be any potential negative social impact that is easily predictable.
techniques other graph self-supervised methods e-g. generative
30


Reviews:
[{"review_id": "IVXZOGBtpy", "reviewer": "Reviewer_661C", "summary": "This paper is the first one to dive into the certifiably robust Graph Contrastive Learning (GCL) and proposes a certifiably robust GCL framework. It defines the certified robustness of GCL and then proposes Randomized EdgeDrop Smoothing (RES), which randomly drops each edge of the input sample with a certain probability. Besides, it also presents a simple training method for robust GCL. The theoretical analyses and extensive experiments demonstrate its effectiveness.", "questions": "Please refer to the weaknesses above.", "limitations": "I believe this work does not have potential negative societal impacts.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is the first one to dive into the certifiably robust Graph Contrastive Learning (GCL) and proposes a certifiably robust GCL framework. It defines the certified robustness of GCL and then proposes Randomized EdgeDrop Smoothing (RES), which randomly drops each edge of the input sample with a certain probability. Besides, it also presents a simple training method for robust GCL. The theoretical analyses and extensive experiments demonstrate its effectiveness. The paper is well-written.", "weaknesses": "I have some minor comments, as below.\n1. In Line 106, the definition of \" concatenation vector \\mathbf{v}\" is confusing. What is the meanings of \"which captures the upper triangular part of the adjacency matrix for the K-hop subgraph of v\". Does it mean the K-hop neighbors of node v?\n2. The use of probability operator symbols is inconsistent. For example, Eq. 2, 6, 7 use \"\\mathbb{P}\", while Eq. 5 use \"Pr\". It is better to harmonize the symbols used.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your approval of the novelties, the valid theoretical and technique details and extensively conducted experiments of our work. We sincerely thank you for your time and thoughtful feedback. We will perform all the changes requested in the minor comments. Here, we hope to address the raised points.\n\n**Q1: What is the meaning of \"which captures the upper triangular part of the adjacency matrix for the K-hop subgraph of v\"**\n\nThanks for your insightful question. We would like to clarify the concatenation vector $\\mathbf{v}$ here is a vector to represent the connection status of any pair of nodes in the K-hop subgraph of the node $v$, which can depict the structure of the K-hop subgraph of the node $v$. To construct such a vector, we select the upper triangular part of the adjacency matrix of the K-hop subgraph of $v$ and flatten it into the vector, where each item in this vector can denote the connection status of any pair of nodes in the K-hop subgraph of node $v$. A similar setting also appeared in [1].\n\n**Q2: The use of probability operator symbols is inconsistent in Eq.(5).**\n\nThanks for pointing this out. We will correct this typo in the final version of this paper. \n\nWe sincerely thank you again for your time and efforts in reviewing our paper. We will include the above discussion and revision in the final version of our paper. If you have any further concerns or questions, please do not hesitate to let us know. We will respond to them timely.\n\n[1] Certified robustness of graph neural networks against adversarial structural perturbation. KDD 2021.\n"}, {"review_id": "ZL8yzFWdrf", "reviewer": "Reviewer_ssR8", "summary": "This paper studies the problem of certifiable robustness against adversarial perturbations in Graph Contrastive learning (GCL). This is an interesting paper where theoretical and empirical results are provided. The goal is to provide provable guarantee of robustness in the face of a limited budget adversarial attack on graph structure, showing that (1) positive samples remain positive samples in GCL, and (2) the downstream node/graph classification output does not change either. To this end randomized edge-drop smoothing (RES) is proposed and analyzed theoretically and empirically. ", "questions": "1- In multiple occasions in the definitions and theorems, an assumption is made on the encoder h being a \"well-trained\" GNN encoder, however this term is not defined, and it is not clear what criteria should be met for this. Since this is repeated in multiple Theorems, its clarification is crucial.\n\n2- Is the importance of certification of the GCL in 9 itself only theoretical, and a stepping stone to providing certification on the downstream node/graph classification? Or is it possible to also evaluate such certification? I cannot seem to find any such results in the experiments section.\n\n3- In ablation study in 6.4, what was the optimal $\\beta$ for the FLIP algorithm? The gap between FlIP and other methods (Baseline and Ours) seems too large, and it is interesting to know if the smaller \\beta=0.1 turned out to be the best value, which would motivate having a finer grained search for a smaller value for this.\n\n4- What is the rationale behind setting such high values for $\\beta$ in experiments in Figure 2? Such high values indicated that almost all edges are dropped in the randomization, which means that no structural information is retained, which is counterintuitive given that such high *certified* accuracy can still be obtained. ", "limitations": "Increase in computational needs for Monte Carlo estimates and its environmental impacts should be mentioned in the limitations section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main advantage of this work is its certification capability, which eliminates dependence on empirical assessment relying on empirical attacks, whose parameter/algorithmic tuning would be questionable. \n\nThe proposed method is simple and intuitive, and the experimental results show relative improvements on SOTA as well.", "weaknesses": "The main disadvantage of the proposed work seems to be its reliance on the latent classes in the downstream task, which is considered to be node/graph classification. This still encompasses a large set of problems and is of interest, however, it does partially violate the claim that a general GCL certification is studied. \n\nAlso, the manuscript has many typos and grammatical errors that would benefit from careful proof-reading.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer ssR8 for recognizing the novelties, the valid theoretical and technique details and extensive experiments of this work. The following is our point-to-point response to the reviewer’s concerns and comments:\n\n**W1: The proposed work seems to rely on the latent classes in the downstream task, which is considered to be node/graph classification.**\n\nThanks for your questions. We acknowledge that our work is based on the latent class to formalize GCL and establish the connection between the certified robustness of GCL and of downstream tasks. Many of the existing works [1,2,3] also exploit latent class to theoretically analyze contrastive learning. Thanks for your good suggestions. We leave other downstream tasks (e.g. link prediction) as future work.\n\n**W2: Typos and grammatical errors.**\n\nThanks for pointing them out. We will correct them in the final version of this paper. \n\n**Q1: Define a “well-trained” GNN encoder.**\n\nThanks for your insightful question. The definition of a “well-trained”: is an encoder that can extract meaningful and discriminative representations by mapping the positive pairs closer in the latent space while pushing dissimilar samples away.\n\n**Q2: The importance of the certification of GCL**\n\nThanks for your insightful question. We would like to kindly clarify that our certified GCL robustness has following contributions:\n\n**(i)** Our work is the first attempt to certify the robustness of GCL.\n\n**(ii)** We propose a novel framework RES to certify GCL’s robustness. This framework also improves the robustness of any GCL model.\n\n**(iii)** Extensive experimental results on 7 real-world datasets validate the effectiveness of RES in certifying robustness and enhancing the robustness of any GCL model in practice. Please see Table 1 and Table 3 of the original paper for the details.\n\n**Q3: The optimal $\\beta$ for the FLIP algorithm.**\n\nThanks for your insightful question. To find the optimal $\\beta$ for FLIP, we follow the same setting with various beta in Sec. 6.4 (see lines 362-363). The robust accuracies of FLIP on both clean and noisy Cora and Pubmed graphs under Nettack with an attack budget of $3$ are shown in **Table 1 of the attached PDF file**. \n\nOur observations are: (i) FLIP achieves the best robust accuracy on the clean graphs when $\\beta=0.1$, implying that $\\beta=0.1$ is the optimal choice. (ii) FLIP generally demonstrates inferior robust accuracy on the clean graphs at $\\beta=0.9$. Our interpretation is that a smaller $\\beta$ in FLIP introduces fewer noisy edges to clean graphs, thereby preserving more structural information, beneficial for downstream tasks. However, based on the analysis in [4], a smaller $\\beta$ leads to a smaller certified perturbation size, which implies a tradeoff between model utility and certifiable robustness within FLIP. Therefore, it is important to study how to select the best $\\beta$ in FLIP to balance the tradeoff. We will leave it as future work.\n\n**Q4: Rationale behind setting high values for $\\beta$ in experiments.**\n\nThe rationale behind setting high $\\beta$ is: The proposed robust encoder training method in Sec. 5.1 improves the model utility of GCL. Even setting a large $\\beta$ for RES, we can still obtain high robust accuracy on clean graphs, further leading to high certified accuracies. \n\nSpecifically, as shown in line 321, certified accuracy denotes the fraction of correctly predicted test nodes/graphs whose certified perturbation size is not smaller than the given perturbation size. It implies that these certified robust samples should also be correctly predicted by RES in the clean datasets. However, as the reviewer said, introducing randomized edgedrop solely to test samples during the inference could potentially hurt downstream task performance and further negatively impact the certified robustness based on Eq.(8). Thus, we propose robust encoder training for RES in Sec. 5.1 by injecting randomized edgedrop noise into one augmented view during GCL . **It ensures the samples with randomized edgedrop noises align in latent class with clean samples under the encoder, thereby mitigating the negative impacts of such noises and further benefiting the robustness and certification of RES.**\n\nWe sincerely thank you again for your time and efforts in improving our paper. We will include the above discussion in the final version of our paper. If you have any further concerns or questions, please do not hesitate to let us know. We will respond to them timely.\n\n[1] A theoretical analysis of contrastive unsupervised representation learning. ICML 2019.\n\n[2] Do more negative samples necessarily hurt in contrastive learning? ICML 2022.\n\n[3] Robustness verification for contrastive learning. ICML 2022.\n\n[4] Certified robustness of graph neural networks against adversarial structural perturbation. KDD 2021.\n"}, {"review_id": "UnLgVJeHEx", "reviewer": "Reviewer_F8a7", "summary": "This study represents the first exploration of certifiable robustness in Graph Contrastive Learning (GCL). The authors propose a unified definition of robustness in GCL, addressing the existing ambiguity in quantifying its resilience to perturbations. The introduction of the Randomized Edgedrop Smoothing method is an interesting approach that applies randomized edgedrop noise into graphs to offer certifiable robustness on unlabeled data while minimizing the insertion of unnecessary edges. Theoretical analyses provided affirm the robust performance of their encoder in subsequent tasks. Extensive empirical experiments on various real-world datasets have been conducted, suggesting that the proposed method enhances the robustness of GCL models and provides certifiable robustness. ", "questions": "1. Could you clarify the operation of the evasion attack in the context of transductive node classification within Graph Contrastive Learning (GCL)?   In a scenario where structural perturbations are incorporated into the test set, however, it's worth noting that the GCL encoder is already trained based on the entire graph. So, in this transductive learning setting, what would be the practical significance of the evasion attack? Could you perhaps provide a schematic or flowchart, similar to Algorithm 1 in your paper, that visually represents the process of the attack method in GCL? This could facilitate a better understanding of its operation and mechanics, thus enriching the comprehension of your methodology.\n2. I recommend considering stronger graph injection attacks for evasion scenarios, such as those presented in [1].\n3. Could you provide a comparison between your proposed Randomized Edgedrop Smoothing (RES) method and the learnable edge-dropping augmentations described in [2]? I am interested in both theoretical distinctions and empirical differences based on experimental results.  \n4. Could you elucidate the distinction between your proposed Randomized Edgedrop Smoothing (RES) method and the conventional edge perturbation for augmentation as outlined in [3]? Understanding this difference could clarify the unique value proposition of your approach.\n5. The definition of the \"concatenation vector v\" as given in line 106 seems somewhat ambiguous, as it appears to include the connected edge of node v. However, equation 5 also features h(v), where v presumably represents node features. Could you provide further clarification regarding the nature and role of the vector v?\n6. In line 198, the space B is defined, but its details remain unclear. Could you provide a more comprehensive explanation of the space B, including its constituent elements? Is it meant to represent a probability space?   \n\n[1]. Chen Y, Yang H, Zhang Y, et al. Understanding and improving graph injection attack by promoting unnoticeability[J]. arXiv preprint arXiv:2202.08057, 2022.  \n[2]. Suresh S, Li P, Hao C, et al. Adversarial graph augmentation to improve graph contrastive learning[J]. Advances in Neural Information Processing Systems, 2021, 34: 15920-15933.  \n[3]. You Y, Chen T, Sui Y, et al. Graph contrastive learning with augmentations[J]. Advances in neural information processing systems, 2020, 33: 5812-5823.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors explore a novel area of certifying the robustness of Graph Convolutional Learning (GCL) against various perturbations. They introduce a comprehensive definition for robustness in GCL and design an innovative framework, Randomized Edgedrop Smoothing (RES), to validate this robustness.\n2. A theoretical analysis provided in the study affirms that the representations learnt by their robust encoder can deliver a provable robust performance in subsequent tasks.\n3. The authors have developed an effective training strategy for robust GCL, integrating the application of randomized edgedrop noise.\n4. Comprehensive empirical evaluations demonstrate that their method can deliver certifiable robustness for downstream tasks.\n", "weaknesses": "1. The selection of adversarial attack strategies in this study seems somewhat underwhelming given the marginal difference between clean accuracy and attack accuracy. It would be beneficial to employ more aggressive attack methods to genuinely assess the robustness of your proposed framework.\n2. From what is shown in Table 3, the RES method appears to result in only slight improvements. Providing results from a broader range of graoh attack methods might lend more robust evidence to support your claims.\n3. The paper seems to be missing a comparative analysis between the proposed Randomized Edgedrop Smoothing  method and existing edge drop augmentation techniques in Graph Contrastive Learning (GCL). Including such an analysis could provide readers with a more concrete understanding of the advantages and potential improvements brought about by the RES method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer F8a7 for recognizing the novelties, the valid theoretical and technique details and extensive experiments of this work. The following is our point-to-point response to the reviewer’s concerns and comments:\n\n**Q1: Clarify the operation of the evasion attack in the context of transductive node classification within GCL**\n\nThanks for your thoughtful questions. Please find our answers below:\n\n**Evasion attack process.** In the context of transductive node classification within GCL, the target nodes of the evasion attack are visible during encoder training and inference. The objective is to perturb these target nodes, causing the GNN encoder $h$, to generate poor representations that degrade the nodes' performances on downstream tasks. The procedure of evasion attacks is summarized in **Fig. 1 of the attached PDF file.** Specifically, $h$ is first trained via GCL on the raw graph. Then perturbations are added to target node $v$, yielding a perturbed node $v{‘}$. After that, we generate the representations of $v{‘}$ via $h$ and evaluate its performance on the downstream tasks. \n\n**Practical significance.** In real-world scenarios like social networks and financial systems, pre-training a GNN encoder on untampered graphs is a common practice. Take social networks as an example: a company could pre-training a GNN encoder on the raw social network graph, and enable downstream task execution via an API. Consequently, user representations are periodically derived from the encoder for these tasks, involving users present during the encoder's training. Yet, malicious attackers might manipulate graph structure by injecting spurious edges, leading to mispredictions in downstream tasks and raising severe trustworthy concerns. Hence, ensuring the model's robustness against evasion attacks is also an important concern.\n\n**Q2: Compare with some stronger graph injection attacks in [1]**\n\nThanks for the suggestions. We add two SOTA graph injection attack methods, i.e., TDGIA and AGIA [1]. We insert the same number of fake nodes as the target nodes. We compare the performance of GRACE and RES-GRACE. For RES-GRACE, we set $\\mu=50$ and $\\beta=0.9$. The comparison results on 4 datasets are shown in **Table 2 of the PDF file**. From the results, we observe that RES-GRACE consistently outperforms the baselines across 4 datasets in defending graph injection attacks.\n\n**Q3: Compare RES with the learnable edge-dropping augmentations in [2]**\n\nThanks for sharing the great work [2]. We would like to kindly clarify that RES is inherently different from [2]:\n\n**(i)** Our work has different objectives as our method utilizes RES to **achieve certificate robustness for GCL**, while [2] is a learnable edge dropping augmentation to enhance downstream task performance. \n\n**(ii) In the inference phase, RES is deployed to guarantee certified robustness. Ans RES is further added to one augmented view during GCL training for model utility and robustness.** However, [2] is only used to augment graphs during training. \n\nTo demonstrate the effectiveness of RES, we compare ADGCL with GraphCL. We also add RES-ADGCL into comparisons. We generate noisy graphs with a 10% random attack. The comparison results on two graph datasets are shown in **Table 3 of the PDF file**. From the table, we observe that RES-GraphCL and RES-ADGCL both achieve comparable performances to the baselines on raw graphs and consistently outperform the baselines in the noisy graphs of two datasets, which validates the effectiveness of RES in any GCL model.\n\n**Q4: Compare RES and the random edge-dropping in [3]**\n\nThanks for your insightful question. We would like to kindly clarify that our RES is inherently different from the random edge-dropping augmentation in [3]. Due to the word limits, please see the **Q1 of the global response** for our detailed responses.\n\n**Q5: The nature and role of the concatenation vector v**\n\nThanks for your insightful question. We would like to clarify that the concatenation vector $\\mathbf{v}$ here is a vector to depict the structure of the node/graph for learning representations. Due to the word limits, please see the **Q2 of the global response** for our detailed responses.\n\n\n**Q6: Explain the space $\\mathbb{B}$**\n\nThanks for your question. In our paper, given a sample $\\mathbf{v}^+$ with the latent class $c^+$,\n**$\\mathbb{B}(\\mathbf{v}^+)$ is a space for $\\mathbf{v}^+$, where each constituent element within it is the positive sample of $\\mathbf{v}^+$**. In the context of GCL, as detailed in 129, the label-invariant augmentation intuition of GCL makes augmented positive views have consistent latent classes with the original ones. Therefore, **each sample within this space also has the same latent class $c^+$, and we can then define $\\mathbb{B}$ in Eq. (4).**\n\n**Role:** By leveraging the space $\\mathbb{B}$ in Theorem 1 and 2, **we establish a connection between the probability of $\\mathbf{v}$ being a positive sample of $\\mathbf{v}^+$ and their cosine similarity in the latent space**. This connection enables the certification of GCL's robustness and transfers such robustness to downstream tasks to solve our problem 1 in Sec. 3.3.\n\n[1] Understanding and improving graph injection attack by promoting unnoticeability. ICLR 2022.\n\n[2] Adversarial graph augmentation to improve graph contrastive learning. NeurIPS 2021.\n\n[3] Graph contrastive learning with augmentations. NeurIPS 2020.\n"}, {"review_id": "e11kQdrNQG", "reviewer": "Reviewer_vCmM", "summary": "This paper introduces a certifiably robust graph contrastive learning method called RES (randomized Edgedrop Smoothing). This paper (1) first introduces the criteria of how to evaluate and certify robustness, (2) and then introduces RES to ensure certifiable robustness, (3) finally, proves that the certified robustness can be transferred to downstream tasks. ", "questions": "1. In problem 1, what are $y$ and $y^\\ast$?\n2. What does \"maximum of {$\\mathbf{v}_1,\\dots, \\mathbf{v}_N$}\" mean in Lemma 1? Can you show a concrete example?\n3. There are many ways to define the probability shown in Eq. (5). For example, empirically, Gaussian is the most common and effective way. What are the advantages of your definition over a simple Gaussian?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper is well motivated that current robust graph contrastive learning methods are not able to certify their robustness. \n2. The theorem introduced in this paper looks interesting.\n3. The experimental results on several benchmark datasets show that the proposed method could outperform baselines.", "weaknesses": "1. The motivation of using $\\mathbf{v}^+$ rather than $\\mathbf{v}$ in Eq. (3) is not quite clear. Specifically, in Eq. (3), why do you use $s(h(\\mathbf{v}'), h(\\mathbf{v}^+)) > s(h(\\mathbf{v}'), h(\\mathbf{v}^-))$ rather than $s(h(\\mathbf{v}'), h(\\mathbf{v})) > s(h(\\mathbf{v}'), h(\\mathbf{v}^-))$.\n2. $v$ and $v^+$, and the term \"positive sample\" are a kind of confusing in section 4.1 (after line 194). I think the \"positive sample\" after line 194 has a different meaning of the \"positive sample\" in contrastive learning. It is highly suggested that the authors find a better way to present the idea here.\n3. The claim in line 225-226 that \"the majority of them will possess identical structural vectors, that is, $\\mathbf{v}\\oplus\\mathbf{\\epsilon}=\\mathbf{v}'\\oplus\\mathbf{\\epsilon}$\" seems too strong. If this is the real case, can you show the statistics in some real datasets?\n4. Random dropping edges is one of the basic graph augmentation techniques that have been introduced in GraphCL [1] and GraphMAE [2]. What's the difference between RES and random edge drop in GraphCL and GraphMAE? \n\n[1] You, Yuning, et al. \"Graph contrastive learning with augmentations.\" Advances in neural information processing systems 33 (2020): 5812-5823.\n[2] Hou, Zhenyu, et al. \"Graphmae: Self-supervised masked graph autoencoders.\" Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer vCmM for recognizing the novelties, the valid theoretical and technique details and extensive experiments of this work. The following is our point-to-point response to the reviewer’s concerns and comments:\n\n**W1: Why to use $\\mathbf{v}^+$ instead of $\\mathbf{v}$ in Eq. (3)**.\n\nThanks for your question. We agree with the reviewer that $\\mathbf{v}$ can be also used here because in Eq. (3), as $\\mathbf{v}$ and $\\mathbf{v}^+$ are the positive samples in GCL, which have the same latent class. Here are two reasons we use $\\mathbf{v}^+$: \n\n**(i)** The use of $\\mathbf{v}^+$ can distinguish it from $\\mathbf{v}^-$, making our statement more clear. \n\n**(ii)** Since given a positive pair $(\\mathbf{v}, \\mathbf{v}^+)$, the goal of robustness certification of GCL is to make sure perturbed sample $\\mathbf{v}’$ is always the positive sample of $\\mathbf{v}^+$, as shown in Eq. (3) and Eq. (5). Replacing $\\mathbf{v}$ as $\\mathbf{v}’$ in Eq. (3) will cause the inconsistentness of notations in subsequent parts.\n\n**W2: \"positive sample\" after line 194 differs from the one in CL**\n\nThanks for your question. We kindly clarify that both two “positive sample” share the same meaning. In GCL, the positive samples are generated from augmentation and they have the same latent classes based on the label-invariant augmentation intuition of GCL (see lines 129-130).\n\nFor the “positive sample“ after line 194, it comes from Def. 2 about the certified robustness of GCL, where $(\\mathbf{v}$, $\\mathbf{v}^+)$ is a positive pair in GCL as shown in line 189. The meaning of Eq. (3) here is to check if $\\mathbf{v}’$ under any perturbation within the specific budget is still most similar to the positive sample $\\mathbf{v}^+$ of $\\mathbf{v}$ than other $\\mathbf{v}^+\\_i$ in the latent space. In other words, it is to check if $\\mathbf{v}’$ is still the positive sample of $\\mathbf{v}^+$. Therefore, the two “positive sample” are the same.\n\n\n**W3: The claim that \"the majority of them will possess identical structural vectors” seems too strong.**\n\nThanks for your insightful question. We kindly clarify that given the perturbed sample $\\mathbf{v}’=\\mathbf{v}\\oplus\\delta$, after adding the randomized edgedrop noise $\\epsilon$, the only difference between $\\mathbf{v}’\\oplus\\epsilon$ and $\\mathbf{v}\\oplus\\epsilon$ is in the part of fake edges in $\\delta$. **Thus, the problem is reformulated to validate if the majority of the injected $\\epsilon$ drop these fake edges.** Specifically, based on Sec. 5.2, RES will draw $\\mu$ samples of $v’\\oplus\\epsilon$. Then use Monte Carlo to decide the final connection status of the edge by validating if the majority of the $\\mu$ samples drop this edge. Thus, **all fake edges in most of the $\\mu$ samples will be dropped if selecting high $\\beta$**, making these fake edges finally dropped. which supports our claim.\n\nWe further report the statistics on Pubmed to validate the correctness of the above statement. Specifically, we conduct Nettack with various perturbation sizes on test nodes. We conduct RES with various $\\mu$ and $\\beta$.  The frequency of test nodes satisfying $\\mathbf{v}\\oplus\\epsilon=\\mathbf{v}’\\oplus\\epsilon$ are shown in **Table 4 of the attached PDF file**. From the table, we observe that almost all test nodes possess $\\mathbf{v}\\oplus\\epsilon=\\mathbf{v}′\\oplus\\epsilon$, validating our claim.\n\n**W4: Difference between RES and random edgedrop in GraphCL and GraphMAE.**\n\nThanks for your insightful question. We kindly clarify that our RES is inherently different from the random edgedrop in GraphCL and GraphMAE. Due to the word limits, please see the **Q1 of the global response** for our detailed responses.\n\n**Q1: What are $y$ and $y^\\*$.**\n\nThanks for pointing them out. $y^\\*$ should be the latent class $c^\\*$ of $\\mathbf{v}$ in line 160 and $y$ should be $c$ in line 161. We apologize for the confusion and will revise them in the final version of our paper.\n\n**Q2: What does \"maximum of $\\\\{\\mathbf{v}_1,\\cdots, \\mathbf{v}_N\\\\}$\" mean in Lemma 1?**\n\nThanks for your question. “Maximum of $\\\\{\\mathbf{v}_1,\\cdots,\\mathbf{v}_N\\\\}$” is the maximum of a sequence of i.i.d samples based on Lemma 1. In our theorem, it refers to $\\\\max\\\\{-D\\_1,\\cdots,-D\\_{n}\\\\}$ in Eq.(C.9), where $D\\_i=(1-s(h(\\mathbf{v^+,v^-\\_i})))/2$. It denotes the negative of half of the minimum distance between representations of positive and negative samples $\\mathbf{v}^+$ and $\\mathbf{v}^-\\_i$. We apologize for this confusion about this notation and will revise it in the final version of our paper. \n\n **Q3: Advantages of Eq.(5) over a simple Gaussian.**\n\nThanks for your insightful question. The advantage of the definition of Eq. (5) is: **We can use Eq.(5) to reformulate the problem of certifying robustness for GCL in problem 1 to the problem of comparing the distances between positive and negative samples $\\mathbf{v}^+$, $\\mathbf{v}^-$ with respect to $\\mathbf{v}$ as shown in Eq.(3). This enables an easier obtainment of GCL’s certified robustness.**\n\nSpecifically, based on Problem 1 in Sec. 3.3, we aim to develop a certifiably robust GCL for encoder $h$ such that the probability of $h(\\mathbf{v}’)$ in the latent class $c^*$ is always the largest over any other $c\\neq c^*$. However, quantitatively calculating such a probability is indeed challenging in GCL. Based on Theorem 1 and its proofs in lines 630-648, Eq. (5) build a connection between the probability of $\\mathbf{v}$ being the positive sample of $\\mathbf{v}^+$ and the distance between them in the latent space. And the probability aligns with that of $\\mathbf{v}’$ in latent class $c^*$ due to label-invariant augmentation intuition in line 129. \nThen, we can RES to derive certified robustness based on Eq. (5).\n\n[1] Graph contrastive learning with augmentations. NeurIPS 2020.\n\n[2] Adversarial graph augmentation to improve graph contrastive learning. NeurIPS 2021.\n\n[3] Label-invariant augmentation for semi-supervised graph classification. NeurIPS 2022. "}, {"review_id": "jyYd5BIFoi", "reviewer": "Reviewer_A65y", "summary": "Inspired by the certifiable robustness of graph contrastive learning (GCL) is still remain unexplored, the authors develop the first certifiably robust framework in GCL by proposing a unified criteria to evaluate and certify the robustness of GCL. Specifically, the authors introduce a novel technique, RES (Randomized Edgedrop Smoothing), to ensure certifiable robustness for any GCL model, and this certified robustness can be provably preserved in downstream tasks. Experiments on 7 real-world datasets show that the proposed RES-GRACE achieves state-of-the-art performance.", "questions": "Please see comments and questions in Weaknesses.", "limitations": "The topic about certifiable robustness is quite interesting and is of high practical value. I believe this work has some potential things need to be addressed such as a better motivation and more details of comparisons in the experiments.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The presentation of the paper is very clear and the figures are easily digestible.\n2. The numerical experimental results and visualization support the effectiveness of the proposed method.", "weaknesses": "1. In this paper, the authors conduct experiments for both node and graph classification tasks over regular and large-scale graphs. It is good. However, the choice of baselines seems somewhat insufficient. Can the authors compare with some recent GCL baselines? E.g., RGCL [1] and GLCC [2].\n\n2. Can the authors provide some explanations why the performance of RES-backbone (e.g., RES-GRACE, RES-DGI) framework sometime is worse than the backbone on raw graph (however, their performance is always better than backbone under perturbation scenarios)? \n\n3. From a clarity perspective, this work is, in my opinion, weakly motivated. It is not clear why the authors consider and start edgedrop smoothing to enhance the robustness of a GCL model. \n\n\n[1] Li, Sihang, et al. \"Let invariant rationale discovery inspire graph contrastive learning.\" International conference on machine learning. PMLR, 2022.\n\n[2] Ju, Wei, et al. \"Glcc: A general framework for graph-level clustering.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer A65y for recognizing the novelties, the clear presentation, the valid technique details and extensively conducted experiments. The following is our point-to-point response to the reviewer’s concerns and comments:\n\n**Q1: Compare with some recent GCL baselines? E.g., RGCL [1] and GLCC [2].**\n\nWe thank the reviewer for raising the related works. Note that since GLCC does not publish their source code for us, instead, we choose to only compare with RGCL, where we implement our RES on RGCL and obtain RES-RGCL. Specifically, we follow the same setting in the paper to compare the robust accuracy of RES-RGCL and RGCL. We set graph classification as the downstream task. The hyperparameter is tuned based on the performance of the validation set. We use random attack to get the noisy graphs and the perturbation rate is 0.1. Each experiment is conducted 5 times and the average results are reported. Comparison results in MUTAG and PROTEINS are shown in **Fig. 2 of the attached PDF file**.\n\nFrom the table, we can observe that (i) When no attack is applied to the raw graphs, RES-RGCL achieves comparable performance to the baseline RGCL. (ii) When attacks are conducted on the noisy graphs, RES-RGCL consistently outperforms the baseline on both the MUTAG and PROTEINS datasets. This result demonstrates the effectiveness of our method in enhancing the robustness of RGCL against adversarial attacks. The above observations are similar to that of GraphCL.\n\nWe also report the certified accuracy of RES-RGCL on the two datasets. The results are shown in **Fig. 3 of the PDF file**. From the figure, we can observe the tradeoff between certified robustness and model utility, which is similar to that of Sec. 6.3.\n\n**Q2: Provide some explanations why the performance of RES-backbone (e.g., RES-GRACE, RES-DGI) framework sometime is worse than the backbone on the raw graph**\n\nThanks for your careful reading. We would like to kindly clarify that the performance of RES-backbone framework is comparable to the baseline on raw graphs in these situations. For example, based on Table 3, the performance of RES-backbone is superior to the baselines on the raw graphs of all datasets except for Pubmed, OGB-arxiv. \n\nSpecifically, RES-DGI achieves robust accuracy of 80.0±0.8 and 64.8±0.1 on the Pubmed and OGB-arxiv datasets, respectively. These results are comparable to the respective performance of DGI on the two datasets: 65.0±0.2 and 80.1±0.9. The difference in average robust accuracy between them is negligible and standard deviations of RES-DGI are also slightly lower than the baseline DGI, which validates our claim.\n\n**Q3: This work is weakly motivated. Why consider and start edgedrop smoothing to enhance the robustness of a GCL mode**\n\nPlease see our following clarification for your concerns about our motivation.\n\n**(i)** Certified robustness aims to prove samples are robust to any perturbation in considered space. **To the best of our knowledge, there is no existing work studying the certified robustness of GCL.** Existing works [3,4,5] on the certifiable robustness of GNNs are designed for supervised settings, However, they generally analyze the worst-case attack on labeled nodes, which cannot be directly adapted to GCL due to the absence of labels.\n\n**(ii)** To address the above challenges, we propose **RES to derive certifiable robustness for GCL**. Our motivation is that injecting the randomized edgedrop noise $\\epsilon$ to $\\mathbf{v}’$ in the inference phase for multiple times will make each perturbed edge in the majority of these samples will be dropped, making these perturbed edges finally drop in the final decision. which makes certifying the robustness of GCL is feasible.\n\n**(iii)** However, applying RES to test samples in the inference solely may hurt performance in downstream tasks and the certified robustness based on Eq.(8). Thus, to address this issue and enhance RES’s robustness, we propose to train the robust GNN encoder by injecting randomized edgedrop noise to one augmented view and maximizing the agreement between two views via GCL to ensures the samples with randomized edgedrop noises have the same latent class as the clean samples. **This eliminates the negative impacts of randomized edgedrop noise, enhances model utility and robustness of GCL and further improves the robustness certification of GCL**. \n\nWe again thank the reviewer for the time and effort in reviewing our paper. If you have any further concerns or questions, please do not hesitate to let us know. We will respond to them timely.\n\n[1] Let invariant rationale discovery inspire graph contrastive learning. ICML 2022. \n\n[2] Glcc: A general framework for graph-level clustering. AAAI 2023.\n\n[3] Certifiable robustness and robust training for graph convolutional networks. KDD 2019.\n\n[4] Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. ICML 2020.\n\n[5] Certified robustness of graph neural networks against adversarial structural perturbation. SIGKDD 2021. \n"}]

Author rebuttal:
We sincerely thank all the reviewers for their thoughtful comments and constructive suggestions, which significantly helped us strengthen our paper. We are encouraged to find that the reviewers appreciate the novelty of this work, the valid theoretical and technique details and extensively conducted experiments and clear presentation. We now provide our answers to these shared comments and report the required additional experimental results and algorithms in **the attached PDF files**. 

**Q1: Difference between RES and random edgedrop in GraphCL.**

Our RES is inherently different from the random edge-dropping augmentation in GraphCL:

**(i)** Random edge-dropping is an augmentation method to generate different augmented views and maximize the agreement between views. However, RES is devised from the robustness perspective, providing certifiable robustness and enhancing the robustness of any GCL method. 

**(ii)** While random edge-dropping is only applied to augment graphs for GCL, RES extends beyond this. Following the generation of two augmented views as shown in Sec. 5.1, RES injects randomized edgedrop noise into one augmented view during GCL training. Then, it performs randomized edgedrop smoothing in the inference phase through Monte Carlo, as shown in Sec. 5.2. Specifically, for inference using RES (based on lines 274-276), $\mu$ samples of $h(\mathbf{v}\oplus\epsilon)$ are drawn by injecting randomized edge-drop noise $\epsilon$ to $\mathbf{v}$ $\mu$ times. The final prediction is from Monte Carlo, selecting the $\mu$ predictions with the highest frequency in $\mu$ samples.

**Q2: About the concatenation vector v.**

The concatenation vector $\mathbf{v}$ is a vector to depict the structure of the node/graph for learning representations. **For node-level tasks, it represents the connection status of any pair of nodes in the K-hop subgraph of the node $v$. For graph-level tasks, it represents the connection status of any pair of nodes in the graph $\mathcal{g}$.** To construct such a vector, we select the upper triangular part of the adjacency matrix of the K-hop subgraph of $v$ or the graph $\mathcal{g}$ and flatten it into the vector, where each item in this vector can denote the connection status of any pair of nodes in the K-hop subgraph of the node $v$ or the graph $\mathcal{g}$.

**Motivation:** The motivation for using this notation is that since we focus on perturbations on the graph structure $\mathbf{A}$ in this paper, we treat the feature vector of $v$ as a constant and use the adjacency matrix of the K-hop subgraph of the node or the adjacency matrix of the graph to represent the structure of the node or graph. For simplicity and clarity, given a GNN encoder $h$ and the concatenation vector $\mathbf{v}$ of the node $v$ or the graph $\mathcal{g}$ as above, **we then omit the node feature matrix $\mathbf{X}$ and simply write the node $v$’s representation $h\_{v}(A,X)$ and the graph $\mathcal{g}$’s representation $h(\mathcal{g})$ as $h(\mathbf{v})$.** Therefore, we use a unified notation $\mathbf{v}$ to denote the node $v$ or the graph $\mathcal{g}$, and further facilitate our theoretical derivations. 


Meta-review: AC read through the reviews, rebuttals and comments, and browse the paper quickly. All reviewers eventually agreed that RES is novel, even though there were some doubts about its difference from randomized edge dropping. Rebuttals seems to address that satisfactorily.
Decision: Accept (poster)