# 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

####


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tobigs.gitbook.io/tobigs-graph-study/chapter18..md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.