CS224W - (2) Traditional Methods for Machine Learning in Graphs

그래프에서 ML을 위한 피처 엔지니어링

그래프 형태의 데이터를 ML로 학습한다고 할 때 전통적인 ML 파이프라인이라면 그래프의 노드, 링크, 그래프 그 자체에 대한 피처를 디자인하고 모든 학습 데이터에서 피처를 생성해야 합니다. 그 다음 로지스틱 회귀나 랜덤 포레스트같은 모델을 학습하고 새로 입력된 노드, 링크, 그래프에 대해 생성한 피처를 적용해 예측값을 얻습니다.

이번 포스트에서 다룰 내용은 바로 피처 디자인입니다. 그래프에 효과적인 피처를 사용하는 것이 좋은 모델 성능을 달성하는 방법인건 모두가 다 압니다. 하지만 전통적인 ML 파이프라인에선 직접 만든 피처를 사용합니다. 이번 포스트에선 전통적인 피처들에 대해서 살펴보고자 합니다. 간단한 설명을 위해 비방향성 그래프에 대해서만 알아보겠습니다.

노드 수준 태스크와 피처

노드 수준의 ML 태스크는 노드 분류(node classification)가 있습니다. 이런 태스크를 위해서 필요한 피처는 네트워크에서 노드의 구조와 위치를 특정 짓습니다. 고려할만한 피처는 크게 네 가지입니다.

• Node degree
• Node centrality
• Clustering coefficient
• Graphlets

Node Degree

노드 $v$의 degree $k_v$는 노드가 가진 엣지(인접 노드)의 수입니다. 인접한 모든 노드를 똑같이 취급합니다.

Node Centrality

Node degree는 인접한 노드의 수를 세어서 노드의 특징을 설명하려고 하지만 노드의 중요성은 고려하지 않습니다. 이와 다르게 node centrality는 노드의 중요성을 고려할 수 있는 방법입니다. 보통 $c_u$로 나타냅니다. Node centrality도 여러 종류로 나뉩니다.

• Eigenvector centrality
• Betweenness centrality
• Closeness centrality
• 이외 여러 가지

Eigenvector Centrality

Eigenvector centrality는 어떤 노드가 다른 중요한 노드에 둘러싸여 있다면 그 노드도 중요하다고 간주합니다. 따라서 eigenvector centrality는 인접 노드의 centrality 합으로 계산합니다.

\[e_u = \frac{1}{\lambda} \sum_{v \in V} \mathbf{A}[u, v] e_v \quad \forall u \in \mathcal{V}.\]

여기서 $\lambda$는 normalization을 위한 상수입니다. 위 식은 재귀 방식을 사용합니다. 모든 노드를 다 순회해야 값을 알 수 있게 되는거죠. 이 식을 풀기 위해서 식을 인접 행렬로 바꾸면 다음과 같습니다.

\[\lambda \mathbf{c} = \mathbf{Ac}.\]

$\mathbf{c}$는 모든 node centrality로 구성된 벡터입니다. 위 식을 통해 $\mathbf{c}$가 인접 행렬의 eigenvector인 것을 알 수 있습니다. 이때 인접 행렬 $A$는 0보다 크거나 같은 값으로만 구성되어 있습니다. 그러므로 Perron-Frobenius Theorem에 의해 가장 큰 eigenvalue $\lambda_\text{max}$는 항상 0보다 크고 오직 하나 뿐입니다. 그러면 $\lambda_\text{max}$에 대응하는 eigenvector $c_\text{max}$는 항상 존재할 것이며, 이 벡터를 centrality로 사용하면 됩니다.

:bulb: Perron-Frobenius Theorem

음수가 아닌 값으로 이루어진 $n \times n$ 행렬 $A$가 있을 때, 이 행렬은 eigenvalue 중 가장 큰 값을 갖는 고유의 eigenvalue를 가진다. 또한 이에 대응하는 eigenvector는 양수로만 구성되어 있다.

Betweenness Centrality

Betweenness centrality는 어떤 노드가 다른 노드들의 최단 경로 사이에 많이 위치할 수록 그 노드가 중요하다고 간주합니다.

\[c_v = \sum_{s \neq v \neq t} \frac{\#(\text{shortest paths between $s$ and $t$ that contain $v$})}{\#(\text{shortest paths between $s$ and $t$})}\]

Closeness Centrality

Closeness centrality는 어떤 노드가 다른 모든 노드들과 가깝게 있을 수록 중요하다고 간주합니다.

\[c_v = \frac{1}{\sum_{u \neq v} \text{shortest path length between $u$ and $v$}}\]

Clustering Coefficient

결집 계수(Clustering coefficient) 는 어떤 노드가 인접 노드와 얼마나 연결되어 있는지 측정하는 지표입니다. 노드 $u$의 결집 계수는 다음과 같이 계산합니다.

\[c_u = \frac{|(v_1, v_2) \in \mathcal{E} : v_1, v_2 \in \mathcal{N}(u)|}{\binom{d_u}{2}} = \frac{2 L_u}{k_u (k_u - 1)}.\]

위 식에서 분자는 노드 $u$의 이웃 노드간 엣지 수를 계산합니다. 분모는 노드 $u$의 이웃에 몇 쌍에 노드가 있는지 계산합니다. 만약 어떤 노드의 결집 계수가 1이라면 모든 이웃이 서로의 이웃이 됩니다.

Graphlets

결집 계수는 그래프에서 서로 연결되어 있는 세 개의 노드로 구성한 노드 트리플렛(node triplets)의 개수와 에고 그래프(ego graph) 에 있는 삼각형의 개수와 큰 관련이 있습니다. 에고 그래프란 노드 자기 자신과 그 노드의 1차 이웃으로만 구성되고 연결된 그래프를 말합니다. 위 이미지에서 두 번째 그래프를 자세히 살펴보겠습니다.

이 그래프는 총 여섯 개의 노드 트리플렛을 갖고 있습니다. 그리고 삼각형은 위에서 보듯 세 개가 있습니다. 이를 이용해 계산한다면 결집 계수는 삼각형의 개수와 노드 트리플렛 개수의 비율이 됩니다. 앞으로 다룰 Graphlet은 위에서 설명한 삼각형을 세는 방법을 이용해 결집 계수를 보다 일반화한 노드 피처입니다.

Induced Subgraph

Graphlet은 어떤 노드의 네트워크 내 이웃 구조를 설명하는 작은 서브그래프입니다. Graphlet을 자세히 다루기 전에 몇 가지 정의에 대해서 짚고 넘어가야 합니다. 첫 번째는 Induced subgraph 입니다. Induced subgraph는 몇 개의 노드를 골랐을 때 해당 노드들이 사이에 연결되어 있는 모든 엣지를 포함하는 서브그래프를 말합니다.

위 그림에서 맨 왼쪽에 있는 그래프를 예로 들겠습니다. 노드 B, C, $u$를 선택했을 때 해당 노드로 구성된 Induced subgraph는 모든 노드가 연결되어 있는 서브그래프입니다. 기존 그래프에서 각 노드가 모두 연결되어 있었기 때문이죠. 따라서 맨 오른쪽 그림에 있는 서브그래프는 원래 그래프와는 다르므로 Induced subgraph가 되지 못합니다.

Graph Isomorphism

같은 노드 수의 두 그래프가 동일한 방식으로 연결되어 있을 때 두 그래프가 isomorphic 하다고 말합니다.

위 두 그래프는 달라보일 수 있지만 서로 isomorphic 합니다. 다음과 같이 노드를 매핑해보면 쉽게 알 수 있습니다. $(e_2, c_2), (e_1, c_5), (e_3, c_4), (e_5, c_3), (e_4, c_1)$로 매핑하면 됩니다.

Graphlet의 정의

이제 위 정의를 이용하여 graphlet을 다음과 같이 정의할 수 있습니다. Graphlet은 위치가 정해진 노드로 구성되어 있고 연결되어 있는 induced non-isomorphic 서브 그래프입니다.

🧐 원문에서는 Rooted connected induced non-isomorphic subgraph라고 정의하고 있습니다.

다음은 두 개의 노드부터 다섯 개의 노드까지의 Graphlet의 모음입니다.

위 그림에서 3-node graphlets에서 알 수 있듯이 노드의 개수는 같지만 서로 다른 형태의, 다시 말해서 isomorphic하지 않은 서브 그래프들로 구성되어 있습니다. 그림에서 알 수 있듯이 총 73개의 서로 다른 graphlet이 있습니다. 73개 좌표의 벡터는 노드 이웃의 위상을 설명하는 노드의 특징이 됩니다.

Graphlet Degree Vector (GDV)

Graphlet을 이용해 새로운 개념을 이끌어낼 수 있는데 바로 Graphlet Degree Vector (GDV) 입니다. GDV는 주어진 노드를 기준으로 한 graphlet의 벡터 수입니다. GDV는 노드의 국소적인 네트워크 위상을 측정한 결과를 제공합니다. 두 노드의 벡터를 직접 비교하면 node degree나 결집 계수보다 더 자세한 국소적인 위상 유사도(local topological similarity)를 측정할 수 있습니다.

위와 같은 그래프가 있을 때 노드 $u$에 대해 오른쪽에 있는 세 개의 graphlet을 고려할 수 있습니다. Graphlet에서 기준이 되는(rooted) $a$, $b$, $c$, $d$로 노드 $u$에 대해 다시 그려보자면 아래와 같습니다.

노드 $u$에 대한 GDV는 $[a, b, c, d] = [2, 1, 0, 2]$가 됩니다.

링크 예측 태스크와 피처

링크 수준 예측 태스크

링크 수준의 예측 태스크는 이미 존재하는 링크를 기반으로 새로운 링크를 예측하는 것입니다. 실제 테스트 시점에는 링크가 없는 노드 쌍에 대해 순위를 매겨 상위 $K$개의 노드 쌍을 예측하게 됩니다. 여기서 가장 중요한 것은 그 한 쌍의 노드에 대한 피처를 디자인하는 것입니다.

링크 예측 태스크는 크게 두 개로 나눌 수 있습니다. 첫 번째로 임의의 링크를 제거하고 그 링크를 예측하는 것입니다. 두 번째는 시간에 따른 링크를 예측하는 것입니다. 주어진 시간 $t_0^\prime$에 존재하는 엣지들로 정의된 그래프 $G[t_0, t_0^\prime]$이 있을 때, 해당 시점에 없었고 이후 시점의 그래프 $G[t_1, t_1^\prime]$에 나타날 것으로 예상되는 엣지에 대한 순위를 매긴 리스트를 반환하는 태스크입니다. 태스크에 대한 평가를 위해선 테스트 기간인 $[t_1, t_1^\prime]$에 생기는 새로운 엣지인 $E_\text{new}$의 개수 $n$ 만큼의 예측된 링크 중 몇 개가 실제 발생했는지 세면 됩니다.

링크 수준의 피처 생성 방법 - (1) 거리 기반 피처 (Distance-based Feature)

링크 수준에서 거리 기반 피처는 두 노드 사이의 최단 거리를 통해 나타냅니다. 매우 간단한 방법이지만 겹치는 이웃 노드에 대한 정보를 활용하지 못한다는 문제가 있습니다. 예를 들어 노드쌍 (B, H), (B, E), (A, B)는 모두 최단 거리가 2입니다. 하지만 (B, E)와 (A, B) 노드쌍이 공유하는 이웃은 하나인 반면 (B, H)는 두 개의 이웃을 공유하고 있습니다. 최단 거리는 같지만 다른 특성을 갖고 있습니다.

링크 수준의 피처 생성 방법 - (2) 국소 이웃 중첩 (Local Neighborhood Overlap)

거리 기반 피처의 단점을 해결하기 위해 두 노드가 얼마나 많은 이웃 노드를 공유하는지 계산하여 피처를 생성할 수 있습니다. 다음의 세 가지 방법으로 국소 이웃 중첩을 계산할 수 있습니다.

• 공통 이웃 : $|N(v_1) \cap N(v_2) |$
  • $|N(A) \cap N(B)| = |{C}| = 1$
• Jaccard’s Coefficient : $\frac{|N(v_1) \cap N(v_2)|}{|N(v_1) \cup N(v_2)|}$
  • $\frac{|N(A) \cap N(B)|}{|N(A) \cup N(B)|} = \frac{|{C}|}{|{C, D}|} = \frac{1}{2}$
• Adamic-Adar Index : $\sum_{u \in N(v_1) \cap N(v_2)} \frac{1}{\log(k_u)}$
  • $\frac{1}{\log(k_c)} = \frac{1}{\log(4)}$

링크 수준의 피처 생성 방법 - (3) 전역 이웃 중첩 (Global Neighborhood Overlap)

하지만 국소 이웃 중첩 방식도 한계가 있습니다. 만약 두 개의 노드가 공통으로 갖는 이웃이 없다면 항상 국소 이웃 중첩 메트릭이 0이 되기 때문입니다. 위 그림에서 노드 A와 노드 E는 공유하고 있는 이웃이 없습니다. 지금 당장은 괜찮지만 앞으로 두 노드가 연결될 수도 있는데 말이죠. 이런 문제를 해결하기 위해서 전체 그래프에서의 이웃 중첩을 고려하는 전역 이웃 중첩 방식을 사용합니다.

대표적인 전역 이웃 중첩 방식으론 Katz index가 있습니다. Katz index는 주어진 노드 쌍 사이의 모든 길이의 방법의 수를 계산합니다. 말이 조금 어려울 수 있는데요. 아래 계산 방법을 통해 자세히 설명하도록 하겠습니다. 앞으로 다루는 모든 계산은 인접 행렬을 이용해서 수행합니다.

인접행렬 $A$에 대해서 어떤 노드 $u \in N(v)$라면 $A_{uv} = 1$인 것은 앞에서 많이 다루었습니다. 이때 노드 $u$와 노드 $v$ 사이에 길이가 $K$가 되도록 하는 방법의 수를 $P_{uv}^{(K)}$라고 두겠습니다. 우리가 보여야할 것은 $P^{(K)} = A^K$ 입니다.

위와 같은 그래프가 있습니다. $P_{uv}^{(1)}$은 두 노드 사이의 길이가 1이 되도록 하는 방법의 수입니다. 이 경우는 단순하게 두 노드가 이어져있는지를 나타냅니다.

\[A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}\]

그럼 두 노드 사이의 길이가 2가 되도록 하는 방법의 수인 $P_{uv}^{(2)}$는 어떻게 계산할까요? 일단 $P_{uv}^{(1)}$가 필요합니다. 두 노드 사이의 길이가 2가 된다는건 어떤 노드 $u$와 이어진 다른 노드가 노드 $v$와 이어져있다는 의미입니다. 이런 경우의 수를 모두 더해주면 되겠죠.

\[P_{uv}^{(2)} = \sum_i A_{ui} \cdot P_{iv}^{(1)} = \sum_i A_{ui} \cdot A_{iv} = A_{uv}^2\] \[A^2 = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} \times \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 3 \end{pmatrix}\]

이 방법을 이용해서 두 노드 사이의 길이가 $\ell$인 방법의 수를 구하면 $A_{uv}^{l}$이 됩니다. 그런데 문제는 노드 쌍의 각 길이의 방법의 수를 모두 더하는건 엄청난 계산 비용이 필요합니다. Discount factor $0 < \beta < 1$을 포함한 Katz index는 다음과 같습니다.

\[S_{uv} = \sum^\infty_{\ell=1} \beta^\ell A^\ell_{uv}\]

다행히 Geometric Series of Matrices에 의해 Katz index는 닫힌 형태로 계산이 가능합니다.

\[S = \sum^\infty_{i=1} \beta^i A^i = (I - \beta A)^{-1} - I.\]

:bulb: 실제로 위 식이 성립하기 위해서는 $\lim_{i \to \infty} \beta A = 0$ 이어야 합니다. 인접 행렬 $A$만으론 이를 만족할 수 없기 때문에 discount factor $\beta$를 이용한다고 보면 됩니다.

그래프 수준의 피처와 그래프 커널

마지막으로 그래프 전체 구조의 특징을 피처로 만드는 방법에 대해서 알아보도록 하겠습니다. 전통적으로 ML에서 그래프 수준의 예측을 할 때 커널(Kernel) 을 굉장히 많이 사용하는데 피처 벡터 대신 적절한 커널을 디자인하는게 핵심입니다. 여기서 보통 커널 $K(G, G^\prime) \in \mathbb{R}$가 데이터 사이의 유사도를 측정하는 역할을 하는데요. 이때 커널 행렬 $\mathbf{K} = \left( K(G, G^\prime) \right)_{G, G^\prime}$은 항상 양수 eigenvalues를 갖습니다. 이 커널에 대해 $K(G, G^\prime) = \phi(G)^T \phi(G^\prime)$을 만족하는 피처 표현 함수인 $\phi(\cdot)$이 존재합니다. 이런 커널을 한 번 정의해놓으면 커널 SVM 같은 모델을 이용해 바로 예측에 사용할 수 있습니다.

그래프 커널의 핵심은 그래프 피처 벡터 $\phi(G)$를 디자인하는 것입니다. 이를 위해 그래프에 대해 Bag-of-Words (BoW) 방식을 활용합니다. 보통 BoW는 텍스트 분석에서 많이 사용하는데요. BoW를 그래프에 활용한다고 하면, 가장 간단하게 텍스트 분석에서의 단어 역할을 그래프에서의 노드가 대신할 수 있을겁니다. 만약 노드 개수에 대해서 커널을 만들어 피처를 표현한다면 아래 그림처럼 나타낼 수 있겠죠.

두 그래프는 네 개의 노드를 갖고 있기 때문에 동일한 피처를 갖게 됩니다. 하지만 조금 더 복잡하게 그래프의 Node Degree에 대해서 커널을 만들면 어떨까요?

완전히 다른 양상을 보입니다. 두 그래프의 노드 수는 같지만, 각 노드의 Degree는 다르기 때문이죠. 결국 두 그래프에 커널을 적용하여 얻는 피처 벡터는 서로 다릅니다. 본 포스트에서 다룰 두 그래프의 유사도를 측정하는 그래프 커널은 크게 두 가지로 지금까지 논의한 내용보다 복잡한 방법으로 커널을 생성합니다.

• Graphlet Kernel
• Weisfeiler-Lehman Kernel

Graphlet Kernel

Graphlet Kernel의 핵심 아이디어는 그래프에서 서로 다른 graphlet의 수를 세는 것입니다. 다만 여기서의 graphlet은 노드 수준에서 논의한 graphlet하곤 조금 다릅니다. 여기서는 노드가 고립되어 있어도 문제가 없는, 즉 모두 연결되어 있을 필요가 없습니다.

주어진 그래프 $G$, graphlet 목록 $\mathcal{G}_k = (g_1, g_2, \cdots, g_k)$에 대해서 graphlet count vector $f_g \in \mathbb{R}^{n_k}$ 를 다음과 같이 정의합니다.

\[(f_G)_i = \# (g_i \subseteq G) \quad \text{for } i = 1, 2, \cdots, n_k.\]

$k=3$에 대해서 다음 그래프 $G$는 이렇게 계산됩니다.

GCV를 이용해서 두 그래프 $G$, $G^\prime$의 graphlet kernel을 다음과 같이 계산할 수 있습니다.

\[K(G, G^\prime) = f_G^T f_{G^\prime}\]

이때 두 그래프의 크기가 다른 경우 이 값에 왜곡이 발생할 수 있습니다. 각각의 피처 벡터를 정규화(normalization)하여 이런 문제를 해결할 수 있습니다.

\[h_G = \frac{f_G}{\text{Sum}(f_G)}, \qquad K(G, G^\prime) = h_G^T h_{G^\prime}.\]

좋은 방법이지만 graphlet을 계산하는 비용이 너무 크다는 것이 단점입니다. 크기가 $N$인 그래프의 $k$-size graphlet의 개수를 세는것은 $n^k$ 만큼의 연산이 필요합니다. 그래프의 node degree가 $d$로 제한이 되어 있다면 모든 $k$-size graphlet을 계산하는 시간 복잡도는 $O(nd^{k-1})$가 됩니다.

Weisfeiler-Lehman Kernel

그러면 보다 효율적인 커널이 필요합니다. 바로 Weisfeiler-Lehman Kernel 입니다. 이 커널은 아까 위에서 논의한 Bag of node degrees의 일반화된 버전입니다. 이 커널을 계산하기 위해서는 color refinement algorithm을 활용합니다.

노드 집합 $V$를 갖는 그래프 $G$가 주어졌을 때, 각 노드 $v$에 초기화 색인 $c^{(0)}(v)$를 부여합니다. 그리고 각 노드의 색을 다음 수식을 통해 반복적으로 개선합니다.

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

여기서 $\text{HASH}$는 해시맵 함수로 입력값이 다르면 다른 색을 반환하는 함수입니다. 이를 $K$번 반복하여 얻는 $c^{(K)}(v)$가 $K$-hop 이웃의 구조를 요약한게 됩니다.

WL 커널은 높은 계산 효율성을 갖습니다. 한 번의 color refinement는 엣지의 수에 선형인 시간 복잡도를 가집니다. 만약 커널을 계산한다면 기껏해야 두 그래프에 있는 노드만큼의 계산만 하면 됩니다. 따라서 최종 시간 복잡도는 총 엣지의 수에 선형적이게 됩니다.