[GNN] 1. Graph란?

 

[GNN] 1. Graph란?

 

 

 

1. Graph란?

- 왜 Graph?

- Graph의 종류

- Graph의 표현

- Graph Tasks

- Graph의 Motif 

 

 

2. GNN 이전의 Machine Learning을 활용한 Graph 학습 

- Node Feature

• Eigenvector centrality
• Betweenness centrality
• Closeness centrality
• .....

- Link Feature

• Distance-based feature
• Local neighborhood overlap
• Global neighborhood overlap

- Graph Feature

• Graphlet kernel
• Weisfeiler-Lehman Kernel 

 

3. Graph Representation Learning

- Node Embedding

- Graph Embedding 

 

 

4. GNN

- Recurrent Graph Neural Networks (RecGNNs)

- Convolutional Graph Neural Networks (ConvGNNs)

• Spectral Model
• Spatial Model 

- Graph AutoEncoders (GAEs) 

• Network Embedding
• Graph Generation

- Spatial-Temporal Graph Neural Networks (STGNNs)

• CNN Based 
• RNN Based
• CNN & RNN based Model 
• Attention based Model 

 

5. GNN의 Benchmark Datasets

- Citation Networks

- Biochemical Graphs

- Social Networks 

- Others

 

 

6. GNN Library

- Pytorch Geometric

- DGL 

 

 

 

 

---

 

 

 

그래프란 무엇이며 왜 쓰는가?

 

Data Representation - 이미지, 문장 

이미지는 각 pixel들로 값들을 표현하며, 문장은 글자 또는 단어 단위로 값들을 표현한다. 

이미지는 CNN을 이용하며 filter를 이동시키며 중요한 정보를 추출했고, 문장은 RNN을 이용하여 순서대로 단어가 들어오면 정보를 추출한다. 

 

 

=> social graph, 3D mesh, molecular Graph 등 다양한 데이터 또한 그래프의 형태로 나타낼 수 있다! 

 

 

How to Measure a Network 

 

1) Degree Distribution

 

: 어떤 그래프가 있을 때, 우리가 여기서 랜덤으로 Node를 뽑았을 때, 그 Node의 degree가 k일 확률들의 분포

 

 

2) Path Length 

 

: 각 Node들이 연결된 Sequence 

 

+) Distance : 여러 Path중 Node(i) -> Node(j)로 가는 Shortest Path를 Distance라고 하며, 길이 없을 때는 Path는 보통 무한대라고 정의

+) Diameter (직경) : 어떤 그래프에서 Path의 최대값

+) Avearge Path length (평균 경로): Path length의 평균값 (무한대인 Path는 무시한다)

 

 

3) Clustering Coefficient 

 

: 어떤 노드 i에 대해 얼마나 이 노드와 연결된 노드들끼리 잘 연결돼 있는가를 나타낸 지수

 

 

 

4) Connected Components (Connectivity)

 

: 가장 큰 Component의 크기 

 

 

 

 

Graph Tasks

 

 

 

1) Node Classification : “주어진 node”가 어느 속성에 속할 것인지 구분하는 task

 

2) Graph Classification :  “그래프 자체”가 어느 속성에 속하는지 구분하는 것

 

3) Edge Classification : “주어진 edge”가 어느 속성에 속하는 것인지 구분하는 것

 

4) Link Prediction : Edge Classification과 달리, node 간에 “edge 자체가 있을지 없을지”를 예측하는 task

 

 

 

 

https://velog.io/@thecho7/Graph-Neural-Network-3

Graph Neural Network - (3)