1 of 48

Graph

Prof. Seungchul Lee

Industrial AI Lab.

2 of 48

Graph (or Network)

  •  

2

3 of 48

Graph (or Network)

  • Graphs can be directed or undirected

​

  • Graphs model any situation where you have objects and pairwise relationships (symmetric or asymmetric) between the objects

​

3

4 of 48

Graph Representation

  •  

4

1

2

7

6

4

5

3

5 of 48

Adjacent Matrix

  •  

5

1

2

7

6

4

5

3

6 of 48

Adjacent Matrix

  •  

6

1

2

7

6

4

5

3

sparse

7 of 48

Quiz 1

  • Directed graph

​

​

​

​

​

  • Undirected graph

​

7

1

3

2

4

1

3

2

4

8 of 48

Quiz 1

  • Directed graph

​

​

​

​

​

  • Undirected graph

​

8

1

3

2

4

1

3

2

4

1 2 3 4

1 0 1 1 1

2 0 0 1 0

3 0 0 0 1

4 0 0 0 0

1 2 3 4

1 0 1 1 1

2 1 0 1 0

3 1 1 0 1

4 1 0 1 0

9 of 48

Quiz 2

  • Directed graph G = (V,E)
    • V = {0,1,2,3,4,5}
    • Adjacency list

​

​

​

​

​

​

​

  • Q: draw the corresponding directed graph

​

​

​

9

10 of 48

Quiz 2

  • Directed graph G = (V,E)
    • V = {0,1,2,3,4,5}
    • Adjacency list

​

​

​

​

​

​

​

  • Q: draw the corresponding directed graph

​

​

​

10

11 of 48

Degree

  •  

11

1

3

2

4

12 of 48

Self-Connecting Edges

  •  

12

1

3

2

4

13 of 48

Neighborhood Normalization

  •  

13

1

3

2

4

14 of 48

Neighborhood Normalization

  •  

14

1

3

2

4

15 of 48

NetworkX

  • https://networkx.org/
  • Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks

15

16 of 48

NetworkX

  • Adjacency matrix

16

17 of 48

Graph Neural Networks

17

18 of 48

Graph Data

  • Characteristic of graph data
    • A graph contains relationships between data

​

​

​

​

18

Person 1

    • Age
    • Height
    • Weight
    • College
    • etc.

Person 2

    • Age
    • Height
    • Weight
    • College
    • etc.

Independent

Dependent

19 of 48

Dependency of Graph Data

  •  

19

20 of 48

Connection between CNN and GCN

  • GCNs perform similar operations where the model learns the features by inspecting neighboring nodes
  • The major difference
    • CNNs are specially built to operate on regular structured data
    • GCNs operate for the graph data that the number of nodes connections vary and the nodes are unordered

20

Kernel

Adjacent matrix

and Kernel

21 of 48

Basics of GCN

  •  

21

1

3

2

4

message

aggregate

Adjacent matrix

and Kernel

22 of 48

Basics of GCN

  1. Message: information passed by neighboring nodes to the central node
  2. Aggregate: collect information from neighboring nodes
  3. Update: embedding update by combining information from neighboring nodes and from itself

​

​

​

​

22

1

3

2

4

1) message

1

3

2

4

update

aggregate

23 of 48

2) Message Aggregation from Local Neighborhood

23

1

3

2

4

aggregate

 

 

 

 

aggregate

24 of 48

3) Update

24

 

 

 

 

aggregate

 

1

3

2

4

update

Update 2:

Non-linear function

Update 1:

Linear combination

25 of 48

Further Improvements

  • Message Passing with Self-Loops
    • As a simplification of the neural message passing approach, it is common to add self-loops to the input graph and omit the explicit update step

​

​

​

​

​

​

​

25

26 of 48

Further Improvements

  • Message Passing with Self-Loops
    • As a simplification of the neural message passing approach, it is common to add self-loops to the input graph and omit the explicit update step

​

​

​

​

  • Neighborhood Normalization
    • The most basic neighborhood aggregation operation simply takes the sum of the neighbor embedding.
    • One issue with this approach is that it can be unstable and highly sensitive to node degrees.
    • One solution to this problem is to simply normalize the aggregation operation based upon the degrees of the nodes involved.
    • The simplest approach is to just take a weighted average rather than sum.

​

​

26

27 of 48

Message Passing

27

1

3

2

4

 

 

 

 

 

28 of 48

1) Message Passing with Self-Loops

28

1

3

2

4

 

 

 

 

 

29 of 48

2) Neighborhood Normalization

29

 

1

3

2

4

 

 

 

 

30 of 48

Q: Which One Is Trainable?

30

 

1

3

2

4

 

 

 

 

Only trainable parameters

31 of 48

Finally Graph Convolutional Networks

  • Multi-layer Graph Convolutional Network (GCN)

31

Self-loops

Neighborhood Normalization

32 of 48

Finally Graph Convolutional Networks

  • Multi-layer Graph Convolutional Network (GCN)

32

Multi-layers

or

sigmoid

or

sigmoid

Image from https://tkipf.github.io/graph-convolutional-networks/

33 of 48

Feature Vector Updates

33

34 of 48

Feature Vector Updates

34

35 of 48

Feature Vector Updates

35

36 of 48

Build 2-layer GCN using ReLU as the Activation Function

36

or

sigmoid

or

sigmoid

37 of 48

Readout: Permutation Invariance

  • Adjacency matrix can be different even though two graph has the same network structure
    • Even if the edge information between all nodes is the same, the order of values in the matrix may be different due to rotation and symmetry
  • Readout layer makes this permutation invariant by multiplying MLP

​

  • Node-wise summation

37

38 of 48

Finally Graph Convolutional Networks

  • Similar to convolutional neural network
  • Multiple graph convolution layers

​

​

​

​

​

38

39 of 48

GCN as Message Passing Framework

39

Image from Graph Representation Learning by William L. Hamilton

40 of 48

Tasks for Graph Neural Network

  • 3 GNN applications

​

​

​

​

40

Task 1: node classification

Task 2: edges prediction

Task 3: graph classification

Label Prediction

Edge Prediction

Label A

Label B

41 of 48

List of GNN Python Libraries

  • PyTorch Geometric
    • PyG
    • Built upon PyTorch
  • Deep Graph Library (DGL)
    • Based on PyTorch, TensorFlow or Apache MXNet.
  • Graph Nets
    • DeepMind’s library for building graph networks in Tensorflow and Sonnet
  • Spektral
    • Based on the Keras API and TensorFlow 2

​

41

From https://neptune.ai/blog/graph-neural-networks-libraries-tools-learning-resources

42 of 48

Lab 1: Node Classification using Graph Convolutional Networks

  • CORA dataset
    • This dataset is the MNIST equivalent in graph learning
  • The CORA dataset consists of 2708 scientific publications classified into one of seven classes.
    • Case_Based: 298
    • Genetic_Algorithms: 418
    • Neural_Networks: 818
    • Probabilistic_Methods: 426
    • Reinforcement_Learning: 217
    • Rule_Learning: 180
    • Theory: 351
  • The citation network consists of 5429 links.
  • Each publication in the dataset is described by a 0/1-valued word vector indicating the absence/presence of the corresponding word from the dictionary.
  • The dictionary consists of 1433 unique words.

42

43 of 48

CORA dataset

  • 2708 nodes of papers
  • 5429 edges by citation
  • 7 classes

43

44 of 48

Graph G and Normalized Adjacency Matrix A

44

45 of 48

GCN Model

45

46 of 48

Train and Evaluation

  • Train

​

​

​

​

​

​

​

  • Evaluation

46

47 of 48

Low Dimensional Mapping

  • T-SNE

47

48 of 48

Learning Resources for Graph Neural Networks

​

  • Books

​

48

From https://neptune.ai/blog/graph-neural-networks-libraries-tools-learning-resources