A Graph Neural Network with Negative Message Passing for Graph Coloring
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 recommended systems and drug
synthesis. Most existing research focuses on using graph neural networks to
solve homophilous problems, but little 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 conventional graph networks, we introduce negative message
passing into the proposed graph neural network for more effective information
exchange in handling graph coloring problems. Moreover, a new loss function
taking into account the self-information of the nodes is suggested to
accelerate the learning process. 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 one real-world application.
Numerical results demonstrate the effectiveness of the proposed graph neural
network.
Xiangyu Wang, Xueming Yan, Yaochu Jin
# A Graph Neural Network with Negative Message Passing for Graph Coloring

###### Abstract

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 recommended systems and drug synthesis. Most existing research focuses on using graph neural networks to solve homophilous problems, but little 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 conventional graph networks, we introduce _negative message passing_ into the proposed graph neural network for more effective information exchange in handling graph coloring problems. Moreover, a new loss function taking into account the self-information of the nodes is suggested to accelerate the learning process. 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 one real-world application. Numerical results demonstrate the effectiveness of the proposed graph neural network.

 graph neural networks, graph coloring, negative message passing, self-information, aggregator

## I Introduction

Different types of data, such as traditional unordered data, time series structured data, and graph-structured data may be encountered in solving real-world optimization problems. Graph-structured data contains rich relationship information between the attributes, making it more challenging to effectively learn the knowledge in the data using traditional machine learning models. Recently, graph neural networks (GNNs) have become extremely popular in the machine learning community, thanks to their strong ability to capture relational information in the data. Many different types of GNNs have been proposed, and they can be usually categorized according to different aggregation methods, such as graph convolutional network (GCN) [1], GraphSAGE [2], graph attention network (GAT) [3], among others. Since GNN enables the nodes to aggregate their neighbors' information, it becomes a powerful tool for solving problems in social networking [4], bioinformatics [5], and community detection [6], to name a few. Node classification is often considered as bi- or multi-class classification problems by inputting the features of nodes and edges and outputting each node's probability belonging to different classes. During the optimization process, each node combines information of its own and its neighbors to generate embedding vectors. By representing node and edge features in a higher dimensional space, embedding vectors are used to solve problems by downstream machine learning tasks in a non-autoregression or autoregression way [7].

However, most of the optimization problems mentioned above are continuous and homophilous. That is, two nodes between one edge tend to be very similar, i.e., have similar embedding vectors. These homophilous problems described as graphs have many real-world applications, and have been studied extensively [8, 9, 10]. On the contrary, some problems contain heterophily property [11] where the connected nodes have as different embeddings as possible. For example, graph coloring problems (GCPs) are a type of classical heterophilous problems because they are defined to have different colors between the connected nodes. GCPs have attracted increased research interest since many real-world applications can be formulated as graph coloring problems, such as arranging timetables and schedules, managing air traffic flow, and many others [12]. In fact, GCPs, like most combinatorial optimization problems (COPs), are NP-hard problems, which require highly intensive computational costs to obtain the exact optimal solutions. Luckily, some approaches have been proposed to find approximate optimal solutions of COPs with the help of GNNs within an acceptable period of computation time [13, 14, 15]. For example, Liu _et al._[16] proposed two supervised residual gated GCNs to directly predict the entire Pareto set for multi-objective facility location problems.
GNNs have inherent advantages to represent GCPs and solve such graph-structured problems, as samples (nodes) can aggregate information from their neighbors. Recently, some efforts have been made to apply GNNs to solve GCPs, and different structured graph neural networks have been proposed. GNN-GCP [17] uses a network containing a GNN to predict the chromatic number of a given graph and uses the generated embedding vectors for clustering to obtain a color assignment. Li _et al._[18] explored several rules for using a GNN to solve GCPs, and proposed a graph neural network called GDN. PI-GNN [19] is inspired by a Potts model, and it is shown to perform well by combining with a novel loss function.

The above algorithms basically follow the classical network structures, which are proposed to solve homophilous problems, such as node classification and link prediction [20]. However, these structures may not necessarily be suited for solving GCPs, and improvements should be made in the structural design to better adapt to the heterogeneous characteristics of GCPs. For this reason, a negative message passing strategy is proposed considering the requirements for GCPs, i.e., two connected nodes should have as different embedding vectors as possible. Meanwhile, color assignment with no conflict and stable convergence during the training process are both desired when solving GCPs. Therefore, a loss function consisting of a utility objective and a convergence objective is proposed to guarantee the good performance of the proposed neural network and a stable training process.

Section II presents the preliminaries of this work, including the definition of graph coloring problems, the aggregation methods of classical GNNs, and the related work that use GNNs to solve graph coloring problems. In Section III, the proposed graph network model with negative message passing and a new loss function is detailed. Section IV describes the experimental results on the benchmark graph coloring problems and a real-world problem. Ablation studies and analysis of the computational complexity are also presented. Finally, conclusions and future work are given in Section V.

## II Preliminaries

### _Definition of Graph Coloring Problems_

We consider an undirected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}=\{1,2,\ldots,n\}\) is the node set, and \(\mathcal{E}\) is the edge set connecting two nodes, represented by \((u,v)\in\mathcal{E}\). The adjacency matrix \(A\) of a graph \(\mathcal{G}\) also represents the connection between the nodes. When nodes \(i\) and \(j\) are connected, \(A(i,j)\) and \(A(j,i)\) are equal to 1; otherwise, elements in these two positions of \(A\) are equal to 0.

Graph coloring problems [21, 22, 23] aim to minimize the number of conflicts while using the minimum number of colors. Mathematically, GCPs can be formulated in two different forms. In the first formulation, GCPs are defined as a constrained minimization problem as follows:

\[\min k, \tag{1}\] \[\mathrm{s.t.}\sum_{(u,v)\in\mathcal{E}}f(u,v)=0,\]

where \(f(u,v)\) represents the clash between neighboring nodes \(u\) and \(v\), and \((u,v)\in\mathcal{E}\). If \(u\) and \(v\) share the same color, \(f(u,v)=1\); otherwise, \(f(u,v)=0\). \(k\) is the number of colors used in graphs. If \(k\) colors can fill a graph with no clash, this graph is called \(k\)-colorable. The chromatic number \(\mathcal{X}(\mathcal{G})\) is the minimum of \(k\), denoting the optimum number of colors without resulting in any conflicts in \(\mathcal{G}\).

Alternatively, GCPs can also be expressed as a constraint satisfaction problem with a given number of colors \(k\):

\[\min \sum_{(u,v)\in\mathcal{E}}f(u,v), \tag{2}\] \[\mathrm{s.t.} k.\]

This formulation aims to minimize the clashes in a graph, given that the number of colors that can be used is \(k\).

The optimization problems defined in Eq. (1) and Eq. (2) are slightly different, which may be suited for different requirements or priorities in solving the same problem. Take the assignment of taxis to customer requests as an example. In Eq. (1), the customer requests are the top priority, and a minimal number of taxis should be found. In this case, the assumption is that there is a sufficient number of taxis. However, if the number of taxis is limited during the peak period, the assignment that can satisfy the majority of customer requests would be preferred. This work will focus on minimizing the number of total conflicts under a certain given number of colors, i.e., the GC problem will be solved according to the formulation in Eq. (2).

An illustrative example consisting of six nodes and seven edges is given in Fig. 1. In Fig. 1 (a), three colors are used, and no connected neighboring nodes have the same color, meaning that this is an optimal solution to the given example.

Fig. 1: Example solutions to graph coloring with six nodes and seven edges. (a) An optimal solution for the given problem, where \(\mathcal{X}(\mathcal{G})=3\). (b) The number of total conflicts is zero, but the number of used colors can be reduced. (c) A solution using only two colors, while the \(\mathcal{X}(\mathcal{G})\) being \(3\), and the number of total conflicts should be minimized.
By contrast, as shown in Fig. 1(b), there is no conflict between the neighboring nodes, but the number of colors used can still be further minimized. In Fig. 1 (c), on the other hand, only two colors have been used, and there is one conflict in color. Overall, Fig. 1 (a) provides an ideal solution, while solutions in Fig. 1 (b) and (c) may also be applicable in different scenarios.

### _Classical GNNs_

The main difference between graph neural networks and other neural networks is that the nodes (samples) in GNNs can gather information from their neighbors before being projected to the next layer, due to the existence of edges [24, 25]. Aggregating embeddings from neighbors and combining them with the node's embedding are two critical operators in GNNs called aggregation and combination. Authors in [18] consider GNNs with aggregation and combination operators as AC-GNNs. They make GNNs powerful in exploiting and revealing relationships between nodes.

The input to GNNs is usually the feature vector or randomly-generated vector of each node. With an adjacency matrix, one node generates a new embedding in the next hidden layer by combining its own and neighbors' aggregated embedding. Therefore, embeddings in the first layer contain first-order neighborhood information and the \(k\)-th hidden layer captures the \(k\)-th neighborhood information. The aggregation and combination operators may differ in various GNNs based on different purposes and optimization tasks. In the following, we briefly review some classical and popular aggregation and combination methods.

GCN [1] considers the equal importance of a node and its neighbor information, which integrates the aggregation and combination methods. The embedding of the \(k\)-th layer is calculated by \(H^{k}=\sigma(\hat{A}H^{k-1}W^{k-1})\), where \(\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}\) is the normalized adjacency matrix with self connections, \(D\) is the degree matrix, and \(W^{k-1}\) is a trainable weight matrix of the \(k-1\)-th layers. On the other hand, some GNNs separate the aggregation and combination methods, assigning different importance to the node embedding and the aggregated neighborhood embedding. GraphSAGE [2] is one example of this type; the embedding of node \(v\) in the \(k\)-th hidden layer is obtained by \(h_{v}^{k}\leftarrow\sigma(W^{k-1}\cdot CONCAT(h_{v}^{k-1},h_{\mathcal{N}(v)} ^{k}))\), where \(h_{\mathcal{N}(v)}^{k}\gets AGGREGATE(h_{u\in\mathcal{N}(v)}^{k-1})\). There are also many other types of aggregation and combination methods proposed very recently, such as HetGNN [26], DNA [27], non-local graph neural networks [28], and SAR [29].

### _Related Work_

Only sporadic work on solving graph coloring problems with the help of graph neural networks have been reported, which are based on supervised or unsupervised learning.

GNN-GCP [17] generates color embeddings and node embeddings with a process of learning whether the graph is \(k\)-colorable or not. At first, \(2^{15}\) positive and \(2^{15}\) negative GCP instances are generated with ground truth given by a GCP solver. The proposed neural network learns the difference between the ground truth and the prediction by using the binary cross entropy as a loss function. The prediction is gotten through a GNN to aggregate neighbor information, an RNN to update the embeddings, and an MLP to get the final logit probability. If the network predicts a graph is k-colorable, the second stage is applied by clustering vertex embeddings using k-means, and nodes in the same cluster share the same color.

Different from the above work that relies on supervised learning and a set of pre-solved GCP instances, unsupervised learning has also been adopted to tackle GCPs by constructing a loss function without requiring the ground truth. In general, the output of unsupervised learning for GCPs are probability vectors of the nodes, indicating which color should be assigned to each node. GDN [18] uses a margin loss function, which minimizes the distance between a pre-defined margin and a Euclidean distance between node pairs. Schuetz _et al._[19] take advantage of the close relationship between GCPs and the Potts model so that the partition function of the Potts model can be converted to the chromatic function of \(\mathcal{G}\) mathematically. Besides, the Potts model only distinguishes whether neighboring spins are in the same state or not, which is very similar to the definition of GCPs. Consequently, a loss function is proposed in PI-GNN that minimizes the inner product of node pairs. Generally, loss functions in unsupervised learning usually aim to minimize the similarity between the connected nodes in solving heterophilous problems such as graph coloring problems.

Besides, solving GCPs with heuristic algorithms has also been studied. Tabucol [30] is a Tabu-based algorithm that defines Tabu moves and a Tabu list tailored for GCPs. It changes the color (for example, red) of one randomly selected node into another color (green) to reduce the number of conflicts. The color set (green, red) will be put into the Tabu list for certain iterations to restrict this node from changing to red. An evolutionary algorithm, HybridEA [31] is proposed to modify traditional ways of generating offspring and use a Tabu-search method as the mutation operator.

## III The Proposed Graph Neural Network Model

The main difference between heterophilous and homophilous optimization problems is that connected nodes in shared edges should express differently rather than similarly. For example, in node classification tasks, neighboring nodes should be classified into different classes instead of the same class. Therefore, the embeddings of connected nodes should be as different as possible, and the first-order neighbors need to pass negative messages to the node. On the other hand, the second-order neighborhood may contain information that positively impacts the node. Therefore, inspired by the heterophilous property of graph coloring problems, we proposed a new AC-GNN, which is called GNN-1N by mainly focusing on the first-order (1st) negative message passing strategy.

To better solve GCPs, the proposed algorithm should take into account two objectives. One is to find a solution without conflict and the other is to achieve fast and stable convergence. Based on the above two objectives, a loss function for solving graph coloring problems in an unsupervised way is proposed.
### _Forward Propagation_

The forward propagation of the proposed framework is described in this subsection. We apply GraphSAGE [2] as a baseline GNN model, and some modifications specialized for solving GCPs are made. In the original paper of GraphSAGE, the authors give three aggregation methods: mean aggregator, LSTM aggregator, and pool aggregator. The embedding \(h_{v}^{k}\) of node \(v\) in the \(k\)-th layer using the mean aggregator is calculated as follows:

\[\begin{split}& h_{\mathcal{N}(v)}^{k}=mean\{h_{u}^{k-1}\},\forall u \in\mathcal{N}(v),\\ & h_{v}^{k}=\sigma\left(W_{self}^{k}\cdot h_{v}^{k-1}+W_{neigh}^ {k}\cdot h_{\mathcal{N}(v)}^{k}\right),\end{split} \tag{3}\]

where \(\mathcal{N}(v)\) is the connected node set of node \(v\), \(h_{\mathcal{N}(v)}^{k}\) is the aggregated embedding of neighborhood of \(v\), \(\sigma\) is the activation operator, \(W_{self}^{k}\) and \(W_{neigh}^{k}\) is the learnable weight matrix for the \(k\)-th layer. In this work, the mean aggregator is considered for improvement.

At the beginning of forward propagation, the embedding of each node is usually the feature vector. However, some graphs in GCPs may not have features, so embeddings are generated randomly. In the first hidden layer, nodes gather the first-order neighborhood information, which should make negative contributions. Thus, the embedding of the first layer is obtained by

\[\begin{split}& h_{\mathcal{N}(v)}^{1}=mean\{h_{u}^{0}\},\forall u \in\mathcal{N}(v),\\ & h_{v}^{1}=\sigma\left(W_{self}^{1}\cdot h_{v}^{0}-\alpha\cdot W _{neigh}^{1}\cdot h_{\mathcal{N}(v)}^{1}\right),\end{split} \tag{4}\]

where \(h_{v}^{0}\) is the randomly generated feature of the input layer of node \(v\), \(\alpha\) is the trainable parameter controlling the negative influence of the neighborhood. Elements in \(W_{self}^{1}\) and \(W_{neigh}^{1}\) are all positive values distributed uniformly from 0 to 1, and \(\alpha\) is initialized to be \(0.5\).

This strategy is reasonable and natural. For example, we assume that there is node \(v\) and its two neighbors \(u_{1}\) and \(u_{2}\), whose embeddings are \([0.8,0.6,0.1]\), \([0.7,0.1,0.1]\), and \([0.5,0.1,0.7]\), respectively. We let \(W_{self}^{1}\) and \(W_{neigh}^{1}\) be an identity matrix, and \(\alpha=0.5\), the embedding of node \(v\) is \([0.5,0.55,-0.1]\) calculated by Eq. (4). If embeddings also represent the probability of the assigned color, \(v\) and \(u_{1}\) conflict with each other before applying Eq. (4), as these two nodes both prefer the first color among the three given colors. The assigned color of node \(v\) changes into the second one after applying Eq. (4). On the other hand, if Eq. (3) is used as an updating strategy in the first hidden layer, \(v\) and \(u_{1}\) will remain to be conflicting with each other.

According to the property of GNNs, the second hidden layer can aggregate the second-order neighborhood information, which may be able to contribute some helpful positive influence. Therefore, in the second-order layer, the original mean aggregator (Eq. (3)) of GraphSAGE is used to generate embeddings \(h_{v}^{2}\).

For graph coloring problems, there are two ways to assign colors to nodes. Firstly, there are \(k\) sets containing nodes, and all nodes in one set have the same color. The second way uses the \(k\)-length probability vector of each node, and the node is assigned to the \(i\)-th color if the probability in the \(i\)-th position of the vector is the largest. This work considers GCPs as an unsupervised classification task, and the second way is used to assign \(k\) colors to different nodes. Therefore, the dimension of \(h_{v}^{2}\) equals the color number \(k\). The probability of node \(v\) can be obtained as follows:

\[p_{v}=softmax\{h_{v}^{2}\}, \tag{5}\]

where \(softmax\) is the softmax operator, i.e., \(p_{v}(j)=\frac{h_{v}^{2}(j)}{\sum_{i=1}^{k}h_{v}^{2}(i)}\). The final color assigned to \(v\) is the color with the highest probability.

### _Loss Function_

A loss function is proposed to achieve the utility-based and the convergence-based goal in an unsupervised way. The former is to minimize the conflicts between the connected nodes with a given number of colors, while the latter is to minimize the uncertainty of nodes, which can stabilize convergence.

As no ground truth is available, the utility-based objective function uses the probability of nodes to reflect the relationship of connected nodes. The main idea is to maximize the difference or minimize the similarity between node pairs. Some loss functions have been proposed based on the above idea. Among them, the loss function inspired by the Potts model performs very well, which is therefore adopted as the utility-based objective function in this work:

\[f_{utility}=\sum_{(u,v)\in\mathcal{E}}p_{v}^{T}\cdot p_{u}. \tag{6}\]

Eq. (6) only aims to minimize the inner product between two probabilities, which can be considered as minimizing the similarity between two nodes. This is reasonable for solving heterophilous problems such as GCPs. Note that no other _a priori_ knowledge is required, making it suitable for solving other unsupervised learning problems.

Fig. 2: The framework of the proposed method, where the first-order aggregator applies Eq. (4) and the second-order aggregator uses the original aggregator Eq. (3). Between the first and the second hidden layers, dropout is employed to avoid getting stuck in local optimums.
In addition to maximizing the difference between the connected nodes, we also intend to increase the probability of one node being assigned a certain color to make the learning process more stable. Therefore, we introduce self-information to construct \(f_{conv}\), which is formulated as follows:

\[f_{conv}=\sum_{i=1}^{n}p_{i}^{T}\cdot\log p_{i}. \tag{7}\]

Self-information represents the amount of information in an event. If the value of self-information is large, it means this event contains more information, indicating a high uncertainty. Otherwise, the uncertainty of this event is low. In terms of GCPs, high self-information of one node means the probabilities of being assigned to different colors are approximately equal. It results in unstable convergence because the color assignment varies greatly under small weight changes. Therefore, nodes with small self-information hold more confidence in the current color assignments, which helps stabilize the convergence.

By combining the terms in Eq. (6) and Eq. (7), we get the following loss function:

\[\min F=f_{utility}+\lambda f_{conv}. \tag{8}\]

where \(\lambda>0\) is a hyperparameter.

### _The Overall Framework_

As shown in Fig. 2, the framework mainly consists of the forward propagation and the optimization process. In the forward propagation, the randomly generated embedding \(h_{i}^{0}\) is assigned to the \(i\)-th node. If we take \(n_{1}\) as an example, it aggregates its first-order negative neighborhood embedding in the first hidden layer, and its second-order neighborhood embedding in the second layer. Between these two hidden layers, the dropout [32] is applied to prevent the solver from getting stuck in a local optimum. After \(n_{1}\) aggregates the two-hop neighborhood information, \(h_{1}^{2}\) is obtained, followed by the softmax function to get a probability vector \(p_{1}\). \(p_{1}\) contains \(k\) elements representing the probabilities of choosing \(k\) colors. After getting the probability vectors of nodes, the loss function \(F\) is calculated with two terms, namely \(f_{utility}\) and \(f_{conv}\). The AdamW optimizer is used to compute the gradient and update weights in the graph neural network.

## IV Numerical Experiments

In this section, experiments on the COLOR dataset [33] are presented at first, and then an application to taxi scheduling is applied. An ablation study is given to demonstrate the stabilization ability of the proposed loss function, and finally, the computational complexity is analyzed.

### _Experiments on COLOR Dataset_

In this experiment, we use the publicly available COLOR dataset to evaluate the performance of the proposed algorithm and its peer methods. The COLOR dataset is a classical, widely used graph dataset in the field of graph coloring problems, where Myciel graphs are based on the Mycielski transformation and Queens graphs are constructed on \(n\) by \(n\) chessboard with \(n^{2}\) nodes. More detailed information on graphs can be found in Table 1, with the number of nodes and edges in each graph. Eq. (2) is optimized in the following experiments given the color number \(k\), which is shown in Table 1.

Five algorithms are chosen as peer algorithms: Tabucol [30], HybridEA [31], GDN [18], PI-GCN [19], and PI-SAGE [19]. Tabucol and HybridEA are tabu-based heuristics algorithms. The rest three algorithms, GDN, PI-GCN, and PI-SAGE, are GNN-based unsupervised algorithms. The above five methods focus on minimizing conflicts with given numbers of colors. GNN-GCP mainly predicts the color number of a given graph. Therefore, it is not included in this comparison. The results in Table I show the conflicts of each graph (\(f(u,v)\) in Eq. (6)) found by the proposed GNN-1N and the algorithms under comparison.

The results of Tabucol and HybridEA are taken from [18], with a maximum run time, i.e., 24 hours per graph, and the results of GDN, PI-GCN, and PI-SAGE are taken from [19]. For a fair comparison, we use the same maximum number of iterations (\(10^{5}\)) to run our methods (GNN-1N) on GPU. Besides, the early stopping mechanism is applied within \(10^{3}\) iterations if the value of the loss function changes less than \(0.001\). The hyperparameters, including the dimensions of \(h_{i}^{k}\), the learning rate \(\eta\) in the AdamW optimizer, the probability of dropout, and \(\lambda\) in the loss function \(F\) are optimized in a similar way to that in [19]. All results listed in Table I are the best coloring results of all methods, from which we can see that the proposed method performs the best on all graphs, especially on large and dense graphs, such as queen11-11 and queen13-13. On the contrary, traditional tabu-based methods and other machine-learning methods cannot find as few conflicts as GNN-1N does.

To gain more insights into the solutions found by our methods, we plot the color assignment of queen13-13 in Fig.

Fig. 3: The final color assignment of queen13-13 with 169 nodes given by our method. Only 15 conflicts highlighted in red lines exist out of 3328 edges (in grey lines) in this figure.
3. There are 169 nodes in this graph, and 13 colors should be used to color nodes. There are 3328 edges plotted with grey lines and 15 conflicted edges highlighted with red lines. The normalized error rate is \(0.45\%=\frac{15}{3328}\times 100\%\), which is relatively small, indicating that our method has a good ability to find less-conflict color assignments.

### _Application_

In this section, we take the taxi scheduling problem as an example to show the ability of GNN-1N to solve graph-structured problems in real life. We give a simple scenario for taxis to customer requests. Seven customs call a taxi company to book taxis one day. They all plan to book a taxi during the evening rush hour from 17:00 to 18:00 and each confirms a time period. The task is to satisfy all customers' requests with an available number of taxis, assuming that only four taxis are available during this peak hour.

To solve this problem, three steps are taken, which are 1) encoding, 2) optimization, and 3) decoding. The encoding step transfers the given timetable into a graph. As shown in Fig. 4 (a), the timetable with departure time and arrival time of seven customers is shown, and each customer is represented by a node in the graph. As customers with overlapping schedules cannot use the same taxi, two nodes should share one edge if two customers have time overlap. For example, the arrival time of customer \(u_{1}\) is earlier than the departure time of \(u_{2}\), so \(u_{1}\) and \(u_{2}\) are not connected. On the other hand, the first customer and the third customer plan to use a taxi from 17:13 to 17:15. Therefore, \(u_{2}\) and \(u_{3}\) are connected, as shown in Fig. 4 (b). After obtaining the graph description of the relationship between customers' schedules, the generated graph is optimized by GNN-1N with a specific color number. The color number is the number of available taxis, which is four here. Figure 4 (c) shows the final color assignments with four colors after optimization, and no conflict is found in the solution. According to the color assignment, seven customers are assigned into four groups, that is, \(\{u_{1},u_{2},u_{7}\}\), \(\{u_{3}\}\), \(\{u_{4},u_{6}\}\), and \(\{u_{5}\}\).

### _Ablation Study and Time Complexity Analysis_

An ablation study is conducted to show the effectiveness of self-information term \(f_{conv}\) (Eq. (7)) included in the loss function \(F\). Figure 5 shows the conflicts trained by the loss function with and without \(f_{conv}\) on queen6-6 and queen8-12 over \(10^{5}\) iterations. To be specific, Eq. (6) is the \(f_{utility}\) proposed in [19], and Eq. (8) is the loss function proposed in [19], the Eq. (8) is the loss function proposed in this paper with adding the self-information term. The hyperparameters are obtained directly from [19], and the \(\lambda\) in Eq. (8) is set to be \(0.25\). As we can see in Fig. 5, the conflicts curve obtained by Eq. (6) is unstable and fluctuates dramatically sometimes. By contrast, the conflicts curve trained by Eq. (8) decreases smoothly. The curves in Fig. 5 indicate the stabilization function of self-information, which can be attributed to the convergence term in Eq. (8).

The runtime (in seconds) is plotted in Fig. 6, which shows the time required by GNN-1N to run \(10^{5}\) iterations on one graph coloring problem. It is reasonable that the runtimes increase with the number of nodes and edges increase, because the computational cost is mainly concentrated in the process of node aggregation and backpropagation. In general, the time

Fig. 4: Taxi scheduling problem. (a) The timetable containing departure time and arrival time of seven customers. (b) Encoding the timetable into a graph coloring problem. (c) Optimizing the graph coloring problem with our unsupervised neural network method and decoding it. Under this scenario, customs and taxis are nodes and colors in graph coloring problems, respectively.
complexity of GNN-1N is similar to PI-GNN [19], as no additional computation is added to the proposed algorithm.

## V Conclusion and Future Work

The graph coloring problem is a classical graph-based problem aiming to find a color assignment using a given number of colors. As the GC problem is an NP-hard problem, it is almost impossible to obtain a feasible solution in an acceptable time. Moreover, due to its graph property, such problems cannot be easily and effectively solved by conventional neural networks. In this work, we propose an unsupervised graph neural network (GNN-1N) tailored for solving GCPs, which combines negative message passing with normal message passing to handle heterophily. Besides, a loss function with the utility-based objective and convergence-based objective is proposed for unsupervised learning. Experimental results on public datasets show that GNN-1N outperforms five state-of-the-art peer algorithms. In addition, a toy real-world application of graph coloring problems is also given to demonstrate further the effectiveness of GNN-1N.

Solving graph-based heterogeneous problems with GNNs is still in its infancy. The following three improvements could be made on the proposed model. First, we can consider pre-/post-processing to further decrease the number of conflicts. Second, the dynamic graph coloring problems are worthy of investigation, as the conditions may change in the real world. Finally, the fairness of color assignment is an interesting topic to examine. For example, each color should be used roughly the same number of times while making sure that there is no conflict in connecting nodes. For the taxi scheduling problem, each taxi should have a similar number of customers. Therefore, fairness coloring is of great practical importance.
