Maximal Balanced Signed Biclique Enumeration in Signed Bipartite Graphs

Abstract

Maximal biclique enumeration is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, in this paper, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> , two positive integers <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tau_{U}, \tau_{V}$</tex> , a subgraph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S=(U_{S},\ V_{S},\ E_{S})$</tex> of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> is a balanced signed biclique if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$i$</tex> ) <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex> is a biclique without any unstable motif, i.e., unbalanced butterfly, and ii) <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert U_{S}\vert \geq\tau_{U}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert V_{S}\vert \geq\tau_{V}$</tex> . In this paper, we aim to enumerate all the maximal balanced signed bicliques, which is proved to be NP-hard. Moreover, due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problem directly. To construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for larger networks, novel optimized strategies are proposed to overcome the three limitations in the baseline method. Extensive experi-ments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of proposed techniques and model. Compared with the baseline approach, the optimized algorithm can achieve up to 3 orders of magnitude speedup.