🔏
Tobigs Graph Study
  • Tobigs Graph Study
  • Chapter1. Machine Learning with Graphs
    • Python code - graph basic
  • Chapter2. Properties of Networks, Random Graph Models
    • Python code - kronecker product
  • Chapter3. Motifs and Structural Roles in Networks
    • Python code - RoIX & ESU Tree
  • Chapter4. Community Structure in Networks
  • Chapter5. Spectral Clustering
  • Chapter6. Message Passing and Node Classification
  • Chapter7. Graph Representation Learning
  • Chapter8. Graph Neural Networks
  • Chapter9. Graph Neural Networks:Hands-on Session
  • Chapter10. Deep Generative Models for Graphs
  • Chapter11. Link Analysis: PageRank
  • Chapter12. Network Effects and Cascading Behavior
  • Chapter13. Probabilistic Contagion and Models of influnce
  • Chapter14. Influence Maximization in Networks
  • Chapter15. Outbreak Detection in Networks
  • Chapter16. network evolution graph
  • Chapter17. Reasoning over Knowledge Graphs
  • Chapter18. Limitations of Graph Neural Networks
  • Chapter19. Applications of Graph Neural Networks
Powered by GitBook
On this page
  • Limitations of Graph Neural Networks
  • Today: Limitations of GNNs
  • 1. Limitations of conventional GNNs in a capturing graph structure
  • Fundamental question
  • Graph Isomorphism
  • Rethinking GNNs
  • Recall : Injectivity
  • Injective Neighbor Aggregation
  • Neighbor aggregation
  • Case Study 1: GCN
  • Case Study 2 : GraphSAGE-maxpool
  • Injective multi-set function
  • Most discriminative GNN
  • Graph pooling in GIN
  • Most discriminative GNN
  • WL Graph Isomorphism Test
  • Relation to Graph Isomorhpism test
  • Experiments : Training accuarcy
  • Experiments : Test accuracy
  • Summary of the first part
  • 2. Vulnerability of GNNs to noise in graph data
  • Adversarial Attacks in DNNs
  • Attacks on Graph Domains
  • Semi-Supervised Node Classification
  • GCN for Semi-Supervised Node Classification
  • Attack possibilities
  • Nettack : High Level Idea
  • Mathematical Formulation
  • Tractable Optimization
  • Nettack Experiments
  • Experiments
  • 3. Open questions & Future directions
  • GNNs for Science Domains
  • Challenges of Applying GNNs
  • Pre-training for GNNs
  • Making GNNs Robust

Was this helpful?

Chapter18. Limitations of Graph Neural Networks

PreviousChapter17. Reasoning over Knowledge GraphsNextChapter19. Applications of Graph Neural Networks

Last updated 4 years ago

Was this helpful?

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

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

injective function