DeepWalk and the Rise of Graph Embeddings

This episode explores how DeepWalk helped launch modern graph representation learning by turning random walks over a social network into “sentences” and then applying the Skip-Gram ideas behind word2vec to learn dense node embeddings. It explains why that mattered in 2014: instead of relying on heavy spectral or matrix-factorization methods, DeepWalk offered an online, scalable way to learn reusable graph features that worked especially well when labeled data was scarce. The discussion digs into the paper’s main empirical claim that, on social-network benchmarks like BlogCatalog, Flickr, and YouTube, the method substantially improved node classification under sparse-label settings. It is interesting because the conversation goes beyond the headline result and asks what really drove the gains: the language-modeling objective, the community-biased random-walk sampler, or simply a better optimization setup for homophilous graphs. Sources: 1. DeepWalk and the Rise of Graph Embeddings https://arxiv.org/pdf/1403.6652 2. Distributed Representations of Words and Phrases and their Compositionality — Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, Jeffrey Dean, 2013 https://scholar.google.com/scholar?q=Distributed+Representations+of+Words+and+Phrases+and+their+Compositionality 3. Efficient Estimation of Word Representations in Vector Space — Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean, 2013 https://scholar.google.com/scholar?q=Efficient+Estimation+of+Word+Representations+in+Vector+Space 4. Learning Latent Social Dimensions for Link Prediction — Lei Tang, Huan Liu, 2011 https://scholar.google.com/scholar?q=Learning+Latent+Social+Dimensions+for+Link+Prediction 5. LINE: Large-scale Information Network Embedding — Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei, 2015 https://scholar.google.com/scholar?q=LINE%3A+Large-scale+Information+Network+Embedding 6. node2vec: Scalable Feature Learning for Networks — Aditya Grover, Jure Leskovec, 2016 https://scholar.google.com/scholar?q=node2vec%3A+Scalable+Feature+Learning+for+Networks 7. Planetoid: Inductive Representation Learning on Large Graphs — Zhilin Yang, William W. Cohen, Ruslan Salakhutdinov, 2016 https://scholar.google.com/scholar?q=Planetoid%3A+Inductive+Representation+Learning+on+Large+Graphs 8. Node Embedding for Homophilous Graphs with ARGEW: Augmentation of Random walks by Graph Edge Weights — authors not shown in snippet, recent; exact year not shown https://scholar.google.com/scholar?q=Node+Embedding+for+Homophilous+Graphs+with+ARGEW%3A+Augmentation+of+Random+walks+by+Graph+Edge+Weights 9. Graph neural networks for graphs with heterophily: A survey — authors not shown in snippet, recent; exact year not shown https://scholar.google.com/scholar?q=Graph+neural+networks+for+graphs+with+heterophily%3A+A+survey 10. Learning attribute and homophily measures through random walks — authors not shown in snippet, recent; exact year not shown https://scholar.google.com/scholar?q=Learning+attribute+and+homophily+measures+through+random+walks 11. Graph Node Embedding by Neighborhood Prediction Based on Multiview Contrastive Learning — authors not shown in snippet, recent; exact year not shown https://scholar.google.com/scholar?q=Graph+Node+Embedding+by+Neighborhood+Prediction+Based+on+Multiview+Contrastive+Learning 12. Dynamic graph representation learning with neural networks: A survey — authors not shown in snippet, recent; exact year not shown https://scholar.google.com/scholar?q=Dynamic+graph+representation+learning+with+neural+networks%3A+A+survey 13. AI Post Transformers: GraphSAGE: Inductive Representation Learning on Large Graphs — Hal Turing & Dr. Ada Shannon, Mon, https://podcast.do-not-panic.com/episodes/graphsage-inductive-representation-learning-on-large-graphs/ Interactive Visualization: DeepWalk and the Rise of Graph Embeddings