A Graph Coloring Algorithm Based on Minimal-cost Graph Neural Networks for Efficient Optimization of Complex Network Structures

Authors: Mahaboob Ali

Country: India

Full-text Research PDF File:   View   |   Download

Abstract: The applications of the Graph Coloring Problem (GCP) and its optimization capabilities, including its ties to complexity as a base-level NP-hard problem, encompass the problem's scheduling, network design, and resource allocation uses. Even in the presence of complicated, dense networks, traditional methods such as heuristics and greedy meta-algorithms still seem to lag in performance and scalability. Constructing a Cost Function-based Graph Coloring Problem Solving Framework Based on Graph Neural Networks (MCGNN) aims to consolidate the use of GNN and cost-driven optimization approaches. In the preservation of the Macualls' formulated GCP under the influence of the Potts' model, MCGNN GNNs and minimum cost mechanisms select fundamentals to predict. MCGNN performances on benchmark tests scale over the 2-20qu and 20% value under dense networks, ranging in the 1000s, compared to the provided datasets and state-of-the-art methods. By leveraging the known theoretical network optimization mechanics akin to the Weisfeiler Lehman construct, and on predictable routing capabilities, we believe it to be simplified enough to apply to the unsolved dense networks. MCGNN aims to be enhanced in future work, also to tackle dynamic graphs and multi-objective coloring problems.

Keywords: “Graph coloring, Graph Neural Network (GNN), Minimal Cost Graph Neural Networ”.

Paper Id: 232834

Published On: 2022-07-08

Published In: Volume 10, Issue 4, July-August 2022

Share this