Neural Community Search with Compressed Graph Embeddings

Abstract Given a graph G and a query node q, community search (CS) aims to find a cohesive subgraph from G that contains q as the desired community of q. CS is a fundamental problem in graph data analytics that has gained much research interest. Recently, a new thought of using the deep learning model to support CS has emerged. Supervised models using Graph Neural Networks are presented (i.e., neural community search). However, the lack of explicit consideration for community features results in suboptimal graph embeddings for online community inference, which adversely affects search accuracy. This motivates our solutions. (1) We first present an offline community-injected graph embedding method that incorporates community cohesiveness features into the learned node representations, ensuring the effectiveness of CS. Next, we present a self-augmented method based on KL divergence to optimize node representations. Then, we conduct an efficient online community search based on the enhanced node representations, by employing inner product operation between q and other candidate nodes. (2) To reduce the memory usage of online community search, we employ an Encoder-Decoder model that achieves nearly lossless compression of graph embeddings, while maintaining the effectiveness of online CS. Comprehensive experimental studies on eight real-world datasets show our solution's superiority on effectiveness (at least 9.6% improvement) and efficiency (one to two orders of magnitude faster). Notably, the proposed optimized solution with compressed graph embeddings achieves a comparable performance with the one without compression, while using only 15.2% (on average) of the memory usage in online community search.