Scalable Approximate Biclique Counting over Large Bipartite Graphs

Summary: Reduce (p,q)-biclique counting to counting (p,q)-brooms — a spanning-tree proxy counted via graph-coloring and efficient dynamic programming. Use DP intermediates for unbiased sampling with provable error bounds; yields up to 8× error reduction and 50× speedup on real bipartite graphs. (summarized by gpt-5-mini on Mar 13 2026)

Paper ID: 14543
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,598 | 27.29%
DOI: 10.14778/3785297.3785301

Incoming Non-self Citations Over Time

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

Authors

1. Jingbang Chen (Chinese University of Hong Kong; SLAI)
2. Weinuo Li (Zhejiang University)
3. Yingli Zhou (Chinese University of Hong Kong)
4. Hangrui Zhou (Tsinghua University)
5. Qiuyang Mang (Chinese University of Hong Kong)
6. Can Wang (Zhejiang University)
7. Yixiang Fang (Chinese University of Hong Kong)
8. Chenhao Ma (Chinese University of Hong Kong)

BibTeX Citation

@article{chen_vldb26,
        title = {{Scalable Approximate Biclique Counting over Large Bipartite Graphs}},
        author = {Chen, Jingbang and Li, Weinuo and Zhou, Yingli and Zhou, Hangrui and Mang, Qiuyang and Wang, Can and Fang, Yixiang and Ma, Chenhao},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {4},
        pages = {576--588},
        doi = {10.14778/3785297.3785301},
        url = {https://doi.org/10.14778/3785297.3785301},
        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 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012699518
1,211	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011648789
2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.9804702e-05
2,294	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	8.7939844e-05
3,723	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.1725638e-05
3,911	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	7.0240227e-05
4,143	Efficient Biclique Counting in Large Bipartite Graphs	2023	SIGMOD	6.8760066e-05
5,427	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	6.2230767e-05
8,019	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	5.5062157e-05
9,916	Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index	2025	VLDB	5.1955087e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,268	Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy	2026	SIGMOD
2	11,173	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
3	10,446	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD
4	2,860	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB
5	10,407	Theoretically and Practically Efficient Maximum Biclique Search	2026	SIGMOD
6	3,997	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB
7	7,455	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD
8	2,294	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB
9	4,143	Efficient Biclique Counting in Large Bipartite Graphs	2023	SIGMOD
10	10,369	Estimating Biclique Counts with Accuracy Guarantees	2026	SIGMOD