GNN Notes : LEC 01

Lec 01 GNN

1. Why Graph?

Graph is general language for entities with relations

2. Type of Graph

  • Natural Network
  • Graph

3. Why Hard?

  • Arbitrary size & Complex topology
  • No reference point
  • Dynamic
  • multimodal

4. Process of supervised graph

1
2
graph LR
1[RawData]-->2[GraphData]-->3[LearningAlgorithm]-->4[Model]

Use Represent Learning instead of Feature Engineering to realize transferring raw data to graph data

5. Classic Graph ML Tasks

  • Node Classification
  • Edge Prediction
  • Graph Classification
  • Clustering : if nodes form a community
  • Graph Generation
  • Graph Evolution

6. Examples of Graph ML Tasks

Node Level

predict residue’s position

Edge Level

Recommend System

Predict the size effects

Subgraph Level

Traffic Prediction

Graph Level

Drug Discovery

Generating novel molecules

7. Components of a Network

$N$ : nodes or vertices

$E$ : edges or links

$G(N,E)$ : network or graph

8. Network Classification

classification from Attribution

  • Directed / Undirected
  • Weighted / Unweighted
  • self-edge
  • multi-graph
  • strongly connected / weakly connected / disconnected

Special Class

  • Bipartite Graph
  • Folded Bipartite Graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
flowchart TB
subgraph Projection-V
VA[A]
VB[B]
VC[C]
VD[D]
VA---VB
VB---VC
VC---VD
VB---VD
end
subgraph total
T1((1))
T2((2))
T3((3))
T4((4))
T5((5))
T6((6))
T7((7))
TA[A]
TB[B]
TC[C]
TD[D]
T1 & T2 & T3 --- TA
T2 & T5 --- TB
T4 & T5 --- TC
T5 & T6 & T7 --- TD
end
subgraph Projection-U
U1((1))
U2((2))
U3((3))
U4((4))
U5((5))
U6((6))
U7((7))
U1---U2---U3---U1
U2---U5
U6---U7---U5---U6
U5---U4

end

9. Node Degree

For Undirected

$k_i$ : the degree of node $i$

$\bar k$ : the average degree of nodes

$\bar k = \frac 1 N \sum_{i=1}^N k_i=\frac{2|E|}{N}$

For Directed

$k_i^{in}$ : the in-degree of node $i$

$k_i^{out}$ : the out-degree of node $i$

$\bar k_i^{in} = \bar k_i^{out} = \frac{|E|}{|N|}$

10. Represent Graph

(1) Adjacency Matrix

Element $A_{ij}$
$$
A_{ij} = \left{ \begin{array}{rcl}
1 & , & if\ link\ from\ i\ to\ j\ exists\
0 & , & otherwise
\end{array}\right.
$$
Degrees

For Undirected

$k_i = \sum_{j=1}^N A_{ij}$

$k_j = \sum_{i=1}^N A_{ij}$

$L = \frac 12 \sum_{i=1}^N \sum_{j=1}^N A_{ij}$

For Directed

$k_j^{in} = \sum_{i=1}^{N}A_ij$

$k_i^{out} = \sum_{j=1}^{N}A_ij$

$L = \sum_{i=1}^N \sum_{j=1}^N A_{ij}$

(2) Edge List

(3) Adjacency List