1 of 65

Adversarial Fairness Attacks on Graph Neural Networks

AI & Ethics, IIT Kharagpur

1

Sandipan Sikdar

2 of 65

About Myself

AI & Ethics, IIT Kharagpur

2

  • Assistant Professor at the Faculty of Electrical Engineering and Computer Science (Nov’22 - )
  • Postdoctoral Researcher at RWTH Aachen (2018 – 2022)
  • PhD, Computer Science and Engineering from Indian Institute of Technology Kharagpur
  • Research Interests: Trustworthy AI

3 of 65

Agenda

  • Graph Representation Learning
  • Graph Neural Networks (GNNs)
  • Adversarial Robustness of GNNs
  • Fairness Attacks on GNNs

AI & Ethics, IIT Kharagpur

3

4 of 65

Networks

AI & Ethics, IIT Kharagpur

4

A general model for describing and modeling complex systems

5 of 65

Many Data are Networks

AI & Ethics, IIT Kharagpur

5

Universal language for describing complex data

6 of 65

Machine Learning with Networks

  • Node classification
    • Predict type of a given node
  • Link prediction
    • Predict whether two nodes are linked
  • Community detection
    • Identify densely linked cluster of nodes
  • Network similarity
    • How similar are two (sub)networks?

AI & Ethics, IIT Kharagpur

6

7 of 65

Example: Node classification

AI & Ethics, IIT Kharagpur

7

8 of 65

Example: Link Prediction

AI & Ethics, IIT Kharagpur

8

9 of 65

Machine Learning

Sikdar, Textmining, SS-24

9

1.5

0.2

24

16

2.9

Data

Machine learning algorithm

Prediction, recommendation,….

10 of 65

How to fit a Network?

Sikdar, Textmining, SS-24

10

Machine learning algorithm

Prediction, recommendation,….

11 of 65

How to fit more complex inputs?

Sikdar, Textmining, SS-24

11

Machine learning algorithm

Prediction, recommendation,….

1.5

0.2

24

16

2.9

“Representation”

Automatically learn features

12 of 65

Feature Learning in Graphs

AI & Ethics, IIT Kharagpur

12

Efficient task-independent feature learning for machine learning in networks!

13 of 65

Node Embedding

AI & Ethics, IIT Kharagpur

13

  • Goal is to encode nodes so that similarity in the embedding space (e.g., dot product) approximates similarity in the original network.

14 of 65

Node Embedding

AI & Ethics, IIT Kharagpur

14

Need to define

Similarity function

15 of 65

Node Embedding

  • Encoder
    • Maps each node to a low-dimensional vector

​

​

​

​

  • Similarity function

AI & Ethics, IIT Kharagpur

15

16 of 65

Setup

  •  

AI & Ethics, IIT Kharagpur

16

17 of 65

Neighborhood Aggregation

  • Goal: Generate node embeddings based on local neighborhoods

AI & Ethics, IIT Kharagpur

17

18 of 65

Neighborhood Aggregation

  • Key idea: Nodes aggregate information from the neighbors using neural network

AI & Ethics, IIT Kharagpur

18

19 of 65

Neighborhood Aggregation

  • Intuition: Network neighborhood defines a computation graph

AI & Ethics, IIT Kharagpur

19

20 of 65

Neighborhood Aggregation

  •  

AI & Ethics, IIT Kharagpur

20

21 of 65

Neighborhood Aggregation

  • Key distinctions are in how different approaches aggregate information across the layers.

AI & Ethics, IIT Kharagpur

21

22 of 65

Neighborhood Aggregation

  • Basic approach: Average neighbor information and apply a neural network.

AI & Ethics, IIT Kharagpur

22

23 of 65

Mathematically speaking

  • Basic approach: Average neighbor information and apply a neural network.

AI & Ethics, IIT Kharagpur

23

 

Initial layer-0 embeddings are equal to node features

 

 

Non-linearity (ReLU, tanh)

average of neighbor’s previous layer embeddings

 

24 of 65

Training the Model

​

​

​

​

​

​

  • After K-layers of neighborhood aggregation, we get output embeddings for each node.
  • We can feed these embeddings into any loss function and run stochastic gradient descent to train the aggregation parameters.

AI & Ethics, IIT Kharagpur

24

 

 

 

Trainable parameters

25 of 65

Training the Model

  • Train in an unsupervised manner using only the graph structure
  • Train such that similar nodes have similar embeddings
  • Dot products between node embeddings approximate edge existence

AI & Ethics, IIT Kharagpur

25

 

 

 

otherwise

26 of 65

Training the Model

  • For the loss function defined in the previous section, one needs to go over all pairs of nodes, which would be computationally expensive
  • Graphs in real-world are sparse: more non-edges than edges
  • We can modify the loss function -

AI & Ethics, IIT Kharagpur

26

 

 

Random distribution over all nodes

27 of 65

Training the Model

  • One can also directly train the model on a supervised task such as node classification

AI & Ethics, IIT Kharagpur

27

28 of 65

Training the Model

  • Supervised training: Node classification

AI & Ethics, IIT Kharagpur

28

 

Node labels

Output node embeddings

Classifier parameters

29 of 65

Model design

  1. Define a neighborhood aggregation function
  2. Define a loss function on the embeddings
  3. Train on a set of nodes
  4. Generate embeddings for nodes as needed

AI & Ethics, IIT Kharagpur

29

30 of 65

Inductive capability

  • The same parameters are shared across all nodes
  • We can generate embeddings for unseen nodes

AI & Ethics, IIT Kharagpur

30

31 of 65

Inductive capability

  • The same parameters are shared across all nodes
  • We can generate embeddings for unseen nodes

AI & Ethics, IIT Kharagpur

31

32 of 65

Graph Convolution Networks

  • A slight variation on the neighborhood aggregation idea

​

AI & Ethics, IIT Kharagpur

32

 

 

Basic neighborhood aggregation

GCN neighborhood aggregation

33 of 65

Graph Convolution Networks

  • Same transformation matrix for self and neighbor embeddings
  • Instead of averaging, normalize by the degree of the neighbor

AI & Ethics, IIT Kharagpur

33

 

34 of 65

Summary

  • We looked into methods for generating node embeddings
  • Key idea is to aggregate information from neighbors
    • GNNs differ mainly on how they aggregate information
  • Training can be performed both in unsupervised and supervised manner
  • Inductive ability: We can even obtain embeddings for a new node without re-training

AI & Ethics, IIT Kharagpur

34

35 of 65

Adversarial robustness

AI & Ethics, IIT Kharagpur

35

36 of 65

Adversarial Robustness

  • Deep neural models are vulnerable to adversarial attacks

​

AI & Ethics, IIT Kharagpur

36

37 of 65

Poisoning Attacks

  • Manipulate the training data or labels
  • Change the behavior of the model on particular inputs

​

AI & Ethics, IIT Kharagpur

37

38 of 65

What about Networks?

AI & Ethics, IIT Kharagpur

38

 

 

39 of 65

What about Networks?

AI & Ethics, IIT Kharagpur

39

40 of 65

What about Networks?

AI & Ethics, IIT Kharagpur

40

41 of 65

Poisoning Attacks

AI & Ethics, IIT Kharagpur

41

42 of 65

Poisoning Attacks on Node Classification

AI & Ethics, IIT Kharagpur

42

 

 

 

 

43 of 65

Experiments: Adversarial Attacks

  • GCN on paper citation network (2800 nodes and 8000 edges)

AI & Ethics, IIT Kharagpur

43

44 of 65

Experiments: Adversarial Attacks

  • GCN’s prediction after carefully modifying just 5 edges attached to the target node (direct adversarial attack).

AI & Ethics, IIT Kharagpur

44

45 of 65

Attack Comparison

  • Direct attack is the strongest attack, significantly worsening GCN’s performance.
  • Indirect attack is more challenging than direct attack
  • Random attack is much weaker than adversarial attack

AI & Ethics, IIT Kharagpur

45

GCN is not robust to adversarial attacks but it is somewhat robust to indirect attacks and random noise.

46 of 65

Adversarial Attacks on Fairness

AI & Ethics, IIT Kharagpur

46

47 of 65

Motivation

  • GNNs are deployed on human centric applications
    • Recommender Systems, Social Networks etc.
  • Adversarial attacks impair prediction accuracy of GNNs
    • But what about fairness?

​

  • Could we design adversarial attacks that impair fairness and at the same time preserve accuracy?

AI & Ethics, IIT Kharagpur

47

48 of 65

Example: NBA network

  •  

AI & Ethics, IIT Kharagpur

48

 

49 of 65

Example: NBA network

AI & Ethics, IIT Kharagpur

49

50 of 65

Attack Strategies

  •  

AI & Ethics, IIT Kharagpur

50

 

51 of 65

Attack Strategies

  • Statistical Parity Difference (SPD)

AI & Ethics, IIT Kharagpur

51

 

 

 

 

 

52 of 65

Attack Strategies

  • Statistical Parity Difference (SPD)

AI & Ethics, IIT Kharagpur

52

 

If we consider even a perfect classifier, it would be as fair as the original label distribution.

53 of 65

Attack Strategies

  •  

AI & Ethics, IIT Kharagpur

53

 

 

 

 

 

54 of 65

Attack Strategies

  •  

AI & Ethics, IIT Kharagpur

54

 

 

 

 

 

55 of 65

Attack Strategies

  •  

AI & Ethics, IIT Kharagpur

55

 

 

 

 

 

56 of 65

Attack Strategies

  •  

AI & Ethics, IIT Kharagpur

56

 

 

 

 

57 of 65

Attack Strategies: Summary

  •  

AI & Ethics, IIT Kharagpur

57

58 of 65

Results on Synthetic Graphs

AI & Ethics, IIT Kharagpur

58

59 of 65

On Real-world Datasets

AI & Ethics, IIT Kharagpur

59

FA-GNN degrades the fairness of various GNN models (incl. GAT, GraphSAGE, FairGNN), DD strategy is the most effective one

60 of 65

Are these Attacks Deceptive?

  • Does it also degrade performance?

AI & Ethics, IIT Kharagpur

60

No! FA-GNN can go unnoticed if only model accuracy is monitored.

61 of 65

What about other Fairness Metrics?

  • We also considered equal opportunity and equalized odds

AI & Ethics, IIT Kharagpur

61

62 of 65

Discussion

  • Evidence of the existence and effectiveness of fairness attacks on GNNs
  • Fairness-enhancing GNNs (NIFTY, FairGNN) are vulnerable too
  • Inter-group links are often encouraged to enhance fairness
    • However, our results demonstrate that this might actually lead to degrading fairness (effectiveness of the DD strategy)

AI & Ethics, IIT Kharagpur

62

63 of 65

What followed

  • This was the first work on fairness attacks on GNNs
  • Several new methods have been proposed
    • HANG (Neurips’23)
    • FATE (ICLR’24)
    • NIFA (Neurips’24)
    • …
  • The proposed simple method still is quite difficult to beat ;)

AI & Ethics, IIT Kharagpur

63

64 of 65

Summary

  •  

AI & Ethics, IIT Kharagpur

64

65 of 65

References

AI & Ethics, IIT Kharagpur

65