M.Sc Thesis | |

M.Sc Student | Nabwani Najeeb |
---|---|

Subject | Learning by Sampling: A Deep Learning Approach to the Plannted Clique Problem with Unlimited Sampling |

Department | Department of Computer Science |

Supervisor | PROF. Assaf Schuster |

Full Thesis text |

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,}*

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.