DeepWalk: Online Learning of Social Representations

1 deepwalk : Online Learning of Social Representations Bryan Perozzi Rami Al-Rfou Steven Skiena Stony Brook University Stony Brook University Stony Brook University Department of Computer Department of Computer Department of Computer Science Science Science {bperozzi, ralrfou, 112. 2. ABSTRACT 222. 2. 118. 8. 6. 117. 7 14 20 5. 1 22. 31 7 6. 10 18. We present deepwalk , a novel approach for Learning latent 115. 5. 221. 1. 331. 1. 220. 0. 2. 1. 111. 1. 7. 21. 15. 19. 23. 29. 9. 4 2 8. 12. 11. 16 3 17. Representations of vertices in a network. These latent rep- 116. 223. 3. 6. 333. 3. 9. 114. 4 8. 5. 33. 3 42 8. 32. 13. 4 27. 334. 4 resentations encode Social relations in a continuous vector 119. 9. 110. 0. 3. 113. 3. 30. 24. space, which is easily exploited by statistical models. Deep- 227. 7. 330. 0. 224. 4. 229. 9. 332. 2. 228. 8. Walk generalizes recent advancements in language modeling 26.}

2 25. and unsupervised feature Learning (or deep Learning ) from 226. 6. 225. 5. sequences of words to graphs. (a) Input: Karate Graph (b) Output: Representation deepwalk uses local information obtained from truncated random walks to learn latent Representations by treating Figure 1: Our proposed method learns a latent space repre- walks as the equivalent of sentences. We demonstrate Deep- sentation of Social interactions in Rd . The learned represen- Walk's latent Representations on several multi-label network tation encodes community structure so it can be easily ex- classification tasks for Social networks such as BlogCatalog, ploited by standard classification methods. Here, our method Flickr, and YouTube. Our results show that deepwalk is used on Zachary's Karate network [44] to generate a la- outperforms challenging baselines which are allowed a global tent representation in R2.

3 Note the correspondence between view of the network, especially in the presence of missing community structure in the input graph and the embedding. information. deepwalk 's Representations can provide F1 Vertex colors represent a modularity-based clustering of the scores up to 10% higher than competing methods when la- input graph. beled data is sparse. In some experiments, deepwalk 's Representations are able to outperform all baseline methods while using 60% less training data. 1. INTRODUCTION. deepwalk is also scalable. It is an Online Learning algo- The sparsity of a network representation is both a strength rithm which builds useful incremental results, and is trivially and a weakness. Sparsity enables the design of efficient dis- parallelizable. These qualities make it suitable for a broad crete algorithms, but can make it harder to generalize in class of real world applications such as network classification, statistical Learning .

4 Machine Learning applications in net- and anomaly detection. works (such as network classification [16, 37], content rec- ommendation [12], anomaly detection [6], and missing link Categories and Subject Descriptors prediction [23]) must be able to deal with this sparsity in [Database Management]: Database Applications - order to survive. Data Mining; [Artificial Intelligence]: Learning ; In this paper we introduce deep Learning (unsupervised [Pattern Recognition]: Model - Statistical feature Learning ) [3] techniques, which have proven successful in natural language processing, into network analysis for the Keywords first time. We develop an algorithm ( deepwalk ) that learns Social Representations of a graph's vertices, by modeling a Social networks; deep Learning ; latent Representations ; learn - stream of short random walks. Social Representations are ing with partial labels; network classification; Online Learning latent features of the vertices that capture neighborhood similarity and community membership.

5 These latent rep- resentations encode Social relations in a continuous vector space with a relatively small number of dimensions. Deep- Permission to make digital or hard copies of all or part of this work for personal or Walk generalizes neural language models to process a special classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation language composed of a set of randomly-generated walks. on the first page. Copyrights for components of this work owned by others than the These neural language models have been used to capture the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or semantic and syntactic structure of human language [7], and republish, to post on servers or to redistribute to lists, requires prior specific permission even logical analogies [29].

6 And/or a fee. Request permissions from deepwalk takes a graph as input and produces a latent KDD'14, August 24 27, 2014, New York, NY, USA. representation as an output. The result of applying our Copyright is held by the owner/author(s). Publication rights licensed to ACM. ACM 978-1-4503-2956-9/14/08 ..$ method to the well-studied Karate network is shown in Fig- ure 1. The graph, as typically presented by force-directed layouts, is shown in Figure 1a. Figure 1b shows the output the labels set Y. In our case, we can utilize the significant of our method with 2 latent dimensions. Beyond the striking information about the dependence of the examples embedded similarity, we note that linearly separable portions of (1b) cor- in the structure of G to achieve superior performance. respond to clusters found through modularity maximization In the literature, this is known as the relational classifica- in the input graph (1a) (shown as vertex colors).

7 Tion (or the collective classification problem [37]). Traditional To demonstrate deepwalk 's potential in real world sce- approaches to relational classification pose the problem as narios, we evaluate its performance on challenging multi-label an inference in an undirected Markov network, and then network classification problems in large heterogeneous graphs. use iterative approximate inference algorithms (such as the In the relational classification problem, the links between iterative classification algorithm [32], Gibbs Sampling [15], or feature vectors violate the traditional assumption. Tech- label relaxation [19]) to compute the posterior distribution niques to address this problem typically use approximate of labels given the network structure. inference techniques [32] to leverage the dependency informa- We propose a different approach to capture the network tion to improve classification results.

8 We distance ourselves topology information. Instead of mixing the label space as from these approaches by Learning label-independent repre- part of the feature space, we propose an unsupervised method sentations of the graph. Our representation quality is not which learns features that capture the graph structure inde- influenced by the choice of labeled vertices, so they can be pendent of the labels' distribution. shared among tasks. This separation between the structural representation and deepwalk outperforms other latent representation meth- the labeling task avoids cascading errors, which can occur in ods for creating Social dimensions [39, 41], especially when iterative methods [34]. Moreover, the same representation labeled nodes are scarce. Strong performance with our repre- can be used for multiple classification problems concerning sentations is possible with very simple linear classifiers ( that network.)

9 Logistic regression). Our Representations are general, and Our goal is to learn XE R|V | d , where d is small number can be combined with any classification method (including of latent dimensions. These low-dimensional Representations iterative inference methods). deepwalk achieves all of that are distributed; meaning each Social phenomena is expressed while being an Online algorithm that is trivially parallelizable. by a subset of the dimensions and each dimension contributes Our contributions are as follows: to a subset of the Social concepts expressed by the space. We introduce deep Learning as a tool to analyze graphs, Using these structural features, we will augment the at- to build robust Representations that are suitable for tributes space to help the classification decision. These statistical modeling. deepwalk learns structural reg- features are general, and can be used with any classification ularities present within short random walks.

10 Algorithm (including iterative methods). However, we be- lieve that the greatest utility of these features is their easy We extensively evaluate our Representations on multi- integration with simple machine Learning algorithms. They label classification tasks on several Social networks. We scale appropriately in real-world networks, as we will show show significantly increased classification performance in Section 6. in the presence of label sparsity, getting improvements 5%-10% of Micro F1 , on the sparsest problems we 3. Learning Social Representations . consider. In some cases, deepwalk 's Representations can outperform its competitors even when given 60% We seek to learn Social Representations with the following less training data. characteristics: Adaptability - Real Social networks are constantly We demonstrate the scalability of our algorithm by evolving; new Social relations should not require repeat- building Representations of web-scale graphs, (such as ing the Learning process all over again.)