Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs

• URL: http://arxiv.org/abs/2408.01503v1
• Date: Fri, 2 Aug 2024 18:02:51 GMT
• Title: Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs
• Authors: Lorenzo Colantonio, Andrea Cacioppo, Federico Scarpati, Stefano Giagu,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The graph coloring problem is an optimization problem involving the assignment of one of q colors to each vertex of a graph such that no two adjacent vertices share the same color. This problem is NP-hard and arises in various practical applications. In this work, we present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We propose a physics-inspired approach that leverages tools used in statistical mechanics to improve the training and performance of the algorithm. The scaling of our method is evaluated for different connectivities and graph sizes. Finally, we demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions where traditional methods struggle.

Related papers

• Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
  In graph-based semi-supervised learning, the Green-function method is a classical method that works by computing the Green's function in the graph space. We make a detailed analysis on it and propose a novel method from the perspective of optimization. Unlike the original method, our improved method can also apply two accelerating techniques, Gaussian Elimination, and Anchored Graphs.
  arXiv  Detail & Related papers  (2024-11-04T04:27:18Z)
• 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 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)
• 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)
• Graph Coarsening with Neural Networks [8.407217618651536]
  We propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way.
  arXiv  Detail & Related papers  (2021-02-02T06:50:07Z)
• 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)
• 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)
• 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)
• Second-Order Pooling for Graph Neural Networks [62.13156203025818]
  We propose to use second-order pooling as graph pooling, which naturally solves the above challenges. We show that direct use of second-order pooling with graph neural networks leads to practical problems. We propose two novel global graph pooling methods based on second-order pooling; namely, bilinear mapping and attentional second-order pooling.
  arXiv  Detail & Related papers  (2020-07-20T20:52:36Z)

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.