Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
This addresses a gap in graph theory for applications like community detection, but it is incremental as it extends prior work on disjoint cliques to overlapping ones.
The paper tackles the problem of recovering overlapping cliques in dense random intersection graphs, which is more challenging than disjoint cases, and presents the first efficient algorithms for exact and approximate recovery that are robust to noise and edge corruptions, working when clique size k is much larger than sqrt(n log(n)).
We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, $d = n^{Ω(1)}$ cliques of size approximately $k$ are randomly planted by choosing the vertices to participate in each clique independently with probability $δ$. While there has been extensive work on recovering one, or multiple disjointly planted cliques in random graphs, the natural extension of this question to recovering overlapping cliques has been, surprisingly, largely unexplored. Moreover, because every vertex can be part of polynomially many cliques, this task is significantly more challenging than in case of disjointly planted cliques (as recently studied by Kothari, Vempala, Wein and Xu [COLT'23]). In this work we obtain the first efficient algorithms for recovering the community structure of RIGs both from the perspective of exact and approximate recovery. Our algorithms are further robust to noise, monotone adversaries, and a certain, optimal number of edge corruptions. They work whenever $k \gg \sqrt{n \log(n)}$. Our techniques follow the proofs-to-algorithms framework utilizing the sum-of-squares hierarchy.