Finding the Maximum Clique in Massive Graphs

Summary: RMC finds exact maximum cliques in massive graphs via randomized, probability-guaranteed seed-set reduction and binary search over clique size bounds. It replaces per-vertex enumeration with iterative k-clique searches, delivering substantially greater efficiency and robustness. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h8095ee1c6bf1f850
Venue: VLDB
Year: 2017
Pagerank: 0.0001046246
Overall Rank: 1,495 | 89.99%
DOI: 10.14778/3137628.3137635
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Can Lu (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)
3. Hao Wei (Chinese University of Hong Kong)
4. Yikai Zhang (Chinese University of Hong Kong)

BibTeX Citation

@article{lu_vldb17,
        title = {{Finding the Maximum Clique in Massive Graphs}},
        author = {Lu, Can and Yu, Jeffrey Xu and Wei, Hao and Zhang, Yikai},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {11},
        pages = {1538--1549},
        doi = {10.14778/3137628.3137635},
        url = {https://doi.org/10.14778/3137628.3137635},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
771	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00014081924
2,480	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	8.387452e-05
3,000	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	7.7498183e-05
3,597	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	7.1598365e-05
4,779	Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach	2021	VLDB	6.4069971e-05
5,066	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	6.2786224e-05
5,571	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.0628752e-05
7,390	One Set to Cover All Maximal Cliques Approximately	2022	SIGMOD	5.5209526e-05
8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	5.2361195e-05
11,280	Most Similar Biclique Search at Scale	2025	VLDB	4.9605343e-05
12,023	Graph Iso/Auto-morphism: A Divide-&-Conquer Approach	2021	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
130	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.0003029792
643	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015219469

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,390	One Set to Cover All Maximal Cliques Approximately	2022	SIGMOD
2	771	Maximum Biclique Search at Billion Scale	2020	VLDB
3	1,198	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB
4	4,155	Maximal Defective Clique Enumeration	2023	SIGMOD
5	3,591	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
6	1,591	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD
7	5,569	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
8	5,007	Accelerating Maximal Clique Enumeration via Graph Reduction	2024	VLDB
9	8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD
10	643	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD