Keyword-Aware Skyline Community Search on Semantics and Structure

Community search (CS) on attributed graphs has been widely studied, catering to various applications such as friend recommendation. Recent works have focused on keywordaware community search with query keywords $Q$, aiming to return the closely connected communities relating to $\boldsymbol{Q}$. To achieve the best recommendation effectiveness, the ideal community should exhibit the strong semantic relevance between attributes of its members and $Q$, the high semantic similarity in attributes among members, and the closely connected structure. However, existing works only consider partial semantics to optimize one of the semantics and structure, which cannot flexibly handle the different optimized preferences for users on the above three conditions because they cannot be optimized simultaneously. Thus, we propose a novel community model that views keyword relevance, attribute similarity, and structure closeness as three different measures. Then, we study the keyword-aware skyline community search (KSCS) problem to provide a set of communities that other communities cannot dominate in terms of the three measures above, thereby facilitating users in easily choosing interested communities from the skyline set according to their preferences. We prove that this problem is NP-hard. Next, we propose a novel top-down KSCS solution with structure-preserving vertex shrinkage to approximate results. Furthermore, we propose an efficient bottom-up solution with two search strategies: structurerelaxed vertex/edge shrinkage and similarity-guided subgraph expansion, which can significantly improve approximation guarantees. Extensive experimental studies on synthetic and realworld datasets validated the effectiveness and efficiency of our methods, where the expansion-based bottom-up method achieves a good balance between efficiency and approximation.