Maximum Defective Biclique Search in Large Bipartite Graphs

Summary: Introduces maximum edge k-defective biclique search, tolerating up to k missing edges for noisy/incomplete bipartite graphs. A pivot-enhanced branch-and-bound algorithm with reductions and bounds achieves sub-2^n worst-case complexity and up to 1000× speedups. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: hfb1404432c9ebd3c
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,860 | 26.99%
DOI: 10.14778/3836663.3836687

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Donghang Cui (Beijing Institute of Technology)
2. Rong-Hua Li (Beijing Institute of Technology)
3. Qiangqiang Dai (Beijing Institute of Technology)
4. Hongchao Qin (Beijing Institute of Technology)
5. Guoren Wang (Beijing Institute of Technology)

BibTeX Citation

@article{cui_vldb26,
        title = {{Maximum Defective Biclique Search in Large Bipartite Graphs}},
        author = {Cui, Donghang and Li, Rong-Hua and Dai, Qiangqiang and Qin, Hongchao and Wang, Guoren},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {11},
        pages = {3259--3272},
        doi = {10.14778/3836663.3836687},
        url = {https://doi.org/10.14778/3836663.3836687},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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,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,743	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	8.0679908e-05
3,860	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	6.9663663e-05
4,612	Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach	2023	SIGMOD	6.5021632e-05
5,500	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	6.1028678e-05
5,552	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	6.0860432e-05
6,914	Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance	2025	VLDB	5.6465623e-05
7,346	Spade: A Real-Time Fraud Detection Framework on Evolving Graphs	2023	VLDB	5.5461419e-05
8,374	Dupin: A Parallel Framework for Densest Subgraph Discovery in Fraud Detection on Massive Graphs	2025	SIGMOD	5.3439977e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,865	Density Decomposition of Bipartite Graphs	2025	SIGMOD
2	10,665	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD
3	3,860	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
4	10,481	Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy	2026	SIGMOD
5	8,884	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD
6	5,552	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
7	11,518	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
8	4,612	Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach	2023	SIGMOD
9	766	Maximum Biclique Search at Billion Scale	2020	VLDB
10	10,599	Theoretically and Practically Efficient Maximum Biclique Search	2026	SIGMOD