[논문 리뷰] DeepWalk: Online Learning of Social Representations

원문 : Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

​

안녕하세요. 이번에 리뷰해볼 paper는 "DeepWalk: Online Learning of Social Representations" 입니다.

이 논문은 Graph를 저차원으로 embedding 하는 아이디어를 최초로 반영한 논문입니다.

​

위와 같은 4개의 Class (색깔)을 가지는 그래프가 있다고 합시다.

DeepWalk 방법론을 사용하여, 각 노드들을 2차원 공간으로 embedding 하면 아래와 같은 결과를 얻을 수 있다고 합니다.

같은 Class는 비슷한 공간에 mapping이 되어 Cluster가 깔끔하게 생성이 될 수 있는 것을 볼 수 있습니다.

​

이렇게 Graph의 노드들을 저차원의 실수 벡터로 embedding 할 수 있다면 큰 메리트가 있습니다.

가장 큰 merit로는 저차원의 벡터들을 각 노드들의 feature를 나타내기 때문에, 이 feature들을 머신러닝의 input으로 사용할 수 있다는 것입니다. 이를 활용해, 비정상적인 노드를 발견하는 Anomaly detection, Class를 예측하는 Class prediction, 비슷한 특징을 가지는 노드를 묶는 Clustering, 마지막으로 두 노드들이 다음 시점에서 연결이 될 것인지를 예측하는 Link prediction의 성능을 좀 더 향상시킬 수 있습니다.

​

DeepWalk 는 Word2vec의 아이디어를 그래프에 적용시켰습니다.

Word2vec의 Skipgram 방법론은 아래 링크에 잘 설명되어 있습니다.

​

https://blog.naver.com/ollehw/221750003632

 

 

​

해당 Paper에서 도식화한 큰 알고리즘의 틀은 다음과 같습니다.

사전에 정해주어야할 parameter로 window size, embedding size, walks per vertax, walk length가 있습니다.

앞의 window size, embedding size 는 word2vec에서와 같은 의미로 사용됩니다.

walks per vertax는 iteration을 의미합니다.

예를 들어서 그래프에 10개의 노드가 있다면, walks per vertax = 3 은 10개의 노드를 각각 3번씩 사용하는 것을 의미합니다.

walk length에 대해서는 이후에 설명드리도록 하겠습니다.

​

Algorithm 2. 에 Binary tree 를 구성한다고 나옵니다.

이는 Hierarchical softmax를 의미합니다.

https://blog.naver.com/ollehw/221750182388

 

그리고 Algorithm 3.에 미리 설정한 walks per vertax의 횟수만큼 iteration이 설정됩니다.

Algorithm 4. 에서 전체 노드들을 랜덤하게 섞습니다.

저희는 간단하게 노드가 8개 (v1, ... , v8) 뿐이라고 가정하겠습니다.

Algorithm 5. 에서 8개의 노드중에서 섞인 순서대로 학습이 진행됩니다. ( 예를 들어, 3 - 1 - 2 - 5 - 8 - 4 - 6 - 7 )

Algorithm 6. 부터 중요합니다.

우선 첫 번째 v3 노드에 대해서 t (walk length) step 만큼 random walk를 진행합니다.

그래프에서 random walk는 예를 들어서, v3 가 v2, v7, v8 과 연결이 되어 있다면, 각각 경로로 이동할 확률이 1/3 의 확률을 가진다고 가정하며, 랜덤하게 움직이는 것입니다.

t = 5 로 설정했다면, 같은 원리로 v3 - v7 - v2 - v4 - v1 이 될 수 있은 것이지요.

v3 - v7 - v2 - v4 - v1 의 sequence 를 저희는 word2vec 의 문장으로 여길 수 있습니다.

Algorithm 7. 는 이제 이 5개의 sequence 내에서 word2vec 을 학습하는 것을 의미합니다.

이 학습 과정에서 사전에 정한 window size, embedding size 가 사용됩니다.

​