[CS224W] 3. Node Embeddings

Embedding Nodes

graph의 두 node의 similarity가 embedding space에서도 비슷해야한다.

Graph의 두 노드 $u$, $v$가 임베딩 ENC를 통해 embedding space에 매핑된 임베딩벡터를 각가 $\mathbf{z}_u, \mathbf{z}_v$라 하면 ENC($u$) = $\mathbf{z}_u$, ENC($v$) = $\mathbf{z}_v$이다. 이때
\[ \text{similarity}(u, v) \approx \mathbf{z}_v^T \mathbf{z}_u \]
인 ENC()와 similarity()를 정의해야한다.

Concept of Node Embedding

Shallow Encoding

가장 단순한 방법으로 embedding-lookup이다. 즉

\[ \text{ENC}(v) = \mathbf{z}_v = \mathbf{Z} \cdot v \]

$\mathbf{Z} \in \mathbb{R}^{d \times | \mathcal{V} |}$ 임베딩 행렬의 각 열은 node embedding이고 학습 가능하여 최적화 가능하다. $d$는 임베딩 차원이다.

$v \in \mathbb{I}^{| \mathcal{V} |}$ indicator vector는 노드 $v$의 위치를 제외하고 모두 0인 벡터이다.

DeepWalk, node2vec이 이러한 Shallow Encoding 방법을 응용한 방법이다.

 

Decoder는 노드 유사성이 일치하도록 한다. objective는 노드 쌍 $(u, v)$과 $\mathbf{z}_v^T \mathbf{u}$가 최대가 하도록 한다.

 

그렇다면 node similarity를 어떻게 정의할 것인가? (두 노드가 link되어 있는지, neighbor를 공유하는지, structureal role의 유사성 등)

unsupervised/self-supervised 방법으로 node embedding을 학습할 수 있고 이는 task independent하다.

 

Random Walk Approaches for Node Embeddings

$\mathbf{z}_u$: 노드 $u$를 임베딩한 임베딩 벡터(aim to find)

$P(v | \mathbf{z}_u)$: 노드 $u$에서 시작한 random walk가 $v$에 방문할 확률

$\sigma(\mathbf{z})[i] = \cfrac{e^{\mathbf{z}}[i]}{\sum_{j=1}^{K}e^{\mathbf{z}}[j]}$: softmax 함수($K$개의 예측값에 대한)

$S(x) = \cfrac{1}{1 + e^{-x}}$: 시그모이드 함수, S자 모양

 

Random Walk: 그래프와 시작점이 주어지면, random하게 이웃 노드를 선택/방문한다. 방문한 이웃노드에서 또 다시 random하게 이웃노드를 선택/방문한다. 

 

random walk 전략 $R$에 대하여, 노드 $u$에서 출발하여 random walk를 하여 노드 $v$에 방문할 확률을 추정한다. 이 확률을 $P_R(v | u)$라 한다. 두 임베딩 벡터 $\mathbf{z}_i$, $\mathbf{z}_j$의 코사인 유사도를 최대화하는 방향으로 최적화한다.

 

Random Walk의 장점

1. Expressivity - 노드 유사성을 유연하게 정의할 수 있다. 
2. Efficiency - 학습 시 모든 노드 쌍을 고려하지 않고, 한 쌍에 대해 생각하면 된다.

 

Random Walk Optimization

그래프 $G = (V, E)$ 가 주어질 때, 우리는 $d$차원 임베딩 공간으로 매핑할 $f$를 학습할 것이다.

\[ f: u \to \mathbb{R}^d: f(u) = \mathbf{z}_u \]

Log-likelihood objective는

\[ \max_f \sum_{u \in V} \log{P(N_R(u) | \mathbf{z}_u}) \]

$N_R(u)$: 전략 $R$을 적용했을 때, 노드 $u$의 이웃 노드 집합이다.

 

maximum likelihood objective는 아래의 Loss로 작성할 수 있다

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

\[ P(v | \mathbf{z}_u) = \cfrac{\exp(\mathbf{z}_u^T \mathbf{z}_v)}{\sum_{n \in V} \exp{(\mathbf{z}_u^T \mathbf{z}_n })} \]

* Why softmax? $v$가 $n$과 가장 유사도가 높기를 기대하기 때문

 

다 합치면 최소화할 Loss는

\[ \mathcal{L} = \sum_{u \in V} \sum_{v \in N_R(u)} - \log{\left(\cfrac{\exp{(\mathbf{z}_u^T \mathbf{z}_v)}} {\sum_{n \in V} \exp{( \mathbf{z}_u^T \mathbf{z}_n )}} \right)}  \]

그러나 시간복잡도는 $O(|V|^2)$가 소요된다. too expensive! → Negative sampling으로 해결

 

Negative Sampling

모든 노드를 정규하는 것이 시간복잡도를 높이는 주범이다. 

아래 아이디어에 착안하여 $k$개의 negative sample만 정규화를 한다.

\[ \log{\left(\cfrac{\exp{(\mathbf{z}_u^T \mathbf{z}_v)}} {\sum_{n \in V} \exp{( \mathbf{z}_u^T \mathbf{z}_n )}} \right)} \approx \log{\left( \sigma(\mathbf{z}_u^T \mathbf{z}_v) \right)} - \sum_{i=1}^{k} \log{\left( \sigma(\mathbf{z}_u^T \mathbf{z}_{n_i}) \right)}, n_i \sim P_V \]

* $\sigma$는 시그모이드 함수이고, $k$개의 negative nodes인 $n_i$는 random distribution의 sample이다.

$k$가 클 수록 robust한 추정이 가능하지만, 동시에 negative event에 대해 높은 bias를 가질 수 있다.

실제로 $k$의 값은 $5 \sim 20$을 사용한다.

 

Stochastic Gradient Descent

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

에서 이제 $\mathcal{L}$을 어떻게 최적화 할 것인다?

간단한 방법은 Gradient Descent 방법을 이용하는 것이다.

 

Gradient Descent

• 모든 노드 $u$에 대하여 랜덤값으로 초기화 한다. $z_u$
• $z_u \leftarrow z_u - \eta \cfrac{\partial \mathcal{L}}{\partial z_u}$, $\eta$는 learning rate

Stochastic Gradient Descent

모든 샘플들에 대해 gradient를 계산하는 것보다, training sample에 대해 계산하자

• 모든 노드 $u$에 대하여 랜덤값으로 초기화 한다. $z_u$
• $\mathcal{L}^{(u)} = \displaystyle\sum_{v \in N_R(u)} -\log{(P(v|\mathbf{z}_u))}$ 가 수렴할때까지 $z_v \leftarrow z_v - \eta \cfrac{\partial \mathcal{L}^{(u)}}{\partial z_v}$ 반복 

 

node2vec

 RandomWalk는 too constrained하다는 문제가 있다.

BFS는 local microscopic view를 , DFS는 global macroscopic view를 가질 수 있다.

Biased fixed-length random walk R을 정의하자

• $p$: previous node를 return
• $q$: outward와 inward의 비율, 직관적으로는 BFS와 DFS의 비율

Biased Random Walks

walker가 edge ($s_1, w$)를 건너 $w$에 있다고 하자. 이때 다음 노드로 갈 수 있는 곳은?

 

BFS-like walk를 하고싶으면 작은 $p$, DFS-like walk를 하고싶으면 작은 $q$를 적용한다.

1. random walk probability를 계산
2. 각 노드 $u$에 대해, 길이가 $l$인 random walk 시행
3. SGD를 이용하여 node2vec 목적함수 최적화

선형 시간이 소요되며, 위 3개 단계는 각각 parallelizable하다.

Other Random Walk ideas

• Based on node attributes
• Based on learned weights
• Directly optimize based on 1-hop and 2-hop random walk probabilites
• Run random walks on modified versions of the original network

Core Idea

임베딩 공간에 임베딩된 노드의 거리는, 원래 그래프에서의 유사성을 반영할 것이다.

node2vec은 node classification에는 적합하고, 다른 방법들은 link prediction이 더 잘한다.

 

Embedding Entire Graphs