1 of 16

Unsupervised Graph Poisoning Attack via Contrastive Loss�Back-propagation

Sixiao Zhang, Hongxu Chen, Xiangguo Sun, Yicong Li, Guandong Xu

DSMI at UTS

2 of 16

Main Contribution

We propose Contrastive Loss Gradient Attack (CLGA), a gradient based unsupervised attack method targeting at graph contrastive learning. Unlike most supervised attack models, CLGA does not rely on labels, and can degrade the quality of the learned embeddings and thus affect the performance of various downstream tasks.

3 of 16

Contents

Preliminaries
Motivations
Contributions
Methodology
Experiments

4 of 16

Preliminaries

Graph representation models

Encoder

1	5	3	6
5	4	0	4
6	3	8	6
8	4	1	0
0	0	1	6

0.1	0.3	0.8

Embeddings

5 of 16

Preliminaries

Graph representation models

graph representation models

supervised

unsupervised

graph contrastive learning

node2vec

DeepWalk

……

6 of 16

Preliminaries

Graph contrastive learning

So what is graph contrastive learning. Well, the core idea is to contrast different views of the original graph. For example, here we have a clean graph with adjacency matrix A and feature matrix X. The first step of graph contrastive learning is to generate two different views of the original graph using some stochastic augmentations t1 and t2. The most common augmentations are like adding or deleting some edges, or masking features. Then the two views’ adjacency matrix and feature matrix A1,X1,A2,X2 are fed into a shared encoder, for example, graph neural network, and it outputs the embeddings of each node. Then these embeddings are used to compute a contrastive loss. By minimizing this loss, the parameters of the encoder is updated. When the learning process is finished, this encoder is used to generate embeddings of the original graph, and those embeddings are used for downstream tasks such as node classification and link prediction. Compared with conventional graph representation models, graph contrastive learning is more robust to adversarial attacks because of the stochastic augmentations t1 and t2. Before going deeper into this, I will first briefly introduce the robustness and graph adversarial attacks.

7 of 16

Preliminaries

Robustness

The robustness of various machine learning models is a hot topic in the research community. For graphs, a small perturbation in the graph structure or the features might change the predictions of the model. For example, in this graph, we have two classes of nodes, the blue ones and the red ones. If we delete this edge, then this node will be classified as a red node with a high probability. For graph representation models, the learned embeddings might be largely perturbed and thus influence the performance of the downstream tasks. Therefore, how to design a model that is robust to such perturbations is an important research direction. There are two main research streams in this direction, one is to design effective adversarial attacks, and another is to defense against these attacks. In this work, we focus on graph adversarial attacks.

8 of 16

Preliminaries

Graph adversarial attacks

Most existing graph adversarial attacks are supervised attacks.

Adversarial attack model

poisoned graph

…

original graph

9 of 16

Motivations

Graph contrastive learning is SOTA unsupervised graph representation model and is more robust to adversarial attacks compared with conventional models.
Existing graph adversarial attacks are mostly supervised attacks. They are not suitable for evaluating the robustness of graph contrastive learning.

Labels are unavailable.

We fill this gap and propose a novel unsupervised attack for graph contrastive learning.

OK, that’s all for the preliminaries and background knowledge. Recall that I have mentioned before that graph contrastive learning is the SOTA unsupervised graph representation model, and is more robust to adversarial attacks compared with conventional models. However, in existing literatures, when evaluating the robustness of graph contrastive learning, people usually use supervised adversarial attacks. But as we know, graph contrastive learning is a type of unsupervised model. Unsupervised models do not use labels because labels are not always available in real-world scenarios. So if we are going to attack graph contrastive learning, it’s better to assume that we don’t have access to any labels. In other words, the attack should also be unsupervised. Recall that existing graph adversarial attacks are mainly supervised attacks, so we fill this gap and propose a novel unsupervised attack for graph contrastive learning.

10 of 16

Contributions

We propose Contrastive Loss Gradient Attack (CLGA), a gradient based unsupervised attack method targeting at graph contrastive learning. Unlike most supervised attack models, CLGA does not rely on labels, and can degrade the quality of the learned embeddings and thus affect the performance of various downstream tasks.
We show by extensive experiments that CLGA outperforms unsupervised attack baselines and has comparable performance with some of the supervised attack methods on three benchmark datasets and on both node classification and link prediction tasks.
We also show that CLGA can be transferred to other graph representation models such as GCN and DeepWalk.
We visualize the learned embeddings to show how CLGA influences the quality of them.

Here are our contributions of this paper. First, we propose Contrastive Loss Gradient Attack (CLGA), a gradient based unsupervised attack method targeting at graph contrastive learning. Unlike most supervised attack models, CLGA does not rely on labels, and can degrade the quality of the learned embeddings and thus affect the performance of various downstream tasks. Second, we show by extensive experiments that CLGA outperforms unsupervised attack baselines and has comparable performance with some of the supervised attack methods on three benchmark datasets and on both node classification and link prediction tasks. Third, we also show that CLGA can be transferred to other graph representation models such as GCN and DeepWalk. At last, we visualize the learned embeddings to show how CLGA influences the quality of them.

11 of 16

Contrastive Loss Gradient Attack

The idea of CLGA is simple. This picture again is the flow chart of graph contrastive learning. As we know, the encoder is learned by minimizing the contrastive loss. So if we want to attack contrastive learning, one possible way is to increase the contrastive loss. If we can somehow locate the most important or informative edges and flip them, then the encoder will learn a suboptimal solution and the performance will be degraded. We achieve this by back-propagating the contrastive loss to the adjacency matrices of the two views. After we have the gradients of the adjacency matrix, we can tell which edge is the most informative. Typically, the edge which has the largest absolute value is the most important or informative edge w.r.t. the loss. So if we flip such edges, the model will be very likely to be poisoned and learn a biased solution. In our method, the back-propagation stops at the two views. We don’t back-propagate through the stochastic augmentation t1 and t2 because they are not always differentiable, for example, adding/deleting nodes or extracting subgraphs. So we only use the gradient of the two views to help locate the most informative edges.

12 of 16

Contrastive Loss Gradient Attack

However, we can’t directly use the gradients of the two views to select edges, because the two views are different from the original graph. In other words, the edges which have the largest gradients in the two views might not be the truly important edges. Because the stochastic augmentations t1 and t2 may cause some edges to have a very large gradient. To this end, to alleviate this issue, we propose to use two little tricks as shown in the two equations here. First, we add up the two gradient matrices of the two views. In this way, the edges that are heavily influenced by the stochastic augmentations will have a small absolute gradient value and will rank at a lower position, so they are not likely to be flipped by CLGA. So why? Well, this is related to the property of contrastive loss. What contrastive loss is doing is to alleviate the gap between the two views. By minimizing the contrastive loss, the encoder will converge to a point where it becomes insensitive to the differences of the two views. That means, even if there are some differences in the two views, like some different edges or different features, the encoder will still try to output similar embeddings for the two views. OK, so now we are looking at the gradients of the adjacency matrix, so imagine that the two views are only different at one edge, so that edge exists in the first view but does not exist in the second view, then how will the gradients of this edge be like? Apparently its gradient in the first view will be negative, and in the second view it will be positive, because the contrastive loss is trying to alleviate the difference between the two views. Then by adding them up, we will get a smaller absolute value. In this way, such edges which are heavily influenced by the stochastic augmentations will rank at a lower position. So this is why we apply the first trick here. OK, to further avoid some special cases or some coincidence, we repeat all the procedures for k times, and add up the delta zeros to obtain a final gradient matrix delta prime. Then we flip the edges with the largest absolute gradient and correct gradient direction in delta prime so that the contrastive loss will increase. In our experiment, we only flip one single edge in each iteration. In each iteration we retrain the encoder using the poisoned adjacency matrix obtained in the previous iteration. We stop after a certain number of edges are flipped.

13 of 16

Experiments

Here are our experiment results. We compare our CLGA with five graph adversarial attack methods on three datasets. We train a contrastive model using the poisoned graphs generated by each attack. Then we use the embeddings to train a logistic regression model and report the node classification accuracy. We also use the embeddings to train an MLP and report the link prediction AUC. So a smaller number means that the corresponding attack method is more powerful and effective. There are four supervised attack methods and one unsupervised attack method. This unsupervised attack baseline is from ICML 2019 and is the only one discussing unsupervised graph adversarial attack. We can observe that our CLGA outperforms the unsupervised baseline, and can sometimes outperform some of the supervised baselines. For example in the second table for link prediction, where the boldfaced ones are the best among all the attacks, and the underlined ones are the second best. We can see that, Metattack is better than our CLGA, but our CLGA is better than other four baselines in most cases.

14 of 16

Experiments

Transferability is another important evaluator for adversarial attacks. A good adversarial attack should have a good performance on not only one or several particular models, but also on other models as well. So the previous experiment results are all done on the contrastive model, so how is the performance of our CLGA on other graph representation models? So here in this table we present the experiment results on DeepWalk and GCN. We train the two models using the poisoned graphs obtained by three adversarial attack methods. The boldfaced ones are the best attacks and the underlined ones are the second best. We can observe that, our CLGA outperforms the second adversarial attack which is the unsupervised baseline. Furthermore, our CLGA can even sometimes outperform the strong supervised baseline Metattack. This suggests that our CLGA not only work well for contrastive learning, but also transfer well to other representation models.

15 of 16

Experiments

16 of 16

Conclusions

In this paper, we introduce Contrastive Loss Gradient Attack (CLGA), an unsupervised untargeted poisoning attack for attacking graph contrastive learning. This is the first work to attack graph contrastive learning in an unsupervised manner without using labels. The quality of the learned embeddings are damaged and the performance of various downstream tasks is degraded. We show by extensive experiments that our CLGA outperforms unsupervised baselines and has comparable and even better performance with supervised baselines. We also show that CLGA is able to be transferred to other graph representation models such as DeepWalk and GCN.