Abstract
Cohesive sub graph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive sub graph mining algorithms on attributed graphs do not consider the fairness of attributes in the subgraph. In this paper, we for the first time introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose two novel fairness-aware maximal clique models on attributed graphs, called weak fair clique and strong fair clique respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called WFCEnum equipped with a novel colorful k-core based pruning technique. We also propose an efficient enumeration algorithm called SFCEnum to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumeration. The results of extensive experiments on four real-world graphs demonstrate the efficiency and effectiveness of the proposed algorithms.
Original language | English |
---|---|
Title of host publication | Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022 |
Publisher | IEEE Computer Society |
Pages | 259-271 |
Number of pages | 13 |
ISBN (Electronic) | 9781665408837 |
DOIs | |
Publication status | Published - 2022 |
Event | 38th IEEE International Conference on Data Engineering, ICDE 2022 - Virtual, Online, Malaysia Duration: 9 May 2022 → 12 May 2022 |
Publication series
Name | Proceedings - International Conference on Data Engineering |
---|---|
Volume | 2022-May |
ISSN (Print) | 1084-4627 |
ISSN (Electronic) | 2375-0286 |
Conference
Conference | 38th IEEE International Conference on Data Engineering, ICDE 2022 |
---|---|
Country/Territory | Malaysia |
City | Virtual, Online |
Period | 9/05/22 → 12/05/22 |
Keywords
- fairness
- graph coloring
- maximal clique