<aside> 💡 프로젝트를 위해 공부했던 Node2Vec 에 대해 정리하고자 한다. 이번 포스팅은 'Node2Vec : Scalable Feautre Learning for Networks' 논문의 내용을 바탕으로 참고 자료와 함께 정리한 내용이다.

</aside>

1. introduction

• ‘DeepWalk’ 와 같이 word2vec 방식을 graph representation 접목한 방법론
• graph 에서는 선형적으로 표현이 되어 있지 않아, 이를 표현해주는 방법이 필요로한데 **‘DeepWalk’ 에서는 random walk sampling을 통해 이를 부여**함
• Node2Vec에서는 선형적 표현을 위해 DFS(Depth-First Search), BFS(Breadth-First Search) 활용

2. Feature Learning framework

• sampling 방식에 따라 node vector representation 이 달라짐

• BFS(Breadth-First Search) sampling
• DFS(Depth-First Search) sampling

2.1 Add Bais Random Walk

• 본 논문에서 BFS와 DFS를 원할하게 보간하는 flexible neighborhood sampling strategy 방법은 제안

$$ RandomWalk= P(c_i=x\,|\,c_{i-1}=u)= \begin{cases} \frac{\pi_{ux}}{Z}\;\;\; if \;u,x \in E \\ 0 \;\; otherwise \\ \end{cases} $$

• $\pi_{ux}$ : unnormalized transition probability between nodes v and x
• $Z$ : normalizing constant
• RandomWalk에 bais 주는 가장 간단한 방법은 $\pi_{vx} = w\pi_{vx}$ 기반으로 다음 node를 sampling 하는 방법
• 이러한 방식은 다양한 neighborhood node search 어려우며, network 구조를 설명하기 충분하지 못함
• 추가적으로 BFS, DFS 각각은 구조적 동질설, 동등성에 적합한 극단적 sampling 방식으로 두가지 특성 모두 나타나는 현실의 문제에 단적으로 사용하기 힘듦

2.2 Node2Vec

• 본 논문에서는 Biased 2nd-order random walk 를 사용 (edge to edge method)