Faster Clustering via Non-Backtracking Random Walks
This is an incremental improvement for researchers and practitioners working with graph clustering, particularly on sparse graphs.
The paper tackles the problem of improving unsupervised graph clustering for sparse graphs by introducing VEC-NBT, a variant of the VEC algorithm that uses a non-backtracking random walk, resulting in shorter walks needed to achieve comparable or greater accuracy.
This paper presents VEC-NBT, a variation on the unsupervised graph clustering technique VEC, which improves upon the performance of the original algorithm significantly for sparse graphs. VEC employs a novel application of the state-of-the-art word2vec model to embed a graph in Euclidean space via random walks on the nodes of the graph. In VEC-NBT, we modify the original algorithm to use a non-backtracking random walk instead of the normal backtracking random walk used in VEC. We introduce a modification to a non-backtracking random walk, which we call a begrudgingly-backtracking random walk, and show empirically that using this model of random walks for VEC-NBT requires shorter walks on the graph to obtain results with comparable or greater accuracy than VEC, especially for sparser graphs.