PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepWalk: Online Learning of Social Representations

Bryan Perozzi, Rami Al-Rfou, Steven Skiena

arXiv:1403.6652v2cs.SIcs.LG

TL;DR

Sparse network representations can hinder statistical generalization for social-network classification. DeepWalk learns vertex representations from truncated random walks, outperforming competing methods by 5%–10% Micro F1 on the sparsest tasks and sometimes with 60% less training data.

  • Problem

    Sparse network representations can make statistical learning and multi-label social-network classification difficult, especially with partially labeled nodes.

  • Method

    DeepWalk models short truncated random walks as sentences to learn low-dimensional vertex representations that capture structural regularities and social relations.

  • Results

    5%–10% Micro F1 improvements occur on the sparsest classification problems, with DeepWalk sometimes outperforming competitors using 60% less training data.

  • Takeaways & Limitations

    DeepWalk provides scalable, online, and parallelizable representations for classification on graphs too large for spectral methods.

  • Takeaways & Limitations

    Its community-aware similarity interpretation is scoped to networks where homophily supports generalization.

Abstract

from arXiv · show

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 modeling and unsupervised feature learning (or deep learning) from sequences of words to graphs. DeepWalk uses local information obtained from truncated random walks to learn latent representations by treating walks as the equivalent of sentences. We demonstrate DeepWalk's latent representations on several multi-label network classification 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 $F_1$ 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 trivially parallelizable. These qualities make it suitable for a broad class of real world applications such as network classification, and anomaly detection.

1. INTRODUCTION

DeepWalk applies unsupervised feature learning to graphs by modeling short random walks to produce latent vertex representations that capture neighborhood similarity and community membership. These representations improve classification under label sparsity while remaining general, scalable, online, and trivially parallelizable.

  • Network sparsity enables efficient discrete algorithms but complicates statistical generalization, challenging applications such as classification, recommendation, anomaly detection, and missing-link prediction.
  • DeepWalk learns latent vertex features by modeling streams of short random walks, transferring unsupervised feature-learning techniques from natural language processing to network analysis.The representations capture neighborhood similarity and community membership.
  • DeepWalk’s representations outperform other latent-representation methods, especially when labeled nodes are scarce, while supporting simple linear and more general classifiers.The approach learns label-independent representations that can be combined with iterative inference methods.
  • 5%-10% Micro F1 improvements occur on the sparsest multi-label classification problems, and DeepWalk can outperform competitors with 60% less training data in some cases.

2. PROBLEM DEFINITION

The problem is multi-label classification in a partially labeled social network, using graph structure to learn label-independent, low-dimensional representations that augment node attributes. This separation supports reusable structural features, avoids cascading errors, and integrates with general classifiers.

  • Problem formulation: The task classifies social-network members into one or more categories using a partially labeled graph G_L=(V,E,X,Y), where X contains node attributes and Y contains labels.The graph is G=(V,E), with V as members and E⊆(V×V) as edges; X∈R^{|V|×S}.
  • Problem formulation: Graph structure provides dependence information among examples beyond traditional mappings from attributes X to labels Y.This relational-classification setting exploits dependencies embedded in G to improve classification performance.
  • Representation objective: The proposed approach learns unsupervised features that capture graph topology independently of the labels’ distribution, rather than mixing labels into the feature space.This distinguishes the method from traditional relational-classification approaches based on inference in undirected Markov networks.
  • Representation objective: Separating structural representations from labeling avoids cascading errors and allows one representation to support multiple classification problems on the same network.The structural features can augment the attribute space and work with any classification algorithm, including iterative methods.
  • Representation objective: The goal is to learn XE∈R^{|V|×d} with a small number d of latent dimensions, distributed so dimensions jointly encode social phenomena and concepts.Each social phenomenon is expressed by a subset of dimensions, while each dimension contributes to a subset of social concepts.

3. LEARNING SOCIAL REPRESENTATIONS

DeepWalk learns vertex representations from streams of short random walks using language-modeling techniques. The resulting embeddings are low-dimensional, continuous, community-aware, adaptable, and capture shared local graph structure.

  • Design requirements: The method targets adaptable, community-aware, low-dimensional, and continuous representations for evolving social networks.These properties support incremental learning, similarity-based generalization, better performance with scarce labels, partial community membership, and robust classification.
  • Learning method: DeepWalk learns vertex representations from a stream of short random walks using optimization techniques originally designed for language modeling.Random walks capture local structure, while local exploration is easy to parallelize.
  • Learning method: Short random walks are treated as sentences, enabling language-modeling methods to estimate vertex-context relationships in graphs.The approach generalizes language modeling by estimating the likelihood of observing a vertex given previously visited vertices.
  • Representation objective: The relaxed optimization captures shared local graph structure, giving similar representations to vertices with similar neighborhoods.Order independence models random-walk nearness and speeds training by building small models one vertex at a time.
  • Properties: The resulting representations are low-dimensional, continuous, encode latent community membership, and adapt to changing network topology through useful intermediate outputs.The direct likelihood objective becomes infeasible as walk length grows, motivating the relaxed formulation.

4. METHOD · 4.1 Overview

DeepWalk’s method treats truncated random walks as a corpus and graph vertices as the vocabulary, using a random-walk generator and an update procedure. The section also introduces algorithm variants and discusses their merits.

  • 4. METHOD: The method section presents DeepWalk’s main algorithmic components, variants, and their merits.It frames the discussion around the algorithm’s components and alternative approaches.
  • 4.1 Overview: DeepWalk requires only a corpus and vocabulary, following the language-modeling setup.Its corpus and vocabulary are defined from the graph rather than supplied separately.
  • 4.1 Overview: Short truncated random walks form DeepWalk’s corpus.The walks are treated as the equivalent corpus for the algorithm.
  • 4.1 Overview: The graph vertices constitute DeepWalk’s vocabulary V.The passage explicitly defines the vocabulary from graph vertices.
  • 4.1 Overview: Knowing V and vertex-frequency distributions in advance is beneficial but unnecessary for the algorithm to work.The passage points to Section 4.2.2 for this property.
  • 4.1 Overview: DeepWalk consists of two main components: a random walk generator and an update procedure.These components define the algorithm’s core processing stages.

4.2 Algorithm:

DeepWalk learns vertex representations by applying SkipGram to truncated random walks, treating nearby vertices in each walk as context. Hierarchical Softmax makes the resulting probability computations scalable, while stochastic gradient descent updates the model parameters.

  • Random-walk generation: DeepWalk samples a root vertex uniformly and follows uniformly chosen neighbors until the walk reaches maximum length t.Walks may vary in length and can include restarts, although experiments use fixed-length walks.
  • Hierarchical Softmax: Hierarchical Softmax replaces the infeasible partition-function computation with binary classifiers along a tree path, reducing complexity from O(|V|) to O(log |V|).Huffman coding assigns shorter paths to frequent vertices to reduce access time.
  • Optimization: The model parameters Φ and T are optimized with stochastic gradient descent, whose derivatives are estimated by back-propagation.The parameter sets each have size O(d|V|).
  • SkipGram training: For each random walk, a window of length 2w + 1 maps each central vertex to its representation and maximizes co-occurrence with context vertices.SkipGram updates representations using the vertices appearing within the walk window.

4.3 Parallelizability

DeepWalk supports parallel training because random-walk vertex frequencies follow a power law, making parameter updates sparse and enabling asynchronous stochastic gradient descent without locks.

  • Parallelizability: Power-law vertex frequencies make updates to Φ sparse, enabling lock-free asynchronous stochastic gradient descent in multi-worker training.The passage attributes this parallelizability to the long tail of infrequent vertices in social-network random walks.

4.4 Algorithm Variants

DeepWalk admits streaming and non-random-walk variants that update representations directly from observed walks or sequences without requiring the entire graph. These variants connect graph representation learning to language modeling and may support continually evolving, web-scale networks.

  • Streaming variant: A streaming variant feeds small graph walks directly to representation-learning code and updates the model without knowledge of the entire graph.It requires modifying the learning process, including initializing α to a small constant because a decaying learning rate is no longer possible.
  • Streaming variant: The streaming approach can retain Huffman coding to reduce frequent element access times.
  • Non-random walks: Graphs generated from streams of non-random walks can feed the modeling phase directly, capturing both network structure and path-traversal frequency.
  • Language modeling: The framework encompasses language modeling by viewing sentences as purposeful walks through an appropriately designed language network, with SkipGram capturing this behavior.
  • Evolving networks: Combining non-random-walk streams with the streaming variant enables training on continually evolving networks without explicitly constructing the entire graph.The authors suggest this could enable web-scale classification without handling a web-scale graph.

5. EXPERIMENTAL DESIGN

The experiments use BlogCatalog, Flickr, and YouTube social networks with task-specific labels, evaluating the approach against spectral, modularity, clustering, relational-classification, and majority baselines.

  • Datasets: The experiments evaluate BlogCatalog, Flickr, and YouTube social networks, whose labels represent topics, user interests, and shared video-genre preferences, respectively.BlogCatalog labels are topic categories; Flickr labels are interest groups; YouTube labels are viewer groups organized by common video genres.
  • Baselines: The evaluation compares the approach with SpectralClustering, Modularity, EdgeCluster, wvRN, and Majority baselines.These baselines cover graph spectral and modularity representations, adjacency-matrix clustering, relational classification, and a naive frequent-label predictor.
  • Baselines: SpectralClustering represents vertices using the d-smallest eigenvectors of the normalized graph Laplacian, assuming graph cuts aid classification.The method generates a representation in R^d from the d-smallest eigenvectors of the normalized graph Laplacian.
  • Baselines: Modularity represents vertices using the top-d eigenvectors of the Modularity matrix, assuming modular graph partitions aid classification.Its eigenvectors encode information about modular graph partitions.
  • Baselines: EdgeCluster applies k-means clustering to the adjacency matrix and scales to graphs too large for spectral decomposition.It has been shown to perform comparably to Modularity while offering this scalability advantage.

6. EXPERIMENTS

DeepWalk is evaluated on multi-label network classification under matched experimental protocols, showing strong performance with sparse labels across BlogCatalog, Flickr, and YouTube. Parameter studies further indicate that performance depends on training examples and random-walk coverage.

  • Experimental protocol: The evaluation uses identical datasets and procedures to prior baselines, with random labeled-node splits repeated 10 times and average Macro-F1 and Micro-F1 reported.Classification uses one-vs-rest logistic regression with LibLinear.
  • BlogCatalog: At 20% labeled nodes, DeepWalk outperforms EdgeCluster, Modularity, and wvRN even when those methods receive 90% of the data.Against SpectralClustering, DeepWalk wins on sparse labels for Macro-F1 at TR ≤20% and Micro-F1 at TR ≤60%.
  • Flickr: 3% labeled Flickr nodes yields DeepWalk Micro-F1 performance exceeding every baseline even with 10% labeled data, while DeepWalk beats all baselines by at least 3% in Micro-F1.The experiment varies TR from 1% to 10%, corresponding to approximately 800 to 8,000 labeled nodes.
  • YouTube: 14% Micro-F1 and 10% Macro-F1 improvements over EdgeCluster occur with 1% labeled YouTube nodes, narrowing to 3% and 5% respectively as training data increases.YouTube’s scale prevents SpectralClustering and Modularity from running, while DeepWalk remains scalable in this sparse-label setting.
  • Parameter sensitivity: The optimal latent dimensionality depends on available training examples, and increasing walks per vertex initially improves results before the effect slows beyond γ > 10.These studies use Flickr and BlogCatalog with fixed window size w = 10 and walk length t = 40.

7. RELATED WORK

DeepWalk differs from prior network-classification methods by learning latent representations rather than modifying classification procedures or computing structural statistics. It applies unsupervised representation learning to graphs through a scalable online method using local information.

  • Methodological differences: DeepWalk does not extend classification through collective inference or graph kernels.
  • Methodological differences: DeepWalk uses a scalable online method based only on local information, whereas many prior methods require global information and operate offline.
  • Representation learning: DeepWalk frames graph feature creation as unsupervised representation learning, producing representations that existing classification methods can use directly as features.

8. CONCLUSIONS

DeepWalk learns latent social representations from truncated random walks, encoding structural regularities and supporting effective multi-label classification. It is scalable and parallelizable, while also connecting graph representation learning with language modeling and motivating further theoretical work.

  • Core contribution: DeepWalk learns vertex representations from local information in truncated random walks, encoding structural regularities for challenging multi-label classification tasks.Experiments across varied graphs illustrate the approach’s effectiveness.
  • Scalability: DeepWalk scales to graphs too large for spectral methods and significantly outperforms other methods designed to operate under sparsity.Its online design also produces meaningful representations on large graphs.
  • Scalability: DeepWalk is parallelizable, allowing workers to update different parts of the model concurrently.This parallelism follows from its online algorithm design.
  • Language-modeling connection: DeepWalk generalizes language modeling to graphs, suggesting that advances in either observable-graph or unobservable-language modeling may improve the other.The authors view language modeling as sampling from an unobservable language graph.
  • Future work: Future work will investigate this duality, use the results to improve language modeling, and strengthen the method’s theoretical justifications.These directions extend both the cross-domain connection and the method’s theoretical foundation.
Loading 1403.6652v2…