Certifiably Robust Graph Contrastive Learning

Notations. Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ denote a graph, where $\mathcal{V}=\{v_{1},\dots,v_{N}\}$ is the set of $N$ nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges, and $\mathbf{X}=\{\mathbf{x}_{1},...,\mathbf{x}_{N}\}$ is the set of node attributes with $\mathbf{x}_{i}$ being the node attribute of $v_{i}$. $\mathbf{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix of $\mathcal{G}$, where $\mathbf{A}_{ij}=1$ if nodes ${v}_{i}$ and ${v}_{j}$ are connected; otherwise $\mathbf{A}_{ij}=0$. 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 a graph $\mathcal{G}$, the goal is to learn a GNN encoder $h$ to produce representation $\mathbf{z}_{v}$ 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 $\mathbb{G}=\{\mathcal{G}_{1},\mathcal{G}_{2},\cdots\}$, the goal is to learn the latent representation $\mathbf{z}_{\mathcal{G}}$ for each graph $\mathcal{G}$, which can be used to predict downstream label $y_{\mathcal{G}}$ of $\mathcal{G}$. For simplicity and clarity, in this paper, we uniformly denote a node or graph as a concatenation vector $\mathbf{v}$. The representation of $\mathbf{v}$ from encoder $h$ is denoted as $h(\mathbf{v})$. More details are shown in Appendix E.2.

Graph Contrastive Learning. Generally, GCL consists of three steps: (i) multiple views are 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 $\{h_{1},h_{2},\cdots\}$, 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].

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 [41]. Let $c^{+}$,$c^{-}$$\in\mathcal{C}$ denote the positive and negative latent classes drawn from $\eta$, $\mathcal{D}_{c^{+}}$ and $\mathcal{D}_{c^{-}}$ are the distributions to sample positive and negative samples, respectively. For each positive pair $(\mathbf{v},\mathbf{v}^{+})\sim\mathcal{D}_{c^{+}}^{2}$ associated with $n$ negative samples $\{\mathbf{v}^{-}_{i}\sim\mathcal{D}_{c^{-}}|i\in[n]\}$, the widely-used loss for GCL, which is also known as InfoNCE loss [42], can be written as follows:

Attacker’s Goal. We consider an attacker conducts an evasion attack in GCL. Given a well-trained GNN encoder $h$ on a clean graph $\mathcal{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 a 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.

Attacker’s Knowledge and Capability. We assume that the attacker follows the grey-box setting to conduct an evasion attack. Specifically, the attacker has access to a benign GNN encoder $h$ trained on a clean dataset through GCL, 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 on perturbations on the graph structure $\mathbf{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 [11, 24, 43]. We leave the extension to feature attack and defense of GCL as future work. We denote $\delta\in\{0,1\}^{N}$ as the structural noise to a node/graph $\mathbf{v}$, where $N$ denote the number of nodes on the graph $\mathbf{v}$ or $K$-hop subgraph of node $\mathbf{v}$ and $\delta_{i}=1$ indicates the addition of a noisy edge to $\mathbf{v}$ in the $i$-th entry, and its L₀-norm $||\delta||_{0}$ indicates the number of noisy edges. We then have the perturbed version of $\mathbf{v}$ by the attacker, denoted as $\mathbf{v}^{\prime}=\mathbf{v}\oplus\delta$.

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:

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 objective is to judge whether the predictions of target nodes/graphs are altered under specific perturbations. Inspired by [40], we consider the following scenario of a successful attack against the GNN encoder.

Given a clean input $\mathbf{v}$, with positive and negative samples $\mathbf{v}^{+}$ and $\mathbf{v}^{-}$ used in the learning process of GCL, respectively, we consider $\mathbf{v}{{}^{\prime}}=\mathbf{v}\oplus\delta$, where $\delta$ represents structural noise on $\mathbf{v}$ and $\mathbf{v}^{-}$ is the attack target of $\mathbf{v}$. The attacker’s goal is to produce an adversarial example $\mathbf{v}{{}^{\prime}}$ that can deceive the model into classifying $\mathbf{v}$ as similar to $\mathbf{v}^{-}$. Formally, given a well-trained GNN encoder $h$ via GCL, we say that $h$ has been successfully attacked at $\mathbf{v}$ if the cosine similarity $s\left(h(\mathbf{v}{{}^{\prime}}),h(\mathbf{v}^{+})\right)$ is less than ${s\left(h(\mathbf{v}{{}^{\prime}}),h(\mathbf{v}^{-})\right)}$. This indicates that $\mathbf{v}{{}^{\prime}}$ is more similar to $\mathbf{v}^{-}$ than to $\mathbf{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

Similar to the supervised certified robustness, this problem is to prove that the point $\mathbf{v^{\prime}}=\mathbf{v}\oplus\delta$ under the perturbation within budget $k$ is still the positive sample of $\mathbf{v}^{+}$. However, unlike the supervised learning, where we can estimate the prediction distribution of $\mathbf{v}$ by leveraging the labels of the training data, it is difficult to estimate such a distribution in GCL because the label information is unavailable. To address this issue, we first consider a space $\mathbb{B}$ for a sample $\mathbf{v}^{+}$, where each sample within it is the positive sample of $\mathbf{v}^{+}$. Formally, given a sample $\mathbf{v}^{+}$ with the latent class $c^{+}$ from the probability distribution $\mathcal{D}_{c}^{+}$, $\mathbb{B}(\mathbf{v}^{+})$ is defined as

GCL maximizes the agreement of the positive pair in the latent space and assume access to similar data in the form of pairs $(\mathbf{v},\mathbf{v}^{+})$ that comes from a distribution $\mathcal{D}^{2}_{c^{+}}$ given the latent class $c^{+}$. Thus, it is natural to connect the latent class and the similarity between representations. The probability that $\mathbf{v}$ is the positive sample of $\mathbf{v}^{+}$ can be given by the following theorem.

The proof is in Appendix C.1. Theorem 1 manifests that we can derive the probability of $\mathbf{v}$ being the positive sample of $\mathbf{v}^{+}$ based on the cosine similarity under $h$, providing us a feasible way to study the certified robustness problem for GCL without the label information.

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 $\epsilon$ for $\mathbf{v}$ that remove each edge of $\mathbf{v}$ with the probability $\beta$. Formally, given a sample $\mathbf{v}$, the probability distribution of $\epsilon$ for $\mathbf{v}$ is given as:

where $\mathbf{v}_{i}$ denotes the connection status of $i$-th entry of $\mathbf{v}$. Given a well-trained GNN encoder $h$ via GCL and a noise $\epsilon$ with the distribution in Eq. (6), the smoothed GNN encoder $g$ is defined as:

Here $\mathbf{V}$ is the set of all nodes/graphs in the dataset. It implies $g$ will return the representation of $\mathbf{v}\oplus\delta$ whose latent class is the same as that of the most probable instance that $\mathbf{v}\oplus\epsilon$ is its positive sample. Therefore, consider the scenario where some noisy edges are injected into a clean input $\mathbf{v}$, resulting in a perturbed sample $\mathbf{v}{{}^{\prime}}$. With a smoothed GNN encoder $g$ learnt through our method, if we set $\beta$ to a large value, it is highly probable that the noisy edges will be eliminated from $\mathbf{v}{{}^{\prime}}$. Consequently, by running multiple randomized edgedrop on $\mathbf{v}$ and $\mathbf{v}{{}^{\prime}}$, a majority of them will possess identical structural vectors, that is, $\mathbf{v}\oplus\epsilon=\mathbf{v}{{}^{\prime}}\oplus\epsilon$, which implies $\mathbf{v}$ and $\mathbf{v}{{}^{\prime}}$ will have the same latent class and the robust performance of $\mathbf{v}{{}^{\prime}}$ in downstream tasks. We can then derive an upper bound on the expected difference in vote count for each class between $\mathbf{v}$ and $\mathbf{v}{{}^{\prime}}$. With this, we can theoretically demonstrate that $g$ is certifiably robust at $\mathbf{v}$ against any perturbation within a specific attack budget. Specifically, let $p_{\mathbf{v}^{+},h}(\mathbf{v})=\mathbb{P}({\mathbf{v}}\in\mathbb{B}(\mathbf{v}^{+});h)$ for simplicity of notation, $\underline{p_{\mathbf{v}^{+},h}}(\mathbf{v}\oplus\epsilon)$ denotes a lower bound on ${p_{\mathbf{v}^{+},h}(\mathbf{v}\oplus\epsilon)}$ with $(1-\alpha)$ confidence and $\overline{p_{\mathbf{v}^{-}_{i},h}}(\mathbf{v}\oplus\epsilon)$ denotes a similar upper bound, the formal theorem is presented as follows:

The proof is in Appendix C.2. Theorem 2 theoretically guarantees that of $\mathbf{v^{\prime}}$ is still the positive sample of $\mathbf{v}^{+}$ with $(1-\alpha)$ confidence if the worst-case margin of $\mathbf{v}\oplus\epsilon$ under $h$ is larger than $2\Delta$, which indicates that the certified robustness of $h$ at $(\mathbf{v},\mathbf{v}^{+})$ is holds in this case. Moreover, it also paves us a efficient way to compute the certified perturbation size in practical (See in Sec. 5.2).

Though we have theoretically shown the capability of learning $l_{0}^{k}$-certifiably robust node/graph representations with RES, it is unclear whether the certified robustness of the smoothed GNN encoder can be preserved in 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.

The proof is in Appendix C.3. By applying Theorem 3, we can prove given $\mathbf{v}$’s perturbed version $\mathbf{v}{{}^{\prime}}=\mathbf{v}\oplus\delta$, where $||\delta||_{0}\leq k$, if $\mathbf{v}$ and $\mathbf{v^{\prime}}$ satisfy Eq. (8) and Eq. (9) in Theorem 2, we have

which implies provable $l^{k}_{0}$-certified robustness retention of $h$ at $(\mathbf{v},c^{+})$ in downstream tasks.

Theorem 2 holds regardless how the base GNN encoder $h$ is trained. However, introducing randomized edgedrop noise solely to test samples during the inference phase could potentially compromise performance in downstream tasks, which further negatively impact the certified robustness performance based on Eq. 8. In order to make $g$ can classify and certify $(\mathbf{v},c^{+})$ correctly and robustly, inspire by [45], we propose to 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. 5 by using GCL to maximize the agreement between two views. Fig. 1 gives an illustration of general process of training the base GNN encoder via our RES. Given an input graph $\mathcal{G}$, two contrasting views $\mathcal{G}_{i}$ and $\mathcal{G}_{j}$ are generated from $\mathcal{G}$ through stochastic data augmentations. Specifically, two views generated from the same instance are usually considered as a positive pair, while two views constructed from different instances are considered as a negative pair. After that, we inject the randomized edgedrop noise $\epsilon$ to one of the two views $\mathcal{G}_{i}$ and obtain $\mathcal{G}_{i}{{}^{\prime}}$. Finally, two GNN encoders are used to generate embeddings of the views and a contrastive loss is applied to maximize the agreement between $\mathcal{G}_{i}{{}^{\prime}}$ and $\mathcal{G}_{j}$. The training algorithm is summarized in Appendix D.

Following [46, 24], we then present the algorithm to use the smoothed GNN encoder $g(\mathbf{v})$ in the downstream tasks and derive the robustness certificates through Monte Carlo algorithms.

Prediction on Downstream Tasks. We draw $\mu$ samples of $h(\mathbf{v}\oplus\epsilon)$, corrupted by randomized edgedrop noises. Then we obtain their predictions via the downstream classifier. If $c_{A}$ is the class which has the largest frequency $\mu_{c_{A}}$ among the $\mu$ predictions, $c_{A}$ 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 $\mathbf{v}$, we need to estimate the lower bound $\underline{p_{\mathbf{v}^{+},h}}(\mathbf{v}\oplus\epsilon)$ and upper bound $\overline{p_{\mathbf{v}^{-}_{i},h}}(\mathbf{v}\oplus\epsilon)$in Eq. 8. Since it is challenging to directly estimate them in GCL, inspired by Theorem 3, if the prediction of $h(\mathbf{v}\oplus\epsilon)$ in downstream tasks is correct, $\mathbf{v}\oplus\epsilon$ will also be the positive sample of $\mathbf{v}$ under $h$, which indicates the connection between $\underline{p_{\mathbf{v}^{+},h}}(\mathbf{v}\oplus\epsilon)$ and the probability of correctly classified in the downstream tasks. Formally, given a label set $\mathcal{C}$ for the downstream task, let $\underline{p_{A}}$ denotes the lower bound of the probability that $h(\mathbf{v}\oplus\epsilon)$ is correctly classified as $c_{A}\in\mathcal{C}$ in the downstream task, $\underline{p_{B}}$ is the upper bound of the probability that $h(\mathbf{v}\oplus\epsilon)$ is classified as $c$ for $c\in\mathcal{C}\backslash\{c_{A}\}$. we have the following probability bound by a confidence level at least $1-\alpha$:

where $\overline{p_{c}}=B(1-\frac{\alpha}{|\mathcal{C}|};\mu_{c}+1,\mu-\mu_{c}),\forall c\neq c_{A}$, and $B(q;u,w)$ is the $q$-th quantile of a beta distribution with shape parameter $u$ and $w$. After that, we calculate $\Delta$ based on Theorem 2 and the maximum $k$ that satisfies Eq. 8 is the certified perturbation size.

Datasets. We conduct experiments on 4 public benchmark datasets for node classification, i.e., Cora, Pubmed [47], Coauthor-Physics [48] and OGB-arxiv [49], and 3 widely used dataset for graph classification i.e., MUTAG, PROTEINS [50] and OGB-molhiv [49]. We use public splits for Cora and Pubmed, and for five other datasets, we perform a 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, we evaluate RES on 4 types of structural attacks in an evasion setting, i.e., Random attack, Nettack [11], PRBCD [51], CLGA [16] for both node and graph classification. In our evaluation, we first train a 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 an 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 are given in Appendix G.2.

Compared Methods. We employ 4 state-of-the-art GCL methods, i.e., GRACE [30], BGRL [52], DGI [31] and GraphCL [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 our method can enhance the robustness of GCL against structural noises, we also consider two robust GCL methods (i.e., Ariel [15] and GCL-Jaccard [12]) and two unsupervised methods ( i.e., 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 are given in Appendix G.3

Evaluation Protocol. In 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 [31], where each model is firstly trained via GCL and then the resulting embeddings are used to train and test a $l_{2}$-regularized logistic regression classifier. The certified accuracy and robust accuracy on test nodes are used to evaluate the robustness performance. 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. Each experiment is conduct 5 times and the average results are reported.

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 as the target GCL method to train a GCN encoder. The smoothed version of GRACE is denoted as RES-GRACE. The results on Cora, Coauthor-Physics and OGB-arxiv are given in Table 1. From the table, we observe: (i) When no attack is applied on the clean graph, our RES-GRACE achieve state-of-the-art performance, especially on large-scale 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 to 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 in Appendix I.1.

To answer Q2, we use certified accuracy as the metric to 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 $\mu=200$, $(1-\alpha)=99.9\%$ to compute the certified accuracy. The results for various $\beta$ are shown in Fig. 2, where the x-axis denotes the given perturbation size. From the figures, we can observe that $\beta$ controls the tradeoff between robustness and model utility. When $\beta$ is larger, the certified accuracy on clean graph is larger, but it drops more quickly as the perturbation size increases. Especially, when $\beta=0.999$, the certified accuracy is nearly independent of the perturbation size. Our analysis reveals that when $\beta$ is low, more structural information is retained 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 $\beta$ is large, less structural information is retained on the graph, which may affect the performance of 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.

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 J. We also investigate how hyperparameters $(1-\alpha)$ and $\mu$ 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 randomized 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 $\beta$. For our method, we set $\beta=0.9$, $1-\alpha=99\%$, and $\mu=50$. For FLIP, to ensure a fair comparison, we set $\alpha=99\%$ and $\mu=50$, and vary $\beta$ over $\{0.1,0.2,\cdots,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 is ineffective in GCL. That is because FLIP introduces excessive noisy edges, which in turn makes it challenging for GCL to learn accurate representations.

Second goal is to understand how RES contributes to 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${}_{i\textbf{S}j\textbf{S}}$, where $i\in\{0,1,2\}$ and $j\in\{0,1\}$ denote the number of removed structures in the training and testing phases, respectively. For our method, we set $\beta=0.9$, $1-\alpha=99\%$ and $\mu=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 in Fig. 3 (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${}_{1\textbf{S}0\textbf{S}}$ 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) RES${}_{2\textbf{S}j\textbf{S}}$ and RES${}_{i\textbf{S}1\textbf{S}}$ perform worse than other methods because of 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 in Appendix J.1.