Graph Coloring with Physics-Inspired Graph Neural Networks

• URL: http://arxiv.org/abs/2202.01606v1
• Date: Thu, 3 Feb 2022 14:24:12 GMT
• Title: Graph Coloring with Physics-Inspired Graph Neural Networks
• Authors: Martin J. A. Schuetz, J. Kyle Brubaker, Zhihuai Zhu, Helmut G. Katzgraber
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 based on the statistical physics Potts model. Generalizations to other multi-class problems such as community detection, data clustering, and the minimum clique cover problem are straightforward. We provide numerical benchmark results and illustrate our approach with an end-to-end application for a real-world scheduling use case within a comprehensive encode-process-decode framework. Our optimization approach performs on par or outperforms existing solvers, with the ability to scale to problems with millions of variables.

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)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• 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 Graph Neural Network with Negative Message Passing for Graph Coloring [12.501032566933178]
  We propose a graph network model for graph coloring, which is a class of representative heterophilous problems. We introduce negative message passing into the proposed graph neural network for more effective information exchange. New loss function taking into account the self-information of the nodes is suggested to accelerate the learning process.
  arXiv  Detail & Related papers  (2023-01-26T15:08:42Z)
• Graph Neural Network with Curriculum Learning for Imbalanced Node Classification [21.085314408929058]
  Graph Neural Network (GNN) is an emerging technique for graph-based learning tasks such as node classification. In this work, we reveal the vulnerability of GNN to the imbalance of node labels. We propose a novel graph neural network framework with curriculum learning (GNN-CL) consisting of two modules.
  arXiv  Detail & Related papers  (2022-02-05T10:46:11Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• 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)
• Adaptive Graph Auto-Encoder for General Data Clustering [90.8576971748142]
  Graph-based clustering plays an important role in the clustering area. Recent studies about graph convolution neural networks have achieved impressive success on graph type data. We propose a graph auto-encoder for general data clustering, which constructs the graph adaptively according to the generative perspective of graphs.
  arXiv  Detail & Related papers  (2020-02-20T10:11:28Z)
• 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.