Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach

Summary: Defines MaxBPs: given a bipartite graph, find K maximal k-biplexes with the most edges, without requiring fixed per-side size constraints. Proposes Symmetric-BK branch-and-bound (FastBB, PBIE); achieves O*(gamma_k^n) with gamma_k<2 and O*(gamma_k^d) on sparse graphs; NP-hard; up to 4 orders of magnitude faster than baselines, aiding fraud-detection tasks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6968e977a4f3b345
Venue: SIGMOD
Year: 2023
Pagerank: 6.5021632e-05
Overall Rank: 4,612 | 69.00%
DOI: 10.1145/3588729

Incoming Non-self Citations Over Time

Authors

1. Kaiqiang Yu (Nanyang Technological University)
2. Cheng Long (Nanyang Technological University)

BibTeX Citation

@inproceedings{yu_sigmod23,
        title = {{Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach}},
        author = {Yu, Kaiqiang and Long, Cheng},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588729},
        url = {https://dl.acm.org/doi/10.1145/3588729},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,500	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	6.1028678e-05
5,585	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	6.0761018e-05
7,043	Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach	2023	SIGMOD	5.6141221e-05
9,677	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.1435978e-05
9,678	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.1435978e-05
10,481	Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy	2026	SIGMOD	4.9793485e-05
10,813	X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs	2026	VLDB	4.9793485e-05
10,860	Maximum Defective Biclique Search in Large Bipartite Graphs	2026	VLDB	4.9793485e-05
11,518	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
766	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00014118259
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
1,788	Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs	2021	SIGMOD	9.6317563e-05
2,320	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6448197e-05
2,325	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	8.6310032e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,552	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
2	3,189	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB
3	2,743	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB
4	766	Maximum Biclique Search at Billion Scale	2020	VLDB
5	1,788	Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs	2021	SIGMOD
6	10,599	Theoretically and Practically Efficient Maximum Biclique Search	2026	SIGMOD
7	2,320	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD
8	10,481	Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy	2026	SIGMOD
9	10,860	Maximum Defective Biclique Search in Large Bipartite Graphs	2026	VLDB
10	11,518	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD