Estimating the stability number of a random graph using convolutional neural networks
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.
Code (1)
Tasks
Combinatorial OptimizationDeep LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Convergence and Stability of Graph Convolutional Networks on Large Random Graphs
We study properties of Graph Convolutional Networks (GCNs) by analyzing their behavior on standard models of random graphs, where nodes are represented by random latent variables and edges are drawn according to a simila…
validStability of Graph Convolutional Neural Networks through the lens of small perturbation analysis
In this work, we study the problem of stability of Graph Convolutional Neural Networks (GCNs) under random small perturbations in the underlying graph topology, i.e. under a limited number of insertions or deletions of e…
Stability of Graph Convolutional Neural Networks to Stochastic Perturbations
Graph convolutional neural networks (GCNNs) are nonlinear processing tools to learn representations from network data. A key property of GCNNs is their stability to graph perturbations. Current analysis considers determi…
On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewires
Recently, the stability of graph filters has been studied as one of the key theoretical properties driving the highly successful graph convolutional neural networks (GCNs). The stability of a graph filter characterizes t…
Stochastic Block ModelGraphlet Count Estimation via Convolutional Neural Networks
Graphlets are defined as k-node connected induced subgraph patterns. For an undirected graph, 3-node graphlets include close triangle and open triangle. When k = 4, there are six types of graphlets, e.g., tailed-triangle…