[Study]Chapter 3. Node Embeddings

해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.

앞선 강의로 그래프의 각 Level에서의 특징을 알아보았다면 해당 챕터에서 그래프의 노드를 임베딩 공간으로 맵핑하는 임베딩에 대해 이야기 합니다.

I. Node Embeddings

그래프 표현 학습은 매번 feature engineering을 하는 것을 완화\(_{alleviates}\)합니다. 즉, 그래프에서 특정 작업에 의존하지 않고\(_{task-independent}\) 특징을 학습하는 것을 목표로합니다.

Figure 1 : Encode network information

그렇다면 왜 embedding을 사용하는가?

여기서 node들을 임베딩 공간으로 투영\(_{projection}\)하면 그래프에서 노드들의 유사도는 임베딩 공간으로 투영된 벡터들의 유사도로 나타낼 수 있게 됩니다.

많은 Downstream prediction¹에서 잠재적으로 사용될 수 있다.

Figure 2 : (좌)Graph를 2차원의 (우)embedding 공간으로 투영하여 시각화한 결과

1. Encoder and Decoder

Figure 3 : Embedding nodes; graph에 있는 노드 쌍의 유사도를 임베딩 공간으로 투영한 노드들의 유사도가 근사하게 encode하는 것이 목표

\[\begin{array}{ll} similarity(u,v) \approx z_v^Tz_u, z_v^Tz_u \text{ : 두 노드 임베딩 내적곱} \end{array}\]

여기에서 \(similarity(\cdot)\)가 \(ENC(u)\)이며 정의할 필요가 있다.

2. “Shallow” Encoding

가장 간단한 encoding 접근법은 embedding-lookup으로 \(ENC(v)=z_v=Z\cdot v\)이다.

Figure 4 : \(Z \in \mathbb{R}^{d\times\vert V\vert}\) : 각 컬럼이 node embedding인 행렬, \(v \in \mathbb{I}^{\vert V\vert}\) : indicator vector; 하나만 빼고 모두 1인 벡터 노드

각 노드를 unique한 임베딩 벡터에 배정하고, 핵심으로는 노드 유사도를 어떻게 정의하는 가이다.

두 노드가 유사하게 임베딩되어있으면, 두 노드는 연결되었는지(나이브한 방법), 이웃을 공유하는지, 구조적인 역할이 유사한지 등을 고려하여 유사도를 정의하고 이러한 유사도 측정을 하는 임베딩을 최적화한다.

비지도, 자기학습 방법으로 노드 임베딩을 학습하게 되는데 여기서 node label, feature 등은 활용하지 않고, 그래프의 구조(DEC를 통해 수집된) 측면이 보존되도록 임베등을 직접 추정하는 것입니다. 이러한 임베딩은 특정 작업에 독립적으로 작용해 어떤 작업에도 사용이 가능하다.

II. Random Walk Approaches for Node Embeddings

노드 u에서 시작하여 random walk를 통해 노드 v를 방문할 (예측된)확률을 비선형 함수(softmax, sigmoid 등)를 사용하여 확률을 추정한다.

\[\begin{array}{ll} z_u \text{ : Vector; 노드 u의 임베딩 벡터} \\ P(v|z_u) \text{ : Probability; z_u에 기반하여 예측} \end{array}\]

1. Random Walk

\[z_uz_v^T \approx \begin{matrix} \text{graph의 u,v 에서} \\ \text{rankdom walk가 함께 나타날 확률} \end{matrix}\]

Figure 5 : 그래프와 시작지점이 주어졌을때 이웃을 랜덤으로 선택하여 해당 이웃으로 랜덤하게 이동한 후 다음 이웃으로 랜덤하게 이동. 이러한 방법으로 랜덤하게 방문된 순차열\(_{sequence}\)이 그래프에서의 random walk이다.

2. Random walk embedding

1. 노드 u에서 출발하여 Random walk 전략 R을 사용하여 노드 v를 방문할 확률(\(P_R(v\vert u)\))을 추정.

2. 무작위 보행 통계량을 encode한 임베딩을 최적화.

   \[z_iz_j^T \approx cos(\theta) \propto P_R(v\vert u)\]

   즉, 임베딩 공간에서의 유사도(\(cos(\theta)\))를 그래프에서의 random walk “유사도”로 encode한다.

이러한 랜덤워크를 쓰는 이유는 무엇인가?

1. 표현력 : local과 higher-order된 이웃의 정보를 포함하는 노드 유사도를 유연한 확률적 정의가 가능.
2. 효율성 : 학습할때 모든 노드의 쌍을 고려할 필요가 없다; random walk를 통해 동일하게 발생한 쌍만 고려.

이러한 임베딩을 위해 유사도를 유지하는 d-dim 공간에 있는 임베딩을 학습하는 비지도 표현학습을 사용한다고 한다. 주된 핵심은 다른 노드 근처에 있는 노드를 네트워크에서도 서로 가까워지도록 하는 학습하는 것이다.

즉, 그래프 \(G=(V,E)\)가 주어졌을때, \(f:u \rightarrow \mathbb{R}^d\)로 매핑하는 \(f(u)=z_u\)를 학습하는 것이다.

\[\text{Log-likelihood = }\max\limits_{f}\sum_{u \in V}logP(N_R(u)\vert z_u)\]

\(N_R(u)\)는 노드 u가 주어졌을때, 근처에있는 노드를 Random walk 전략 R을 사용하여 얻어진 u의 이웃으로 정의한다.

다시말해 노드 u가 주어졌을때 \(N_R(u)\)을 예측하는 특징 표현을 학습하는 것이다.

3. Randomwalk optimization

무작위 보행을 통한 임베딩을 최적화(즉, 학습)하는 방법을 설명한다.

1. 각 노드 u에서 시작하는 짧은 고정 길이의 무작위 경로를 생성한다.
2. 각 노드 u는 \(N_R(u)\)를 수집하고, 무작위 경로를 사용하여 방문한 Node들의 Multiset을 구한다.

3. 임베딩을 최적화한다.

   node u가 주어졌을때 이웃 \(N_R(u)\)을 예측한다.

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

   임베딩 \(z_u\)를 최적화하여 무작위 보행의 동시발생의 확률을 최대화합니다.

   Figure 6 : Negative log-likelihood objective

   Figure 6의 노란색 부분에서 softmax를 사용하여 \(P(v\vert z_u)\)를 파라미터화 하는데, Softmax를 사용하면 \(\sum_i exp(x_i) \approx \max\limits_{i} exp(x_i)\)가 가능하게 됩니다.

   무작위 보행 임베딩을 최적화하는 것은 L을 최소화하는 임베딩 \(z_u\)를 찾는것과 같다.

   그러나 순진하게 위와 같이 실행하기에는 중첩된 \(\sum_{n \in V}\) 때문에 \(O(\vert V\vert^2)\)의 복잡도를 주어 비용이 많이 들기에 softmax안에 있는 정규화 항을 근사하여 해결해야한다.

   이러한 방법은 Negative sampling으로 해결한다.

   \[\begin{array}{ll} log(P(v|z_u)) & = log(\frac{exp(z_u^Tz_v)}{\sum_{n \in V}exp(z_u^Tz_v)}) \\ & \approx log(\sigma(z^T_uz_v)) - \sum^k_{i=1}log(\sigma(z^T_uz_v)), n_i \sim P_V \end{array}\]

   여기서 sigmoid function은 각 항의 확률을 0과 1사이의 값으로 변환해주고, 노드들은 무작위 분포(\(n_i~P_V\))를 따른다.

   왜 근사 방법이 유효한가?²

   기술적으로는 다른 목적 함수이지만 Negative sampling은 Noise Contrastive Estimation(NCE)의 형태로 softmax의 log 확률로 근사된다. 새로운 공식은 \(P_{v\cdot}\)분포로 부터 샘플 추출된 \(n_i\) 노드들로 부터 로지스틱 회귀인 sigmoid 함수를 사용해서 목표 노드 v를 구별하는 방식으로 상호작용한다.

   따라서, 모든 노드를 정규화하는 것 대신에 k번 랜덤 “negative samples”인 \(n_i\)를 정규화하는것으로 대체할 수 있다. 이러한 Negative sampling은 중첩된 summation을 제거하여 빠르게 계산할 수 있도록 도와준다.

   k개의 negative 노드 \(n_i\) sample은 각 노드를 선택할 확률을 가지고 있고, degree에 비례\(_{proportional}\)한다. 이에 관하여 k는 아래와 같이 두가지를 고려해야한다.

   1. robust estimates보다 더 높은 k를 지정해야한다.
   2. 경험적으로 부정적인 결과가 나오는 5-20 보다 높은 k를 지정해야한다.

   어떻게 최적화(값을 최소화)해야 할까?

   경사하강법\(_{Gradient-Descent}\)을 통해 \(\mathcal{L}\)을 아래와 같은 방법으로 최소화할 수 있다.

   • Initialize $z_u$ for all nodes $u$ randomly in the range [0, 1].
   • While not converged:
     • For each node $u$:
       • Compute the derivative: \(\frac{\partial\mathcal{L}}{\partial z_u}\)
       • Update \(z_u\): \(z_u \leftarrow z_u - \eta \cdot \frac{\partial\mathcal{L}}{\partial z_u}\)

4. Stochastic Gradient Descent

모든 샘플에 대한 경사를 평가하는 것 대신에 개별적인 훈련 샘플을 평가한다.

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

• Initialize $z_u$ for all nodes $u$ randomly in the range [0, 1].
• While not converged:
  • Compute the derivative: \(\frac{\partial\mathcal{L}^{(u)}}{\partial z_v}\)를 계산한다.
  • Update \(z_u\): \(\leftarrow z_v - \eta\frac{\partial\mathcal{L}^{(u)}}{\partial z_v}\)

여기까지 우리는 무작위 보행 전략 R이 주어졌을때 임베딩을 어떻게 최적화하는지 보았다. 그렇다면 이제는 무작위 보행을 수행하기 위해 어떤 전략 R을 사용해야하는 지 알아보자. 가장 간단한 방법으로 DeepWalk³가 있지만 유사성 개념이 너무 제한적이라는 문제 또한 존재합니다. 그렇다면 어떻게 일반화 해야할까요?

III. Node2vec

그래프 임베딩과 같은 목표를 가지고 해당 목표를 Downsteram prediction 작업과 개별적인 최대 우도 최적화 문제로 생각합니다.

Node2vec⁴의 주된 개념은 노드 u의 이웃 네트워크 \(N_R(u)\)가 부유한 노드 임베딩으로 이끌것이라는 유연한 생각입니다. 편향된 2nd order 무작위 보행 R을 발전시켜 u의 이웃 네트워크 \(N_R(u)\)를 생성하는 것입니다.

1. biased walks

아이디어는 네트워크의 local과 global view간의 tarde off가 되는 편향된 무작위 보행을 유연하게 사용하는 것이다.

여기서 노드 u의 이웃들 \(N_R(u)\)를 정하는 두개의 전략을 정의합니다.

1. \(N_{BFS}(u)\); local microscopic view, 주변만 돌음
2. \(N_{DFS}(u)\); global microscopic view, 멀리까지 나아감

2. interpolction BFS, DFS

주된 아이디어는 어디서 걸어왔는지를 기억하는 것이다. 즉, 보행자가 edge(\(s_1\), w)를 가로지르고 w에 있으면 ‘다음에는 어디로 갈 것인가?’에 대한 해답을 찾는 것이다.

편향된 고정된 길이의 무작위 보행 R은 노드 u로 부터 이웃들 \(N_R(u)\)를 생성한다.

따라서 \(N_{R}(u)\)는 편향된 보행을 통해 방문한 노드들이다.

Figure 7 : R-nd. 보행자는 edge(\(s_1\), w)를 가로지르고\(_{traversed}\), 현재 w에 있으며 s3로 갈 확률은 1/q이고, s1은 1/p, s2는 1이다.

\[w = \begin{matrix} s1 \\ s2 \\ s3 \end{matrix} = \begin{matrix} 1/p \\ 1 \\ 1/q \end{matrix}\]

아래와 같은 파라미터가 필요하며 unnormalized된 모델의 transition 확률들이다.

• p : return parameter; 이전 노드에서 다시 가져오는 노드
• q : in-out parameter; outward(DFS) vs inward(BFS)로 q는 “ratio”이다.

Node2vec Algorithm

1. 무작위 보행 확률을 계산한다
2. 노드 u에서 시작하는 l 길이의 무작위 보행을 r번 시뮬레이션한다
3. node2vec 목적함수를 확률적경사하강법을 통해 최적화한다.

해당 알고리즘의 시간복잡도는 선형적이고 세 단계모두 개별적으로 병렬화가능하다. 이외에도 임베딩 목적을 공유하는 다양한 랜덤워크가 존재⁵하고, 노드 유사도에 관한 다양한 개념(나이브, 이웃 overlap, 무작위 보행)들이 존재한다.

그러면 이중에 어떤 방법을 사용해야할까? 모든 경우에 성공적인 하나의 방법은 없다.
그러나 무작위 보행이 대체적으로 더 효과적⁶이라고 하고, 일반적으로는 적용하고자 하는 것에 유사도를 맞춰서 선택해야한다.

IV. Embedding Entire Graphs

부분그래프나 전체 그래프 G를 \(z_G\)로 임베딩하는 것을 목표로 한다.

Figure 8 : Embedding Graphs

그래프를 임베딩하는 세가지 접근밥을 아래와 같이 소개한다.

1. Approach 1

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

간단하지만 효과적인 접근법으로 (sub)graph G들의 노드 임베딩을 모두 더하거나 평균하는 방법이다.
“Convolutional Networks on Graphs for Learning Molecular Fingerprints, Duvenaud et al., 2016”에서 그들의 그래프 구조에 기반한 원자들\(_{molecules}\)을 분류하는데 사용되었다.

2. Approach 2

Figure 9 : virtual node; generate virtual super-node on (sub)graph

“virtual node”로 (sub)graph를 표현하는데 정규 그래프 임베딩 기법을 사용하고, (sub)graph에 걸쳐있는 가상의 super-node를 만들고 그 노드를 임베딩한다.“Gated Graph Sequence Neural Networks, Li et al., 2016”에서 부분 그래프 임베딩을 하는 일반적인 기술로 제안하였다.

3. Approach 3

Anonymous Walk⁷으로 무작위 보행을 통해 우리가 처음 방문한 노드의 인덱스들의 상태를 익명 보행이라고 한다.

이러한 익명 보행은 지수적으로 증가하는데 쉽게 사용하기 위해서는 l번째 익명 보행 \(w_i\)을 시뮬레이션하고 기록하여 확률 분포의 그래프로 표현해야한다.

Figure 10 : 익명 보행의 독립적인 m개의 집합을 생성하는데 필요한 횟수, \(\epsilon\) 보다 적은 확률의 오차와 \(\delta\)보다 작은 분포를 원한다.

이러한 익명 보행 방법은 각 보행을 몇번 발생했는지 빈도를 간단하게 표현하는 Random-Walk보다 익명 보행 \(w_i\)의 임베딩 \(z_i\)를 학습하는게 더 좋다.

여기서 보행을 임베딩 하는 방법은 시작 노드 u에서 l 길이의 무작위 보행 T개를 얻은 후 \(\Delta\) 크기의 window에서 상호 발생한 보행을 예측한다.

\[N_R(u) = \{w_1^u,...,w_T^u,\}\]

즉, 다음 보행이 예측되도록 임베딩을 한다.

Figure 12 : \(max\sum^{T-\Delta}_{t=\Delta}logP(w_t|w_{t-\Delta}, ..., w_{t+\Delta}, z_G)\)에서 \(\Delta\)-window size 로 예측 보행을 학습하고, 모든 노드를 합한다.

이렇게 최적화한 그래프 임베딩을 얻어 예측을 하는데 사용한다.

Figure 11 : Anonymous Walk Architecture.

1. ML은 일반적으로 두 부분으로 나뉘어지는데 데이터 처리, 특징 추출, 학습등으로 이루어진 Upstream Processing과 학습된 모델을 실제 목적에 사용하는 Downstream Prediction으로 나뉘어진다. ↩

2. 더 자세한 내용은 word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method에서 설명한다. ↩

3. Perozzi et al. 2014. DeepWalk: Online Learning of Social Representations. KDD ↩

4. Grover et al. 2016. node2vec: Scalable Feature Learning for Networks. KDD. ↩

5. 다른 무작위 보행(Based on node attributes (Dong et al., 2017)., Based on learned weights (Abu-El-Haija et al., 2017)), 대체 최적화 문제(LINE from Tang et al. 2015), 네트워크 전처리(Ribeiro et al. 2017’s struct2vec, Chen et al. 2016’s HARP) ↩

6. E.g., node2vec performs better on node classification while alternative methods perform better on link prediction (Goyal and Ferrara, 2017 survey) ↩

7. Anonymous Walk Embeddings, ICML 2018 ↩