HashWalk: An efficient node classification method based on clique-compressed graph embedding

摘要

In recent years, random walk based embedding has become a popular method for node classification. However, current methods still require a huge computational cost to obtain the representation of a large number of nodes. In addition, walking methods cannot adapt well to diverse network structures. Hence, this paper proposes HashWalk to generate a clique-compressed graph that can be used in random walk based embedding for node classification. Specifically, HashWalk compresses cliques into single nodes, and these single nodes are able to inherit neighbors of cliques. As a result, HashWalk can significantly reduce the number of training nodes and computational cost. Besides, HashWalk uses the random walk mapping method to obtain walking sequences of the clique-compressed graph, which makes random walk adapt to network structure. The experimental results prove that HashWalk provides faster time efficiency and lower space complexity while ensuring the accuracy. In summary, this paper provides a fast and effective method using clique-compressed graph embedding for node classification.(c) 2022 Elsevier B.V. All rights reserved.