Neural network approach to the planted clique problem

This thesis investigates the computational performance of neural networks (NNs) in addressing a challenging problem known as the planted clique problem. This is a highly significant problem in average-case complexity theory due to its large statistical-computational gap. The primary aim of this thesis is to conduct a numerical analysis of NNs, comparing them with existing algorithms, and exploring potential similarities in problem-solving strategies employed by NNs and humans. Firstly, the problem's setting is introduced, focusing on the detection of graphs with planted cliques. Different algorithms used to solve this task are described, among which Approximate Message Passing (AMP) is identified as the best known algorithm. AMP, in fact, is able to recover the nodes of a planted clique in a random graph in polynomial time, up to a clique size of $k = \sqrt{n/e}$, where $n$ is the number of nodes in the graph. Convolutional Neural Networks (CNNs) are then employed to solve the same detection problem. CNNs are used for the visual analysis of adjacency matrices, specifically to identify distinctive patterns that indicate the presence of a planted clique. The theory and mechanisms behind CNNs are elucidated and their performance in solving the problem is analyzed. Additionally, alternative neural networks capable of solving the same problem are briefly described and their performance is compared. Eventually, human participants will be incorporated into the experiments so that the strategies in problem-solving between CNNs and the human visual system will be compared. This thesis contributes to the understanding of NNs' capabilities and limitations in solving the planted clique problem and other hard inference problems. It also provides some insights into the comparative performance of NNs, existing algorithms, and human participants. By investigating the similarities in problem solving between NNs and humans, this research will offer a better understanding of the underlying mechanisms employed by NNs and their potential alignment with human cognitive processes.