Skip to yearly menu bar Skip to main content


Structure of Nonlinear Node Embeddings in Stochastic Block Models

Christopher Harker · Aditya Bhaskara

Auditorium 1 Foyer 68


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 embeddings 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.

Live content is unavailable. Log in and register to view live content