node2vec : Scalable Feature Learning for Networks 리뷰

node2Vec.pdf

0.76MB

목적 :

네트워크에 존재하는 노드들을 이용해 예측 작업에 용이하게 하는 것을 목적으로 논문은 전개된다. 네트워크는 상당히 복잡하기 때문에 이것을 저 차원으로 변환한 이후에 다양한 예측 작업을 수행할 수 있게끔 임베딩하는 것이 그 목적이라고 할 수 있다.

 

그러나 임베딩 된 노드들이 놓여 있는 embeding space의 노드들은 기존의 공간인 graph space에서의 노드들 간의 상대적 관계를 임베딩 과정에서 잃으면 안 된다. 이것을 잃게 되면 굳이 알고리즘을 사용해 가면서 해결할 문제가 아니지 않은가. 본논문에서는 이 관계를 이웃(neighborhood)에 입각해 설명하였다. 예를 들어 graph space에서 매우 긴밀히 연결되어 있는 노드들은 embeding space에서도 긴밀한 관계를 가져야 한다는 것이다.

 

문제 :

하지만 graph space에서 긴밀히 연결 되어 있는 노드들을 어떻게 저 차원 공간으로 옮기는 동시에 주변 노드들과의 관계까지 보존할 수 있을까?

 

해결 :

이를 해결하기 위해서는 graph space에서 노드들을 explore해봐야 한다. 여기서 제시하는 방법은 편향된 random walk이다. 나름 목적성을 갖고 움직이는 random walk인 셈이다. 제시하는 random walk는 파라미터에 의해 bias의 정도가 조절되며 이것에 대해서는 뒤에서 더 자세히 다룰 것이다.

 

기대 :

유연하고 효율적인 random walk를 제시하므로써 네트워크의 특징들을 빠르고 정확하게 파악할 수 있게 된다. node2vec은 multi-label classification, link prediction 등에 사용될 수 있고 domain specific 하지 않고 general 한 네트워크에 사용될 수 있다.

 

multi-label classification, link prediction 예시

multi-label classification
하나의 논문은 여러 주제를 다룰 수 있다. 이때 어떤 논문이 어떤 주제들을 다루고 있는지 라벨링 하는 예측 작업.

 

link prediction

sns상에서 두 사용자가 있는데 공통으로 팔로우 하고 있는 공통 친구가 10명이다. 이것을 기반으로 두 사용자를 추천 친구로 제시할 것인지에 대한 예측 작업.

 

semi-supervised learning

소셜 네트워크 network에서의 노드들(유저들)을 2차원 공간으로 임베딩 시켜야 한다고 생각해 보자. 

supervised learning관점에서는 일단 존재하는 데이터에 대해서 어디로 임베딩 될지에 대한 정답을 갖고 있어야 한다. 하지만 우리는 명확한 정답을 찾아가야 하는 것이지 어느 한 노드에 대해서도 어떻게 임베딩 될지 학습 전에는 전혀 모르는 상태이다.

 

unsupervised learning관점에서는 데이터 자체만 던져주고 노드들간의 특징을 알아서 파악하게끔 하기 때문에 우리의 문제 상황에 적합해 보이지만 현존하는 기술들로는 확장 가능한 비지도 학습을 네트워크에 적용시키기 어렵다. 왜냐하면 비지도 학습의 일종인 Principal Component Analysis, Multi-Dimensional Scaling과 그의 확장 모델들은 전체 네트워크에 대한 데이터 matrix가 데이터 특징의 분산이 최대화 되게끔 목적 함수를 최적화시키고 이러한 작업은 매우 무거운 연산을 수반한다.

 

그래서 여기서 제안하는 방법은 stochastic gradient descent(SGD)를 이용한 semi supervised learning이다. 현존 하는 graph에서 특정 길이만큼의 연결되어 있는 노드들을 random walk로 뽑아서 neighbor이라고 군집화 하고(간선으로 이어져 있는 노드들을 뽑았기 때문에 어느 정도 연관성이 있는 노드들임을 미리 알 수 있음) 이 노드 집합을 이용해 목적 함수를 최적화시킨다.  

 

 

Similarities이어서 네트워크에 있는 노드의 군집화 기준에 대해 설명하는데, 그것은 바로 homophily, structural equivalence이다. homophily는 노드들의 유사성, structural equivalence(샘플링 된 노드들끼리 공유하는 이웃이 많을수록 커짐)는 구조적 등가성을 의미한다. 즉 노드들이 강한 연결성을 가질수록 homophily특성이 커지고 반대로 structural equivalence는 강한 연결성을 보이지 않더라도 네트워크 상에서의 구조적 역할이 비슷할 수 있다. 허나 실세계 데이터에서는 두 특성 모두 포함하고 있는 네트워크가 허다하기 때문에 두 특성을 모두 포착하고 그를 토대로 학습할 수 있는 유연한 샘플링 전략이 필요하다. 

 

샘플링 기법

앞서 우리는 두 특성을 포착하기 위해 biased random walk를 실행할 것이다. 여기서 제안한 기법은 Skip-gram model로 부터 강하게 영감을 받았다. Skip-gram model은 NLP에서 특정 단어를 중심으로 window size만큼 주변 단어들을 학습시키는 방법이다. 전체 글에서 국소적인 부분만 학습시키기 때문에 연산량이 획기적으로 줄어든다.

 

예시를 들어 보자. "I am reading a book about computer science."

windo size = 2라고 할 때 book을 기준으로 Skip-gram sampling을 수행 하면 S = {"reading","a","about","computer"}이 수집된다. Windo size 안으로 수집된 데이터들은 "book" 주변에 올 확률이 높다고 학습시키는 것이다. 그렇다면 S에 있는 단어들을 positive, 나머지 단어들을 negative 하다고 매긴 뒤 신경망에 학습시키면 된다. 그런데 여기서 문제는 나머지 단어들이 10만 개, 100만 개 혹은 그 이상이 되면 연산 처리 속도가 급격히 저하될 것이다. 그래서 고안된 방법이 ("book", "reading") 쌍을 positive, 사전에서 랜덤으로 뽑은 단어 여러 개를 negative 하다고 단정 지어버리고 학습시키는 것이다.

 

예를 들어   

("book","reading") -> +

("book","apple")  -> -

("book","hot")  -> -

("book","a")  -> -

 

하지만 "a"는 사실 positive(+)로 학습해야 하는 것 아니냐고 생각할 수 있다. 여기서는 연산의 속도를 위해 approximate 할 뿐이기 때문에 크게 신경 쓰지 않는다.

 

이제 이 아이디어를 네트워크에 적용해보자. 안타깝게도 NLP에서 문장은 linear 하지만 네트워크에서 노드들은 그렇지 않다. 그래서 단어를 노드로 치환해서 생각해 보면 random walk를 이용해 sampling 하면 좋다는 것을 알 수 있다.

 

"특정 단어와 연관성이 높은 단어들은 주변 단어들이다." -> "특정 노드와 연관성이 높은 노드들은 연결 되어 있는 노드들이다."

 

목적 함수:

Random walk를 통해 노드 $u$에 대해 sampling을 진행할 것이고 여기서 수집된 노드들의 집합을 $N_S(u)$(N은 neighbor)라고 하자. 이때 S는 샘플링을 위해 채택된 샘플링 전략이다. 

 

$$\max_f \sum_{u\in V} \log Pr(N_S(u)|f(u))$$

여기서 목적 함수인 $f$는 노드를 입력받았을 때 output으로 임베딩된 벡터를 출력해 주는 목적 함수이다. 

---

 

$$\log Pr(N_S(u)|f(u)) = \prod_{n_i \in N_S(u)} Pr(n_i|f(u))$$

개별 노드는 다른 노드와 독립이라고 가정을 하기 때문에 노드$u$가 N에 얼마나 적합한지 알기 위해 네트워크 안에 들어 있는 노드들과 $u$노드의 유사도의 product로 나타낼 수 있다.

---

$$Pr(n_i|f(u)) = \frac{\exp(f(n_i)\cdot f(u))}{\sum_{v\in V}\exp(f(v)\cdot f(u))}$$

두 노드의 유사도는 네트워크 전체 노드의 임베딩된 스페이스에서의 dot product의 결과에 대한 두 노드의 dot product의 softmax로 얻을 수 있다. 

---

하지만 분모를 계산 하기에는 컴퓨팅 자원이 너무 많이 소모된다. 이 부분에서 앞서 설명한 negative sampling을 사용하면 되는 것이다. 예를 들어 20개의 negative sampling으로 모아진 노드들(이 sampling 집합을 NS라고 하자, 반드시 이 집합에 $u$노드도 포함되어야 한다)이 있다고 할 때  $n_i$이외의 20개의 노드들은 $n$노드와 연관성이 없다고 학습시키는 것이다. 이로써 분모의 softmax 부분의 연산 효율을 획기적으로 향상할 수 있다. 

 

또한 sampling stretegy(S)에 따라 네트워크를 어떤 기준에 따라 임베딩 하고 싶은지 유연하게 설정할 수 있다. 

 

탐색 전략:

앞에서도 계속 설명했듯이 biased random walk을 이용해서 노드 $u$의 이웃들을 sampling할 것이다. 대표적인 탐색 방법은 BFS와 DFS가 있지만 이 둘은 두 가지 특성(homophily, structural equivalence) 중 각각 하나씩만을 위주로 포착할 수 있는 유연하지 못한 알고리즘이다. 

미리 말하고 가자면 BFS는 structural equivalence를, DFS는 homophily를 sampling 특성으로 삼는다. 아마 납득이 가지 않을 것이다. BFS가 노드 주변을 국소적으로 탐색해서 동질성(homophily)을 기준으로 노드들을 모을 거 같은데? 노드의 구조적 역할은 DFS가 더 잘 찾을 거 같은데? 이런 생각들은 위의 그림 때문에 생긴다. 

 

소셜 네트워크를 예시로 들어보자. 한국에 거주하는 K와 일본에 거주하는 J에 대해 BFS 탐색을 해서 나온 결과가 거대한 네트워크라면 그 둘은 인싸(?)라고 볼 수 있는 것이다. K와 J는 일면식도 없지만 비슷한 역할을 하고 있음을 알 수 있다. 반면에 두 노드는 비슷한 특성을 갖고 있기 때문에 연결 되어 있으므로 DFS를 통해 이것을 광범위 하게 측정하고 싶은 것이다. 

 

두 개념 모두 바라보는 관점에 따라 다양한 해석이 가능하지만 전체적인 틀은 위에서 설명한 바와 크게 차이나지 않는다.