Fairness-aware Maximal Biclique Enumeration on Bipartite Graphs
Preprint
Abstract
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 \emph{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 \nonesidebc~and \ntwosidebc~respectively. To efficiently enumerate all {\nonesidebc}s, 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 \onesideFBCEM, 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.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Fairness-aware Maximal Clique Enumeration2022
- Multi-level attention graph neural network based on co-expression gene modules for disease diagnosis and prognosisBioinformatics, 2022
- Efficient maintenance for maximal bicliques in bipartite graph streamsWorld Wide Web, 2021
- Efficient and Effective Community Search on Large-scale Bipartite Graphs2021
- Bipartite graph-based approach for clustering of cell lines by gene expression–drug response associationsBioinformatics, 2021
- New heuristic approaches for maximum balanced biclique problemInformation Sciences, 2018
- Bipartite Network Analysis of Gene Sharings in the Microbial WorldMolecular Biology and Evolution, 2018
- Fraud Prevention in Online Digital Advertising2017
- A collaborative user-centered framework for recommending items in Online Social NetworksComputers in Human Behavior, 2015
- Bicliques in Graphs I: Bounds on Their NumberCombinatorica, 2000