Fairness-aware Maximal Biclique Enumeration on Bipartite Graphs

Maximal biclique enumeration is a fundamental problem in bipartite graph data analysis. Existing biclique enumeration methods mainly focus on non-attributed bipartite graphs and also ignore the fairness of graph attributes. In this paper, we introduce the concept of fairness into the biclique model for the first time and study the problem of fairness-aware biclique enumeration. Specifically, we propose two fairness-aware biclique models, called single-side fair biclique and bi-side fair biclique respectively. To efficiently enumerate all single-side fair bicliques, we first present two non-trivial pruning techniques, called fair α-β core pruning and colorful fair α-β core pruning, to reduce the graph size without losing accuracy. Then, we develop a branch and bound algorithm, called FairBCEM, to enumerate all single-side fair bicliques on the reduced bipartite graph. To further improve the efficiency, we propose an efficient branch and bound algorithm with a carefully-designed combinatorial enumeration technique. Note that all of our techniques can also be extended to enumerate all bi-side fair bicliques. We also extend the two fairness-aware biclique models by constraining the ratio of the number of vertices of each attribute to the total number of vertices and present corresponding enumeration algorithms. Extensive experimental results on five large real-world datasets demonstrate our methods’ efficiency, effectiveness, and scalability.