  Cohesive subgraph mining on attributed graphs is a fundamental problem in
graph data analysis. Existing cohesive subgraph 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
three novel fairness-aware maximal clique models on attributed graphs, called
weak fair clique, strong fair clique and relative 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
enumerations. To enumerate all relative fair cliques, we design an enhanced
colorful k-core based pruning technique for 2D attribute, and then develop two
efficient search algorithms: RFCRefineEnum and RFCAlterEnum based on the ideas
of WFCEnum and SFCEnum for arbitrary dimension attribute. The results of
extensive experiments on four real-world graphs demonstrate the efficiency,
scalability and effectiveness of the proposed algorithms.
