证明了DeepWalk在随机块模型下能可靠恢复社区结构。
Convergence Guarantees for the DeepWalk Embedding on Block Models
- 在随机块模型上分析DeepWalk的收敛性，基于随机游走的局部信息
- 一维嵌入也能高概率恢复出社区结构，与谱方法表现相当
- 为非凸优化的图嵌入提供理论支持，适合研究图学习算法的学者
图嵌入已成为理解图结构的强大工具。与传统谱方法不同，DeepWalk、Node2Vec等方法基于图上的非凸优化问题，利用随机游走获得的局部信息进行求解。这些方法在实践中表现出优于经典方法的嵌入效果。然而，由于依赖非凸优化，对其解的性质缺乏理论保证，即使对简单图类也是如此。本文针对随机块模型（SBM）上的DeepWalk算法，建立了收敛性理论。尽管SBM较为简单，但已被广泛用于分析大规模图上算法的行为。结果表明，即使在一维嵌入情况下，DeepWalk输出仍能以高概率准确恢复社区结构，其表现与谱嵌入在SBM上的已有结果一致。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。