A graph $G$ is said to be $k$-critical if $G$ is $k$-colorable and $G-e$ is not $k$-colorable for every edge
$e$ of $G$. In this paper, we present some new methods from two or more small 4-critical graphs to  construct a larger 4-critical planar graphs.

§ INTRODUCTION

Let $G=(V,E)$ be a graph, $G$ is said to be $k$-colorable if there is a assignment of $k$ colors to the vertices of $G$ such that no two adjacent vertices of $G$ get the same color.  The chromatic number of $G$, denoted by $\chi(G)$, is the least integer $k$ such that $G$ is $k$-colorable.
A graph $G$ is said to be $k$-critical if $G$ is $k$-colorable and $G-e$ is not $k$-colorable for every edge
$e$ of $G$. A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
About 1950 G. A. Dirac introduced the concept of criticality as a methodological means in the theory of graph colouring. He himself, G. Hajbs and T. Gallai were the first to develop special constructions for creating colour-critical graphs and establishing theorems on their properties.
The basic tool to be used to construct critical graphs is Hajós’ construction [4, 6]: Let $G_1$ and $G_2$ be two disjoint graphs with
edges $x_1y_1$ and $x_2y_2$, let $G$ be a new graphs obtained from $G_1$ and $G_2$ by removing $x_1y_1$ and $x_2y_2$, identifying $x_1$ and $x_2$, and joining $y_1$ and $y_2$
by a new edge. It is well known that if $G_1$ and $G_2$ are $k$-critical graphs, so is $G$.

There is a survey on methods of constructing critical graphs, see [9]. As for 4-critical planar graphs,
there are only a few methods which are known to constructing 4-critical planar graphs
(see [1, 2, 3, 5, 7, 8] etc). In this paper, we present some new methods
for constructing 4-critical planar graphs, given two or more 4-critical planar graphs.

§ MAIN RESULTS

Some new methods for constructing 4-critical planar graphs

Let $G_1, G_2, G_3$ be three planar graphs. Suppose that $u_1u_2u_3$, $v_1v_2v_3$ and $w_1w_2w_3$ are three paths each lie in the boundary of some face of $G_1$, $G_2$ and $G_3$ respectively.  Let $G=G_1\circ G_2\circ G_3$ be a graph (see Figure <ref>) obtained by

(a) Deleting the edges $u_2u_3$, $v_2v_3$ and $w_2w_3$;

(b) Identifying  $u_1$ with $w_3$, $u_3$ with $v_1$ and $v_1$ with $w_1$;

(c) Adding a new vertex $z$, and adding three new edges $zu_2$, $zv_2$, $zw_2$.

[x=0.57, y=3.48,Lpos=80]$w_3$
[x=0.43, y=3.48,Lpos=100]$u_1$
[x=-.25, y=2.3]$u_2$
[x=-0.93, y=1.12,Lpos=180]$u_3$
[x=-0.86, y=1,Lpos=-90]$v_1$
[x=.5, y=1,Lpos=90]$v_2$
[x=1.86, y=1,Lpos=-88]$v_3$
[x=1.93, y=1.12]$w_1$
[x=1.25, y=2.3,Lpos=180]$w_2$

(0.57,3.48) .. controls (2.99,3.31) .. (1.93,1.12);
(0.43,3.48) .. controls (-1.97,3.31) .. (-0.93,1.12);
(-0.86,1) .. controls (0.5,-0.76) .. (1.86,1);
(-1.11,2.8) node$G_1$;
(0.5,0.12) node$G_2$;
(2.12,2.8) node$G_3$;

[x=0.5, y=3.6,Lpos=90,Math,L=u_1]u_1
[x=-1, y=1,Lpos=180,Math]v_1
[x=2, y=1,Math]w_1
[x=.5, y=1,Lpos=135,Math]v_2
[x=1.25, y=2.3,Lpos=180,Math]w_2
[x=-.25, y=2.3,Math]u_2
[x=.5, y=1.87,Math]z
(u_1) .. controls (2.99,3.31) .. (w_1);
(u_1) .. controls (-1.97,3.31) .. (v_1);
(v_1) .. controls (0.5,-0.76) .. (w_1);
(-1.11,2.8) node$G_1$;
(0.5,0.12) node$G_2$;
(2.12,2.8) node$G_3$;

[dash pattern=on 3pt off 3pt] (u_1)– (w_2);
[dash pattern=on 3pt off 3pt] (w_1)– (v_2);
[dash pattern=on 3pt off 3pt] (v_1)– (u_2);

$G=G_1\circ G_2\circ G_{3}$

[x=8.02, y=4.18,Lpos=90,Math,L=u_1]u_1
[x=5, y=2,Lpos=180,Math]v_1
[x=6.51, y=3.09,Lpos=0,Math]u_2
[x=6.14, y=-1.54,Lpos=-90,Math]w_1
[x=9.86, y=-1.55,Lpos=-45,,Ldist=-3pt,Math]x_1
[x=11.04, y=1.97,Math]y_1
[x=5.57, y=0.23,Lpos=87.5,Ldist=-1pt,Math]v_2
[x=8, y=-1.55,Lpos=45,Ldist=-3pt,Math]w_2
[x=10.45, y=0.21,Lpos=95,Math]x_2
[x=9.52, y=3.08,Lpos=-90,Math]y_2
[x=8.01, y=1.01,Ldist=-1pt,Lpos=90,Math]z
[dash pattern=on 3pt off 3pt] (u_1)– (u_2);
[dash pattern=on 3pt off 3pt] (v_1)– (v_2);
[dash pattern=on 3pt off 3pt] (w_1)– (w_2);
[dash pattern=on 3pt off 3pt] (x_1)– (x_2);
[dash pattern=on 3pt off 3pt] (y_1)– (y_2);
(u_1) .. controls (11,5) .. (y_1);
(u_1) .. controls (5,5) .. (v_1);
(v_1) .. controls (3,-1) .. (w_1);
(w_1) .. controls (8,-4) .. (x_1);
(x_1) .. controls (13,-1) .. (y_1);
(6,4) node$G_1$;
(4.44,-0.36) node$G_2$;
(8,-3) node$G_3$;
(11.84,-0.32) node$G_4$;
(10,4) node$G_5$;

The graph $G=G_1\circ G_2\circ G_{3}\circ G_4\circ G_5$

If $G_1=G_2=G_3=K_4$, the new graph $G=G_1\circ G_2\circ G_3$ is shown in Figure <ref>. It is a 4-critical planar graph.

The graph $G=K_4\circ K_4\circ K_4$

If $G_1=G_2=G_3=G_4=G_5=K_4$, the new graph $G=G_1\circ G_2\circ G_3\circ G_4\circ G_5$ is shown in Figure <ref>. It is a 4-critical planar graph.

The graph $G=K_4\circ K_4\circ K_4\circ K_4\circ K_4$

If $G_1$, $G_2$ and $G_3$ are 4-critical planar graphs, then $G=G_1\circ G_2\circ G_3$ is a 4-critical graph.

Proof. (i) It is clear that $G$ is still a planar graph, by the Four Color Theorem, we have $\chi (G)\le 4$. We next show that $\chi (G)\ge 4$.

If $G$ can be colored with 3 colors,  let $c$ be a 3-coloring of $G$. Since $G_1$ is 4-critical, $G_1-w_2w_3$ can be colored with 3 colors. In such a
coloring, $w_3$ and $w_2$ must be colored with the same color (otherwise this would be a 3-coloring of $G_1$
as well). This implies that $c(u_1)=c(w_2)$. Similarly, we have that $c(w_1)=c(v_2)$ and $c(v_1)=c(u_2)$.
Note that $z$ is adjacent to each vertex of $\{u_2,v_2,w_2\}$, at least two vertices of them have the same color,
without loss of generality, we assume that $c(u_2)=c(v_2)$,
then $c(v_1)=c(v_2)$ since $c(u_2)=c(v_1)$, this is impossible since $v_1$ and $v_2$ are adjacent in $G$.
Therefore, we have $\chi (G)= 4$.

(ii) We show that $\chi (G-e)\le 3$ for every edge in $G$. Let $H_1,H_2$ and $H_3$ be the subgraph of $G$ induced by $V(G_1), V(G_2)$ and $V(G_3)$ respectively. It is clear that $H_1=G_1-u_2u_3, H_2=G_2-v_2v_3$ and $H_3=G_3-w_2w_3$ respectively. Consider the following three cases:

Case 1. $e\in\{zu_2,zv_2,zw_2\}$.

Since $G_1$ is 4-critical, there is a three coloring $c_1$ of $G_1-{u_2u_3}$ such that $u_2$ and $u_3$ get the same
color. Without loss of generality, assume that $c_1(u_2)=c_1(u_3)=1$ and $c_1(u_1)=2$. Also, since $G_2$ is 4-critical,
there is a three coloring $c_2$ of $G_2-{v_2v_3}$ such that $c_1(v_1)=1$ and $c_2(v_2)=c_1(v_3)=3$. (if $c_2(v_2)=c_2(v_3)=2$, we can swap the colors of 2 and 3 in $G_2$). Similarly, since $G_3$ is 4-critical,
there is a three coloring $c_3$ of $G_3-{w_2w_3}$ such that $c_3(w_1)=3$ and $c_3(w_2)=c_3(w_3)=2$. As $u_1=w_3$, $v_1=u_3$ and $w_1=v_3$, we see that $c_1,c_2,c_3$ form a 3-coloring of $G-z$, this coloring can
obviously be extended to a 3-coloring of $G-e$.

Case 2. $e\in E(G)/\{zu_2,zv_2,zw_2,u_1u_2,v_1v_2,w_1w_2\}$.

Without loss of generality, assume that $e\in E(G_1)-u_1u_2$.  Since $G_1$ is 4-critical, there is a 3-coloring  of $G_1-e$. This coloring induces a 3-coloring $c_1$ of $H_1-e$. Without loss of generality, we assume that $c_1(v_1)=1$ and $c_1(u_2)=2$.

If $c_1(u_1)=3$, then since there is a 3-coloring $c_3$ of $H_3$ such that $c_3(u_1)=c_3(w_2)=3$ and $c_3(w_1)=2$. Similarly, there is a 3-coloring $c_2$ of $H_2$ such that $c_2(w_1)=c_2(v_2)=2$ and $c_2(v_1)=1$. Therefore, $c_1,c_2,c_3$ induce a 3-coloring of $G-z$. This coloring can be extended to a 3-coloring of $G-e$, since there are two
colors used in the neighbors of $z$.

If $c_1(u_1)=3$, by a similar argument as above, we can show that $G-e$ is 3-colorable.

Case 3. $e\in\{u_1u_2,v_1v_2,w_1w_2\}$.

Without loss of generality, assume that $e=u_1u_2$. Since $G_1$ is 4-critical, there is a 3-coloring of $G_1-e$ such that $u_1$ and $u_2$ have the same color. This coloring induces a 3-coloring $c_1$ of $H_1-e$. Assume, without loss of generality, $c_1(u_1)=c_1(u_2)=1$ and $c_1(v_1)=2$. Since $G_3$ is 4-critical, there is a 3-coloring $c_3$ of $H_3$ such that $c_3(u_1)=c_3(w_2)=1$ and $c_3(w_1)=3$. Similarly, there is a 3-coloring $c_2$ of $H_2$ such that $c_2(w_1)=c_2(v_2)=3$ and $c_2(v_1)=2$. Therefore, $c_1,c_2,c_3$ induce a 3-coloring of $G-z$. This coloring can be extended to a 3-coloring of $G-e$, since there are two colors used in the neighbors of $z$. $\Box$

Let $G_1, G_2,\cdots G_{2k+1}$ be three planar graphs. Suppose that $u^1_1u^1_2u^1_3$,
$u^2_1u^2_2u^2_3$, $\cdots$,
$u^{2k+1}_1u^{2k+1}_2u^{2k+1}_3$  are $(2k+1)$ paths each lie in the boundary of some face of $G_1$, $G_2$ and $G_{2k+1}$ respectively.  Let $G=G_1\circ G_2\circ\cdots\circ G_{2k+1}$ be a graph (if $k=2$, see Figure <ref>) obtained by

(a) Deleting the edges $u^1_2u^1_3$, $u^2_2u^2_3$,$\cdots$, $u^{2k+1}_2u^{2k+1}_3$;

(b) Identifying  $u^1_1$ with $u^{2k+1}_3$, $u^1_3$ with $u^2_1$ and $u^2_3$ with $u^3_1$, $\cdots$,$u^{2k}_3$ with $u^{2k+1}_1$;

(c) Adding a new vertex $z$, and adding $2k+1$ new edges $zu^1_2$, $zu^2_2$, $\cdots$, $zu^{2k+1}_2$.

If $G_1$, $G_2$ and $G_{2k+1}$ are 4-critical planar graphs, then $G=G_1\circ G_2\circ\cdots\circ G_{2k+1}$ is a 4-critical planar graph.

Proof. (i) It is clear that $G$ is still a planar graph, by the Four Color Theorem, we have $\chi (G)\le 4$. We next show that $\chi (G)\ge 4$.

Since each $G_i$ is 4-critical, $G_i-u^i_2u^i_3$ ($1\le i\le 2k+1$) is 3-colorable and $c(u^i_2)=c(u^i_3)$ for any 3-coloring of $G_i-u^i_2u^i_3$. If $G$ is 3-colorable, without loss of generality, let $c$ be a 3-coloring of $G_i-u^i_2u^i_3$.
Denote by $H$ the subgraph of $G$ induced by the vertex set $\{z,u^1_1,u^1_2,u^1_3,u^2_2,u^2_3,\cdots,u^{2k}_{2},u^{2k}_3,u^{2k+1}_2\}$. Then $H$ is 3-colorable, but this is impossible since $c(u^i_2)=c(u^i_3)$ ($1\le i\le 2k+1$).

(ii) We show that $\chi (G-e)\le 3$ for every edge in $G$. Let $H_1,H_2$,$\cdots$, $H_{2k+1}$ be the subgraph of $G$ induced by $V(G_1), V(G_2)$,$\cdots$, $V(G_{2k+1})$ respectively. It is clear that $H_i=G_i-u^i_2u^i_3$ ($1\le i\le 2k+1$). Consider the following three cases:

Case 1. $e\in\{zu^1_2,zu^2_2,\cdots,zu^{2k+1}_2\}$.

Without loss of generality, assume that $e=zu^1_2$.
Since $G_1$ is 4-critical, there is a three coloring $c_1$ of $G_1-{u^1_2u^1_3}$ such that $c_1(u^1_2)=c_1(u^1_3)=1$ and $c_1(u^1_1)=3$. Also, since $G_2$ is 4-critical,
there is a three coloring $c_2$ of $G_2-{u^2_2u^2_3}$ such that $c_2(u^1_3)=1$ and $c_2(u^2_2)=c_2(u^2_3)=2$.
In general, if $i\ge 3$ is odd, since $G_i$ is 4-critical,
there is a three coloring $c_i$ of $G_i-{u^i_2u^i_3}$ such that $c_i(u^{i-1}_3)=2$ and $c_i(u^i_2)=c_i(u^i_3)=3$;
if $i\ge 3$ is even, since $G_i$ is 4-critical,
there is a three coloring $c_i$ of $G_i-{u^i_2u^i_3}$ such that $c_i(u^{i-1}_3)=3$ and $c_i(u^i_2)=c_i(u^i_3)=2$;
Finally, we color $z$ with color 1. We see that $c_1,c_2,\cdots,c_{2k+1}$ together with the color of $z$ extends  a 3-coloring of $G-e$.

Case 2. $e\in E(H_i)$, for ($1\le i\le 2k+1$).

Without loss of generality, assume that $e\in E(H_1)$.

Suppose first that $e=u^1_1u^1_2$. Since $G_1$ is 4-critical, there is a 3-coloring of $G_1-e$ such that $u^1_1$ and $u^1_2$ have the same color. This coloring induces a 3-coloring $c_1$ of $H_1-e$. Assume, without loss of generality, $c_1(u^1_1)=c_1(u^1_2)=1$ and $c_1(u^1_3)=3$. Since $G_2$ is 4-critical, there is a three coloring $c_i$ of $G_2-{u^2_2u^2_3}$ such that $c_2(u^{1}_3)=3$ and $c_2(u^2_2)=c_2(u^2_3)=2$; In general, if $i\ge 3$ is odd, since $G_i$ is 4-critical,
there is a three coloring $c_i$ of $G_i-{u^i_2u^i_3}$ such that $c_i(u^{i-1}_3)=2$ and $c_i(u^i_2)=c_i(u^i_3)=1$;
if $i\ge 3$ is even, since $G_i$ is 4-critical,
there is a three coloring $c_i$ of $G_i-{u^i_2u^i_3}$ such that $c_i(u^{i-1}_3)=1$ and $c_i(u^i_2)=c_i(u^i_3)=2$;
Finally, we color $z$ with color 3. We see that $c_1,c_2,\cdots,c_{2k+1}$ together with the color of $z$ extends  a 3-coloring of $G-e$.

Suppose now that $e\in H_1-u^1_1u^1_2$.

Since $G_1$ is 4-critical, there is a 3-coloring  of $G_1-e$. This coloring induces a 3-coloring $c_1$ of $H_1-e$.
Assume without loss of generality, let $c_1(u^1_1)=2$, $c_1(u^1_2)=1$ and $c_1(u^1_3)=k$, where $k\in\{2,3\}$.

since $G_2$ is 4-critical,
there is a three coloring $c_2$ of $G_2-{u^2_2u^2_3}$ such that $c_2(u^1_3)=k$ and $c_2(u^2_2)=c_2(u^2_3)=1$;

If $i\ge 3$ is odd, since $G_i$ is 4-critical,
there is a three coloring $c_i$ of $G_i-{u^i_2u^i_3}$ such that $c_i(u^{i-1}_3)=1$ and $c_i(u^i_2)=c_i(u^i_3)=2$;
if $i\ge 3$ is even, since $G_i$ is 4-critical,
there is a three coloring $c_i$ of $G_i-{u^i_2u^i_3}$ such that $c_i(u^{i-1}_3)=2$ and $c_i(u^i_2)=c_i(u^i_3)=1$;
Finally, we color $z$ with color 3. We see that $c_1,c_2,\cdots,c_{2k+1}$ together with the color of $z$ extends  a 3-coloring of $G-e$. $\Box$

[x=1, y=5,Lpos=90,Math,L=u_1]A
[x=-1.85, y=0.01,Lpos=180,Math,L=u_3]B
[x=3.87, y=0.01,Lpos=0,Math,L=v_3]C
[x=-0.43, y=2.5,Lpos=0,Math,L=u_2]D
[x=2.44, y=2.5,Lpos=180,Math,L=v_2]E

VertexStyle/.append  style=fill=white
[x=1, y=1.68,Lpos=-90,Math,L=z]H
EdgeStyle/.style = -,bend left=80,color=gray
EdgeStyle/.style = -,bend right=80,color=gray
[dash pattern=on 3pt off 3pt] (E)– (C);
[dash pattern=on 3pt off 3pt] (B)– (D);
(3.5,2.5) node$G_2$;
(-1.5,2.5) node$G_1$;

The graph $G=g_3(G_1,G_2)$

Let $G_1, G_2$ be two planar graphs. Suppose that $u_1u_2u_3$ and $v_1v_2v_3$ are two paths each lie in the boundary of some face of $G_1$, $G_2$ respectively.  Let $G=g_3(G_1, G_2)$ be a graph (see Figure <ref>) obtained from $G_1$ and $G_2$ by

(a) Deleting the edges $u_2u_3$ and $v_2v_3$;

(b) Identifying  $u_1$ with $v_1$;

(c) Adding a new vertex $z$, and adding three new edges $zu_1$, $zu_2$, $zv_2$;

(d) Adding a new edge $u_3v_3$.

If $G_1=G_2=K_4$, for example, $G=g_3(K_4,K_4)$, see Figure <ref>, it is a 4-critical planar graph.

The graph $G=g_3(K_4, K_4)$

If $G_1$, $G_2$ and $G_{2k+1}$ are 4-critical planar graphs, then $G=g_3(G_1, G_2)$ is a 4-critical planar graph.

Proof. (i) It is clear that $G$ is still a planar graph, by the Four Color Theorem, we have $\chi (G)\le 4$. We next show that $\chi (G)\ge 4$.

If $G$ is 3-colorable, then
since $G_1$ and $G_2$ are 4-critical, $G_1-u_2u_3$ and $G-v_2v_3$ are 3-colorable and $c(u_2)=c(u_3)$ and  $c(v_2)=c(v_3)$ for any 3-coloring $c$ of $G$.  Note that $u_3$ and $v_3$ are adjacent, without loss of generality, let $c(u_1)=1$, $c(u_2)=c(u_3)=2$ and $c(v_2)=c(v_3)=3$. This is impossible since we can not color $z$ with color 1,2 or 3.

(ii) We show that $\chi (G-e)\le 3$ for every edge in $G$. Let $H_1,H_2$  be the subgraph of $G$ induced by $V(G_1), V(G_2)$  respectively. It is clear that $H_1=G_1-u_2u_3, H_2=G_2-v_2v_3$. Consider the following  cases:

Case 1. $e\not\in (E(H_1)\cup E(H_2))$.

If $e=u_3v_3$, let $c_1$ and $c_2$ be the two 3-colorings of $H_1$ and $H_2$ respectively. Since $c_1(u_2)=c_1(u_3)$ and $c_2(v_2)=c_2(v_3)$, without loss of generality, let $c_1(u_1)=c_2(u_1)=1$, $c_1(u_2)=c_1(u_3)=2$ and $c_2(v_2)=c_2(v_3)=2$, then we can color $z$ with color 3. Therefore, $c_1,c_2$
together with the color of $z$ extend to a 3-coloring of $G$.

If $e=zu_1$, let $c_1$ and $c_2$ be the two 3-colorings of $H_1$ and $H_2$ respectively. Since $c_1(u_2)=c_1(u_3)$ and $c_2(v_2)=c_2(v_3)$, without loss of generality, let $c_1(u_1)=c_2(u_1)=1$, $c_1(u_2)=c_1(u_3)=2$ and $c_2(v_2)=c_2(v_3)=3$, then we can color $z$ with color 1. Therefore, $c_1,c_2$
together with the color of $z$ extend to a 3-coloring of $G$.

If $e=zu_2$ or $e=zv_2$, without loss of generality, assume that $e=zu_2$. Let $c_1$ and $c_2$ be the two 3-colorings of $H_1$ and $H_2$ respectively. Since $c_1(u_2)=c_1(u_3)$ and $c_2(v_2)=c_2(v_3)$, without loss of generality, let $c_1(u_1)=c_2(u_1)=1$, $c_1(u_2)=c_1(u_3)=2$ and $c_2(v_2)=c_2(v_3)=3$, then we can color $z$ with color 2. Therefore, $c_1,c_2$ together with the color of $z$ extend to a 3-coloring of $G$.

Case 2. $e\in (E(H_1)\cup E(H_2))$.

Without loss of generality, assume that $e\in E(H_1)$.

If $e=u_1u_2$, let $c_2$ be the  3-colorings  $H_2$. Since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-u_1u_2$ such that $c_1(u_1)=c_1(u_2)$. Without loss of generality, let $c_1(u_1)=c_1(u_2)=c_2(u_1)=1$, $c_1(u_3)=2$ and $c_2(v_2)=c_2(v_3)=3$, then we can color $z$ with color 2. Therefore, $c_1,c_2$ together with the color of $z$ extend to a 3-coloring of $G$.

If $e\not=u_1u_2$, let $c_2$ be the  3-colorings  $H_2$. Since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-e$. This implies that $c_1(u_2)\ne c_1(u_3)$. Without loss of generality, let $c_1(u_1)=c_2(u_1)=1$, $c_1(u_3)=k$ ($k\in\{1,3\}$) and $c_2(v_2)=c_2(v_3)=2$, then we can color $z$ with color 3. Therefore, $c_1,c_2$ together with the color of $z$ extend to a 3-coloring of $G$. $\Box$

Let $G_1, G_2$ be two planar graphs. Suppose that $u_1u_2u_3$ and $v_1v_2v_3$ are two paths each lie in the boundary of some face of $G_1$, $G_2$ respectively.  Let $G=g_4(G_1, G_2)$ be a graph (see Figure <ref>) obtained from $G_1$ and $G_2$ by

(a) Deleting the edges $u_1u_2$ and $v_1v_2$;

(b) Adding four new edges $u_1v_1$, $u_2v_3$, $u_3v_2$ and $u_3v_3$

[x=1, y=4,Lpos=90,Ldist=-3pt,Math,L=u_1]A
[x=1, y=3,Lpos=0,Ldist=-1pt,Math,L=u_2]B
[x=1, y=2,Lpos=-90,Ldist=-3pt,Math,L=u_3]C
[x=2, y=4,Lpos=90,Ldist=-3pt,Math,L=v_1]D
[x=2, y=3,Lpos=180,Ldist=-1pt,Math,L=v_2]E
[x=2, y=2,Lpos=-90,Ldist=-3pt,Math,L=v_3]F

EdgeStyle/.style = -,bend right=90,color=gray
EdgeStyle/.style = -,bend left=90,color=gray
[dash pattern=on 3pt off 3pt] (A)– (B);
[dash pattern=on 3pt off 3pt] (D)– (E);
(2.4,3) node$G_2$;
(0.6,3) node$G_1$;

[x=1, y=4,Lpos=90,Ldist=-3pt,Math,L=u_1]A
[x=1, y=3,Lpos=-15,Ldist=-3pt,Math,L=u_2]B
[x=1, y=2,Lpos=-90,Ldist=-3pt,Math,L=u_3]C
[x=2, y=4,Lpos=90,Ldist=-3pt,Math,L=v_1]D
[x=2, y=2,Lpos=-90,Ldist=-3pt,Math,L=v_2]E
[x=1.5, y=3,Lpos=160,Ldist=-3pt,Math,L=v_3]F

EdgeStyle/.style = -,bend right=90,color=gray
EdgeStyle/.style = -,bend right=30,color=gray
[dash pattern=on 3pt off 3pt] (A)– (B);
[dash pattern=on 3pt off 3pt] (D)– (E);
(1.85,3) node$G_2$;
(0.6,3) node$G_1$;

The graph $G=g_4(G_1,G_2)$

If $G_1=K_4$ and $G_2=W_5$, the graph $G=g_4(K_4, W_5)$ is illustrated in Figure <ref>. It is a 4-critical planar graph. Note that the graph in Figure <ref> (b) is a redrawing of (a).

The graph $G=g_4(K_4, W_5)$

If $G_1$, $G_2$ and $G_{2k+1}$ are 4-critical planar graphs, then $G=g_4(G_1, G_2)$ is also a 4-critical planar graph.

Proof. It is clear that $G=g_4(G_1, G_2)$ is planar, see Figure <ref>(b). Note that the graphs shown in Figure <ref>(a) and (b) are isomorphic, but their drawings are different.

(i) We first show that $\chi (G)\ge 4$. Suppose on the contrary that $G$ is 3-colorable, then
since $G_1$ and $G_2$ are 4-critical, $G_1-u_1u_2$ and $G-v_1v_2$ are 3-colorable and $c(u_1)=c(u_2)$,$c(v_1)=c(v_2)=2$.  Without loss of generality, assume $c(u_1)=c(u_2)=1$ and $c(u_2)=c(u_3)=2$. Then $u_3$ and $v_3$ must be colored with color 3, this is impossible since $u_3$ and $v_3$ are adjacent. Therefore, we have $\chi (G)\ge 4$.

(ii) We show that $\chi (G-e)\le 3$ for every edge in $G$. Consider the following  cases:

Case 1. $e\in \{u_1v_1,u_3v_3, u_2v_3, u_3v_2\}$.

If $e=u_1v_1$, since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-u_1u_2$ such that $c_1(u_1)=c_1(u_2)=1$ and $c_1(u_3)=2$. Moreover, since $G_2$ is 4-critical, there is a 3-coloring $c_2$ of $G_2-v_1v_2$ such that $c_2(v_1)=c_2(v_2)=1$ and $c_2(v_3)=3$. It is clear that $c_1$ and $c_2$ extend to a 3-coloring of $G$.

If $e=u_3v_3$, since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-u_1u_2$ such that $c_1(u_1)=c_1(u_2)=1$ and $c_1(u_3)=2$. Moreover, since $G_2$ is 4-critical, there is a 3-coloring $c_2$ of $G_2-v_1v_2$ such that $c_2(v_1)=c_2(v_2)=1$ and $c_2(v_3)=2$. It is clear that $c_1$ and $c_2$ extend to a 3-coloring of $G$.

If $e=u_2v_3$ or $e=u_3v_2$, assume without loss of generality, that $e=u_2v_3$. Since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-u_1u_2$ such that $c_1(u_1)=c_1(u_2)=1$ and $c_1(u_3)=2$. Moreover, since $G_2$ is 4-critical, there is a 3-coloring $c_2$ of $G_2-v_1v_2$ such that $c_2(v_1)=c_2(v_2)=3$ and $c_2(v_3)=1$. It is clear that $c_1$ and $c_2$ extend to a 3-coloring of $G$.

Case 2. $e\in E(G_1-u_1u_2)$ or $e\in E(G_2-v_1v_2)$.

Without loss of generality, assume that $e\in E(G_1-u_1u_2)$.

If $e=u_2u_3$, since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-e$ such that $c_1(u_2)=c_1(u_3)=1$ and $c_1(u_1)=2$. Moreover, since $G_2$ is 4-critical, there is a 3-coloring $c_2$ of $G_2-v_1v_2$ such that $c_2(v_1)=c_2(v_2)=1$ and $c_2(v_3)=2$. It is clear that $c_1$ and $c_2$ extend to a 3-coloring of $G$.

If $e\ne u_2u_3$, since $G_1$ is 4-critical, there is a 3-coloring $c_1$ of $G_1-e$ such that $c_1(u_1)=1$,$c_1(u_2)=2$ and $c_1(u_3)=k$ (where $k\in\{1,3\}$). Moreover, since $G_2$ is 4-critical, there is a 3-coloring $c_2$ of $G_2-v_1v_2$ such that $c_2(v_1)=c_2(v_2)=1$ and $c_2(v_3)=2$. It is straightforward to verify that $c_1$ and $c_2$ extend to a 3-coloring of $G$. $\Box$

This research work is supported by National Natural Science Foundation of China under grant No. 11571168 and 11371193.

[1] H. L. Abbott, D. R. Hare and B. Zhou, Large faces in 4-critical planar graphs with minimum degree 4,
Combinatorica 15 (4) (1995), 455-467.

[2] H. L. Abbott and B. Zhou, The edge-density of 4-critical planar graphs, Combinatorica 11 (3) (1991), 185-189.

[3]O. V. Borodin, Z. Dvořákc, A. V. Kostochkad, B. Lidický, M. Yancey, Planar 4-critical graphs with four triangles, European Journal of Combinatorics 41 (2014) 138-151.

[4]
G. Hajós, Über eine Konstruktion nicht $n$-färbbarer Graphen. Wiss. Z. Martin-Luther-Univ.Halle-Wittenberg, Math.-Naturw. Reihe 10, 116-117, 1961.

[5] B. Grünbaum, The edge-density of 4-critical planar graphs, Combinatorica 8 (1) (1988), 137-139.

[6]T. R. Jensen and B.Toft. Graph Coloring Problems. Wiley, New York, 1995.

[7]G. Koester, 4-critical 4-valent planar graphs constructed with crowns,
Math. Scand. 67 (1990), 15-22.

[8]G. Koester, On 4-critical planar graphs with high edge
density, Discrete Mathematics 98 (1991), 147-151.

[9]H. Sachs and M. Stiebitz, On constructive methods in the theory of color-critical graphs, Discrete Mathematics 74 (1989), 201-226.


# Parallel Graph Coloring Algorithms for Distributed GPU Environments

Ian Bogle and George M. Slota  Department of Computer Science  Rensselaer
Polytechnic Institute  Lally 317, 110 8th St  Troy, NY 12180
<EMAIL_ADDRESS>Erik G. Boman, Karen D. Devine, and Sivasankaran
Rajamanickam  Scalable Algorithms Department  Sandia National Laboratories,
New Mexico<EMAIL_ADDRESS>
###### Abstract

Graph coloring is often used in parallelizing scientific computations that run
in distributed and multi-GPU environments; it identifies sets of independent
data that can be updated in parallel. Many algorithms exist for graph coloring
on a single GPU or in distributed memory, but to the best of our knowledge,
hybrid MPI+GPU algorithms have been unexplored until this work. We present
several MPI+GPU coloring approaches based on the distributed coloring
algorithms of Gebremedhin et al. and the shared-memory algorithms of Deveci et
al. The on-node parallel coloring uses implementations in KokkosKernels, which
provide parallelization for both multicore CPUs and GPUs. We further extend
our approaches to compute distance-2 and partial distance-2 colorings, giving
the first known distributed, multi-GPU algorithm for these problems. In
addition, we propose a novel heuristic to reduce communication for recoloring
in distributed graph coloring. Our experiments show that our approaches
operate efficiently on inputs too large to fit on a single GPU and scale up to
graphs with 76.7 billion edges running on 128 GPUs.

###### keywords:

graph coloring; distributed algorithms; GPU; combinatorial scientific
computing

††journal: Parallel Computing

##  1 Introduction

We present new multi-GPU, distributed memory implementations of distance-1,
distance-2, and partial distance-2 graph coloring. _Distance-1 graph coloring_
assigns _colors_ (i.e., labels) to all vertices in a graph such that no two
neighboring vertices have the same color. Similarly, _distance-2 coloring_
assigns colors such that no vertices within _two hops_ , also called a “two-
hop neighborhood,” have the same color. _Partial distance-2 coloring_ is a
special case of distance-2 coloring, in which only one set of a bipartite
graph’s vertices are colored. Usually, these problems are formulated as NP-
hard optimization problems, where the number of colors used to fully color a
graph is minimized. Serial heuristic algorithms have traditionally been used
to solve these problems, one of the most notable being the DSatur algorithm of
Brélaz [1]. More recently, parallel algorithms [2, 3] have been proposed; such
algorithms usually require multiple _rounds_ to correct for improper
_speculative_ colorings produced in multi-threaded or distributed
environments.

There are many useful applications of graph coloring. Most commonly, it is
employed to find concurrency in parallel scientific computations [2, 4]; all
data sharing a color can be updated in parallel without incurring race
conditions. Other applications use coloring as a preprocessing step to speed
up the computation of Jacobian and Hessian matrices [5] and to identify short
circuits in printed circuit designs [6]. Despite the intractability of
minimizing the number of colors for non-trivial graphs, such applications
benefit from good heuristic algorithms that produce small numbers of colors.
For instance, Deveci et al. [2] show that a smaller number of colors used by a
coloring-based preconditioner reduces the runtime of a conjugate gradient
solver by 33%.

In particular, this work is motivated by the use of graph coloring as a
preprocessing step for distributed scientific computations such as automatic
differentiation [7]. For such applications, assembling the associated graphs
on a single node to run a sequential coloring algorithm may not be feasible
[3]. As such, we focus on running our algorithms on the parallel architectures
used by the underlying applications. These architectures typically are highly
distributed, with multiple CPUs and/or GPUs per node. Therefore, we
specifically consider coloring algorithms that can use the “MPI+X” paradigm,
where the Message Passing Interface (MPI) library is used in distributed
memory and “X” is multicore CPU or GPU acceleration.

###  1.1 Contributions

We present and examine two MPI+X implementations of distance-1 coloring as
well as one MPI+X implementation of distance-2 coloring. In order to run on a
wide variety of architectures, we use the Kokkos performance portability
framework [8, 9] for on-node parallelism and Trilinos [10] for distributed
MPI-based parallelism. The combination of Kokkos and MPI allows our algorithms
to run on multiple multicore CPUs or multiple GPUs in a system. For this
paper, we focus on the performance of our algorithms in MPI+GPU environments.
For distance-1 coloring of real-world networks, our algorithms achieve up to
2.38x speedup on 128 GPUs compared to a single GPU, and only a 2.23% increase
in the number of colors on average. For distance-2 coloring, our algorithm
achieves up to 33x speedup and, on average, a 7.5% increase in the number of
colors. We also demonstrate good weak scaling behavior up to 128 GPUs for
graphs with up to 12.8 billion vertices and 76.7 billion edges.

##  2 Background

###  2.1 Coloring Problem

While there exist many definitions of the “graph coloring problem,” we
specifically consider variants of distance-1 and distance-2 coloring. Consider
graph $G=(V,E)$ with vertex set $V$ and edge set $E$. _Distance-1 coloring_
assigns to each vertex $v\in V$ a color $C(v)$ such that $\forall(u,v)\in
E,C(u)\neq C(v)$. In _distance-2 coloring_ , colors are assigned such that
$\forall(u,v),(v,w)\in E,C(u)\neq C(v)\neq C(w)$; i.e., all vertices within
two hops of each other have different colors. _Partial Distance-2 coloring_ is
a special case of distance-2 coloring in which $\forall(u,v),(v,w)\in
E,C(u)\neq C(w)$; it is typically applied to bipartite graphs in which only
one set of the vertices is given colors (thus, the designation “partial”).
Partial distance-2 coloring is used to color sparse Jacobian matrices [11].
When a coloring satisfies one of the above constraints, it is called _proper_.
The goal is to find proper colorings of $G$ such that the total number of
different colors used is minimized.

###  2.2 Coloring Background

While minimizing the number of colors is NP-hard, serial coloring algorithms
using greedy heuristics have been effective for many applications [12]. The
serial greedy algorithm in Algorithm 1 colors vertices one at a time. Colors
are represented by integers, and the smallest usable color is assigned as a
vertex’s color. Most serial and parallel coloring algorithms use some
variation of greedy coloring, with algorithmic differences usually involving
the processing order of vertices or, in parallel, the handling of conflicts
and communication.

Algorithm 1 Serial greedy coloring algorithm

procedure SerialGreedy(Graph $G=(V,E)$)

$C(\forall v\in V)\leftarrow 0$ $\triangleright$ Initialize all colors as null

for all $v\in V$ in some order do

$c\leftarrow$ the _smallest_ color not used by a neighbor of $v$

$C(v)\leftarrow c$

_Conflicts_ in a coloring are edges that violate the color-assignment
criterion; for example, in distance-1 coloring, a conflict is an edge with
both endpoints sharing the same color. Colorings that contain conflicts are
not proper colorings, and are referred to as _pseudo-colorings_. Pseudo-
colorings arise only in parallel coloring, as conflicts arise only when two
vertices are colored concurrently. A coloring’s “quality” refers to the number
of colors used; higher quality colorings of a graph $G$ use fewer colors,
while lower quality colorings of $G$ use more colors.

It has been observed that the order vertices are visited affects the number of
colors needed. Popular vertex orderings include largest-degree-first,
smallest-degree-last, and saturation degree [13]. These orderings are highly
sequential and do not allow much parallelism. However, relaxations of those
orderings can allow some parallelism [14].

###  2.3 Parallel Coloring Algorithms

There are two popular approaches to parallel graph coloring. The first
concurrently finds independent sets of vertices and concurrently colors all of
the vertices in each set. This approach was used by Jones and Plassmann [15].
Osama et al. [16] found independent sets on a single GPU and explored the
impact of varying the baseline independent set algorithm.

The second approach, referred to as “speculate and iterate” [12, 17], colors
as many vertices as possible in parallel and then iteratively fixes conflicts
in the resulting pseudo-coloring until no conflicts remain. Gebremedhin et al.
[12], Çatalyürek et al. [17] and Rokos et al. [18] present shared-memory
implementations based on the speculate and iterate approach. Deveci et al. [2]
present implementations based on the speculate and iterate approach that are
scalable on a single GPU. Distributed-memory algorithms such as those in [3,
19] use the speculate and iterate approach. Grosset et al. [20] present a
hybrid speculate and iterate approach that splits computations between the CPU
and a single GPU, but does not operate on multiple GPUs in a distributed
memory context. Sallinen et al. [21] demonstrated how to color very large,
dynamic graphs efficiently. Besta et al. [13] developed shared memory coloring
algorithms and analyzed their performance. They compared to both Jones-
Plassman and speculative methods, but only on multicore CPU.

Bozdağ et al. [3] showed that, in distributed memory, the speculative approach
is more scalable than methods based on the independent set approach of Jones
and Plassmann. Therefore, we choose a speculative and iterative approach with
our algorithms.

###  2.4 Distributed Coloring

In a typical distributed memory setting, an input graph is split into
subgraphs that are assigned to separate processes. A process’s _local graph_
$G_{l}=\\{V_{l}+V_{g},E_{l}+E_{g}\\}$ is the subgraph assigned to the process.
Its vertex set $V_{l}$ contains _local vertices_ , and a process is said to
_own_ its local vertices. The intersection of all processes’ $V_{l}$ is null,
and the union equals $V$. The local graph also has non-local vertex set
$V_{g}$, with such non-local vertices commonly referred to as _ghost vertices_
; these vertices are copies of vertices owned by other processes. To ensure a
proper coloring, each process needs to store color state information for both
local vertices and ghost vertices; typically, ghost vertices are treated as
read-only. The local graph contains edge set $E_{l}$, edges between local
vertices, and $E_{g}$, edges containing at least one ghost vertex as an
endpoint. Bozdağ et al. [3] also defines two subsets of local vertices:
_boundary vertices_ and _interior vertices_. Boundary vertices are locally
owned vertices that share an edge with at least one ghost; interior vertices
are locally owned vertices that do not neighbor ghosts. For processes to
communicate colors associated with their local vertices, each vertex has a
unique global identifier (GID).

##  3 Methods

We present three hybrid MPI+GPU algorithms, called Distance-1 (D1), Distance-1
Two Ghost Layer (D1-2GL) and Distance-2 (D2). D1 and D1-2GL solve the
distance-1 coloring problem, and D2 does distance-2 coloring. We apply a
variation of our D2 coloring to do partial D2-coloring (PD2). We leverage
Trilinos [10] for distributed MPI-based parallelism and Kokkos [8] for on-node
parallelism. KokkosKernels [9] provides baseline implementations of distance-1
and distance-2 coloring algorithms that we use and modify for our local
coloring and recoloring subroutines.

Our three proposed algorithms follow the same basic framework, which builds
upon that of Bozdağ et al. [3]. Bozdağ et al. observe that interior vertices
can be properly colored independently on each process without creating
conflicts or requiring communication. They propose first coloring interior
vertices, and then coloring boundary vertices in small batches over multiple
rounds involving communication between processes. This approach can reduce the
occurrence of conflicts, which in turn reduces the amount of communication
necessary to properly color the boundary. In our approach, we color all
_local_ vertices first. Then, after communicating boundary vertices’ colors,
we fix all conflicts. Several rounds of conflict resolution and communication
may be needed to resolve all conflicts. We found that this approach was
generally faster than the batched boundary coloring, and it allowed us to use
existing parallel coloring routines in KokkosKernels without substantial
modification.

Algorithm 2 Distributed-Memory Speculative Coloring

procedure Parallel-Color(
Local Graph $G_{l}=\\{V_{l}+V_{g},E_{l}+E_{g}\\}$,GID)

colors $\leftarrow$ Color($G_{l}$, colors) $\triangleright$ Initially color
local graph

Communicate colors of boundary vertices

conflicts $\leftarrow$ Detect-Conflicts($G_{l}$, colors, GID)

Allreduce(conflicts, SUM) $\triangleright$ Global sum conflicts

while conflicts $>$ 0 do

$\mathit{gc}\leftarrow$ current colors of all ghosts

colors = Color($G_{l}$, colors) $\triangleright$ Recolor conflicted

$\triangleright$ vertices

Replace ghost colors with $\mathit{gc}$

Communicate updated boundary colors

conflicts $\leftarrow$ Detect-Conflicts($G_{l}$, colors, GID)

Allreduce(conflicts, SUM) $\triangleright$ Global sum conflicts

return colors

Algorithm 2 demonstrates the general approach for our three speculative
distributed algorithms. First, each process colors all local vertices with a
shared-memory algorithm. Then, each process communicates its boundary
vertices’ colors to processes with corresponding ghosts. Processes detect
conflicts in a globally consistent way and remove the colors of conflicted
vertices. Finally, processes locally recolor all uncolored vertices,
communicate updates, detect conflicts, and repeat until no conflicts are
found.

###  3.1 Distributed Boundaries

Figure 1: Definition of boundary vertex sets for different coloring instances

Figure 1 shows the sets of boundary vertices for distance-1 and distance-2
formulations of graph coloring. A process’ distance-1 boundary vertices are
its owned vertices that have edge neighbors owned by other processes. Its
distance-2 boundary vertices are its owned vertices whose neighbors have
neighbors owned by other processes. These sets allow us to optimize our
distributed conflict detection, as only vertices in the boundary may conflict
with a vertex on another process.

###  3.2 Distance-1 Coloring (D1)

Our Distance-1 method begins by independently coloring all owned vertices on
each process using the GPU-enabled algorithms by Deveci et al. [2] VB_BIT and
EB_BIT in KokkosKernels [9]. VB_BIT uses vertex-based parallelism; each vertex
is colored by a single thread. VB_BIT uses compact bit-based representations
of colors to make it performant on GPUs. EB_BIT uses edge-based parallelism; a
thread colors the endpoints of a single edge. EB_BIT also uses the compact
color representation to reduce memory usage on GPUs. For graphs with skewed
degree distribution (e.g., social networks), edge-based parallelism typically
yields better workload balance between GPU threads. We observed that for
graphs with a sufficiently large maximum degree, edge-based EB_BIT
outperformed vertex-based VB_BIT on Tesla V100 GPUs. Therefore, we use a
simple heuristic based on maximum degree: we use EB_BIT for graphs with
maximum degree greater than 6000; otherwise, we use VB_BIT.

Algorithm 3 Distance-1 conflict detection

procedure Detect-Conflicts-D1(
Local Graph $G_{l}=\\{V_{l}+V_{g},E_{l}+E_{g}\\}$, colors, GID)

conflicts $\leftarrow$ 0

for all $v\in V_{g}$ do in parallel

for all $\langle v,u\rangle\in(E_{g})$ do

conflicts $\leftarrow$ conflicts $+$ Check-Conflicts($v,u,\ldots$)

if colors[$v$] $=$ 0 then

break

return conflicts

Algorithm 4 Algorithm to identify and resolve conflicts

procedure Check-Conflicts($v$, $u$, colors, GID, recolorDegrees)

if colors[$v$] $=$ colors[$u$] then

if recolorDegrees and degree($v$) $<$ degree($u$) then

colors[$v$] $\leftarrow$ 0

else if recolorDegrees and degree($u$) $<$ degree($v$) then

colors[$u$] $\leftarrow$ 0

else if rand(GID[$v$]) $>$ rand(GID[$u$]) then

colors[$v$] $\leftarrow$ 0

else if rand(GID[$u$]) $>$ rand(GID[$v$]) then

colors[$u$] $\leftarrow$ 0

else if GID[$v$] $>$ GID[$u$] then

colors[$v$] $\leftarrow$ 0

else

colors[$u$] $\leftarrow$ 0

return 1

return 0

Algorithm 3 shows the conflict detection component of Algorithm 2. This
algorithm runs on each process using its local graph $G_{l}$. It detects
conflicts across processor boundaries and uncolors vertices to resolve the
conflicts before recoloring.

After the initial coloring, only boundary vertices can be in conflict with one
another111As suggested by Bozdağ et al., we considered reordering local
vertices to group all boundary vertices together for ease of processing. This
optimization did not show benefit in our implementation, as reordering tended
to be slower than coloring of the entire local graph.. We perform a full
exchange of boundary vertices’ colors using collective communication functions
implemented in the Zoltan2 package of Trilinos [10]. After the initial all-to-
all boundary exchange, we only communicate the colors of boundary vertices
that have been recolored. After each process receives its ghosts’ colors, it
detects conflicts by checking each owned vertex’s color against the colors of
its neighbor. The conflict detection is done in parallel over the owned
vertices using Kokkos. The overall time of conflict detection is small enough
that any imbalance resulting from our use of vertex-based parallelism is
insignificant relative to end-to-end times for the D1 algorithm.

Once we have identified all conflicts, we again use VB_BIT or EB_BIT to
recolor the determined set of conflicting vertices. We modified KokkosKernels’
coloring implementations to accept a “partial” coloring and the full local
graph, including ghosts. (Our initial coloring phase did not need ghost
information.) We also modified VB_BIT to accept a list of vertices to be
recolored. Such a modification was not feasible for EB_BIT.

Before we detect conflicts and recolor vertices, we save a copy of the ghosts’
colors ($\mathit{gc}$ in Algorithm 3). Then we give color zero to all vertices
that will be recolored; our coloring functions interpret color zero as
uncolored.

To prevent the coloring functions from resolving conflicts without respecting
our conflict resolution rules (thus preventing convergence of our parallel
coloring), we allow a process to temporarily recolor some ghosts, even though
the process does not have enough color information to correctly recolor them.
The ghosts’ colors are then restored to their original values in order to keep
ghosts’ colors consistent with their owning process. Then, we communicate only
recolored owned vertices, ensuring that recoloring changes only owned
vertices.

###  3.3 Distributed Recoloring Using Vertex Degrees

When a conflict is found, only one vertex involved in the conflict needs to be
recolored. Since conflicts happen on edges between two processes’ vertices,
both processes must agree on which vertex will be recolored.

We propose a new algorithm for selecting vertices to be recolored in the
conflict phase, based on prioritizing by vertex degrees. This idea was
inspired by the effectiveness of largest-first and smallest-last ordering in
the serial greedy algorithm. To the best of our knowledge, prioritizing the
distributed recoloring of lower degree vertices is a novel approach to
distributed coloring conflict resolution. In this approach, shown in Algorithm
4, when recolorDegrees is true, our conflict detection prioritizes recoloring
the lower degree vertex involved in a distributed conflict. For vertices with
equal degree, we adopt the random conflict resolution scheme of Bozdağ et al.
in which the conflicted vertex with the higher random number generated from
its global identifier (GID) is chosen for recoloring.

The idea behind our recolorDegrees heuristic is that recoloring vertices with
large degrees will likely result in giving those vertices a higher color,
while recoloring vertices with a smaller degree may be able to use a smaller
color for that vertex. Additionally, recoloring vertices with fewer neighbors
means that it is less likely that we recolor neighboring vertices concurrently
which can reduce the number of conflicts that arise during distributed
recoloring. We show that this approach generally decreases runtime for
distance-1 coloring, and reduces the number of colors used. In our
experiments, recolorDegrees reduces our color usage by 8.9% and runtime by
roughly 7% for D1 on average. It achieves a maximum speedup of 45%, and a
maximum color reduction of 39% over using D1 without recolorDegrees.

We compute the vertex degrees only once. Possible variations include using a
“dynamic” degree based on how many neighbors have been colored or the
“saturation degree” (how many colors the colored neighbors have been
assigned). We do not investigate those variations here.

###  3.4 Two Ghost Layers Coloring (D1-2GL)

Our second algorithm for distance-1 coloring, D1-2GL, follows the D1 method,
but adds another ghost vertex “layer” to the subgraphs on each process. In D1,
a process’ subgraph does not include neighbors of ghost vertices unless those
neighbors are already owned by the process. In D1-2GL, we include all
neighbors of ghost vertices (the two-hop neighborhood of local vertices) in
each process’s subgraph, giving us “two ghost layers.” To the best of our
knowledge, this approach has not been explored before with respect to graph
coloring.

This method can reduce the total amount of communication relative to D1 for
certain graphs by reducing the total number of recoloring rounds needed. In
particular, for mesh or otherwise regular graphs, the second ghost layer is
primarily made up of interior vertices on other processes. Interior vertices
are never recolored, so the colors of the vertices in the second ghost layer
are fixed. Each process can then directly resolve more conflicts in a
consistent way, thus requiring fewer rounds of recoloring. Fewer recoloring
rounds results in fewer collective communications.

However, in D1-2GL, each communication is more expensive than in D1, because a
larger boundary from each process is communicated. Also, in irregular graphs,
the second ghost layer often does not have mostly interior vertices. The
relative proportion of interior vertices in the second layer also gets smaller
as the number of processes increases. For the extra ghost layer to pay off, it
must reduce the number of rounds of communications enough to make up for the
increased cost of each communication.

To construct the second ghost layer on each process, processes exchange the
adjacency lists of their boundary vertices; this step is needed only once.
After the ghosts’ connectivity information is added, we use the same coloring
approach as in D1.

We optimize our conflict detection for both distance-1 implementations by
looking through only the ghost vertices’ adjacencies ($E_{g}$), as they
neighbor all local boundary vertices. Our local coloring algorithms require
our local graphs to have undirected edges to ghost vertices, so this
optimization is trivial for both D1 and D1-2GL.

Table 1: Summary of D1 and D2 input graphs. $\delta_{avg}$ refers to average degree and $\delta_{max}$ refers to maximum degree. Values listed are after preprocessing to remove multi-edges and self-loops. k = thousand, M = million, B = billion. Graph | Class | #Vertices | #Edges | $\delta_{avg}$ | $\delta_{max}$ | Memory (GB)
---|---|---|---|---|---|---
ldoor | PDE Problem | 0.9 M | 21 M | 45 | 77 | 0.32
Audikw_1 | PDE Problem | 0.9 M | 39 M | 81 | 345 | 0.59
Bump_2911 | PDE Problem | 2.9 M | 63 M | 43 | 194 | 0.96
Queen_4147 | PDE Problem | 4.1 M | 163 M | 78 | 89 | 2.5
soc-LiveJournal1 | Social Network | 4.8 M | 43 M | 18 | 20 k | 0.67
hollywood-2009 | Social Network | 1.1 M | 57 M | 99 | 12 k | 0.86
twitter7 | Social Network | 42 M | 1.4 B | 35 | 2.9 M | 21
com-Friendster | Social Network | 66 M | 1.8 B | 55 | 5.2 k | 27
europe_osm | Road Network | 51 M | 54 M | 2.1 | 13 | 1.2
indochina-2004 | Web Graph | 7.4 M | 194 M | 26 | 256 k | 2.9
MOLIERE_2016 | Document Mining Network | 30 M | 3.3 B | 80 | 2.1 M | 49
rgg_n_2_24_s0 | Synthetic Graph | 17 M | 133 M | 15 | 40 | 2.1
kron_g500-logn21 | Synthetic Graph | 2.0 M | 182 M | 87 | 8.7 | 2.7
mycielskian19 | Synthetic Graph | 393 k | 452 M | 2.3 k | 196 k | 6.7
mycielskian20 | Synthetic Graph | 786 k | 1.4 B | 3.4 k | 393 k | 21
hexahedral | Weak Scaling Tests | 12.5 M – 12.8 B | 75 M – 76.7 B | 6 | 6 | 1.2 GB – 1.1 TB

###  3.5 Distance-2 Coloring (D2)

Our distance-2 coloring algorithm, D2, builds upon both D1 and D1-2GL. As with
distance-1 coloring, we use algorithms from Deveci et al. in KokkosKernels for
local distance-2 coloring. Specifically, we use NB_BIT, which is a “net-based”
distance-2 coloring algorithm that uses the approach described by Taş et al.
[22]. Instead of checking for distance-2 conflicts only between a single
vertex and its two-hop neighborhood, the net-based approach detects distance-2
conflicts among the immediate neighbors of a vertex. Our D2 approach also
utilizes a second ghost layer to give each process the full two-hop
neighborhood of its boundary vertices. This enables each process to directly
check for distance-2 conflicts with local adjacency information. To find a
distance-2 conflict for a given vertex, its entire two-hop neighborhood must
be checked for potential conflicting colors.

Algorithm 5 Distance-2 conflict detection

procedure Detect-D2-Conflicts(
Local Graph $G_{l}=\\{V_{l}+V_{g},E_{l}+E_{g}\\}$, $V_{b}$, colors, GID,
doPartialColoring)

conflicts $\leftarrow$ 0

for all $v\in V_{b}$ do in parallel

for all $\langle v,u\rangle\in(E_{l}+E_{g})$ do

if not doPartialColoring then

conflicts $\leftarrow$ conflicts $+$ Check-Conflicts($v,u,\ldots$)

if colors[$v$] $=$ 0 then

break

for all $\langle u,x\rangle\in(E_{l}+E_{g})$ do

$\triangleright$ $u$ is one hop and $x$ is two hops from $v$

conflicts $\leftarrow$ conflicts $+$ Check-Conflicts($v,x,\ldots$)

if colors[$v$] $=$ 0 then

break

if colors[$v$] $=$ 0 then

break

return conflicts

Algorithm 5 shows conflict detection in D2 for each process. We again use
vertex-based parallelism while detecting conflicts; each thread examines the
entire two-hop neighborhood of a vertex $v$. The input argument $V_{b}$ is the
set of distance-2 boundary vertices (as in Figure 1), which we precompute. As
with distance-1 conflict detection, we identify all local conflicts and use a
random number generator to ensure that vertices to be recolored are chosen
consistently across processes. The iterative recoloring method of D1 then also
works for D2 — we recolor all conflicts, replace the old ghost colors, and
then communicate local changes.

###  3.6 Partial Distance-2 Coloring (PD2)

We have also implemented an algorithm, PD2, that solves the partial distance-2
coloring problem. Partial distance-2 coloring is similar to distance-2
coloring, but it detects and resolves only two-hop conflicts. Typically,
partial distance-2 coloring is used on non-symmetric graphs. A bipartite graph
$B(V_{s},V_{t},E_{B})$ is constructed from $G(V,E)$ with an undirected edge
$\langle v_{s}\in V_{s},v_{t}\in V_{t}\rangle$ $\in E_{B}$ for each directed
edge $\langle v_{s},v_{t}\rangle\in E$; colors are needed only for vertices in
$V_{s}$. Partial distance-2 coloring colors only one set of the vertices in
the bipartite graph, which is why it is a partial coloring. In algorithm 5,
when doPartialColoring is false, the algorithm detects all distance-2
conflicts. When doPartialColoring is true, it only detects two-hop conflicts
for the partial coloring. Currently, our PD2 implementation must color all
vertices in the bipartite representation of the graph; applications can ignore
colors for vertices in $V_{t}$. Removing this limitation is a subject for
future work.

###  3.7 Partitioning

We assume that target applications partition and distribute their input graphs
in some way before calling these coloring algorithms. In our experiments, we
used XtraPuLP v0.3 [23] to partition our graphs. Determining optimal
partitions for coloring is not our goal in this work. Rather, we have chosen a
partitioning strategy representative of that used in many applications. We
partition graphs by balancing the number of edges per-process and minimizing a
global edge-cut metric. This approach effectively balances per-process
workload and helps minimize global communication requirements.

##  4 Experimental Setup

We performed scaling experiments on the AiMOS supercomputer housed at
Rensselaer Polytechnic Institute. The system has 268 nodes, each equipped with
two IBM Power 9 processors clocked at 3.15 GHz, 4x NVIDIA Tesla V100 GPUs with
16 GB of memory connected via NVLink, 512 GB of RAM, and 1.6 TB Samsung NVMe
Flash memory. Inter-node communication uses a Mellanox Infiniband
interconnect. We compile with xlC 16.1.1 and use Spectrum MPI with GPU-Direct
communication disabled.

The graphs we used to test D1 and D2 are listed in Table 1. Most of the graphs
are from the SuiteSparse Matrix Collection [24]. The maximum degree
$\delta_{max}$ can be considered an upper bound for the number of colors used,
as any incomplete, connected, and undirected graph can be colored using
$\delta_{max}$ colors [25]. We selected many of the same graphs used by Deveci
et al. to allow for direct performance comparisons. We include many graphs
from Partial Differential Equation (PDE) problems because they are
representative of graphs used with Automatic Differentiation [7], which is a
target application for graph coloring algorithms. We also include social
network graphs and a web crawl to demonstrate scaling of our methods on
irregular real-world datasets. We preprocessed all graphs to remove multi-
edges and self-loops, and we used subroutines from HPCGraph [26] for efficient
I/O.

We compare our implementation against distributed distance-1 and distance-2
coloring in the Zoltan [27] package of Trilinos. Zoltan’s implementations are
based directly on Bozdağ et al. [3]. Zoltan’s distributed algorithm for
distance-2 coloring requires only a single ghost layer, and to reduce
conflicts, the boundary vertices are colored in small batches. For our
results, we ran Zoltan and our approaches with four MPI ranks per node on
AiMOS, and used the same partitioning method across all of our comparisons.
Our methods D1, D1-2GL, and D2 were run with four GPUs and four MPI ranks (one
per GPU) per node. Zoltan uses only MPI parallelism; it does not use GPU or
multicore parallelism. For consistency, we use four MPI ranks per node with
Zoltan, and use the same number of nodes for experiments with Zoltan and our
methods. We used Zoltan’s default coloring parameters; we did not experiment
with options for vertex visit ordering, boundary coloring batch size, etc.

We omit direct comparison to single-node GPU coloring codes such as CuSPARSE
[28], as we use subroutines for on-node coloring from Deveci et al. [2].
Deveci et al. have already performed a comprehensive comparison between their
coloring methods and those in CuSPARSE, reporting an average speedup of 50%
across a similar set of test instances. As such, we are confident that our on-
node GPU coloring is representative of the current state-of-the-art.

##  5 Results

For our experiments, we compare overall performance for D1 and D2 on up to 128
ranks versus Zoltan. Our performance metrics include execution time, parallel
scaling, and number of colors used. We do not include the partitioning time
for XtraPuLP; we assume target applications will partition and distribute
their graphs. Each of the results reported represents an average of five runs.

###  5.1 Distance-1 Performance

We summarize the performance of our algorithms relative to Zoltan using the
performance profiles in Figure 2. Performance profiles plot the proportion of
problems an algorithm can solve for a given relative cost. The relative cost
is obtained by dividing each approach’s execution time (or colors used) by the
best approach’s execution time (or colors used) for a given problem. In these
plots, the line that is higher represents the best performing algorithm. The
further to the right that an algorithm’s profile is, the worse it is relative
to the best algorithm. D1-baseline does not consider vertex degree when doing
distributed recoloring (e.g., recolorDegrees is false in Algorithm 4).
D1-recolor-degree represents our novel approach that recolors distributed
conflicts based on vertex degree (e.g., recolorDegrees is true in Algorithm
4).

Figure 2: Performance profiles comparing D1-baseline and D1-recolor-degree on
128 Tesla V100 GPUs with Zoltan’s distance-1 coloring on 128 Power9 cores in
terms of (a) execution time and (b) number of colors computed for the graphs
listed in Table 1.

(a) Runtime performance profile

(b) Color performance profile

We ran D1-baseline, D1-recolor-degree and Zoltan with 128 MPI ranks to color
the 15 SuiteSparse graphs in Table 1. D1-baseline and D1-recolor-degree used
MPI plus 128 Tesla V100 GPUs, while Zoltan used MPI on 128 Power9 CPU cores
across 32 nodes (four MPI ranks per node). Some skewed graphs (e.g.,
hollywood-2009) did not run on 128 ranks on Zoltan or D1-baseline; in those
cases we use the largest run that completed for both approaches. Figure 2(a)
shows that D1-recolor-degree outperforms both Zoltan and D1-baselines in terms
of execution time in these experiments. D1-baseline and D1-recolor-degree are
very similar in terms of runtime performance, but D1-recolor-degree is the
fastest approach for 60% of the graphs, D1-baseline is fastest on 26%, and
Zoltan is fastest on 13%. Zoltan is faster than our approaches on two of the
smallest graphs, Audikw_1, and ldoor. D1-baseline is faster than D1-recolor-
degrees on four graphs which are more varied in application and structure:
Bump_2911, com-Friendster, rgg_n_2_24_s0, and twitter7. There are four graphs
for which D1-baseline and D1-recolor-degrees runtime performance differ
substantially: Audikw_1 (D1-baseline is 32% faster), ldoor (D1-recolor-degrees
is 42% faster), mycielskian19 (D1-recolor-degrees is 45% faster), and
mycielskian20 (D1-recolor-degrees is 38% faster). D1-baseline has at most a
10x speedup over Zoltan (with the mycielskian20 graph) and at worst an 1.95x
slowdown relative to Zoltan (with ldoor), while D1-recolor-degrees achieves at
most a 14x speedup over Zoltan (on mycielskian20), and at worst a 2x slowdown
(on Audikw_1).

Figure 2(b) shows that Zoltan outperforms D1-baseline in terms of color usage,
but D1-recolor-degree is much more competitive. Both Zoltan and D1-recolor-
degree use the fewest colors in 53% of experiments; Zoltan and D1-recolor-
degree tie on a single graph. D1-baseline uses the fewest number of colors on
a single graph, for which it ties D1-recolor-degree. D1-recolor-degree uses
more colors than D1-baseline for two graphs (indochina-2004 and twitter7); in
both graph, D1-baseline uses roughly 1% fewer colors. On average, D1-recolor-
degree uses 8.9% fewer colors than D1-baseline, and in the best case, it
reduces color usage 39% relative to D1-baseline (mycielskian19). On average,
D1-recolor-degree uses 4% fewer colors than Zoltan. In the worst case,
D1-recolor-degree uses 51% more colors than Zoltan (twitter7); in the best
case, D1-recolor-degree uses 53% fewer colors than Zoltan (mycielskian20).

Because the performance of D1-recolor-degree is generally better than that of
D1-baseline, all further distance-1 coloring results use D1-recolor-degree,
and we refer to D1-recolor-degree as D1 going forward.

###  5.2 Distance-1 Strong Scaling

Figure 3 shows strong scaling times for Queen_4147 and com-Friendster. These
graphs are selected for presentation because they are the largest graphs of
their respective problem domains. Data points that are absent were the result
of out-of-memory issues or execution times (including partitioning) that were
longer than our single job allocation limits. D1 scales better on the com-
Friendster graph than on Queen_4147, as the GPUs can be more fully utilized
with the much larger com-Friendster graph. For Queen_4147, D1 on 128 GPUs
shows a speedup of around 2.38x over a single GPU. D1 uses 12% fewer colors
than Zoltan in the 128 rank run on Queen_4147, as well as running 1.75x faster
than Zoltan on that graph. For com-Friendster, D1 is roughly 4.6x faster than
Zoltan in the 128 rank run, and only uses 0.6% more colors than Zoltan.

Figure 3: Zoltan and D1 strong scaling on select (a) PDE and (b) Social
Network graphs.

(a) Queen_4147

(b) com-Friendster

For graph processing in general, it is often difficult to demonstrate good
strong scaling relative to single node runs. From the Graph500.org benchmark
(June 2020 BFS results) [29], the relative per-node performance difference in
the metric of “edges processed per second” between the fastest multi-node
results and fastest single node results are well over 100x. For coloring on
GPUs, graphs that can fit into a single GPU do not provide sufficient work
parallelism for large numbers of GPUs, and multi-GPU execution incurs
communication overheads and additional required rounds for speculative
coloring. However, on roughly half of the graphs that fit on a single GPU, D1
with 128 GPUs achieves an average speedup of 1.9x over a single GPU. D1
achieves a maximum speedup of 2.43x on the mycielskian20 graph. For the other
half of the graphs, D1 does not show a speedup over a single GPU. On small or
highly skewed graphs that fit on a single GPU, speedup is limited, due to the
communication overheads and work imbalances that result from distribution even
with relatively good partitioning. Distributed coloring is valuable even for
these small problems, however, as parallel applications using coloring
typically have distributed data that would be expensive to gather into one GPU
for single-GPU coloring.

On average over all the graphs, D1 uses 38% more colors than the single GPU
run, while Zoltan uses 53.6% more colors than the single GPU run. Such large
color usage increases are mostly due to the Mycielskian19 and Mycielskian20
graphs. These graphs were generated to have known minimum number of colors
(chromatic numbers) of 19 and 20 respectively, and our single GPU runs use 19
and 21 colors to color those graphs. Both D1 and Zoltan have trouble coloring
these graphs in distributed memory, but our D1 implementation colors these
graphs in fewer colors than Zoltan. Without these two outliers, the average
color increase from the single GPU run is only 2.23% for D1, and Zoltan
decreases color usage by 0.1% on average. Zoltan’s higher coloring quality is
due to its inherently lower concurrency.

Figure 4: D1 communication time (Comm) and computation time (Comp) from 1 to
128 GPUs.

(a) Queen_4147

(b) com-Friendster

Figure 4 shows the total communication and computation time associated with
each run. For both graphs, the dominant scaling factor is computation.
Specifically, the computational overhead associated with recoloring vertices
in distributed memory is the dominant scaling factor. However, strong scaling
is good on both graphs, despite the fact that adding more ranks to a problem
also increases the number of vertices that need to be recolored. Figure 4(b)
shows that D1 scales to more ranks on com-Friendster, primarily because of the
graph’s larger size.

###  5.3 Distance-1 Weak Scaling

The greatest benefit of our approach is its ability to efficiently process
massive-scale graphs. We demonstrate this benefit with a weak-scaling study
conducted with uniform 3D hexahedral meshes. The meshes were partitioned with
block partitioning along a single axis, resulting in the mesh being
distributed in “slabs.” Larger meshes were generated by doubling the number of
elements in a single dimension to keep the per-process communication and
computational workload constant. Each distinct per-process workload increases
the boundary by a factor of two, which correspondingly increases communication
and recoloring overhead for distributed runs. We run with up to 100 million
vertices per GPU, yielding a graph of 12.8 billion vertices and 76.7 billion
edges in our largest tests; this graph was colored in less than two seconds.

Figure 5: Weak scaling of D1 on 3D mesh graphs. Tests use 12.5, 25, 50, and
100 million vertices per GPU.

Figure 5 shows that the single rank runs for each workload are similar,
indicating that communication and recoloring overhead are the dominant scaling
factors for this study. In increasing the boundary size by a factor of two, we
do not necessarily increase the number of distributed conflicts by two,
especially in such a regular graph. The smaller workloads all have similar and
relatively small recoloring workloads, which is why they show more consistent
weak scaling than the 100 Million vertex per rank experiment. That particular
experiment does substantially more recoloring than the others, resulting in
its increase in runtime as the number of ranks increases. We have found that
for extremely regular meshes like these, the number of vertices on process
boundaries impacts the recoloring workloads for D1.

###  5.4 D1-2GL Performance

In general, D1-2GL reduces the number of collective communications used in the
distributed distance-1 coloring. Figure 6 compares the number of communication
rounds for D1-baseline and D1-2GL on the Queen_4157 input for 2 to 128 MPI
ranks, averaged over five runs. With 128 ranks on this graph, D1-2GL method
reduces the number of rounds by 25% on average, giving speedup of 1.18x.
D1-2GL provides speedups over D1-baseline with the smaller graphs: 1.17x with
Audikw_1 and 1.2x with ldoor. Unfortunately, due to the increased cost of each
communication round, D1-2GL does not generally achieve a total execution time
speedup over D1-baseline on AiMOS. Additionally, second ghost layer vertices
may be recolored if they are boundary vertices on another processor; this
occurs often in dense inputs and incurs further recoloring rounds. However, in
distributed systems with much higher latency costs, D1-2GL could be
beneficial.

Figure 6: Number of communication rounds for D1-baseline and D1-2GL on
Queen_4147 from 2 to 128 ranks.

###  5.5 Distance-2 Performance

We compare our D2 method to Zoltan’s distance-2 coloring using eight graphs
from Table 1: Bump_2911, Queen_4147, hollywood-2009, europe_osm,
rgg_n_2_24_s0, ldoor, Audikw_1, and soc-LiveJournal1. We use the same
experimental setup as with the distance-1 performance comparison. Figure 7(a)
shows that D2 compares well against Zoltan in terms of execution time, with D2
outperforming Zoltan on all but two graphs. In the best case, we see an 8.5x
speedup over Zoltan on the Queen_4147 graph.

Figure 7: Performance profiles comparing D2 on 128 Tesla V100 GPUs with
Zoltan’s distance-2 coloring on 128 Power9 cores in terms of (a) execution
time and (b) number of colors computed for a subset of graphs listed in Table
1.

(a) Runtime performance profile

(b) Color performance profile

Figure 7(b) shows that D2 has similar color usage as Zoltan. D2 and Zoltan
each produce fewer colors in half of the experiments. In all but one case in
which Zoltan uses fewer colors, D2 uses no more than 10% more colors.
Interestingly, the number of colors used by D2 on the soc-LiveJournal1 graph
is unchanged with one and 128 GPUs. Zoltan outperforms D2 with respect to
runtime on skewed graphs because Zoltan has distance-2 optimizations which
reduce communication overhead and minimize the chance for distributed
conflicts.

###  5.6 Distance-2 Strong Scaling

Figures 8(a) and 8(b) show the strong scaling behavior of D2 and Zoltan on
Bump_2911 and Queen_4147. Bump_2911 shows that D2 scales better initially than
Zoltan, and with 128 ranks, D2 is 2.9x faster than Zoltan, using 0.7% more
colors. Queen_4147 shows better scaling for D2 as well; with 128 ranks, D2 is
8.5x faster than Zoltan and uses 10% fewer colors.

Figure 8: D2 and Zoltan strong scaling for distance-2 coloring.

(a) Bump_2911

(b) Queen_4147

On average over the eight graphs, D2 exhibits 4.29x speedup on 128 GPUs over a
single GPU, and uses 7.5% more colors than single GPU runs. Speedup is greater
with D2 than D1 because distance-2 coloring is more computationally intensive,
and thus has a larger work-to-overhead ratio.

Figure 9: D2 communication time (comm) and computation time (comp) from 1 to
128 GPUs.

(a) Bump_2911

(b) Queen_4147

Figures 9(a) and 9(b) show the communication and computation breakdown of D2
on Bump_2911 and Queen_4147. Bump_2911 shows computation and communication
scaling for up to 128 ranks, while color usage increases by only 0.6%. In
general, the relative increase in color usage from a single rank for
distance-2 coloring is less than for distance-1 coloring. The number of colors
used for distance-2 coloring is greater than for distance-1; therefore, a
similar absolute increase in color count results in a lower proportional
increase.

###  5.7 Distance-2 Weak Scaling

Figure 10 demonstrates the weak scaling behavior for D2. The same hexahedral
mesh graphs were used as in the D1 weak scaling experiments. In general, D2
has fairly consistent weak scaling. The runtimes across workloads with a
single rank increase by more than factor of two because the number of edges in
each mesh increases by more than a factor of two, and the complexity of the
distance-2 coloring algorithm for local colorings depends on the number of
edges. Weak scaling to large process counts is good for all workloads.

Figure 10: Distance-2 weak scaling of D2 on 3D mesh graphs.

###  5.8 Partial Distance-2 Strong Scaling

Table 2: Summary of the graphs used for PD2 tests. Statistics are for the bipartite representation of the graph (Section 3.6). $\delta_{avg}$ is average degree and $\delta_{max}$ is maximum degree. Numeric values listed are after preprocessing to remove multi-edges and self-loops. k = thousand, M = million Graph | Class | #Vtx | #Edges | $\delta_{avg}$ | $\delta_{max}$
---|---|---|---|---|---
Hamrle3 | Circuit Sim. | 2.9 M | 5.5 M | 3.5 | 18
patents | Patent Citations | 7.5 M | 14.9 M | 1.9 | 1k

Table 2 shows the graphs that we used to compare our PD2 implementation
against Zoltan. Partial distance-2 coloring is typically used on non-symmetric
and bipartite graphs; the graphs in Table 2 are representative of application
use cases. We report metrics reported for the bipartite representation of the
graph (as described in Section 3.6). Partial distance-2 colorings typically
are needed for only a subset of the vertices in a graph, but our PD2
implementation colors all vertices in the graph. We compare to Zoltan, which
colors only vertices that would be colored in typical partial distance-2
coloring. Thus, in general, PD2 is coloring roughly twice as many vertices as
Zoltan.

Figure 11: PD2 strong scaling for partial distance-2 coloring.

(a) patents

(b) Hamrle3

Figure 11 shows the strong scaling behavior of PD2. The experiment with
Hamrle3 on four ranks benefits from a particularly good partition that results
in less recoloring for both PD2 and Zoltan relative to other process
configurations. For the patents graph, D2 has a particularly heavy recoloring
workload for four ranks, resulting in a large increase in runtime from two to
four ranks. Even though PD2 is coloring more vertices than Zoltan in these
tests, PD2 achieves roughly 2x speedup on 128 ranks with Hamrle3. With
patents, Zoltan is faster than PD2; this result can be attributed partially to
Zoltan’s optimized recoloring scheme that reduces the number of conflicts
introduced while recoloring distributed conflicts. PD2 achieves a 1.73x
speedup over a single GPU with the patents graph, while it did not show any
speedup from a single GPU with Hamrle3. Figure 11(a) shows that, with the
patents graph, Zoltan is faster on one core than a single GPU. This speedup is
attributed to Zoltan’s coloring fewer vertices than PD2; when Zoltan colors
the same number of vertices as PD2, their single rank runtimes are equal.
Investigating the cause of this result is a subject for future research.

For these two graphs, PD2 uses a very similar number of colors as Zoltan. PD2
uses at most 10% more colors in the distributed runs. This difference is
typically only one to five colors more than Zoltan.

Figure 12: PD2 communication time (comm) and computation time (comp) from 1 to
128 GPUs

(a) patents

(b) Hamrle3

Figure 12 shows that computation is the main factor in the scaling behavior of
PD2. In distributed runs, the largest factor of the runtime is the computation
overhead involved in recoloring distributed conflicts. Figure 12(b) shows an
unexpected decrease in computation for the Hamrle3 graph for four ranks, which
is due to a decrease in the recoloring workload. PD2’s recoloring workload is
approximately 25,000 vertices per rank in most experiments, but the four-rank
experiment has a recoloring workload of 9,000 vertices per rank. Figure 12(a)
shows that the four-rank PD2 run has a much longer computation time than
expected; this is due to the total distributed recoloring workload increasing
by a factor of six. Additionally, the 64-rank run with the patents graph shows
slightly less computational scaling than expected, due to an increase in
recoloring rounds. Increasing recoloring rounds serializes recoloring
computation and incurs more rounds of communication, resulting in a runtime
increase. Optimizing recoloring to reduce subsequent conflicts and reduce the
number of recoloring rounds necessary in D2 and PD2 are subjects for future
research.

##  6 Future work

We have presented new multi-GPU distributed memory implementations of
distance-1, distance-2 and partial distance-2 graph coloring. These methods
enable parallel graph coloring for graphs too large to fit into a single GPUs
memory; weak-scaling results demonstrate coloring of a graph with 12.8 billion
vertices and 76.7 billion edges in less than two seconds. We introduced a new
recoloring heuristic based on vertex degrees that reduces the amount of
recoloring needed in parallel coloring methods. We showed that our approaches
are scalable to 128 GPUs and produce colorings with quality similar to or
better than Zoltan’s distributed memory coloring algorithms.

Because our coloring algorithms use the Kokkos and KokkosKernels library for
on-node performance portability, our MPI+X methods can also run on
distributed-memory computers with multicore (CPU-based) nodes. In this work,
we focused on GPU architectures; exploring multicore performance is future
work.

We are currently integrating this code into the Zoltan2 package of Trilinos.
Our goal is to deliver a complete suite of MPI+X algorithms for distance-1,
distance-2, and partial distance-2 coloring in Zoltan2. We will modify PD2 to
allow it to color only vertices of interest to the application as Zoltan does.

We also will investigate further optimizations to increase performance. There
are optimizations present in Zoltan’s implementation that are not directly
applicable to our implementation, but can inform optimizations that reduce the
overall recoloring workload and minimize communication. These changes could
increase performance for D1, D2, and PD2, as well as make D2 and PD2 more
scalable on skewed graphs.

##  7 Acknowledgments

We thank the Center of Computational Innovations at RPI for maintaining the
equipment used in this research, including the AiMOS supercomputer supported
by the National Science Foundation under Grant No. 1828083. This research was
also supported by the Exascale Computing Project (17-SC-20-SC), a
collaborative effort of the U.S. Department of Energy Office of Science and
the National Nuclear Security Administration. Sandia National Laboratories is
a multimission laboratory managed and operated by National Technology and
Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell
International, Inc., for the U.S. Department of Energy’s National Nuclear
Security Administration under contract DE-NA-0003525.

## References

## References

  * [1] D. Brélaz, New methods to color the vertices of a graph, Communications of the ACM 22 (4) (1979) 251–256.
  * [2] M. Deveci, E. G. Boman, K. D. Devine, S. Rajamanickam, Parallel graph coloring for manycore architectures, in: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2016, pp. 892–901.
  * [3] D. Bozdağ, A. H. Gebremedhin, F. Manne, E. G. Boman, U. V. Catalyurek, A framework for scalable greedy coloring on distributed-memory parallel computers, Journal of Parallel and Distributed Computing 68 (4) (2008) 515–535.
  * [4] J. Allwright, R. Bordawekar, P. Coddington, K. Dincer, C. Martin, A comparison of parallel graph coloring algorithms, SCCS-666 (1995) 1–19.
  * [5] A. H. Gebremedhin, D. Nguyen, M. M. A. Patwary, A. Pothen, Colpack: Software for graph coloring and related problems in scientific computing, ACM Transactions on Mathematical Software (TOMS) 40 (1) (2013) 1.
  * [6] M. Garey, D. Johnson, H. So, An application of graph coloring to printed circuit testing, IEEE Transactions on Circuits and Systems 23 (10) (1976) 591–599.
  * [7] A. H. Gebremedhin, A. Walther, An introduction to algorithmic differentiation, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 10 (1) (2020) e1334.
  * [8] H. C. Edwards, C. R. Trott, D. Sunderland, Kokkos: Enabling manycore performance portability through polymorphic memory access patterns, Journal of Parallel and Distributed Computing 74 (12) (2014) 3202–3216.
  * [9] Kokkos Kernels (2017).
URL https://github.com/kokkos/kokkos-kernels

  * [10] M. A. Heroux, R. A. Bartlett, V. E. Howle, R. J. Hoekstra, J. J. Hu, T. G. Kolda, R. B. Lehoucq, K. R. Long, R. P. Pawlowski, E. T. Phipps, et al., An overview of the Trilinos project, ACM Transactions on Mathematical Software (TOMS) 31 (3) (2005) 397–423.
  * [11] A. H. Gebremedhin, F. Manne, A. Pothen, What color is your Jacobian? graph coloring for derivatives., SIAM Review 47 (4) (2005) 629––705.
  * [12] A. H. Gebremedhin, F. Manne, Scalable parallel graph coloring algorithms, Concurrency: Practice and Experience 12 (12) (2000) 1131–1146.
  * [13] M. Besta, A. Carigiet, K. Janda, Z. Vonarburg-Shmaria, L. Gianinazzi, T. Hoefler, High-performance parallel graph coloring with strong guarantees on work, depth, and quality, in: SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, 2020, pp. 1–17.
  * [14] W. Hasenplaugh, T. Kaler, T. B. Schardl, C. E. Leiserson, Ordering heuristics for parallel graph coloring, in: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, Association for Computing Machinery, New York, NY, USA, 2014, p. 166–177.  doi:10.1145/2612669.2612697.
URL https://doi.org/10.1145/2612669.2612697

  * [15] M. T. Jones, P. E. Plassmann, A parallel graph coloring heuristic, SIAM Journal on Scientific Computing 14 (3) (1993) 654–669.
  * [16] M. Osama, M. Truong, C. Yang, A. Buluç, J. D. Owens, Graph coloring on the GPU, in: GrAPL: Workshop on Graphs, Architectures, Programming, and Learning (IPDPSW), 2019.
URL http://eecs.berkeley.edu/~aydin/coloring.pdf

  * [17] Ü. V. Çatalyürek, J. Feo, A. H. Gebremedhin, M. Halappanavar, A. Pothen, Graph coloring algorithms for multi-core and massively multithreaded architectures, Parallel Computing 38 (10-11) (2012) 576–594.
  * [18] G. Rokos, G. Gorman, P. H. Kelly, A fast and scalable graph coloring algorithm for multi-core and many-core architectures, in: European Conference on Parallel Processing, Springer, 2015, pp. 414–425.
  * [19] A. E. Sariyüce, E. Saule, Ü. V. Çatalyürek, Scalable hybrid implementation of graph coloring using MPI and OpenMP, in: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, IEEE, 2012, pp. 1744–1753.
  * [20] A. V. P. Grosset, P. Zhu, S. Liu, S. Venkatasubramanian, M. Hall, Evaluating graph coloring on GPUs, ACM SIGPLAN Notices 46 (8) (2011) 297–298.
  * [21] S. Sallinen, K. Iwabuchi, S. Poudel, M. Gokhale, M. Ripeanu, R. Pearce, Graph colouring as a challenge problem for dynamic graph processing on distributed systems, in: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’16, IEEE Press, 2016.
  * [22] M. K. Taş, K. Kaya, E. Saule, Greed is good: Optimistic algorithms for bipartite-graph partial coloring on multicore architectures, arXiv preprint arXiv:1701.02628.
  * [23] G. M. Slota, S. Rajamanickam, K. Devine, K. Madduri, Partitioning trillion-edge graphs in minutes, in: 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2017, pp. 646–655.
  * [24] T. A. Davis, Y. Hu, The university of florida sparse matrix collection, ACM Trans. Math. Softw. 38 (1) (2011) 1:1–1:25.  doi:10.1145/2049662.2049663.
URL http://doi.acm.org/10.1145/2049662.2049663

  * [25] R. L. Brooks, On colouring the nodes of a network, in: Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 37, Cambridge University Press, 1941, pp. 194–197.
  * [26] G. M. Slota, S. Rajamanickam, K. Madduri, A case study of complex graph analysis in distributed memory: Implementation and optimization, in: International Parallel & Distributed Processing Symposium (IPDPS), 2016.
  * [27] K. D. Devine, E. G. Boman, L. A. Riesen, U. V. Catalyurek, C. Chevalier, Getting started with Zoltan: A short tutorial, in: Dagstuhl Seminar Proceedings, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2009.
  * [28] M. Naumov, P. Castonguay, J. Cohen, Parallel graph coloring with applications to the incomplete-lu factorization on the gpu, Tech. rep., NVidia White Paper (2015).
  * [29] Graph 500 (2020).
URL https://graph500.org/