MPSketch: Message Passing Networks via Randomized Hashing for Efficient Attributed Network Embedding

Given a network, it is well recognized that attributed network embedding represents each node of the network in a low-dimensional space, and, thus, brings considerable benefits for numerous graph mining tasks. In practice, a diverse set of graph tasks can be processed efficiently via the compact representation that preserves content and structure information. The majority of attributed network embedding approaches, especially, the graph neural network (GNN) algorithms, are substantially costly in either time or space due to the expensive learning process, while the randomized hashing technique, locality-sensitive hashing (LSH), which does not need learning, can speedup the embedding process at the expense of losing some accuracy. In this article, we propose the MPSketch model, which bridges the performance gap between the GNN framework and the LSH framework by adopting the LSH technique to pass messages and capture high-order proximity in a larger aggregated information pool from the neighborhood. The extensive experimental results confirm that in node classification and link prediction, the proposed MPSketch algorithm enjoys performance comparable to the state-of-the-art learning-based algorithms and outperforms the existing LSH algorithms, while running faster than the GNN algorithms by 3-4 orders of magnitude. More precisely, MPSketch runs 2121, 1167, and 1155 times faster than GraphSAGE, GraphZoom, and FATNet on average, respectively.