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

• URL: http://arxiv.org/abs/2407.07827v2
• Date: Fri, 19 Jul 2024 02:51:01 GMT
• Title: Estimating the stability number of a random graph using convolutional neural networks
• Authors: Randy Davila,
• Abstract summary: We explore the feasibility of using convolutional neural networks (CNNs) on graph images to predict the cardinality of properties of random graphs and networks. The model and results presented in this study suggest potential for applying deep learning in optimization problems previously not considered by simple deep learning techniques.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals [18.45931641798935]
  This paper introduces Polynomial Graphical Lasso (PGL), a new approach to learning graph structures from nodal signals. Our key contribution lies in the signals as Gaussian and stationary on the graph, enabling the development of a graph-learning lasso.
  arXiv  Detail & Related papers  (2024-04-03T10:19:53Z)
• Image Keypoint Matching using Graph Neural Networks [22.33342295278866]
  We propose a graph neural network for the problem of image matching. The proposed method first generates initial soft correspondences between keypoints using localized node embeddings. We evaluate our method on natural image datasets with keypoint annotations and show that, in comparison to a state-of-the-art model, our method speeds up inference times without sacrificing prediction accuracy.
  arXiv  Detail & Related papers  (2022-05-27T23:38:44Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Graphon-aided Joint Estimation of Multiple Graphs [24.077455621015552]
  We consider the problem of estimating the topology of multiple networks from nodal observations. We adopt a graphon as our random graph model, which is a nonparametric model from which graphs of potentially different sizes can be drawn.
  arXiv  Detail & Related papers  (2022-02-11T15:20:44Z)
• Gaussian Graphical Model Selection for Huge Data via Minipatch Learning [1.2891210250935146]
  We propose the Minipatch Graph (MPGraph) estimator to solve the problem of graphical model selection. MPGraph is a generalization of thresholded graph estimators fit to tiny, random subsets of both the observations and the nodes. We prove that our algorithm achieves finite-sample graph selection consistency.
  arXiv  Detail & Related papers  (2021-10-22T21:06:48Z)
• Graph and graphon neural network stability [122.06927400759021]
  Graph networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of network data. We analyze GNN stability using kernel objects called graphons.
  arXiv  Detail & Related papers  (2020-10-23T16:55:56Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design. We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
  arXiv  Detail & Related papers  (2020-10-21T20:04:22Z)
• Convergence and Stability of Graph Convolutional Networks on Large Random Graphs [22.387735135790706]
  We study properties of Graph Convolutional Networks (GCNs) by analyzing their behavior on standard models of random graphs. We first study the convergence of GCNs to their continuous counterpart as the number of nodes grows. We then analyze the stability of GCNs to small deformations of the random graph model.
  arXiv  Detail & Related papers  (2020-06-02T18:36:19Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.