Structure of Nonlinear Node Embeddings in Stochastic Block Models
Structure of Nonlinear Node Embeddings in Stochastic Block Models
复制标题
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
C. Harker;Aditya Bhaskara
中科院分区：
文献类型：
--
作者：
C. Harker;Aditya Bhaskara
在实践中广泛使用了非线性节点嵌入技术，例如深行和Node2VEC，以发现图中的结构。尽管在特殊制度（例如高嵌入维度的情况）中可以保证理论保证，但即使是从简单生成模型获得的图表，最佳低维嵌入方式的结构也无法正式理解。我们考虑随机块模型，并表明在适当的分离条件下，可以分析最佳嵌入。类似于基于特征向量（光谱）嵌入的已知结果，从理论上讲，我们证明了解决方案向量良好的群集，直至sublinear误差。
Nonlinear node embedding techniques such as DeepWalk and Node2Vec are used extensively in practice to uncover structure in graphs. Despite theoretical guarantees in special regimes (such as the case of high embedding dimension), the structure of the optimal low dimensional embed-dings has not been formally understood even for graphs obtained from simple generative models. We consider the stochastic block model and show that under appropriate separation conditions, the optimal embeddings can be analytically characterized. Akin to known results on eigenvector based (spectral) embeddings, we prove theoretically that solution vectors are well-clustered, up to a sublinear error.