A deep learning guided memetic framework for graph coloring problems

• URL: http://arxiv.org/abs/2109.05948v1
• Date: Mon, 13 Sep 2021 13:17:41 GMT
• Title: A deep learning guided memetic framework for graph coloring problems
• Authors: Olivier Goudet, Cyril Grelier and Jin-Kao Hao
• Abstract summary: We present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.
• Score: 15.426481600285724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given an undirected graph $G=(V,E)$ with a set of vertices $V$ and a set of edges $E$, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. The proposed algorithm is evaluated on the weighted graph coloring problem and computational results show that the proposed approach allows to obtain new upper bounds for medium and large graphs. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.

Related papers

• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  We present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions.
  arXiv  Detail & Related papers  (2024-08-02T18:02:51Z)
• Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks [1.5469452301122175]
  A dominating set of a graph $mathcalG=(V, E) is a subset of vertices $SsubseteqmathcalV setminus S$ outside the dominating set. We propose a novel learning-based approach to compute solutions for the minimum dominating set problem using graph$ convolutional networks.
  arXiv  Detail & Related papers  (2023-06-06T06:22:42Z)
• Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks [5.620334754517149]
  We investigate whether deep reinforcement learning can be used to discover a competitive construction for graph colouring. Our proposed approach, ReLCol, uses deep Q-learning together with a graph neural network for feature extraction. We demonstrate that reinforcement learning is a promising direction for further research on the graph colouring problem.
  arXiv  Detail & Related papers  (2023-04-08T15:41:01Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  We propose a general learnable graph matching method to address these issues. Our method achieves state-of-the-art performance on several MOT datasets. For image matching, our method outperforms state-of-the-art methods on a popular indoor dataset, ScanNet.
  arXiv  Detail & Related papers  (2023-03-27T17:39:00Z)
• A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource [87.7460720701592]
  This paper introduces formulaic definition, evaluation, and development in this field. The taxonomy of deep graph clustering methods is presented based on four different criteria, including graph type, network architecture, learning paradigm, and clustering method. The applications of deep graph clustering methods in six domains, including computer vision, natural language processing, recommendation systems, social network analyses, bioinformatics, and medical science, are presented.
  arXiv  Detail & Related papers  (2022-11-23T11:31:11Z)
• Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
  We show how graph neural networks can be used to solve the canonical graph coloring problem. We frame graph coloring as a multi-class node classification problem and utilize an unsupervised training strategy.
  arXiv  Detail & Related papers  (2022-02-03T14:24:12Z)
• Learning Combinatorial Node Labeling Algorithms [8.687178298010968]
  We present a graph neural network to learn graph colorings using reinforcement learning. Our learned deterministics give better solutions than classical degree-based greedys.
  arXiv  Detail & Related papers  (2021-06-07T13:21:09Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

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.