Convergence Guarantees for the DeepWalk Embedding on Block Models

2024-10-26 · Christopher Harker, Aditya Bhaskara

Graph embeddings have emerged as a powerful tool for understanding the structure of graphs. Unlike classical spectral methods, recent methods such as DeepWalk, Node2Vec, etc. are based on solving nonlinear optimization problems on the graph, using local information obtained by performing random walks. These techniques have empirically been shown to produce ''better'' embeddings than their classical counterparts. However, due to their reliance on solving a nonconvex optimization problem, obtaining theoretical guarantees on the properties of the solution has remained a challenge, even for simple classes of graphs. In this work, we show convergence properties for the DeepWalk algorithm on graphs obtained from the Stochastic Block Model (SBM). Despite being simplistic, the SBM has proved to be a classic model for analyzing the behavior of algorithms on large graphs. Our results mirror the existing ones for spectral embeddings on SBMs, showing that even in the case of one-dimensional embeddings, the output of the DeepWalk algorithm provably recovers the cluster structure with high probability.

📄 PDF Abstract BibTeX arXiv:2410.20248

Code (0)

등록된 구현이 없습니다.

Tasks

Stochastic Block Model

Methods 이 논문이 사용한 방법론

DeepWalk DeepWalk learns embeddings (social representations) of a graph's vertices, by modeling a stream of short random walks. Social representations are latent features of the…

Exact Recovery of Community Structures Using DeepWalk and Node2vec

2021-01-18 · Yichi Zhang, Minh Tang

Random-walk based network embedding algorithms like DeepWalk and node2vec are widely used to obtain Euclidean representation of the nodes in a network prior to performing downstream inference tasks. However, despite thei…

Clustering Community Detection Network Embedding

Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec

2017-10-09 · Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li 외

Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show t…

Network Embedding Representation Learning

InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity

2020-05-29 · Sudhanshu Chanpuriya, Cameron Musco

The skip-gram model for learning word embeddings (Mikolov et al. 2013) has been widely popular, and DeepWalk (Perozzi et al. 2014), among other methods, has extended the model to learning node representations from networ…

Learning Word Embeddings Multi-Label Classification MUlTI-LABEL-ClASSIFICATION Word Embeddings

Comprehend DeepWalk as Matrix Factorization

2015-01-02 · Cheng Yang, Zhiyuan Liu

Word2vec, as an efficient tool for learning vector representation of words has shown its effectiveness in many natural language processing tasks. Mikolov et al. issued Skip-Gram and Negative Sampling model for developing…

DeepWalking Backwards: From Embeddings Back to Graphs

2021-02-17 · Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, Charalampos E. Tsourakakis

Low-dimensional node embeddings play a key role in analyzing graph datasets. However, little work studies exactly what information is encoded by popular embedding methods, and how this information correlates with perform…