[GNN] Node Embedding 2편 (node2vec)

본 게시글은 Stanford 대학교 Jure Leskovec 교수님의

Stanford CS224W: Machine Learning with Graphs(2021) 강의를 듣고

학습을 목적으로 재구성한 글입니다

스스로 정리한 내용이라 오류가 있을 수 있습니다

 

https://web.stanford.edu/class/cs224w/

 

https://www.youtube.com/watch?v=6g9vtxUmfwM&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=15

---

지난 시간에는 node embedding의 방법으로

random walk를 배웠고

random walk를 고정된 길이로 uniformly 수행하는 것이

deepwalk라는 것을 배웠다

 

이러한 Random walk 실행법을 다르게하고

노드 u의 이웃 노드인 N(u)를 다르게 정의한 것이

node2vec이다

deepwalk와 node2vec은 모두 동일한

node embedding 방법론이다 

 

 

node2vec의 목표는 노드들의 그래프 내 구조가 비슷하면

노드를 벡터 공간에서도 가까이 위치시키는 것이다

 

앞에서도 설명했지만 node2vec과 deepwalk의 차이는

N(u)가 어떻게 정의되는가와

random walk가 어떻게 정의되는가이다

 

 

 

node2vec에서 이웃 노드를 정의하는 방법이다

그래프 탐색 방법에서는 크게 BFS(넓이우선탐색)과 DFS(깊이우선탐색)이 있다

 

 

 

BFS로 이웃 노드를 정의하면

local microscopic view이고

DFS로 이웃 노드를 정의하면

global macroscopic view이다

 

 

 

node2vec에서 random walk를 수행할 떄는

p와 q라는 2개의 파라미터를 사용한다

 

p는 return parameter로 원래 있던 노드로 돌아가는 것을 제어하고

q는 in-out parameter로 낯선 노드로 얼마나 멀리가는지를 제어한다

 

 

 

위 그림처럼 가운데 연두색 노드 w에서 출발해서

왼쪽 아래 노란색 w로 이동했다고 가정해보자

 

그럼 S1은 이웃한 노드이기 때문에 1이 되고

원래 있던 연두색 w로 돌아가는 것은

1/p이 되고

S2, S3는 아직 가보지않은 낯선 노드이기때문에

1/q가 된다

 

1과 1/p, 1/q는 각각 그냥 점수이지 확률이 아니라고한다

p가 크면 돌아갈 확률이 낮아지고 -> DFS

q가 크면 낯선 노드로 갈 확률이 낮아진다고 한다 -> BFS

 

 

 

따라서 위에서 설명한 내용을 정리하면

오른쪽과 같이 w에서 출발해서

target node들과 unnormalized probability를

정리할 수 있다

 

 

 

node2vec algorithm을 정리해보자

 

1. 이전의 deepwalk에서는 1번 과정을

shorted-fix length로 randomly하게 수행했다

하지만 node2vec은 이 과정을

p, q 파라미터를 이용해서 확률을 계산한다

 

이후는 deepwalk와 동일하게

2. l의 lengthfh r random walk를 각 노드 u로부터 수행한 뒤

3. 목적함수를 SGD를 사용해서 최적화한다

 

이러한 방식은 시간복잡도가 선형이며

각각 병렬로 수행할 수 있다

하지만 단점으로는 individually하게

더 큰 embedding을 계산해야하는 점이라고 한다

 

 

 

이외에도 다양한 방식의

random walk ideas들이 존재한다고 한다

 

 

 

그렇다면 우리는 어떤 node embedding 방식을 써야할까?

각 방식들은 저마다의 장단점이 있다

예를 들면 node classification을 수행할 때에는

node2vec이 성능이 좋다고 한다

 

따라서 우리가 수행하고자하는 업무에 따라서

적절한 node embedding 방식을 사용하면 된다