Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

• URL: http://arxiv.org/abs/2602.18419v1
• Date: Fri, 20 Feb 2026 18:41:48 GMT
• Title: Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
• Authors: Geri Skenderi, Lorenzo Buffoni, Francesco D'Amico, David Machado, Raffaele Marino, Matteo Negri, Federico Ricci-Tersenghi, Carlo Lucibello, Maria Chiara Angelini,
• Abstract summary: Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical algorithms.<n>From a statistical physics perspective, we propose new hard benchmarks based on random problems.<n>We provide these benchmarks, along with performance results from both classical outperforms and GNNs.
• Score: 12.674439476285754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical heuristics. However, such claims risk being unsolid due to a lack of standard benchmarks on truly hard instances. From a statistical physics perspective, we propose new hard benchmarks based on random problems. We provide these benchmarks, along with performance results from both classical heuristics and GNNs. Our fair comparison shows that classical algorithms still outperform GNNs. We discuss the challenges for neural networks in this domain. Future claims of superiority can be made more robust using our benchmarks, available at https://github.com/ArtLabBocconi/RandCSPBench.

Related papers

• Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks [0.0]
  The ability to train Deep Neural Networks (DNNs) with constraints is instrumental in improving the fairness of modern machine-learning models.<n>We provide a challenging benchmark of real-world large-scale fairness-constrained learning tasks built on top of the US Census (Folktables)<n>We demonstrate the use of the benchmark by implementing and comparing three recently proposed, but as-of-yet unimplemented, algorithms.
  arXiv  Detail & Related papers  (2025-07-05T13:01:18Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Benchmarking ChatGPT on Algorithmic Reasoning [58.50071292008407]
  We evaluate ChatGPT's ability to solve algorithm problems from the CLRS benchmark suite that is designed for GNNs. We find that ChatGPT outperforms specialist GNN models, using Python to successfully solve these problems.
  arXiv  Detail & Related papers  (2024-04-04T13:39:06Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Cracking nuts with a sledgehammer: when modern graph neural networks do worse than classical greedy algorithms [2.436681150766912]
  We show that a simple greedy algorithm, running in almost linear time, can find solutions for the MIS problem of much better quality than the GNN. We do not see any good reason for solving the MIS with these GNN, as well as for using a sledgehammer to crack nuts.
  arXiv  Detail & Related papers  (2022-06-27T11:54:01Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  We introduce GNNRank, a modeling framework compatible with any GNN capable of learning digraph embeddings. We show that our methods attain competitive and often superior performance compared with existing approaches.
  arXiv  Detail & Related papers  (2022-02-01T04:19:50Z)
• Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study [100.27567794045045]
  Training deep graph neural networks (GNNs) is notoriously hard. We present the first fair and reproducible benchmark dedicated to assessing the "tricks" of training deep GNNs.
  arXiv  Detail & Related papers  (2021-08-24T05:00:37Z)
• Graph Neural Network for Large-Scale Network Localization [35.29322617956428]
  Graph neural networks (GNNs) are popular to use for classifying structured data in the context of machine learning. In this work, we adopt GNN for a classic but challenging nonlinear regression problem, namely the network localization. Our main findings are in order. First, GNN is potentially the best solution to large-scale network localization in terms of accuracy, robustness and computational time.
  arXiv  Detail & Related papers  (2020-10-22T12:39:26Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training [101.3819906739515]
  We study what normalization is effective for Graph Neural Networks (GNNs) Faster convergence is achieved with InstanceNorm compared to BatchNorm and LayerNorm. GraphNorm also improves the generalization of GNNs, achieving better performance on graph classification benchmarks.
  arXiv  Detail & Related papers  (2020-09-07T17:55:21Z)
• Graph Random Neural Network for Semi-Supervised Learning on Graphs [36.218650686748546]
  We study the problem of semi-supervised learning on graphs, for which graph neural networks (GNNs) have been extensively explored. Most existing GNNs inherently suffer from the limitations of over-smoothing, non-robustness, and weak-generalization when labeled nodes are scarce. In this paper, we propose a simple yet effective framework -- GRAPH R NEURAL NETWORKS (GRAND) -- to address these issues.
  arXiv  Detail & Related papers  (2020-05-22T09:40:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.