Counting Small Balanced (p,q)-bicliques in Signed Bipartite Graphs
Pith reviewed 2026-05-07 14:18 UTC · model grok-4.3
The pith
A vertex-based pruning algorithm counts small balanced (p,q)-bicliques in signed bipartite graphs orders of magnitude faster than adapted baselines.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We adapt the state-of-the-art unsigned biclique counter BCList++ into SBCList++ to handle edge signs, then introduce BBWC, which enforces balance during wedge enumeration, and BBVP, which directly enumerates feasible vertex sets with early pruning; on large real-world signed bipartite graphs BBVP achieves an average speedup of 636 times over SBCList++ when counting balanced (3,3)-bicliques.
What carries the argument
BBVP, the vertex-based pruning algorithm that directly enumerates candidate vertex sets while checking sign balance to discard invalid combinations early.
If this is right
- Higher-order balanced motif analysis becomes feasible on networks with millions of edges.
- The same pruning idea can be applied to other small fixed-size signed motifs beyond (p,q)-bicliques.
- Applications in biology and recommender systems gain practical tools for detecting balanced multi-entity relationships.
- Balance constraints integrated at the enumeration step yield consistent gains over post-processing approaches.
Where Pith is reading between the lines
- The pruning strategy may extend to counting other signed substructures such as balanced cycles or clusters.
- If graphs evolve over time, incremental versions of BBVP could maintain counts with low update cost.
- The efficiency gain suggests that explicit balance checking during search is cheaper than separate verification after enumeration.
Load-bearing premise
The input signed bipartite graphs contain enough structure that most invalid vertex sets can be pruned early without the pruning checks themselves becoming a bottleneck.
What would settle it
A signed bipartite graph on which BBVP either returns a different count from exhaustive enumeration or runs slower than SBCList++ would falsify the performance claim.
read the original abstract
Two disjoint sets of entities and their relationship can be modelled as a bipartite graph. Real-life examples include drug-target interaction in biological networks, user-item relationships in e-commerce networks, etc. Motif-based analysis is essential for understanding the structure of large-scale networks, and bipartite graphs are no exception. In contrast to unsigned graphs, motif analysis in signed bipartite graphs has received limited attention. The smallest non-trivial motif in a signed bipartite graph is a balanced (2,2)-biclique, often called a balanced butterfly, which captures only local patterns and cannot reveal higher-order relationships. Bipartite motifs have been studied in the literature in the context of signed bipartite graphs, such as maximal biclique, bitruss, and so on. None of these works addresses bipartite motifs with fixed-sized vertex sets, which are often relevant in practical situations. In this work, we study the balanced (p,q)-biclique counting problem for small values of p and q. As a baseline, we first adapt and extend the state-of-the-art BCList++ algorithm for unsigned bipartite graphs to incorporate edge signs, which we call SBCList++. We then propose two efficient algorithms: BBWC, a wedge-centric approach that enforces balance constraints during enumeration, and BBVP, a vertex-based pruning approach that directly enumerates feasible vertex sets. Extensive experiments on large real-world datasets demonstrate that the vertex-based pruning algorithm, BBVP, significantly outperforms the baseline, achieving an average speedup of 636$\times$ over SBCList++ (where p=q=3).
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript addresses the balanced (p,q)-biclique counting problem in signed bipartite graphs. It adapts the BCList++ algorithm for unsigned graphs to produce the signed baseline SBCList++, then introduces two new algorithms: BBWC (wedge-centric enumeration that enforces balance constraints during the process) and BBVP (direct enumeration of feasible vertex sets via vertex-based pruning). The central empirical claim is that BBVP substantially outperforms the baseline on large real-world signed bipartite graphs, with an average speedup of 636× for the case p = q = 3.
Significance. If the reported speedups and correctness arguments hold, the work is a useful practical contribution to motif analysis in signed networks, filling a gap between local patterns such as balanced butterflies and higher-order fixed-size bicliques relevant to biological and e-commerce applications. Strengths include the provision of pseudocode, explicit arguments for the pruning rules, and direct empirical timing comparisons against an explicitly adapted baseline. The absence of theoretical runtime bounds or a formal theorem statement for overall correctness limits the theoretical impact, but the empirical focus aligns with the algorithmic design contribution.
minor comments (2)
- The experimental description does not specify dataset characteristics (vertex/edge counts, sign distributions) or edge-case handling details, which would strengthen reproducibility of the 636× speedup claim.
- A short formal definition of a balanced (p,q)-biclique and the precise balance condition used should appear in the preliminaries to avoid any ambiguity in the enumeration rules.
Simulated Author's Rebuttal
We thank the referee for the constructive review and the recommendation for minor revision. We appreciate the recognition of the practical contribution of BBVP, the provision of pseudocode and pruning arguments, and the direct comparisons to the adapted baseline. We address the primary limitation noted in the report below.
read point-by-point responses
-
Referee: The absence of theoretical runtime bounds or a formal theorem statement for overall correctness limits the theoretical impact.
Authors: We acknowledge this observation. Our emphasis is on practical, scalable algorithms for real-world signed bipartite graphs, consistent with much of the motif-counting literature where output-sensitive enumeration is the focus. In the revised manuscript we will add an explicit theorem stating the correctness of BBWC and BBVP (with a proof outline based on the pruning invariants already described in the text) together with a short discussion of the algorithms' time complexity in terms of the number of candidate wedges and vertex sets processed. We believe this addresses the concern while preserving the empirical orientation of the work. revision: yes
Circularity Check
No significant circularity; algorithmic design and empirical evaluation are self-contained
full rationale
The manuscript describes two new algorithms (BBWC and BBVP) for enumerating balanced (p,q)-bicliques, an adaptation of an external baseline (SBCList++ from BCList++), pseudocode for pruning rules, and correctness arguments. Central performance claims are empirical speedups measured on real-world datasets against the explicitly adapted baseline. No equations, fitted parameters, or predictions reduce to inputs by construction; no self-citation chains support load-bearing uniqueness or ansatz claims. The derivation chain consists of standard algorithmic steps (wedge enumeration, vertex pruning, balance checks) that are independently verifiable from the supplied pseudocode and do not rely on self-referential definitions.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Standard definition of a balanced signed biclique (product of edge signs is positive or even number of negative edges).
Reference graph
Works this paper leans on
-
[1]
The Journal of psychology , volume=
Attitudes and cognitive organization , author=. The Journal of psychology , volume=. 1946 , publisher=
work page 1946
-
[2]
Proceedings of the VLDB Endowment , volume=
Identifying similar-bicliques in bipartite graphs , author=. Proceedings of the VLDB Endowment , volume=. 2022 , publisher=
work page 2022
-
[3]
Proceedings of the VLDB Endowment , year=
Maximum biclique search at billion scale , author=. Proceedings of the VLDB Endowment , year=
-
[4]
Proceedings of the VLDB Endowment , volume=
Efficient maximal biclique enumeration for large sparse bipartite graphs , author=. Proceedings of the VLDB Endowment , volume=. 2022 , publisher=
work page 2022
-
[5]
Proceedings of the VLDB Endowment , volume =
Kai Hiu Chung and Alexander Zhou and Yue Wang and Lei Chen , title =. Proceedings of the VLDB Endowment , volume =. 2023 , doi =
work page 2023
-
[6]
Accelerated butterfly counting with vertex priority on bipartite graphs , author=. The VLDB Journal , volume=. 2023 , publisher=
work page 2023
-
[7]
K. Wang and X. Lin and L. Qin and W. Zhang and Y. Zhang , title =. The VLDB Journal , pages =
-
[8]
IEEE Transactions on Knowledge and Data Engineering , volume=
Maximum Signed -Clique Identification in Large Signed Graphs , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2021 , publisher=
work page 2021
- [9]
-
[10]
IEEE Transactions on Knowledge and Data Engineering , volume=
Efficient Maximal Biclique Enumeration on Large Signed Bipartite Graphs , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2024 , publisher=
work page 2024
-
[11]
Advances in artificial intelligence , volume=
A survey of collaborative filtering techniques , author=. Advances in artificial intelligence , volume=. 2009 , publisher=
work page 2009
-
[12]
2014 IEEE International Congress on Big Data , pages=
Rectangle counting in large bipartite graphs , author=. 2014 IEEE International Congress on Big Data , pages=. 2014 , organization=
work page 2014
-
[13]
Journal of Complex Networks , volume=
Measuring and modeling bipartite graphs with community structure , author=. Journal of Complex Networks , volume=. 2017 , publisher=
work page 2017
-
[14]
Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining , pages=
Peeling bipartite networks for dense subgraph discovery , author=. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining , pages=
-
[15]
Butterfly counting and bitruss decomposition on uncertain bipartite graphs , author=. The VLDB Journal , volume=. 2023 , publisher=
work page 2023
-
[16]
Proceedings of the VLDB Endowment , volume=
Efficient bi-triangle counting for large bipartite networks , author=. Proceedings of the VLDB Endowment , volume=. 2021 , publisher=
work page 2021
-
[17]
Triadic closure in two-mode networks: Redefining the global and local clustering coefficients , author=. Social networks , volume=. 2013 , publisher=
work page 2013
-
[18]
IEEE Transactions on Knowledge and Data Engineering , year=
Fast Counting and Utilizing Induced 6-Cycles in Bipartite Networks , author=. IEEE Transactions on Knowledge and Data Engineering , year=
-
[19]
Fleet: Butterfly estimation from a bipartite graph stream , author=. Proceedings of the 28th ACM International Conference on Information and Knowledge Management , pages=
-
[20]
(p, q)-biclique counting and enumeration for large sparse bipartite graphs , author=. The VLDB Journal , volume=. 2023 , publisher=
work page 2023
-
[21]
Scalable large near-clique detection in large-scale networks via sampling , author=. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages=
-
[22]
Network analysis of 2-mode data , author=. Social networks , volume=. 1997 , publisher=
work page 1997
-
[23]
2020 IEEE 36th International Conference on Data Engineering (ICDE) , pages=
Efficient bitruss decomposition for large-scale bipartite graphs , author=. 2020 IEEE 36th International Conference on Data Engineering (ICDE) , pages=. 2020 , organization=
work page 2020
-
[24]
Balance in signed bipartite networks , author=. Proceedings of the 28th ACM International Conference on Information and Knowledge Management , pages=
-
[25]
International Conference on Database Systems for Advanced Applications , pages=
Discovering cliques in signed networks based on balance theory , author=. International Conference on Database Systems for Advanced Applications , pages=. 2020 , organization=
work page 2020
-
[26]
Reviews of modern physics , volume=
Statistical mechanics of complex networks , author=. Reviews of modern physics , volume=. 2002 , publisher=
work page 2002
-
[27]
Finding and evaluating community structurein networks , author=. Physical review E , volume=
-
[28]
Discovering functions and revealing mechanisms at molecular level from biological networks , author=. Proteomics , volume=. 2007 , publisher=
work page 2007
-
[29]
Food web models: a plea for groups , author=. Ecology letters , volume=. 2009 , publisher=
work page 2009
-
[30]
Briefings in bioinformatics , volume=
Exploiting drug--disease relationships for computational drug repositioning , author=. Briefings in bioinformatics , volume=. 2011 , publisher=
work page 2011
-
[31]
Computational genetic neuroanatomy of the developing mouse brain: dimensionality reduction, visualization, and clustering , author=. BMC bioinformatics , volume=. 2013 , publisher=
work page 2013
-
[32]
Bioinformatics advances , volume=
Biclique extension as an effective approach to identify missing links in metabolic compound--protein interaction networks , author=. Bioinformatics advances , volume=. 2022 , publisher=
work page 2022
-
[33]
Molecular systems biology , volume=
Systematic mapping of protein-metabolite interactions in central metabolism of Escherichia coli , author=. Molecular systems biology , volume=
-
[34]
A map of protein-metabolite interactions reveals principles of chemical communication , author=. Cell , volume=. 2018 , publisher=
work page 2018
-
[35]
Bipartite graph capsule network , author=. World Wide Web , volume=. 2023 , publisher=
work page 2023
-
[36]
Motifs in bipartite ecological networks: uncovering indirect interactions , author=. Oikos , volume=. 2019 , publisher=
work page 2019
-
[37]
Network motifs: simple building blocks of complex networks , author=. Science , volume=. 2002 , publisher=
work page 2002
-
[38]
Frontiers in pharmacology , volume=
Network-based methods for prediction of drug-target interactions , author=. Frontiers in pharmacology , volume=. 2018 , publisher=
work page 2018
-
[39]
Artificial Intelligence Review , pages=
Fuzzy community detection on the basis of similarities in structural/attribute in large-scale social networks , author=. Artificial Intelligence Review , pages=. 2022 , publisher=
work page 2022
-
[40]
2018 IEEE International Conference on Data Mining Workshops (ICDMW) , pages=
Congressional vote analysis using signed networks , author=. 2018 IEEE International Conference on Data Mining Workshops (ICDMW) , pages=. 2018 , organization=
work page 2018
-
[41]
Multi-factor congressional vote prediction , author=. Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining , pages=
work page 2019
- [42]
- [43]
-
[44]
Cohesive subgraph detection in large bipartite networks , author=. Proceedings of the 32nd International Conference on Scientific and Statistical Database Management , pages=
-
[45]
Butterfly counting in bipartite networks , author=. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , pages=
-
[46]
Proceedings of the VLDB Endowment , volume=
Efficient load-balanced butterfly counting on GPU , author=. Proceedings of the VLDB Endowment , volume=. 2022 , publisher=
work page 2022
-
[47]
Proceedings of the SIGCHI conference on human factors in computing systems , pages=
Signed networks in social media , author=. Proceedings of the SIGCHI conference on human factors in computing systems , pages=
-
[48]
ACM Computing Surveys (CSUR) , volume=
A survey of signed network mining in social media , author=. ACM Computing Surveys (CSUR) , volume=. 2016 , publisher=
work page 2016
-
[49]
Proceedings of the 2017 SIAM international conference on data mining , pages=
Signed network embedding in social media , author=. Proceedings of the 2017 SIAM international conference on data mining , pages=. 2017 , organization=
work page 2017
-
[50]
2018 IEEE 34th International Conference on Data Engineering (ICDE) , pages=
Efficient signed clique search in signed networks , author=. 2018 IEEE 34th International Conference on Data Engineering (ICDE) , pages=. 2018 , organization=
work page 2018
-
[51]
Proceedings of the 29th ACM International Conference on Information & Knowledge Management , pages=
Community identification in signed networks: a k-truss based model , author=. Proceedings of the 29th ACM International Conference on Information & Knowledge Management , pages=
-
[52]
Drug combinatorics and side effect estimation on the signed human drug-target network , author=. BMC systems biology , volume=. 2016 , publisher=
work page 2016
-
[53]
Decision Support Systems , volume=
Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach , author=. Decision Support Systems , volume=. 2013 , publisher=
work page 2013
-
[54]
Paper recommendation based on author-paper interest and graph structure , author=. 2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD) , pages=. 2021 , organization=
work page 2021
-
[55]
Proceedings of the ACM on Management of Data , volume=
Efficient Core Maintenance in Large Bipartite Graphs , author=. Proceedings of the ACM on Management of Data , volume=. 2023 , publisher=
work page 2023
-
[56]
International conference on database systems for advanced applications , pages=
Bitruss decomposition of bipartite graphs , author=. International conference on database systems for advanced applications , pages=. 2016 , organization=
work page 2016
-
[57]
IEEE Transactions on Knowledge and Data Engineering , volume=
Higher-order truss decomposition in graphs , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2021 , publisher=
work page 2021
-
[58]
2022 IEEE 38th International Conference on Data Engineering (ICDE) , pages=
Maximal balanced signed biclique enumeration in signed bipartite graphs , author=. 2022 IEEE 38th International Conference on Data Engineering (ICDE) , pages=. 2022 , organization=
work page 2022
-
[59]
Theoretical Computer Science , volume=
A new decomposition technique for maximal clique enumeration for sparse graphs , author=. Theoretical Computer Science , volume=. 2019 , publisher=
work page 2019
-
[60]
2019 IEEE 35th International Conference on Data Engineering (ICDE) , pages=
Efficient maximal spatial clique enumeration , author=. 2019 IEEE 35th International Conference on Data Engineering (ICDE) , pages=. 2019 , organization=
work page 2019
-
[61]
On the enumeration of maximal ( , )-cliques of a temporal network , author=. Proceedings of the ACM India Joint International Conference on Data Science and Management of Data , pages=
-
[62]
ACM Transactions on Database Systems (TODS) , volume=
Finding maximal cliques in massive networks , author=. ACM Transactions on Database Systems (TODS) , volume=. 2011 , publisher=
work page 2011
-
[63]
2024 IEEE International Conference on Big Data (BigData) , pages=
Efficient counting of balanced (2, k)-bicliques in Signed Bipartite Graphs , author=. 2024 IEEE International Conference on Big Data (BigData) , pages=. 2024 , organization=
work page 2024
-
[64]
Proceedings of The Web Conference 2020 , pages=
Efficient maximal balanced clique enumeration in signed networks , author=. Proceedings of The Web Conference 2020 , pages=
work page 2020
-
[65]
Parallelizing maximal clique enumeration over graph data , author=. Database Systems for Advanced Applications: 21st International Conference, DASFAA 2016, Dallas, TX, USA, April 16-19, 2016, Proceedings, Part II 21 , pages=. 2016 , organization=
work page 2016
-
[66]
2018 IEEE 25th International Conference on High Performance Computing (HiPC) , pages=
Shared-memory parallel maximal clique enumeration , author=. 2018 IEEE 25th International Conference on High Performance Computing (HiPC) , pages=. 2018 , organization=
work page 2018
-
[67]
IEEE Transactions on Parallel and Distributed Systems , volume=
Accelerating the Bron-Kerbosch algorithm for maximal clique enumeration using GPUs , author=. IEEE Transactions on Parallel and Distributed Systems , volume=. 2021 , publisher=
work page 2021
-
[68]
2010 IEEE International Conference on Data Mining Workshops , pages=
dmaximalcliques: A distributed algorithm for enumerating all maximal cliques and maximal clique distribution , author=. 2010 IEEE International Conference on Data Mining Workshops , pages=. 2010 , organization=
work page 2010
-
[69]
SIAM Journal on Computing , volume=
The enumeration of maximal cliques of large graphs , author=. SIAM Journal on Computing , volume=. 1973 , publisher=
work page 1973
-
[70]
Communications of the ACM , volume=
Algorithm 457: finding all cliques of an undirected graph , author=. Communications of the ACM , volume=. 1973 , publisher=
work page 1973
-
[71]
The Network Data Repository with Interactive Graph Analytics and Visualization , author=. AAAI , url=
-
[72]
Information processing letters , volume=
Arboricity and bipartite subgraph listing algorithms , author=. Information processing letters , volume=. 1994 , publisher=
work page 1994
-
[73]
IEEE Transactions on Knowledge and Data Engineering , volume=
Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2007 , publisher=
work page 2007
-
[74]
On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types , author=. BMC bioinformatics , volume=. 2014 , publisher=
work page 2014
- [75]
-
[76]
Proceedings of the VLDB Endowment , volume=
(p, q)-biclique counting and enumeration for large sparse bipartite graphs , author=. Proceedings of the VLDB Endowment , volume=. 2021 , publisher=
work page 2021
-
[77]
Proceedings of the 2021 International Conference on Management of Data , pages=
Efficient exact algorithms for maximum balanced biclique search in bipartite graphs , author=. Proceedings of the 2021 International Conference on Management of Data , pages=
work page 2021
-
[78]
Proceedings of the 2016 SIAM International Conference on Data Mining , pages=
On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach , author=. Proceedings of the 2016 SIAM International Conference on Data Mining , pages=. 2016 , organization=
work page 2016
-
[79]
Scale reduction techniques for computing maximum induced bicliques , author=. Algorithms , volume=. 2017 , publisher=
work page 2017
-
[80]
IEEE Transactions on Knowledge and Data Engineering , year=
Efficient balanced signed biclique search in signed bipartite graphs , author=. IEEE Transactions on Knowledge and Data Engineering , year=
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.