Covering K-Cliques in Billion-Scale Graphs
Kaiyu Chen, Dong Wen, Hanchen Wang, Zhengyi Yang, Wenjie Zhang, Xuemin Lin
RAIDS Lab Authors
Details
Research Area
Tags
Resources
Abstract
The k-clique structure in graphs has been investigated in various real-world applications, such as community detection in complex networks, functional module discovery in biological networks, and link spam detection in web graphs. Despite extensive research on k-clique enumeration, the large number of k-cliques in many graphs poses a challenge for practical application and computation. To address this, we explore the k-clique τ-cover problem, a generalization of the vertex cover problem. The problem aims to find a small set of vertices that can effectively represent all k-cliques in the graph. We prove the NP-hardness of finding the minimum k-clique cover. We propose a hierarchical solution that computes a small cover without enumerating k-cliques. Extensive experiments on real-world graphs verify the efficiency and effectiveness of our solution.
Author Affiliations
BibTeX
@inproceedings{chen2025Efficient,
title = {Covering K-Cliques in Billion-Scale Graphs},
author = {Chen, Kaiyu and Wen, Dong and Wang, Hanchen and Yang, Zhengyi and Zhang, Wenjie and Lin, Xuemin},
series = {WWW '25},
url = {http://dx.doi.org/10.1145/3696410.3714897},
doi = {10.1145/3696410.3714897},
booktitle = {Proceedings of the ACM on Web Conference 2025},
publisher = {ACM},
year = {2025},
month = Apr,
pages = {2299-2308},
collection = {WWW '25}
}