CS224W - (3) Node Embeddings

들어가며

전통적인 머신러닝에서 그래프를 다룰 때는 위 그림과 같은 프로세스를 가졌습니다. 입력값으로 그래프를 받으면 피처 엔지니어링을 통해 구조화된 피처를 생성하고 모델을 학습하여 예측값을 반환했죠. 이 모든 과정은 태스크마다 새롭게 진행되어야 했고, 많은 시간을 들여야 했습니다.

하지만 앞으로 다룰 그래프 표현 학습(Graph Representation Learning) 을 통해서라면 매번 피처 엔지니어링을 수행할 필요가 없어집니다. 특징 학습 또는 표현 학습이라고도 불리는 방법을 통해 피처를 자동으로 학습할 수 있습니다. 그러면 위에서 언급한 단점들을 충분히 해결할 수 있게 되죠.

그래프 표현 학습의 목표는 그래프를 머신러닝으로 작업하되 태스크에 독립적이고 효율적인 특징 학습을 수행하는 것입니다. 그러기 위해서는 그래프의 노드를 피처를 표현하는 어떤 벡터로 변환하여 임베딩 공간(embedding space) 에 매핑시켜야 합니다.

이렇게 임베딩을 하고 나면 여러 특징이 있는데요. 우선 노드를 임베딩하였을 노드 사이의 임베딩의 유사도는 실제 그 네트워크의 유사도를 나타냅니다. 두 노드가 가까이 있다면 실제 임베딩 벡터도 가까이 위치하고 있는거죠. 또한 임베딩은 네트워크의 정보를 인코딩하여 갖게 됩니다. 마지막으로 임베딩은 노드 분류, 링크 예측, 그래프 분류, 이상 감지, 클러스터링 등 다양한 태스크에서 활용하게 됩니다.

노드 임베딩 : 인코더와 디코더

본 절에서는 네 개의 노드를 가진 그래프를 다뤄서 노드 임베딩을 설명합니다.

• 그래프 $G$
• 노드 집합 $V = { 1, 2, 3, 4 }$
• 인접 행렬 $A$

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

이제 도트 곱(dot product) 같은 임베딩 공간의 유사성이 실제 그래프의 유사성에 가까워지도록 노드를 인코딩하는 것이 목표입니다. 실제 그래프에서 두 노드 $u$와 $v$의 유사도를 $\text{sim}(u, v)$ 라고 할 때 다음과 같은 식을 만족하도록 하는 것이 목표인거죠.

\[\text{sim}(u, v) \approx z_v^T z_u = \text{ENC}(v)^T \text{ENC}(u)\]

이제 실제 그래프에서의 유사도와 노드를 인코딩하는 방식에 대해서 정의해야 합니다. 우선 노드 임베딩을 학습하는 방법은 다음과 같습니다.

1. 인코더가 노드를 임베딩에 매핑합니다.
2. 실제 네트워크의 유사도에 대한 메트릭과 같은 노드 유사도 함수를 정의합니다.
3. 디코더가 임베딩을 유사도에 매핑합니다.
4. 마지막으로 다음을 만족하도록 파라미터를 최적화합니다.

\[\text{sim}(u, v) \approx z_v^T z_u\]

인코더는 각 노드를 저차원의 벡터로 매핑하는 역할을 합니다. 반대로 디코더는 인코더가 생성한 노드 임베딩에서 유사도 같은 특정 그래프 통계를 재구성하는 역할을 합니다. 인코더와 디코더를 사용한 방법을 묘사하면 다음과 같습니다.

Shallow Encoding

가장 간단한 인코딩 방식은 인코더가 단순히 룩업 테이블에서 입력으로 주어진 노드 인덱스의 열만 출력하는 것입니다.

\[\text{ENC}(v) = z_v = Z \cdot v\]

• $Z \in \mathbb{R}^{d \times |\mathcal{V}|}$
  • 각 컬럼이 노드 임베딩인 행렬로 학습해야 하고 최적화해야 하는 목표
• $v \in \mathbb{I}^{|\mathcal{V}|}$
  • Indicator vector

이 방법은 각 노드가 개별적인 임베딩 벡터를 갖게 되는데, 각 노드의 임베딩을 직접 최적화할 수 있다는 장점이 있습니다. 하지만 반대로 노드의 수가 많아질 경우 룩업 테이블이 매우 커진다는 단점이 있습니다. Shallow encoding을 쓰는 기법을 많이 찾아볼 수 있는데 DeepWalk나 node2vec 등이 있습니다.

노드 임베딩을 위한 랜덤 워크 접근법

랜덤 워크는 문자 그대로 그래프의 노드에서 다른 이웃으로 순차적으로, 그리고 임의대로 이동하는 것을 말합니다. 그래프와 시작점이 주어지면 시작점의 이웃을 무작위로 선택하고 그 이웃으로 이동한 다음, 아까의 방법을 계속 반복합니다. 만약 두 랜덤 워크가 있을 때 두 노드 $u$와 $v$가 함께 등장하는 빈도가 높다면 두 노드는 서로 가깝게 위치한다고 볼 수 있습니다. 그래서 위에서부터 계속 언급해왔던 $\text{sim}(u, v)$를 여기에선 랜덤 워크에서 두 노드가 함께 등장할 확률로 볼 수 있습니다.

\[z_u^T z_v = \text{Probability that $u$ and $v$ co-occur on a random walk over the graph}\]

랜덤워크 임베딩은 다음 순서대로 진행됩니다.

1. 노드 $u$로부터 시작하는 어떤 랜덤 워크 $R$이 있을 때, 이 랜덤 워크가 노드 $v$를 지날 확률 $P_R(v \mid u)$를 추정합니다.
2. 이 확률값을 토대로 임베딩을 최적화 합니다. 이때 임베딩 공간에서의 유사도는 $z_u$와 $z_v$의 내적입니다.

랜덤 워크의 장점은 다음과 같습니다.

1. 표현력(Expressivity)
   • 국소적인 이웃 정보와 높은 차원의 이웃 정보를 모두 통합하는 노드 유사도에 대한 확률적 정의이기 때문
2. 효율성(Efficiency)
   • 학습 시 모든 노드 쌍을 고려할 필요 없이 랜덤 워크에서 함께 등장하는 노드 쌍만 고려하면 되기 때문

이제 최적화시키는 것만 남았습니다. 주어진 그래프 $G = (V, E)$에 대해서 어떤 맵핑 $f: u \to \mathbb{R}^d \implies f(u) = z_u$ 를 학습하는 것이 목표입니다.

1. 우선 노드 $u$에서 시작하는 짧은 거리의 랜덤 워크 $R$을 수행합니다.
2. 각 노드 $u$로부터 이웃 $N_R(u)$를 수집합니다. 이때 $N_R(u)$는 랜덤 워크에서 특정 노드를 여러 번 지날 수 있기 때문에 중복된 원소를 가질 수 있습니다.
3. 주어진 노드 $u$에 대해 이웃 $N_R(u)$를 예측하는 것을 목적으로 다음 목적 함수를 최적화 합니다.

\[\max_f \sum_{u \in V} \log P(N_R(u) \mid z_u)\]

위 식은 다음과 같이 쓸 수 있습니다.

\[\mathcal{L} = \sum_{u \in V} \sum_{v \in N_R(u)} -\log(P(v \mid z_u))\]

여기서 랜덤 워크에서 동시에 두 노드가 등장할 우도(likelihood)를 최대화하는 방향으로 임베딩을 최적화합니다. 이때 $P(v \mid z_u)$를 소프트맥스 함수를 이용해서 매개변수화합니다.

\[P(v \mid z_u) = \frac{\exp(z_u^T z_v)}{\sum_{n \in V} \exp(z_u^T z_n)}.\]

다시 손실 함수를 정리하면 다음과 같습니다.

\[\mathcal{L} = \sum_{u \in V} \sum_{v \in N_R(u)} -\frac{\exp(z_u^T z_v)}{\sum_{n \in V} \exp(z_u^T z_n)}\]

하지만 이 계산을 하게 되면 맨 처음 합과 소프트맥스의 분모에서 $V$ 를 거듭하여 계산하는 문제가 생깁니다. 즉 $O(|V|^2)$ 만큼의 복잡도가 요구되는데 계산 비용이 너무나 크다는 문제가 있습니다.

네거티브 샘플링(Negative sampling)

그래서 여기에서 그 유명한 네거티브 샘플링을 사용합니다. Word2Vec에 사용된 매우 유명한 기법으로 이 경우엔 전체 노드에 대해 내적을 계산하는 대신 노드 $u$와 이웃하지 않은 노드 $k$개를 샘플링하여 일종의 log loss를 계산하게 됩니다.

\[\frac{\exp(z_u^T z_v)}{\sum_{n \in V} \exp(z_u^T z_n)} \approx \log (\sigma(z_u^Tz_v)) - \sum^k_{i=1} \log(\sigma(z_u^T z_{n_i})), \quad n_i \sim P_V\]

여기서 $\sigma$는 시그모이드 함수로 소프트맥스에 비해 계산적으로 매우 빠르다는 장점이 있습니다. 그리고 $k$ 개의 노드는 각각의 degree에 비례하여 확률을 계산해 샘플링을 합니다. 보통 $k$는 5에서 20 정도의 값으로 설정합니다. $k$의 값이 클 수록 더 강건한 추정을 하지만 이웃하지 않은 노드에 더욱 편향적인 결과가 나올 수 있습니다. 마지막으로 네거티브 샘플링을 적용한 손실 함수에 Stochastic Gradient Descent를 적용하여 임베딩을 최적화하면 됩니다.

Node2Vec

위의 랜덤 워크 방식을 보다 일반화한 node2vec 방식에 대해서 알아보도록 하겠습니다. 우선 node2vec의 목적은 네트워크 내 비슷한 이웃을 가진 노드를 피처 공간에 가깝게 임베딩시키는 것입니다. 그리고 이 목적 달성을 위해 다운스트림 예측 태스크들과 최대한 독립적인 최대 우도(maximum likelihood) 최적화 문제로 설정합니다.

Node2vec이 위 방법과 가장 다른 점은 그래프에서 이웃 노드 집합 $N_R(u)$를 찾을 때 비교적 유연한 랜덤 워크 전략 $R$을 이용해 노드 임베딩에 더욱 풍부한 정보를 인코딩한다는 점입니다. 이 풍부한 정보를 위해 그냥 랜덤 워크가 아닌 편향된 이계(second-order) 랜덤 워크를 활용합니다. 이 편향된 랜덤 워크는 각각 네트워크의 국소적인 측면과 전역적인 측면을 바라볼 때 발생하는 트레이드 오프의 균형을 맞출 수 있는 유연성을 제공합니다.

BFS와 DFS의 트레이드 오프

위와 같은 그래프가 있다고 할 때 node2vec은 노드 $u$의 이웃을 정의하는 두 가지 방식을 사용합니다. $N_R(u)$의 크기가 3이라고 가정했을 때 우선 국소적인 미시적 관점에서의 이웃은 다음과 같습니다.

\[N_\text{BFS}(u) = \{ s_1, s_2, s_3 \}\]

전역적이고 거시적인 관점에서의 이웃은 조금 다릅니다.

\[N_\text{DFS}(u) = \{ s_4, s_5, s_6 \}\]

편향 랜덤 워크

고정 길이의 편향된 랜덤 워크는 다음 두 가지 파라미터를 사용합니다.

• $p$
  • 이전 노드로 돌아갈 확률을 정하는 파라미터
• $q$
  • 직전 노드에서 먼 노드로 갈 확률을 정하는 파라미터
  • DFS와 BFS의 비율을 정하는 개념

랜덤 워크로 처음 노드 $s_1$에서 현재 $w$로 도착했다고 가정하겠습니다. 요컨대 노드 $w$에서 움직일 수 있는 경우의 수는 모두 세 가지 입니다.

• $s_1$으로 돌아가기
• 거리가 동일한 $s_2$로 이동하기 ($w$와 $s_2$는 모두 $s_1$의 이웃)
• 거리가 더 멀어지는 $s_3$로 이동하기

실제 어떤 노드로 이동하게 되는지는 위에서 언급한 파라미터 $p$와 $q$에 의해서 정해집니다.

위에서 언급한 경우의 수 세 가지와 파라미터 $p$, $q$는 다음 방식으로 대응됩니다.

• 원래 노드로 돌아갈 확률 : $1/p$
• 거리가 동일한 원래 노드의 이웃으로 이동할 확률 : $1$
• 거리가 더 멀어지도록 이동할 확률 $1/q$

이 모든 확률값은 정규화되지 않습니다. BFS와 DFS의 관점에서 이야기 해본다면 BFS 처럼 행동하기 위해서는 $p$의 값이 낮아야 합니다. 그래야지만 거리가 동일한 원래 노드의 이웃으로 이동할 확률이 높아지기 때문이죠. 반대로 $q$의 값이 낮아진다면 더 먼 곳으로 이동할 확률이 높아지기 때문에 DFS처럼 행동하게 됩니다. 즉 $p$와 $q$에 따라 랜덤 워크가 편항적으로 진행되게 됩니다.

학습 알고리즘

Node2vec의 학습 알고리즘은 다음의 순서를 가집니다.

1. 랜덤 워크 확률을 계산합니다.
2. 노드 $u$에서 시작하는 길이 $l$의 랜덤 워크 $r$을 실행합니다.
3. SGD를 이용해서 node2vec의 목적 함수를 최적화합니다.

Node2vec의 학습은 선형 시간 복잡도를 가져 매우 빠르게 진행됩니다. 또한 각 순서를 병렬 처리할 수 있어 더욱 빠르게 학습할 수 있죠.

전체 그래프 임베딩하기

이번에는 전체 그래프를 임베딩하는 방법에 대해 알아보도록 하겠습니다. 우리가 하고자 하는 것은 그래프 $G$나 그 서브그래프를 임베딩하는 것입니다.

지금까지 다루었던 방법을 활용하여 간단하게 구현해본다면 노드 임베딩을 사용할 수 있습니다. 노드 임베딩을 그래프 $G$나 그 서브그래프에 적용합니다. 그리고 그래프나 서브그래프의 노드 임베딩을 모두 더하거나 평균을 계산합니다.

\[z_g = \sum_{v \ in G} z_v\]

다른 방법으로는 가상 노드(virtual node) 를 사용하는 방법입니다. 임베딩하고자 하는 그래프나 서브그래프의 모든 노드와 연결된 가상 노드를 생성합니다. 그리고 여기에 기본적인 그래프 임베딩 방식을 적용합니다.

행렬 분해와 노드 임베딩

노드 임베딩을 다시 살펴보면 가까이 있는 두 노드 $u$와 $v$에 대해서 노드 임베딩 $z_v^T z_u$를 최대화하는 목적함수를 통해 임베딩을 합니다. 임베딩 행렬 $Z$는 임베딩 차원 $d$에 대해 $d \times |\mathcal{V}|$의 크기를 갖습니다. 가장 간단한 노드 유사도는 노드간 연결 정보이기 때문에 어떻게 보면 $z_v^T z_u$는 인접 행렬에서 $A_{u, v}$와 같다고 생각할 수 있습니다.

\[Z_T Z = A\]

임베딩 차원 $d$는 일반적으로 노드의 수 $n$보다 매우 작습니다. 또한 인접 행렬 $A$를 완벽하게 $Z^T Z$ 형태로 분해하게 만드는 $Z$를 계산하는 것도 불가능합니다. 그래서 보통 행렬 분해는 $Z$를 근사적으로 학습하도록 합니다.

\[\min_Z \| A - Z^T Z \|_2\]

위 식대로 $A - Z^T Z$의 L2 norm을 최소화하는 $Z$를 찾도록 최적화를 하는데, 요즘은 L2 norm 대신 소프트맥스를 많이 사용하고 있습니다. 결론적으로 엣지간 연결로 정의한 노드 유사도를 사용한 내적 디코더는 인접 행렬 $A$에 대한 행렬 분해와 같음을 알 수 있습니다.

이와 유사하게 Deepwalk과 node2vec도 행렬 분해로 나타낼 수 있는데 랜덤 워크 기반의 복잡한 노드 유사도를 정의하기 때문에 굉장히 복잡한 행렬 분해식을 얻게 됩니다. 가령 Deepwalk은 다음의 행렬 분해 형태로 나타낼 수 있습니다. 자세한 설명은 아래 이미지로 갈음합니다.

\[\log \left( \text{vol}(G) \left( \frac{1}{T} \sum^T_{r=1} (D^{-1} A)^r \right) D^{-1} \right) - \log b\]

Node2vec은 이보다 더 복잡하여 따로 논문을 찾아보시는 것을 추천 드립니다.

임베딩의 활용

노드 임베딩은 다음 태스크에 활용될 수 있습니다.

• 클러스터링 / 커뮤니티 검출 : 클러스터 포인트 $z_i$
• 노드 분류 : $z_i$에 기반한 노드 $i$의 라벨 예측
• 링크 예측 : $(z_i, z_j)$에 기반한 $(i, j)$ 엣지 예측
  • 두 임베딩 $z_i, z_j$를 여러 방식으로 사용할 수 있습니다.
    • Concatenate: $f(z_i, z_j) = g([z_i, z_j])$
    • Hadamard: $f(z_i, z_j) = g(z_i * z_j)$
    • Sum/Avg: $f(z_i, z_j) = g(z_i + z_j)$
    • Distance: $f(z_i, z_j) = g(\| z_i - z_j \|_2)$
• 그래프 분류: 노드 임베딩이나 임의의 랜덤 워크를 집계한 그래프 임베딩 $z_G$를 활용하여 라벨을 예측

노드 임베딩의 한계

노드 임베딩은 다음의 한계점을 갖고 있습니다.

1. 학습 데이터에 존재하지 않는 노드에 대한 임베딩을 얻을 수 없습니다. 반드시 다시 계산해야 합니다.
2. 구조적인 유사도를 학습할 수 없습니다.

• 노드 1과 노드 11은 구조적으로 유사합니다. 삼각형의 일부이며 degree 2를 갖기 때문입니다.
• 하지만 지금까지 배운 노드 임베딩 방법으로는 매우 다른 결과값을 얻게 됩니다.
  1. 노드, 엣지, 그래프 피처를 활용할 수 없습니다.
• 단백질-단백질 상호작용 그래프를 예로 들었을 때 각 단백질의 특징을 피처 벡터로 사용할 수 있는데, 노드 임베딩은 이러한 정보를 활용할 수 없습니다.