Fair Group Summarization with Graph Patterns

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.