[DeepWalk]DeepWalk: Online Learning of Social Representations(KDD’14)

Random Walks

• 특정 node를 기준으로 이름처럼 정말 random하게 돌아다니는 방법이다. Graph는 node들과 이를 연결하는 link들이 존재하는데, 특정 node에서 시작하여 link로 연결된 node들을 uniform distribution에 기반하여 돌아다닌다.(i.e. 주변 node들을 같은 확률로 돌아다닌다.)
• 이렇게하여 사전에 설정해둔 hyper-parameter에 따라, node마다 walk length $t$개만큼의 Node들을 traverse하고, 이를 $\gamma$번 반복하여 $\gamma$개의 walk들을 생성한다.

Skip Gram

• Skip Gram은 NLP model에서 매우 유명한 model인 Word2Vec(정리 잘 된 blog)에서 제안한 방법이다. 하나의 단어를 embedding 하려고 할 때, 해당 단어의 앞뒤로 window size $w$만큼씩의 단어를 함께 고려한다. 이때 window에 속하는 단어들로 중심단어를 학습하면 CBOW라는 방법이 되고, 중심단어로 window의 단어들을 학습시킨다면 Skip Gram이 된다. 보통 Skip Gram은 같은 data를 사용하더라도 CBOW보다 단어당 학습되는 횟수가 많아 성능이 더 좋다고 한다.

• 위 내용을 loss function으로 만들어 수식으로 적으면 다음과 같다.
  $L = -\sum_{u \in V}\sum_{v \in N(u)}P(v|z_u)$($u$는 주어진 data에서 임의의 node, $N(u)$는 node $u$의 neighbors를 나타냄.(skip gram에선 window size에 드는 단어들) $z_u$는 node $u$의 embedding vector)
  이를 풀어서 해석하면 다음과 같다. 모든 node $u$에 대해, 각 node $u$의 neighbors인 node $v$에 대하여, node $$ $u$의 embedding이 주어졌을 때 node $v$가 나타날 확률의 total summation이다. 즉, 특정 node $u$가 주어졌을 때, $u$의 neighbor인 node $v$가 같이 나타날 확률을 높이는 방향으로(embedding의 관점에서 보자면 vector가 유사하게 되도록) 학습이 진행된다.

• Loss function에서 확률은 다음과 같이 다시 쓸 수 있다.
  $P(v|z_u) = log(softmax) = log({exp(z_u^Tz_v) \over \Sigma_{n \in S} exp(z_u^Tz_v)})$
  확률은 softmax함수에 log를 취한 값을 사용한다. 이때 softmax 함수의 분모 부분에 negative sampling이라는 약간의 trick이 들어간다. 원래대로라면 분모에 $z_u$의 모든 node들에 대한 inner product이 들어가야한다. 하지만 node의 갯수가 많아질수록 이는 점점 computational cost가 기하급수적으로 늘어나게 된다. 이를 해결하기 위해 node $v$에 해당되지 않는 node들의 집합 $S$에서 k개의 sample을 임의대로 뽑아 분모로 approximation하여 사용한다. 이를 negative sampling이라고 한다.

• 위와 같이 DeepWalk model은 Random Walk을 통해 특정 node의 random variable인 Walk들을 만들어내고, 이를 기반으로 하여 skip gram을 사용하여 각 embedding vector들을 update하는 방식으로 학습을 진행한다.(위의 notation들 중 특히 Skip Gram 설명부분은 상당부분 원문 paper와 다르다. 보다 가독성이 좋고 이해하기 쉬운 CS224W에서의 notation을 참조하여 기술하였음을 알린다.)

• 장점:

  1. data가 상당히 sparse한 경우, graph data로 취급하여 embedding을 할 수 있다.(다만 관계성이 필요)
  2. node의 label 혹은 feature information없이도 embedding을 할 수 있다.
  3. graph의 일부 data들이 변경되었을 경우, 전체 data에 대한 re-computaion을 할 필요없이 해당되는 부분만 다시 학습시켜주면된다.(특정 Node와 그 Neighbor들)

• 단점:

  1. 2번의 반대급부로 node의 label을 사용하는 semi-supervised learning이 되지 않고, feature information도 반영이 되지 않는다.
  2. Random Walk을 할 때 특정 node에겐 중요한 neighbor과 중요하지 않은 neighbor가 있을 텐데 이를 구분하지 않고 똑같은 확률로 random walk이 진행된다.