Fair Group Summarization with Graph Patterns
Fair Group Summarization with Graph Patterns
复制标题
DOI：
10.1109/icde55515.2023.00154
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Hanchao Ma;Sheng Guan;Mengying Wang;Qi Song;Yinghui Wu
中科院分区：
文献类型：
--
作者：
Hanchao Ma;Sheng Guan;Mengying Wang;Qi Song;Yinghui Wu
给定图中的一组节点组（例如，性别或种族群体），如何简洁地概括他们的邻居，同时确保一个“公平”的代表，以减轻某一群体的代表不足或过度？我们提出了一个新的框架来计算简明摘要的节点组的公平性保证。(1)我们引入了一种称为r-summaries的模式校正结构。一个r-摘要使用一个图形模式集来指定代表节点和一个辅助边缘校正集来描述它们的r-跳邻居。(2)我们制定了公平的组摘要问题，这是计算一个r-总结，可以选择和准确地描述高质量的节点和他们的邻居与小的边缘校正，同时保证一个理想的覆盖范围为每个组。在社交推荐、医疗保健和图形搜索中，生成这种摘要的需求是显而易见的。我们证明该问题是$\Sigma _2^p$-完全的，而验证问题已经是NP-完全的。(3)我们提出了近似算法，可以生成r-摘要（a）保证质量和覆盖特性，和（B）相对近似的最佳边缘校正成本。对于大的群体，我们引入了一个有效的算法，交错节点选择和本地化的模式发现，以减少不必要的计算。此外，我们引入了一个算法，以递增地维护的r-摘要动态图与不断发展的边缘。使用真实世界的数据，我们实验验证了我们的算法的效率和有效性，并验证其应用。
Given a set of node groups in a graph (e.g., gender or race groups), how to succinctly summarize their neighbors, and meanwhile ensure a "fair" representation to mitigate under- or over-representation of a certain group? We propose a novel framework to compute concise summaries of node groups with fairness guarantees. (1) We introduce a pattern-correction structure called r-summaries. An r-summary uses a graph pattern set to specify representative nodes and an auxiliary edge correction set to losslessly describe their r-hop neighbors. (2) We formulate the fair group summarization problem, which is to compute an r-summary that can select and accurately describe high quality nodes and their neighbors with small edge corrections, and meanwhile guarantee a desirable coverage for each group. The need for generating such summaries is evident in social recommendation, healthcare and graph search. We show that the problem is $\Sigma _2^p$-complete with the verification problem already NP-complete. (3) We present approximation algorithms that can generate r-summaries with (a) guaranteed quality and coverage properties, and (b) relative approximations on optimal edge correction costs. For large groups, we introduce an efficient algorithm that interleaves node selection and localized pattern discovery to reduce unnecessary computation. In addition, we introduce an algorithm to incrementally maintain the r-summaries over dynamic graphs with evolving edges. Using real-world data, we experimentally verify the efficiency and effectiveness of our algorithms and verify their applications.