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

Randy Davila
7/10/2024
cs.LGmath.CO

No official code found. Best implementation: RandyRDavila/Estimating-the-stability-number-of-a-random-graph-using-convolutional-neural-networks (0 stars, MIT, last commit 2024-07-18).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

RandyRDavila/Estimating-the-stability-number-of-a-random-graph-using-convolutional-neural-networksCommunity100%
MIT
00Python, Jupyter NotebookJul 18, 20242 years agoMIT

Similar Papers

Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction

83% match2025

Graph Q-Learning for Combinatorial Optimization

82% match2024

A Distributed Training Architecture For Combinatorial Optimization

80% match2025

On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective

80% match2025

Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems

80% match2024

Graph Neural Networks are Heuristics

80% match1 repo22026

Cite this paper

@article{davila2024estimating,
  title  = {Estimating the stability number of a random graph using convolutional neural networks},
  author = {Randy Davila},
  year   = {2024},
  eprint = {2407.07827},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2407.07827v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2407.07827.svg)](https://codeofpaper.com/paper/2407.07827)

Discussion