GNN소개 및 내용 정리

참조: (번역) medium.com/watcha/gnn-%EC%86%8C%EA%B0%9C-%EA%B8%B0%EC%B4%88%EB%B6%80%ED%84%B0-%EB%85%BC%EB%AC%B8%EA%B9%8C%EC%A7%80-96567b783479

GNN 소개 — 기초부터 논문까지

참조: (원본) towardsdatascience.com/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

An Introduction to Graph Neural Network(GNN) For Analysing Structured Data

1. Graph Theory
2. graph = vertices + edges

• G = (V, E) where V is a set of nodes and E is the edges between the nodes
• Adjacency Matrix: A로 표현하며 차원은 $N\times N$.
• Feature Matrix: 각 노드의 feature를 나타내며 차원은 $N\times F$

Why is a graph difficult to analyze?

1. 그래프가 Eucliean space상에 존재하지 않기 때문에
2. 그래프가 고정되어 있는 형태가 아니기 때문에
3. 인간이 해석하기 쉽도록 visualization이 어렵기 때문에

Why use Graphs?

1. relationship과 interaction와 같은 개념에 대하여 제공을 잘해준다.
2. 풀고자 하는 문제상황을 단순화시켜 접근할 수 있다.

Traditional Graph Analysis Methods

1. searching algorithm 
   1. BFS
   2. DFS
2. Shortest path algorithm
   1. Dijkstra's algorithm
   2. Nearest Neighbor 
3. spanning-tree algorithm
   1. Prim's algorithm
4. Clustering methods
   1. Highly Connected Components
   2. k-mean algorithm

한계: 알고리즘을 적용하기 전에 입력 그래프에 대한 prior knowledge 필요

Graph Neural Network

• node가 이웃과의 연결에 의해 정의된다
• 연결이 되어 있지 않은 점은 의미가 없음
• node embedding: final state of the node

Recurrent Graph Neural Network

• Banach Fixed-Point Theorem
•