{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:23:04Z","timestamp":1775874184608,"version":"3.50.1"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005721","name":"Universit\u00e4t Bielefeld","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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<jats:italic>negative message passing<\/jats:italic>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<jats:italic>d<\/jats:italic>-regular graphs with up to<jats:inline-formula><jats:alternatives><jats:tex-math>$$10^4$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>10<\/mml:mn><mml:mn>4<\/mml:mn><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>nodes, demonstrating the effectiveness of the proposed graph neural network.<\/jats:p>","DOI":"10.1007\/s40747-024-01355-w","type":"journal-article","created":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T20:57:50Z","timestamp":1710363470000},"page":"4445-4455","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A graph neural network with negative message passing and uniformity maximization for graph coloring"],"prefix":"10.1007","volume":"10","author":[{"given":"Xiangyu","family":"Wang","sequence":"first","affiliation":[]},{"given":"Xueming","family":"Yan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1100-0631","authenticated-orcid":false,"given":"Yaochu","family":"Jin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"1355_CR1","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1016\/j.neucom.2020.03.119","volume":"452","author":"X Wang","year":"2021","unstructured":"Wang X, Wang J, Zhang K, Lin F, Chang Q (2021) Convergence and objective functions of noise-injected multilayer perceptrons with hidden multipliers. Neurocomputing 452:796\u2013812","journal-title":"Neurocomputing"},{"issue":"3","key":"1355_CR2","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1109\/TNNLS.2020.2980383","volume":"32","author":"J Wang","year":"2020","unstructured":"Wang J, Zhang H, Wang J, Pu Y, Pal NR (2020) Feature selection using a neural network with group lasso regularization and controlled redundancy. IEEE Trans Neural Netw Learn Syst 32(3):1110\u20131123","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"issue":"3","key":"1355_CR3","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1109\/TCYB.2019.2950105","volume":"50","author":"X Xie","year":"2019","unstructured":"Xie X, Zhang H, Wang J, Chang Q, Wang J, Pal NR (2019) Learning optimized structure of neural networks by hidden node pruning with $$l_{1}$$ regularization. IEEE Trans Cybern 50(3):1333\u20131346","journal-title":"IEEE Trans Cybern"},{"issue":"2","key":"1355_CR4","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1109\/MCI.2014.2307227","volume":"9","author":"E Cambria","year":"2014","unstructured":"Cambria E, White B (2014) Jumping nlp curves: a review of natural language processing research. IEEE Comput Intell Mag 9(2):48\u201357","journal-title":"IEEE Comput Intell Mag"},{"issue":"2","key":"1355_CR5","first-page":"139","volume":"7","author":"Y Kang","year":"2020","unstructured":"Kang Y, Cai Z, Tan C-W, Huang Q, Liu H (2020) Natural language processing (nlp) in management research: a literature review. J Manag Anal 7(2):139\u2013172","journal-title":"J Manag Anal"},{"issue":"2","key":"1355_CR6","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1109\/TNNLS.2021.3070843","volume":"33","author":"S Ji","year":"2021","unstructured":"Ji S, Pan S, Cambria E, Marttinen P, Philip SY (2021) A survey on knowledge graphs: representation, acquisition, and applications. IEEE Trans Neural Netw Learn Syst 33(2):494\u2013514","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"1355_CR7","unstructured":"Choudhary S, Luthra T, Mittal A, Singh R (2021) A survey of knowledge graph embedding and their applications. arXiv preprint arXiv:2107.07842"},{"key":"1355_CR8","doi-asserted-by":"crossref","unstructured":"Zhang C, Song D, Huang C, Swami A, Chawla NV (2019) Heterogeneous graph neural network. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, p. 793\u2013803","DOI":"10.1145\/3292500.3330961"},{"issue":"1","key":"1355_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","volume":"20","author":"F Scarselli","year":"2008","unstructured":"Scarselli F, Gori M, Chung Tsoi A, Hagenbuchner M, Monfardini G (2008) The graph neural network model. IEEE Trans Neural Netw 20(1):61\u201380","journal-title":"IEEE Trans Neural Netw"},{"issue":"3","key":"1355_CR10","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/TNN.2008.2010350","volume":"20","author":"A Micheli","year":"2009","unstructured":"Micheli A (2009) Neural network for graphs: a contextual constructive approach. IEEE Trans Neural Netw 20(3):498\u2013511","journal-title":"IEEE Trans Neural Netw"},{"key":"1355_CR11","unstructured":"Kipf TN, Welling M (2016) Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907"},{"key":"1355_CR12","unstructured":"Hamilton W, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, 30"},{"key":"1355_CR13","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y (2017) Graph attention networks. arXiv preprint arXiv:1710.10903"},{"key":"1355_CR14","doi-asserted-by":"crossref","unstructured":"Zhang Y, Gao S, Pei J, Huang H (2022) Improving social network embedding via new second-order continuous graph neural networks. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 2515\u20132523","DOI":"10.1145\/3534678.3539415"},{"key":"1355_CR15","unstructured":"Xue H, Rajan V, Lin Y (2022) Graph coloring via neural networks for haplotype assembly and viral quasispecies reconstruction. arXiv preprint arXiv:2210.12158"},{"key":"1355_CR16","first-page":"27","volume":"1050","author":"J Bruna","year":"2017","unstructured":"Bruna J, Li X (2017) Community detection with graph neural networks. Stat 1050:27","journal-title":"Stat"},{"key":"1355_CR17","unstructured":"Rong Y, Huang W, Xu T, Huang J (2019) Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903"},{"key":"1355_CR18","doi-asserted-by":"crossref","unstructured":"Zhao T, Zhang X, Wang S (2021) Graphsmote: Imbalanced node classification on graphs with graph neural networks. In: Proceedings of the 14th ACM international conference on web search and data mining, p 833\u2013841","DOI":"10.1145\/3437963.3441720"},{"key":"1355_CR19","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1016\/j.procs.2022.01.084","volume":"199","author":"Y Shi","year":"2022","unstructured":"Shi Y, Zhang Y (2022) The neural network methods for solving traveling salesman problem. Procedia Comput Sci 199:681\u2013686","journal-title":"Procedia Comput Sci"},{"key":"1355_CR20","doi-asserted-by":"publisher","DOI":"10.3389\/frai.2020.580607","volume":"3","author":"T Jan","year":"2021","unstructured":"Jan T, Martin R, Hinrikus W, Martin G (2021) Graph neural networks for maximum constraint satisfaction. Front Artif Intell 3:580607","journal-title":"Front Artif Intell"},{"key":"1355_CR21","unstructured":"Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227"},{"key":"1355_CR22","doi-asserted-by":"crossref","unstructured":"Lemos H, Prates M, Avelar P, Lamb L (2019) Graph colouring meets deep learning: effective graph neural network models for combinatorial problems. In: 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), p. 879\u2013885. IEEE","DOI":"10.1109\/ICTAI.2019.00125"},{"key":"1355_CR23","doi-asserted-by":"crossref","unstructured":"Prates M, Avelar PHC, Lemos H, Lamb LC, Vardi MY (2019) Learning to solve np-complete problems: A graph neural network for decision tsp. In: Proceedings of the AAAI Conference on Artificial Intelligence, volume\u00a033, p. 4731\u20134738","DOI":"10.1609\/aaai.v33i01.33014731"},{"key":"1355_CR24","unstructured":"Selsam D, Lamm M, B\u00fcnz B, Liang P, de\u00a0Moura L, Dill DL (2018) Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03685"},{"issue":"2","key":"1355_CR25","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s41019-021-00155-3","volume":"6","author":"Y Peng","year":"2021","unstructured":"Peng Y, Choi B, Jianliang X (2021) Graph learning for combinatorial optimization: a survey of state-of-the-art. Data Sci Eng 6(2):119\u2013141","journal-title":"Data Sci Eng"},{"key":"1355_CR26","unstructured":"Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. In: Advances in Neural Information Processing Systems, 28"},{"key":"1355_CR27","unstructured":"Kool W, Van\u00a0Hoof H, Welling M (2018) Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475"},{"key":"1355_CR28","unstructured":"Sato R, Yamada M, Kashima H (2019) Approximation ratios of graph neural networks for combinatorial problems. In: Advances in Neural Information Processing Systems, 32"},{"key":"1355_CR29","doi-asserted-by":"crossref","unstructured":"Bai Y, Ding H, Bian S, Chen T, Sun Y, Wang W. Simgnn: A neural network approach to fast graph similarity computation. In: Proceedings of the twelfth ACM International Conference on Web Search and Data Mining, p. 384\u2013392","DOI":"10.1145\/3289600.3290967"},{"issue":"5","key":"1355_CR30","doi-asserted-by":"publisher","first-page":"2033","DOI":"10.1109\/TKDE.2020.3008732","volume":"34","author":"W Fan","year":"2020","unstructured":"Fan W, Ma Y, Li Q, Wang J, Cai G, Tang J, Yin D (2020) A graph neural network framework for social recommendations. IEEE Trans Knowl Data Eng 34(5):2033\u20132047","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"5","key":"1355_CR31","first-page":"1","volume":"55","author":"W Shiwen","year":"2022","unstructured":"Shiwen W, Sun F, Wentao Z, Xie X, Cui B (2022) Graph neural networks in recommender systems: a survey. ACM Comput Surv 55(5):1\u201337","journal-title":"ACM Comput Surv"},{"issue":"4","key":"1355_CR32","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.cels.2020.08.016","volume":"11","author":"A Strokach","year":"2020","unstructured":"Strokach A, Becerra D, Corbi-Verge C, Perez-Riba A, Kim PM (2020) Fast and flexible protein design using deep graph neural networks. Cell Syst 11(4):402\u2013411","journal-title":"Cell Syst"},{"key":"1355_CR33","unstructured":"Xin Z, Yixin L, Shirui P, Miao Z, Di\u00a0J, Philip\u00a0SY (2022) Graph neural networks for graphs with heterophily: a survey. arXiv preprint arXiv:2202.07082"},{"key":"1355_CR34","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/B:ANOR.0000032574.01332.98","volume":"130","author":"N Barnier","year":"2004","unstructured":"Barnier N, Brisset P (2004) Graph coloring for air traffic flow management. Ann Oper Res 130:163\u2013178","journal-title":"Ann Oper Res"},{"key":"1355_CR35","unstructured":"Li W, Li R, Ma Y, On Chan S, Pan D, Yu B (2022) Rethinking graph neural networks for the graph coloring problem. arXiv preprint arXiv:2208.06975"},{"issue":"4","key":"1355_CR36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.4.043131","volume":"4","author":"MJA Schuetz","year":"2022","unstructured":"Schuetz MJA, Brubaker JK, Zhu Z, Katzgraber HG (2022) Graph coloring with physics-inspired graph neural networks. Phys Rev Res 4(4):043131","journal-title":"Phys Rev Res"},{"key":"1355_CR37","unstructured":"Zhang M, Chen Y (2018) Link prediction based on graph neural networks. In: Advances in Neural Information Processing Systems, 31"},{"key":"1355_CR38","volume-title":"Graph coloring problems","author":"TR Jensen","year":"2011","unstructured":"Jensen TR, Toft B (2011) Graph coloring problems. Wiley, New York"},{"key":"1355_CR39","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.aiopen.2021.01.001","volume":"1","author":"J Zhou","year":"2020","unstructured":"Zhou J, Cui G, Shengding H, Zhang Z, Yang C, Liu Z, Wang L, Li C, Sun M (2020) Graph neural networks: a review of methods and applications. AI Open 1:57\u201381","journal-title":"AI Open"},{"issue":"1","key":"1355_CR40","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","volume":"32","author":"Z Wu","year":"2020","unstructured":"Wu Z, Pan S, Chen F, Long G, Zhang C, Philip SY (2020) A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst 32(1):4\u201324","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"1355_CR41","unstructured":"Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in Neural Information Processing Systems, 29"},{"key":"1355_CR42","unstructured":"Wu F, Souza A, Zhang T, Fifty C, Yu T, Weinberger K (2019) Simplifying graph convolutional networks. In: International Conference on Machine Learning, p. 6861\u20136871. PMLR"},{"key":"1355_CR43","doi-asserted-by":"crossref","unstructured":"Bo D, Wang X, Shi C, Shen H (2021) Beyond low-frequency information in graph convolutional networks. In: Proceedings of the AAAI Conference on Artificial Intelligence 35, p. 3950\u20133957","DOI":"10.1609\/aaai.v35i5.16514"},{"key":"1355_CR44","unstructured":"Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE (2017) Neural message passing for quantum chemistry. In: International Conference on Machine Learning, p. 1263\u20131272. PMLR"},{"key":"1355_CR45","unstructured":"Battaglia PW, Hamrick JB, Bapst V, Sanchez-Gonzalez A, Zambaldi V, Malinowski M, Tacchetti A, Raposo D, Santoro A, Faulkner R, et\u00a0al. (2018) Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261"},{"key":"1355_CR46","unstructured":"Chami I, Ying Z, R\u00e9 C, Leskovec J (2019) Hyperbolic graph convolutional neural networks. In: Advances in Neural Information Processing Systems, 32"},{"key":"1355_CR47","doi-asserted-by":"crossref","unstructured":"Morris C, Ritzert M, Fey M, Hamilton WL, Lenssen JE, Rattan G, Grohe M (2019) Weisfeiler and leman go neural: higher-order graph neural networks. In: Proceedings of the AAAI Conference on Artificial Intelligence 33, p. 4602\u20134609","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"1355_CR48","unstructured":"Pei H, Wei B, Chang KCC, Lei Y, Yang B (2020) Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287"},{"key":"1355_CR49","first-page":"1","volume":"71","author":"Z Kong","year":"2022","unstructured":"Kong Z, Jin X, Zhengguo X, Zhang B (2022) Spatio-temporal fusion attention: a novel approach for remaining useful life prediction based on graph neural network. IEEE Trans Instrum Meas 71:1\u201312","journal-title":"IEEE Trans Instrum Meas"},{"key":"1355_CR50","doi-asserted-by":"crossref","unstructured":"Si C, Chen W, Wang W, Wang L, Tan T (2019) An attention enhanced graph convolutional lstm network for skeleton-based action recognition. In: Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition, p. 1227\u20131236","DOI":"10.1109\/CVPR.2019.00132"},{"key":"1355_CR51","unstructured":"Thekumparampil KK, Wang C, Oh S, Li L-J (2018) Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv:1803.03735"},{"issue":"4","key":"1355_CR52","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz A, de Werra D (1987) Using tabu search techniques for graph coloring. Computing 39(4):345\u2013351","journal-title":"Computing"},{"key":"1355_CR53","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P Galinier","year":"1999","unstructured":"Galinier P, Hao J-K (1999) Hybrid evolutionary algorithms for graph coloring. J Comb Optim 3:379\u2013397","journal-title":"J Comb Optim"},{"issue":"1","key":"1355_CR54","first-page":"1929","volume":"15","author":"N Srivastava","year":"2014","unstructured":"Srivastava N, Hinton G, Krizhevsky A, Sutskever I, Salakhutdinov R (2014) Dropout: a simple way to prevent neural networks from overfitting. J Mach Learn Res 15(1):1929\u20131958","journal-title":"J Mach Learn Res"},{"key":"1355_CR55","first-page":"7793","volume":"33","author":"J Zhu","year":"2020","unstructured":"Zhu J, Yan Y, Zhao L, Heimann M, Akoglu L, Koutra D (2020) Beyond homophily in graph neural networks: current limitations and effective designs. Adv Neural Inf Process Syst 33:7793\u20137804","journal-title":"Adv Neural Inf Process Syst"},{"issue":"1","key":"1355_CR56","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.aim.2009.08.006","volume":"223","author":"G Kemkes","year":"2010","unstructured":"Kemkes G, P\u00e9rez-Gim\u00e9nez X, Wormald N (2010) On the chromatic number of random d-regular graphs. Adv Math 223(1):300\u2013328","journal-title":"Adv Math"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01355-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-024-01355-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01355-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,14]],"date-time":"2024-11-14T07:53:00Z","timestamp":1731570780000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-024-01355-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1355"],"URL":"https:\/\/doi.org\/10.1007\/s40747-024-01355-w","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"assertion":[{"value":"10 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}