Chapter18. Limitations of Graph Neural Networks

Limitations of Graph Neural Networks

Today: Limitations of GNNs

• Some Simple graph structures cannot be distinguished by conventional GNNs.

• 노드 색깔이 같으면?? 문제가 생긴다.

• GNNs are not robust to noise in graph data.

• Noise에 대하여 로버스트하지 않다.

1. Limitations of conventional GNNs in a capturing graph structure

Fundamental question

• Given two different graphs, can GNNs map them into different graph representations?

  • 다른 그래프 표현에 대한 함수를 만들 수 있을까에 대한 문제.

• Important condition for classification scenario.

Graph Isomorphism

• Essentially, graph isomorphism test problem

  • 그래프의 동형을 찾는 문제

• No polynomial algorithms exist for general case.

  • NPHARD 문제

• GNNs may not perfectly distinguish any graphs

  • 완벽히 이 문제를 풀 수는 없다.

Rethinking GNNs

• GNNs use different computational graphs to distinguish different graphs

• Node representation captures rooted subtree structure.

• Most discriminative GNNs map different subtrees into different node representations (denoted by different colors)

Recall : Injectivity

• Function is injective if it maps differenet elements into different outputs.

Injective Neighbor Aggregation

• Entire neighbor aggregation is injective if every step of neighbor aggregation is injective

Neighbor aggregation

• Neighbor aggregation is essentially a function over multi-set (set with repeating elements)

Discriminative Power of CNNs can be characterized by that of multi-set functions

Case Study 1: GCN

Recall : GCN uses mean pooling.

injective function

Case Study 2 : GraphSAGE-maxpool

Recall : GraphSAGE uses max pooling.

How can we design injective multi-set function using neural networks?

Injective multi-set function

• Theorem

Most discriminative GNN

Graph pooling in GIN

• Graph pooling is also function over multiset. Sum pooling can give injective graph pooling!

Most discriminative GNN

• So far : GIN achieves maximal discriminative power by using injective neighbor aggregation

WL Graph Isomorphism Test

• GIN is closely related to Wisfeiler-Lehman(WL) Graph Isomorphism Test

• WL test is known to be capable of distinguishing most of real-world graphs.

• Next : We will show GIN is as discriminative as the WL test.

• WL first maps different rooted subtrees to different colors

• WL then counts different colors

• Finally, WL compares the count

WL test and GIN are opreationally equivalent.

Graphs that WL test can distinguish <->Graphs that GIN can distinguish.

Relation to Graph Isomorhpism test

Observation

• GINs have the same discriminative power as the WL graph isomorphism test.

• WL test has been known to distinguish most of the graphs, except for some corner cases

Experiments : Training accuarcy

• Graph classification : social and bio/chem graphs Training accuracy of different GNN architectures. GIN fits training data much better than GCN, GraphSAGE.

Experiments : Test accuracy

• Graph classification : social and bio/chem graphs

GIN outperforms existing GNNs also in terms of test accuracy because it can better capture graph structure.

Summary of the first part

• Existing GNNs use non-injective neighbor aggregation, thus have low discriminative power

• GIN uses injective neighbor aggregationk, and is an discriminative as the WL graph isomorphism test.

• GIN achieves state-of-the-art test performance in graph classification.

2. Vulnerability of GNNs to noise in graph data

Adversarial Attacks in DNNs

• Deep Neural Networks are vulnerable to adversarial attacks

• Attacks are often implemented as imperceptible noise that changes the prediction

Attacks on Graph Domains

• Adversaries are very common in applications of graph neural networks, search engines, recommender systems, social networks, etc.

• These adveraries will exploit any exposed vulnerabilites!

Semi-Supervised Node Classification

• Here we focus on semi-supervised node classification using Graph Convolutional Neural Networks(GCN)

GCN for Semi-Supervised Node Classification

Attack possibilities

Nettack : High Level Idea

• Zugner +, Adverarial Attacks on Neural Networks for Graph Data, KDD`18

Mathematical Formulation

• Find a modified graph that maximized the change of predicted labels of target node

Let's parse the objective function

Tractable Optimization

• In practice, we cannot exactly solve the optimization problem because..

  • Graph modification is discrete (cannot use simple gradient descent to optimize)

  • Inner loop involves expensive re-training of GCN

• Some heuristics have been proposed to efficiently obtain an approximate solution

• For example:

  • Greedily choosing the step-by-step graph modification

  • Simplifying GCN by removing ReLU activation (to work in closed form)

  • ETC

Nettack Experiments

• Semi-Supervised node classification with GCN

  • Class predictions for a single node, produced by 5 GCNs with different random initilizations

Experiments

• The GCN prediction is easily manipulated by only 5 modifications of graph structure (|V|=~2K, |E=5k)

3. Open questions & Future directions

GNNs for Science Domains

• Chemistry : Molecular graphs

  • Molecular property prediction

• Biology : Protein-Protein Interaction Networks

  • Protein function prediction

Challenges of Applying GNNs

• Scarcity of labeled data

  • Labels require expensive experiments

    • Models overfit to small training datasets

• Out-of-distribution prediction

  • Test examples are very different from training in scientific discovery

    • Models typically perform poorly

Pre-training for GNNs

• Pre-training GNNs [Hu+2019]

Making GNNs Robust

• We have seen how to attack GNNs

• Open question:

  • How to defend against the attacks?

Challenges

• Tractable optimization on discrete graph data

• Achieving good trade-off between Accuracy and Robustness