Effective Fairest Community Search Over Heterogeneous Information Networks

Community search over heterogeneous information networks has been applied to wide domains, such as activity organization and team formation. Existing studies focus on identifying groups of members that meet the minimum engagement requirements. But in reality, given a group, its members may exhibit large gaps in their engagement levels with the group. It is easy to result in unfairness among the highly engaged members and lowly engaged members if we treat these members similarly. To fill in the research gap, we formally define the problem of individual fairest community search (denoted as IFCS) over heterogeneous information networks (HINs), which aims to find a set of vertices that have the same vertex type, motif-constrained relationships, and small variation in their engagement levels. Nonetheless, it is nontrivial to handle the IFCS problem due to its NP-hardness. To address the challenge, we first propose a baseline solution to identify the satisfied results by enumerating all the community candidates and computing their fairness score. To reduce the computational cost of community enumeration, we design a message-passing based strategy to filter out the vertices that are repeatedly checked for motif constraints, and further provide an optimization strategy to reduce the number of motif instances to be computed. To accelerate the search, we also derive the upper bound of the fairness score for community candidates and present a pruning-based optimization algorithm. Lastly, we conduct extensive experiments on four real-world datasets to demonstrate the effectiveness and efficiency of our proposed IFCS methods, which achieve at least ×3 times faster than the baseline solution.