> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter18..md).

# 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.
* 노드 색깔이 같으면?? 문제가 생긴다. 

![](/files/-M8TehkeWHK2k317LTMP)

* GNNs are not robust to noise in graph data.
* Noise에 대하여 로버스트하지 않다. 

![](/files/-M8TgH2zt0J6yxid2Vo-)

## 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.

![](/files/-M8Th3nGAqmSe4wrfXjp)

### 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

![](/files/-M8UtLF_eIrD99pWkWgQ)

* Node representation captures rooted subtree structure.

![](/files/-M8UtchCSYMP3vwGSRYk)

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

![](/files/-M8UtqXgwBLvJHiUhx1e)

![](/files/-M8UtzxEWfQgjfQ7xP8p)

### Recall : Injectivity

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

![](/files/-M8UuPsWeikVVIwOQXHM)

### Injective Neighbor Aggregation

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

![](/files/-M8UuiqExeAR-AY8VilG)

### Neighbor aggregation

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

![](/files/-M8UvR9UnHYN7MwlPkeC)

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

### Case Study 1: GCN

Recall : GCN uses mean pooling. 

![](/files/-M8Uw4251UEmaw1i_wsV)

![](/files/-M8Uw8Il5AXcA0gAGkFm)

![injective function](/files/-M97owU0n3Y7Dxti_Y7u)

###  Case Study 2 : GraphSAGE-maxpool

Recall : GraphSAGE uses max pooling.

![](/files/-M8UwNilHt2d63VE7ERA)

![](/files/-M8UwSS8SwFhhBb5Fp58)

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

### Injective multi-set function

* Theorem

![](/files/-M8Uwh_VuuJCI432X1Ui)

![](/files/-M8Uwnf4QQp3XY9NiPBm)

### Most discriminative GNN

![](/files/-M8Ux7mQy4KPIIKVTS_A)

### Graph pooling in GIN

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

![](/files/-M8UxXPN_HDLo2QiFZwe)

### 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

![](/files/-M8V5ZTT_J8Q3NoWCSws)

* WL then counts different colors

![](/files/-M8V5fbSBJ-obpd-L0rW)

* Finally, WL compares the count

![](/files/-M8V5nJTQc5QpKiVnMjy)

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

![](/files/-M8V6J_8G8T89mn55wUc)

### 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.

![](/files/-M8V6a7XICvVGdt-rvGS)

![](/files/-M8V6fzgB7jccFhibElJ)

### 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.&#x20;

![](/files/-M8V7Y5QiYIlFtdlJjJs)

### 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.&#x20;
* 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

![](/files/-M8VC2c6oV2VD2CpV409)

### 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)**

![](/files/-M8VCWyQ7VERFKHxvqt3)

### GCN for Semi-Supervised Node Classification

![](/files/-M8VCc5jj7_cvUPQ7hmi)

### Attack possibilities

![](/files/-M8VCm5lf6KET8wrzhPC)

### Nettack : High Level Idea

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

![](/files/-M8VCy7JMpecRenw76_c)

### Mathematical Formulation

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

Let's parse the objective function

![](/files/-M8VDFR0zBNN48vFIfTa)

![](/files/-M8VDKIqkbmeldDl9Nk8)

![](/files/-M8VDN7jCu_USEypTPkh)

![](/files/-M8VDQaw7hwXaMRRh2ZY)

### 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

![](/files/-M8VDo71x1SmxC6LVqX-)

* 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

![](/files/-M8VEEuBi2AwbPUz0c-v)

### Experiments

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

![](/files/-M8VEWMLaSufy710uI0u)

## 3. Open questions & Future directions

### GNNs for Science Domains

* Chemistry : Molecular graphs
  * Molecular property prediction

![](/files/-M8VElW4vHY38DR7THPc)

* Biology : Protein-Protein Interaction Networks&#x20;
  * Protein function prediction

![](/files/-M8VEtjT9TJVoj05gsIu)

### 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]

![](/files/-M8VFLsp8JgYwQuHvoHG)

### 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

####