[그래프 기계학습] Before Graph Neural Networks

Graph Representation Learning

Graph Neural Network (GNN)에 대해 본격적으로 알기 이전에, GNN 이전에 그래프 데이터에 사용되었던 접근 방식들에 대해서 먼저 알아보고자 한다.

Why Graphs?

그래프는 노드에 해당하는 entity와 엣지에 해당하는 relation과 interation을 설명하고 분석하기 위해 존재하는 일반적인 표현 방법이다. 여기서 흥미로운 부분은 그래프 데이터는 어디든지 존재한다는 것이다. 컴퓨터 비전에서 주로 사용하는 이미지나 자연어 분야에서 주로 사용하는 텍스트 데이터는 특정 분야에 국한되어 사용되지 않는 그래프 데이터와는 다소 다른 부분이 있다. 여러 연구 분야에 종사하는 연구자들은 다른 배경 지식을 가지고 있고, 이로부터 그래프와 GNN을 설명하는 방법도 각자 다르다. 우리가 지금부터 보려고 하는 그래프와 GNN은 여러 분야 중에서도 특히 그래프마이닝 분야에서 설명하는 가장 보편적인 방식으로 자세하게 알아보려고 한다.

Problem

우리가 흔히 알고 있는 representation learning를 그래프에 사용했을 때 형식적인 정의가 존재하지는 않는다. 그래서 graph representation learning은 단지 그래프를 파악하는 어떤 function을 학습하는 것이라고 말하고자 한다.

우리는 Graph $G$와 target $y$가 주어졌을 때 $G$로부터 $y$로의 function $f_\theta$를 어떻게 학습하여 찾아낼 수 있는지 알아보려고 한다. 특히, 우리는 directed graph에 관심을 가지고 알아볼 것이다. Graph $G$는 일반적으로 vertex $V$와 edge $E$의 pair로써 정의된다. 각 vertex는 일반적으로 $u$나 $v$와 같은 notation으로 정의가 되며, 이들을 연결하는 edge는 $(u,v)$와 같이 정의된다. 여기서 undirect graph에서의 edge라고 한다면 $\{u,v\}$와 같은 set으로 표현할 수 있다. 그래서 방향성이 존재하는 directed graph에서 $(u,v)$와 $(v,u)$는 서로 다르게 된다. 그래프에서 edge의 표현은 이외에도 $uv$, $e$, $e_{uv}$ 등과 같이 다양하게 정의될 수 있다.

현실에서 우리는 heterogeneous graph에 대해서 관심이 많다. Heterogeneous graph는 homogeneous graph와는 다르게 각각의 vertex와 edge가 attribute와 관련이 있고, node attribute를 $\mathcal{X}$, edge attribute를 $\mathcal{R}$로 표현할 수 있다. 즉, node와 edge가 하나의 type으로 정의되는 homogeneous graph와다는 다르게 heterogeneous graph는 각각이 여러 type으로 정의될 수 있다.

다시 graph representation learning의 목적을 생각해보면 우리는 결국 어떠한 graph가 주어졌을 때 target을 만족하는 parameterized 된 function $f_\theta$를 찾아야 한다. 그래서 graph representation learning의 흥미로운 부분중 하나가 각 dataset과 target에 따라 여러 task를 수행할 수 있다는 것이다. 가장 먼저 살펴볼 것은 그래프에서 각 vertex가 어떠한 target을 가지는지 예측하고자 한다. 이외에도 edge 수준의 edge-level prediction과 graph 전체를 예측하는 graph-level prediction이 graph representation learning의 대표적인 task들이 된다. 구체적으로 link prediction은 불완전한 그래프가 주어졌을 때 연결되어 있지 않은 edge의 연결성을 예측하는 task이다.

Node Classfication Problem

Graph로부터 node classification을 한다고 했을 때 처음에 이해가 잘 안되는 부분이 있을 수 있다. 이럴때에는 image classification 혹은 segmentation을 생각해보면 간단하게 이해할 수 있다. Image classification은 image가 주어졌을 때 해당 이미지가 어떠한 것인지 맞추면 되고, segmentation의 경우에는 pixel 수준에서의 classification으로 각 pixel이 어떠한 것을 나타내는지 예측하는 문제를 푸는 것이다. 이를 graph의 관점에서 생각하면 3d 모양의 graph에서 각 vertex가 어떠한 것을 나타내는지 예측한다고 생각하면 된다.

Node-wise Functions

구체적으로 학습 메커니즘에 들어가기에 앞서 node-wise function에 대해서 알아보고자 한다. 학습 메커니즘이 없는 상태에서 우리가 원하는 것은 하나의 graph가 주어졌을 때, 각 vertex로부터 어떠한 function $f$를 거쳐서 이를 vector representation으로 표현하고자 하는 것이다. 구체적으로 node가 $f$의 input으로 주어졌을 때, output으로 node에 대응되는 vector 형식의 embedding으로 변환하고 예측하고 싶은 것이다. $N$개의 node가 주어진다면 $N$개의 embedding을 얻어야 하는 것이다.

Setup

우리가 undirected graph $G$가 있고, 이에 대해서 어떠한 attribute도 존재하지 않는다고 생각해보자. 그러면 우리는 이 graph를 vertex set $V:\{1,2,3,4\}$로 표현할 수 있고, 이에 대한 연결성 정보인 adjacency matrix $A$를 위와 같이 표현할 수 있게 된다. Vertex가 총 4개 존재한다면, 이에 대응되는 adjacency matrix는 $4\times4$의 크기를 가지게 된다. 각 위치의 binary number는 해당 index의 두 vertex 사이에 edge가 존재하는지 유무를 나타낸 것이다.