Deep Learning Chromatic and Clique Numbers of Graphs

Let $N\in\mathbb{N}.$ Denote the set of graphs of order $N$ by $X_{N}.$ When generating graphs of order $N$ we feel it is more natural for the DNN to also encounter graphs of all orders less than $N,$ so we actually generate graphs of various orders and embed them in $X_{N}.$ Let $n\in\{2,\dots,N\}.$

Let $K_{n}$ denote the complete graph of order $n.$ Note that $V(K_{n})=\{1,\dots,n\}$ and $|E(K_{n})|=n(n-1)/2.$ Let $j$ be a uniformly random number between $0$ and $n(n-1)/2.$ To generate a random graph of order $n$ we shuffle the set of edges $E(K_{n})$ and delete $j$ of the edges. Denote this graph by $G^{0}_{n}.$

Next append the vertices $\{n+1,\dots,N\}$ to $V(G^{0}_{n})$ and do not modify the edges $E(G^{0}_{n}).$ Denote this new graph by $G^{1}_{n}.$ Note that it contains $N-n$ vertices that are isolated. It is of order $N$ but we wish to embed it in a more random manner into $X_{N}.$ Note that each of the vertices $\{n+1,\dots,N\}$ of $G^{1}_{n}$ has no edges incident with it.

Choose a random permutation $\sigma:\{1,\dots,N\}\mapsto\{1,\dots,N\}$ and define $E_{n}=\sigma(E(G^{1}_{n})),$ where $\sigma(r,s)=\left(\sigma(r),\sigma(s)\right).$ Next define $G_{n}=(\{1,\dots,N\},E_{n}).$

Finally for a given $k\in\mathbb{N},$ and $n\in\{2,\dots,N\}$ we generate $k$ different graphs $G_{n}.$ This will generate a training set with $k(N-1)$ examples. The Python code to generate our data sets is available at github.com/mathprofessor/coloring1.

Let $G$ be a graph. To compute $\omega(G)$ we utilize the algorithm of Bron and Kerbosch [BK73]. More specifically we encode our graph using the Python library NetworkX [HSS08] which implements an updated version [BK73, TTT06, CK08].

Though computing maximal cliques and graph colorings are independent problems, we can utilize the maximal clique as a heuristic to speed up finding an optimal coloring using a SAT solver. Specifically we use the open source constraint programming solver Google OR-Tools: CP-SAT [PF19].

Let $G=(V,E)$ and let $V=\{1,\dots,N\}.$ For $v\in V$ let $x_{v}$ be the color of vertex $v,$ where $x_{v}$ is integer valued with values also in $\{1,\dots,N\}.$ Let $z$ be an integer valued variable, also with values in $\{1,\dots,N\}.$ Suppose $G_{c}=(V_{c},E_{c})$ is a maximal clique of $G.$

We consider the following constraint programming problem with objective:

1. 1.

   For each $v$ in $V_{c},$ arbitrarily assign to $x_{v}$ a unique color in $\{1,\dots,|V_{c}|\}.$

2. 2.

   For each edge $(i,j)\in E,$ we add the constraint $x_{i}\neq x_{j}.$

3. 3.

   For each vertex $i\in V,$ we have $x_{i}\leq z.$

4. 4.

   Finally we add an objective to minimize the variable $z.$

We summarize these steps in Algorithm 1. The Python code to implement the above algorithm can be found at github.com/mathprofessor/coloring1.

To measure and compare performance of the different models, the empirical study will use the mean absolute error (mae) and the percentage of records with an absolute error less than or equal to $l$, $P_{l}$ (typically, $l=0.5\mbox{ or }1$):

where $n$ is the number of records in the dataset and $y_{i}$ and $\hat{y}_{i}$ are the actual and predicted values of the dependent variable for record $i$. The absolute error for a single record $i$ is denoted as $\textsc{ae}(i)$.

Training for the linear regression model uses only the training dataset. Parameters for the deep neural network models are estimated using the training dataset, and the validation dataset is used to determine when to terminate the training process. The test set is only used to estimate the generalization performance. mae is the metric used to train the neural network models, and $P_{l}$ is computed post-training for evaluation purposes.

To set a simple baseline for performance, we built a regression model with the independent variable as the number of edges in the graph, and the dependent variable either $\chi(G)$ or $\omega(G$). The scatterplots for the test data are in Figure 2, along with the regression line.

Intuitively, there should be a positive correlation between the number of edges in a graph and both the chromatic number and maximum clique size. As can be seen from the scatterplot, for a fixed number of edges, there is a wide range of values for $\chi(G)$ and $\omega(G$).

Table 1 summarizes the performance metrics of the regression model on test data. The mean absolute error on test data for predicting the chromatic number is 2.31, while the mean absolute error for predicting the maximum clique size is 2.62. There is certainly opportunity for substantial improvement over this very simplistic and naive model.

The objective of this work is to determine if a deep neural network can be built to predict $\chi(G)$ and $\omega(G$) without performing domain-specific feature engineering, hence using only the adjacency matrix of a graph. Our initial attempt is to use a dense network created using the Sequential API in Keras. For each input graph, the adjacency matrix was flattened into a $50\times 50=2500$ input vector. We experimented with various hyperparameters, including the number of hidden layers and the number of hidden nodes per layer, activation function, learning rate and optimizer.

Generally speaking, lower values for the number of layers and number of hidden nodes per layer performed worse than higher values, while the choice of activation function, learning rate and optimizer did not substantially change the performance of the dense neural network. Therefore, our final dense model consisted of 13 hidden layers with 1000 nodes per layer, ReLU activation function, and Adam optimizer with the default learning rate. The final layer contains a single node with a linear activation function to produce a single output, either the chromatic number or maximum clique size. Note that all deep learning models were built in Tensorflow version 2.5 using the Keras API.

The results for this dense model are presented in Table 2. When predicting the chromatic number, the mae on the test dataset was 1.59, with $P_{0.5}=37.5\%$ and $P_{1}=60.7\%$. Results for maximum clique size are similar: mae of 1.81, with $P_{0.5}=35.1\%$ and $P_{1}=57.7\%$. Compared to the results in Table 1, this dense model presents significant lift over the regression model, as would be expected.

Convolutional Neural Networks (CNNs) are commonly used with images, which are often represented as a 2-dimensional tensor of pixel values (in the case of greyscale images). In our case, the adjacency matrix of a graph is also 2-dimensional, with entries of 1 in the $i^{th}$ row and $j^{th}$ column if the two vertices $i$ and $j$ are connected, and 0 otherwise. Given this representation of the graph, CNNs are a natural choice for the architecture of the neural network.

The input into the CNN is a tensor with dimensions $(50,50,1)$, representing the height (rows), width (columns), and number of channels. We experimented with a number of different architectures, varying the number of convolutional and maximum pooling layers, the number of filters and size of the convolution kernel, in addition to the number of dense layers and hidden nodes per layer.

Section 4.4.1 describes the Sequential CNN model that obtained solid performance on the test data, while Section 4.4.2 describes a more refined architecture that we refer to as a wide convolutional neural network.

The performance of the four different models - a baseline regression model, a Dense Sequential Neural Network and two different Convolutional Neural Networks - is summarized in Figure 7 and in Table 5.

Figure 7 shows the significant improvement in both metrics $P_{1}$ and $P_{0.5}$ towards the convolutional neural networks. Clearly the CNN architecture is detecting the relationships between nodes in the graph directly from the adjacency matrix in a way that is useful for predicting $\chi(G)$ and $\omega(G)$, showing substantial lift over a dense neural network.

Table 5 summarizes the mae values obtained on test data for each of the models. In addition, the column titled ‘% Impr.’ shows the percentage improvement in the mean absolute error versus the baseline (regression) model. For example, the Sequential CNN obtained an mae of 0.43, which is 81.4% lower than the mae of the regression model. As with the data shown in Figure 7, convolutional neural networks significantly outperform other approaches. Further, the wide CNN, which combines convolution filters with different kernel sizes and strides, is able to combine information in a way that allows it to outperform a more standard CNN.

To provide a more in-depth understanding of the performance of the wide CNN, Figure 8 shows the distribution of the absolute error for predicting $\chi(G)$ on the test data. To improve readability, records in the test data were first divided into groups by the value of $\chi(G)$ (e.g., $\chi(G)\in(0,2]$). A boxplot showing the distribution of absolute error for each group of records is then plotted.

Each box shows three quartile values (e.g., $25^{th}$ percentile, median, and $75^{th}$ percentile) with whiskers that extend to 1.5 times the interquartile range (IQR). As expected, the distribution of errors increases as the chromatic number increases, however performance of the model is very good regardless of the chromatic number.

To further analyze performance, an additional metric, the absolute percentage error (ape), is considered. ape divides the absolute error by the actual target value, and is typically expressed as a percentage:

Similar to mae, the mape is the mean absolute percentage error over all $n$ records in the test data:

Absolute percentage error is useful for counteracting the phenomenon observed in Figure 8, namely that as the value for the target variable increases, the observed absolute errors also tend to increase, but relative to the value of the target variable, the increases in error are not as meaningful. For example, if $y_{i}=30$ and $\hat{y}_{i}=32$, $\textsc{ae}(i)=2$ but $\textsc{ape}(i)=6.7\%$. Compare this to a situation where $y_{j}=2$ and $\hat{y}_{j}=4$. Records $i$ and $j$ have the same absolute error ($\textsc{ae}(i)=\textsc{ae}(j)=2$), however the absolute percentage error for $j$ is $100\%$, compared to $6.7\%$ for $i$. We note that there are many additional performance metrics proposed in the literature (e.g., weighted mape, symmetric mape), however a full consideration of these metrics does not have a significant impact on this work.

Table 6 shows the mape for both CNN models on the test data. All models achieve a mape significantly less than 10, which we would characterize as strong performance. Furthermore, Figure 9 shows the distribution of ape obtained by the wide CNN across different ranges of $\chi(G)$, similar to Figure 8. As you can see from Figure 9, the IQR is relatively stable across groups, but as expected, there is a higher level of skew in ape when $\chi(G)$ is small (i.e., when dividing by a small actual value, small absolute errors can become large percentage errors).