[CS224W] Traditional feature-based methods: Graph-level features

Contents

 

이전 챕터에서 Node-level, Link-level prediction에 대해서 다루어보았다. 이번 챕터에서는 마지막 남음 Graph-level prediction에 대해서 다루어본다.

 

Graph-Level Features

Kernel Methods

Graph-level에서는 Graph kernel이라는 것을 사용하는데, 이는 전체 그래프 예측에 사용되는 kernel을 의미하며, 이를 통해 전체 그래프의 구조에 대한 특징을 추출하는 것을 목표로 한다. 기존의 노드 혹은 링크에서는 각 노드들의 feature vector를 생성하였으나, Graph-level에서는 feature vector 대신에 kernel을 디자인하는 것이 가장 큰 차이점이다. 

 

kernel $K(G, G') \in \mathbb{R}$은 그래프 $G$와 $G'$ 간의 유사도를 측정한다. kernel matrix는 $\boldsymbol{K} = (K(G, G'))_{G, G'}$으로 표현할 수 있으며, kernel matrix는 항상 positive semidefinite이다. 즉, positive eigenvalue만을 가진다. kernel은 두 그래프 간의 표현을 내적한 것으로 계산할 수 있으며, 수식으로 표현하면 다음과 같다 

\[ \text{feature representation} = \phi(\cdot)\]

\[ K(G, G') = \phi(G)^T \phi(G') \]

이와 같은 방식은 머신러닝 모델 중 kernel SVM와 유사하다. 

 

그래프 간의 유사도를 측정하는 kernel은 대표적으로 Graphlet kernel [1], Weisfeiler-Lehman Kernel [2]를 사용하며, 그 외 Random-walk kernel, Shortest-path graph kernel 등 다양한 kernel이 존재하지만 본 강의에서는 대표적인 두 kernel에 대해서만 다룬다. 일단 먼저 두 kernel을 다루기 이전 Graph kernel이 어떤 것인지 알아보자. 

 

Graph Kernel

Graph Kernel의 핵심 아이디어는 바로 그래프를 위한 Bag-of-Words (BoW)에 있다. BoW는 문서 안에 존재하는 단어들의 수를 count하는 모델이다. Graph 내에서는 Sub-Graph를 count하는 것으로 볼 수 있으며, BoW에서 Words는 Graph에서 node로 이해할 수 있다. BoW는 단어의 순서를 별도로 고려하지 않고 단순히 count만 하기 때문에 아래의 그림과 같은 결과를 도출할 수 있다. 

4개의 빨간 노드를 가지고 있지만 서로 다른 그래프를 동일한 그래프로 보고 동일한 feature vector를 추출하는 것이다. 단순히 BoW만 가지고 그래프를 표현하는 것은 어렵다. 일반적인 노드에는 차수(Degree)라는 개념이 존재하는데, BoW에 차수의 개념을 적용하면 어떻게 될까? 

 

 

위 그래프에서 차수가 1인 경우에는 초록색, 2인 경우는 보라색, 3인 경우에는 노랑색으로 표시한다고 가정하자. 그렇다면 첫 번째 그래프는  [1, 2, 1]로 표현할 수 있으며, 두 번째 그래프는 [0, 2, 2]로 표현할 수 있다. 이처럼 차수를 도입하면 두 그래프는 서로 다른 Representation을 가지게 된다. 이와 같은 경우를 Bag-of-Node Degree로 말할 수 있으며, Graphlet kernel, Weisfeiler-Lehman(WL) kernel 도 Bag-of-*로 그래프를 표현한다. 두 kernel은 앞에서 다룬 node degree보다 정교한 *를 사용한다. 

 

Graphlet Kernel

앞에서 다룬 내용을 토대로 Graphlet Kernel이 어떤 역할을 할지 생각해보자. 기본적으로 BoW의 개념을 착안하여 Bag-of-*를 사용한다고 언급했다. Graphlet Kernel은 Graphlet을 count하는 방법으로 생각할 수 있다. Graphlet이 어떤 것인지는 여기를 참고하면 된다. 이때 graphlet에 존재하는 노드들은 굳이 연결되어 있지 않아도 된다. Graphlet은 고립된(isolated) 노드도 허용하기 때문이다. 

 

그래프  $\mathcal{g}_k = (g_1, g_2, ..., g_{n_k})$가 주어졌다고 가정하자. 이때 $\mathcal{g}_k$는 k개의 노드를 가진 graphlet의 list를 의미한다. k=3인 경우와 k=4인 경우 아래와 같은 graphlet을 가질 수 있다. 

 

그래프 $G$가 주어지고, graphlet list $\mathcal{g}_k = (g_1, g_2, ..., g_{n_k})$가 주어졌을 때 graphlet count vector $\boldsymbol{f}_G \in \mathbb{R}^{n_k}$로 정의할 수 있으며, $(\boldsymbol{f}_G)_i = \#(g_i \subset G) \ \text{for } i=1, 2, ..., n_k$로 표현할 수 있다. k=3인 경우는 다음과 같은 형태로 표현이 가능하다. 

 

이를 통해 도출된 $f_G$와 $f_{G'}$을 내적하는 것이 바로 graphlet kernel의 계산 방법이다. $\boldsymbol{f}_G^T \boldsymbol{f}_{G'} $, 그러나 두 그래프 간의 길이가 서로 다른 경우에는 값을 크게 외곡할 수 있다. 이를 해결하기 위해 각각의 featue vector를 normalize해서 사용하며, 수식은 다음과 같다. 

\[ \boldsymbol{h}_G = \frac{\boldsymbol{f}_G}{\sum \boldsymbol{f}_G}, \ \ \ K(G, G') = \boldsymbol{h}_G^T \boldsymbol{h}_{G'} \]

 

Limitation

Graphlet Kernel에서는 계속해서 Graphlet을 계산해야 된다는 문제점이 존재한다. k개의 노드를 가진 graph의 경우 $n^k$만큼의 연산량이 요구되기 때문이다. 또한, subgraph isomorphism test를 수행할 때 NP-hard가 발생할 수 있다. NP-hard는 NP에 속하는 모든 판정, 즉 동형인지 확인하는 과정을 다항시간 내에 풀 수 없다는 것을 의미한다. 마지막으로, 노드의 차수가 d인 경우 $O(nd^{k-1})$의 시간 복잡도를 가진다. 

 

 

Weisfeiler-Lehman Kernel

Graphlet kernel 보다 효율적으로 계산하기 위해 나온 kernel이 바로 Weisfeiler-Lehman Kernel 즉, WL kernel이다. WL kernel은 보다 효율적으로 $\phi(G)$를 설계하는 것을 목표로 한다. 이는, 이웃 구조를 활용하여 node vocablulary를 효율적으로 활용할 수 있도록 하는 것이며, 이를 Color Refinement Algorithm이라 부른다. 

 

Color Refinement

Color Refinement Algorithm을 직역하면 색을 정제하는 알고리즘이다. 이 알고리즘이 어떠한 방식으로 진행되는지 알아보자. 먼저, color $c^{(0)}(v)$ 각 노드 v에 대한 초기 color를 할당한다. 그 후, 아래의 알고리즘을 K step 만큼 반복하여 $c^{(k+1)}(v)$를 도출한다. 그 후 각 step에서 도출된 결과를 합계하여 $c^{(K)}(v)$를 구성할 수 있으며, 이를 K-hop neighborhood라 부른다.

\[ c^{(k+1)}(v) = \text{HASH}({c^{(k)}(v), {c^{(k)}(u)}_{u \in N(v)}})\]

이때 $\text{HASH}$는 다른 입력을 다른 색상으로 mapping하는 역할을 수행한다. 노드의 차수만 사용하는 경우는 one-hop neighborhood information이기 때문에 Bag-of-node degrees의 일반화 버전으로 부른다. 

위 그림을 예시로 들면, 먼저 initial color를 각 노드에 대해서 할당하고, 각 노드 이웃의 color를 합계한다. 그 후 hash를 통해 노드가 가지고 있는 color를 mapping하는 작업을 수행한다. 위 결과를 바탕으로 다시 한 번 알고리즘을 수행하면 다음과 같은 결과가 도출된다. 

 

첫 번째 그래프를 $G$로, 두 번째 그래프를 $G'$으로 표기하고, 각 그래프의 color의 번호에 따라 정렬하게 되면 다음과 같은 결과가 도출되며 각 그래프의 $\phi$를 내적함으로써 kernel을 정의할 수 있다.

\[ \phi(G) = [6, 2, 1, 2, 1, 0, 2, 1, 0, 0, 0, 2, 1] \]

\[ \phi(G') = [6, 2, 1, 2, 1, 1, 1, 0, 1, 1, 1, 0, 1] \]

\[ K(G, G') = \phi(G)^T \phi(G') = 49 \]

 

Graphlet kernel에 비해서 WL kernel의 매우 효율적으로 연산을 하는 것을 확인할 수 있다. K-step의 color refinement algorithm은 node의 color를 보다 풍부하게 만들 수 있다. 즉, 정보를 많이 담을 수 있다는 것이다. 또한, 시간 복잡도는 엣지의 수에 linear하기 때문에 graphlet kernel보다 훨씬 빠른 속도를 보인다. 마지막으로, 이를 Bag-of-*로 표현하면 Bag-of-colors가 된다.