# A short review on the maximum clique problem algorithms with classical, AI, and quantum methods

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 60 of its 256 references that are in the map.
- First posted on arXiv 13 Mar 2024.

## Builds on (most cited first, 30 of 60)

- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Kernel Renormalization](https://mlsanity.com/paper/2012.04030/) (2020)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Geometric Scattering for Graph Data Analysis](https://mlsanity.com/paper/1810.03068/) (2018)
- [Graph Convolutional Neural Networks via Scattering](https://mlsanity.com/paper/1804.00099/) (2018)
- [Diffusion Scattering Transforms on Graphs](https://mlsanity.com/paper/1806.08829/) (2018)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [Goal-Aware Neural SAT Solver](https://mlsanity.com/paper/2106.07162/) (2021)
- [Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?](https://mlsanity.com/paper/2206.01506/) (2022)
- [Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut](https://mlsanity.com/paper/2210.00623/) (2022)
- [Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage](https://mlsanity.com/paper/1302.6256/) (2013)
- [The backtracking survey propagation algorithm for solving random K-SAT problems](https://mlsanity.com/paper/1508.05117/) (2015)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Learning the noise fingerprint of quantum devices](https://mlsanity.com/paper/2109.11405/) (2021)
- [Learning from Survey Propagation: a Neural Network for MAX-E-3-SAT](https://mlsanity.com/paper/2012.06344/) (2020)
- [Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes](https://mlsanity.com/paper/2012.07747/) (2020)
- [Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems](https://mlsanity.com/paper/1502.06590/) (2015)

## Abstract (arXiv)

This manuscript provides a comprehensive review of the Maximum Clique Problem, a computational problem that involves finding subsets of vertices in a graph that are all pairwise adjacent to each other. As such, this review is a continuation of the series of previous reviews from 1994, 1999 and 2014. The manuscript covers in a simple way classical algorithms and includes a review of recent developments in graph neural networks and quantum algorithms.