DeepWalk: online learning of social representations
By Bryan Perozzi, Rami Al-Rfou, Steven S. Skiena. 2014
10,831 citations recorded by the source corpus.
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 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 trivially parallelizable. These qualities make it suitable for a broad class of real world applications such as network classification, and anomaly detection.
Subfields: Artificial Intelligence, Representation & Self-Supervised Learning, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Mohit Bansal
- Percy Liang
- Jianfeng Gao
- Quoc V. Le
- Ruslan Salakhutdinov
- Jure Leskovec
- Luke S. Zettlemoyer
In Representation & Self-Supervised Learning
- William L. Hamilton
- Jure Leskovec
- Yoshua Bengio
- Stephan Günnemann
- Bryan Perozzi
- Aleksandar Bojchevski
- Philip S. Yu
- Dacheng Tao
In Graph Learning
- William L. Hamilton
- Jure Leskovec
- Stephan Günnemann
- Aleksandar Bojchevski
- Michael M. Bronstein
- Matthias Fey
- Rex Ying
- Bryan Perozzi
Citations in the corpus
- Inductive Representation Learning on Large Graphs (2017, neutral): “[28], where we run a new round of SGD optimization to embed the new test nodes before making predictions (see the Appendix for details).”
- node2vec: Scalable Feature Learning for Networks (2016, methodology): “Recent attempts in this direction [24, 28] propose efficient algorithms but rely on a rigid notion of a network neighborhood, which results in these approaches being largely insensitive to connectivity patterns unique to networks.”
- Revisiting Semi-Supervised Learning with Graph Embeddings (2016, methodology): “Graph embedding methods (Perozzi et al., 2014; Tian et al., 2014) encode the graph structure into embeddings; however, different from our approach, these methods are purely unsupervised and do not leverage label information for a specific task.”
- Gated Graph Sequence Neural Networks (2015, methodology): “Standard approaches to the problem include engineering custom features of an input graph, graph kernels (Kashima et al., 2003; Shervashidze et al., 2011), and methods that define graph features in terms of random walks on graphs (Perozzi et al., 2014).”
- LINE: Large-scale Information Network Embedding (2015, methodology): “The most recent work related with ours is DeepWalk [16], which deploys a truncated random walk for social network embedding.”
- Predicting multicellular function through multi-layer tissue networks (2017, background): “Recent studies focused on embedding nodes into lowdimensional vector spaces by first using random walks to construct the network neighborhood of every node in the graph, and then optimizing an objective function with network neighborhoods as input (Perozzi et al., 2014; Tang et al., 2015; Grover and”
- Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “Finally, in the network analysis community, several works constructed graph embeddings [28, 38, 12, 17, 44] methods inspired by the Word2Vec technique [27].”
- Stochastic Training of Graph Convolutional Networks (2017, background): “…Welling, 2016; Berg et al., 2017) and knowledge graphs (Schlichtkrull et al., 2017), outperforming multi-layer perceptron (MLP) models that do not use the graph structure and graph embedding approaches (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016) that do not use node features.”
- Variational Graph Auto-Encoders (2016, methodology): “In contrast to most existing models for unsupervised learning on graph-structured data and link prediction [5, 6, 7, 8], our model can naturally incorporate node features, which significantly improves predictive performance on a number of benchmark datasets.”
- Strategies for Pre-training Graph Neural Networks (2019, methodology): “In the first category are methods that use local random walk-based objectives (Grover & Leskovec, 2016; Perozzi et al., 2014; Tang et al., 2015) and methods that reconstruct a graph’s adjacency matrix, e.g. , by predicting edge existence (Hamilton et al., 2017a; Kipf & Welling, 2016).”
- SHINE: Signed Heterogeneous Information Network Embedding for Sentiment Link Prediction (2017, background): “Another promising approach called network embedding [8, 17, 23, 26], which automatically learns features of users in network, seems plausible to solve the task.”
- Attacking Graph-based Classification via Manipulating the Graph Structure (2019, methodology): “We consider three representative collective classification methods, i.e., JWP [63], LBP [23], and RW [64], and four representative graph neural network methods, i.e., LINE [58], Deep-Walk [48], node2vec [28], and GCN [36].”
- Differential Privacy Preservation for Deep Auto-Encoders: an Application of Human Behavior Prediction (2016, background): “…success in recent years, the applications of deep learning are being expanded into other fields such as social media (Yuan et al. 2013), social network analysis (Perozzi, Al-Rfou, and Skiena 2014), bioinformatics (Chicco, Sadowski, and Baldi 2014), medicine and healthcare (Song et al. 2014).”
- Compositional Fairness Constraints for Graph Embeddings (2019, methodology): “, 2001), with recent years witnessing a surge in methods that rely on random-walk based objectives (Grover & Leskovec, 2016; Perozzi et al., 2014), deep autoencoders (Wang et al.”
- Auto-GNN: Neural architecture search of graph neural networks (2019, methodology): “Graph neural networks (GNN) [1, 2] has been demonstrated that it could achieve superior performance in modeling graph-structured data, within various domains such as social media [3–6] and bioinformatics [7, 8].”
- Relational inductive biases, deep learning, and graph networks (2018, background): “ecent work has also focused on building generative models of graphs (Li et al., 2018; De Cao and Kipf, 2018; You et al., 2018; Bojchevski et al., 2018), and unsupervised learning of graph embeddings (Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016; Garca-Duran and Niepert, 2017). ”
- Position-aware Graph Neural Networks (2019, background): “…et al., 2018b), with successful applications across domains such as social and information networks (Ying et al., 2018a), chemistry (You et al., 2018a), and biology (Zitnik & Leskovec, 2017). matrix-factorization approaches (Belkin & Niyogi, 2002), and random-walk approaches (Perozzi et al., 2014).”