Learning Combinatorial Node Labeling Algorithms

• URL: http://arxiv.org/abs/2106.03594v1
• Date: Mon, 7 Jun 2021 13:21:09 GMT
• Title: Learning Combinatorial Node Labeling Algorithms
• Authors: Lukas Gianinazzi, Maximilian Fries, Nikoli Dryden, Tal Ben-Nun, Torsten Hoefler
• Abstract summary: We present a graph neural network to learn graph colorings using reinforcement learning. Our learned deterministics give better solutions than classical degree-based greedys.
• Score: 8.687178298010968
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a graph neural network to learn graph coloring heuristics using reinforcement learning. Our learned deterministic heuristics give better solutions than classical degree-based greedy heuristics and only take seconds to evaluate on graphs with tens of thousands of vertices. As our approach is based on policy-gradients, it also learns a probabilistic policy as well. These probabilistic policies outperform all greedy coloring baselines and a machine learning baseline. Our approach generalizes several previous machine-learning frameworks, which applied to problems like minimum vertex cover. We also demonstrate that our approach outperforms two greedy heuristics on minimum vertex cover.

Related papers

• 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)
• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  Graph-level learning has been applied to many tasks including comparison, regression, classification, and more. Traditional approaches to learning a set of graphs rely on hand-crafted features, such as substructures. Deep learning has helped graph-level learning adapt to the growing scale of graphs by extracting features automatically and encoding graphs into low-dimensional representations.
  arXiv  Detail & Related papers  (2023-01-14T09:15:49Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  We use a learning framework for a pruning process of the input graph towards reducing the clique of the maximum enumeration problem. We study the role of using different vertex representations on the performance of this runtime method. We observe that using local graph features in the classification process produce more accurate results when combined with a feature elimination process.
  arXiv  Detail & Related papers  (2022-10-30T22:04:32Z)
• Learning Graph Regularisation for Guided Super-Resolution [77.7568596501908]
  We introduce a novel formulation for guided super-resolution. Its core is a differentiable optimisation layer that operates on a learned affinity graph. We extensively evaluate our method on several datasets, and consistently outperform recent baselines in terms of quantitative reconstruction errors.
  arXiv  Detail & Related papers  (2022-03-27T13:12:18Z)
• 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)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  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.
  arXiv  Detail & Related papers  (2021-09-13T13:17:41Z)
• 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)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  Graph embedding is a way to transform and encode the data structure in high dimensional and non-Euclidean feature space. CensNet is a general graph embedding framework, which embeds both nodes and edges to a latent feature space. Our approach achieves or matches the state-of-the-art performance in four graph learning tasks.
  arXiv  Detail & Related papers  (2020-10-25T22:39:31Z)
• Reward Propagation Using Graph Convolutional Networks [61.32891095232801]
  We propose a new framework for learning potential functions by leveraging ideas from graph representation learning. Our approach relies on Graph Convolutional Networks which we use as a key ingredient in combination with the probabilistic inference view of reinforcement learning.
  arXiv  Detail & Related papers  (2020-10-06T04:38:16Z)
• Geometrically Principled Connections in Graph Neural Networks [66.51286736506658]
  We argue geometry should remain the primary driving force behind innovation in the emerging field of geometric deep learning. We relate graph neural networks to widely successful computer graphics and data approximation models: radial basis functions (RBFs) We introduce affine skip connections, a novel building block formed by combining a fully connected layer with any graph convolution operator.
  arXiv  Detail & Related papers  (2020-04-06T13:25:46Z)
• 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.