DeepWalk: Online Learning ofSocial Representations
ACM SIG-KDD
August 26, 2014

Bryan Perozzi, Rami Al-Rfou, Steven Skiena
Stony Brook University

Outline● Introduction: Graphs as Features● Language Modeling● DeepWalk● Evaluation: Network Classification● Conclusions & Future Work

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Features From Graphs
A first step in machine learning for graphs is to
extract graph features:Adjacency Matrix● node: degree● pairs: # of common neighbors● groups: cluster assignments

Bryan Perozzi

|V|●
●
●
●●Anomaly Detection
Attribute Prediction
Clustering
Link Prediction...

DeepWalk: Online Learning of Social Representations

What is a Graph Representation?

Adjacency Matrix

We can also create features by transforming thegraph into a lower dimensional latent
representation.

Bryan Perozzi

Latent Dimensions|V|d << |V|

●
●
●
●
●

Anomaly Detection
Attribute Prediction
Clustering
Link Prediction...

DeepWalk: Online Learning of Social Representations

DeepWalk
DeepWalk learns a latent representation ofadjacency matrices using deep learningtechniques developed for language modeling.

Adjacency Matrix

Latent Dimensions

DeepWalk|V|

Bryan Perozzid << |V|●●●●●Anomaly Detection
Attribute Prediction
Clustering
Link Prediction...

DeepWalk: Online Learning of Social Representations

Visual Example
On Zachary’s Karate Graph:

Input
Bryan Perozzi

OutputDeepWalk: Online Learning of Social Representations

Advantages of DeepWalk● Scalable - An online algorithm that does notuse entire graph at once
● Walks as sentences metaphor● Works great!
● Implementation available: bit.ly/deepwalk

Adjacency Matrix

Latent Dimensions

DeepWalk|V|

Bryan Perozzid << |V|●●●●●Anomaly Detection
Attribute Prediction
Clustering
Link Prediction...

DeepWalk: Online Learning of Social Representations

Outline● Introduction: Graphs as Features● Language Modeling● DeepWalk● Evaluation: Network Classification● Conclusions & Future Work

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Language ModelingLearning a
representationmeans learning amapping function
from word cooccurrence[Baroni et al, 2009]

We hope that the learned
representations capture
inherent structure[Rumelhart+, 2003]
Bryan Perozzi

DeepWalk: Online Learning of Social Representations

World of Word Embeddings
This is a very active research topic in NLP.
•Importance sampling and hierarchical classification were proposed to speed up training.
[F. Morin and Y.Bengio, AISTATS 2005] [Y. Bengio and J. Sencal, IEEENN 2008] [A. Mnih, G.
Hinton, NIPS 2008]•NLP applications based on learned representations.
[Colbert et al. NLP (Almost) from Scratch, (JMLR), 2011.]•Recurrent networks were proposed to learn sequential representations.
[Tomas Mikolov et al. ICASSP 2011]•Composed representations learned through recursive networks were used for parsing,paraphrase detection, and sentiment analysis.
[ R. Socher, C. Manning, A. Ng, EMNLP (2011, 2012, 2013) NIPS (2011, 2012) ACL (2012,2013) ]•Vector spaces of representations are developed to simplify compositionality.
[ T. Mikolov, G. Corrado, K. Chen and J. Dean, ICLR 2013, NIPS 2013]

Co-Occurrence Matrix

Word Frequency in Natural Language■ Words frequency in a naturallanguage corpus follows a powerlaw.

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Connection: Power Laws

Vertex frequency in random walks onscale free graphs also follows a powerlaw.

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Vertex Frequency in SFG

Scale Free Graph■ Short truncated random walks
are sentences in an artificial
language!
■ Random walk distance is
known to be good features formany problems

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

The Cool Idea

Short random walks =sentences

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Outline● Introduction: Graphs as Features● Language Modeling● DeepWalk● Evaluation: Network Classification● Conclusions & Future Work

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Deep Learning for Networks
2
Random Walks

1

43 Representation Mapping

Input: Graph

Hierarchical Softmax

Bryan Perozzi

5

Output: Representation

DeepWalk: Online Learning of Social Representations

Deep Learning for Networks
2
Random Walks

1

43 Representation Mapping

Input: Graph

Hierarchical Softmax

Bryan Perozzi

5

Output: Representation

DeepWalk: Online Learning of Social Representations

Random Walks■ We generate
in the graph.

random walks for each vertex■ Each short random walk has length.

■ Pick the next step uniformly from the vertex
neighbors.
■ Example:
Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Deep Learning for Networks
2
Random Walks

1

4

3 Representation Mapping

Input: Graph

Hierarchical Softmax

Bryan Perozzi

5

Output: Representation

DeepWalk: Online Learning of Social Representations

Representation Mapping■ Map the vertex under focus (its representation.
■ Define a window of size
■ If= 1 and=Maximize:

Bryan Perozzi

DeepWalk: Online Learning of Social Representations) toDeep Learning for Networks
2Random Walks

14

3 Representation Mapping

Input: Graph

Hierarchical Softmax

Bryan Perozzi

5

Output: Representation

DeepWalk: Online Learning of Social Representations

Hierarchical Softmax
Calculating
involves O(V) operations
for each update! Instead:● Consider the graph vertices
as leaves of a balanced
binary tree.
● Maximizing
is equivalent to maximizing
the probability of the pathfrom the root to the node.
specifically, maximizing

C3
C2
C1

Each of {C1, C2, C3} is alogistic binary classifier.
Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Learning[Mikolov+, 2013]■ Learned parameters:■ Vertex representations■ Tree binary classifiers weights■ Randomly initialize the representations.
■ For each {C1, C2, C3} calculate the loss
function.
■ Use Stochastic Gradient Descent to update
both the classifier weights and the vertex
representation simultaneously.
Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Deep Learning for Networks
2Random Walks

143 Representation Mapping

Input: Graph

Hierarchical Softmax

Bryan Perozzi

5

Output: Representation

DeepWalk: Online Learning of Social Representations

Outline● Introduction: Graphs as Features● Language Modeling● DeepWalk● Evaluation: Network Classification● Conclusions & Future Work

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Attribute Prediction
The Semi-Supervised Network Classification
Stony Brookproblem:Googlers
students

INPUT

2

A partially labelled graph with node
attributes.

1436OUTPUT
Attributes for nodes which do nothave them.
Bryan Perozzi

DeepWalk: Online Learning of Social Representations

5Baselines■

Approximate Inference Techniques:❑■

weighted vote Relational Neighbor (wvRN)[Macskassy+, ‘03]

Latent Dimensions
Spectral Methods■ SpectralClustering [Tang+, ‘11]
■ MaxModularity [Tang+, ‘09]
❑ k-means■ EdgeCluster [Tang+, ‘09]
❑Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Results: BlogCatalog

DeepWalk performs well, especially when labels aresparse.
Bryan Perozzi

Results: Flickr

Bryan Perozzi

Results: YouTube

Spectral Methods do not scale to large graphs.
Bryan Perozzi

Parallelization●●Parallelization doesn’t affect representation quality.
The sparser the graph, the easier to achieve linear
scalability. (Feng+, NIPS ‘11)

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Outline● Introduction: Graphs as Features● Language Modeling● DeepWalk● Evaluation: Network Classification● Conclusions & Future Work

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Variants / Future Work■Streaming
No need to ever store entire graph❑ Can build & update representation as new data
comes in.
❑■“Non-Random” Walks
Many graphs occur through as a by-product ofinteractions❑ One could outside processes (users, etc) to feed
the modeling phase❑ [This is what language modeling is doing]❑

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Take-away

Language Modeling techniques can beused for online learning of network
representations.

Bryan Perozzi

DeepWalk: Online Learning of Social Representations

Thanks!
Bryan Perozzi@phaneinbperozzi@cs.stonybrook.eduDeepWalk available at:
http://bit.ly/deepwalk

Bryan Perozzi

DeepWalk: Online Learning of Social Representations