[Graph] Representing Networks -Degree

Contents

 

 

Graph Neural Network (GNN)을 다루기 위해서는 일단 그래프가 어떤건지부터 이해하고 넘어가야 한다. 아래의 엄청 간단한 그래프 구조 예시를 통해 쉽게 설명이 가능하다. 

 

우리는 이러한 그래프를 아래와 같은 간단한 수식으로 표현할 수 있다. 

 

\[ \mathcal{g} = \{\mathcal{V}, \mathcal{E} \}, \mathcal{V} = \{v_1, ..., v_N\}, \ \ N = |\mathcal{V}|, \mathcal{E} = \{e_1, ... , e_M\},\ \ M=|\mathcal{E}| \]

$\mathcal{V}$는 노드(node)의 집합을 의미하고, $\mathcal{E}$는 엣지(edge)의 집합을 의미한다. 소셜 네트워크나 화학 등 다양한 분야에서 사용되며, $e_1$는 $v_1$과 $v_2$를 연결하는 엣지를 의미하며 $(v^1_{e_1}, v^2_{e_1})$로 표기할 수 있다. (노드는 정점(Vertex)이라고 부르기도 하기 때문에 node의 수식을 $V$로 표기하였다.)

 

그래프는 노드와 엣지로 구성되어 있으며, 각각의 크기가 존재한다. 그렇다면 노드가 5개 존재하고, 엣지가 10개 존재하는 경우와 노드가 5개 존재하고, 엣지가 5인 경우 두 그래프의 크기는 같을까? 다를까? 그래프의 크기를 나타낼 때에는 노드의 수로 표현한다. 앞선 예시의 경우, 두 그래프의 크기는 동일하다. 즉, 노드의 크기가 같다면 동일한 크기의 그래프라 한다. 

 

그래프는 유향그래프와 무향그래프로 나눌 수 있다. 유향은 방향성이 존재하는 것을 의미하고, 무향은 방향성이 존재하지 않는 것을 의미한다. 수식으로 표현하면, 유향인 경우 $(v^1_{e_1}, v^2_{e_1}) = (v^2_{e_1}, v^1_{e_1})$이지만, 무향인 경우에는 $(v^1_{e_1}, v^2_{e_1}) \neq (v^1_{e_1}, v^2_{e_1})$ 이다.

 

지금까지 그래프를 그림으로 어떻게 구성되었는지 확인하였다. GNN 혹은 GCN (Graph Convolutional Network)로 만들어 학습하기 위해서는 수치로 표현되어야 하는 것이 당연하다. 그렇다면, 이전까지 예시로 사용한 그래프를 한 번 행렬로 표현해보자. 

 

 

각각의 노드를 연결하는 엣지가 존재하는 경우 1로 표기할 수 있다. 또한, 노드 자기 자신과 연결된 엣지는 존재하지 않기 때문에 행렬의 대각선의 성분은 모두 0이 된다. 우리는 이러한 행렬을 인접 행렬(adjacency matrix)라고 부른다. 이번 글에서는 행렬을 수식적으로 깊게 다루진 않는다. 만약 상세한 내용 및 수식을 다루고 싶다면 여기를 참고하길 바란다. 

 

첫번째, $v^1_{e_i}$와 $v^1_{e_i}$를 연결하는 사건(incident)을 간선 혹은 엣지 $e_i$라고 부른다. 두번째, 노드 $v_i$와 $v_j$ 사이에 엣지가 존재하는 경우에만 노드 $v_i$와 $v_j$는 인접(adjacent)하다. 마지막으로, 그래프는 그래프의 노드 간의 연결을 설명하는 인접 행렬로 표현할 수 있다. 

 

Degree

Degree는 노드 $v$와 인접한 노드의 수를 의미한다. 즉, 노드 $v$에 3개의 엣지가 연결되어 있다면 $v$의 차수는 3이 된다. Neighbors은 인접한 노드의 집합을 의미한다. 즉, 노드 $v_1$에 노드 $v_2, v_3$이 연결되어 있는 경우 노드의 이웃은 $\{v_2, v_3\}$이 된다. Total Degree는 모든 노드의 차수를 더한 것이다. 즉, 노드들의 차수가 각각 3, 4 그리고 5인 경우 Total Degree는 12가 된다. 이를 수식으로 표현하면 아래와 같다.

\[ \text{Degree} : k_i = \sum_j A_{ij} \]

\[ m = \frac{1}{2} \sum^n_{i=1} k_i = \frac{1}{2} \sum^n_{i=1} \sum^n_{j=i} A_{ij} \]

\[ \text{Mean Degree} : \left\langle k \right\rangle = \frac{1}{n} \sum_i k_i = \frac{2m}{n} \]

이때 m은 엣지의 개수를 의미한다. .모든 차수의 합을 구할 경우 엣지가 중복으로 계산되기 때문에 $\frac{1}{2}$로 나누어주는 것이다. 이렇게 구한 엣지의 수를 통해 $\text{mean Degree}$를 표현할 수도 있다. 위 경우는 무향 그래프 기준으로 설명하였다. 유향 그래프에서는 들어오는 차수(Indegree)와 나가는 차수(Outdegree)를 따로 계산하여야 한다.

\[ \text{Degree} = \text{Indegree + Outdegree} \]

\[ k_i = k^{in}_i + k^{out}_i \]

\[ k_3 = \sum^n_{i=1} A_{i3} + \sum^n_{j=1} A_{3j} \]

들어오는 차수의 경우 열을 기준으로 합산하여 계산할 수 있고, 나가는 차수의 경우 행을 기준으로 계산할 수 있다. 이를 합치면 바로 해당 노드의 차수가 된다.