Diversified Subgraph Query Generation with Group Fairness
Diversified Subgraph Query Generation with Group Fairness
复制标题
DOI：
10.1145/3488560.3498525
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Hanchao Ma;Sheng Guan;Christopher Toomey;Yinghui Wu
中科院分区：
文献类型：
--
作者：
Hanchao Ma;Sheng Guan;Christopher Toomey;Yinghui Wu
研究了输出满足多样性和公平性约束的子图查询生成问题。给定一组具有相关基数要求的组，计算具有多样化输出的子图查询，同时覆盖具有所需基数的组。这种需求在具有公平性约束的网络和社交搜索中是显而易见的。我们将子图查询生成问题形式化为一个基于查询多样性和公平性的双准则优化问题，并验证了其困难性和可逼近性。我们表明，问题是在NIP2，即使是单节点查询，仍然是NP完全的。尽管困难，（1）我们表明，近似存在时，相应的子集选择过程提供了良好的解决方案，并提供可行的算法与性能保证两个实际的查询生成场景。我们还提出了一个快速的启发式算法的一般问题，提前终止没有枚举查询。我们的实验验证，我们的算法可以有效地生成查询所需的多样性和覆盖特性的目标群体。
This paper investigates the problem of subgraph query generation with output that satisfies both diversity and fairness constraints. Given a set of groups with associated cardinality requirements, it is to compute subgraph queries with diversified output that meanwhile covers the groups with the desired cardinality. Such need is evident in web and social search with fairness constraints. We formalize subgraph query generation as a bi-criteria optimization problem on the diversity and fairness properties of queries, and verify its hardness and approximability. We show that the problem is in Σp2 , and remains NP-complete even for single-node queries. Despite the hardness, (1) we show that approximations exist whenever a corresponding subset selection process provides good solutions, and provide feasible algorithms with performance guarantees for two practical query generation scenarios. We also present a fast heuristic algorithm for the general problem, which early terminates without enumerating queries. We experimentally verify that our algorithms can efficiently generate queries with desired diversity and coverage properties for targeted groups.