Effective fairest community search over heterogeneous information networks
Abstract
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.
Keywords
community search, fairness community, heterogeneous information network
Document Type
Conference Proceeding
Date of Publication
1-1-2026
Publication Title
2026 IEEE 42nd International Conference on Data Engineering (ICDE)
Publisher
IEEE
School
School of Business and Law
Funding received from the Australian Research Council (ARC)
DP240101591, LP180100750
Administering Institution
Edith Cowan University
ISBN
[9798331583651]
Copyright
free_to_read
First Page
1073
Last Page
1085
Recommended Citation
Zhao, T., Li, J., Li, M., Luo, W., Cheng, J., Miao, Y., & Wang, H. (2026). Effective fairest community search over heterogeneous information networks. In 2026 IEEE 42nd International Conference on Data Engineering (ICDE) (pp. 1073-1085). IEEE. https://doi.org/10.1109/ICDE65706.2026.00085