DeepWalk: Online Learning of Social Representations
Bryan Perozzi

Rami Al-Rfou

Steven Skiena

Stony Brook University
Department of Computer
Science

Stony Brook University
Department of Computer
Science

Stony Brook University
Department of Computer
Science{bperozzi, ralrfou, skiena}@cs.stonybrook.edu
112
2

ABSTRACT
We present DeepWalk, a novel approach for learning latent
representations of vertices in a network. These latent representations encode social relations in a continuous vector
space, which is easily exploited by statistical models. DeepWalk generalizes recent advancements in language modelingand unsupervised feature learning (or deep learning) fromsequences of words to graphs.
DeepWalk uses local information obtained from truncatedrandom walks to learn latent representations by treating
walks as the equivalent of sentences. We demonstrate DeepWalk’s latent representations on several multi-label networkclassification tasks for social networks such as BlogCatalog,
Flickr, and YouTube. Our results show that DeepWalk
outperforms challenging baselines which are allowed a global
view of the network, especially in the presence of missing
information. DeepWalk’s representations can provide F1
scores up to 10% higher than competing methods when labeled data is sparse. In some experiments, DeepWalk’s
representations are able to outperform all baseline methods
while using 60% less training data.
DeepWalk is also scalable. It is an online learning algorithm which builds useful incremental results, and is triviallyparallelizable. These qualities make it suitable for a broadclass of real world applications such as network classification,
and anomaly detection.

Categories and Subject Descriptors
H.2.8 [Database Management]: Database Applications Data Mining; I.2.6 [Artificial Intelligence]: Learning; I.5.1[Pattern Recognition]: Model - Statistical

Keywords
social networks; deep learning; latent representations; learning with partial labels; network classification; online learning

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
KDD’14, August 24–27, 2014, New York, NY, USA.
Copyright is held by the owner/author(s). Publication rights licensed to ACM.
ACM 978-1-4503-2956-9/14/08 ...$15.00.
http://dx.doi.org/10.1145/2623330.2623732

222
2
118
8

221
1
115
5

0.6
7

2

14

117
7

6
111
1

220
0

331
1

5

9
114
4

223
3

8

16

15

119
9

3

4

7

18

1.2

4

19

6

2 8
12

29

1.0

17

3

33

13
32

3 42 8

27
24
30

113
3

110
0

22

9

23

333
3
334
4

5
1

11
21

1
116
6

20

31
10

0.8

1.4
332
2

330
0

229
9

227
7

1.6

224
4

228
8

26

1.8
1.0
226
6

25

0.5

0.0

0.5

1.0

1.5

2.0

2.5

225
5

(a) Input: Karate Graph(b) Output: Representation

Figure 1: Our proposed method learns a latent space representation of social interactions in Rd . The learned representation encodes community structure so it can be easily exploited by standard classification methods. Here, our method
is used on Zachary’s Karate network [44] to generate a latent representation in R2 . Note the correspondence between
community structure in the input graph and the embedding.
Vertex colors represent a modularity-based clustering of the
input graph.

1.

INTRODUCTION

The sparsity of a network representation is both a strengthand a weakness. Sparsity enables the design of efficient discrete algorithms, but can make it harder to generalize instatistical learning. Machine learning applications in networks (such as network classification [16, 37], content recommendation [12], anomaly detection [6], and missing link
prediction [23]) must be able to deal with this sparsity inorder to survive.
In this paper we introduce deep learning (unsupervised
feature learning) [3] techniques, which have proven successful
in natural language processing, into network analysis for the
first time. We develop an algorithm (DeepWalk) that learnssocial representations of a graph’s vertices, by modeling a
stream of short random walks. Social representations arelatent features of the vertices that capture neighborhood
similarity and community membership. These latent representations encode social relations in a continuous vector
space with a relatively small number of dimensions. DeepWalk generalizes neural language models to process a special
language composed of a set of randomly-generated walks.
These neural language models have been used to capture thesemantic and syntactic structure of human language [7], andeven logical analogies [29].
DeepWalk takes a graph as input and produces a latent
representation as an output. The result of applying our
method to the well-studied Karate network is shown in Figure 1. The graph, as typically presented by force-directedlayouts, is shown in Figure 1a. Figure 1b shows the output
of our method with 2 latent dimensions. Beyond the striking
similarity, we note that linearly separable portions of (1b) correspond to clusters found through modularity maximizationin the input graph (1a) (shown as vertex colors).
To demonstrate DeepWalk’s potential in real world scenarios, we evaluate its performance on challenging multi-label
network classification problems in large heterogeneous graphs.
In the relational classification problem, the links between
feature vectors violate the traditional i.i.d. assumption. Techniques to address this problem typically use approximate
inference techniques [32] to leverage the dependency information to improve classification results. We distance ourselvesfrom these approaches by learning label-independent representations of the graph. Our representation quality is not
influenced by the choice of labeled vertices, so they can beshared among tasks.
DeepWalk outperforms other latent representation methods for creating social dimensions [39, 41], especially whenlabeled nodes are scarce. Strong performance with our representations is possible with very simple linear classifiers (e.g.
logistic regression). Our representations are general, andcan be combined with any classification method (including
iterative inference methods). DeepWalk achieves all of thatwhile being an online algorithm that is trivially parallelizable.
Our contributions are as follows:• We introduce deep learning as a tool to analyze graphs,
to build robust representations that are suitable forstatistical modeling. DeepWalk learns structural regularities present within short random walks.
• We extensively evaluate our representations on multilabel classification tasks on several social networks. We
show significantly increased classification performancein the presence of label sparsity, getting improvements
5%-10% of Micro F1 , on the sparsest problems weconsider. In some cases, DeepWalk’s representations
can outperform its competitors even when given 60%
less training data.
• We demonstrate the scalability of our algorithm bybuilding representations of web-scale graphs, (such as
YouTube) using a parallel implementation. Moreover,
we describe the minimal changes necessary to build astreaming version of our approach.
The rest of the paper is arranged as follows. In Sections 2
and 3, we discuss the problem formulation of classification indata networks, and how it relates to our work. In Section 4 we
present DeepWalk, our approach for Social Representation
Learning. We outline ours experiments in Section 5, andpresent their results in Section 6. We close with a discussionof related work in Section 7, and our conclusions.

2.

PROBLEM DEFINITION

We consider the problem of classifying members of a social
network into one or more categories. Let G = (V, E), where
V represent the members of the network, E are their connections, E ⊆ (V × V ), and GL = (V, E, X, Y ) is a partiallylabeled social network, with attributes X ∈ R|V |×S where S
is the size of the feature space for each attribute vector, andY ∈ R|V |×|Y| , Y is the set of labels.
In a traditional machine learning classification setting, we
aim to learn a hypothesis H that maps elements of X tothe labels set Y. In our case, we can utilize the significant
information about the dependence of the examples embeddedin the structure of G to achieve superior performance.
In the literature, this is known as the relational classification (or the collective classification problem [37]). Traditional
approaches to relational classification pose the problem as
an inference in an undirected Markov network, and thenuse iterative approximate inference algorithms (such as theiterative classification algorithm [32], Gibbs Sampling [15], orlabel relaxation [19]) to compute the posterior distributionof labels given the network structure.
We propose a different approach to capture the network
topology information. Instead of mixing the label space aspart of the feature space, we propose an unsupervised method
which learns features that capture the graph structure independent of the labels’ distribution.
This separation between the structural representation andthe labeling task avoids cascading errors, which can occur initerative methods [34]. Moreover, the same representation
can be used for multiple classification problems concerningthat network.
Our goal is to learn XE ∈ R|V |×d , where d is small numberof latent dimensions. These low-dimensional representations
are distributed; meaning each social phenomena is expressedby a subset of the dimensions and each dimension contributes
to a subset of the social concepts expressed by the space.
Using these structural features, we will augment the attributes space to help the classification decision. Thesefeatures are general, and can be used with any classification
algorithm (including iterative methods). However, we believe that the greatest utility of these features is their easy
integration with simple machine learning algorithms. They
scale appropriately in real-world networks, as we will showin Section 6.

3.

LEARNING SOCIAL REPRESENTATIONS

We seek to learn social representations with the following
characteristics:• Adaptability - Real social networks are constantly
evolving; new social relations should not require repeating the learning process all over again.
• Community aware - The distance between latentdimensions should represent a metric for evaluatingsocial similarity between the corresponding membersof the network. This allows generalization in networks
with homophily.
• Low dimensional - When labeled data is scarce lowdimensional models generalize better, and speed up
convergence and inference.
• Continuous - We require latent representations tomodel partial community membership in continuous
space. In addition to providing a nuanced view ofcommunity membership, a continuous representation
has smooth decision boundaries between communities
which allows more robust classification.
Our method satisfies these requirements by learning representation for vertices from a stream of short random walks,
using optimization techniques originally designed for language modeling. Here, we review the basics of both random
walks and language modeling, and describe how their combination satisfies our requirements.

FrequencymofmVert
exmOccurrenceminmShort mRandom mWalks
5

10

4

10

3

10

2

10

1

10

0

# of Words

k mofmVert ices

10

10

0

10

1

2

3

4

10
10
10
Vert exmvisit at ionmcount

10

5

10

6

(a) YouTube Social Graph

10

6

10

5

10

4

10

3

10

2

10

1

10

0

3.3

Frequency of Word Occurrence in Wikipedia

10

0

10

1

10

2

3

4

10
10
10
Word mention count

5

10

6

10

7

(b) Wikipedia Article Text

Figure 2: The distribution of vertices appearing in shortrandom walks (2a) follows a power-law, much like the distribution of words in natural language (2b).

3.1

Random Walks

We denote a random walk rooted at vertex vi as Wvi . It is astochastic process with random variables Wv1i , Wv2i , . . . , Wvkisuch that Wvk+1
is a vertex chosen at random from theineighbors of vertex vk . Random walks have been used as asimilarity measure for a variety of problems in content recommendation [12] and community detection [2]. They are also
the foundation of a class of output sensitive algorithms which
use them to compute local community structure informationin time sublinear to the size of the input graph [38].
It is this connection to local structure that motivates us
to use a stream of short random walks as our basic toolfor extracting information from a network. In addition tocapturing community information, using random walks as
the basis for our algorithm gives us two other desirable
properties. First, local exploration is easy to parallelize.
Several random walkers (in different threads, processes, or
machines) can simultaneously explore different parts of thesame graph. Secondly, relying on information obtained fromshort random walks make it possible to accommodate smallchanges in the graph structure without the need for global
recomputation. We can iteratively update the learned modelwith new random walks from the changed region in time
sub-linear to the entire graph.

3.2

Connection: Power laws

Having chosen online random walks as our primitive for
capturing graph structure, we now need a suitable method
to capture this information. If the degree distribution ofa connected graph follows a power law (i.e. scale-free), we
observe that the frequency which vertices appear in the shortrandom walks will also follow a power-law distribution.
Word frequency in natural language follows a similar distribution, and techniques from language modeling account forthis distributional behavior. To emphasize this similarity weshow two different power-law distributions in Figure 2. The
first comes from a series of short random walks on a scale-freegraph, and the second comes from the text of 100,000 articles
from the English Wikipedia.
A core contribution of our work is the idea that techniques
which have been used to model natural language (where thesymbol frequency follows a power law distribution (or Zipf ’slaw )) can be re-purposed to model community structure in
networks. We spend the rest of this section reviewing thegrowing work in language modeling, and transforming it tolearn representations of vertices which satisfy our criteria.

Language Modeling

The goal of language modeling is to estimate the likelihoodof a specific sequence of words appearing in a corpus. Moreformally, given a sequence of words W1n = (w0 , w1 , · · · , wn ),where wi ∈ V (V is the vocabulary), we would like to maximize the Pr(wn |w0 , w1 , · · · , wn−1 ) over all the training corpus. Recent work in representation learning has focusedon using probabilistic neural networks to build general representations of words which extend the scope of language
modeling beyond its original goals.
In this work, we present a generalization of language modeling to explore the graph through a stream of short random
walks. These walks can be thought of as short sentences andphrases in a special language; the direct analog is to estimate
the likelihood of observing vertex vi given all the previous
vertices visited so far in the random walk, i.e.

Pr vi | (v1 , v2 , · · · , vi−1 )(1)
Our goal is to learn a latent representation, not only aprobability distribution of node co-occurrences, and so we
introduce a mapping function Φ : v ∈ V 7→ R|V |×d . This
mapping Φ represents the latent social representation associated with each vertex v in the graph. (In practice, we
represent Φ by a |V | × d matrix of free parameters, which willserve later on as our XE ). The problem then, is to estimate
the likelihood:Pr vi | Φ(v1 ), Φ(v2 ), · · · , Φ(vi−1 )(2)However, as the walk length grows, computing this conditional probability becomes unfeasible.
A recent relaxation in language modeling [27, 28] turns
the prediction problem on its head. First, instead of using
the context to predict a missing word, it uses one word
to predict the context. Secondly, the context is composedof the words appearing to both the right and left of thegiven word. Finally, it removes the ordering constraint on
the problem, instead, requiring the model to maximize theprobability of any word appearing in the context without
the knowledge of its offset from the given word. In terms ofvertex representation modeling, this yields the optimization
problem:minimize − log Pr {vi−w , · · · , vi+w } \ vi | Φ(vi )(3)Φ
We find these relaxations are particularly desirable forsocial representation learning. First, the order independence
assumption better captures a sense of ‘nearness’ that isprovided by random walks. Moreover, this relaxation is quite
useful for speeding up the training time by building small
models as one vertex is given at a time.
Solving the optimization problem from Eq. 3 builds representations that capture the shared similarities in local
graph structure between vertices. Vertices which have similar
neighborhoods will acquire similar representations (encoding
co-citation similarity), allowing generalization on machinelearning tasks.
By combining both truncated random walks and language
models we formulate a method which satisfies all of ourdesired properties. This method generates representationsof social networks that are low-dimensional, and exist in acontinuous vector space. Its representations encode latentforms of community membership, and because the method

Algorithm 1 DeepWalk(G, w, d, γ, t)Input: graph G(V, E)
window size w
embedding size dwalks per vertex γ
walk length t
Output: matrix of vertex representations Φ ∈ R|V |×d
1: Initialization: Sample Φ from U |V |×d
2: Build a binary Tree T from V
3: for i = 0 to γ do
4:
O = Shuffle(V )5:for each vi ∈ O do
6:
Wvi = RandomW alk(G, vi ,t)7:
SkipGram(Φ, Wvi , w)
8:
end for
9: end for

outputs useful intermediate representations, it can adapt tochanging network topology.

Algorithm 2 SkipGram(Φ, Wvi , w)
1: for each vj ∈ Wvi do
2:for each uk ∈ Wvi [j − w : j + w] do
3:J(Φ) = − log Pr(uk | Φ(vj ))∂J4:
Φ = Φ − α ∗ ∂Φ5:
end for
6: end forthese representations in accordance with our objective function in Eq. 3.

4.2.1

SkipGram

SkipGram is a language model that maximizes the cooccurrence probability among the words that appear within
a window, w, in a sentence. It approximates the conditional
probability in Equation 3 using an independence assumption
as the followingi+wYPr {vi−w , · · · , vi+w } \ vi | Φ(vi ) =Pr(vj |Φ(vi ))
j=i−w
j6=i

4.

METHODIn this section we discuss the main components of ouralgorithm. We also present several variants of our approachand discuss their merits.

4.1

Overview

As in any language modeling algorithm, the only required
input is a corpus and a vocabulary V. DeepWalk considers
a set of short truncated random walks its own corpus, andthe graph vertices as its own vocabulary (V = V ). While
it is beneficial to know V and the frequency distribution ofvertices in the random walks ahead of the training, it is notnecessary for the algorithm to work as we will show in 4.2.2.

4.2

Algorithm: DeepWalk

The algorithm consists of two main components; first a
random walk generator, and second, an update procedure.
The random walk generator takes a graph G and samples
uniformly a random vertex vi as the root of the random
walk Wvi . A walk samples uniformly from the neighborsof the last vertex visited until the maximum length (t) isreached. While we set the length of our random walks inthe experiments to be fixed, there is no restriction for the
random walks to be of the same length. These walks could
have restarts (i.e. a teleport probability of returning backto their root), but our preliminary results did not show any
advantage of using restarts. In practice, our implementation
specifies a number of random walks γ of length t to start ateach vertex.
Lines 3-9 in Algorithm 1 shows the core of our approach.
The outer loop specifies the number of times, γ, which weshould start random walks at each vertex. We think of each
iteration as making a ‘pass’ over the data and sample one
walk per node during this pass. At the start of each pass wegenerate a random ordering to traverse the vertices. This
is not strictly required, but is well-known to speed up theconvergence of stochastic gradient descent.
In the inner loop, we iterate over all the vertices of thegraph. For each vertex vi we generate a random walk
|Wvi | = t, and then use it to update our representations(Line 7). We use the SkipGram algorithm [27] to update(4)
Algorithm 2 iterates over all possible collocations in random walk that appear within the window w (lines 1-2). For
each, we map each vertex vj to its current representation
vector Φ(vj ) ∈ Rd (See Figure 3b). Given the representation of vj , we would like to maximize the probability of its
neighbors in the walk (line 3). We can learn such a posterior
distribution using several choices of classifiers. For example, modeling the previous problem using logistic regression
would result in a huge number of labels (that is equal to|V |) which could be in millions or billions. Such models
require vast computational resources which could span awhole cluster of computers [4]. To avoid this necessity andspeed up the training time, we instead use the HierarchicalSoftmax [30, 31] to approximate the probability distribution.

4.2.2

Hierarchical Softmax

Given that uk ∈ V , calculating Pr(uk | Φ(vj )) in line 3
is not feasible. Computing the partition function (normalization factor) is expensive, so instead we will factorize theconditional probability using Hierarchical softmax. We assign
the vertices to the leaves of a binary tree, turning the prediction problem into maximizing the probability of a specificpath in the hierarchy (See Figure 3c). If the path to vertex uk
is identified by a sequence of tree nodes (b0 , b1 , . . . , bdlog |V |e ),(b0 = root, bdlog |V |e = uk ) thendlog |V |ePr(uk | Φ(vj )) =Y

Pr(bl | Φ(vj ))

(5)

l=1

Now, Pr(bl | Φ(vj )) could be modeled by a binary classifierthat is assigned to the parent of the node bl as Equation 6shows,
Pr(bl | Φ(vj ) = 1/(1 + e−Φ(vj )·Ψ(bl ) )(6)where Ψ(bl ) ∈ Rd is the representation assigned to tree node
bl ’s parent. This reduces the computational complexity ofcalculating Pr(uk | Φ(vj )) from O(|V |) to O(log |V |).
We can speed up the training process further, by assigning
shorter paths to the frequent vertices in the random walks.
Huffman coding is used to reduce the access time of frequentelements in the tree.

(a) Random walk generation.

(b) Representation mapping.

(c) Hierarchical Softmax.

Figure 3: Overview of DeepWalk. We slide a window of length 2w + 1 over the random walk Wv4 , mapping the central
vertex v1 to its representation Φ(v1 ). Hierarchical Softmax factors out Pr(v3 | Φ(v1 )) and Pr(v5 | Φ(v1 )) over sequences ofprobability distributions corresponding to the paths starting at the root and ending at v3 and v5 . The representation Φ isupdated to maximize the probability of v1 co-occurring with its context {v3 , v5 }.

4.3

Algorithm Variants

Here we discuss some variants of our proposed method,which we believe may be of interest.

4.4.1

0

BlogCat alog
Flickr

2

-1

2

-2

2

-3

Streaming

One interesting variant of this method is a streaming approach, which could be implemented without knowledge ofthe entire graph. In this variant small walks from the graphare passed directly to the representation learning code, andthe model is updated directly. Some modifications to thelearning process will also be necessary. First, using a decaying learning rate may no longer be desirable as it assumes theknowledge of the total corpus size. Instead, we can initialize

BlogCat alog

0.02

Flickr
0.01

0.00

0.01

0.02

2

0

Parallelizability

As shown in Figure 2 the frequency distribution of vertices
in random walks of social network and words in a language
both follow a power law. This results in a long tail of infrequent vertices, therefore, the updates that affect Φ will besparse in nature. This allows us to use asynchronous versionof stochastic gradient descent (ASGD), in the multi-worker
case. Given that our updates are sparse and we do not acquire a lock to access the model shared parameters, ASGD
will achieve an optimal rate of convergence [36]. While werun experiments on one machine using multiple threads, it
has been demonstrated that this technique is highly scalable,
and can be used in very large scale machine learning [9].
Figure 4 presents the effects of parallelizing DeepWalk. It
shows the speed up in processing BlogCatalog and Flickr
networks is consistent as we increase the number of workers
to 8 (Figure 4a). It also shows that there is no loss of predictive performance relative to the running DeepWalk serially(Figure 4b).

4.4

2

Relat ive Change in Micro F 1

Optimization

The model parameter set is θ = {Φ, Ψ} where the sizeof each is O(d|V |). Stochastic gradient descent (SGD) [5]is used to optimize these parameters (Line 4, Algorithm 2).
The derivatives are estimated using the back-propagation
algorithm. The learning rate α for SGD is initially set to2.5% at the beginning of the training and then decreased
linearly with the number of vertices that are seen so far.

Relat ive Tim e

4.2.3

2

1

2

2

2

3

2

0

2

1

2

2

# of Workers# of Workers(a) Running Time(b) Performance2

3

Figure 4: Effects of parallelizing DeepWalk
the learning rate α to a small constant value. This will takelonger to learn, but may be worth it in some applications.
Second, we cannot necessarily build a tree of parameters any
more. If the cardinality of V is known (or can be bounded),
we can build the Hierarchical Softmax tree for that maximum
value. Vertices can be assigned to one of the remaining leaves
when they are first seen. If we have the ability to estimate
the vertex frequency a priori, we can also still use Huffman
coding to decrease frequent element access times.

4.4.2

Non-random walks

Some graphs are created as a by-product of agents interacting with a sequence of elements (e.g. users’ navigationof pages on a website). When a graph is created by such a
stream of non-random walks, we can use this process to feed
the modeling phase directly. Graphs sampled in this way will
not only capture information related to network structure,
but also to the frequency at which paths are traversed.
In our view, this variant also encompasses language modeling. Sentences can be viewed as purposed walks throughan appropriately designed language network, and language
models like SkipGram are designed to capture this behavior.
This approach can be combined with the streaming variant(Section 4.4.1) to train features on a continually evolving
network without ever explicitly constructing the entire graph.
Maintaining representations with this technique could enableweb-scale classification without the hassles of dealing with aweb-scale graph.

Name
|V |
|E|
|Y|
LabelsBlogCatalog
10,312333,983
39
Interests

Flickr
80,5135,899,882
195
GroupsYouTube1,138,499
2,990,443
47
GroupsTable 1: Graphs used in our experiments.

5.

EXPERIMENTAL DESIGNIn this section we provide an overview of the datasets andmethods which we will use in our experiments. Code anddata to reproduce our results will be available at the firstauthor’s website.1

5.1

Datasets

An overview of the graphs we consider in our experiments
is given in Figure 1.
• BlogCatalog [39] is a network of social relationships
provided by blogger authors. The labels represent the
topic categories provided by the authors.
• Flickr [39] is a network of the contacts between usersof the photo sharing website. The labels represent theinterest groups of the users such as ‘black and whitephotos’.
• YouTube [40] is a social network between users of
the popular video sharing website. The labels here
represent groups of viewers that enjoy common video
genres (e.g. anime and wrestling).

5.2

Baseline Methods

To validate the performance of our approach we compare
it against a number of baselines:• SpectralClustering [41]: This method generates a representation in Rd from the d-smallest eigenvectors ofe the normalized graph Laplacian of G. Utilizing theL,eigenvectors of Le implicitly assumes that graph cuts
will be useful for classification.
• Modularity [39]: This method generates a representation in Rd from the top-d eigenvectors of B, theModularity matrix of G. The eigenvectors of B encode
information about modular graph partitions of G [35].
Using them as features assumes that modular graphpartitions will be useful for classification.
• EdgeCluster [40]: This method uses k-means clustering
to cluster the adjacency matrix of G. Its has been shownto perform comparably to the Modularity method, withthe added advantage of scaling to graphs which are toolarge for spectral decomposition.
• wvRN [25]: The weighted-vote Relational Neighbor isa relational classifier. Given the neighborhood Ni ofvertex vi , wvRN estimates Pr(yi |Ni ) with the (appropriately normalized)
P weighted mean of its neighbors (i.ePr(yi |Ni ) = Z1 vj ∈Ni wij Pr(yj | Nj )). It has shown
surprisingly good performance in real networks, andhas been advocated as a sensible relational classification
baseline [26].
• Majority: This naı̈ve method simply chooses the mostfrequent labels in the training set.
1

http://bit.ly/deepwalk

6.

EXPERIMENTS

In this section we present an experimental analysis of our
method. We thoroughly evaluate it on a number of multilabel classification tasks, and analyze its sensitivity acrossseveral parameters.

6.1

Multi-Label Classification

To facilitate the comparison between our method and therelevant baselines, we use the exact same datasets and experimental procedure as in [39, 40]. Specifically, we randomly
sample a portion (TR ) of the labeled nodes, and use themas training data. The rest of the nodes are used as test. We
repeat this process 10 times, and report the average performance in terms of both Macro-F1 and Micro-F1 . Whenpossible we report the original results [39, 40] here directly.
For all models we use a one-vs-rest logistic regression implemented by LibLinear [11] extended to return the mostprobable labels as in [39]. We present results for DeepWalk with (γ = 80, w = 10, d = 128). The results for(SpectralClustering, Modularity, EdgeCluster) use Tang andLiu’s preferred dimensionality, d = 500.

6.1.1

BlogCatalog

In this experiment we increase the training ratio (TR ) on
the BlogCatalog network from 10% to 90%. Our results
are presented in Table 2. Numbers in bold represent thehighest performance in each column.
DeepWalk performs consistently better than EdgeCluster,
Modularity, and wvRN. In fact, when trained with only 20%of the nodes labeled, DeepWalk performs better than theseapproaches when they are given 90% of the data. The performance of SpectralClustering proves much more competitive,
but DeepWalk still outperforms when labeled data is sparseon both Macro-F1 (TR ≤ 20%) and Micro-F1 (TR ≤ 60%).
This strong performance when only small fractions of thegraph are labeled is a core strength of our approach. In thefollowing experiments, we investigate the performance of ourrepresentations on even more sparsely labeled graphs.

6.1.2

FlickrIn this experiment we vary the training ratio (TR ) on the
Flickr network from 1% to 10%. This corresponds to having
approximately 800 to 8,000 nodes labeled for classificationin the entire network. Table 3 presents our results, which
are consistent with the previous experiment. DeepWalk
outperforms all baselines by at least 3% with respect to MicroF1 . Additionally, its Micro-F1 performance when only 3% of
the graph is labeled beats all other methods even when they
have been given 10% of the data. In other words, DeepWalk
can outperform the baselines with 60% less training data. It
also performs quite well in Macro-F1 , initially performing
close to SpectralClustering, but distancing itself to a 1%
improvement.

6.1.3

YouTubeThe YouTube network is considerably larger than theprevious ones we have experimented on, and its size prevents two of our baseline methods (SpectralClustering andModularity) from running on it. It is much closer to a realworld graph than those we have previously considered.
The results of varying the training ratio (TR ) from 1% to
10% are presented in Table 4. They show that DeepWalksignificantly outperforms the scalable baseline for creating

% Labeled Nodes

10%

20%

30%

40%

50%

60%

70%

80%

90%

Micro-F1(%)

DeepWalk
SpectralClustering
EdgeCluster
Modularity
wvRN
Majority

36.00
31.06
27.94
27.35
19.51
16.51

38.20
34.95
30.76
30.74
24.34
16.66

39.60
37.27
31.85
31.77
25.62
16.61

40.30
38.93
32.99
32.97
28.82
16.70

41.00
39.97
34.12
34.09
30.37
16.91

41.30
40.99
35.00
36.13
31.81
16.99

41.50
41.66
34.63
36.08
32.19
16.92

41.50
42.42
35.99
37.23
33.33
16.49

42.00
42.62
36.29
38.18
34.28
17.26

Macro-F1(%)

DeepWalk
SpectralClustering
EdgeCluster
Modularity
wvRN
Majority

21.30
19.14
16.16
17.36
6.25
2.52

23.80
23.57
19.16
20.00
10.13
2.55

25.30
25.97
20.48
20.80
11.64
2.52

26.30
27.46
22.00
21.85
14.24
2.58

27.30
28.31
23.00
22.65
15.86
2.58

27.60
29.46
23.64
23.41
17.18
2.63

27.90
30.13
23.82
23.89
17.98
2.61

28.20
31.38
24.61
24.20
18.86
2.48

28.90
31.78
24.92
24.97
19.57
2.62

Table 2: Multi-label classification results in BlogCatalog

Micro-F1(%)

Macro-F1(%)% Labeled Nodes

1%

2%

3%

4%

5%

6%

7%

8%

9%

10%

DeepWalk
SpectralClustering
EdgeCluster
Modularity
wvRN
Majority

32.4
27.43
25.75
22.75
17.7
16.34

34.6
30.11
28.53
25.29
14.43
16.31

35.9
31.63
29.14
27.3
15.72
16.34

36.7
32.69
30.31
27.6
20.97
16.46

37.2
33.31
30.85
28.05
19.83
16.65

37.7
33.95
31.53
29.33
19.42
16.44

38.1
34.46
31.75
29.43
19.22
16.38

38.3
34.81
31.76
28.89
21.25
16.62

38.5
35.14
32.19
29.17
22.51
16.67

38.7
35.41
32.84
29.2
22.73
16.71

DeepWalk
SpectralClustering
EdgeCluster
Modularity
wvRN
Majority

14.0
13.84
10.52
10.21
1.53
0.45

17.3
17.49
14.10
13.37
2.46
0.44

19.6
19.44
15.91
15.24
2.91
0.45

21.1
20.75
16.72
15.11
3.47
0.46

22.1
21.60
18.01
16.14
4.95
0.47

22.9
22.36
18.54
16.64
5.56
0.44

23.6
23.01
19.54
17.02
5.82
0.45

24.1
23.36
20.18
17.1
6.59
0.47

24.6
23.82
20.78
17.14
8.00
0.47

25.0
24.05
20.85
17.12
7.26
0.47

Table 3: Multi-label classification results in Flickr

Micro-F1(%)

Macro-F1(%)% Labeled Nodes

1%

2%

3%

4%

5%

6%

7%

8%

9%

10%

DeepWalk
SpectralClustering
EdgeCluster
Modularity
wvRN
Majority

37.95
—
23.90
—
26.79
24.90

39.28
—
31.68
—
29.18
24.84

40.08
—
35.53
—
33.1
25.25

40.78
—
36.76
—
32.88
25.23

41.32
—
37.81
—
35.76
25.22

41.72
—
38.63
—
37.38
25.33

42.12
—
38.94
—
38.21
25.31

42.48
—
39.46
—
37.75
25.34

42.78
—
39.92
—
38.68
25.38

43.05
—
40.07
—
39.42
25.38

DeepWalk
SpectralClustering
EdgeCluster
Modularity
wvRN
Majority

29.22
—
19.48
—
13.15
6.12

31.83
—
25.01
—
15.78
5.86

33.06
—
28.15
—
19.66
6.21

33.90
—
29.17
—
20.9
6.1

34.35
—
29.82
—
23.31
6.07

34.66
—
30.65
—
25.43
6.19

34.96
—
30.75
—
27.08
6.17

35.22
—
31.23
—
26.48
6.16

35.42
—
31.45
—
28.33
6.18

35.67
—
31.54
—
28.89
6.19

Table 4: Multi-label classification results in YouTube

0.40

0.38

0.35

0.32

0.30

0.30

γ

4

2

5

2

6

d

2

7

0.05
0.09
2

8

2

(a1) Flickr, γ = 30

M i cr o F 1

0.40

0.38

0.36

Training
0.1
0.2

0.32

2

5

2

6

d

2

7

2

8

0.5
0.9

4

2

5

2

6

d

2

7

2

0

2

1

2

2

2

3

γ

2

4

2

5

128
256

2

6

2

2

(b1) Flickr, TR = 0.05
0.45

0.40

0.40

0.40

0.35

0.35

0.25

γ
1
3
10

0.20

30
50
90

0.30

0.25

d
16
32
64

0.20

128
256

0.15
2

4

2

5

2

6

d

2

7

2

8

(a4) BlogCatalog, TR = 0.5

0

2

1

2

2

2

3

γ

2

4

2

5

2

6

0.05
0.09
2

7

(b2) Flickr, d = 128

0.45

0.30

Training
0.01
0.02

0.25

7

0.45

8

(a3) BlogCatalog, γ = 30

16
32
64
2

0.15
2

0.25

30
50
90

(a2) Flickr, TR = 0.05

0.42

0.34

4

0.30

d

1
3
10

M i cr o F 1

2

0.25

M i cr o F 1

Training
0.01
0.02

0.30

M i cr o F 1

M i cr o F 1

0.34

M i cr o F 1

0.35

M i cr o F 1

M i cr o F 1

0.36

0.35

0.35

0.30

0.25
Training
0.1
0.2

0.20

0.5
0.9

0.15
2

0

2

1

2

2

2

3

γ

2

4

2

5

2

6

2

7

(b3) BlogCatalog, TR = 0.5(a) Stability over dimensions, d

2

0

2

1

2

2

2

3

γ

2

4

2

5

2

6

2

7

(b4) BlogCatalog, d = 128(b) Stability over number of walks, γ

Figure 5: Parameter Sensitivity Studygraph representations, EdgeCluster. When 1% of the labelednodes are used for test, the Micro-F1 improves by 14%.
The Macro-F1 shows a corresponding 10% increase. This
lead narrows as the training data increases, but DeepWalk
ends with a 3% lead in Micro-F1 , and an impressive 5%
improvement in Macro-F1 .
This experiment showcases the performance benefits thatcan occur from using social representation learning for multilabel classification. DeepWalk, can scale to large graphs,
and performs exceedingly well in such a sparsely labeledenvironment.

6.2

Parameter Sensitivity

In order to evaluate how changes to the parameterization of DeepWalk effect its performance on classification
tasks, we conducted experiments on two multi-label classifications tasks (Flickr, and BlogCatalog). In the interestof brevity, we have fixed the window size and the walk length
to emphasize local structure (w = 10, t = 40). We thenvary the number of latent dimensions (d), the number ofwalks started per vertex (γ), and the amount of training
data available (TR ) to determine their impact on the networkclassification performance.

6.2.1

Effect of Dimensionality

Figure 5a shows the effects of increasing the number oflatent dimensions available to our model.
Figures 5a1 and 5a3 examine the effects of varying thedimensionality and training ratio. The performance is quiteconsistent between both Flickr and BlogCatalog andshow that the optimal dimensionality for a model is dependent on the number of training examples. (Note that 1% of
Flickr has approximately as many labeled examples as 10%
of BlogCatalog).
Figures 5a2 and 5a4 examine the effects of varying thedimensionality and number of walks per vertex. The relative
performance between dimensions is relatively stable acrossdifferent values of γ. These charts have two interestingobservations. The first is that there is most of the benefit
is accomplished by starting γ = 30 walks per node in bothgraphs. The second is that the relative difference between

different values of γ is quite consistent between the twographs. Flickr has an order of magnitude more edges than
BlogCatalog, and we find this behavior interesting.
These experiments show that our method can make usefulmodels of various sizes. They also show that the performanceof the model depends on the number of random walks it
has seen, and the appropriate dimensionality of the model
depends on the training examples available.

6.2.2

Effect of sampling frequency

Figure 5b shows the effects of increasing γ, the number ofrandom walks that we start from each vertex.
The results are very consistent for different dimensions(Fig. 5b1, Fig. 5b3) and the amount of training data (Fig.
5b2, Fig. 5b4). Initially, increasing γ has a big effect in
the results, but this effect quickly slows (γ > 10). These
results demonstrate that we are able to learn meaningfullatent representations for vertices after only a small numberof random walks.

7.

RELATED WORKThe main differences between our proposed method andprevious work can be summarized as follows:
1. We learn our latent social representations, instead ofcomputing statistics related to centrality [13] or partitioning [41].
2. We do not attempt to extend the classification procedure itself (through collective inference [37] or graphkernels [21]).
3. We propose a scalable online method which uses only
local information. Most methods require global information and are offline [17, 39–41].
4. We apply unsupervised representation learning to graphs.
In this section we discuss related work in network classification and unsupervised feature learning.

7.1

Relational Learning

Relational classification (or collective classification) methods [15, 25, 32] use links between data items as part of theclassification process. Exact inference in the collective classification problem is NP-hard, and solutions have focused on
the use of approximate inference algorithm which may not
be guaranteed to converge [37].
The most relevant relational classification algorithms to
our work incorporate community information by learning
clusters [33], by adding edges between nearby nodes [14], byusing PageRank [24], or by extending relational classification
to take additional features into account [43]. Our work takes
a substantially different approach. Instead of a new approximation inference algorithm, we propose a procedure whichlearns representations of network structure which can thenbe used by existing inference procedure (including iterativeones).
A number of techniques for generating features from graphs
have also been proposed [13, 17, 39–41]. In contrast to thesemethods, we frame the feature creation procedure as a representation learning problem.
Graph Kernels [42] have been proposed as a way to use
relational data as part of the classification process, but arequite slow unless approximated [20]. Our approach is complementary; instead of encoding the structure as part of akernel function, we learn a representation which allows them
to be used directly as features for any classification method.

7.2

Unsupervised Feature Learning

Distributed representations have been proposed to model
structural relationship between concepts [18]. These representations are trained by the back-propagation and gradientdescent. Computational costs and numerical instability led
to these techniques to be abandoned for almost a decade.
Recently, distributed computing allowed for larger models
to be trained [4], and the growth of data for unsupervised
learning algorithms to emerge [10]. Distributed representations usually are trained through neural networks, these
networks have made advancements in diverse fields such as
computer vision [22], speech recognition [8], and natural
language processing [1, 7].

8.

CONCLUSIONSWe propose DeepWalk, a novel approach for learning
latent social representations of vertices. Using local information from truncated random walks as input, our method
learns a representation which encodes structural regularities. Experiments on a variety of different graphs illustrate
the effectiveness of our approach on challenging multi-label
classification tasks.
As an online algorithm, DeepWalk is also scalable. Our
results show that we can create meaningful representations
for graphs which are too large for standard spectral methods.
On such large graphs, our method significantly outperforms
other methods designed to operate for sparsity. We also
show that our approach is parallelizable, allowing workers to
update different parts of the model concurrently.
In addition to being effective and scalable, our approachis also an appealing generalization of language modeling.
This connection is mutually beneficial. Advances in language modeling may continue to generate improved latent
representations for networks. In our view, language modeling is actually sampling from an unobservable language
graph. We believe that insights obtained from modeling observable graphs may in turn yield improvements to modelingunobservable ones.

Our future work in the area will focus on investigating
this duality further, using our results to improve language
modeling, and strengthening the theoretical justifications of
the method.

Acknowledgements
The authors thank the reviewers for their helpful comments. This
research was partially supported by NSF Grants DBI-1060572 andIIS-1017181, and a Google Faculty Research Award.

9.

REFERENCES[1] R. Al-Rfou, B. Perozzi, and S. Skiena. Polyglot:
Distributed word representations for multilingual nlp.
In Proceedings of the Seventeenth Conference on
Computational Natural Language Learning, pages
183–192, Sofia, Bulgaria, August 2013. ACL.
[2] R. Andersen, F. Chung, and K. Lang. Local graphpartitioning using pagerank vectors. In Foundations ofComputer Science, 2006. FOCS’06. 47th Annual IEEE
Symposium on, pages 475–486. IEEE, 2006.
[3] Y. Bengio, A. Courville, and P. Vincent. Representation
learning: A review and new perspectives. 2013.
[4] Y. Bengio, R. Ducharme, and P. Vincent. A neuralprobabilistic language model. Journal of Machine
Learning Research, 3:1137–1155, 2003.
[5] L. Bottou. Stochastic gradient learning in neuralnetworks. In Proceedings of Neuro-Nı̂mes 91, Nimes,
France, 1991. EC2.
[6] V. Chandola, A. Banerjee, and V. Kumar. Anomaly
detection: A survey. ACM Computing Surveys (CSUR),
41(3):15, 2009.
[7] R. Collobert and J. Weston. A unified architecture fornatural language processing: Deep neural networks
with multitask learning. In Proceedings of the 25th
ICML, ICML ’08, pages 160–167. ACM, 2008.
[8] G. E. Dahl, D. Yu, L. Deng, and A. Acero.
Context-dependent pre-trained deep neural networks
for large-vocabulary speech recognition. Audio, Speech,
and Language Processing, IEEE Transactions on,
20(1):30–42, 2012.
[9] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin,Q. Le, M. Mao, M. Ranzato, A. Senior, P. Tucker,
K. Yang, and A. Ng. Large scale distributed deep
networks. In P. Bartlett, F. Pereira, C. Burges,
L. Bottou, and K. Weinberger, editors, Advances in
Neural Information Processing Systems 25, pages
1232–1240. 2012.
[10] D. Erhan, Y. Bengio, A. Courville, P.-A. Manzagol,
P. Vincent, and S. Bengio. Why does unsupervised
pre-training help deep learning? The Journal of
Machine Learning Research, 11:625–660, 2010.
[11] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, andC.-J. Lin. LIBLINEAR: A library for large linear
classification. Journal of Machine Learning Research,
9:1871–1874, 2008.
[12] F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens.
Random-walk computation of similarities between
nodes of a graph with application to collaborative
recommendation. Knowledge and Data Engineering,IEEE Transactions on, 19(3):355–369, 2007.
[13] B. Gallagher and T. Eliassi-Rad. Leveraging
label-independent features for classification in sparselylabeled networks: An empirical study. In Advances in
Social Network Mining and Analysis, pages 1–19.
Springer, 2010.
[14] B. Gallagher, H. Tong, T. Eliassi-Rad, andC. Faloutsos. Using ghost edges for classification insparsely labeled networks. In Proceedings of the 14th
ACM SIGKDD, KDD ’08, pages 256–264, New York,NY, USA, 2008. ACM.
[15] S. Geman and D. Geman. Stochastic relaxation, gibbs
distributions, and the bayesian restoration of images.
Pattern Analysis and Machine Intelligence, IEEE
Transactions on, (6):721–741, 1984.
[16] L. Getoor and B. Taskar. Introduction to statistical
relational learning. MIT press, 2007.
[17] K. Henderson, B. Gallagher, L. Li, L. Akoglu,
T. Eliassi-Rad, H. Tong, and C. Faloutsos. It’s who you
know: Graph mining using recursive structural features.
In Proceedings of the 17th ACM SIGKDD, KDD ’11,
pages 663–671, New York, NY, USA, 2011. ACM.
[18] G. E. Hinton. Learning distributed representations ofconcepts. In Proceedings of the eighth annual conferenceof the cognitive science society, pages 1–12. Amherst,
MA, 1986.
[19] R. A. Hummel and S. W. Zucker. On the foundationsof relaxation labeling processes. Pattern Analysis andMachine Intelligence, IEEE Transactions on,(3):267–287, 1983.
[20] U. Kang, H. Tong, and J. Sun. Fast random walk graphkernel. In SDM, pages 828–838, 2012.
[21] R. I. Kondor and J. Lafferty. Diffusion kernels ongraphs and other discrete input spaces. In ICML,
volume 2, pages 315–322, 2002.
[22] A. Krizhevsky, I. Sutskever, and G. E. Hinton.
Imagenet classification with deep convolutional neuralnetworks. In NIPS, volume 1, page 4, 2012.
[23] D. Liben-Nowell and J. Kleinberg. The link-prediction
problem for social networks. Journal of the American
society for information science and technology,
58(7):1019–1031, 2007.
[24] F. Lin and W. Cohen. Semi-supervised classification of
network data using very few labels. In Advances in
Social Networks Analysis and Mining (ASONAM),
2010 International Conference on, pages 192–199, Aug
2010.
[25] S. A. Macskassy and F. Provost. A simple relationalclassifier. In Proceedings of the Second Workshop on
Multi-Relational Data Mining (MRDM-2003) at
KDD-2003, pages 64–76, 2003.
[26] S. A. Macskassy and F. Provost. Classification in
networked data: A toolkit and a univariate case study.
The Journal of Machine Learning Research, 8:935–983,
2007.
[27] T. Mikolov, K. Chen, G. Corrado, and J. Dean.
Efficient estimation of word representations in vector
space. CoRR, abs/1301.3781, 2013.
[28] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, andJ. Dean. Distributed representations of words andphrases and their compositionality. In Advances in
Neural Information Processing Systems 26, pages
3111–3119. 2013.

[29] T. Mikolov, W.-t. Yih, and G. Zweig. Linguistic
regularities in continuous space word representations.
In Proceedings of NAACL-HLT, pages 746–751, 2013.
[30] A. Mnih and G. E. Hinton. A scalable hierarchicaldistributed language model. Advances in neural
information processing systems, 21:1081–1088, 2009.
[31] F. Morin and Y. Bengio. Hierarchical probabilisticneural network language model. In Proceedings of theinternational workshop on artificial intelligence andstatistics, pages 246–252, 2005.
[32] J. Neville and D. Jensen. Iterative classification in
relational data. In Proc. AAAI-2000 Workshop on
Learning Statistical Models from Relational Data, pages
13–20, 2000.
[33] J. Neville and D. Jensen. Leveraging relational
autocorrelation with latent group models. In
Proceedings of the 4th International Workshop on
Multi-relational Mining, MRDM ’05, pages 49–55, New
York, NY, USA, 2005. ACM.
[34] J. Neville and D. Jensen. A bias/variancedecomposition for models using collective inference.
Machine Learning, 73(1):87–106, 2008.
[35] M. E. Newman. Modularity and community structure
in networks. Proceedings of the National Academy of
Sciences, 103(23):8577–8582, 2006.
[36] B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A
lock-free approach to parallelizing stochastic gradientdescent. In Advances in Neural Information Processing
Systems 24, pages 693–701. 2011.
[37] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher,
and T. Eliassi-Rad. Collective classification in network
data. AI magazine, 29(3):93, 2008.
[38] D. A. Spielman and S.-H. Teng. Nearly-linear timealgorithms for graph partitioning, graph sparsification,and solving linear systems. In Proceedings of thethirty-sixth annual ACM symposium on Theory ofcomputing, pages 81–90. ACM, 2004.
[39] L. Tang and H. Liu. Relational learning via latentsocial dimensions. In Proceedings of the 15th ACM
SIGKDD, KDD ’09, pages 817–826, New York, NY,
USA, 2009. ACM.
[40] L. Tang and H. Liu. Scalable learning of collective
behavior based on sparse social dimensions. In
Proceedings of the 18th ACM conference on
Information and knowledge management, pages
1107–1116. ACM, 2009.
[41] L. Tang and H. Liu. Leveraging social media networks
for classification. Data Mining and Knowledge
Discovery, 23(3):447–478, 2011.
[42] S. Vishwanathan, N. N. Schraudolph, R. Kondor, andK. M. Borgwardt. Graph kernels. The Journal of
Machine Learning Research, 99:1201–1242, 2010.
[43] X. Wang and G. Sukthankar. Multi-label relational
neighbor classification using social context features. In
Proceedings of the 19th ACM SIGKDD, pages 464–472.
ACM, 2013.
[44] W. Zachary. An information flow model for conflict andfission in small groups1. Journal of anthropologicalresearch, 33(4):452–473, 1977.