# Estimating the stability number of a random graph using convolutional neural networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 17 references that are in the map.
- First posted on arXiv 10 Jul 2024.

## Builds on (most cited first, 1 of 1)

- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)

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

- [Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction](https://mlsanity.com/paper/2511.18150/) (2025)

## Abstract (arXiv)

Graph combinatorial optimization problems are widely applicable and notoriously difficult to compute; for example, consider the traveling salesman or facility location problems. In this paper, we explore the feasibility of using convolutional neural networks (CNNs) on graph images to predict the cardinality of combinatorial properties of random graphs and networks. Specifically, we use image representations of modified adjacency matrices of random graphs as training samples for a CNN model to predict the stability number of random graphs; where the stability number is the cardinality of a maximum set of vertices in a graph that contains no pairwise adjacency between vertices. The model and results presented in this study suggest potential for applying deep learning in combinatorial optimization problems previously not considered by simple deep learning techniques.