[Graph Neural Network] Traditional Feature-based Method

 

 

머신러닝 모델에서 graph를 사용하기 위해서는 feature를 얻고 이를 기반으로 예측을 해야한다. graph는 node -level , link -level , graph-level 에서의 feature을 디자인할 수 있다. 쉽게 이해하기 위해 undirected graphs를 기준으로 node, link, graph를 알아보자.

Node-level

node-level의 task는 보통 node classification이다. 즉, node의 구조와 위치에 대한 feature을 얻는 것이 목표인 것이다. 이를 위해 우리가 알아야 할 개념은 node degree, node contrality, clustering coefficient, graphlet이다.

node degree ($k_v$)는 어떤 node $v$로부터 연결된 edge의 수이다. 이는 이웃한 노드들의 중요성은 고려하지 않고 노드가 몇 개의 이웃 노드와 연결되어 있는지를 단순히 세는 방법이다.

node centrality ($c_v$)는 그래프에서 노드의 중요성을 나타낸다. 이를 구하는 방법에는 여러가지가 있는데, 그 중에서 eigenvector centrality, betweenness cetrality, closeness centrality를 알아보자.

eigenvector centrality는 이름처럼 eigenvector를 이용하는 방식이다. 이는 특정 노드가 얼마나 중요한 노드들과 연결되어있는지를 나타낸다. $$c_v={{1}\over{\lambda}}\Sigma_{u\in N(v)} c_u$$ 벡터와 행렬로 나타내면 아래와 같이 나타낼 수 있다.$$\lambda c = A c$$ 여기서 $c$는 centrality vector, $A$는 adjacency matrix, $\lambda$는 eigenvalue이다. 가장 큰 eigenvalue가 네트워크에서 가장 영향력 있는 노드들 사이의 연결을 반영하며, 이에 대응하는 eigenvector $c_{max}$가 보통 centrality 계산에 사용된다. 

betweenness centrality는 주변의 두 노드를 연결하는 최단 경로에 해당 노드를 얼마나 많이 거쳐가는지로 중요성을 정의한다. 즉, 어떤 node $v$에 대해 betweenness centrality를 구하고자 한다면 node $v$를 제외한 나머지 노드들을 최단 경로로 연결할 때 node $v$를 거쳐가는 경우의 수의 합을 구하면 된다. 수식적으로 나타내면 아래와 같다. $$c_v = \Sigma_{s\neq v\neq t}{{n_{st,v}}\over{n_{st}}}$$ 여기서 $n_{st}$는 s와 t 사이의 최단 경로 수를, $n_{st,v}$는 s와 t 사이에 v를 거쳐가는 최단 경로의 수를 의미한다.

closeness centrality는 주변의 다른 노드들과의 최단 거리의 합이 얼마나 짧은지로 중요성을 정의한다. 위의 두 centrality에 비해 비교적 직관적이다. $$c_v =  {{1}\over{\Sigma_{u\neq v}l_{uv}}}$$ 여기서 $l_{uv}$는 $u$와 $v$ 사이의 최단 경로의 길이를 의미한다.

어떤 node $v$와 이웃하는 노드들이 서로 얼마나 연결되어 있는지를 나타내는 척도는 clustering coefficient이다. 이는 주변 노드들의 모든 pair의 수 중에서 주변 노드끼리 연결되어있는 edge의 수의 비율이다. 이 값이 높을수록 해당 노드가 속한 subgraph의 노드들이 서로 밀접하게 연결되어 있음을 나타낸다. 수식적으로는 아래와 같이 나타낼 수 있다.

clustering coefficient는 ego-network에 만들어지는 삼각형의 수를 세면 쉽게 판단할 수 있다. 이를 일반화하여 특정한 조건을 만족하는 subgraph의 수를 세면 graphlets이 된다. graphlets의 정의는 "rooted connected non-isomorphic subgraphs"이다. 즉, 어떤 노드를 기준으로 서로 구조적으로 동일하지 않은, 연결된 subgraph를 말한다. 아래는 node의 개수에 따른 graphlets이다. 2개~5개의 node로 이루어져 있으며 이는 네트워크의 구조적 패턴을 이해할 수 있도록 한다.

5-node graphlets을 보다보면 별 모양도 5개의 노드로 만들 수 있는데 왜 없지? 하는 생각을 할 수 있다. 하지만 이는 적절히 mapping하거나 구조를 재배열하면 오각형 모양($G_{15}$)과 동형(isomorphic), 즉 구조적으로 동일하다는 것을 알 수 있다. graphlets은 비동형이어야 하므로 별 모양과 오각형 모양은 동시에 graphlets로 표현하지 않는다.

이 개념을 바탕으로 GDV (Graphlet Degree Vector)를 정의할 수 있다. GDV는 주어진 노드를 root로 하는 graphlets의 개수를 나타내는 벡터이다. 즉, 특정 노드가 다양한 graphlet에 얼마나 많이 속하는지를 나타낸다. 이 벡터의 각 요소는 해당 노드가 특정 유형의 graphlet에서 얼마나 중요한지를 나타낸다. 아래의 그림을 예로 들어보자.

이 그래프에 대한 graphlets의 리스트 아래와 같다.

node $v$를 기준으로 하는 graphlet의 요소들은 아래와 같다.

따라서 각 a,b,c,d의 개수를 벡터로 나타내면 [2,1,0,2] 이고 이것이 node $v$의 GDV이다. 이는 노의 local network topology 즉, 직접적으로 특정 노드와 연결된 이웃 노드 간의 연결 구조를 더 자세하게 나타낸다.

 

Link-level

link-level의 task는 보통 존재하는 link를 기반으로 새로운 link 혹은 누락된 link를 예측하는 일이다. 이는 하나의 노드가 아닌, 노드 덩어리(pair)의 feature을 디자인하는 것이 중요하다. link-level feature 중 distance-based feature, local neighborhood overlap, global neighborhood overlap를 순서대로 알아보자.

distance-based features는  두 노드의 최단 경로 거리를 의미한다. 하지만 이는 이웃하는 노드가 얼마나 중복되는지의 정도를 반영하지 못한다. 이를 반영하기 위한 feature가 local neighborhood overlap이다. 이는 node $v_1$과 $v_2$ 둘다 이웃하는 노드의 개수를 의미한다. 이를 나타내기 위해서는 common neighbors, Jaccard's coefficient, Admic-Adar index 개념이 필요하다. common neighbors는 $|N(v_1)\cap N(v_2)|$으로, 공통적으로 이웃하는 노드의 수를 나타낸다. Jaccard's coefficient는 $|{N(v_1)\cap N(v_2)}\over{N(v_1)\cup N(v_2)}|$로, 각각 이웃하는 노드의 수와 공통적으로 이웃하는 노드의 수의 비율을 나타낸다. Adamic-Adar index는 $\Sigma_{u\in N(v_1)\cap N(v_2)}{{1}\over{log(k_u)}}$로, 공통된 이웃의 중요도는 그들의 node degree에 따라 감소함을 나타낸다. 즉 degree가 낮은 노드들과 공통으로 많이 이웃하고 있는 것이, 다른 노드들과 연결이 많이 되어있는 노드들과 공통으로 많이 이웃하는 것보다 좋다는 의미이다. 아래의 예시와 함께 보자.

공통적으로 이웃하는 노드의 수는 $|N(A)\cap N(B)|=|N(C)|=1$이다. Jaccard's coefficient는 $|{{N(A)\cap N(B)}\over{N(A)\cup N(B)}}|=|{{C}\over{C,D}}|=0.5$, Adamic-Adar index는 ${{1}\over{log(k_c)}}={{1}\over{log(4)}}$이다.

local neighborhood overlap은 두 노드와 공통된 이웃노드가 없으면 미래에 연결될 수 있음에도 불구하고 지표가 모두 0이 된다는 한계가 있다. global neighborhood overlap은 전체 그래프를 고려하여 이러한 한계를 해결할 수 있다. 먼저 Katz index를 알아야 한다. 이는 주어진 노드들에 대해 서로 다른 길이의 경로의 수를 나타낸다. 두 노드 사이의 경로의 수를 어떻게 계산할 수 있을까? 그래프의 adjacency matrix의 power를 이용한다. $P^{(K)}_{uv}$를 node $u$와 $v$ 사이의 길이가 $K$인 경로의 개수라고 하자. adjacency matrix의 요소는 각 노드 사이의 연결이 되어있으면 1 아니면 0이기 때문에 $K$가 1이라면 adjacency matrix와 동일하다. 하지만 $K$가 2라면 node $u$의 이웃과 node $v$ 사이의 길이가 1인 경로의 수를 찾으면 된다. $$P^{(2)}_{uv}=\Sigma_i A_{ui}*P^{(1)}_{iv}=\Sigma_i A_{ui} * A_{iv} = A_{uv}^2$$ adjacency matrix는 인접한, 즉 길이가 1인 경로로 연결되어 있는 노드들의 관계를 나타내기 때문에 가능한 것이다. 이러한 관계에 의해서 $P^{(K)}_{uv}= A_{uv}^K$로 정의할 수 있다. Katz index는 결과적으로 모든 길이의 경로들을 더한 값이므로 $S_{v_1v_2}=\Sigma_{l}\beta^l A_{v_1v_2}^l$으로 표현할 수 있다. 이때 $\beta$는 discount factor로 0과 1 사이의 값이다. 이를 행렬 형태로 나타낸 Katz index matrix를 closed−form으로 계산하면 Neumann 급수를 이용하여 아래와 같이 나타난다. $$S = \Sigma_{i=1}^\infty \beta^iA^i = \Sigma_{i=0}^\infty \beta^iA^i - \beta^0 A^0 = (I-\beta A)^{-1} - I $$

 

Graph-level

graph-level에서는 전체 그래프의 구조를 반영하는 feature를 디자인하는 것이 목표다. 이전의 ML에서 자주 사용되던 graph-level 예측법인 Kernel method에 대해 알아보자. 이는 feature vector 대신에 kernel을 디자인하는 방식이다. kernel($K(G, G')$)은 데이터 사이의 유사성을 나타내는 정도이다. kernel matrix($K$)는 kernel을 원소로 가진 벡터다. 항상 positive semidefinite 즉, 행렬의 모든 eigenvalue가 0보다 크거나 같아야 한다. kernel 함수는 아래와 같이 표현될 수 있다. $$K(G, G') = \phi(G)^T\cdot \phi(G')$$ 여기서 $\phi(\cdot)$는 데이터 $G$와 $G'$을 어떤 고차원 특징 공간으로 변환하는 mapping function이다. 두 데이터에 대한 $\phi(\cdot)$함수의 dot product를 통해 kernel 함수는 두 데이터가 변환된 공간에서 얼마나 유사한지를 나타내게 된다.

이러한 배경을 바탕으로 graph kernels를 살펴보자. graph kernel는 그래프 특징 벡터인 $\phi(G)$를 디자인하는 것을 목표로 한다. 여기서 BoW (Bag-of-Words) 모델이 사용되는데 이는 문서에서 단어의 순서를 고려하지 않고 단어의 출현 빈도만을 특징으로 사용하는 모델이다. 이를 그래프들 간의 노드를 단어처럼 간주하여 각 노드를 하나의 단어로 생각하고 그래프를 BoW 방식으로 표현할 수 있다. 하지만 이는 다른 구조의 그래프도 동일한 값을 가지게 된다. 우리가 이후에 살펴보게 될 Graphlet Kernel과 Weisfeiler-Lehman Kernel 모두 words보단 더 세밀한 *에 대해 Bag-of-* 모델을 사용하게 된다.

graphlet kernel은 그래프에서 서로 다른 graphlets의 개수를 세는 것에서 시작한다. 여기서 graphlet의 정의는 node-level에서 정의했던 것과 사뭇 다르다. graph-level에서의 graphlet은 연결되어 있지 않아도, root가 아니어도 된다. $\zeta_k=(g_1,g_2,\cdots,g_{n_k})$를 노드의 개수가 k개인 graphlets의 list라고 하자. 예를 들어 k가 3이라면 4가지 graphlets을 가지게 된다. node-level에서 node의 개수가 3개인 graphlets은 $g_1$, $g_2$와 같은 형태 2가지였던 것과 다르게, graph-level에서는 4가지이다.

주어진 graph $G$와 graphlet list $\zeta_k$에 대해 graphlet count vector $f_G$를 정의할 수 있다. $$(f_G)_i=\#(g_i\subseteq G) (i=1,2,\cdots,n_k)$$ 

예를 들어, node가 3개인 경우에 대해 graphlet count vector를 구한다면 각 graphlet이 그래프에서 몇 개 존재하는 지를 세면 된다.

graphlet kernel에서 graphlet kernel을 $K(G,G')=f_G^T f_{G'}$으로 계산한다. 하지만 이는 $G$와 $G'$이 다른 사이즈일 때 그 값이 크게 왜곡되는 문제가 있다. 이를 해결하기 위해 각 feature vector를 표준화하여 사용한다. $$h_G = {{f_G}\over{\Sigma f_G}}$$ $$K(G,G')=h_G^T h_{G'}$$

하지만 graphlet kernel 방법은 시간이 많이 걸린다. 모든 그래프의 isomorphism을 확인하는 것의 NP-hard 문제이기 때문이다. 보다 효율적인 방안은 Weisfeiler-Lehman Kernel이다. 이는 효율적인 그래프 특징 매핑 함수 $\phi(\cdot)$를 디자인하는 것을 목표로 한다. 여기은 color refinement라는 개념이 필요하다. 각 노드 $v$에 초기 색상 $c^{(0)}(v)$를 할당하고 노드의 색상을 HASH를 이용하여 반복적으로 서로 다른 입력에 서로 다른 색상을 매핑한다. $$c^{(k+1)}(v)=HASH(c^{(k)}(v),\{c^{(k)}(v)\}_{u\in N(v)})$$ 아래 예제를 통해 확인해보자.

결과적으로 1~13의 color에 대해 총 개수를 세서 그를 벡터화한 것이 그래프 특징 벡터 $\phi(G)$가 된다. 이 예제에서의 그래프 특징 벡터를 나타내면 아래와 같다. $$\phi(left) = [6,2,1,2,1,0,2,1,0,0,0,2,1]$$ $$\phi(right)=[6,2,1,2,1,1,1,0,1,1,1,0,1]$$ $$K(left,right) = \phi(left)^T \dot \phi(right) = 49$$

위의 예제에서 볼 수 있듯이 WL kernel은 각 단계에서 그래프에서 나타난 색상만 추적하면서 커널 값을 계산하여, edge 수에 선형적이므로 연산적으로 효율적이다. 이러한 장점을 바탕으로 WL kernel GNN과 밀접하게 연관이 된다.

[출처] Stanford CS224W