node2vec: Scalable Feature Learning for Networks

[chullhwan-song]

https://cs.stanford.edu/people/jure/pubs/node2vec-kdd16.pdf

[chullhwan-song]

what?

• word2vec는 단어의 연관성에 대한 feature representation
• node2vec는 node와 node 즉, 이들 relation, 연관성(neighborhoods)이 있는 edge를 표현하는 vector representation = Find embedding of nodes to 𝑑-dimensions that preserves similarity
  • word2vec에 대한 응용
• 주의) 구현하기에 open source를 이용할 예정임 > 개념 이해정도만ㅎ

idea

• Learn node embedding such that nearby nodes are close together
  • 한 노드와 가까이에 있는 노드과 함께 embedding 시키는 학습.
• Graph(G) = (V, E) < 이게 input
• , 즉, f 를 학습시키는것.
  • f : feature representation > 현재 노드와 relation(edge)의 관계를 학습시킨 embedding feature.
• 주어진 노드 가 있을때, 가까이에 있는 노드들을 어떻게 정의는
  • 이때, neighbourhood of 𝑢 obtained by some strategy 𝑆 > 어떤 전략?andom walk, BFS vs DFS
  • 우리의 목표는 다음 수식(log-probability)을 Maximize하는 것
    
    
    • f : 노드 u에 대한 feature representation,
  • 이를 조건 독립이라고 가정
    
    
    • 이때 바로의 softmax 수식에 대해 를 SGD로 평가하여 학습.
• 여기서, 어떻게 를 결정(determine) 하느냐가 주어진 소스 node u 의 많은 다른 이웃을 평가하는 문제가 된다. > 그래서 여기서 제안하는것이 무작위(random)으로 이웃을 샘플링하는 법을 제안함. = random walk
• 이웃을 search하는 전통적인 방식에는 BFS vs DFS이 아래에 나와있다.
  
  • Breadth-first Sampling (BFS) :
  • Depth-first Sampling (DFS) :
  • 위의 그림은 일때의 BFS, DFS의 예시이다.
    
• Interpolating BFS and DFS
  • 이 연구에서는 기본적인 방침이 이 두가지를 적절히 섞어가며 이웃을 샘플링한다. 실제로는 그래프에서 벡터의 정보를 넣어야하기 때문에, DFS보다 BFS에 더 weight를 준다.
  • 그러니까? 샘플링한 노드중에서 같은 network에 속하는 노드 또는 네트워크 상에서 같은 역할을 하는 노드끼리 벡터로 나타내어 같은 공간에 가까이 위치하도록 한다(학습시키는)..
    
    
  • 이를 기반으로 다음을 잘 읽어보면 감이..
    
    
    
    
• node2vec algorithm
  1. Simulate 𝑟 random walks of length 𝑙 starting from each node 𝑢
  2. Optimize the node2vec objective using Stochastic Gradient Descent
     

실험