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\) nodes, demonstrating the effectiveness of the proposed graph neural network.
Hinweise
Part of this work was done when Y. Jin was with the Faculty of Technology, Bielefeld University, Germany supported by an Alexander von Humboldt Professorship for Artificial Intelligence.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
Different types of data, such as traditional unordered data [1‐3], time series structured data [4, 5], and graph-structured data [6, 7] may be encountered in solving real-world optimization problems. Graph-structured data contain 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) [8‐10] 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, such as graph convolutional networks (GCNs) [11], GraphSAGE [12], and graph attention networks (GATs) [13]. Since a GNN enables nodes to aggregate their neighbors’ information, it becomes a powerful tool for solving problems in graph-structured problems, such as social networking [14], bioinformatics [15], and community detection [16], to name a few. Node classification in graphs is often considered as bi- or multi-class classification problem by inputting the features of nodes and edges and outputting each node’s probability belonging to different classes [17, 18].
In fact, most combinatorial optimization problems (COPs) [19, 20, 23], for example GCPs, are NP-hard problems, requiring highly intensive computational costs to obtain the optimal solutions. Luckily, some approaches have been proposed to find approximate optimal solutions of COPs with the help of GNNs within an acceptable amount of computation time [21]. GNNs were explored for solving decision COPs, wherein the learned graph models determine whether the input problem is solvable under certain constraints [22‐24]. The output of these GNNs is binary, providing a ‘yes or no’ answer. To be specific, in Ref. [23], the trained GNN aims to determine whether the route of a given traveling salesman problem can be shorter than a certain threshold C. On the other hand, GNNs are used to generate solutions of COPs in a non-autoregressive or autoregressive manner [25]. Autoregressive methods predict a partial solution in each step, gradually constructing a complete solution [26, 27]. On the other hand, non-autoregressive GNNs produce a probability heatmap, allowing various search heuristics to be employed for finding solutions [28, 29].
Anzeige
However, most optimization problems mentioned above are under homophilous assumption. That is, two nodes between one edge tend to be very similar with possessing similar embedding or feature vectors. These homophilous problems described as graphs have many real-world applications, and have been widely studied [30‐32]. On the contrary, certain problems exhibit heterophily, as discussed in Ref. [33]. This implies that connected nodes should have different embeddings or they tend to be clustered into different groups rather than the same one. For example, graph coloring problems (GCPs) are a type of classical heterophilous problem because they are defined to have different colors between connected nodes. GCPs have attracted increased research interest because many real-world applications can be formulated as graph coloring problems, such as timetabling and scheduling, air traffic flow management [34], and even haplotype assembly and viral quasispecies reconstruction [15].
Recently, many efforts have been made to solve GCPs using GNNs with various structures. Lemos et al. [22] proposed a GNN-GCP that employs a recurrent graph neural network, trained in a supervised way using a binary entropy loss function, to predict whether the chromatic number of a given graph is a certain number and uses the generated embedding vectors to obtain a color assignment. On the other hand, unsupervised learning is applied to train GNNs for solving GCPs, since the ground truth of GCPs is not unique. Li et al. [35] explored several rules for using a GNN to solve GCPs and proposed a GNN called GDN. A margin loss function that minimizes the distance between a pre-defined margin and an Euclidean distance between node pairs is adopted. Schuetz et al. [36] suggested a physics-inspired GNN (PI-GNN), which is trained using a loss function inspired by a Potts model to minimize the inner product of the output of node pairs and is shown to perform very well. In general, loss functions used in unsupervised learning aim to maximize (minimize) the difference (similarity) between embeddings of connected nodes, however, there is no regularization term proposed to prevent solutions from getting stuck in local optima.
The above GNNs basically follow the classical network structures, which are designated for homophilous problems, such as node classification and link prediction [37]. 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 heterophilous nature of GCPs. For this reason, we propose a negative message-passing strategy considering the requirements for GCPs, i.e., two connected nodes should have strongly different embedding vectors. On the other hand, certain existing methods for GCPs encounter the challenge of being trapped in local optima, hindering further enhancements to solutions. In light of this, we propose a novel loss function. It comprises a utility-based term, serving as the primary objective to minimize the inner product between two probability vectors of connected nodes. In addition, there is a uniformity-based term designed to maximize the uniformity of color assignment for each node by leveraging information entropy from information theory. This idea stems from the insight that a high probability of assigning a specific color to a node correlates with a reduced likelihood of the node exploring alternative colors. Thus, our emphasis on promoting uniformity in the probability distribution for selecting different colors per node serves to alleviate the risk of solutions becoming trapped in possible local optima and give the graph neural network more chance to choose suitable colors for each node, ultimately yielding improved results.
“Preliminaries” presents the preliminaries of this work, including the definition of graph coloring problems, a brief introduction to message-passing strategies, and related work that uses GNNs to solve GCPs. In “The proposed model”, the proposed graph network model with negative message passing and a new objective function are presented in detail. “Theoretical proof” gives theoretical proof of the proposed message passing strategy. “Numerical experiments” describes the experimental results on widely used benchmark graph coloring problems and d-regular graphs. Sensitivity analysis of a hyperparameter in the objective function and an application case are also presented. Finally, conclusions, limitations, and future work are given in “Conclusion and future work”.
Anzeige
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 \(\varvec{A}\) of a graph \(\mathcal {G}\) also represents the connection between the nodes. When nodes i and j are connected, \(\varvec{A} (i,j)\) and \(\varvec{A}(j, i)\) are equal to 1; otherwise, elements in these two positions of \(\varvec{A}\) are equal to 0.
Graph coloring problems [38] aim to minimize the number of conflicts while using a minimum number of colors. Mathematically, GCPs can be formulated in two different forms. In the first formulation, GCPs are defined as follows:
where \(f_k(u,v)\) represents the clash between neighboring nodes u and v by using k colors, where \((u,v)\in \mathcal {E}\) and k (the number of colors to be used in a graph) is a variable to be optimized. If u and v share the same color, \(f_k(u,v)=1\); otherwise, \(f_k(u,v)=0\). 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 constrained optimization problem given the number of colors K:
The above formulation aims to minimize the clashes in a graph, given that K colors can be used.
The optimization problems defined in Eqs. (1) and (2) are 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 minimum 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 given number of colors, i.e., the GCP will be solved according to the formulation in Eq. (2).
Message-passing strategies
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 [39]. In general, GNNs can be classified into spectral-based and spatial-based methods. The former is mainly based on graph processing theory [40], which has more theoretical guarantees, such as GCN [11], ChebNet [41], SGC [42], FAGCN [43], among others. On the other hand, the spatial-based GNNs focus on aggregating neighbors’ information through edges, which is called a message-passing strategy. Thanks to its intuitive characteristics, many works have been proposed based on the idea of message-passing, such as MPNN [44], GAT [13], and so on [45‐51].
The key concepts of message-passing strategies are aggregation and combination. A general framework of message-passing strategies is first proposed in MPNN [44], which can be described as
In the given expression, \({\textbf {h}}_v^t\), \({\textbf {h}}_u^t\), and \({\textbf {e}}_{vu}\) denote the embeddings of node v, node u in the tth hidden layer, and the edge features, respectively. Here, \(\mathcal {N}(v)\) represents the set of neighbors of node v. The learnable matrix \(M_t\) and \(U_t\) in the tth hidden layer are optimized through the backpropagation.
Equation (3) aggregates embeddings from neighbors, while Eq. (4) combines them with the node’s embedding to get the updated node embeddings for the next layer. Therefore, embeddings in the first layer contain first-order neighborhood information and the kth hidden layer captures the kth neighborhood information.
Related work
Only sporadic attempts to solve GCPs with the help of GNNs have been reported, which are based on supervised or unsupervised learning.
GNN-GCP [22] generates color and node embeddings by learning whether the graph is k-colorable or not. At first, \(2^{15}\) positive and \(2^{15}\) negative GCP instances are generated with the 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 obtained through a GNN to aggregate neighbor information, a recurrent neural network to update the embeddings, and a multi-layer perceptron to get the final logit probability. If the network predicts a graph is k-colorable, then vertex embeddings are clustered 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 an objective 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. In GDN [35], a margin loss function that minimizes the distance between a pre-defined margin and an Euclidean distance between node pairs is adopted. Schuetz et al. [36] take advantage of the close relationship between GCPs and the Potts model so that the partition function of the Potts model can be converted into 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, an objective function is proposed in PI-GNN to minimize the inner product of node pairs. Usually, objective functions in unsupervised learning for solving GCPs aim to minimize the similarity of probability or embedding vectors between the connected nodes.
In addition, heuristic algorithms have also been studied to solve GCPs. Tabucol [52] 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 [53], is proposed to modify traditional ways of generating offspring and use a Tabu-search method as the mutation operator.
The proposed model
This section provides an in-depth exposition of the components of GNN-NU, our novel graph neural network incorporating Negative message passing and an objective function consisting a Uniformity maximization term.
Forward propagation
For homophilous optimization problems, the connected nodes in the shared edges should have a large degree of similarity. On the contrary, connected nodes for heterophilous problems should exhibit different behaviors. For example, in node classification tasks, neighboring nodes should be classified into different classes instead of the same class, which means the embeddings of connected nodes should be as different as possible. Therefore, a node’s first-order neighbors need to pass negative messages to it, while its second-order neighborhood may contain information that positively impacts the node (proof can be found in “Theoretical proof”). Next, we provide a comprehensive explanation of the forward propagation process of GNN-NU, which includes the negative message-passing strategy.
In most classification tasks or routing problems, there are features for each node, which can be treated as input for graph neural networks. By making full use of features, GNNs can extract sufficient information to achieve the training targets. However, nodes in GCPs do not contain any features, and topology information is vital for GNNs to solve GCPs. To allow the topology information to pass through the graph neural network, we randomly generate an embedding vector for each node in this work, similar to Ref. [36], which is learnable during training.
In the first hidden layer, nodes gather the first-order neighborhood information based on the proposed negative message-passing strategy. As a result, the aggregated embedding of node v in the first layer is obtained as follows:
where \(\varvec{h}_u^0\) is the randomly generated input embeddings of the node u, \(\mathcal {N}(v)\) is the connected node set of node v, \(\varvec{h}_{\mathcal {N}(v)}^1\) is the aggregated embedding of neighborhood of v in the first hidden layer. To be specific, \(\varvec{h}_{\mathcal {N}(v)}^1\) is generated by calculating the mean value of all embedding vectors of nodes in \(\mathcal {N}(v)\). The updated embedding of node v, \(\varvec{h}_v^1\), is obtained by combining the previous embedding vector \(\varvec{h}_v^0\) and the aggregated vector \(\varvec{h}_{\mathcal {N}(v)}^1\) by the following formula:
where elements in \(\varvec{W}_{self}^1\) and \(\varvec{W}_{neigh}^1\) are all initialized to be positive values, and \(\sigma \)\((\cdot )\) is the activation function ReLU.
The proposed negative message-passing strategy is intuitive for GCPs, in which the connected nodes should have different embeddings rather than similar ones. After getting embeddings of nodes in the first layer by negative message-passing strategy, the dropout [54] operator is applied to avoid the graph neural network being overfitting. Then, \(\varvec{h}_v^{1}\) is updated in the second layer using the normal message passing as follows:
where \(\mathcal {N}(v)\) is the connected node set of node v, \(\varvec{h}_{\mathcal {N}(v)}^2\) is the aggregated embedding of two-hop neighborhood of v in the second layer, \(\varvec{W}_{self}^2\) and \(\varvec{W}_{neigh}^2\) is the learnable weight matrix for the second layer. Like most other GNNs, the second hidden layer in our model aggregates the second-order neighborhood information based on the conventional mean aggregator (Eq. (7)) to generate embedding \(\varvec{h}_v^2\).
Here, we consider graph coloring problems as a K-class classification problem, where nodes in the same class share the same color. We follow the one-hot encoding to classify colors. Followed by a dropout operator applied to \(\varvec{h}_v^2\), the probability of colors being assigned to node v can be obtained as follows:
where softmax is the softmax operator. It can be written as \(\varvec{p}_v(j)=\frac{\varvec{h}_v^2(j)}{\sum _{i=1}^{K}\varvec{h}_v^2(i)}\), where \(\varvec{p}_v(j)\) and \(\varvec{h}_v^2(j)\) represent the jth element of \(\varvec{p}_v\) and \(\varvec{h}_v^2\), respectively. The final color assigned to v is the color with the highest probability.
Objective function
The GNN-NU model introduces a novel objective function designed to achieve two primary objectives: minimizing conflicts (utility-based \(f_1\)) and maximizing uniformity (uniformity-based \(f_2\)) in color assignments for each node. Specifically, the utility-based objective aims to minimize the conflicts between the connected nodes with a given number of colors, while the uniformity-based objective intends to maximize the uniformity of nodes to avoid getting stuck into the local optimum. This design empowers the model to discover a conflict-free global optimum.
As no ground truth is available, the utility-based term uses the probability of the nodes to reflect the relationship between the connected nodes, and the main idea is to maximize the difference or minimize the similarity between the node pairs. Some objective functions have been proposed in the literature based on the above idea. Among them, a function inspired by the Potts model has been shown to perform very well, which is therefore adopted as the utility-based term in this work:
Equation (9) aims to minimize the inner product between two probabilities, which can be considered as minimizing the similarity between two nodes.
In addition to the primary objective, we also include a second term in the proposed objective function to enhance the uniformity of color assignments for each node. This extension is motivated by the observation that existing unsupervised GNN models for GCPs only focus on minimizing conflicts by reducing similarity between connected nodes. However, when the probability of a specific color assigned to a node is close to one, the transition to another color becomes challenging, potentially leading to solutions being trapped in local optima. By adding the uniformity-based term, it could help nodes easier transfer from one color to another one during the training process, which can avoid suboptimal solutions.
To attain this goal, we seek a function capable of characterizing the probability distribution of color selection for individual nodes. Information entropy aligns with this requirement effectively, which can be calculated as follows:
$$\begin{aligned} f_2=\sum _{i=1}^n \mathbb E [- \log \varvec{p}_i(C)], \end{aligned}$$
(10)
where \({\varvec{p}}_i(C)\) represent the probability of node i choosing the color C among K given colors. From the above formula, we can see that the value of information entropy is the highest when K elements in \({\varvec{p}}_i\) are equal, which meets our idea of obtaining uniform probability for color assigning to each node. In other words, in the context of GCPs, high information entropy of one node means the probabilities of being assigned to different colors are approximately equal, which gives the neural network more chance to explore different color assignments and get better results.
By combining the terms in Eqs. (9) and (10), we get the following objective function:
where \(\lambda >0\) is a hyperparameter, \(\mathcal {|E|}\) and n are the number of edges and nodes, respectively, and K is the number of colors to be used in one graph. By multiplying \(\frac{\mathcal {|E|}}{n\cdot \log K}\) with \(f_2\), the scale between \(f_1\) and \(f_2\) is equal.
The overall framework
Fig. 1
The framework of the proposed method GNN-NU, where the first-order aggregator applies Eqs. (5) and (6) and the second-order aggregator uses the original aggregator in Eq. (7) for message passing. Dropout is employed between two hidden layers to avoid getting stuck in local optimums
×
As shown in Fig. 1, the framework mainly consists of the forward propagation and the optimization process. In the forward propagation, the randomly generated embedding \(\varvec{h}_i^0\) is assigned to the ith node. If we take node 1 as an example, it aggregates its first-order negative neighborhood embedding in the first hidden layer using Eqs. (5) and (6), and its second-order neighborhood embedding in the second layer by commonly used message-passing strategy in Eq. (7). Between these two hidden layers, dropout [54] is applied to prevent the solver from getting stuck in a local optimum. After node 1 aggregates the two-hop neighborhood information, \(\varvec{h}_1^2\) is obtained, followed by the softmax function to get a probability vector \(\varvec{p}_1\). \(\varvec{p}_1\) contains K elements representing the probabilities of choosing K colors. After getting the probability vectors of nodes, the objective function F is calculated with two terms, namely the utility-based \(f_1\) and uniformity-based \(f_2\). Color assignments without conflicts are not unique in most GCPs, because some nodes with lower degrees (connecting to fewer nodes) can be colored by more than one feasible color. Therefore, supervised learning is not suitable here, as labels are very diverse. Unsupervised learning is applied here to describe our objectives and guide the graph neural network to find a suitable color assignment with no conflict. After getting the loss function F, the AdamW optimizer is used to compute the gradient and update weights in the graph neural network.
Theoretical proof
Inspired by Ref. [55], we provide below a theoretical proof to support the proposed aggregation method, where the first-order neighboring nodes contribute negative impacts while the second-order ones contribute positively. Here, we only consider the most simple condition by analyzing a d-regular graph, in which every vertex is connected by d neighbors, and K colors are used.
Here, we set \(\textbf{Y}_{|\mathcal {V}|\times K}\) to be the ideal coloring assignment, in which the vth row represents node v being colored by the ith color with the ith column being one and rest being zero. We denote \(\varvec{y}_v = i\) as node v is colored by the ith color. For each \(v \in \mathcal {V}\), the color assignments of its neighbors are conditionally independent given \(\varvec{y}_v\). We could obtain the probability matrix for node v’s neighborhood, which is defined as follows:
where \([\textbf{P}_v]_{i,j} = P(\varvec{y}_u = j|\varvec{y}_v = i)\), meaning that the probability of node u has the jth color given node v has the ith color. In this matrix, the diagonal elements are all zeros, as two connected nodes should not have the same color. We derive the above matrix based on the definition of GCPs, and it is obvious that the first-order neighbors are always heterophilous, as \([\textbf{P}_v]_{i,i}<[\textbf{P}_v]_{i,j}\) when \(i \ne j \).
We assume that w is a second-hop neighbor of node v, i.e., \(w \in \mathcal {N}_2 \{v\}\). The probability of node w choosing the jth color given that node v chooses the ith color can be calculated as \(P(\varvec{y}_w=j|\varvec{y}_v=i)=\sum _{k'}P(\varvec{y}_w=j|\varvec{y}_u=k')\cdot P(\varvec{y}_u=k'|\varvec{y}_v=i) = [\textbf{P}_v]^2\):
In Eq. (13), for all i and j\((i \ne j)\), we have \([\textbf{P}_v]^2_{i,i}> [\textbf{P}_v]^2_{i,j}\), when \(K>1\). Therefore, the homophily is the predominant factor within the two-hop neighborhood given any node v. This aligns with our strategy to employ the standard aggregator in the second hidden layer, facilitating the integration of second-hop information.
In summary, we can conclude that in expectation, heterophily dominates in the first-order neighbors of GCPs while homophily dominates in the second-order neighbors if the color assignments of nodes are conditionally independent.
Table 1
Numerical results and data information for the COLOR dataset
Graph Name
K
# Nodes
# Edges
Tabucol
HybridEA
GDN
PI-GCN
PI-SAGE
GNN-NU
myciel5
6
47
236
0
0
0
0
0
0
myciel6
7
95
755
0
0
0
0
0
0
queen5-5
5
25
160
0
0
0
0
0
0
queen6-6
7
36
290
0
0
4
1
0
0
queen7-7
7
49
476
10
9
15
8
0
0
queen8-8
9
64
728
8
5
7
6
1
1
queen9-9
10
81
1056
5
6
13
13
1
1
queen8-12
12
96
1368
10
3
7
10
0
0
queen11-11
11
121
1980
33
22
33
37
17
13
queen13-13
13
169
3328
42
37
40
61
26
15
The bold values highlight the best or better results
Numerical experiments
In this section, experiments on the COLOR dataset1 and d-regular graphs are presented. Parameter analysis is conducted to demonstrate the ability and influence of the proposed uniformity-based term in the objective function. In addition, a simple application of GCPs is shown to illustrate the ability of GNN-NU to solve real-world graph-structured problems.
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, 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 the graphs can be found in Table 1, including the number of nodes and edges in each graph. Equation (2) is optimized in the following experiments given the color number K, which is shown in Table 1.
Five algorithms are chosen for comparison, namely Tabucol [52], HybridEA [53], GDN [35], PI-GCN [36], and PI-SAGE [36]. Tabucol and HybridEA are tabu search-based heuristics algorithms. The rest three algorithms, GDN, PI-GCN, and PI-SAGE, are GNN-based unsupervised learning algorithms. The above five methods focus on minimizing the conflicts with given numbers of colors. Note, however, that GNN-GCP mainly predicts the color number of a given graph. Therefore, it is not included in this comparison. The results in Table 1 show the conflicts of each graph, \(f_k(u,v)\) in Eq. (2), found by the proposed GNN-NU and the algorithms under comparison.
The results of Tabucol and HybridEA are taken from Ref. [35], with a maximum run time, i.e., 24 h per graph, and the results of GDN, PI-GCN, and PI-SAGE are taken from Ref. [36]. For a fair comparison, we use the same maximum number of iterations (\(10^5\)) to run our methods (GNN-NU) on NVIDIA A40. 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 \(\varvec{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 Ref. [36]. All results listed in Table 1 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 search-based methods and other machine learning methods cannot find as few conflicts as GNN-NU does.
To gain more insights into the solutions found by our methods, we plot the color assignment of queen13-13 in Fig. 2. There are 169 nodes in this graph, and 13 colors are used to color the 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 conflicting color assignments.
Fig. 2
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
×
Fig. 3
The runtimes (in seconds) of GNN-NU required on each graph coloring problem for \(10^5\) iterations
×
Fig. 4
The average time and cost of 3-regular and 6-regular graphs obtained by GNN-NU and PI-SAGE with the number of nodes ranging from 100 to 10,000
×
Table 2
The number of conflicts and consumption times averaged over ten independent runs for the d-regular graphs obtained by the peer algorithm PI-SAGE and the proposed algorithm GNN-NU
n
3-regular graph
6-regular graph
Conflicts
Time
Conflicts
Time
PI-SAGE
GNN-NU
PI-SAGE
GNN-NU
PI-SAGE
GNN-NU
PI-SAGE
GNN-NU
100
1.0(1.34)
0.0(0.00)
1.0(0.66)
0.6(0.17)
5.8(2.23)
0.0(0.00)
3.2(0.85)
4.5(3.15)
200
3.5(1.63)
0.0(0.00)
1.9(0.48)
1.1(0.40)
10.6(2.84)
0.0(0.00)
6.0(1.53)
8.4(5.74)
500
9.5(3.20)
0.0(0.00)
4.2(0.61)
5.1(4.01)
20.9(3.88)
0.0(0.00)
24.4(8.26)
19.5(9.33)
700
12.0(3.63)
0.0(0.00)
9.5(4.05)
7.0(3.97)
28.1(7.79)
0.0(0.00)
33.0(10.54)
25.7(10.67)
1000
16.5(4.18)
0.0(0.00)
11.7(3.90)
8.6(4.55)
33.1(5.58)
0.0(0.00)
78.0(13.28)
51.7(15.09)
2000
23.1(8.53)
0.0(0.00)
57.4(15.54)
26.6(17.58)
60.4(8.30)
0.0(0.00)
154.0(27.39)
130.8(44.65)
4000
33.8(2.68)
0.0(0.00)
184.3(29.79)
43.8(16.48)
107.3(4.69)
0.0(0.00)
424.2(65.06)
226.8(93.52)
6000
51.3(8.10)
0.0(0.00)
271.4(56.78)
89.3(41.78)
154.3(13.20)
0.0(0.00)
765.5(176.10)
357.0(107.62)
8000
62.0(6.72)
0.0(0.00)
463.4(75.03)
127.6(30.00)
192.3(18.45)
0.0(0.00)
1240.3(275.95)
583.7(217.76)
10,000
68.8(10.61)
0.0(0.00)
628.4(129.87)
152.3(67.85)
235.4(14.67)
0.0(0.00)
1574.2(280.58)
728.3(280.23)
The bold values highlight the best or better results
The runtime (in seconds) is plotted in Fig. 3, which shows the time required by GNN-NU to run \(10^5\) iterations on one graph coloring problem. It is reasonable that the runtimes increase with the numbers of nodes and edges increase, because the computational cost is mainly concentrated in the process of node aggregation and backpropagation. In general, the time complexity of GNN-1N is similar to PI-GNN [36], as no additional computation is added to the proposed algorithm.
Fig. 5
a–d The analysis parameter \(\lambda ^\prime \) ranging from 0.01 to 0.75 in Eq. (11) on queen6-6, queen8-12, 3-regular graph and 6-regular graph with 5000 nodes, where \(\lambda ^\prime = \frac{\lambda \cdot \mathcal {|E|}}{n\cdot \log K}\). e–h Convergence profiles of conflicts trained by Eq. (9), i.e., \(\lambda ^\prime =0\) and Eq. (11) with \(\lambda ^\prime =0.2\)
×
Fig. 6
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
×
Experiments on d-regular graph
In this subsection, the d-regular graph is used to conduct the experiment to show the effectiveness of the proposed method. The chromatic number of a d-regular graph is derivable due to the specific structure. According to the theory in [56], the chromatic number of a d-regular graph (\(d \ge 3\)) with n nodes \(\mathcal {X}(\mathcal {G}_{n,d})\) is \(k-1\) or k, where k is the smallest integer satisfying \(d<2(k-1)\log (k-1)\). Furthermore, the chromatic number is k, if \(d>(2k-3)\log (k-1)\). Therefore, we can get \(\mathcal {X}(\mathcal {G}_{n,3})=3\) and \(\mathcal {X}(\mathcal {G}_{n,6})=4\).
The results of the experiments are shown in Fig. 4, where every point is averaged over 10 independent runs, and the number of nodes ranges from \(10^2\) to \(10^4\). There is an early stopping mechanism applied within 100 iterations if the value of the loss function changes less than 0.001. The average time that PI-SAGE and GNN-NU takes is shown in Fig. 4a, c. PI-SAGE takes more time compared with GNN-NU, and the difference becomes more obvious when the number of nodes becomes larger. Regarding the average conflicts of 3-regular and 6-regular graphs (see in Fig. 4b, d), we observe that GNN-NU is highly competitive in finding the optimum, while PI-SAGE performs worse when the problem scale increases. The detailed results of Fig. 4 are shown in Table 2.
Parameter sensitivity analysis
In this subsection, an analysis of the hyperparameter\(\lambda \) in Eq. (11) is conducted. We found through experiments that the value of \(\lambda \) is influenced by the number of nodes, edges, and used colors in each graph. Therefore, we let \(\lambda ^\prime = \frac{\lambda \cdot \mathcal {|E|}}{n\cdot \log K}\), and further analyze \(\lambda ^\prime \).
The influence of the convergence curve under different values of \(\lambda ^\prime \) is shown in Fig. 5a–d obtained on queen6-6, queen8-12, 3-regular graph, and 6-regular graph with 5000 nodes, respectively. As we can see, the curves get closer to 0 when the value of \(\lambda ^\prime \) grows from 0.01 to 0.2, showing that the ability of the uniformity-based \(f_2\) (Eq. (10)) to escape local optima progressively improves. However, the conflicts become larger as \(\lambda ^\prime \) increases, i.e., \(\lambda ^\prime =0.75\). This is because the uniformity-based \(f_2\) (Eq. (10)) dominates the utility-based \(f_1\) (Eq. (9)), making all nodes share the same color. In fact, the utility-based function \(f_1\) should have the main influence when finding a no-conflict color assignment, while a proper value of \(\lambda \) with \(f_2\) contributes positively to finding the global optimum. Therefore, according to the results shown in Fig. 5, \(\lambda ^\prime =0.2\) is recommended to balance between \(f_1\) and \(f_2\).
In addition, we present conflict curves trained solely by \(f_1\) and those resulting from the combination of \(f_1\) and \(\lambda ^\prime f_2\) to show the effectiveness of \(f_2\) in Fig. 5e–h. Here, we set \(\lambda ^\prime =0.2\) as discussed above, and the rest hyperparameters are obtained directly from Ref. [36]. As we can see, all curves trained with \(f_2\) could remain in relatively smaller conflicts, while those trained without \(f_2\) tend to have more conflicts and fluctuate dramatically sometimes. Thus, the effectiveness of the uniformity-based \(f_2\) in Eq. (11) to avoid being stuck into the local optimum has been proven.
Application
In this section, we take a taxi scheduling problem as an example of a practical application of GCPs, showcasing the ability of GNN-NU 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 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, which aligns with the definition in Eq. (2).
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. 6a, 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 (shown in Fig. 6b). 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. 6b. After obtaining the graph description of the relationship between customers’ schedules, the generated graph is optimized by GNN-NU with a specific color number. The color number is the number of available taxis, which is four here. Figure 6c 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\}\).
Conclusion and future work
The GCP is an NP-hard problem and it is almost impossible to obtain a feasible solution within an acceptable period of time using exact solvers. Moreover, due to their graph property, GCPs cannot be easily and effectively solved by conventional neural networks. In this work, we propose an unsupervised graph neural network (GNN-NU) tailored for solving GCPs by combining negative message passing with normal message passing to handle heterophily. Besides, an objective function simultaneously considering the utility and uniformity is proposed for unsupervised learning. Experimental results on public datasets and d-regular graphs with up to \(10^4\) nodes show that GNN-NU outperforms five state-of-the-art peer algorithms. In addition, theoretical proof and parameter sensitivity analysis confirm the effectiveness of the proposed strategies. However, there is room for improvements for the proposed GNN-NU. For example, the hyperparameter \(\lambda \) in this paper is fixed. We expect that a self-adaption of the hyperparameter during training may lead to a more stabilized and faster convergence. In addition, the current method solves graph coloring problems from scratch, without leveraging knowledge from prior solving instances. Therefore, exploring ways in supervised learning to incorporate insights from previous instances may offer further improvements.
Solving graph-based homophilous problems with GNNs are still in its infancy. The following three improvements could be made to address the limitations of the proposed algorithm. 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, which is of great practical importance.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.