[CS224W] 3.2 Random Walk Approches for Node Embeddings

Notation

• Vector Zu : node u 의 embedding
• prob P(v | Zu) : node u에서 random walk해 v에 visit할 확률
• softmax function : 확률 분포를 return하는 함수
• sigmoid function : 값을 0과 1사이로 변환하는 함수

Random Walk

• some node에서 시작해 무작위로 이동하는 graph 차원의 process
  
• v와 u가 random walk에서 동시에 일어난 확률이 유사도와 근사하게 학습

Why Random Walks?

• u와 v가 동시에 random walk에 등장하면 유사 이웃을 가지고 서로 가까이 있다는 것 (Expressivity)
• 훈련시 모든 노드 쌍을 고려할 필요가 없음 (Efficiency)

• Zu가 주어졌을 때 Random Walk에 나타나는 node의 확률 로그 sum한 값을 maximize

Optimization

1. 짧은 고정된 거리의 random walk를 각 node로 부터 진행
2. 각각 u로 부터 방문한 노드 세트의 확률을 총 합하고 이를 통해 embedding 최적화
3. MLE
   
   최종적으로 다음과 같은 공식
   

• 여기서 MLE 함수 L을 최소화 하는 Z를 찾는 것

• 다만 O(V^2)의 매우 높은 시간 복잡도를 가짐!
  softmax에서 시간이 너무 오래걸리기에

• How to fix?

Negative Sampling

• Softmax 함수에 대한 근사치

• k개 sample을 추출해 sigmoid function을 취하는 것

• 모든 노드에 정규화 하는 것이 아닌, 이웃하지 않은 negative sample을 통해 근사한다는 것

• Negative sample은 degree가 높을 수록 추출될 확률이 높음

• K가 높을수록 강력한 추정치를 구할 수 있으나, higher bias를 일으킬 수 있음

• 5~20이 흔히 선택 됨

• 만약 Node가 100,000개 정도 있다면 매우 efficient한 선택이 될 것

SGD

• optimization은 SGD로 해결 됨
• 기존 GD에서 확률적 방법으로 small batch나 이웃을 사용해 gradient descent 를 수행하는 것

1. 고정된 random walk로 각각 노드마다 이웃 노드 수집
2. Negative SAmpling과 SGD를 통해 최적화

How to Randomg Walk?

• 어떻게 해야 더 Representative 하게 random walk 할 수 있을까?

Node2Vec

• 표현력있는 이웃을 얻을수록 풍부한 node embedding이 가능해짐
• neighborhood Nr(U)가 정의되는 방식만이 deepwalk와 다름

Biased Walks

• Local과 Global하게 탐색하려면 BFS와 DFS가 가능 할 것
  이는 일종의 trade-off
  BFS는 Local한 정보를 제공해주며 DFS는 Global한 정보를 제공
  

• 두 개의 하이퍼파라미터 P와 Q를 지정
  P : 이전 노드로 복귀
  Q : DFS로 나아갈지 BFS로 나아갈지 (BFS와 DFS의 비율)

• 최종적으로 3가지 선택이 가능, 왔던 길로 돌아올 것인가, further move 할 것인가(DFS), 주변을 살펴볼 것인가(BFS)
• Node가 어디서 왔는지 알고 있기에, 2차 RandomWalk라고 Notate
  
• 다음과 같은 확률을 가질 것
• 이를 통해 u 각각 다른 이웃을 가질 것

Summary

1. Compute Random Walk Prob
2. 각 u로부터 random wolk 실시
3. Node2Vec을 통해 SGD

• 선형 복잡도와 3 step 병렬화라는 장점..
• 모든 node에 대해 각각 embedding 해야 한다는 단점
• 이외에도 다른 random walk idea가 존재