[Graph Neural Network] Graph Representation

GNN은 Graph Neural Network로, 이름처럼 graph를 이용한 신경망이다. 이를 이해하기 전에 먼저 graph에 대해 이해해보자.

network를 이루는 구성 요소는 objects, interaction, system인데 우리가 다룰 graph에서는 각각 node, link, graph(network)로, 순서대로 $N$, $E$, $G(N,E)$라고 표현한다. graph의 장점은 specific cases를 general하게 표현할 수 있다는 것이다.

graph에는 directed와 undirected가 있다. 이름에서 바로 알 수 있듯이, directed는 방향이 존재하는 것, undirected는 방향이 존재하지 않는 것이다. 

어떤 node로부터 인접한 edges의 수를 node degree ($k_i$)라고 한다. undirected graph의 경우 average degree (평균적으로 인접하는 edges의 수)는 $\bar{k}=<k>={{1}\over{N}}\Sigma^N_{i=1} k_i = {{2E}\over{N}}$ 이다. 반면, directed graph의 경우 in-degree와 out-degree라는 개념이 생겨서 화살표가 들어오는 방향과 나가는 방향의 edge를 나누어서 정의한다. 결과적으로 in-degree와 out-degree의 수는 항상 같으며 average degree는 $\bar{k}={{E}\over{N}}$이다. 이때, 어떤 node에 대해 들어오는 방향의 edge가 0개이고 나가는 방향의 edge만 있다면 이를 source라 부르고, 반대로 나가는 방향의 edge가 0개이고 들어오는 방향의 edge만 있다면 이를 sink라 부른다.

Bipartite Graph

Bipartite graph는 두 집합이 존재할 때 서로에 대해서만 연결되어 있고 집합 내의 node끼리는 연결되지 않은 graph, 즉 두 집합이 independent set인 graph를 말한다.

graph를 표현하는 방법 중 하나는 adjacency matrix이다. 이 adjacency matrix $A$에 대해 node $i$로부터 node $j$로 연결되어 있다면 $A_{ij}=1$, 아니면 0으로 나타내는 방식이다. 이때, undirected graph에 대한 adjacency matrix는 symmetric한 반면에 directed graph에 대한 adjacency matrix는 그렇지 않다. 

이때, 여러 nodes가 연결된 component 두개가 서로 전혀 연결되지 않는다면 이를 adjacency matrix로 나타냈을 때 block-diagonal의 형태를 띄게 된다. 하지만 대부분의 현실세계의 netwowrk는 분산적이기 때문에 adjacency matrix는 대부분 0으로 채워진다. 

다른 graph를 표현하는 방법 중 하나는 edge list로 좌표로 나타내는 것이다. 또한 이런 분산적인 network의 세계에 적합한 adjacency list도 있다. 이는 특정 node로부터 나가는 방향의 link가 존재하는 모든 node를 작성하는 것이다.

graph를 분류하는 기준에는 direction의 유무 외에도 weight, ranking, type 등 여러가지가 있다. 그 중 weighted와 unweighted만 살펴보면 weighted graph는 unweighted graph와 달리 node 사이의 link의 weight 에 따라 1이 아니라 0.5 혹은 2 등 적절한 수를 활용하는 것을 볼 수 있다.