Analyzing Adversarial Vulnerabilities of Graph Lottery Tickets

1

Graph Neural Networks (GNNs): Applications

Traffic Forecasting

Drug Discovery

Recommendation

Uber Eats

Google Map

Aspirin

2

Unified Graph Sparsification (UGS): Prune the Graph and GNNs Iteratively

Prune

Chen, Tianlong, et al. "A unified lottery ticket hypothesis for graph neural networks." International conference on machine learning. PMLR, 2021.

Computation cost and inference time are reduced

3

Graph Lottery Tickets (GLTs): Maintain Model Performance After Pruning

Accuracy maintained!

Classification accuracy of the original model

Model: 2-layer Graph Convolution Network (GCN) Dataset: Cora

4

Are GLTs Vulnerable to Adversarial Attacks?

Attack

Will GLTs be robust to the attack?

5

Outline

• Analyzing Adversarial Robustness of GLTs

​

• Improving the Robustness of GLTs

​

• Evaluation

​

• Conclusion

6

Adversarial Attacks on Graphs Degrade the Model Performance

+

=

Attacker’s objective:

Degrade the overall classification accuracy of the GNNs,

by maliciously adding edges to the original graph before the GNNs training.

Structural global poisoning attack:

7

Robustness of GLTs to Adversarial Attacks

20%

Model: 2-layer GCN Dataset: Cora

Attack: PGD Attack Perturbation Rate: 20%

8

GLTs Perform Worse as Perturbation Rate Increases

Datasets: Cora, Citeseer, PubMed

​

GNNs:

Graph Convolution Network (GCN),

Graph Isomorphism Network (GIN),

Graph Attention Network (GAT)

​

Attacks: PGD, MetaAttack

​

Perturbation rates: 5%, 10%, 15%, 20%

The vulnerability of GLTs to adversarial attacks is common:

9

Adversarial Attacks Non-uniformly Perturb the Graphs

Attack

Boundary between train and test nodes

Test-Test

Train-Train

Train-Test

Train-Test

Blue pots: Original edges

Red pots: Adversarial edges

Almost not been attacked!

The edges between test nodes are not being attacked!

Li, Kuan, et al. "Revisiting graph adversarial attack and defense from a data distribution perspective." ICLR. 2022.

Clean graph

Attacked graph

Test

nodes

Train

nodes

10

Self-Training: Generate Pseudo-Labels for Test Nodes using a MLP

MLP

Train

MLP

Inference

Select

11

How to Generate Pseudo-Labels?

MLP Prediction:

Select top 2

Select top 2

Selected

test nodes

Selected

test nodes

12

Replace Train Labels with Test Pseudo-Labels

Original Loss function:

Proposed Loss function:

Labels of train nodes

Replace with

13

Improved Performance of GLTs on Attacked Graphs

Model: 2-layer GCN Dataset: Cora

Attack: PGD Attack Perturbation Rate: 20%

14

Improved Robustness of GLTs

15

Conclusion

• The performance of GLTs is significantly affected by global structural poisoning attacks.

• Adversarial attacks (PGD and MetaAttack) non-uniformly perturb the graph structure.

• Clean neighborhood information of test nodes helps improve the robustness of GLTs effectively.

16

Thank you.

Email: zhiyuni@usc.edu

17