Asymptotics of $\ell_2$ Regularized Network Embeddings
This work addresses the problem of improving network embedding methods for tasks like node classification or link prediction, offering theoretical insights and practical benefits for researchers and practitioners in network analysis, though it is incremental as it builds on existing embedding techniques.
The paper investigates the effect of adding an L2 penalty to network embedding methods like DeepWalk and node2vec, proving that under exchangeability assumptions, this asymptotically leads to learning a graphon with a nuclear-norm penalty and providing distribution guarantees for the embeddings. It also shows empirically that concatenating node covariates to L2-regularized node2vec embeddings yields comparable or superior performance to non-linear methods that incorporate both covariates and network structure.
A common approach to solving prediction tasks on large networks, such as node classification or link prediction, begin by learning a Euclidean embedding of the nodes of the network, from which traditional machine learning methods can then be applied. This includes methods such as DeepWalk and node2vec, which learn embeddings by optimizing stochastic losses formed over subsamples of the graph at each iteration of stochastic gradient descent. In this paper, we study the effects of adding an $\ell_2$ penalty of the embedding vectors to the training loss of these types of methods. We prove that, under some exchangeability assumptions on the graph, this asymptotically leads to learning a graphon with a nuclear-norm-type penalty, and give guarantees for the asymptotic distribution of the learned embedding vectors. In particular, the exact form of the penalty depends on the choice of subsampling method used as part of stochastic gradient descent. We also illustrate empirically that concatenating node covariates to $\ell_2$ regularized node2vec embeddings leads to comparable, when not superior, performance to methods which incorporate node covariates and the network structure in a non-linear manner.