Accelerating DeepWalk via Context-Level Parameter Update and Huffman Tree Pruning

As a classic unsupervised graph representation learning algorithm, DeepWalk is widely used in various tasks. DeepWalk consists of random walk and Word2Vec-based training, and the latter is more time-consuming due to large-scale softmax computation. To address this, many approximation methods have been proposed. Among them, sampling-based methods struggle to achieve satisfactory accuracy due to large sampling variance and the mismatch between sampling and true distribution. For softmax-based methods, their training efficiency is not high. To this end, we propose CLPU and HTP to reduce redundant operations in these methods. Firstly, we observe that there exist multiple updates for the same node within one window. Based on this, CLPU counts node occurrences and label contributions, and then performs parameter update only once. Secondly, we delve into whether it is necessary to update Huffman tree’s upper-level nodes multiple times and propose HTP: focusing on a few auxiliary nodes before leaves instead of the whole traversal path from root, which reduces time complexity from logarithmic to constant. Experiments on 14 datasets demonstrate that CLPU and HTP achieve a speed improvement of 1.9x-2.8x and 2.8x-4.3x, while surpassing other methods in terms of accuracy.