Deep Learning for Graphs: Naïve Approach부터 Graph Encoder, GIN까지

Matrix는 풀 수 없는 문제들을 graph를 이용해 술술 풀어버리는 GNN의 매력에 한창 빠져있는 저는, 대학원 졸업논문에까지 GNN을 도입하기로 결정했습니다! 😂😂
또한 Computer Vision 분야에서 자율주행을 맡고 있는 친구에게도 GNN 영업을 성공했다는 후문이… (진짜)

아무래도 아직 CV나 NLP 분야에 비해 상대적으로 연구 분야가 늦게 떠올라서, 개척 할 만한 연구가 많다는 점 또한 흥미로운 것 같아요. 다만 친구가 말하길 GNN 최신 논문들 리뷰하는데 코드가 아직 안 올라와 있어서 논문만 열심히 읽었다고 합니다..

이전 포스팅에서는 GNN이 무엇인지, 그리고 활용 분야와 한계점에 대해서 소개하고 PageRank에 GNN을 활용한 논문을 함께 리뷰해보았는데요,

https://sysout.tistory.com/93

GNN Overview 및 검색 엔진에 연결해 보기 (Predict Then Propagate: Graph Neural Networks Meet Personalized PageRank)

이번 포스팅에서는 graph를 실제로 deep learning network에 넣기 위해서 encoding, 혹은 embedding 하는 방법을 논문과 함께 수식까지! 살펴보려 합니다.

 

---

Graph Embedding Using Naïve Approach

Definition

Graph를 표현하는 방법 중 가장 naive하게 접근하는 방법입니다. 위 그래프와 같은 undirected graph가 있다고 하면, 인접 행렬(adjacency matrix)과 각 node의 feature를 추출한 feature vector는 아래와 같이 나오게 됩니다. Feature value의 경우 임의의 값을 정하여 넣었습니다.

Naive하다-는 단어의 의미처럼 순수하게, 아무런 값의 변경 없이 두 matrix를 concatenate합니다. 그리고 이 matrix를 input으로 넣고 GNN에 feed-forward 하게 됩니다.

이러한 방법은 매우 간단하고, 직관적이지만 상용화하기에는 많은 단점이 있습니다.

Limitations

• Not SCALABLE
  • Graph size가 커지면 그만큼 parameter의 개수도 기하급수적으로 증가합니다.
  • Graph size가 달라지면 기존 matrix를 사용할 수 없고 새로 matrix를 만들어야 합니다.
• Not Invariant to Node Reordering
  : Node가 재정렬되면, 같은 graph여도 기존 matrix를 사용할 수 없습니다.

---

 

Graph Embedding Using Graph Encoder

Main Idea

이러한 단점을 보완하기 위하여, node embedding (vector representation) 방법으로 graph encoder가 제안되었습니다. 이 encoder의 main idea는 아래 속담과 비슷하다고 할 수 있습니다.

A man is known by the company he keeps.

직역하면, "사귀는 친구들을 보면 그 사람을 알 수 있다." 라는 뜻인데요, node를 벡터 공간에 나타내었을 때 주변 node의 정보로 해당 node를 classification하고, edge를 연결해주는 방법입니다.

본격적으로 GNN으로 들어가 보면, graph encoder는 보통 2가지 절차로 구성됩니다.

1. Aggregation (Message Passing)
   : 이웃 node의 정보들을 결합
2. Combination (Update)
   : 해당 결과를 기반으로, target node의 정보를 계산

Graph-level task에서는 3번째 절차로 모든 node들을 결합하여 graph의 정보를 나타내는 Readout을 하는데, 본 포스팅에서는 node/edge-level에 집중하고 있기 때문에 언급만 하고 자세하게는 다루지 않겠습니다. 

Aggregation

이웃 node들의 k-1번째의 hidden state를 결합합니다. 그림에서는 vertex 1은 2, 4와 연결되어 있으니 target node에 해당하는 aggregation 값은 k-1번째 h2, h4를 결합한 값이 되겠습니다.

Combination

그 다음, k-1번째 target node의 hidden state와 방금 계산했던 aggregated information을 사용하여 k 번째 target node의 hidden state를 update 하는 작업을 합니다. 위 그림에서는 k번째 h1 값을 업데이트 하기 위해 k-1번째의 h1 값과 인접 노드인 k-1번째의 h2, h4를 결합한 aggregated 값을 combine하여 새로운 값을 얻어내는 것을 보실 수 있겠습니다.

수식으로 살펴보기

Aggregate, combine으로 추상화하여 graph encoder를 알아보았는데요, 좀 더 심도 있게 수식으로도 살펴보자구요! 💨💨

K개의 layer로 이루어진 Deep Encoder에서는 아래와 같은 수식으로 hidden state 업데이트 함수를 정의합니다.

두 번째 식을 풀어서 설명하자면 다음과 같습니다 (K/k 대소문자 유의하면서, 색을 맞춰보며 이해해 보아요!) — 1부터 K 사이에 존재하는 모든 k에 대하여, k번째 hidden state는 해당 노드에 인접한 neighbor들의 직전 layer (k-1번째 layer) embedding 의 평균과 가중치 W의 곱에, 직전 layer embedding 값에 B를 곱한 결과에다가 비선형성을 준 최종 값이 k번째 node의 hidden state를 embedding한 값이 되겠습니다. 그리하여 마지막 K번째 layer에서 aggregation 값을 얻을 수 있게 되고, 그것을 z_v라고 칭하게 된 것이죠. 문장이 길어서 한번에 읽기 힘들었을 수도 있는데 이제 숨 쉬어도 됩니다~! ㅎㅎ

이제 핵심은 다 깨우쳤습니다. 나머지 값들은 기존에 주어진 조건 내에서 연산을 하는 방식이니, 결과적으로 neural network 내의 learnable paramter는 W, B 두 개가 되겠습니다.

 

---

How Well Can GNNs Perform the Graph Isomorphism Test?

Graph Isomorphism Test란, 두 그래프가 주어졌을 때 서로가 같은 graph인지 아니면 다른 graph인지 판별하는 문제입니다. 얼핏 생각하기에는 쉬운 문제처럼 보이지만 모든 node의 인접 node를 비교하면서 풀다 보면 polynomial 시간 내에 풀기 힘든 문제입니다. 흔히 NP-problem 이라고 하죠.

그렇다면 GNN이 얼마나 이 문제를 잘 풀수 있는지 볼까요? 아직 GNN 영업은 끝나지 않았다구욧!

GNN이 처음부터 isomorphism 여부를 잘 구분하지는 못합니다. Graph를 설계할 때 node aggregation 방법을 잘 선택해줘야 하죠. 예컨대 mean pooling, max pooling의 경우 중복된 node가 있다면 다른 graph를 같은 graph로 인식하기 쉽상입니다. How Powerful Are Grraph Neural Networks? (Xu et al.) 논문에서는 기존 GCN이나 GraphSage가 가지지 못했던 'Injectivity'에 집중하여 GIN(Graph Isomorphism Network) 모델을 제시하며 이 문제를 해결하고자 합니다.

Injectivity를 한글로 번역하게 되면 '단사'라는 뜻인데요. 잠깐 학창시절에 배운 수학을 떠올려 보면 왼쪽 그림처럼 다른 input에 같은 output이 매칭될 수 있는 함수의 경우 non-injective function, 오른쪽 그림처럼 다른 input이면 다른 output을 낼 수 있는 함수를 injective function이라고 칭합니다. 

그 식은 생각보다 간단합니다. 비선형 함수를 먼저 적용하고, 이를 더한 다음 다시 비선형성을 주는 거죠. MLP + Sum Pooling의 형태로 이해하면 되겠습니다.

이 모델은 graph isomorphism test를 아주 잘 푸는 Weisfeiler-Lehman (WL) Test 방식과 실제로 동작성이 매우 비슷하며 현존하는 GNN 알고리즘 중에 가장 강한 discriminative power를 가지고 있다고 합니다. WL 알고리즘이 무려 1968년에 제안된 알고리즘이라는 건 또 하나의 깊은 깨달음(!)을 주는 것 같아요.

Other GNN Models

위에서 소개한 GCN, GIN 모델에서 봤듯이 aggregation, combination에 따라서 network의 특성이 확연히 달라지면서 특정 task에 특화되는 양상을 보입니다. 아래 테이블은 다양한 GNN 모델들의 aggregator, updater를 명기해 놓은 자료입니다. Hoxy.. 나도 식 하나 만들면 논문 뚝딱...? 🙄🙄ㅎㅎ

 

---

References

• SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS (Kipf and Welling, ICLR 2017)
  https://arxiv.org/pdf/1609.02907.pdf%EF%BC%89
• [DMQA Open Seminar] Graph Attention Networks
  https://www.youtube.com/watch?v=NSjpECvEf0Y
• https://velog.io/@tobigs-gnn1213/8.-Graph-Neural-Networks

8. Graph Neural Networks

• https://www.sciencedirect.com/science/article/pii/S2666651021000012

Graph neural networks: A review of methods and applications

 

모두의 연구소에서 진행하는 "함께 콘텐츠를 제작하는 콘텐츠 크리에이터 모임"
COCRE(코크리) 2기 회원으로 제작한 글입니다. 코크리란? 🐘