Introduction to Graph Neural Network (MPNN)

지동환·2023년 7월 5일

Graph?

\mathcal{G=(V,E)}

$\mathcal V$ : node
$\mathcal E$ : edge
Adjacency Matrix
$A\in \mathbb R ^{n\times n}$
- 방향성이 없는 경우 대칭 행렬이다.
- 연결은 1, 아니면 0으로 표현 됨
Node Feature
$X\in\mathbb R^{n\times d}$
- Node에 타입 $d$ 를 저장.
- 다양한 경우가 가능하지만 가장 기본적인 구조.

Heterogeneous
- $\mathcal {T_n+T_e} > 2$
  - node type의 개수 + edge type의 개수가 2보다 크다.
- 번거로움이 있지만, 다양한 것을 표현할 수 있다.
Homogeneous
- $\mathcal{T_n+T_e=2}$
- node type이나 edge type이 따로 존재한다는 것은 아니다.
- type ≠ label. type을 같은 걸로 만든다고, 같은 label을 가진 것은 아니다.

Node classification
- GNN을 사용해 representation을 만들어서 Latent Space에서 다룬다.
- Softmax!
- Study에서 대부분 다룰 주제이다.
Link Prediction
- 어렵지만 많이 사용되는 task. (RecSys)
- Predict
Graph Classification
- Graph 전체의 type을 판단하는 것.
- 분자 결합 그래프를 보고 무엇인지 맞추기.
- Readout function으로 하나의 representaion으로 합하기

Transductive learning
- 엄청 큰 Graph 하나가 있다.
- 거기서 아는 정보가 있고 아닌게 있다.
- 알고 있는 정보에 대해서만 learning을 한다.
- test 때는? 같은 data에 대해 진행하되, 모르는 data에 대해서.
- Semi-supervised learning이라고 생각하면 된다.
- Study에서 다루는 논문들이 대부분
Inductive learning
- Graph 하나를 알고 training.
- 파란색 graph 여러개로 GNN을 학습
- 학습 때는 보지 못 했던 새로운 graph에 적용.
가장 큰 차이.
- transductive setting에서는 볼 수는 있다.
- Graph에는 구조 정보가 가장 중요하다. 그러한 정보를 볼 수 있다.

\bold h^{(k+1)}_u=\text{UPDATE}^{(k+1)}(\bold h^{(k)}_{u},\text{AGGREGATE}^{(k+1)}(\{\bold h^{(k)}_v,\forall v\in \mathcal N(u)\})) \\ =\text{UPDATE}^{(k+1)}(\bold h^{(k)}_u, \bold m^{(k+1)}_{\mathcal N(u)})

$\mathcal N(u)$ : u node의 모든 이웃들의 set
n1 node 주변의 정보들을 가져오는게 aggregate하는 과정
- 꼭 1 hop 떨어져야 하는가? 아니다.
  - 이웃을 어떻게 정의해 줄 수 있는가? ‘좋은’ 이웃은 어떻게 정의할까?
- 어떻게 가져온다는 거냐? 다양할 수 있다.
  - MLP, Convolution 등.
가져온 정보를 바탕으로 n1의 정보를 변경하는 update 과정.
- update도 어떤 과정을 해도 된다. linear 등등~
- 간단하게 사용한다면 agrregate해 온 정보와 내 정보를 concat하고 linear에 태운다.
멀리 떨어진 친구의 정보를 받아오려면?
- Layer를 쌓으면 된다. 이전 Layer에서 Aggregate 될 때 주변 정보를 담아 놨기 때문에.
- 이웃들에게 받아 오는 정보를 ‘message’라고 한다.
깊게 쌓으면 모든 그래프 정보를 담아올 수 있대!!
- 하지만 그렇지 않다. Oversmoothing…
Graph Neural Network 그 자체라고 생각해 볼 수도 있다. 현재 가장 널리 사용되는 framework

Python, Machine & Deep Learning
- Aggregate 하는게 맞을까?

\bold h^{(k+1)}=\sigma(\bold W^{(k+1)}_{\text{self}}\bold h^{(k)}_{u}+\bold W^{(k+1)}_{\text{neigh}}\sum_{v\in\mathcal N(u)} \bold h^{(k)}_v + \bold b^{(k+1)})

Base GNN
- $\sum$ : Aggregate. 지금이야 더하지만… 다양한 방법이 있지. 평균? Normalize? Attention Weight를 줄 수도 있다. (GAT)
- 가져온 정보를 어떻게 합할까? (Update)
  - 고민해 보면 연구할게 많은 분야일 것이다.

\bold H^{(k+1)}=\sigma(\bold H^{(k)}\bold W^{(k+1)}_{\text{self}}+\bold A\bold H^{(k)}\bold W^{(k+1)}_{\text{neigh}})

Node Level이 아니라, Graph Level에서 표현할 수도 있다.
- 각 단계에서 표현하는 얘기가 같다. 위로 갈 수록 일반화 되어서 표현되는 것.
Graph Neural Network
- 어 ㅅㅂ 그렇네? 싶은 부분들
1 layer를 쌓았을 떄 1 hop. Layer를 하나 쌓으면 1 hop 정보를 가져올 수 있다.
그러면 이론상 Layer를 존나 쌓으면 정보를 많이 담아 오겠구나!!
- 아니다. 모든 Layer의 정보를 가져오면, Feature가 한 점으로 수렴된다.
- Oversmoothing!!!
- n1의 Embedding을 만들 땐 3 hop은 보지도 못했다.
- 멀리 볼 수록 성능이 좋아야 할 것 같은데, oversmoothing이 발생했네? Open question이다.

고려대학교 컴퓨터학과 19. 현재 학부 인턴. 인공지능을 공부하는 중. 주 관심사는 Graph, Vision, 그리고 TRUE AGI.