Network Embedding Using Sparse Approximations of Random Walks
Paula Mercurio Di Liu
In this paper, we propose an efficient numerical implementation of Network
Embedding based on commute times, using sparse approximation of a diffusion
process on the network obtained by a modified version of the diffusion wavelet
algorithm. The node embeddings are computed by optimizing the cross entropy
loss via the stochastic gradient descent method with sampling of
low-dimensional representations of green functions. We demonstrate the efficacy
of this method for data clustering and multi-label classification through
several examples, and compare its performance over existing methods in terms of
efficiency and accuracy. Theoretical issues justifying the scheme are also
discussed.