# Colorings with neighborhood parity condition

Mirko Petruševski , Riste Škrekovski Department of Mathematics and
Informatics, Faculty of Mechanical Engineering - Skopje, Republic of North
Macedonia. E-Mail<EMAIL_ADDRESS>University of Ljubljana &
Faculty of Information Studies, Novo mesto, Slovenia. E-Mail:
<EMAIL_ADDRESS>
###### Abstract

In this short paper, we introduce a new vertex coloring whose motivation comes
from our series on odd edge-colorings of graphs. A proper vertex coloring
$\varphi$ of a graph $G$ is said to be odd if for each non-isolated vertex
$x\in V(G)$ there exists a color $c$ such that $\varphi^{-1}(c)\cap N(x)$ is
odd-sized. We prove that every simple planar graph admits an odd $9$-coloring,
and conjecture that $5$ colors always suffice.

Keywords: planar graph, neighborhood, proper coloring, odd coloring.

##  1 Introduction

All considered graphs in this paper are simple, finite and undirected. We
follow [3] for all terminology and notation not defined here. A
$k$-(vertex-)coloring of a graph $G$ is an assignment
$\varphi:V(G)\to\\{1,\ldots,k\\}$. A coloring $\varphi$ is said to be proper
if every color class is an independent subset of the vertex set of $G$. A
hypergraph $\mathcal{H}=(V(\mathcal{H}),\mathcal{E}(\mathcal{H}))$ is a
generalization of a graph, its (hyper-)edges are subsets of $V(\mathcal{H})$
of arbitrary positive size. There are various notions of (vertex-)coloring of
hypergraphs, which when restricted to graphs coincide with proper graph
coloring. One such notion was introduced by Even at al. [9] (in a geometric
setting) in connection with frequency assignment problems for cellular
networks, as follows. A coloring of a hypergraph $\mathcal{H}$ is conflict-
free (CF) if for every edge $e\in\mathcal{E}(\mathcal{H})$ there is a color
$c$ that occurs exactly once on the vertices of $e$. The CF chromatic number
of $\mathcal{H}$ is the minimum $k$ for which $\mathcal{H}$ admits a CF
$k$-coloring. For graphs, Cheilaris [5] studied the CF coloring with respect
to neighborhoods, that is, the coloring in which for every non-isolated vertex
$x$ there is a color that occurs exactly once in the (open) neighborhood
$N(x)$, and proved the upper bound $2\sqrt{n}$ for the CF chromatic number of
a graph of order $n$. For more on CF colorings see, e.g., [8, 11, 13, 16, 20].

A similar but considerably less studied notion (concerning a weaker
requirement for the occurrence of a color) was introduced by Cheilaris et al.
[7] as follows. An odd coloring of a hypergraph $\mathcal{H}$ is a coloring
such that for every edge $e\in\mathcal{E}(\mathcal{H})$ there is a color $c$
with an odd number of vertices of $e$ colored by $c$. Particular features of
the same notion (under the name weak-parity coloring) have been considered by
Fabrici and Göring [10] (in regard to face-hypergraphs of planar graphs) and
also by Bunde et al. [4] (in regard to coloring of graphs with respect to
paths, i.e., path-hypergraphs). For various edge colorings of graphs with
parity condition required at the vertices we refer the reader to [2, 6, 12,
14, 15, 17, 18].

In this paper we study certain aspects of odd colorings for graphs with
respect to (open) neighborhoods, that is, the colorings of a graph $G$ such
that for every non-isolated vertex $x$ there is a color that occurs an odd
number of times in the neighborhood $N_{G}(x)$. Our focus is on colorings that
are at the same time proper, and we mainly confine to planar graphs.

Let us denote by $\chi_{o}(G)$ the minimum number of colors in any proper
coloring of a given graph $G$ that is odd with respect to neighborhoods, call
this the odd chromatic number of $G$. Note that the obvious inequality
$\chi(G)\leq\chi_{o}(G)$ may be strict; e.g., $\chi(C_{4})=2$ whereas
$\chi_{o}(C_{4})=4$. Similarly, $\chi(C_{5})=3$ whereas $\chi_{o}(C_{5})=5$.
In fact, the difference $\chi_{o}(G)-\chi(G)$ can acquire arbitrarily large
values. Indeed, let $G$ be obtained from $K_{n}$ $(n\geq 2)$ by subdividing
each edge once. Since $G$ is bipartite, $\chi(G)=2$. On the other hand, it is
readily seen that $\chi_{o}(G)\geq n$. Note in passing another distinction
between the chromatic number and the odd chromatic number. The former graph
parameter is monotonic in regard to the ‘subgraph relation’, that is, if
$H\subseteq G$ then $\chi(H)\leq\chi(G)$. This nice monotonicity feature does
not hold for the odd chromatic number in general. For example, $C_{4}$ is a
subgraph of the kite $K_{4}-e$, but nevertheless we have
$\chi_{o}(C_{4})=4>3=\chi_{o}(K_{4}-e)$.

The Four Color Theorem [1, 19] asserts the tight upper bound $\chi(G)\leq 4$
for the chromatic number of any planar graph $G$. One naturally starts
wondering about an analogous bound for the odd chromatic number of all planar
graphs. Since $\chi_{o}(C_{5})=5$, four colors no longer suffice. It is our
belief that five colors always suffice.

######  Conjecture 1.1.

For every planar graph $G$ it holds that $\chi_{o}(G)\leq 5$.

The bound in Conjecture 1.1 is achieved for infinitely many planar graphs.
Namely, let $\mathcal{F}=\\{G:G$ is a non-trivial connected graph such that
every block of $G$ is isomorphic to $C_{5}\\}$.

######  Proposition 1.2.

If $G\in\mathcal{F}$ then $\chi_{o}(G)=5$.

###### Proof.

Consider a counter-example $G$ with minimum number of blocks, $b(G)$. Since
$G\neq C_{5}$, we have that $b(G)\geq 2$. Let $B$ be an endblock of $G$, and
let $v_{1},v_{2},v_{3},v_{4},v_{5}$ be the vertices of the $5$-cycle $B$ met
on a circular traversing that starts at the unique cut vertex $v_{1}$
contained within $B$. Consider the graph
$G^{\prime}=G-\\{v_{2},v_{3},v_{4},v_{5}\\}$. Since $G^{\prime}\in\mathcal{F}$
and $b(G^{\prime})=b(G)-1$, it holds that $\chi_{o}(G^{\prime})=5$. Take an
odd coloring of $G^{\prime}$ with color set $\\{1,2,3,4,5\\}$ such that
$v_{1}$ is colored by $1$ and the color $4$ has odd number of occurrences in
$N_{G^{\prime}}(v_{1})$. Extend to $V(G)$ by assigning the color $i$ to
$v_{i}$, for $i=2,3,4,5$. This clearly gives an odd $5$-coloring of $G$.
Consequently, since we are supposing $\chi_{o}(G)\neq 5$, there must exist an
odd coloring $c$ of $G$ with color set $\\{1,2,3,4\\}$. Upon permutation of
colors, we may assume that $c(v_{i})=i$ for $1\leq i\leq 4$. Hence, it must be
that $c(v_{5})=2$. Thus, any color which satisfies the odd-condition in
$N_{G}(v_{1})$ has an odd number of occurrences in $N_{G^{\prime}}(v_{1})$ as
well. It follows that the restriction of $c$ to $G^{\prime}$ is an odd
$4$-coloring, contradicting the minimality choice of $G$. ∎

The main purpose of this paper is to provide the first support to Conjecture
1.1 by proving the following.

######  Theorem 1.3.

For every planar graph $G$ it holds that $\chi_{o}(G)\leq 9$.

The rest of the article is organized as follows. In the next section we
provide a proof of Theorem 1.3. And in Section 3 we briefly convey some of our
ideas for possible further work on the topic of proper colorings of graphs
that are odd with respect to neighborhoods.

##  2 Proof of Theorem 1.3

Throughout, we will refer to a coloring of this kind as a nice coloring; that
is, a nice coloring is a (proper) odd coloring which uses at most $9$ colors.
Arguing by contradiction, let $G$ be a counter-example of minimum order
$n=n(G)$. Clearly, $G$ is connected and has $n\geq 10$ vertices. We proceed to
exhibit several structural constraints of $G$.

Claim 1. The minimum degree $\delta(G)$ equals $5$.

Since $G$ is a connected planar simple graph with $n>2$ vertices, the
inequality $\delta(G)\leq 5$ is a consequence of Euler’s formula. Consider a
vertex $v$ of degree $d_{G}(v)=\delta(G)$. If $d_{G}(v)=1$ or $3$, then take a
nice coloring of $G-v$. By forbidding at most six colors at $v$ (namely, at
most three colors used for $v$’s neighbors and at most three additional colors
in regard to oddness concerning the neighborhoods in $G-v$ of these vertices),
the coloring extends to a nice coloring of $G$.

Suppose next that $d_{G}(v)=2$, and say $N_{G}(v)=\\{x,y\\}$. Construct
$G^{\prime}$ by removing $v$ from $G$ plus connecting $x$ and $y$ if they are
not already adjacent. By minimality, $G^{\prime}$ admits a nice coloring $c$.
Say $c(x)=1$ and $c(y)=2$, and let color(s) $1^{\prime}$ and $2^{\prime}$,
respectively, have odd number of occurrences in $N_{G^{\prime}}(x)$ and
$N_{G^{\prime}}(y)$. If there are several possibilities for $1^{\prime}$, then
choose $1^{\prime}\neq 2$; do similarly for $2^{\prime}$ in regard to $1$.
Extend the coloring to $G$ by using for $v$ a color different from
$1,2,1^{\prime},2^{\prime}$. The properness of the coloring is clearly
preserved. As for the weak-oddness concerning neighborhoods, $v$ is fine
because $1\neq 2$. If $1^{\prime}\neq 2$ then $x$ is fine since $1^{\prime}$
remains to be odd on $N_{G}(x)$. Contrarily, if $1^{\prime}=2$ then $c(v)$ is
odd on $N_{G}(x)$. Similarly, the vertex $y$ is also fine.

Finally, suppose $d_{G}(v)=4$ and let $w\in N_{G}(v)$. Remove $v$ and connect
$w$ by an edge to every other non-adjacent neighbor of $v$. The obtained graph
$G^{\prime\prime}$ is simple and planar. Indeed, it can be equivalently
obtained from $G$ by contracting the edge $vw$ (if parallel edges arise
through possible mutual neighbors of $v$ and $w$, then for each such adjacency
a single edge is kept and its copies are deleted). Notice that under any nice
coloring of $G^{\prime\prime}$, the color of $w$ occurs exactly once in
$N_{G}(v)$. Therefore, any such coloring extends to a nice coloring of $G$ by
forbidding at most eight colors at $v$.

We conclude that $d_{G}(v)=5$.∎

We refer to any vertex of degree $d$ as a $d$-vertex. Similarly, a vertex of
degree at least $d$ is a $d^{+}$-vertex. Analogous terminology applies to
faces in regard to a planar embedding of $G$.

Claim 2. If $v$ is a $5$-vertex of $G$, then it has at most one neighbor of
odd degree.

Suppose each of two vertices $u,w\in N_{G}(v)$ has an odd degree in $G$.
Consider a nice coloring $c$ of $G-v$. We intend to extend $c$ to $G$. Since
$N_{G}(u)$ and $N_{G}(w)$ are odd-sized, no color is blocked at $v$ in regard
to oddness in the neighborhoods of $u$ and $w$. Moreover, as $N_{G}(v)$ is
odd-sized as well, the oddness of a color in this particular neighborhood is
guaranteed. Therefore, by forbidding at most eight colors at $v$ (all of
$c(N_{G}(v))$ and at most $3$ additional colors concerning oddness in
neighborhoods of the vertices forming $N_{G}(v)\backslash\\{u,w\\}$), the
coloring $c$ extends to a nice coloring of $G$.∎

Since the graph $G$ is connected, for an arbitrary planar embedding Euler’s
formula gives

$|V(G)|-|E(G)|+|F(G)|=2\,,$

where $F(G)$ is the set of faces. Our proof is based on the discharging
technique. We assign initial charges to the vertices and faces according to
the left-hand side of the following equality (which immediately follows from
Euler’s formula):

$\sum_{v\in V(G)}(d(v)-6)+\sum_{f\in F(G)}(2d(f)-6)=-12\,.$

Thus, any vertex $v$ receives charge $d(v)-6$, and any face $f$ obtains charge
$2d(f)-6$. As $G$ is simple, for every face $f$ it holds that $d(f)\geq 3$,
implying that its initial charge is non-negative. By Claim 1, the only
vertices that have negative initial charge are the $5$-vertices of $G$ (each
is assigned with charge $-1$).

Claim 3. Any $d$-face $f\in F(G)$ is incident with at most
$\left\lfloor\frac{2d}{3}\right\rfloor$ $5$-vertices.

By Claim 2, on a facial walk of $f$ no three consecutive vertices are of
degree $5$. From this, the stated upper bound for the number of $5$-vertices
incident with $f$ follows immediately.∎

We use the following discharging rules (cf. Figure 1):

  * (R1)

Every $4^{+}$-face $f$ sends charge $1$ to any incident $5$-vertex $v$.

  * (R2)

Every $8^{+}$-vertex $u$ sends charge to any adjacent $5$-vertex $v$ if both
faces incident with the edge $uv$ are triangles, as follows: if one of these
triangles has another $5$-vertex (besides $v$), then the sent charge equals
$\frac{1}{3}$; otherwise, the sent charge equals $\frac{1}{2}$. (In view of
Claim 2, it cannot be that both these triangles have a $5$-vertex $\neq v$.)

  * (R3)

Every $4^{+}$-face $f$ sends through every incident edge $uw$ with
$d(u)=d(w)=6$ charge $\frac{1}{2}$ to a $5$-vertex $v$ if $uvw$ is a
triangular face and $f$ is not a $4$-face incident with two $5$-vertices.

Figure 1: In (R2), the numbers standing in brackets beside vertices or faces
indicate their degrees. In (R3), $f$ is not a $4$-face incident with two
$5$-vertices and $uvw$ is an adjacent triangular face.

Claim 4. No $8^{+}$-vertex becomes negatively charged by applying $(R2)$.

Suppose there is a $d$-vertex $u$ with $d\geq 8$ that becomes negatively
charged by applying Rule 2. Recall that its initial charge was $d-6$. Consider
a circular ordering of $N_{G}(u)$ in regard to the embedding of $G$. Note that
no three consecutive neighbors $v_{i},v_{i+1},v_{i+2}\in N_{G}(u)$ have
received charge from $u$ during the discharging process, for otherwise
$v_{i+1}$ contradicts Claim 2. Therefore, $u$ gave charge to at most
$\left\lfloor\frac{2d}{3}\right\rfloor$ of its neighbors, and at most
$\frac{1}{2}$ of charge per neighbor. Consequently,
$d-6<\frac{2d}{3}\cdot\frac{1}{2}$. Equivalently, $d<9$. So $u$ is an
$8$-vertex. Moreover, since we are supposing that it is negatively charged
after applying Rule 2, the vertex $v$ gave charge to precisely five
$5$-vertices. However, then it is easily seen that the initial charge $2$ of
$v$ is reduced by at most
$\frac{11}{6}=\frac{1}{3}+\frac{1}{3}+\frac{1}{3}+\frac{1}{3}+\frac{1}{2}$, a
contradiction.∎

Claim 5. No $4^{+}$-face becomes negatively charged by applying $(R1)$ or
$(R3)$.

Suppose there is a $d$-face $f$ that becomes negatively charged by applying
Rules 1 or 3. Recall that its initial charge was $2d-6$. For the purposes of
this proof, it is useful to think of the charge sent by $f$ according to Rule
3 as follows. Consider any maximal sequence of ‘consecutive’ triangular faces
that are adjacent to $f$, and split the sequence into $2$-tuples and a
possible $1$-tuple. For every such $2$-tuple of triangular faces, the total
charge $1=\frac{1}{2}+\frac{1}{2}$ first goes to their common $6$-vertex, and
only afterwards splits evenly and reaches the targeted $5$-vertices (possibly
the same). And for every such $1$-tuple the charge $\frac{1}{2}$ coming from
$f$ to this face first splits evenly and goes to the pair of $6$-vertices
shared with $f$, and only afterwards reaches the targeted $5$-vertex.

With this perspective in mind, consider a facial walk of $f$ and notice that
during the discharging it gives away to each incident vertex charge of either
$0,\frac{1}{4}$, or $1$; moreover, no three consecutive vertices receive from
$f$ charge $1$ (according to Claim 2). Hence, on at most
$\left\lfloor\frac{2d}{3}\right\rfloor$ occasions $f$ gives charge $1$, and on
the other $\left\lfloor\frac{d+1}{3}\right\rfloor$ occasions $f$ gives charge
at most $\frac{1}{4}$. Consequently, $2d-6<\frac{2d}{3}+\frac{d+1}{12}$.
Equivalently, $d<\frac{73}{15}$. So $f$ is a $4$-face. However, it is easily
seen that a $4$-face gives away at most $2$ of its initial charge (which also
equals $2$), a contradiction. ∎

Since the total charge remains negative (it equals $-12$), from Claims 4 and 5
it follows that there is a $5$-vertex $v$ which remains negatively charged
even after applying the discharging rules. By (R1) and (R2), we have the
following.

Claim 6. The $5$-vertex $v$ has only $3$-faces around it, and it is a neighbor
of at most two $8^{+}$-vertices. Moreover, if $v$ neighbors exactly two
$8^{+}$-vertices, then these three vertices have another $5$-vertex as a
common neighbor.

Let $v_{1},v_{2},v_{3},v_{4},v_{5}$ be the neighbors of $v$ in a circular
order regarding the considered plane embedding, i.e., such that
$vv_{1}v_{2},vv_{2}v_{3},vv_{3}v_{4},vv_{4}v_{5},vv_{5}v_{1}$ are the five
$3$-faces incident with $v$.

Claim 7. For some $j=1,2,\ldots,5$, the vertices $v_{j},v_{j+2}$ are not
adjacent and their only common neighbors are $v,v_{j+1}$.

Arguing by contradiction, suppose that every pair of vertices $v_{j},v_{j+2}$
are either adjacent or have a common neighbor $\neq v,v_{j+1}$. This readily
implies the existence of a vertex $x\neq v$ that is adjacent to all five
vertices $v_{1},v_{2},v_{3},v_{4},v_{5}$. Now take a nice coloring $c$ of
$G-v$, and let $s=|c(N_{G}(v))|$. In view of the $5$-cycle
$v_{1}v_{2}v_{3}v_{4}v_{5}$, it holds that $s\in\\{3,4,5\\}$. In case $s=3$,
the coloring $c$ extends to a nice coloring of $G$ since at most $8$ colors
are forbidden at $v$. These are the three colors used on $N_{G}(v)$ and at
most five additional colors in regard to ‘oddness’ in $N_{G-v}(v_{i})$ for
$i=1,2,\ldots,5$. Hence $s\in\\{4,5\\}$, and from this we are able to further
deduce that there are precisely $s$ vertices $v_{i}(i=1,2,\ldots,5)$ such that
$c(v_{i-1})\neq c(v_{i+1})$.

Unless the coloring $c$ extends to $G$, each of the nine available colors is
blocked at the vertex $v$, either due to properness or to ‘oddness’.
Consequently, there are at least $(9-s)$ vertices among the $v_{i}$’s each of
which blocks at $v$ a separate color $\neq
c(v_{1}),c(v_{2}),c(v_{3}),c(v_{4}),c(v_{5})$ in regard to ‘oddness’ in its
neighborhood within $G-v$. Clearly, any such $v_{i}$ is of even degree in $G$
and any color from $\\{c(v_{i-1}),c(v_{i+1})\\}$ appears an even number of
times in $N_{G-v}(v_{i})$. Moreover, for at least four such vertices $v_{i}$,
say $v_{1},v_{2},v_{3},v_{4}$, it also holds that $c(v_{i-1})\neq c(v_{i+1})$.
Noting that the color $c(x)$ occurs in every of the four neighborhoods
$N_{G-v}(v_{i})$ for $i=1,\ldots,4$, it follows that $c(x)$ has an odd number
of appearances in such a neighborhood for at most one vertex $v_{i}$.
Therefore, at least three $v_{i}$’s are of degree $\geq 2+2+2+1=7$ in $G-v$.
(Namely, each of the colors $c(v_{i-1}),c(v_{i+1}),c(x)$ yields a summand of
$2$, and the summand of $1$ refers to the color blocked by $v_{i}$ due to
‘oddness’ in $N_{G-v}(v_{i})$). However, this yields at least three
$8^{+}$-neighbors of $v$ in $G$, contradicting Claim 6.∎

Let $v_{j},v_{j+2}$ fulfil Claim 7. Consider the graph
$(G-v)/\\{v_{j},v_{j+2}\\}$ obtained from $G-v$ by identifying $v_{j}$ and
$v_{j+2}$, and then deleting one of the arising two parallel edges (between
the new vertex $\\{v_{j},v_{j+2}\\}$ and the vertex $v_{j+1}$). Take a nice
coloring of $(G-v)/\\{v_{j},v_{j+2}\\}$, and look into the inherited coloring
$c$ of $G-v$.

Claim 8. All $v_{i}$’s are of even degree in $G$, and the coloring $c$ is
nice.

Notice that besides the odd-condition at $v_{j+1}$, the coloring $c$ is nice
on $G-v$. If $d_{G}(v_{j+1})$ is odd, then when adding $v$ to $G-v$ we do not
need to care about odd-condition at $v_{j+1}$, as it will automatically hold.
But then we need to avoid only $8$ colors when coloring $v$, which is doable,
a contradiction. Hence $d_{G}(v_{j+1})$ is even. Consequently, $c$ is a nice
coloring of $G-v$ (as $d_{G-v}(v_{j+1})$ is odd and the rest of the conditions
are fine). Since $c$ does not extend to a nice coloring of $G$, by reasoning
in the same manner as at the beginning of the proof of Claim 7, we are able to
conclude that $|c(N_{G}(v))|\geq 4$. On the other hand, by the construction of
$c$ we clearly have $|c(N_{G}(v))|<5$. So it must be that exactly four colors
appear in $N_{G}(v)$. Moreover, as $c$ is non-extendable, each of the vertices
$v_{1},v_{2},v_{3},v_{4},v_{5}$ blocks at $v$ a separate color $\notin
c(N_{G}(v))$ in regard to already (and uniquely) fulfilled ‘oddness’ in its
neighborhood in $G-v$. However, this readily implies that each $v_{i}$ is of
even degree in $G$.∎

Figure 2: Local color distribution, guaranteed ‘free hanging’ colors and the
faces adjacent with the local triangulation around $v$.

The proof of Claim 8 certifies that, upon permuting colors, the following
color distribution occurs under $c$: the colors $1,2,1,3,4$ are used on
$v_{1},v_{2},v_{3},v_{4},v_{5}$, respectively, and each of the colors
$5,6,7,8,9$ happens to be the only color with an odd number of appearances on
a separate neighborhood $N_{G-v}(v_{i})$ (cf. Figure 2(a)). Moreover, as
colors $5,6,7,8,9$ are ‘exclusive’ in regard to ‘oddness’ on
$N_{G-v}(v_{1}),N_{G-v}(v_{2}),N_{G-v}(v_{3}),N_{G-v}(v_{4}),N_{G-v}(v_{5})$,
respectively, any of the colors $1,2,3,4$ has an even (possibly $0$) number of
occurrences in each set $N_{G-v}(v_{i})$ $(i=1,\ldots,5)$. Consequently, the
situation depicted in Figure 2(b) is present, that is, at four of the
$v_{i}$’s (namely, $v_{1},v_{2},v_{4},v_{5}$) we are guaranteed two more ‘free
hanging’ colors per vertex. Let $f_{i}$ $(i=1,\ldots,5)$ be the face incident
with $v_{i}v_{i+1}$ but not with $v$ (cf. Figure 2(b)). Note that
$f_{1},f_{2},f_{3},f_{4},f_{5}$ need not be pairwise distinct. We say that
$f_{i}$ is convenient if it is a $4^{+}$-face and $v_{i},v_{i+1}$ are
$6$-vertices whose only common neighbor is $v$.

Claim 9. If all of $v_{1},v_{2},v_{3},v_{4},v_{5}$ are $6$-vertices in $G$,
then at least two members of the list $f_{1},f_{2},f_{3},f_{4},f_{5}$ are
convenient.

It suffices to observe the following: if a given $f_{k}$ is a $3$-face, then
the vertices $v_{k}$ and $v_{k+1}$ must share a free hanging color. Since all
the $v_{i}$’s are $6$-vertices, it follows that $v_{3}$ and $v_{4}$ do not
have a common free hanging color. Consequently, $f_{3}$ is convenient. Quite
similarly, $f_{5}$ is convenient.∎

Following the same line of reasoning, we also conclude the following:

Claim 10. If precisely one of $v_{1},v_{2},v_{3},v_{4},v_{5}$ is an
$8^{+}$-vertex in $G$, then some $f_{i}$ is convenient.

Indeed, we may assume that neither $v_{1}$ nor $v_{5}$ is the $8^{+}$-neighbor
of $v$. Then $v_{1},v_{5}$ are $6$-vertices without a common free hanging
color. Consequently, $f_{5}$ is convenient.∎

Our next (and final) claim assures that every convenient face $f_{i}$ sends
charge $\frac{1}{2}$ to $v$, in accordance with (R3).

Claim 11. No convenient face is a quadrangle $ABCD$ where $A,B$ are
$5$-vertices and $C,D$ are $6$-vertices.

Arguing by contradiction, we suppose that the situation depicted in Figure
3(a) is present. Without loss of generality, we may assume that $B$ and $D$
are non-adjacent and $N_{G}(B)\cap N_{G}(D)=\\{A,C\\}$. Indeed, if each of the
pairs of vertices $A,C$ and $B,D$ are either adjacent or share a common
neighbor outside the set $\\{A,B,C,D\\}$, then by planarity, the situation
depicted in Figure 3(b) occurs. However, then $C$ and $D$ have a common
neighbor $\neq v$, which contradicts that the considered face is convenient.

Figure 3: A convenient face next to the $5$-vertex $v$ that happens to be a
quadrangle $ABCD$, where $A,B$ are $5$-vertices and $C,D$ are $6$-vertices.

With our assumption for the pair $B,D$, we look at the graph
$G^{\prime}=(G-\\{v,A,C\\})/\\{B,D\\}$, that is, $G^{\prime}$ is obtained from
$G-\\{v,A,C\\}$ by identifying $B$ and $D$. Since $G^{\prime}$ is planar and
smaller than $G$, it admits a nice coloring. Consider the inherited partial
coloring $c$ of $G$. Note that vertices $B$ and $D$ are colored the same under
$c$, and the only uncolored vertices are $v,A$ and $C$. We extend $c$ to a
nice coloring of $G$ as follows.

First we color $v$, and for the time being we don’t care about preserving
oddness in $N_{G-A-C}(D)$. Apart from the color $c(D)$ and possibly a second
color in regard to unique oddness in $N_{G-\\{v,A\\}}(C)$, at most $6=3\cdot
2$ more colors are forbidden at $v$ (by its three neighbors $\neq C,D$ and
oddness in their respective neighborhoods within $G-\\{v,A,C\\}$). Thus there
is a color which is available for $v$.

Next we color $C$. There are at most $8=1+1+3\cdot 2$ colors forbidden at $C$
(namely, the color $c(B)=c(D)$, the color $c(v)$ and possibly six more colors
concerning the other three neighbors of $C$ and oddness in their respective
neighborhoods within $G-A$). So there is a color available for $C$. Once $C$
is assigned with an available color, note that there is a color with an odd
number of appearances in $N_{G-A}(D)$ (because $d_{G-A}(D)=5$).

Finally, we color $A$. Since this is a $5$-vertex, it suffices to choose a
color for $A$ so that the properness of the coloring and the oddness in
$N_{G-A}(D)$ are preserved. As $B$ and $D$ are colored the same, and $B$ is a
$5$-vertex, the number of forbidden colors at $A$ is at most $8=1+1+3\cdot 2$
(the color $c(B)=c(D)$, possibly a second color in regard to unique oddness in
$N_{G-A}(D)$, and six more colors concerning the other three neighbors of $A$
and oddness in their respective neighborhoods within $G-A$). We conclude that
$c$ indeed extends to a nice coloring of $G$, a contradiction.∎

From Claims 9-11 it follows that the vertex $v$ receives charge at least $1$
during the discharging process, hence it cannot remain to be negatively
charged. This contradiction concludes our proof.

##  3 Further work

By Proposition 1.2, there exist plenty of planar graphs with girth $5$ that
require five colors for an odd coloring. We are tempted to propose the
following.

######  Conjecture 3.1.

Every planar graph $G$ of girth at least $6$ has $\chi_{o}(G)\leq 4$.

If true, Conjecture 3.1 would imply the Four Color Theorem (4CT). Indeed, say
$G$ is an arbitrary planar graph. Subdivide every edge of $G$ once, i.e.,
consider the complete subdivision $S(G)$. As girth $g(S(G))\geq 6$, take an
odd $4$-coloring $c$ of $S(G)$. The restriction of $c$ to $V(G)$ is a proper
$4$-coloring of $G$.

Although the problem of odd coloring is intriguing already in the class of
plane graphs, the concept can be naturally studied also for graphs embedded in
higher surfaces. For a surface $\Sigma$, we define the odd chromatic number of
$\Sigma$,

$\chi_{o}(\Sigma)=\max_{G\hookrightarrow\Sigma}\chi_{o}(G),$

as the maximum of $\chi_{o}(G)$ over all graphs $G$ embedded into $\Sigma$.
Conjecture 1.1 and Proposition 1.2 combined purport that $\chi_{o}(S_{0})=5$,
where $S_{0}$ is the sphere. It would be interesting to have a similar
characterization to the Heawood number for other surfaces of higher genus.

######  Problem 3.2.

Determine $\chi_{o}(\Sigma)$ for surfaces $\Sigma$ of higher genus.

Possibly the odd chromatic number of higher surfaces coincides with the
corresponding Heawood number.

Acknowledgements. This work is partially supported by ARRS Program P1-0383 and
ARRS Project J1-3002.

## References

  * [1] K. Appel and W. Haken, The solution of the Four-Color Map Problem, Sci. Amer. $\mathbf{237}$, (1977) 108–121.
  * [2] R. Atanasov, M. Petruševski, R. Škrekovski, Odd edge-colorability of subcubic graphs, Ars Math. Contemp. $\mathbf{10}$ (2016), 359–370.
  * [3] J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Springer, New York $\mathbf{244}$ (2008).
  * [4] D. P. Bunde, K. Milans, D. B. West and H. Wu, Parity and strong parity edge-coloring of graphs, Congr. Numer. $\mathbf{187}$ (2007) 193–213.
  * [5] P. Cheilaris, Conflict-Free Coloring, PhD Thesis (City University of New York, 2009).
  * [6] M. Petruševski, A note on weak odd edge-colorings of graphs, Adv. Math. Sci. Journal $\mathbf{4}(1)$ (2015) 7–10.
  * [7] P. Cheilaris, B. Keszegh and D. Pálvölgyi, Unique-maximum and conflict-free colouring for hypergraphs and tree graphs, SIAM J. Discrete Math $\mathbf{27}$ (2013) 1775–1787.
  * [8] P. Cheilaris and G. Tóth, Graph unique-maximum and conflict-free coloring, J. Discrete Algorithms $\mathbf{9}$ (2011) 241–251.
  * [9] G. Even, Z. Lotker, D. Ron and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM J. Comput. $\mathbf{33}$ (2003) 94–136.
  * [10] I. Fabrici and F. Göring, Unique-maximum coloring of plane graphs, Dicussiones Mathematicae Graph Theory $\mathbf{36}$ (2016) 95–102.
  * [11] R. Glebov, T. Szabó and G. Tardos, Conflict-free colorings of graphs, Combin. Probab. Comput. $\mathbf{23(3)}$ (2014) 434–448.
  * [12] M. Kano, G. Y. Katona, K. Varga, Decomposition of a graph into two disjoint odd subgraphs, Graphs and Combin. $\mathbf{34}(6)$ (2018) 1581–1588.
  * [13] A. V. Kostochka, M. Kumbhat and T. Łuczak, Conflict-free colorings of uniform hypergraphs with few edges, Combin. Probab. Comput. $\mathbf{21}$ (2012) 611–622.
  * [14] B. Lužar, M. Petruševski, R. Škrekovski, Odd edge coloring of graphs, Ars Math. Contemp. $\mathbf{9}$ (2015) 277–287.
  * [15] B. Lužar, M. Petruševski, R. Škrekovski, On vertex-parity edge-colorings, J. Combin. Optim. $\mathbf{35}(2)$ (2018) 373–388.
  * [16] J. Pach and G. Tardos, Conflict-free colorings of graphs and hypergraphs, Combin. Probab. Comput. $\mathbf{18}$ (2009) 819–834.
  * [17] M. Petruševski, Odd $4$-edge-colorability of graphs, J. Graph Theory $\mathbf{87}(4)$ (2018) 460–474.
  * [18] M. Petruševski, R. Škrekovski, Odd decompositions and coverings of graphs, European J. Combin. $\mathbf{91}$ (2021) 103225.
  * [19] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, A New Proof of the Four Colour Theorem, Electron. Res. Announc. Amer. Math. Soc. 2 (1996) 17–25.
  * [20] S. Smorodinsky, Conflict-free coloring and its applications, In: I. Bárány, K. J. Böröczky, G. F. , Tóth and J. Pach (eds) Geometry-Intuitive, Discrete and Convex. Bolyai Society Mathematical Studies, $\mathbf{24}$ Springer, Berlin, Heidelberg (2013).


2

# Silicon photonic-electronic neural network for fibre nonlinearity
compensation

Chaoran Huang1,4 Shinsuke Fujisawa2 Thomas Ferreira de Lima1 Alexander N.
Tait1 Eric C. Blow1 Yue Tian2 Simon Bilodeau1 Aashu Jha1 Fatih Yaman2 Hsuan-
Tung Peng1 Hussam G. Batshon2 Bhavin J. Shastri1,3 Yoshihisa Inada5 Ting Wang2
and Paul R. Prucnal1

###### Abstract

In optical communication systems, fibre nonlinearity is the major obstacle in
increasing the transmission capacity. Typically, digital signal processing
techniques and hardware are used to deal with optical communication signals,
but increasing speed and computational complexity create challenges for such
approaches. Highly parallel, ultrafast neural networks using photonic devices
have the potential to ease the requirements placed on the digital signal
processing circuits by processing the optical signals in the analogue domain.
Here we report a silicon photonic–electronic neural network for solving fibre
nonlinearity compensation of submarine optical fibre transmission systems. Our
approach uses a photonic neural network based on wavelength-division
multiplexing built on a CMOS-compatible silicon photonic platform. We show
that the platform can be used to compensate optical fibre nonlinearities and
improve the signal quality (Q)-factor in a 10,080 km submarine fibre
communication system. The Q-factor improvement is comparable to that of a
software-based neural network implemented on a 32-bit graphic processing unit
assisted workstation. Our reconfigurable photonic-electronic integrated neural
network promises to address pressing challenges in high-speed intelligent
signal processing.

Department of Electrical Engineering, Princeton University, Princeton, NJ
08542, USA

NEC Laboratories America, Inc., 4 Independence Way, Princeton, NJ 08540, USA

Department of Physics, Engineering Physics and Astronomy, Queen’s University,
Kingston, ON K7L 3N6, Canada

Department of Electronic Engineering, the Chinese University of Hong Kong

Submarine Network Division, NEC Corporation, 108-8001 Tokyo, Japan

Artificial Neural networks (ANNs) can learn from examples and perform tasks
without being programmed with explicit rules, providing a powerful tool to
solve problems in many disciplines[1, 2]. Current applications with ANNs, such
as image and voice recognition, are typically performed locally at kHz speed
or on cloud servers – which high latency – using conventional computers. But
many emerging ANN applications demand gigahertz bandwidth, real-time
operations, and low power consumption [3, 4, 5]. ANNs have, for example, been
applied in optical fiber communications where they can learn optical fiber
transmission models from received signals without prior knowledge of
transmission conditions[6, 7]. The ANNs can be used to compensate fibre
nonlinearity impairment, the major limiting effect of increasing capacities in
long-distance transmission systems[8]. Compared to conventional fiber
nonlinearity compensation approaches, such as digital backpropagation
(DBP)[9], an ANN can achieve comparable signal quality improvement with lower
computational complexity[10]. However, such ANNs have only been implemented in
software, and thus the data processing was not in real-time[8].

In optical communication systems, the signal bandwidth is tens of gigahertz,
and the signals must be processed in real-time. Bounded by the clock rate of
digital electronic hardware (typically application-specific integrated
circuits; ASICs), processing such high-speed signals requires massive
parallelisation. As a result, the circuit complexity scales with the
computational complexity of the digital signal processing (DSP) algorithms. At
the same time, the signal processing unit needs to be built into a pluggable
transceiver module and its power consumption needs to fit into the power
envelope of network switches, typically tens of watts including both optical
and electrical modules[11]. The challenges in high circuit complexity with a
tight power budget have prohibited implementing high-performance, but
computationally intensive, ANN based algorithms[12]. And efforts have been
focused on developing algorithms that lead to a compromise between
transmission link performance and DSP complexity.

An alternative approach is to explore hardware that intrinsically offers both
high bandwidth and low power consumption in ANN applications, and photonic
neural networks (PNNs) could potentially provide such capabilites[13, 14].
PNNs aim to leverage high-speed optical devices to mimic the essential
computing primitives (neurons and synapses) and connect them into a neural
network with highly parallel and dense optical interconnects. As a result,
PNNs are potentially capable of supporting real-time ANN implementations with
tens of gigahertz bandwidth in a single pipeline. The approach could thus
address DSP related hardware constraints, such as analogue-to-digital
performance and computational complexity, and help cope with the increasing
data transmission capacity.

PNNs have previously been demonstrated on various platforms, including free-
space[15, 16], optical fibres[17, 18, 19], diffractive optics[20, 21], and
integrated photonic circuits[22, 23, 24, 25, 26]. The past decade has seen a
rapid development of silicon photonics, driven by the rising demands in
optical communication capacities. These advances have provided fast and
efficient optical modulators and detectors for optical communications, and
have led to high-density integrated optoelectronic devices and interconnects
that can perform scalable information processing and computing tasks. However,
many of the integrated devices demonstrated so far have focused on building
analogue interconnects for multiply-accumulate (MAC) computations for linear
matrix-vector multiplication operations [20, 24]with nonlinear activation
functions (neurons) implemented offline (in the digital domain) or with slow
optics. Alternatively, there have been demonstrations of neurons with
reconfigurable activation functions but without co-integrated linear
operations [27, 28]. The lack of a fully integrated neuron with network
compatibility prevents PNNs from performing real-time processing with
gigahertz bandwidth, which is vital for many signal processing applications.

In this Article, we report an integrated silicon PNN system that integrates a
full NN model with neurons and synapses, and demonstrate for the first time
that a PNN is capable of simultaneously providing accurate weighting,
summation, and biased nonlinearity (i.e., neurons) for high-speed signals.
Integrating fast photonic neurons on chip is a critical step toward achieving
high-speed NNs for real-time intelligent signal processing. Our PNN is a
reconfigurable photonic-electronic integrated circuit and is programmable to
perform different tasks. We demonstrate a unique application of PNN for fibre
nonlinearity compensation (NLC) in submarine optical fibre communications
transmission systems. ANN parameters trained on a computer in advance are
accurately uploaded to our photonic chip, which can then be used to perform
inference acceleration tasks. Our platform can predict optical fibre
nonlinearities and improve the signal quality (Q)-factor in a 10,080 km
submarine fibre communication system. The Q-factor improvement is comparable
to the results obtained from a software-based neural network running on a
32-bit graphics processing unit (GPU)-assisted workstation. The results
illustrate that our photonic analogue computing circuit can preserve signal
integrity, while offering potential speed and gigahertz bandwidth advantages
without sacrificing accuracy. The NLC application could also be generalized as
a regression problem, and extended to solve different real-world application
problems currently unreachable with conventional computing technologies.

##  1 Neural network model for fiber nonlinearity compensation

We investigate a 10,080 km submarine optical transmission system carrying a
single channel Gbaud polarization-multiplexed (PM)-16 quadrature amplitude
modulation (QAM) signal. While recent demonstrations have shown the
transmission capacities have approached the Shannon limit in the linear regime
of optical fibers, the nonlinear impairment remains the major limiting effect
in long-distance transmission systems [29]. The evolution of the signals in
the fiber link is described by the Nonlinear Schrödinger Equation:

$\frac{\partial{u_{x/y}(t,z)}}{\partial{z}}+\underbrace{i\frac{\beta_{2}}{2}\frac{\partial^{2}{u_{x/y}(t,z)}}{\partial^{2}{t}}}_{\text{\footnotesize
dispersion}}=\underbrace{i\frac{8}{9}\gamma[\mid u_{x/y}(t,z)\mid^{2}+\mid
u_{y/x}(t,z)\mid^{2}]\mid u_{x/y}(t,z)}_{\text{\footnotesize Kerr
nonlinearity}},$ (1)

where $u_{x/y}(t,z)$ is the optical field at the x and y polarizations,
respectively, $\beta_{2}$ is the group velocity dispersion governing the
linear impairment, and $\gamma$ is the Kerr nonlinear coefficient governing
the nonlinear impairment in the fiber transmission systems. Although state-of-
the-art DSP can overcome linear impairments, nonlinear impairments remain
difficult to overcome due to the difficulty in applying computationally
expensive nonlinear compensation algorithms using ASICs. The nonlinearity
impairment can be treated as the the perturbation due to the nonlinear
effects, _i.e._ , $u_{x/y}(t,z)=u_{0,x/y}(t,z)+\Delta u_{x/y}(t,z)$, where
$u_{0,x/y}(t,z)$ is the solution of linear propagation and $\Delta
u_{x/y}(t,z)$ is the nonlinear perturbation. The idea of NLC is to build up a
model of the nonlinear perturbation $\Delta u_{x/y}(t,z)$ with the abundance
of transmission data using a NN, and remove the distortion by subtracting the
perturbation from the received optical field $u_{x/y}(t,z)$.

Here we first consider how fiber nonlinearities impair the signal on the
x-polarization as an example. We define a term triplet as
$T=H_{n}H_{m+n}^{*}H_{m}+V_{n}V_{m+n}^{*}H_{m}$, where $H$ and $V$ are the
received symbol sequences at the x- and y- polarizations, respectively. $m$
and $n$ are symbol indices with respect to the symbols of interest $H_{0}$.
Triplet $T$ represents the nonlinearities added on the X-polarization signals,
which is caused by the nonlinear interactions among the signals at the same
polarization (i.e., $H_{n}H_{m+n}^{*}H_{m}$) and orthogonal polarizations
($V_{n}V_{m+n}^{*}H_{m}$), as shown in Eq. 2. Triplet $T$ corresponds to the
nonlinear terms on the right side of Eq. 1. Then, the nonlinear perturbation
can be approximated by a combination of triplets $T$ [30]:

$\begin{split}\Delta u_{x/y}(0,z)=\sum
P_{0}^{3/2}(\underbrace{H_{n}H_{m+n}^{*}H_{m}}_{\begin{subarray}{c}\text{\footnotesize
intra-polarization}\\\ \text{\footnotesize
nonlinearity}\end{subarray}}+\underbrace{V_{n}V_{m+n}^{*}H_{m})}_{\begin{subarray}{c}\text{\footnotesize
inter-polarization}\\\ \text{\footnotesize
nonlinearity}\end{subarray}}C_{m,n}\end{split}$ (2)

where $P_{0}$ is the launch power, $C_{m,n}$ are the nonlinear perturbation
coefficients.

1.

Figure 1:  (a) (left) Neural network (NN) model for fiber nonlinearity
compensation (NLC). The NN has an input layer with nonlinear triplets, 2
hidden layers with of 2 and 8 neurons in each layer, and an output layer with
2 output nodes corresponding to the real and imaginary parts of the estimated
nonlinearity on one polarization, and (right) PNN implementation of the second
hidden layer of the NN model based on weight-and-broadcast architecture[31,
22]. Red (blue) arcs are n-doped (p-doped) regions. (b) A false-color confocal
micrograph of the PNN device. (c) Chip packaging and optical coupling setup.
(d) A detailed circuit diagram of a photonic neuron.

Fig. 1(a) shows the NN model for NLC. The NN is a fully connected feed-forward
network consisting of an input layer with 892 triplets, two hidden layers with
2 and 8 neurons, respectively, and an output layer. The model is trained using
the signal on either x or y polarization only, but the trained parameters can
be applied to both polarizations. Here, we choose polarization x as an
example. The inputs of the NN are the triplets $T$ for the x-polarization
signal [8]. The two outputs of the NN are the real and imaginary components of
the estimated nonlinearity $\hat{H}_{k,NL}$ at the k-th symbol. The recovered
symbol $\hat{H}_{k}$ is obtained by subtracting $\hat{H}_{k,~{}NL}$ from the
received symbol $H_{k}$, i.e. $\hat{H}_{k}=H_{k}-\hat{H}_{k,~{}NL}$. The NN is
trained by searching for the tensor parameters that minimize the mean squared
error (MSE) between the $\hat{H}_{k}$ and the transmitted symbol $A_{x,k}$.
After training, the NN can execute the inference task of estimating the
optical nonlinearity of every incoming symbol. The NN is much simpler than
those used for many other applications (e.g. image processing). Nevertheless,
high-speed communications signals require fast operating speed, posing many
challenges to today’s digital electronic hardware. For example, to process 32
Gbaud PM-16QAM signals, NN hardware must have a throughput of approximately
232.4 TOPS. A typical NN accelerator, Tensor Processing Unit (TPU), offers a
peak operation throughput of 92 TOPS[32]. As a result, the need for evaluating
NN models for optical communication signals necessitates the development of
new hardware.

##  2 Photonic hardware implementation

The NN model are implemented using a PNN with WDM-based broadcast-and-weight
architecture, as shown in the yellow region of Fig. 1(a). The information of
each neuron is encoded on a unique wavelength of light and multiplexed on a
single optical waveguide. In the feed-forward network, the neuron output in
the previous layer is first broadcast to all neurons in the next layer by a
power splitter, then weighted in parallel with an array of microring
resonators (MRR) in an MRR weight bank configuration, and finally summed by a
balanced photodetector. Weights are applied by the MRR banks by tuning the
partial transmission of signals. The weighted signals are detected, generating
photocurrent to drive the optical modulators in the second layer. This process
involves a nonlinear conversion of optical power into electrical current and
back into the signal pathway, and hence serves as the nonlinear activation
function (i.e. neuron) in the PNN[27].

The signal pathways in the PNN can be fabricated using standard silicon
photonic platforms, which provides critical aspects of feasibility and
economies of scaling to the full NN model for NLC. Several notable studies
have demonstrated the integration of thousands of photonic components on a
single silicon photonic chip[33, 34]. For the first time, we show that the PNN
can provide accurate and fast weighting, summation, and biased nonlinearity
for high-speed signals, and we experimentally implement the second hidden
layer of the NN model using a 4$\times$2 PNN, as shown in Fig. 1(b). In
particular, integrating fast photonic neurons on chip is a critical move
toward achieving high-speed NNs for real-time applications such as NLC. In the
Discussion section, we discuss that the PNN can be robustly scaled to
incorporate the full NN model.

The PNN device comprises two arrays of MRR weight banks connected to two
photonic neurons. The second hidden layer consists of 8 neurons, and each
neuron is connected to the two neurons in the first hidden layer by a
2$\times$2 weight matrix. To emulate the second hidden layer with the
4$\times$2 PNN circuit, we feed the two first-layer outputs to the PNN four
times with four subsets of weights and biases. The photonic neuron circuit
diagram is shown in Fig. 1(d). The MRR weight bank is implemented with in-ring
N-doped photoconductive heaters[35] and provides the key functionality to
configure connection strengths (_i.e._ weights or synapses). The weight is
determined by the MRR transmission, which can be thermally tuned by adjusting
the electrical current applied to the N-doped heaters[35]. The N-doped heaters
allow continuous, multi-channel control of the MRR weight bank with accuracies
up to 8 bits[36, 37], which quantifies the precision of weights implementation
affected by the noise in the setup. The bit resolution obtained in photonic
matrix multiplier is comparable that used in DSP ASICs. The MRR weight bank
has two complementary optical outputs, each of which is detected by a
germanium-on-silicon photodetector. The two photodetectors form a balanced
photodetector [38], where the output photocurrent represents the subtraction
operation between the two MRR weight bank outputs, resulting in a
complementary –1 to +1 continuous weight range. The photocurrent, combined
with a forward bias current $I_{bias}$, modulates the transmission of the MRR
modulator (_i.e._ photonic neuron) via free-carrier injection to the p-n
junction, and hence modulates the optical power of a continuous-wave laser
(labeled as ”neuron pump”). The on-chip capacitor and resistor provide a
network matching circuit for efficient optical-electrical-optical (OEO)
conversion (see Supplementary information Photonic neuron simulation for
detailed circuit analysis). The MRR modulator exhibits nonlinear electrical-
to-optical transfer functions, which produce the activation function in the
NN. Furthermore, the neuron biases can be configured by adjusting the
electrical current applied to the MRR modulator.

1.08

Figure 2:  (a) Flowchart of training process. (b) Activation function of
photonic neuron. (c) The Q factor converges as the NN is trained, 32,016
symbols generated from the transmission system to monitor the training
process; red trace: Q factor before nonlinearity compensation. (d)
Transmission performance comparison. The neural network model for NLC is
trained with the activation function of photonic neuron. The 3-step and 6-step
DBP mean that fiber nonlinearity is compensated based on the conventional DSP
approach digital backpropagation by equally dividing 10,080 km transmission
link into 3 and 6 sections, respectively.

##  3 Training with photonic neural network

The proposed PNN provides trainable parameters including both weights and
biases. Trainable biases are critical for the NLC application, because they
can optimize the transfer function shapes to best approximate the higher-order
nonlinearity features from the symbols. To ensure that the trained NN
parameters can be accurately mapped on the photonic device, we include the
activation function of photonic neurons in the training phase. As shown in
Fig. 2(a), we begin by characterizing the on-chip activation function by
sending a training data sequence into the weight bank and recording the
corresponding neuron output waveform. The transfer function is fitted to a
Lorentzian function, as shown in Fig. 2(b), since the E/O response of MRR
modulators is typically a Lorentzian function. The training data have the same
data rate as the test data, in order to capture the bandwidth and the noise in
the device that would affect the activation function shape. Following that, we
apply the characterized activation function in the NN model and train the
neural network with the Adam learning algorithm[39].

The NN is trained with 32,106 training symbols in a single channel 32 Gbaud
PM-16-QAM signal transmitted over a 10,080 km pure silica core fiber link. The
weights are constrained to a range of -1 to 1 during the training, according
to the operation range of the MRR weight bank. We monitor the Q-factor of a
cross-validation (CV) data set to ensure that the NN is successfully trained
to recognize the fiber nonlinear distortion. The CV data set contains 32,106
symbols and is independent with the training data set. As shown in Fig. 2(c),
the Q-factor of the CV data increases gradually in the training process and
finally converges to 8.1 dB after 21,600 steps. To enable efficient training,
here we train the NN with a launch power higher than the optimal value. After
training, a test data set with varying launch powers is sent to the optical
link and processed by the trained NN. The nonlinear perturbation obtained from
the NN is weighted by the difference in the launch power between the training
and test set, and is then subtracted from the received signal. The Q factor of
the signal after NLC is calculated and plotted in Fig. 2(d). The optical power
at the Q factor peak is the optimal power that should be launched in the
transmission fiber. Using the simulated PNN, the Q factor of the transmission
link is increased by 0.66 dB as compared to that without NLC. Compared with
3-step DBP, the PNN is capable of achieving comparable Q factor performance.

1.08

Figure 3:  Experimental Setup. MZ-Mod: Mach-Zehnder modulator; AWG: arbitrary
waveform generator, CPL: coupler; EDFA: erbium-doped fiber amplifier, PC:
polarization controller; SMU: source meter unites; PNN: photonic neural
network; PD: photodetector.

##  4 Photonic neural network implementation

Following training, we implement the trained NN model to the PNN device, and
evaluate whether the PNN can accurately compensate fiber nonlinearity
impairment for high-speed signals. (See Supplementary Table. 3 for the weights
and biases values). The experimental setup is shown in Fig. 3. To emulate the
first hidden layer outputs, two external cavity lasers are modulated with two
waveforms generated from a two-channel arbitrary waveform generator (AWG).
Each channel operates at a sampling rate of 375 MSample/s and generates a
waveform of 32,106 test symbols at a symbol rate of 46.875 Mbaud/s. The test
signal is independent of the signals in the training phase. The wavelengths of
two lasers are initially aligned with the resonances of two MRRs in the MRR
weight banks. The two signals are then combined and coupled into the PNN chip
via a grating coupler. Two neuron pumps are derived from another two external
cavity lasers with wavelengths close to the resonances of the MRR modulators.
The modulator’s p-n junction is forward biased, allowing photocurrents from
the balanced photodetector to modulate the neuron pumps through free-carrier
injection. Under the carrier injection mode, the measured neuron bandwidth is
150 MHz. In Supplementary information Fig. 2, we show that, with the same
photonic circuits and optimized MRR modulator geometry, the neuron bandwidth
can be practically improved to 10 GHz.

1.08

Figure 4: (a) waveforms at the second hidden layer output. Green dashed line:
photonic neuron waveform; red dot: photonic neuron waveform downsampled to the
data rate of 16-QAM signals; blue triangle: simulated waveform after
downsampling. Ideally, the red points should overlap with the blue. And biased
activation function characterized from the measured waveforms (blue dot)
versus ideal activation function. (b) constellations of the 16-QAM signal on
the X-polarization. Red: without nonlinearity compensation (NLC); blue: NLC
using PNN; green: NLC using simulated NN. Red cross: constellation diagram of
16QAM without noise.

The trained NN parameters are grouped into four subsets, each with a
2$\times$2 weight matrix and 2 neuron biases. Each weight matrix is mapped to
a current matrix $\bm{I_{h}}$ and applied to the in-ring heaters of the MRR
weight banks using the control method described in Ref [36]. To apply neuron
biases, the modulator bias current $I_{bias}$ is tuned to approximate the
trained transfer function. The 2$\times$2 current matrix and 2 modulator
biases are simultaneously applied to the PNN chip. Fig. 4(a) shows the
waveform snapshots from the PNN output, which presents the outputs of the
second hidden layer, together with the measured transfer function of the eight
neurons. Each neuron’s transfer function corresponds to the different piece of
the characterized Lorentzian function under intended neuron biases. We
simulate the same NN with a 32-bit GPU-assisted workstation to benchmark the
accuracy of PNN implementation. Each neuron is evaluated by comparing the
experimental PNN output (red dots) with the simulated NN (blue dots). The mean
squared errors (MSEs) of photonic neurons are calculated over 32,016 test
symbols. MSEs are used to quantify the errors caused by noises and derivations
from target weights and activation functions. The MSEs vary between 0.008 to
0.014. The signal’s Q factor is then calculated from the eight photonic neuron
outputs (see Supplementary information Q factor calculation). Without
nonlinearity compensation, the optimal Q-factor of the signal is 9.34 dB,
obtained at the launch power of -1 dBm. With the PNN, the signal’s Q factor is
improved by 0.60 dB, and the constellation diagram after NLC is plotted in
Fig. 4(b.i), showing less noise in contrast to that without NLC. The Q-factor
obtained from the simulated NN indicates a 0.65 dB gain in Q-factor. That is,
the penalty of loading the neural network to the PNN is only 0.05 dB after
taking into account all inherent noise from the physical components and
equipment.

##  5 Scalability for NLC

Mainstream silicon photonic platforms offer an opportunity to implement the
entire neural network for NLC on a single silicon photonic chip. Silicon
photonic circuits with a few thousands of elements have been demonstrated [33,
34]. Weight pruning[8] is an effective pathway for reducing the PNN footprint
and power consumption, which can be accomplished by having a few more neurons
in hidden layers (see Fig. 5) while reducing the number of input triplets. The
current NN model has 892 input triplets. After weight pruning, the number of
inputs can be reduced by three times to 300. The photonic neural network, in
this case, has 952 optoelectronic components. These components require 0.38
mm2 chip space. Electrical traces and pads connecting to the optoelectronic
components provide electrical biases to the photonic circuit. Electrical
traces and pads connecting to the optoelectronic components provide electrical
biases to the photonic circuit. The amount of chip space used by electrical
traces and pads varies significantly depending on the chip floorplan and
packaging technologies. For example, the electrical traces can be very short
using the flip-chip bonding technology, and the pads take up 0.76 mm2 areas
(each bonding pad takes 20$\mu$m $\times$ 20$\mu$m area)[40]. Ref [33] have
demonstrated that silicon photonic devices with comparable footprints are
feasible.

A challenge of large-scale silicon photonic circuits is device non-uniformity,
i.e., the dimensions and performances of the devices across the chip are not
uniform and deviate from the design. In PNNs, device non-uniformity will cause
variations of the relationship between the actuated MRR currents and the
actual weights, the activation function shape, etc. The influences of device
variations can be minimized by pre-calibrating each device or using control
methods, such as the feedback MRR control [35, 36]. Device variances can be
further reduced through post-fabrication technologies such as trimming [41] or
in-situ training[42]. Another challenge deals with light sources. Frequency
combs-based WDM sources[43] allow the generation of broadband and evenly
spaced emission wavelengths from a single laser, and thus offer a practical
approach of generating WDM light sources for the PNN. Soliton-based frequency
combs built on CMOS-compatible photonic integrated circuits can generate
hundreds of comb lines. Such systems can integrate with the PNN device.

##  6 Claiming cascadability for NLC

We discuss the feasibility of scaling the current chip to a multi-layer neural
network. This issue refers to the need for cascadability, that is, the ability
to have the one neuron output to excite the neurons in the next layer.
Cascadability requires 1) the neuron output can evoke an equivalent response
in neurons in the subsquent layer; 2) to avoid noise propagation along with
multiple neural layers. The main conclusion is, in order to have one layer
driving the next layer, enough power must be provided to compensate for loss
and power splitting due to fan-out to the next layer. Such power can come from
optical lasers or electrical gain via a high transimpedance. The electrical
gain can be provided with a passive resistor or an active TIA, both of which
are compatible with today’s silicon photonic platform. For example, we have
implemented an on-chip resistor in our current PNN design. Alternatively, we
can use an efficient modulator (i.e. small $V_{\pi}$ and junction capacitor C)
to reduce the power requirement. We derive the devices and power requirement
of maintaining the cascadability in the Supplementary information  Performance
comparison between DSP and PNNs.

Regarding noise propagation, we found that if the voltage swing to the
modulator is large enough, the nonlinear transfer function of the modulator
can suppress the noise and avoid noise propagation across the network[44].
Such requirements can also be addressed with sufficient power or with an
efficient modulator, as argued in [45, 44, 46].

##  7 Impact of activation function and the number of neurons

In the NLC application, the NN is trained to recognize the fiber nonlinearity
perturbation from the received symbols. An appropriate choice of activation
function can benefit such regression problems by including higher-order
nonlinearities among the symbols. Fiber nonlinearity perturbation manifests
itself as long, heavy-tailed symbols due to nonlinear phase noise. To extract
such features, especially the tail edge, an activation function with an
unbounded range is preferred. Fig. 5(a) shows the performance gap between the
Lorentzian function of an MRR modulator neuron and the Leaky ReLU function
which has no upper boundary for positive input. Generally, for different NN
applications, activation functions need to be chosen to synthesize particular
tasks. In contrast to a single cavity MRR, photonic devices with multiple
coupled cavities can exhibit different lineshapes beyond the Lorentzian shape.
Additional transfer function programmability could be achieved at the expense
of additional circuits and calibration complexity using multiple-cavity
modulators for some or all of the neurons[28]. Reconfigurable elements such as
heaters or phase change materials allow optimizing device’s transfer functions
for different machine learning tasks.

In addition, as shown in Fig. 5(b), the Q-factor improves as the number of
neurons on the second-hidden layer increases. This can be expected because,
with more neurons, the network can more precisely constitute different parts
of nonlinearity perturbation over symbols. PNNs add almost no delays as the NN
size increases, because the major operations in a PNN are computed at a single
time step.

Figure 5: (a) Leaky ReLU, optimized for fiber nonlinearity compensation as
demonstrated by Zhang et al.[8], and Lorentzian, characterized from the PNN.
(b) The comparison of Q factor improvement between Leaky ReLU (red) and
Lorentzian (blue) activation functions.

### 7.1

##  8 Conclusion

We have reported a reconfigurable photonic-electronic integrated neural
network platform that incorporates photonic components on a silicon photonic
platform for high-speed information processing. We demonstrated our system is
capable of performing essential functionalities such as accurate weighting,
summation, and biased nonlinearity for neural network computing. We applied
this system for fibre nonlinearity compensation in trans-Pacific transmission
data links, which require extremely high throughput and real-time signal
processing. We experimentally implemented the second layer of the neural
network using silicon photonic neurons, and showed in simulations that the
extended system can accurately model the fibre nonlinearity, leading to a
Q-factor improvement comparable with numerical simulations on a conventional
computer. The system is capable of processing optical signals in the analogue
domain, thereby significantly relaxing the stringent requirements of
complexity and speed that are typically placed on conventional DSP circuits.
Our approach could help in the development of reconfigurable
photonic–electronic integrated circuits for solving a range of problems in
high-speed intelligent signal processing.

###  8.1 Device Fabrication

The device sample is fabricated on a silicon-on-insulator (SOI) wafer with a
silicon thickness of 220 nm and a buried oxide thickness of 2 $\mu$m. The
waveguide is 500 nm wide. The weight bank consists of four MRRs coupled with
two bus waveguides in an add/drop configuration. The four MRRs have radii of
8.0, 8.1, 8.2, 8.3 $\mu$m, respectively. Only the first two MRRs are used in
the experiments. A slight difference is introduced in the ring radii to avoid
resonance collision. The gap between the ring and bus waveguide is 200 nm,
yielding a Q factor of $\sim$6000\. For the purpose of weight control, in-ring
N-doped photoconductive heaters are used. To implement the N-doped heater,
each MRR consists of a ring waveguide etched to a 90 nm thick pedestal that
hosts the phosphorus dopants. A 10 $\mu$m wide N doping section is patterned
to follow the MRR, outside of which heavy N++ doping is used to make ohmic
contacts. Metal vias and traces are deposited to connect the heater contacts
of the MRR weight bank to electrical metal pads.

The MRR modulator consists of a ring waveguide with a radius of 8 $\mu$m
coupled to two bus waveguides with gaps of 0.2 and 0.5 $\mu$m respectively.
The ring waveguide is etched to a 90-nm-thick pedestal that hosts boron and
phosphorus to form n+ and n-, and p+ and p- regions, respectively. The lightly
p- and n-doped regions are extended to the waveguide core to form a p-n
junction for high-speed modulation. The highly p+ or n+ doped regions are
located at the pedestal edge to serve as p-type and n-type ohmic contact
areas. To fabricate the germanium-on-silicon photodetector, a germanium layer
is deposited and patterned on top of the silicon waveguide. Boron and
phosphorus are implanted in the sidewalls and slabs of the Ge waveguide to
form a horizontal p-i-n junction as well as p-type and n-type ohmic contact
areas. Metal vias and traces are deposited to connect the electrical ports of
the devices to the electrical metal pads. The cross-sections of MRR resonator
embedded with n-doped heater, MRR modulator, and germanium-on-silicon
photodetector are illustrated in Supplementary Fig. 1.

The on-chip capacitor is formed by two layers of metal and has a capacitance
of 2 pF. The resistor is formed by a slab waveguide etched to a 90 nm thick
pedestal that heavily doped with phosphorus (N++). The resistor has a
resistance of 300 $\Omega$.

All data used in this study are available from the corresponding author upon
reasonable request.

All codes used in this study are available from the corresponding author upon
reasonable request.

This research is supported by the Office of Naval Research (ONR)
(N00014-18-1-2297), Defense Advanced Research Projects Agency (HR00111990049),
National Science Foundation (NSF) (Grants No. ECCS 1642962 and No. DGE
1148900), and CUHK Research Direct Grant. The devices were fabricated at the
IME ASTAR foundry in Singapore. Fabrication support was provided via the
Natural Sciences and Engineering Research Council of Canada (NSERC) Silicon
Electronic-Photonic Integrated Circuits (SiEPIC) Program and the Canadian
Microelectronics Corporation (CMC).

C.H., S.F., and T.L. conceived the ideas and implement the experimental setup,
designed the experiment, conducted the experiment measurement, and analyzed
the results. C.H., T.L., E.B., S.B., A.J., H.P. designed the silicon photonic
chip. A.T., Y.T., F.Y, B.S. provided the theoretical support. T.L., E.B., S.B.
performed the chip packaging. C.H., S.F., T.L., A.T., B.S. wrote the
manuscript. T.W. and P.P. supervised the research and contributed to the
general concept and interpretation of the results. All authors discussed the
data and contributed to the manuscript.

The authors declare no competing interests.

Chaoran Huang (email<EMAIL_ADDRESS>ORCID: 0000-0001-6997-758X),
Paul R. Prucnal (email<EMAIL_ADDRESS>ORCID: 0000-0002-5291-5830).

###  8.2 References

## References

  * [1] Najafabadi, M. M. _et al._ Deep learning applications and challenges in big data analytics.  _Journal of Big Data_ 2, 1 (2015).
  * [2] Deng, L., Yu, D. _et al._ Deep learning: methods and applications.  _Foundations and Trends® in Signal Processing_ 7, 197–387 (2014).
  * [3] De Lima, T. F. _et al._ Machine learning with neuromorphic photonics.  _Journal of Lightwave Technology_ 37, 1515–1534 (2019).
  * [4] Wang, Y. & Boyd, S.  Fast model predictive control using online optimization.  _IEEE Transactions on control systems technology_ 18, 267–278 (2009).
  * [5] Shi, Y. _et al._ Deep learning for rf signal classification in unknown and dynamic spectrum environments.  In _2019 IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN)_ , 1–10 (IEEE, 2019).
  * [6] Zibar, D., Piels, M., Jones, R. & Schäeffer, C. G.  Machine learning techniques in optical communication.  _Journal of Lightwave Technology_ 34, 1442–1452 (2015).
  * [7] Khan, F. N., Fan, Q., Lu, C. & Lau, A. P. T.  An optical communication’s perspective on machine learning and its applications.  _Journal of Lightwave Technology_ 37, 493–516 (2019).
  * [8] Zhang, S. _et al._ Field and lab experimental demonstration of nonlinear impairment compensation using neural networks.  _Nature communications_ 10, 1–8 (2019).
  * [9] Ip, E. & Kahn, J. M.  Compensation of dispersion and nonlinear impairments using digital backpropagation.  _Journal of Lightwave Technology_ 26, 3416–3425 (2008).
  * [10] Giacoumidis, E., Lin, Y., Blott, M. & Barry, L. P.  Real-time machine learning based fiber-induced nonlinearity compensation in energy-efficient coherent optical networks.  _APL Photonics_ 5, 041301 (2020).
  * [11] Morero, D. A., Castrillon, M. A., Aguirre, A., Hueda, M. R. & Agazzi, O. E.  Design tradeoffs and challenges in practical coherent optical transceiver implementations.  _Journal of Lightwave Technology_ 34, 121–136 (2016).
  * [12] Du, L. B. _et al._ Digital fiber nonlinearity compensation: toward 1-tb/s transport.  _IEEE signal processing magazine_ 31, 46–56 (2014).
  * [13] Prucnal, P. R. & Shastri, B. J.  _Neuromorphic photonics_ (CRC Press, 2017).
  * [14] Shastri, B. J. _et al._ Photonics for artificial intelligence and neuromorphic computing.  _Nature Photonics_ 15, 102–114 (2021).
  * [15] Brunner, D. & Fischer, I.  Reconfigurable semiconductor laser networks based on diffractive coupling.  _Optics letters_ 40, 3854–3857 (2015).
  * [16] Zuo, Y. _et al._ All-optical neural network with nonlinear activation functions.  _Optica_ 6, 1132–1137 (2019).
  * [17] Hill, M. T., Frietman, E. E., de Waardt, H., Khoe, G.-d. & Dorren, H. J.  All fiber-optic neural network using coupled soa based ring lasers.  _IEEE Transactions on Neural Networks_ 13, 1504–1513 (2002).
  * [18] Fok, M. P. _et al._ Signal feature recognition based on lightwave neuromorphic signal processing.  _Optics letters_ 36, 19–21 (2011).
  * [19] Brunner, D., Soriano, M. C., Mirasso, C. R. & Fischer, I.  Parallel photonic information processing at gigabyte per second data rates using transient states.  _Nature communications_ 4, 1–7 (2013).
  * [20] Lin, X. _et al._ All-optical machine learning using diffractive deep neural networks.  _Science_ 361, 1004–1008 (2018).
  * [21] Bueno, J. _et al._ Reinforcement learning in a large-scale photonic recurrent neural network.  _Optica_ 5, 756–760 (2018).
  * [22] Tait, A. N. _et al._ Neuromorphic photonic networks using silicon photonic weight banks.  _Scientific reports_ 7, 1–10 (2017).
  * [23] Peng, H.-T., Nahmias, M. A., De Lima, T. F., Tait, A. N. & Shastri, B. J.  Neuromorphic photonic integrated circuits.  _IEEE Journal of Selected Topics in Quantum Electronics_ 24, 1–15 (2018).
  * [24] Shen, Y. _et al._ Deep learning with coherent nanophotonic circuits.  _Nature Photonics_ 11, 441 (2017).
  * [25] Feldmann, J., Youngblood, N., Wright, C. D., Bhaskaran, H. & Pernice, W.  All-optical spiking neurosynaptic networks with self-learning capabilities.  _Nature_ 569, 208–214 (2019).
  * [26] Vandoorne, K. _et al._ Experimental demonstration of reservoir computing on a silicon photonics chip.  _Nature communications_ 5, 1–6 (2014).
  * [27] Tait, A. N. _et al._ Silicon photonic modulator neuron.  _Physical Review Applied_ 11, 064043 (2019).
  * [28] Huang, C. _et al._ On-chip programmable nonlinear optical signal processor and its applications.  _IEEE Journal of Selected Topics in Quantum Electronics_ (2020).
  * [29] Essiambre, R.-J., Kramer, G., Winzer, P. J., Foschini, G. J. & Goebel, B.  Capacity limits of optical fiber networks.  _Journal of Lightwave Technology_ 28, 662–701 (2010).
  * [30] Tao, Z. _et al._ Multiplier-free intrachannel nonlinearity compensating algorithm operating at symbol rate.  _Journal of Lightwave technology_ 29, 2570–2576 (2011).
  * [31] Tait, A. N., Nahmias, M. A., Shastri, B. J. & Prucnal, P. R.  Broadcast and weight: an integrated network for scalable photonic spike processing.  _Journal of Lightwave Technology_ 32, 4029–4041 (2014).
  * [32] Jouppi, N. P. _et al._ In-datacenter performance analysis of a tensor processing unit.  In _Proceedings of the 44th Annual International Symposium on Computer Architecture_ , 1–12 (2017).
  * [33] Sun, J., Timurdogan, E., Yaacobi, A., Hosseini, E. S. & Watts, M. R.  Large-scale nanophotonic phased array.  _Nature_ 493, 195–199 (2013).
  * [34] Poulton, C. V. _et al._ 8192-element optical phased array with 100 steering range and flip-chip cmos.  In _CLEO: Applications and Technology_ , JTh4A–3 (Optical Society of America, 2020).
  * [35] Tait, A. N. _et al._ Feedback control for microring weight banks.  _Optics express_ 26, 26422–26443 (2018).
  * [36] Huang, C. _et al._ Demonstration of scalable microring weight bank control for large-scale photonic integrated circuits.  _APL Photonics_ 5, 040803 (2020).
  * [37] Zhang, W. _et al._ Microring weight banks control beyond 8.5-bits accuracy.  _arXiv preprint arXiv:2104.01164_ (2021).
  * [38] Hai, M. S., Sakib, M. N. & Liboiron-Ladouceur, O.  A 16 ghz silicon-based monolithic balanced photodetector with on-chip capacitors for 25 gbaud front-end receivers.  _Optics express_ 21, 32680–32689 (2013).
  * [39] Kingma, D. P. & Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * [40] Carroll, L. _et al._ Photonic packaging: transforming silicon photonic integrated circuits into photonic devices.  _Applied Sciences_ 6, 426 (2016).
  * [41] Atabaki, A. H., Eftekhar, A. A., Askari, M. & Adibi, A.  Accurate post-fabrication trimming of ultra-compact resonators on silicon.  _Optics express_ 21, 14139–14145 (2013).
  * [42] Wang, Z. _et al._ In situ training of feed-forward and recurrent convolutional memristor networks.  _Nature Machine Intelligence_ 1, 434–442 (2019).
  * [43] Brasch, V. _et al._ Photonic chip–based optical frequency comb using soliton cherenkov radiation.  _Science_ 351, 357–360 (2016).
  * [44] de Lima, T. F. _et al._ Noise analysis of photonic modulator neurons.  _IEEE Journal of Selected Topics in Quantum Electronics_ 26, 1–9 (2019).
  * [45] Nozaki, K. _et al._ Femtofarad optoelectronic integration demonstrating energy-saving signal conversion and nonlinear functions.  _Nature Photonics_ 13, 454–459 (2019).
  * [46] Nahmias, M. A. _et al._ Photonic multiply-accumulate operations for neural networks.  _IEEE Journal of Selected Topics in Quantum Electronics_ 26, 1–18 (2019).