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.

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


  • 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


  • 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?


  • Tractable optimization on discrete graph data

  • Achieving good trade-off between Accuracy and Robustness

Last updated