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

Raffaele Marino; Lorenzo Buffoni; Bogdan Zavalnij

cs.AIMar 13, 2024

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

Authors: Raffaele Marino, Lorenzo Buffoni, Bogdan Zavalnij

Organizations: Dipartimento di Fisica e Astronomia Università degli studi di Firenze Via Giovanni Sansone 1, 50019 Sesto Fiorentino, Florence, Italy · HUN-REN Rényi Institute of Mathematics H-1053, Reáltanoda u. 13-15 Budapest, Hungary

Abstract

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.

Explore similar work

Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture
Aug 11, 2025Xiang Li, Shanshan Wang, Chenglong XiaoMaximum Independent Set Graph Neural Networks
Graph Neural Networks with Triangle-Based Messages for the Multicut Problem
May 13, 2026Jannik Irmai, Lucas Fabian Naumann, Bjoern AndresMaximum Independent Set Graph Neural Networks
Neurosymbolic Discovery of Algebraic Graph Constructions
Aug 8, 2026David Seka, Stefan SzeiderGraph Theory Algebraic Structures

Aug 11, 2025 · cs.LGJ/K move · Enter open · S save

Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture

Xiang Li, Shanshan Wang, Chenglong Xiao

Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.

Maximum Independent Set Graph Neural Networks Graph Representations Machine Learning

Open paper Ask about it PDF

Abstract

Explore similar work

Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture

Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

Neurosymbolic Discovery of Algebraic Graph Constructions