Subgraph Query Generation with Fairness and Diversity Constraints
Subgraph Query Generation with Fairness and Diversity Constraints
复制标题
DOI：
10.1109/icde53745.2022.00278
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Hanchao Ma;Sheng Guan;Mengying Wang;Yen-shuo Chang;Yinghui Wu
中科院分区：
文献类型：
--
作者：
Hanchao Ma;Sheng Guan;Mengying Wang;Yen-shuo Chang;Yinghui Wu
研究了同时保证多样性和组公平性的子图查询生成问题。给定查询模板（具有参数化搜索谓词）和图中的节点组集合，计算实例化查询模板的子图查询集合，并且每个查询确保多样化的答案，同时覆盖具有期望数量的节点的每个组。这种需求在具有公平性约束、查询优化和查询基准测试的网络和社交搜索中是显而易见的。我们形式化的双标准优化问题，旨在找到一个帕累托最优的查询实例的多样性和公平性措施。我们证明了问题是在Δ$P $2中，并验证了它的硬度（NP-难和固定参数易处理）。我们提供了（1）两个有效的算法，可以近似Pareto最优集的E-支配关系，产生有界大小的代表性查询实例，和（2）一个在线算法，逐步产生和维护固定大小的E-Pareto集与小延迟时间。我们的实验验证，我们的算法可以有效地生成查询所需的多样性和覆盖特性的目标群体。
This paper studies the problem of subgraph query generation with guarantees on both diversity and group fairness. Given a query template (with parameterized search predicates) and a set of node groups in a graph, it is to compute a set of sub-graph queries that instantiate the query template, and each query ensures diversified answers that meanwhile covers each group with a desired number of nodes. Such need is evident in web and social search with fairness constraints, query optimization, and query benchmarking. We formalize a bi-criteria optimization problem that aims to find a Pareto optimal set of query instances in terms of diversity and fairness measures. We show the problem is in Δ$P$ 2 and verify its hardness (NP-hard and fixed-parameter tractable). We provide (1) two efficient algorithms that can approximate Pareto optimal sets with E-dominance relations that yield representative query instances with a bounded size, and (2) an online algorithm that progressively generates and maintains fixed-size ∊-Pareto set with small delay time. We experimentally verify that our algorithms can efficiently generate queries with desired diversity and coverage properties for targeted groups.