node2vec and Learning Graph Embeddings

This episode explores how node2vec adapts the word2vec idea to graphs by learning node embeddings from random walks instead of hand-engineered network features. It explains the core technical move in detail: second-order walks controlled by the `p` and `q` parameters, which bias the sampling process toward more local, BFS-like neighborhoods or more exploratory, DFS-like paths. The discussion highlights the paper’s main claim that this tunable notion of context can capture both homophily and structural roles, while also questioning how strongly the experiments actually prove that flexibility versus simply showing better benchmark performance. Listeners would find it interesting for its clear breakdown of why node2vec became influential: it made graph representation learning feel practical, scalable, and easy to use before modern graph neural methods took over. Sources: 1. node2vec: Scalable Feature Learning for Networks — Aditya Grover, Jure Leskovec, 2016 http://arxiv.org/abs/1607.00653 2. DeepWalk: Online Learning of Social Representations — Bryan Perozzi, Rami Al-Rfou, Steven Skiena, 2014 https://scholar.google.com/scholar?q=DeepWalk%3A+Online+Learning+of+Social+Representations 3. 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 4. node2vec: Scalable Feature Learning for Networks — Aditya Grover, Jure Leskovec, 2016 https://scholar.google.com/scholar?q=node2vec%3A+Scalable+Feature+Learning+for+Networks 5. Inductive Representation Learning on Large Graphs — William L. Hamilton, Rex Ying, Jure Leskovec, 2017 https://scholar.google.com/scholar?q=Inductive+Representation+Learning+on+Large+Graphs 6. The PageRank Citation Ranking: Bringing Order to the Web — Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 1999 https://scholar.google.com/scholar?q=The+PageRank+Citation+Ranking%3A+Bringing+Order+to+the+Web 7. Supervised Random Walks: Predicting and Recommending Links in Social Networks — Lars Backstrom, Jure Leskovec, 2011 https://scholar.google.com/scholar?q=Supervised+Random+Walks%3A+Predicting+and+Recommending+Links+in+Social+Networks 8. Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time — Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Anand Sharma, Charles Sugnet, Mark Ulrich, Jure Leskovec, 2018 https://scholar.google.com/scholar?q=Pixie%3A+A+System+for+Recommending+3%2B+Billion+Items+to+200%2B+Million+Users+in+Real-Time 9. The Link-Prediction Problem for Social Networks — David Liben-Nowell, Jon Kleinberg, 2007 https://scholar.google.com/scholar?q=The+Link-Prediction+Problem+for+Social+Networks 10. Link Prediction Based on Graph Neural Networks — Muhan Zhang, Zhicheng Cui, Marion Neumann, Yixin Chen, 2018 https://scholar.google.com/scholar?q=Link+Prediction+Based+on+Graph+Neural+Networks 11. Revisiting Semi-Supervised Learning with Graph Embeddings — Zhilin Yang, William W. Cohen, Ruslan Salakhutdinov, 2016 https://scholar.google.com/scholar?q=Revisiting+Semi-Supervised+Learning+with+Graph+Embeddings 12. Semi-Supervised Classification with Graph Convolutional Networks — Thomas N. Kipf, Max Welling, 2017 https://scholar.google.com/scholar?q=Semi-Supervised+Classification+with+Graph+Convolutional+Networks 13. word2vec Explained: Deriving Mikolov et al.'s Negative-Sampling Word-Embedding Method — Yoav Goldberg, Omer Levy, 2014 https://scholar.google.com/scholar?q=word2vec+Explained%3A+Deriving+Mikolov+et+al.%27s+Negative-Sampling+Word-Embedding+Method 14. RolX: Structural Role Extraction and Mining in Large Graphs — Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, S. H. Akoglu, Danai Koutra, Christos Faloutsos, Lei Li, 2012 https://scholar.google.com/scholar?q=RolX%3A+Structural+Role+Extraction+and+Mining+in+Large+Graphs 15. Role-aware random walk for network embedding — Hegui Zhang, Gang Kou, Yi Peng, Boyu Zhang, 2024 https://scholar.google.com/scholar?q=Role-aware+random+walk+for+network+embedding 16. WalkLM: A Uniform Language Model Fine-tuning Framework for Attributed Graph Embedding — Yanchao Tan, Zihao Zhou, Hang Lv, Weiming Liu, Carl Yang, 2023 https://scholar.google.com/scholar?q=WalkLM%3A+A+Uniform+Language+Model+Fine-tuning+Framework+for+Attributed+Graph+Embedding 17. INCREASE: Inductive Graph Representation Learning for Spatio-Temporal Kriging — Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, Jianzhong Qi, Chaochao Chen, Longbiao Chen, 2023 https://scholar.google.com/scholar?q=INCREASE%3A+Inductive+Graph+Representation+Learning+for+Spatio-Temporal+Kriging 18. Graph Condensation for Inductive Node Representation Learning — Xinyi Gao, Tong Chen, Yilong Zang, Wentao Zhang, et al., 2023 https://scholar.google.com/scholar?q=Graph+Condensation+for+Inductive+Node+Representation+Learning 19. Distributed Graph Embedding with Information-Oriented Random Walks — Peng Fang, Arijit Khan, Siqiang Luo, Fang Wang, et al., 2023 https://scholar.google.com/scholar?q=Distributed+Graph+Embedding+with+Information-Oriented+Random+Walks 20. 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: node2vec and Learning Graph Embeddings