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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient Dense Diverse Subgraph Search in Attributed Graphs

  • Luyao Gao,
  • Sijin Wang,
  • Yikai Zhang,
  • Can Lu

摘要

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.