[Study]Chapter 2. Traditional Methods for ML on Graphs
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
앞선 포스트에서 Graph를 사용하는 이유와 표현하는 방법을 배웠었고, 이번에는 그래프에서 데이터의 특징을 살펴보자.
I. Feature Design
효과적인 특징 \(x\)를 사용하는 것이 모델의 성능을 이끌어내는 중요한 key이다.
이전의 전통적인 ML 파이프라인은 직접 특징을 선택하는 ‘hand-designed feature’를 사용했다.
II. Node-Level Tasks and Features
\(G=(V,E)\)가 주어지면, \(f:V->\mathbb{R}\)로 학습하여 \(p(y=1\|x)\) 얻는다.
여기서 학습의 목표는 그래프에서 node의 위치와 구조를 특징화\(_{Characterize}\)하는 것이다.
1. Node degree
- degree \(k_v\)는 node \(v\)의 연결된 edge의 개수로 이웃 노드들의 중요도 수집 없이 세는게 가능하다.
2. Node centrality
노드 중심성 \(C_v\)는 노드의 중요도를 고려하는 방법으로 다양한 방법이 존재한다.
Eigenvector centrality
node \(v\)가 \(u \in N(v)\)인 중요한 이웃 노드들에 둘러쌓여 있으면 \(v\)도 중요하다.따라서, node \(v\)의 중요성을 아래와 같이 정의한다.
\[c_v = \frac{1}{\lambda}\sum_{u\in N(v)}c_u,\lambda\text{ : Normalization Constant}\]여기서 \(\lambda\)는 정규화 상수이며 A의 가장 큰 eigenvalue으로 변하는데, 위의 중심성 방정식\(_{equation}\)은 재귀적인 방식으로 아래와 같은 행렬 형태로 다시 작성되는 것을 알아야합니다.
\[\lambda c = Ac \left \{\begin{array}{ll} A_{uv}=1\text{ if }u \in N(v) \\ \lambda\text{ : Eigenvalue} \\ c\text{ : Centrality vector} \end{array} \right.\]Perron-Frobenius Theorem1에 의해 \(\lambda_{max}\)는 항상 양수\(_{positive}\)이며 고유하기 때문에 \(\lambda_{max}\)와 상호작용하는 \(c_{max}\)를 중심성으로 사용하게 된다.
Betweenness centrality
다른 노드들
\[c_v=\sum_{S\neq v\neq t}\frac{\#\text{v를 포함하는 s와 t사이의 짧은 통로}}{\#(\text{s와 t 사이의 짧은 통로})}\]사이에서 짧은 통로가 많이 놓여있다면 중요하다.Closeness centrality
다른 모든 노드에서
\[c_v=\frac{}{\sum_{u\neq v}\text{u와 v의 최단 거리}}\]가장 짧은 최단 path를 가지고 있을 수록 중요하다.and many others…
3. Clustering coefficient
노드 \(v\)와 연결된 이웃 노드들을 어떻게 연결되었는지 측정하는 방법이다.
\[e_v = \frac{\#(\text{이웃 노드들 간의 edge})}{\begin{pmatrix} k_v \\ 2 \end{pmatrix}}, \begin{pmatrix} k_v \\ 2 \end{pmatrix} = \#(k_v\text{의 degree})\]여기서 결집 계수는 그래프에서 자기를 중심(ego-network)으로 #(triangles)로 계산이 가능하다.
즉, 위의 정의를 #(graphlets)로 일반화가 가능합니다.
4. Graphlets
Graphlets는 \(u\)의 이웃 노드들의 구조를 묘사하는 작은 부분 그래프들로 노드 \(u\) 주위의 구조를 묘사하는 것입니다.
Figure 1 : size가 2-5인 노드들의 graphlets을 고려하면 node의 이웃 topology를 묘사하는 노드의 특징인 73개의 coordinates vector를 얻게 됨.
- Graphlet degree vector(GDV)
- Graphlet-base features for nodes, GDV는 연결된 #(graphlets)로 count 되고 node의 local network topolgy의 측정 방법을 제공합니다. 이는 두 노드에서 얻어진 벡터들을 비교함으로써 node degree, 결집 계수 보다 상세한 지역 topological 유사도를 얻을 수 있습니다.
우리는 이러한 특징들을 아래와 같이 분류할 수 있다.
- 중요도 기반
- 노드 차수 : 이웃 노드의 수 측정
- 노드 중심성 : 이웃 노드의 중요ㅛ성 측정(고유벡터, 매개, 근접 중심성 등)
- 구조 기반
- 노드 차수 : 이웃 노드의 수 측정
- 결집 계수 : 이웃 노드들이 얼마나 연결되었는지 측정
- GDV : 다른 graphlet들의 발생 빈도 측정
III. Link Predcition Task and Features
이미 존재하는 연결을 기반으로 새로운 연결\(_{link}\)를 예측하는 작업으로 노드 쌍의 특징을 잘 디자인하는 것이다. 예측하는 작업으로는 아래와 같이 두가지 방법이 존재한다.
- Links missing at random
- 임의로 연결을 지우고 예측.
- Links over time
- \(t_0'\)시간까지 \(G[t_0, t_0']\)가 주여졌을때, \(G[t_1, t_1']\)까지 나타날 edges들의 순위 list를 나타내고 상위 n개 중에서 맞춘 edge들의 수로 평가한다.
- \(n=\vert E_{new}\vert\), \([t_1, t_1']\)기간 동안 나타는 edge들의 수
- \(t_0'\)시간까지 \(G[t_0, t_0']\)가 주여졌을때, \(G[t_1, t_1']\)까지 나타날 edges들의 순위 list를 나타내고 상위 n개 중에서 맞춘 edge들의 수로 평가한다.
- Methodology
- 각각 노드의 쌍 (x,y)에서 score c(x,y)를 계산(ex. #[x,y의 공통 이웃])하고, 내림차순으로 정렬 후 상위 n 개의 pair를 새로운 연결로 예측하면 해당 연결은 \(G[t_1, t_1']\)에서 나타나게 되어있다.
1. Distance-based feature
해당 feature는 두 노드의 최단 거리를 측정하지만 이웃이 겹치는 degree를 수집하지 못한다.
ex. A-B-C,F-D-C 라고할떄 (A,C), (F,C)는 모두 같은 2 이지만, A-D-C가 존재할떄 (A,C)는 두 루트를 구분하지 못한다.
2. Local neighborhood overlap
두 노드들간의 공유된 이웃 노드들을 수집한다.
Common neighbors
\[|N(v_1) \cap N(v_2)|\]Jaccard’s coefficient
\[\frac{|N(v_1) \cap N(v_2)|}{|N(v_1) \cup N(v_2)|}\]Adamic-Adar index
\[\sum_{u \in N(v_1) \cap N(v_2)}\frac{1}{log(k_u)}\]
4. Global neighborhood overlap
local neighborhood features의 제한을 거는 방법으로 두 노드가 공통으로 이웃을 가지고 있지 않으면(\(\vert N_A \cap N_E\vert = 0\)) metric은 항상 0이다. 하지만 두 노드는 잠재적으로 연결되어있다. 따라서, 전체 그래프를 고려해 이러한 한계를 해결한다.
- Katz index
- 인접 행렬을 활용하여 주어진 노드 쌍의 가능한 모든 walk의 길이를 센다.
Figure 5 : 1->2->2, 1->4->2; 더 높은 거리의 이웃을 찾기 위해서는 해당 방법을 반복하면 된다(3은 2에서 1거리 노드를 찾음)
따라서, \(A^l_{uv}\)는 length l의 #walks를 알 수 있고 이다.
Figure 6 : Katz index는 walk lengths의 전체 합이다.
IV. Graph-Level Features
해당 특성들은 전체 그래프의 구조를 특징화를 얻어내는 것이다.
\[\begin{array}{ll} K = (K(G,G'))_{G,G'}\text{, 항상 positve} \\ K(G,G')=\phi(G)^T\phi(G') \\ \phi(\cdot)\text{ = representation} \end{array}\]1. Backgorund
Kernel Methods- 그래프 레벨 예측을 진행할때 전통적으로 흔히 사용되는 ML 방법으로 feature vector들을 대신하여 kernel을 디자인한다. 쉽게말해 Kernel(\(K(G,G') \in \mathbb{R}\))은 데이터 사이의 유사도로 측정된다. 이러한 kernel이 kernel SVM과 같은 off-the-shelf ML model2로 정의되었으면 예측을 하는데 사용할 수 있다.
2. Graphlet Kernel
Graph Kernels은 두 그래프의 유사도를 측정으로 Bag-of-Words(Bow)3를 graph에 적용하여 feature vector \(\phi{Q}\)를 디자인하는것이 목표이다.
그렇다면 BoW를 Graph에 적용시키는 Bag-of-node degrees를 사용하게 되면 어떻게 될까?
Figure 7 : 두개의 Graphlet Kernel과 Weisfeiler-Lehman(WL) Kernel이 그래프의 표현으로 Bag-of-*를 사용하면, *는 노드 degree보다 더 정교해\(_{sophisticated}\)진다.
여기서는 그래프에서 각기 다른 Graphlets의 수를 세는 것이 주된 핵심으로 node-level에서의 정의와 다름을 알아야한다.
두 가지 다른 점은 여기서의 Node는 연결되지 않아도(isolated nodes) 되고 특정 시작점이 고정되지 않다는 점입니다.
그래프 G가 주어졌을때, \(g_k = (g_1, g_2, ..., g_{n_k})\)는 \(f_G \in \mathbb{R}^{n_k}\)로 아래와 같이 정의된다.
\[f_{G_i}=\#(g_i \subseteq G) \text{ for i = 1,2,..., }n_k\] Figure 8 : k=3인 graphlets의 예시
두개의 그래프 \(G, G'\)가 주어졌을때 Graphlet kernel은 아래와 같이 계산된다.
\[K(G, G') = f_G^Tf_{G'}\]문제는 G, G’가 다른 사이즈인경우 값을 크게 왜곡\(_{skew}\)하기에 각 특징 벡터들을 정규화한다.
\[h_G = \frac{f_G}{Sum(f_G)},\space K(G, G')=h_G^Th_{G'}\]이러한 계산 방식은 expensive하고 worst-case를 피할 수 없고 subgraph isomorphism test가 NP-hard로 노드 degree가 \(d\)라면 Graphlets의 사이즈가 k의 복잡도 \(O(nd^{k-1})\) 이다.
3. WL-Kernel
WL(Weisfeiler-Lehman) kernel은 앞선 Graphlet Kernel 보다 더 효과적인 \(\phi(G)\)를 디자인하는것이다.
주된 핵심으로 이웃 구조를 사용해 반복적으로 노드의 어휘\(_{vocabulary}\)를 풍요롭게하는 것이다. 해당 방법을 사용하는 알고리즘으로 “Color Refinement”가 있다.
Color Refinement- 노드 V의 집합을 가진 그래프 G가 주어졌을때 초기 색상 \(c^{(0)}(v)\)을 각 노드 v에 부여하고, 반복적으로 node의 색상을 아래와 같은 방법으로 통해 재정의한다. \[c^{(k+1)}(v)=HASH({c^{(k)}(v), c^{(k)}(u)_{u \in N(v)}})\]
여기서 HASH는 다른 input을 다른 색상으로 매핑하는 함수이고, K번의 색상 재정의 이후에 \(c^{(k+1)}(v)\)는 K-hop 이웃의 구조를 요약하게 됩니다.
Figure 9 : 초기에 같은 색상을 배정하고, 이웃의 색상들을 종합하는 과정
Figure 10 : 이웃과의 색상이 종합된 이후 HASH함수를 통해 색상을 부여하는 과정
위 과정을 k번 반복한 이후에 WL-kernel은 주어진 node들의 숫자를 count하게 됩니다. 이렇게 생성된 색상 개수 차원의 vector들({2,5,4,3,4,2}, {2,5,3,4,4,2})의 내적곱을 통해 \(K(G,G')\)를 계산하게 됩니다.
WL kernel은 효과적인 계산이 가능하고, 각 color refinement의 시간 복잡도는 #(edges)에 선형적이며 이웃 색상을 더 하는 과정이 포함되기떄문입니다. 색상은 두 그래프를 따라가면서 만들어지기 떄문에 #(colors)도 node의 최대 숫자만큼 됩니다.
이렇게 Graphlets Kernel, WL-Kernel 이외에도 Rankdom-walk kernel, Shortest-path graph kernel 등 Graph-level의 feature를 추출하는 다양한 방법들이 존재합니다.