A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery

Summary: k-clique densest subgraph via Frank-Wolfe reformulation that replaces expensive k-clique enumeration with counting. Efficient approximation using state-of-the-art counting plus optimizations; up to 10^7× faster than prior methods at same guarantee. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: h0d48e8d472167c77
Venue: SIGMOD
Year: 2024
Pagerank: 5.4289543e-05
Overall Rank: 7,832 | 47.51%
DOI: 10.1145/3654922

Incoming Non-self Citations Over Time

Authors

1. Yingli Zhou (Chinese University of Hong Kong)
2. Qingshuo Guo (Chinese University of Hong Kong)
3. Yixiang Fang (Chinese University of Hong Kong)
4. Chenhao Ma (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{zhou_sigmod24,
        title = {{A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery}},
        author = {Zhou, Yingli and Guo, Qingshuo and Fang, Yixiang and Ma, Chenhao},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654922},
        url = {https://dl.acm.org/doi/10.1145/3654922},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,666	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.698709e-05
10,093	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	5.068372e-05
10,394	Effective Structurally Similar Community Search in Large Temporal Graphs	2027	SIGMOD	4.9605343e-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
10,708	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.9605343e-05
10,737	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.9605343e-05
10,783	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.9605343e-05
10,860	CREST: Approximate k-Clique Counting in Real-World Networks via Refinement of Star-Based Sample Space	2026	VLDB	4.9605343e-05
10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	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

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.0001076734
1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2189157e-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,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,725	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.9991587e-05
9,004	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	5.2256037e-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	10,520	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD
2	3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
3	9,004	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD
4	1,198	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB
5	10,499	Bound-Tightened Densest Subgraph Discovery on GPU	2026	SIGMOD
6	11,284	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB
7	3,396	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD
8	10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB
9	1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
10	11,383	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB