Efficient Dense Diverse Subgraph Search in Attributed Graphs
摘要
Given a user-specified query vertex, the task of finding a cohesive subgraph containing the query, known as subgraph search, is fundamental in graph analytics and has numerous applications. In many real-world graphs, vertices are associated with attributes. Though subgraph search in such attributed graphs has been extensively studied, most existing approaches emphasize structural and attribute cohesiveness, often overlooking the representation of minority groups. When vertices carry sensitive attributes such as race, gender, or political opinion, this can lead to biased and unrepresentative subgraphs. Therefore, we investigate the problem of diverse subgraph search, which aims to identify a dense subgraph containing a query vertex while ensuring attribute diversity. Specifically, we formulate the problem of densest at-least- \(\boldsymbol{k}\) subgraph search ( ). Despite its NP-hardness, we develop two efficient approximation algorithms to address the problem. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of our algorithms, underscoring the practical value of our study.