Complementary Random Walk: A New Perspective on Graph Embedding

Random-walk based graph embedding algorithms like DeepWalk and Node2Vec are widely used to learn distinguishable representations of the nodes in a network. These methods treat different walks starting from every node as sentences in language to learn latent representations. However, nodes in a unique walking sequence often appear repeatedly. This situation results in the latent representations obtained by the aforementioned algorithms cannot capture the relationship between unconnected nodes, which have similar node features and graph topology structures. In this paper, we propose Complementary Random Walk (CRW) to solve this problem and embed the nodes in a network to obtain more robust low-dimensional vectors. By conducting a K-means clustering algorithm to cluster different features extracted from the graph, we can supply the original random walk with many other walking sequences, which consist of different unconnected nodes. And those nodes are sampled from the same cluster based on graph features, such as node degree, motif features, and so on. Our experiments achieve comparable or superior performance compared with other methods, validating the effectiveness of CRW.