Estimating the stability number of a random graph using convolutional neural networks
This addresses combinatorial optimization problems, which are widely applicable but computationally hard, though the approach appears incremental as it applies existing CNNs to a new representation.
The paper tackled predicting the stability number of random graphs using convolutional neural networks (CNNs) on graph images, achieving results that suggest potential for deep learning in combinatorial optimization.
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.