# Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model

arXiv: https://arxiv.org/abs/2106.05720 · HTML: https://mlsanity.com/paper/2106.05720/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2021.

## Built on by (most cited first, 6 of 6)

- [Hopfield model with planted patterns: a teacher-student self-supervised learning model](https://mlsanity.com/paper/2304.13710/) (2023)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining](https://mlsanity.com/paper/2511.22866/) (2025)
- [Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis](https://mlsanity.com/paper/2512.03419/) (2025)
- [Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Mining](https://mlsanity.com/paper/2512.20915/) (2025)

## Abstract (arXiv)

Over-parametrization was a crucial ingredient for recent developments in inference and machine-learning fields. However a good theory explaining this success is still lacking. In this paper we study a very simple case of mismatched over-parametrized algorithm applied to one of the most studied inference problem: the planted clique problem. We analyze a Monte Carlo (MC) algorithm in the same class of the famous Jerrum algorithm. We show how this MC algorithm is in general suboptimal for the recovery of the planted clique. We show however how to enhance its performances by adding a (mismatched) parameter: the temperature; we numerically find that this over-parametrized version of the algorithm can reach the supposed algorithmic threshold for the planted clique problem.