Embedding Both Finite and Infinite Communities on Graphs [Application Notes]

Abstract

In this paper, we introduce a new setting for graph embedding, which considers embedding communities instead of individual nodes. We find that community embedding is not only useful for community-level applications such as graph visualization but also provide an exciting opportunity to improve community detection and node classification. Specifically, we consider the interaction between community embedding and detection as a closed loop, through node embedding. On the one hand, node embedding can improve community detection since the detected communities are used to fit a community embedding. On the other hand, community embedding can be used to optimize node embedding by introducing a community-aware high-order proximity. However, in practice, the number of communities can be unknown beforehand; thus we extend our previous Community Embedding (ComE) model. We propose ComE+, a new model which handles both: the unknown truth community assignments and the unknown number of communities present in the dataset. We further develop an efficient inference algorithm for ComE+ for keeping complexity low. Our extensive evaluation shows that ComE+ improves the state-of-the-art baselines in various application tasks, e.g., community detection and node classification.