[논문 리뷰] node2vec: Scalable feature learning for networks

[원문] Grover, A., & Leskovec, J. (2016, August). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 855-864). ACM.

​

Node2vec 은 Word2vec의 아이디어를 가져왔습니다.

Node2vec의 목적함수는 Word2vec 의 목적함수와 굉장히 유사합니다.

u가 skip-gram 입장에서 중심 노드를 의미하며, N_s(u) 는 노드 u의 이웃 노드 집합입니다.

즉 skip-gram이 중심단어로부터 주변단어가 나올 로그 우도를 최대화하는 것이라면, node2vec 에서는 중심 노드로부터 이웃 노드들이 나올 로그 우도를 최대화 하는 것이라 생각하면 됩니다.

​

node2vec 은 word2vec 과 마찬가지로 두 가지 전제하에 수행됩니다.

첫 번째로, 각 노드간의 조건부 독립이라는 가정입니다.

이 가정하에서, 위 확률은 조건부독립 성질에 의해서 이웃 노드 집합에 있는 모든 노드들의 각각 확률을 곱한 것으로 쪼개질 수 있습니다.

​

두 번째로, A 노드와 B 노드 사이의 관계는 상호 같다는 전제입니다.

이는 Undirected를 의미하는 것으로 저는 해석했습니다.

이러한 전제에 의해서, 두 노드 벡터 사이의 내적으로 표현가능하며, 확률은 sigmoid function에 의해 표현할 수 있게됩니다.

​

이러한 전제 하에서 node2vec의 목적함수는 아래와 같은 식으로 표현됩니다.

이 때, Z_u 는 다음과 같습니다.

​

​

node2vec은 word2vec과 학습 방법이 매우 유사하지만, word2vec은 문장이라는 단어의 sequence를 활용하여 학습합니다.

따라서 node2vec도 node의 sequence 정보가 필요할 수 밖에 없습니다.

​

node2vec은 두 가지 관점에서 이러한 sample sequence를 생성합니다.

바로 Breadth-first Sampling과 Depth-first Sampling 입니다.

 

아래와 같은 그래프가 있다고 가정합시다.1번노드를 Root node로 가정하고, Breadth-first search 를 수...

blog.naver.com

위 논문에서는 BFS sampling 을 우선시 하여 학습하면, Structural equivalence라는 관점을 반영할 수 있다고 합니다.

위의 그림은 BFS sampling을 우선시한 결과입니다.

파란색 노드들은 네트워크 구조 관점에서 Bridge 역할을 하는 유사한 노드들로 보입니다.

반면 노란색 노드들은 네트워크 구조 관점에서 적은 연결로 동떨어진 역할을 지닙니다.

이처럼, 네트워크 구조 관점에서 같은 역할을 하는 노드 끼리 뭉치게 됩니다.

node2vec은 이러한 네트워크 구조 관점의 유사성은 기존 방법에서 배제되지만, 이는 중요한 정보라고 강조합니다.

​

반면에 DFS 방식은 homophily 라는 관점을 반영할 수 있다고 합니다.

위 그림처럼 DFS는 가까운 이웃에 높은 유사성을 부여하는 방법입니다.

​

node2vec은 이러한 두 가지 관점을 두 parameter : p (Return parameter), q (In-out parameter) 를 사용해 조정합니다.

​

다시 돌아와서, 노드 sequence가 sampling 되는 과정을 자세히 들여다보겠습니다.

큰 틀은 위와 같습니다.

i-1 sequence에 v라는 노드가 sampling 되었습니다.

우리는 다음 sequence인 i 번째 노드 x를 sampling 해야 합니다.

(v,x) in E : 는 x가 v의 이웃 노드임을 의미하기 때문에, 이웃 노드에 한해서만 확률을 가지게 됩니다.

보통 pi_v,r 은 노드 v와 r 사이의 edge weight 값을 가집니다. Z는 Normalize 상수입니다.

​

하지만 위의 방법은 본 논문의 관점을 반영하기에 한계가 있다고 합니다.

따라서 node2vec에서는 2nd order random walk 방법을 제안합니다.

논문에는 위와 같은 부분에 설명되어 있습니다.

t 노드에서 2-nd random walk를 진행할 때, 첫번째로 v라는 노드에 가게 되었습니다.

이 때, 두번째 방향으로 t로 다시 돌아오거나, x1, x2, x3로 가게될 수 있습니다.

t로 돌아오는 경우는 d(t,t)=0, x1로 가는 경우는 d(t,x1)=1, x2로 가는 경우는 d(t,x2)=2, x3로 가는 경우는 d(t,x3)=2 를 만족합니다.

즉 p는 t로 되돌아오는 경우를 control 하고, q는 t에서 멀어지는 방향으로 갈 확률을 control 합니다.

역수로 계산되는 p가 작거나 q가 커질경우 sampling이 근처 노드에서만 맴돌도록 이루어지고, 반대의 경우 멀리 있는 노드로 뻗어나가는 식으로 sampling이 이루어집니다.

​

따라서 p와 q의 설정에 따라 node2vec은 다른 결과를 반환합니다.