mlsanityData to 7 Oct 2026

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

arXiv 2403.09742 ↗First posted 13 Mar 2024cs.AI cond-mat.dis-nn cs.DScited by 0

Not on the map. Why?

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.

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

Builds on

60 of 256 references.

References · 60

  1. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  2. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  4. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  5. 2020Can Graph Neural Networks Count Substructures?cited by 235
  6. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  7. 2013Ising formulations of many NP problemscited by 204
  8. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  9. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  10. 2019What Can Neural Networks Reason About?cited by 155
  11. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  12. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
38 more
  1. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  2. 2020Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Kernel Renormalizationcited by 71
  3. 2016SNAP: A General Purpose Network Analysis and Graph Mining Librarycited by 56
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2018Geometric Scattering for Graph Data Analysiscited by 49
  6. 2018Graph Convolutional Neural Networks via Scatteringcited by 46
  7. 2018Diffusion Scattering Transforms on Graphscited by 43
  8. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
  9. 2021Goal-Aware Neural SAT Solvercited by 27
  10. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25
  11. 2022Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cutcited by 19
  12. 2013Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storagecited by 15
  13. 2015The backtracking survey propagation algorithm for solving random K-SAT problemscited by 14
  14. 2015Sum-of-squares lower bounds for planted cliquecited by 12
  15. 2021Learning the noise fingerprint of quantum devicescited by 12
  16. 2020Learning from Survey Propagation: a Neural Network for MAX-E-3-SATcited by 11
  17. 2020Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemescited by 11
  18. 2015Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problemscited by 9
  19. 2019The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Propertycited by 9
  20. 2023Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 9
  21. 2014Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Covercited by 8
  22. 2015Finding One Community in a Sparse Graphcited by 8
  23. 2017Scalable Kernelization for Maximum Independent Setscited by 8
  24. 2019The Resolution of Keller's Conjecturecited by 8
  25. 2022Hard Optimization Problems have Soft Edgescited by 8
  26. 2022Almost-Linear Planted Cliques Elude the Metropolis Processcited by 7
  27. 2020Learning fine-grained search space pruning and heuristics for combinatorial optimizationcited by 6
  28. 2021Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique modelcited by 6
  29. 2018Parallel Tempering for the planted clique problemcited by 5
  30. 2020A Survey on Approximation in Parameterized Complexity: Hardness and Algorithmscited by 5
  31. 2023Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problemscited by 5
  32. 2023Complex Recurrent Spectral Networkcited by 5
  33. 2014Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detectioncited by 4
  34. 2017A Unifying View of Explicit and Implicit Feature Maps of Graph Kernelscited by 4
  35. 2020Large independent sets on random d-regular graphs with fixed degree dcited by 4
  36. 2020Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformationscited by 4
  37. 2015Solving the Maximum Clique Problem with Symmetric Rank-One Nonnegative Matrix Approximationcited by 3
  38. 2023Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problemscited by 3

50 most cited of 60 All 60 (JSON)

Built on by

Not cited yet.