Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer

Summary: Introduces a divide-and-conquer algorithm for locally h-clique densest subgraph discovery, avoiding redundant computation while enumerating multiple locally optimal dense regions. Experiments on 15 large graphs show up to 100× speedups over the state of the art. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: h97f4676ba3a17b32
Venue: VLDB
Year: 2026
Pagerank: 4.9605343e-05
Overall Rank: 10,879 | 27.08%
DOI: 10.14778/3828612.3828616
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

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

Authors

1. Yingli Zhou (Chinese University of Hong Kong)
2. Taohua Huang (Xidian University)
3. Yixiang Fang (Chinese University of Hong Kong)

BibTeX Citation

@article{zhou_vldb26,
        title = {{Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer}},
        author = {Zhou, Yingli and Huang, Taohua and Fang, Yixiang},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {10},
        pages = {2577--2590},
        doi = {10.14778/3828612.3828616},
        url = {https://doi.org/10.14778/3828612.3828616},
        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 28 of 28 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
130	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.0003029792
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022625826
560	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00016408664
580	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00016057466
978	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00012699423
1,198	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011541919
1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2189157e-05
2,072	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0668141e-05
2,900	Piggybacking on Social Networks	2013	VLDB	7.8819591e-05
2,926	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	7.837861e-05
3,170	On Querying Historical K-Cores	2021	VLDB	7.5572564e-05
3,396	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	7.3277458e-05
3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	7.0037629e-05
4,377	Anchored Densest Subgraph	2022	SIGMOD	6.6166943e-05
4,944	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	6.3297928e-05
5,575	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	6.0626208e-05
6,226	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8266364e-05
6,666	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.698709e-05
7,832	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	5.4289543e-05
7,851	Densest Multipartite Subgraph Search in Heterogeneous Information Networks	2024	VLDB	5.4232533e-05
8,993	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD	5.2288673e-05
9,004	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	5.2256037e-05
9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.0910746e-05
10,520	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD	4.9605343e-05
10,636	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.9605343e-05
11,284	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.9605343e-05
11,383	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.9605343e-05
11,966	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,377	Anchored Densest Subgraph	2022	SIGMOD
2	10,499	Bound-Tightened Densest Subgraph Discovery on GPU	2026	SIGMOD
3	9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB
4	3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
5	7,832	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD
6	10,520	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD
7	2,926	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB
8	1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
9	11,383	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB
10	8,993	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD