Technical Report MSC-2021-02

Title: Learning by Sampling: A Deep Learning Approach to the Planted Clique Problem With Unlimited Sampling
Authors: Najeeb Nabwani
Supervisors: Assaf Schuster
PDFCurrently accessibly only within the Technion network
Abstract: The planted clique problem plays an important role in the field of average-case complexity. The problem involves detecting graphs that contain a hidden clique of size $k$, which was planted in graphs from the Erdos-Renyi model $G_{n,0.5}$. The planted clique conjecture suggests that there is no polynomial-time algorithm that can solve the planted clique problem when $2\log_2(n) \ll k \ll \sqrt{n}$. This conjecture has served as the underlying hardness assumption in several different works, in fields such as cryptography and machine learning.

We propose a deep learning framework to build a model that can solve the planted clique problem with a high probability. Due to the well-defined random distribution of the planted clique problem, when certain conditions are met, we are able to generate unlimited amounts of training data with constant-time labelling. Our framework leverages this ability and uses polynomial-sized feed-forward neural networks for training on this data. We evaluate this framework empirically on multiple different planted clique distributions and manage to achieve high accuracy scores that surpass 90\% in some cases.

We also address the possibility of expanding this framework to the maximum clique problem. The set of graphs with $n$ nodes is broken down into smaller subsets, and for each subset, we train a network to detect graphs that contain a maximum clique of at least size $k$. We assume that for each subset, an oracle machine exists that can label some of the graphs in that subset in polynomial time. By conducting empirical evaluations on small graphs, we prove this concept using an exponential-time algorithm to simulate the oracle machine. The results show that if we can approximate such an oracle machine in polynomial time, then the maximum clique problem can be effectively learned from the smaller subsets.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion