연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.
유튜브 강의 링크는 다음과 같다.
https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn
Stanford CS224W: Machine Learning with Graphs
This course covers important research on the structure and analysis of such large social and information networks and on models and algorithms that abstract ...
www.youtube.com
목차
이전 포스팅 내용을 잠깐 복기해보자면,
그래프를 활용한 machine learning의 task는 아래와 같았다.
- Node-level prediction
- Link-level prediction
- Graph-level prediction
그리고 그래프를 황용한 ML pipeline은 아래와 같았다.
- Node, link, graph의 feature를 design한다.
- 모든 training data에 대한 feature를 얻는다.
- Random forest, SVM, Neural network 등으로 ML model을 학습한다.
- 주어진 새로운 node/link/graph의 feature를 얻고, prediction을 진행한다.
그래프에 대해서 효과적인 feature를 사용하는 것은 모델이 좋은 성능을 갖도록 하기 위한 핵심이다.
전통적인 ML pipeline에서는 사람이 직접 design한 feature를 사용한다.
이번에는 각 task에서 feature design을 어떻게 하는지 알아보자. (간단하게 Undirected graph만 다루도록 한다.)
그래프를 사용한 ML의 목표는 object set에 대해 예측을 하는 것이다.
이때 Design으로는 \(d\)차원의 벡터를 feature로, node, edge, set of nodes, 혹은 graph 전체를 object로 볼 수 있다.
예를 들면, node-level prediction의 과정은 다음과 같다.
Given \( \mathbf{G} = \left( \mathbf{V}, \mathbf{E} \right) \),
Learn a function \( f : \mathbf{V} \rightarrow \mathbb{R}\)
위와 같은 function을 어떻게 학습할지 알아보자.
Node-level Tasks and Features
예를 들어, node의 class를 예측하고 싶다고 하자.
이때 machine learning을 위해서는 feature가 필요하다.
이러한 feature의 목적은 network 내에서 어떤 node의 구조와 위치를 특정하는 것이다.
대표적으로 다음과 같은 feature가 있다.
- Node degree
- Node centrality
- Clustering coefficient
- Graphlets
각 feature에 대해 자세히 알아보자.
Node Degree
Node \(v\)의 degree \(k_v\)는 이전에도 다루었듯, 그 node와 이웃한 node, 즉 그 node의 edge의 개수이다.
하지만, degree는 단순히 edge의 개수만 세고, 각 edge(이웃 node)가 얼마나 중요한지를 알 수 없다.
이 단점을 보완하기 위해 node centrality라는 개념이 등장한다.
Node Centrality
Node \(v\)의 centrality \(c_v\)는 graph에서 node가 얼마나 중요한지를 나타낸다.
그 중요도를 표현하는 방법은 여러가지가 있다.
- Eigenvector centrality
- Betweenness centrality
- Closeness centrality
- ...
Eigenvector Centrality
Eigenvector centrality에서는 node \(v\)의 이웃 노드들이 중요할수록 해당 노드가 중요하다고 정의한다.
Centrality는 이웃 노드의 centrality의 합으로, 수식으로 나타내면 다음과 같다.
\( c_v = \cfrac{1}{\lambda} \sum\limits_{u \in N(v)} c_u \)
\(lambda\)는 normalization constant(adjacency matrix \(\mathbf{A}\)의 eigenvalue 중 가장 큰 값)이고, \(u\)는 \(v\)의 이웃 노드 중 하나이다.
위 식은 재귀적(recursive)인 계산 방법인데, 이를 adjacency matrix \(\mathbf{A}\)로 다음과 같이 나타낼 수 있다.
\( \lambda \mathbf{c} = \mathbf{Ac} \)
Adjacency matrix \(\mathbf{A}\)에서 node \(u\)와 \(v\)가 이어져 있다면 element \(\mathbf{A}_{uv} = 1\)일 것이다.
또한, \(\mathbf{c}\)는 centrality vector이다.
위 식에서, centrality \(\mathbf{c}\)는 \(\mathbf{A}\)의 eigenvector, \(\lambda\)는 eigenvalue임을 알 수 있다.
이때 Perron-Frobenius theorem(이 내용을 자세히 다루지는 않겠다.)에 의해 \(\lambda_{\max}\)는 항상 양수이며, 유일하다.
여기서 \(\lambda_{\max}\)에 따른 \(\mathbf{c}_{\max}\)를 centrality로 사용한다.
Betweenness Centrality
Betweenness centrality에서는 그래프 내의 두 노드간의 path에 해당 노드가 많이 포함될수록 중요한 노드로 정의한다.
식으로 나타내면 다음과 같다.
\( c_v = \sum\limits_{s \neq v \neq t} \cfrac{\text{# of shortest paths between }s \text{ and } t \text{ that contain } v}{\text{# of shortest paths between }s \text{ and } t} \)
위 그래프 예시를 통해 알아보자.
우선, \(c_A = c_E = 0\)이다. 이 노드들은 graph의 끝 부분에 위치하므로 다른 두 노드의 path 중간에 있을 수 없기 때문이다. 또, \(c_B = 0\)인데, 이는 \(A-E\) path에서 B 노드를 거치면 shortest path가 아니기 때문이다. (\(A-D\) 등 다른 path들에서도 마찬가지이다.)
또한 \(c_C = 3\)이다. \(A-C-B\), \(A-C-D\), \(A-C-D-E\) path가 해당한다. (정확한 계산은 간단하니 직접 해보도록 하자.)
그리고 \(c_D = 3\)인데, \(A-C-D-E\), \(B-D-E\), \(C-D-E\) path를 통해 계산할 수 있다.
Closeness Centrality
Closeness centrality에서는 해당 노드가 모든 다른 노드로 향하는 최단 거리 path의 길이의 합이 작을수록 중요한 노드로 정의한다.
\( c_v = \cfrac{1}{\sum\limits_{u \neq v} \text{shortest path length between } u \text{ and } v} \)
아까와 같은 그래프에서 closeness centrality를 구해보자.
노드 A를 예로 들면, \(c_A = 1 / (2 + 1 + 2 + 3) = 1/8 \)이다. B로의 최단 거리와 D로의 최단 거리가 2, C로의 최단 거리는 1, E로의 최단 거리는 3이기 때문이다.
이에 비해 노드 D는 \(c_D = 1/(2 + 1 + 1 + 1) = 1/5\)로, 노드 A보다 큰 값을 가지므로 더 중요한 node로 볼 수 있다.
Clustering Coefficient
Clustering coefficient는 이웃 노드 두 개와 해당 노드의 triplet 개수에 대한 이웃 노드들과의 triangle 개수로 계산하고, network에 존재하는 triangle의 개수에 대한 개념이다.
수식으로 나타내보면 다음과 같다.
\( e_v = \cfrac{\text{# of trianlges among the triplets}}{\binom{k_v}{2}} \)
분모는 노드 \(v\)와 연결된 노드 중에서 2개를 뽑는 경우의 수(즉, 노드 자신까지 포함하여 3개의 노드 조합(triplet)의 수)이고, 분자는 그 triplet에서 edge가 모두 존재하여 trianlge을 이루는 것의 개수이다.
아래 예시를 통해 알아보자.
가운데 예시부터 보자.
분모는 \(\binom{4}{2} = 6\)으로, 총 6개의 triplet(A-B-v, A-C-v, A-D-v, B-C-v, B-D-v, C-D-v)이 존재함을 알 수 있다. 그리고, 분자를 살펴보면, 이중에서 triangle을 생성하는 것은 총 3개(A-B-v, A-C-v, B-D-v)임을 알 수 있다.
따라서 clustering coefficient \(e_v = 3/6 = 0.5\)이다.
마찬가지로 위의 첫 번째 예시에서는 \(e_v = 1\)이고, 세 번째 예시는 \(e_v = 0\)이다.
사전에 정의한 subgraph인 graphlet을 통해 위 개념을 일반화할 수 있다.
Graphlets
Graphlet은 subgraph의 개념으로, 특정 노드의 이웃의 구조를 나타낸다.
Degree는 특정 노드와 닿는 이웃(edge)의 개수를, clustering coefficient는 특정 노드와 닿는 triangle의 개수를 나타냈었다.
이와 비슷한 개념으로, graphlet degree vector (GDV)는 graphlet 기반의 feature로, 특정 노드와 닿는 graphlet의 개수를 나타낸다.
노드가 몇 개인지에 따라 다양한 graphlet이 존재한다. 이러한 graphlet 몇 개로 전체 그래프가 구성되었는지를 gdv로 알 수 있고, 이것이 node의 부분적인 network topology를 나타내어 그래프를 해석할 수 있다.
두 노드에 대해 gdv를 비교하면 단순히 degree나 clustering coefficient를 비교하는 것보다 더 상세하게 구조의 차이를 알 수 있다.
먼저, 두 가지 개념을 알아두어야 한다.
- Induced subgraph
- Graph의 subgraph 중에서 모든 vertices(nodes)가 연결된 형태의 subgraph를 말한다.
- Graph isomorphism(동형 사상, 즉 동일 구조)
- 두 그래프가 Isomorphic하다는 것은, 같은 개수의 node가 같은 방식으로 연결된 graph임을 말한다.
위 두 그래프는 왼쪽 그래프의 node를 \(e_1 \rightarrow c_5, e_2 \rightarrow c_2, e_3 \rightarrow c_4, e_4 \rightarrow c_1, e_5 \rightarrow c_3\)로 mapping하면 완전히 같은 graph임을 알 수 있다. 이 경우 두 그래프가 isomorphic하다고 한다.
Graphlet은 주어진 개수의 node에 대한 여러 subgraph 중에서 non-isomorphic한 subgraph들을 말한다. 다음 예시를 보자.
그래프의 크기(node 개수)가 많아질수록 당연히 가질 수 있는 graphlet의 개수도 많아질 것이다.
\(G_2\) 예시를 살펴보면, 노드 세 개 중 어디를 기준으로 하던 똑같은 subgraph(isomorphic)를 나타낸다. 따라서 \(G_2\)와 같은 형상의 graph에서 가능한 graphlet은 하나 뿐이다.
위 예시에서 알 수 있듯이, 노드 5개를 갖는 graph의 graphlet 개수는 73개이다. (즉, gdv의 차원이 73일 것이다.)
이제 특정 노드의 graphlet을 예시를 통해 알아보자.
위 예시와 같은 graph의 node \(v\)를 포함할 수 있는 graphlet의 list는 다음과 같다. (즉, 2-node, 3-node graphlet이 가능하다.)
가능한 graphlet 중에서 node \(v\)에 해당하는 graphlet instance는 아래와 같다.
즉, node \(v\)에 대해 list에서 a 형태의 graphlet을 갖는 instance 2개, b 형태의 graphlet을 갖는 instance 1개, c 형태의 graphlet을 갖는 instance 0개, d 형태의 graphlet을 갖는 instance 2개가 있다.
이를 graphlet degree vector로 나타내면 다음과 같다.
\( \text{GDV of node }v: \quad \left[ 2, 1, 0, 2 \right] \)
GDV는 첫 번째 index부터 차례대로 a, b, c, d형태의 graphlet의 instance 개수를 나타낸다.
만약 이웃 노드가 총 5개라면, 해당 노드는 73차원의 graphlet degree vector를 갖게 된다. 이 gdv로 노드 주변의 topology를 나타낼 수 있는 것이다. 그리고 거리는 4 이하의 연결 관계(distance of 4 hops, up to 4 edges)를 나타낼 것이다.
정리하자면, node-level feature는 다음과 같이 분류할 수 있다.
- Importance-based features : 그래프에서 영향력 있는 노드를 예측하는 task에 적절
- Node degree
- Node centrality
- Structure-based features : 노드 근처의 local network topology 특성을 나타냄 → 그래프에서 어떤 노드의 특정 역할을 예측하는 task에 적절
- Node degree
- Clustering coefficient
- Graphlet degree vector
가장 포괄적인 개념은 마지막에 소개한 graphlet degree vector이다.
Link Prediction Task and Features
Link-level prediction task란, 기존의 llink들을 기반으로 새로운 link를 예측하는 task를 말한다.
이때, 링크가 없는 모든 노드 쌍들을 정렬하여 상위 \(K\)개의 노드 쌍에 대해 예측한다.
여기서 핵심은 바로 노드 쌍에 대한 feature를 잘 설계해야 한다는 것이다.
Link prediction task의 두 가지 formulation은 다음과 같다.
- Links missing at random
- 링크의 set을 무작위로 제거하고, 그것들을 예측한다.
- Static network에 유용하게 사용된다.
- Links over time
- 주어진 시간 \(t_0\)부터 \(t_0^\prime\)까지의 graph \(G[t_0, t_0^\prime]\)가 주어졌을 때, 정렬된 list \(L\)을 출력한다. 이때 list에는 \(G[t_0, t_0^\prime]\)에는 없는 \(G[t_1, t_1^\prime]\)의 새로운 link를 예측한다.
- Evaluation 과정에서는 test period \([t_1, t_1^\prime]\)동안 새로 생긴 edge의 개수 \(n = \vert E_{new} \vert\)에 대해 list \(L\)의 top \(n\)개 elements를 취하여 correct edge 개수를 센다.
links over time formulation에서 얼마나 가까운지를 통해 link를 예측할 수도 있다.
- 각 노드 쌍 \((x,y)\)에 대해 score \(c(x,y)\)를 계산한다. 이때 score는 node \(x\)와 \(y\)의 공통 이웃 노드 개수 등 여러가지가 될 수 있다.
- \((x,y)\) 쌍을 score \(c(x,y)\)에 대해 내림차순으로 정렬한다.
- Top \(n\)개 쌍을 새로운 link로 예측한다.
- 이 link들이 \(G[t_1, t_1^\prime]\)에서 실제로 나타나는지 확인한다.
Link의 feature는 다음과 같은 종류가 있다.
- Distance-based feature
- Local neighborhood overlap
- Global neighborhood overlap
하나씩 자세히 살펴보자.
Distance-based Features
Distance-based features는 글자 그대로 두 노드 사이의 최단거리를 feature로 사용한다.
다음 예시를 살펴보자.
위 그래프에서, 두 노드 쌍 간의 shortest path 값을 몇 가지 살펴보자.
\( S_{\text{BH}} = S_{\text{BE}} = S_{\text{AB}} = 2 \)
\( S_{\text{BG}} = S_{\text{BF}} = 3 \)
그런데, 이 feature는 겹치는 이웃 노드의 차수를 고려하지 못한다.
예를 들어, 노드 쌍 \((B,H)\)는 \(C\)와 \(D\)가 공통 이웃 노드(2개)인데, \((B, E)\)는 공통 이웃 노드가 \(D\)하나이다.
이를 고려해주기 위해 'neighborhood overlap'이라는 개념을 사용한다.
Local Neighborhood Overlap
Local neighborhood overlap은 두 노드 \(v_1\)과 \(v_2\) 사이의 공통 이웃 노드의 개수를 센다.
중복되는 이웃 노드를 반영함으로써 얼마나 많은 노드를 공유하는지 계산해주는 것이다.
공통 이웃 노드의 개수는 식으로 \(\vert N(v_1) \cap N(v_2) \vert\)와 같이 나타낼 수 있다.
여기서 Jaccard's coefficient는 다음과 같다.
\( \cfrac{\vert N(v_1) \cap N(v_2) \vert}{\vert N(v_1) \cup N(v_2) \vert} \)
이는 IoU (Intersection over Union) 개념으로, 두 집합(여기서는 두 노드의 이웃 노드) 간의 유사도를 나타낸다. 0에서 1 사이의 값을 가지며, 1에 가까울 수록 두 집합이 유사하다.
또한 Adamic-Adar index라는 개념도 알아두자.
\( \sum\limits_{u \in N(v_1) \cap N(v_2)} \cfrac{1}{\log{(k_u)}} \)
여기서 \(k_u\)는 겹치는 노드의 degree이다.
이 개념은 어떤 노드 쌍에 대해 겹치는 노드의 degree가 클수록 link를 예측할 때 중요도가 떨어짐을 나타낸다.
노드 쌍 \((A,B)\)와 \((B,F)\)를 비교해보자.
먼저, \((A,B)\)의 Jaccard's coefficient와 Adamic-Adar index는 다음과 같이 계산된다.
Jaccard's coefficient : \( \cfrac{\{C\}}{\{C, D\}} = \cfrac{1}{2} \)
Adamic-Adar index : \( \cfrac{1}{\log{N(C)}} = \cfrac{1}{\log 4} \)
그리고 \((B,F)\)의 값들은 다음과 같다.
Jaccard's coefficient : \( \cfrac{\{ C, D \}}{\{ C, D, E \}} = \cfrac{2}{3} \)
Adamic-Adar index : \( \cfrac{1}{\log{N(C)}} + \cfrac{1}{\log{N(D)}} = \cfrac{1}{\log 4} + \cfrac{1}{\log 4} \)
즉, 노드 쌍 \((B,F)\)가 \((A,B)\)보다 두 노드 간에 유사성도 높고, 중요도가 높음을 알 수 있다.
하지만 위 예시에서 local neighborhood overlap을 적용할 때, 노드 \(A\)와 노드 \(E\) 사이에는 중복되는 이웃 노드가 없으므로 값이 항상 0이 되지만, 꽤 중요한 노드일 수도 있다.
이 문제를 해결하기 위해 global neighborhood overlap을 사용한다.
Global Neighborhood Overlap
Global neighborhood overlap에서는 graph 전체를 고려하기 위해 Katz index를 사용한다.
Katz index란, 노드 쌍 사이의 (모든 길이에 대한) 모든 path의 수를 센다.
이때 adjacency matrix의 power(거듭제곱)를 사용한다.
Adjacency matrix \(\mathbf{A}\)에서두 노드 \(u, v\) 사이에 길이가 1인(즉, 서로 연결된) path 개수는 \(\mathbf{A}_{uv}\)이다.
Adjacency matrix \(\mathbf{A}\)에서 두 노드 \(u, v\) 사이에 길이가 2인 path 개수는 \(\mathbf{A}_{uv}^2\)이다.
...
Adjacency matrix \(\mathbf{A}\)에서 두 노드 \(u, v\) 사이에 길이가 l인 path 개수는 \(\mathbf{A}_{uv}^l\)이다.
위를 증명해보자.
\(\mathbf{P}_{uv}^{(K)}\)가 \(u\)와 \(v\) 사이의 길이가 \(K\)인 path 개수라 하자.
먼저 길이가 1인 경우는 adjacency matrix의 정의에 의해 당연하다. (\(\mathbf{P}_{12}^{(1)} = \mathbf{A}_{12}\))
다음으로 길이가 2인 경우(\(\mathbf{P}_{uv}^{(2)}\))를 알아보자. \(u\)에서 출발하므로, \(u\)의 각 이웃 노드와 \(v\) 사이에 길이가 1인 path의 수를 구하고, 모두 더하면 될 것이다. 그 과정을 식으로 나타내면 다음과 같다.
\( \mathbf{P}_{uv}^{(2)} = \sum\limits_{i} \mathbf{A}_{ui} * \mathbf{P}_{iv}^{(1)} = \sum\limits_{i} \mathbf{A}_{ui} * \mathbf{A}_{iv} = \mathbf{A}_{uv}^2 \)
이를 확장하면 \(\mathbf{P}_{uv}^{(K)} = \mathbf{A}_{uv}^k\)임을 알 수 있다.
따라서 두 노드 \(v_1, v_2\) 사이의 Kat index는 다음과 같이 계산한다.
\( S_{v_1 v_2} = \sum\limits_{l=1}^\infty \beta^l \mathbf{A}_{v_1 v_2}^l \)
여기서 \(\beta\)는 0과 1 사이의 값으로, discount factor이다.(1에 가까울수록 길이의 영향이 커진다.)
Closed form으로는 다음과 같이 나타낸다.
\( \mathbf{S} = \sum\limits_{i=1}^\infty \beta^i \mathbf{A}^i = \left( \mathbf{I} - \beta \mathbf{A} \right)^{-1} - \mathbf{I} \)
참고로, matrix에 대한 무한 급수를 closed form으로 나타낼 때에는 geometric series(기하 급수)를 이용한다.
\(\sum\limits_{i=1}^\infty \beta^i \mathbf{A}^i = \left( \mathbf{I} - \beta \mathbf{A} \right)^{-1} \)
Graph-level Features and Graph Kernels
Graph-level feature는 그래프 전체를 표현할 수 있는 구조를 말한다.
먼저, kernel method가 무엇인지 알아둘 필요가 있다.
Kernel method란, graph-level prediction을 진행하는 전통적인 ML에서 사용되는 방법으로, feature vector 대신에 kernel이라는 것을 설계한다.
Kernel이 무엇인지 간단히 살펴보자면, kernel \(K(G, G') \in \mathbb{R}\)는 data point간의 유사도를 측정하는 데 쓰인다.
Kernel matrix \(\mathbf{K} = \left( K \left( G, G' \right) \right)_{G, G'}\)는 항상 positive semidefinite (=양의 eigenvalue를 가짐)이어야 하고, 다음을 만족하는 feature representation (vector) \(\boldsymbol{\phi}(\cdot)\)이 존재한다.
\( \left( G, G' \right) = \boldsymbol{\phi}(G)^T \boldsymbol{\phi}(G') \)
이러한 kernel은 기존 머신러닝 모델인 kernel SVM 등에서 많이 사용됐었다.
그리고 Graph의 feature는 다음과 같은 종류가 있다. (모두 graph에 대한 kernel이다. 즉 두 그래프에 대한 유사도를 측정한다.)
- Graphlet Kernel
- Weisfeiler-Lehman Kernel
- 이외에도 random-walk kernel, shortest-path graph kernel 등 많은 feature가 있다.
마찬가지로 하나씩 살펴보자.
Graph Kernel - Idea
Graph kernel의 목적은 graph의 feature vector \(\boldsymbol{\phi}(G)\)를 설계하는 것이다.
핵심 아이디어로 graph에 대한 BoW(Bag-of-Words)를 사용한다. BoW는 간단히 document 전체에 대한 word 개수를 세는 것이다. (순서에 상관이 없다.)
단순히 graph로 확장해서 생각해보면, node의 개수를 세어 feature로 활용하는 방법일 것이다. (이름 붙이자면 Bag of Nodes..?)
하지만, 노드 개수가 같다고 해도 완전히 다른 그래프일 수 있다. Edge가 매우 다양하게 존재할 수 있기 때문이다.
그럼 node degree를 사용하는 것은 어떨까? (Bag of Degrees)
위 예시와 같이 처음 방법보다는 적절한 feature인 듯 하다.
이러한 방식으로, Graphlet kernel과 Weisfelier-Lehman(WL) Kernel 모두 'Bag-of-Something'을 통해 그래프를 표현한다. 문제는 어떤 것을 셀 것인가이다.
Graphlet Features
Graphlet feature의 핵심 아이디어는 주어진 graph의 graphlet의 개수를 세는 것이다.
Graphlet in Graphlet features
그런데 앞서 언급했던 graphlet과는 조금 정의가 다르다.
- 노드끼리 연결되지 않아도 된다. (Isolated node도 고려한다.)
- Not rooted
예시를 통해 알아보자.
노드 개수가 k개인 graphlet의 list를 \(\mathcal{g}_k = \left( g_1, g_2, \dots, g_{n_k} \right) \)라 하자.
원래 graphlet의 정의에 따르면 3-node graphlet은 다음과 같다.
하지만 여기서는 k=3일 때의 graphlet이 다음과 같이 4개가 존재한다.
k=4일 때에는 다음과 같이 11개의 graphlet이 존재한다. (원래는 6개이다.)
Graphlet Count Vector & Graphlet Kernel
그럼 graph가 주어졌을 때 feature를 어떻게 나타내는지 알아보자.
주어진 graph \(G\)에 대해, graphlet list \(\mathcal{g}_k = (g_1, g_2, \dots, g_{n_k})\)는 다음과 같은 graphlet count vector \(\boldsymbol{f}_G \in \mathbb{R}^{n_k}\)를 정의한다.
\( (\boldsymbol{f}_G)_i = \# (g_i \subseteq G) \text{ for } i = 1, 2, \dots, n_k \)
위 예시에 대해 k=3인 graphlet에 대한 예를 들어 보면, \(G\)는 다음과 같은 graphlet을 포함할 것이다.
이를 graphlet count vector로 나타내면 \(\boldsymbol{f}_G = \left(1, 3, 6, 0 \right)^T\)으로 나타낼 수 있다.
이러한 방식으로 구한 graphlet count vector가 바로 kernel을 나타내는 feature가 될 것이다.
두 그래프 \(G, G'\)이 주어졌을 때, graphlet kernel은 다음과 같이 계산한다.
\( K(G, G') = \boldsymbol{f}_G^T \boldsymbol{f}_{G'} \)
하지만 \(G\)와 \(G'\)의 크기가 다르다면, 단순히 graphlet 개수를 세면 당연히 크기가 큰 경우가 값이 커질 가능성이 높다. 이 효과를 없애주기 위해 각 feature vector를 normalize해준다.
\( \boldsymbol{h}_G = \cfrac{\boldsymbol{f}_G}{\text{Sum}(\boldsymbol{f}_G)} \)
따라서 최종 graphlet kernel은 다음과 같이 계산한다.
\( K(G, G') = \boldsymbol{h}_G^T \boldsymbol{h}_{G'} \)
Graphlet Kernel의 문제점
Graphlet kernel은 graphlet의 개수를 세는 데 시간이 많이 든다는 치명적인 단점이 있다.
Size가 n인 graph에 대해 size가 k인 graphlet을 세는 데 \(n^k\)의 연산이 필요하다.
(Graph가 다른 graph의 subgraph인지 판단하는 문제는 NP-hard 문제이므로, worst-case를 피할 수 없다. graph의 node degree를 \(d\)로 제한하면 시간복잡도가 \(O(nd^{k-1})\) 알고리즘이 존재하긴 한다.)
다음으로는 시간복잡도 측면에서 좀 더 효율적인 'WL Kernel'을 알아보자.
Weisfeiler-Lehman Kernel
WL kernel은 좀 더 효율적인 feature descriptor \(\boldsymbol{\phi}(G)\)로 multi-hop neighborhood information을 사용한다. 즉, 이웃 구조를 반복적으로 적용하는 'color'라는 개념을 사용한다.
Color Refinement Algorithm
따라서 WL kernel은 color refinement라고도 한다. 이 알고리즘의 과정을 살펴보자.
노드 집합 \(V\)를 갖는 graph \(G\)가 주어졌을 때,
- 각 노드 \(v\)에 initial color \(c^{(0)}(v)\)를 할당한다.
- 다음 식으로 노드의 color를 반복적으로 수정한다.
- \( c^{(k+1)}(v) = \text{HASH}\left( \left\{ c^{(k)}(v), \left\{ c^{(k)}(u) \right\}_{u \in N(v)} \right\} \right) \)
- 어떤 노드 \(v\)의 다음 color는 해당 노드의 이전 color와 이웃 노드의 이전 color들에 대해 HASH 함수를 적용하여 구한다.
- 위 과정을 K번 반복하면, \(c^{(K)}(v)\)는 K-hop neighborhood의 구조를 표현하게 된다.
HASH함수란, 임의 길이의 데이터를 고정된 길이로 맵핑하는 함수이다. 이때 맵핑은 해시 테이블을 따라 진행된다.
예를 들어보자.
다음과 같은 두 그래프가 주어졌다. (초기 color 값까지 할당된 상태이다.)
단순히 이웃 color 값들을 합하여 다음 그래프를 얻는다.
그후, hash table을 이용하여 다음 color 값을 얻는다.
같은 방법으로 다음 color까지 구하면 다음과 같다.
Color Count Vector
이제 예시에서의 WL kernel을 구해보자. WL kernel은 주어진 color에 해당하는 노드 수를 세는 vector인 color count vector를 사용한다.
예시에서 첫 번째 그래프를 \(G\), 두 번째 그래프를 \(G'\)이라 하면, 각 color count vector는 다음과 같다.
\( \boldsymbol{\phi}(G) = \left[ 6, 2, 1, 2, 1, 0, 2, 1, 0, 0, 0, 2, 1, 0 \right]\)
\( \boldsymbol{\phi}(G) = \left[ 6, 2, 1, 2, 1, 1, 1, 0, 1, 1, 1, 0, 1 \right] \)
첫 번째 인덱스(color=1)는 첫 번째 iteration, 두 번째 인덱스(color=2)부터 다섯 번째 인덱스(color=5)는 두 번째 iteration, 이후는 세 번째 iteration임을 알 수 있다.
이를 통해 WL kernel 값을 구하면,
\( K(G,G') = \boldsymbol{\phi}(G)^T \boldsymbol{\phi}(G') = 50\)임을 알 수 있다.
WL kernel의 특징
WL kernel은 계산 효율성이 좋다.
Color refinement의 시간 복잡도는 edge 수에 대해서 선형이다.
최근댓글