EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A graph neural network with negative message passing and uniformity maximization for graph coloring

Xiangyu Wang, Xueming Yan, Yaochu Jin

Complex & Intelligent Systems · 2024-06 · 10 (3) · 4445-4455

DOI: 10.1007/s40747-024-01355-w ↗

Kurz gefasst

Fachartikel in der Zeitschrift Complex & Intelligent Systems, online erschienen am 13.03.2024. Verfasst von Xiangyu Wang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Universität Bielefeld.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Graph neural networks have received increased attention over the past years due to their promising ability to handle graph-structured data, which can be found in many real-world problems such as recommender systems and drug synthesis. Most existing research focuses on using graph neural networks to solve homophilous problems, and not much attention has been paid to heterophily-type problems. In this paper, we propose a graph network model for graph coloring, which is a class of representative heterophilous problems. Different from the message passing in conventional graph networks, we introduce negative message passing into a physics-inspired graph neural network for more effective information exchange in handling graph coloring problems. Moreover, a new term in the objective function taking into account the information entropy of nodes is suggested to increase the uniformity of the color assignment of each node, giving the neural network more chance to choose suitable colors for each node. Therefore, it could avoid the final solution getting stuck into the local optimum. Experimental studies are carried out to compare the proposed graph model with five state-of-the-art algorithms on ten publicly available graph coloring problems and d -regular graphs with up to $$10^4$$ 10 4 nodes, demonstrating the effectiveness of the proposed graph neural network.

Förderung

  • Universität Bielefeld

Zitieren

APA

Wang, X., Yan, X., & Jin, Y. (2024). A graph neural network with negative message passing and uniformity maximization for graph coloring. Complex & Intelligent Systems, 10(3), 4445-4455. https://doi.org/10.1007/s40747-024-01355-w

Vancouver

Wang X, Yan X, Jin Y. A graph neural network with negative message passing and uniformity maximization for graph coloring. Complex & Intelligent Systems. 2024;10(3):4445-4455. doi:10.1007/s40747-024-01355-w

BibTeX
@article{Wang2024,
  author = {Wang, Xiangyu and Yan, Xueming and Jin, Yaochu},
  title = {A graph neural network with negative message passing and uniformity maximization for graph coloring},
  journal = {Complex & Intelligent Systems},
  year = {2024},
  volume = {10},
  number = {3},
  pages = {4445--4455},
  doi = {10.1007/s40747-024-01355-w}
}
Kostenlos starten →