<aside> 💡 프로젝트를 위해 공부했던 DeepWalk 에 대해 정리하고자 한다. 이번 포스팅은 DeepWalk로 불리는 'Online Learning of Social Representations' 논문의 내용을 바탕으로 참고 자료와 함께 다시 정리한 내용이다.

</aside>

0. Preliminaries

• Random walk
• Word2Vec - SkipGram
• Graph Embedding

1. introduction

• short random-walk 를 통해 graph node의 social representations을 학습하는 방법 제안
• social interactions를 잠제 공간표현으로 학습 하는 방법 (graph info를 입력으로 받아 latent representation을 output)

2. Method

• graph($G$) 에서 random walk 기반으로 sampling ($W_{v_i}$)
• 최대 길이($t$)에 도달할 때까지 마지막으로 방문한 node의에서 균일하게 sampling
• center node sequence (target)가 주어졌을때 node sequence (random walk output) 가 최대화 되는 방향으로 weight update (optimization)

$$ Pr(W_{v_i}\;|\;\Phi(W_{v_1}),\,\Phi(W_{v_2})\,,\,\Phi(W_{v_2})\,,\, \dots\,,\,,\,\Phi(W_{v_{i-1}})) $$

$$ Hierarchical\,Softmax = Pr(u_k\,|\,\Phi(v_j))=\Pi^{\lceil log|v| \rceil}_{l=1}Pr(b_l\,|\,\Phi(v_j)) $$

3. Implementation

class DeepWalk :
    def __init__(self, G, num_walks, walk_length) :
        import random
        from gensim.models import Word2Vec
        self.walks = []

        for i in range(num_walks) :
            for node in G.nodes() :
                walk = [node]

                for j in range(walk_length) :
                    neighbors = list(G.neighbors(walk[-1]))

                    if len(neighbors) > 0 :
                        walk.append(neighbors[random.randint(0, len(neighbors) -1)])
                        self.walks.append(walk)

        model = Word2Vec(self.walks, vector_size = 2, window = 5, min_count = 1, sg = 1, workers = 2)
        self.ne = {node : model.wv[node].tolist() for node in G.nodes()}
        self._get = {"walks" : self.walks, "node_embedding" : self.ne}

    def __len__(self) :
        return len(self.ne)

    def __getitem__(self, item) :
        return self._get[item]

3. reference

[0] DeepWalk : Online Learning of Social Representations