Finding Hamiltonian cycles with graph neural networks

• URL: http://arxiv.org/abs/2306.06523v1
• Date: Sat, 10 Jun 2023 21:18:31 GMT
• Title: Finding Hamiltonian cycles with graph neural networks
• Authors: Filip Bosni\'c, Mile \v{S}iki\'c
• Abstract summary: We train a small message-passing graph neural network to predict Hamiltonian cycles on ErdHos-Rnyi'e random graphs. The model generalizes well to larger graph sizes and retains reasonable performance even on graphs eight times the original size.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We train a small message-passing graph neural network to predict Hamiltonian cycles on Erd\H{o}s-R\'enyi random graphs in a critical regime. It outperforms existing hand-crafted heuristics after about 2.5 hours of training on a single GPU. Our findings encourage an alternative approach to solving computationally demanding (NP-hard) problems arising in practice. Instead of devising a heuristic by hand, one can train it end-to-end using a neural network. This has several advantages. Firstly, it is relatively quick and requires little problem-specific knowledge. Secondly, the network can adjust to the distribution of training samples, improving the performance on the most relevant problem instances. The model is trained using supervised learning on artificially created problem instances; this training procedure does not use an existing solver to produce the supervised signal. Finally, the model generalizes well to larger graph sizes and retains reasonable performance even on graphs eight times the original size.

Related papers

• Algebraic Representations for Faster Predictions in Convolutional Neural Networks [0.0]
  Convolutional neural networks (CNNs) are a popular choice of model for tasks in computer vision. skip connections may be added to create an easier gradient optimization problem. We show that arbitrarily complex, trained, linear CNNs with skip connections can be simplified into a single-layer model.
  arXiv  Detail & Related papers  (2024-08-14T21:10:05Z)
• Unlearning Graph Classifiers with Limited Data Resources [39.29148804411811]
  Controlled data removal is becoming an important feature of machine learning models for data-sensitive Web applications. It is still largely unknown how to perform efficient machine unlearning of graph neural networks (GNNs) Our main contribution is the first known nonlinear approximate graph unlearning method based on GSTs. Our second contribution is a theoretical analysis of the computational complexity of the proposed unlearning mechanism. Our third contribution are extensive simulation results which show that, compared to complete retraining of GNNs after each removal request, the new GST-based approach offers, on average, a 10.38x speed-up
  arXiv  Detail & Related papers  (2022-11-06T20:46:50Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Training Graph Neural Networks by Graphon Estimation [2.5997274006052544]
  We propose to train a graph neural network via resampling from a graphon estimate obtained from the underlying network data. We show that our approach is competitive with and in many cases outperform the other over-smoothing reducing GNN training methods.
  arXiv  Detail & Related papers  (2021-09-04T19:21:48Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  Graph Neural Networks (GNNs) perform learned message passing over an input graph. We train a deep GNN with up to 100 message passing steps and achieve several state-of-the-art results.
  arXiv  Detail & Related papers  (2021-06-15T08:50:10Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)
• Scalable Graph Neural Network Training: The Case for Sampling [4.9201378771958675]
  Graph Neural Networks (GNNs) are a new and increasingly popular family of deep neural network architectures to perform learning on graphs. Training them efficiently is challenging due to the irregular nature of graph data. Two different approaches have emerged in the literature: whole-graph and sample-based training.
  arXiv  Detail & Related papers  (2021-05-05T20:44:10Z)
• Binary Graph Neural Networks [69.51765073772226]
  Graph Neural Networks (GNNs) have emerged as a powerful and flexible framework for representation learning on irregular data. In this paper, we present and evaluate different strategies for the binarization of graph neural networks. We show that through careful design of the models, and control of the training process, binary graph neural networks can be trained at only a moderate cost in accuracy on challenging benchmarks.
  arXiv  Detail & Related papers  (2020-12-31T18:48:58Z)
• 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.