We present Walklets, a novel approach for learning multiscale representations
of vertices in a network. In contrast to previous works, these representations
explicitly encode multiscale vertex relationships in a way that is analytically
derivable.
Walklets generates these multiscale relationships by subsampling short random
walks on the vertices of a graph. By `skipping' over steps in each random walk,
our method generates a corpus of vertex pairs which are reachable via paths of
a fixed length. This corpus can then be used to learn a series of latent
representations, each of which captures successively higher order relationships
from the adjacency matrix.
We demonstrate the efficacy of Walklets's latent representations on several
multi-label network classification tasks for social networks such as
BlogCatalog, DBLP, Flickr, and YouTube. Our results show that Walklets
outperforms new methods based on neural matrix factorization. Specifically, we
outperform DeepWalk by up to 10% and LINE by 58% Micro-F1 on challenging
multi-label classification tasks. Finally, Walklets is an online algorithm, and
can easily scale to graphs with millions of vertices and edges.

我们提出了一种名为 Walklets 的算法，通过子采样短的随机游走，在图的顶点之间建立多尺度关系，从而生成多维表示，用于社交网络等多标签网络分类任务，其效果优于 DeepWalk 和 LINE 等方法，且为在线算法，可轻松扩展到数百万个顶点和边。