Recognition: unknown
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=
1946
-
[2]
Proceedings of the VLDB Endowment , volume=
Identifying similar-bicliques in bipartite graphs , author=. Proceedings of the VLDB Endowment , volume=. 2022 , publisher=
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=
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 =
2023
-
[6]
The VLDB Journal , volume=
Accelerated butterfly counting with vertex priority on bipartite graphs , author=. The VLDB Journal , volume=. 2023 , publisher=
2023
-
[7]
Wang and X
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=
2021
-
[9]
Shi and J
J. Shi and J. Shun , title =. Symposium on Algorithmic Principles of Computer Systems (APoCS) , pages =
-
[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=
2024
-
[11]
Advances in artificial intelligence , volume=
A survey of collaborative filtering techniques , author=. Advances in artificial intelligence , volume=. 2009 , publisher=
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=
2014
-
[13]
Journal of Complex Networks , volume=
Measuring and modeling bipartite graphs with community structure , author=. Journal of Complex Networks , volume=. 2017 , publisher=
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]
The VLDB Journal , volume=
Butterfly counting and bitruss decomposition on uncertain bipartite graphs , author=. The VLDB Journal , volume=. 2023 , publisher=
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=
2021
-
[17]
Social networks , volume=
Triadic closure in two-mode networks: Redefining the global and local clustering coefficients , author=. Social networks , volume=. 2013 , publisher=
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]
Proceedings of the 28th ACM International Conference on Information and Knowledge Management , pages=
Fleet: Butterfly estimation from a bipartite graph stream , author=. Proceedings of the 28th ACM International Conference on Information and Knowledge Management , pages=
-
[20]
The VLDB Journal , volume=
(p, q)-biclique counting and enumeration for large sparse bipartite graphs , author=. The VLDB Journal , volume=. 2023 , publisher=
2023
-
[21]
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages=
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]
Social networks , volume=
Network analysis of 2-mode data , author=. Social networks , volume=. 1997 , publisher=
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=
2020
-
[24]
Proceedings of the 28th ACM International Conference on Information and Knowledge Management , pages=
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=
2020
-
[26]
Reviews of modern physics , volume=
Statistical mechanics of complex networks , author=. Reviews of modern physics , volume=. 2002 , publisher=
2002
-
[27]
Physical review E , volume=
Finding and evaluating community structurein networks , author=. Physical review E , volume=
-
[28]
Proteomics , volume=
Discovering functions and revealing mechanisms at molecular level from biological networks , author=. Proteomics , volume=. 2007 , publisher=
2007
-
[29]
Ecology letters , volume=
Food web models: a plea for groups , author=. Ecology letters , volume=. 2009 , publisher=
2009
-
[30]
Briefings in bioinformatics , volume=
Exploiting drug--disease relationships for computational drug repositioning , author=. Briefings in bioinformatics , volume=. 2011 , publisher=
2011
-
[31]
BMC bioinformatics , volume=
Computational genetic neuroanatomy of the developing mouse brain: dimensionality reduction, visualization, and clustering , author=. BMC bioinformatics , volume=. 2013 , publisher=
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=
2022
-
[33]
Molecular systems biology , volume=
Systematic mapping of protein-metabolite interactions in central metabolism of Escherichia coli , author=. Molecular systems biology , volume=
-
[34]
Cell , volume=
A map of protein-metabolite interactions reveals principles of chemical communication , author=. Cell , volume=. 2018 , publisher=
2018
-
[35]
World Wide Web , volume=
Bipartite graph capsule network , author=. World Wide Web , volume=. 2023 , publisher=
2023
-
[36]
Oikos , volume=
Motifs in bipartite ecological networks: uncovering indirect interactions , author=. Oikos , volume=. 2019 , publisher=
2019
-
[37]
Science , volume=
Network motifs: simple building blocks of complex networks , author=. Science , volume=. 2002 , publisher=
2002
-
[38]
Frontiers in pharmacology , volume=
Network-based methods for prediction of drug-target interactions , author=. Frontiers in pharmacology , volume=. 2018 , publisher=
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=
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=
2018
-
[41]
Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining , pages=
Multi-factor congressional vote prediction , author=. Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining , pages=
2019
-
[42]
, author=
Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks. , author=. PVLDB , year=
-
[43]
, author=
Structural balance: a generalization of Heider's theory. , author=. Psychological review , volume=. 1956 , publisher=
1956
-
[44]
Proceedings of the 32nd International Conference on Scientific and Statistical Database Management , pages=
Cohesive subgraph detection in large bipartite networks , author=. Proceedings of the 32nd International Conference on Scientific and Statistical Database Management , pages=
-
[45]
Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , pages=
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=
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=
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=
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=
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]
BMC systems biology , volume=
Drug combinatorics and side effect estimation on the signed human drug-target network , author=. BMC systems biology , volume=. 2016 , publisher=
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=
2013
-
[54]
2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD) , pages=
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=
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=
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=
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=
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=
2022
-
[59]
Theoretical Computer Science , volume=
A new decomposition technique for maximal clique enumeration for sparse graphs , author=. Theoretical Computer Science , volume=. 2019 , publisher=
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=
2019
-
[61]
Proceedings of the ACM India Joint International Conference on Data Science and Management of Data , pages=
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=
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=
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=
2020
-
[65]
Database Systems for Advanced Applications: 21st International Conference, DASFAA 2016, Dallas, TX, USA, April 16-19, 2016, Proceedings, Part II 21 , pages=
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=
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=
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=
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=
2010
-
[69]
SIAM Journal on Computing , volume=
The enumeration of maximal cliques of large graphs , author=. SIAM Journal on Computing , volume=. 1973 , publisher=
1973
-
[70]
Communications of the ACM , volume=
Algorithm 457: finding all cliques of an undirected graph , author=. Communications of the ACM , volume=. 1973 , publisher=
1973
-
[71]
AAAI , url=
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=
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=
2007
-
[74]
BMC bioinformatics , volume=
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=
2014
-
[75]
, author=
Pivot-based Maximal Biclique Enumeration. , author=. IJCAI , pages=
-
[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=
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=
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=
2016
-
[79]
Algorithms , volume=
Scale reduction techniques for computing maximum induced bicliques , author=. Algorithms , volume=. 2017 , publisher=
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.