Chapter10 에서는 일반적인 data의 array (e.g. 이미지) 를 다루는 CNN을 공부하였다. Chapter12 에서는 가변 길이 (variable length) 를 갖는 sequences (e.g. 텍스트) 를 다루는 transformers 에 대하여 공부하였다. 본 챕터에서는 graph neural networks 를 소개한다. 이름에서도 알 수 있다싶이, 이는 graph (set of edges and nodes) 를 다루는 neural architecture 이다.

graph 를 processing 하기 위해서는 크게 3가지 주요 챌린징 포인트들이 있다.

1. 먼저, 이들의 topology 가 variable 하고 충분히 expressive 하며 이러한 variation 을 다룰 수 있는 네트워크를 디자인하기 쉽지 않다.
2. 둘째로, graphs 는 굉장히 클 수 있다. (e.g. 인스타그램에서 전세계인들의 follow 관계 → 70억X70억 matrix). 인스타그램과 같은 social netowk 의 경우는 수십억 이상의 nodes 를 가질 수 있다.
3. 셋째로, 오직 하나의 monolithic graph 만이 존재할 수 있다. (e.g. 인스타그램 전체 그래프는 하나.) 따라서 기존의 방대한 데이터셋을 가지고 학습하는 방법이 적절하지 않을 수 있다.

위와 같은 문제를 해결하기 위해 먼저 graph 의 real-world example 을 먼저 살펴보고 어떻게 graph 를 encode 하는지, 또 어떻게 supervised learning 을 graph 모델에 대하여 정의할지 공부한다. 그리고 자연스럽게 GNN의 한 갈래인, graph convolutional networks 에 대하여 공부한다.

13.1 What is graph?

Graph는 굉장히 흔한 구조이고 nodes 와 vertices 의 set 으로 구성된다. 각 nodes의 pair 들은 edges 혹은 links 로 연결된다. Graph 는 보통 각 nodes 들이 빼곡하게 연결되기 보단 듬성듬성 연결되어 sparse 하다.

Real world 의 몇 가지 objects 들은 자연스럽게 graphs 의 형태를 갖는다. 예를 들어 도로를 생각해보자. 도로에서 nodes 어떤 “장소”가 될 것이고, “길”은 각 “장소”들을 잇는 edges 가 될 것이다. (See Fig. 13.1a)). 화학 분자(?) (chemical moldules) 들도 nodes 들은 원자들을 나타내고 edges 들은 화학적 결합을 나타내는 작은 graph 로 볼 수 있다. (See Fig. 13.1b)). 전자회로는 각 componenets 들은 nodes 로, 그리고 각 components 들을 연결하는 선들을 edges 로 볼 수 있다. (See Fig. 13.1c))

위와 같은 3개의 예시 뿐만 아니라, 아래와 같은 다양한 데이터들을 graph 의 형태로 나타낼 수 있다.

• Social networks (인스타그램)

• Scientific literatures (LLM의 모든 논문은 “Attention is all you need” 논문을 cite함.)

• Wikipedia (wikipedia도 각각의 링크로 연결)

• Computer programs (연산 순서)

  

  https://gfxcourses.stanford.edu/cs149/fall23/lecture/whyparallelism/slide_45

• Geometric point clouds

  

  각 points 들은 node, 각 point들의 주변 point 들을 연결한 edges 로 표현 가능

• Protein interactions

• etc…