# Edge coloring of graphs of signed class $1$ and $2$

Robert Janczewski11footnotemark: 1 Department of Algorithms and System
Modeling, Faculty of Electronics, Telecommunication and Informatics, Gdańsk
University of Technology, ul. Narutowicza $11/12$, Gdańsk, Poland  Krzysztof
Turowski22footnotemark: 2 Theoretical Computer Science Department,
Jagiellonian University, Kraków, $30$–$348$, Poland  Bartłomiej
Wróblewski33footnotemark: 3 Department of Algorithms and System Modeling,
Faculty of Electronics, Telecommunication and Informatics, Gdańsk University
of Technology, ul. Narutowicza $11/12$, Gdańsk, Poland

###### Abstract

Recently, Behr [1] introduced a notion of the chromatic index of signed graphs
and proved that for every signed graph $(G$, $\sigma)$ it holds that

$\Delta(G)\leq\chi^{\prime}(G\text{, }\sigma)\leq\Delta(G)+1\text{,}$

where $\Delta(G)$ is the maximum degree of $G$ and $\chi^{\prime}$ denotes its
chromatic index.

In general, the chromatic index of $(G$, $\sigma)$ depends on both the
underlying graph $G$ and the signature $\sigma$. In the paper we study graphs
$G$ for which $\chi^{\prime}(G$, $\sigma)$ does not depend on $\sigma$. To
this aim we introduce two new classes of graphs, namely $1^{\pm}$ and
$2^{\pm}$, such that graph $G$ is of class $1^{\pm}$ (respectively, $2^{\pm}$)
if and only if $\chi^{\prime}(G$, $\sigma)=\Delta(G)$ (respectively,
$\chi^{\prime}(G$, $\sigma)=\Delta(G)+1$) for all possible signatures
$\sigma$.

We prove that all wheels, necklaces, complete bipartite graphs $K_{r,t}$ with
$r\neq t$ and almost all cacti graphs are of class $1^{\pm}$. Moreover, we
give sufficient and necessary conditions for a graph to be of class $2^{\pm}$,
i.e. we show that these graphs must have odd maximum degree and give examples
of such graphs with arbitrary odd maximum degree bigger than $1$.

###### keywords:

signed graphs , edge coloring signed graphs , complete bipartite graphs ,
cacti

janczewski_footnotejanczewski_footnotefootnotetext: E-mail:
<EMAIL_ADDRESS>E-mail:
<EMAIL_ADDRESS>E-mail<EMAIL_ADDRESS>
##  1 Introduction

In this paper we only consider simple, finite and undirected graphs. Graph $G$
has a set of vertices $V(G)$ and a set of edges $E(G)$ with $n(G)$, $m(G)$
denoting their cardinalities, respectively. By $\deg_{G}(v)$ we denote degree
of a vertex $v$ in a graph $G$ and by $\Delta(G)$ the maximum degree of all
vertices of $G$. _Incidence_ is a pair $(v$, $e)$, where $v$ is a vertex, $e$
is an edge and $v$ is one of the endpoints of $e$. Incidence $(v$, $e)$ will
be shortly denoted by $v\colon e$ and the set of all graph’s incidences will
be denoted by $I(G)$. All other definitions and symbols are consistent with
those defined in Diestel [2].

Signed graphs were introduced in $1950$s by Harary [3] as a generalization of
simple graphs. Their main purpose was to better model social relations of
disliking, indifference and liking. A _signed graph_ is a pair $(G$, $\sigma)$
where $G$ is a graph and $\sigma\colon E(G)\to\\{\pm 1\\}$ is a function. $G$
and $\sigma$ are called the _underlying_ graph of $(G$, $\sigma)$ and the
_signature_ of $(G$, $\sigma)$, respectively. Edge $e\in E(G)$ will be called
_positive_ (respectively, _negative_) if and only if $\sigma(e)=1$
(respectively, $\sigma(e)=-1$). Cycle in $(G$, $\sigma)$ is called _positive_
(respectively, _negative_) if product of signs of its edges is positive
(respectively, negative). A signed graph with only positive cycles is
_balanced_ otherwise it is _unbalanced_.

Switching of a set $V^{\prime}\subseteq V(G)$ of a signed graph $(G$,
$\sigma)$ is an operation resulting in a signed graph $(G$, $\sigma^{\prime})$
such that for every edge $uv\in E(G)$ we have

$\sigma^{\prime}(uv)=\begin{cases}-\sigma(uv)\text{, }&\text{if exactly one of
$u$, $v$ belongs to $V^{\prime}$,}\\\ \sigma(uv)\text{,
}&\text{otherwise.}\end{cases}$

For example, switching a vertex, i.e. switching a subset of vertices of
cardinality one, negates the signs of its incident edges. If a signed graph
$(G$, $\sigma^{\prime})$ can be obtained by switching some of the vertices of
$(G$, $\sigma)$, we say that $(G$, $\sigma^{\prime})$ and $(G$, $\sigma)$ are
_switching equivalent_. It is well-known that switching equivalence is an
equivalence relation in the set of all signed graphs with a fixed underlying
graph.

In $2020$, Behr [1] introduced a concept of edge coloring of signed graphs as
a generalization of ordinary graph edge coloring. Let $n$ be a positive
integer and

$M_{n}=\begin{cases}\\{0\text{, }\pm 1\text{, }\ldots\text{, }\pm k\\}\text{,
}&\text{if $n=2k+1$,}\\\ \\{\pm 1\text{, }\ldots\text{, }\pm k\\}\text{,
}&\text{if $n=2k$.}\end{cases}$

An _$n$ -edge-coloring_ of a signed graph $(G$, $\sigma)$ is a function
$f\colon I(G)\to M_{n}$ such that $f(u\colon uv)=-\sigma(uv)f(v\colon uv)$ for
each edge $uv\in E(G)$ and $f(u\colon e_{1})\neq f(u\colon e_{2})$ for all
edges $e_{1}\neq e_{2}$ such that $u\colon e_{1}$, $u\colon e_{2}\in I(G)$. By
$\chi^{\prime}(G$, $\sigma)$ we denote _the chromatic index_ of a signed graph
$(G$, $\sigma)$, i.e. the smallest $n$ for which $(G$, $\sigma)$ has an
$n$-edge-coloring.

Behr [1] proved that every signed path can be colored using $2$ colors and a
signed cycle can be colored with $2$ colors if and only if it’s balanced. The
main result of Behr’s article [1] is the generalized Vizing’s theorem. We will
call it the Behr’s theorem to emphasize the importance of Behr’s achievement.

######  Theorem 1 (Behr [1]).

$\Delta(G)\leq\chi^{\prime}(G$, $\sigma)\leq\Delta(G)+1$ for all signed graphs
$(G$, $\sigma)$. ∎

In this paper we introduce two new classes of graphs, namely $1^{\pm}$ and
$2^{\pm}$, such that graph $G$ is of class $1^{\pm}$ (respectively, $2^{\pm}$)
if and only if $\chi^{\prime}(G$, $\sigma)=\Delta(G)$ (respectively,
$\chi^{\prime}(G$, $\sigma)=\Delta(G)+1$) for all possible signatures
$\sigma$. In Section 2 we relate these classes to previously known notions. We
also show sufficient and necessary conditions for a regular signed graph $(G$,
$\sigma)$ to be $\Delta(G)$-edge-colorable and use these results to obtain
sufficient and necessary conditions for a regular signed graph to be of class
$2^{\pm}$. Next, we show that graphs of class $2^{\pm}$ must be of odd maximum
degree and there are such graphs for any greater than $1$ odd value of the
degree. In Section 3 we prove that all cacti except cycles are of class
$1^{\pm}$. Section 4 deals with wheels—they are all of class $1^{\pm}$. In
Section 5 we show that all necklaces except cycles are of class $1^{\pm}$. In
Section 6 we deal with complete bipartite graphs by showing that graphs
$K_{r,t}$ are of class $1^{\pm}$ for any $r\neq t$. The paper ends with some
open problems and conjectures.

##  2 $1^{\pm}$ and $2^{\pm}$

Behr [4] defined _class ratio $\mathcal{C}(G)$_ of graph $G$ to be the number
of possible signatures $\sigma\colon E(G)\to\\{\pm 1\\}$ such that the signed
graph $(G$, $\sigma)$ is $\Delta(G)$-colorable, divided by the number of all
possible signatures defined on $E(G)$, i.e. $2^{m(G)}$. The class ratio is a
rational number satisfying $0\leq\mathcal{C}(G)\leq 1$ and, by previous
definitions, $G$ is of class $1^{\pm}$ (respectively, $2^{\pm}$) if and only
if $\mathcal{C}(G)=1$ (respectively, $\mathcal{C}(G)=0$). Clearly, there are
graphs that are neither of class $1^{\pm}$ nor $2^{\pm}$. The obvious example
is a cycle—all signed cycles are $2$-colorable if are balanced and require $3$
colors otherwise. It is also easy to see that if $G$ is of class $1^{\pm}$
($2^{\pm}$), then it is of class $1$ ($2$), where class $1$ ($2$) is defined
as all graphs $G$ whose ordinary chromatic index equals $\Delta(G)$
($\Delta(G)+1$). This relation provides justification for our notation: class
$X^{\pm}$ is both a signed counterpart of class $X$ and a subclass of $X$.

Recall that graph $G$ is _$r$ -regular_ if and only if $\deg_{G}(v)=r$ for all
$v\in V(G)$. Recall also that $M\subseteq E(G)$ is a (_perfect_) _matching_ in
$G$ if every vertex of $G$ is incident to at most (exactly) one edge of $M$.

######  Lemma 2.

Let $G$ be a $k$-regular graph and $\sigma\colon E(G)\to\\{\pm 1\\}$ be a
signature. $\chi^{\prime}(G$, $\sigma)=\Delta(G)$ if and only if one of the
following conditions holds:

  1. 1.

$k=2r$ where $r$ is a positive integer and $(G$, $\sigma)$ admits a
decomposition into exactly $r$ spanning edge disjoint $2$-regular balanced
subgraphs.

  2. 2.

$k=2r+1$ where $r$ is a positive integer and $(G$, $\sigma)$ admits a
decomposition into a perfect matching and exactly $r$ spanning edge disjoint
$2$-regular balanced subgraphs.

###### Proof.

We prove the equivalence by proving both implications.

($\Leftarrow)$ In the $k=2r$ case, each of the $r$ spanning edge disjoint
$2$-regular balanced subgraphs can be colored using exactly $2$ colors, so in
total $2r$ colors are sufficient to color the whole graph. In the $k=2r+1$
case, the matching can be colored using color $0$, each of the $r$ spanning
edge disjoint $2$-regular balanced subgraphs can be colored using $2$ colors,
so in total $2r+1$ colors are also sufficient. Since $\Delta(G)=2r$ in the
first case and $\Delta(G)=2r+1$ in the second, we get $\chi^{\prime}(G$,
$\sigma)=\Delta(G)$.

($\Rightarrow)$ We consider the two cases separately:

  1. $(1)$

$G$ is a $2r$-regular graph, so $m(G)=r\cdot n(G)$. Let $c$ be an arbitrary
$\Delta(G)$-edge-coloring of $(G$, $\sigma)$. For every pair of opposite
colors used by $c$, edges colored with them form a subgraph with maximum
degree not exceeding $2$. Clearly, all such subgraphs are edge disjoint. Each
of the subgraphs has at most $n(G)$ edges. There are exactly $r$ such
subgraphs in $G$ and $G$ has $r\cdot n(G)$ edges, so every subgraph contains
exactly $n(G)$ edges. If a subgraph with maximum degree not exceeding $2$
contains $n(G)$ edges, it clearly is spanning and $2$-regular. If it can be
colored with two colors, it has to be balanced, too.

  2. $(2)$

$G$ is a $(2r+1)$-regular graph, so $m(G)=r\cdot n(G)+\frac{1}{2}n(G)$. Let
$c$ be an arbitrary $\Delta(G)$-edge-coloring of $(G$, $\sigma)$. The set of
edges colored in $c$ with color $0$ must form a matching in $G$. Matching in
$G$ can have maximum size of $\frac{1}{2}n(G)$, so there have to be at least
$r\cdot n(G)$ edges colored by $c$ with colors different than $0$. Such edges
form $r$ subgraphs with maximum degree not exceeding $2$, each of them is
colored with $\\{-k,k\\}$ for some $k\neq 0$. Clearly, they are edge disjoint
subgraphs with degree not exceeding $2$, so they have in total at most $r\cdot
n(G)$ edges. Combining these observations, we conclude that these subgraphs
have exactly $r\cdot n(G)$ edges. This implies that they are $2$-regular,
spanning and balanced – since otherwise they could not be colored using only
colors $\\{-k,k\\}$. This also implies that our matching has $\frac{1}{2}n(G)$
edges, which means it is perfect.

∎

Let $\mathbf{1}_{X}$ denote the function $X\ni x\mapsto 1\in\\{\pm 1\\}$.

######  Corollary 3.

If $G$ is a graph with even $\Delta(G)$, then $G$ is not of class $2^{\pm}$.

###### Proof.

Every graph has a regular supergraph with the same maximum degree. Let $H$ be
a $\Delta(G)$-regular supergraph of $G$. It follows from Petersen’s $2$-factor
theorem [5] that $H$ admits a decomposition into $r$ edge disjoint
$2$-regular, spanning subgraphs. Since all edges in a signed graph $(H$,
$\mathbf{1}_{E(H)})$ are positive, these subgraphs are balanced. Lemma 2
implies that $\chi^{\prime}(H$, $\mathbf{1}_{E(H)})=\Delta(H)$. Hence
$\chi^{\prime}(G$, $\mathbf{1}_{E(G)})\leq\chi^{\prime}(H$,
$\mathbf{1}_{E(H)})=\Delta(H)=\Delta(G)$, which shows that $G$ is not of class
$2^{\pm}$. ∎

######  Theorem 4.

Let $G$ be a graph. $G$ is of class $2^{\pm}$ if and only if $\Delta(G)$ is
odd and there is no matching $M$ in $G$ such that $\Delta(G\setminus
M)<\Delta(G)$.

###### Proof.

If follows from Corollary 3 that if graph is of class $2^{\pm}$ then its
maximum degree must be odd.

($\Rightarrow)$ Let $G$ be a graph with odd maximum degree. Suppose that there
is a matching $M\subseteq E(G)$ such that $\Delta(G\setminus M)<\Delta(G)$. We
will show that $G$ is not of class $2^{\pm}$. Clearly, $\Delta(G\setminus M)$
is even since $\Delta(G\setminus M)=\Delta(G)-1$. The proof of Corollary 3
shows that a signed graph $(G\setminus M$, $\mathbf{1}_{E(G)\setminus M})$ is
$\Delta(G\setminus M)$-colorable. Since $\Delta(G\setminus M)$ is even,
$\Delta(G\setminus M)$-colorings of $G\setminus M$ does not use color $0$. We
can extend any of these colorings to a coloring of $G$ by using color $0$ on
$M$, so $(G$, $\mathbf{1}_{E(G)})$ is $\Delta(G)$-edge-colorable. This
completes the proof.

($\Leftarrow$) Let us assume $\Delta(G)$ is odd, there is no matching
$M\subseteq E(G)$ such that $\Delta(G\setminus M)<\Delta(G)$ and $G$ is not of
class $2^{\pm}$. We show that this leads to a contradiction. There must exist
a signature $\sigma$ such that $(G$, $\sigma)$ is $\Delta(G)$-edge-colorable.
Let $c$ be an arbitrary $\Delta(G)$-edge-coloring of $(G$, $\sigma)$. Edges
colored in $c$ with color $0$ must form a matching $M$. Clearly,
$\Delta(G\setminus M)=\Delta(G)$, so graph $(G\setminus M$,
$\sigma|_{E(G)\setminus M})$ requires at least $\Delta(G)$ colors different
than $0$. It follows that $(G$, $\sigma)$ cannot be colored using $\Delta(G)$
colors, so $G$ is of class $2^{\pm}$. ∎

It’s easy to observe that signed graphs with $\Delta=1$ can be colored using
color $0$ regardless of their signature, so graphs with $\Delta=1$ are of
class $1^{\pm}$.

######  Theorem 5.

For every $k\geq 1$ there is a graph $G$ of class $2^{\pm}$ such that
$\Delta(G)=2k+1$.

###### Proof.

We will describe the procedure of construction of a graph $G$ such that
$\Delta(G)=2k+1$ and $G$ is of class $2^{\pm}$. We start by constructing a
complete bipartite graph $H$ with parts $\\{u_{1}$, …, $u_{2k}\\}$ and
$\\{v_{1}$, …, $v_{2k}\\}$. Next we create a graph $H^{\prime}$ by adding
edges $u_{2i-1}u_{2i}$ for $1\leq i\leq k$ to $H$, a new vertex $v$ and edges
$v_{i}v$ for $1\leq i\leq 2k$. It is easy to see that

$\deg_{H^{\prime}}(w)=\begin{cases}2k\text{, }&\text{if $v=w$,}\\\ 2k+1\text{,
}&\text{otherwise.}\end{cases}$

Now we construct the graph $G$ by creating two disjoint copies of $H^{\prime}$
and connecting their lowest degree vertices with path $P_{3}$ in such a way
that these vertices are the endpoints of the path (see Figure 1 for an
example). By $v^{\prime}_{1}$, $v_{c}$, $v^{\prime}_{2}$ we denote vertices of
that path and by $v^{\prime}_{1}v_{c}$, $v_{c}v^{\prime}_{2}$—its edges. Let’s
observe that $\deg_{G}(v_{c})=2$ and other vertices of $G$ have degree $2k+1$.

To complete the proof it suffices to show that $G$ is of class $2^{\pm}$.
Clearly, $\Delta(G)$ is odd, so Theorem 4 tells us that we need to show that
there is no matching $M\subseteq E(G)$ such that $\Delta(G\setminus
M)<\Delta(G)$. Let’s assume there is such a matching $M$ in $G$. We show that
it leads to a contradiction. Clearly, $M$ must cover all the vertices of $G$
other than $v_{c}$—it must cover all the vertices of both copies of
$H^{\prime}$. Let’s observe that $H^{\prime}$ has an odd number of vertices,
so there is no perfect matching in it. It means that in order to cover
vertices of both copies of $H^{\prime}$, $M$ must contain edges
$v^{\prime}_{1}v_{c}$ and $v_{c}v^{\prime}_{2}$. Then $M$ contains two edges
incident with $v_{c}$, so $M$ is not a matching, a contradiction that
completes the proof. ∎

Figure 1: Example graph of class $2^{\pm}$ with $\Delta=5$.

##  3 Cacti

A connected graph $G$ is called _cactus_ if and only if every edge of $G$
belongs to at most one cycle. Clearly every tree is a cactus as it doesn’t
have cycles at all. It is a well known fact [6] that graph $G$ is a cactus if
and only if there exists a sequence of graphs $G_{1}$, …, $G_{k}$ called a
_decomposition of $G$_, such that:

  1. 1.

$G_{i}$ is a cycle or a path $P_{2}$ for $1\leq i\leq k$;

  2. 2.

$G_{i}$ has exactly one vertex in common with $G_{1}\cup\ldots\cup G_{i-1}$
for $2\leq i\leq k$;

  3. 3.

$G=G_{1}\cup\ldots\cup G_{k}$.

We prove that almost all signed cacti are of class $1^{\pm}$.

######  Theorem 6.

Let $G$ be a cactus. If $G$ is not a cycle, then $G$ is of class $1^{\pm}$.

###### Proof.

Let $\sigma\colon E(G)\to\\{\pm 1\\}$ be a function. If $\Delta(G)\leq 2$,
then $G$ is a path, so our claim is obvious. Therefore we assume that
$\Delta(G)\geq 3$ in the remainder of the proof.

Let $G_{1}$, …, $G_{k}$ be an arbitrary decomposition of $G$ meeting the three
above conditions. By $G^{\prime}_{l}$ we denote $G_{1}\cup\ldots\cup G_{l}$.
Clearly, $G^{\prime}_{k}=G$. We will use induction on $l$ to prove that
$(G^{\prime}_{l}$, $\sigma|_{E(G^{\prime}_{l})})$ is $\Delta(G)$-edge-
colorable. Let us observe that $G^{\prime}_{1}$ is a cycle or path, so
$(G^{\prime}_{1}$, $\sigma|_{E(G^{\prime}_{1})})$ can be colored using
$\Delta(G)\geq 3$ colors. Let’s assume that $(G^{\prime}_{l}$,
$\sigma|_{E(G^{\prime}_{l})})$ is $\Delta(G)$-edge-colorable for any $l<x$. We
will show that $(G^{\prime}_{x}$, $\sigma|_{E(G^{\prime}_{x})})$ can be
colored using at most $\Delta(G)$ colors. Let us note that
$G^{\prime}_{x}=G^{\prime}_{x-1}\cup G_{x}$ and $(G^{\prime}_{x-1}$,
$\sigma|_{E(G^{\prime}_{x-1})})$ is $\Delta(G)$-edge-colorable. By $c$ we
denote an arbitrary $\Delta(G)$-edge-coloring of $(G^{\prime}_{x-1}$,
$\sigma|_{E(G^{\prime}_{x-1})})$. It follows from the definition of the
decomposition of $G$ that $G_{x}$ is either a path $P_{2}$ or a cycle and
$G_{x}$ has exactly one vertex in common with $G^{\prime}_{x-1}$. Let us
consider the two cases separately.

  1. 1.

$G_{x}$ is a path $P_{2}$. By $u$, $v$ we denote vertices of $G_{x}$ and
without loss of generality we assume $u\in V(G^{\prime}_{x-1})$. Clearly,
there are at most $\Delta(G)-1$ edges incident to $u$ in $G^{\prime}_{x-1}$,
so there must be a color $\alpha\in M_{\Delta(G)}$ not used on any of these
edges by $c$. Let’s color $u\colon uv$ with $\alpha$ and $v\colon uv$ with
$-\sigma(uv)\alpha$. That way $(G^{\prime}_{x}$,
$\sigma|_{E(G^{\prime}_{x})})$ can be colored using $\Delta(G)$ colors.

  2. 2.

$G_{x}$ is a cycle. By $u\in V(G_{x})$ we denote a vertex such that $u\in
V(G^{\prime}_{x-1})$. By $uv_{1}$, $uv_{2}$ we denote two different edges of
$G_{x}$. Clearly, there are at most $\Delta(G)-2$ edges incident to $u$ in
$G^{\prime}_{x-1}$, so there must be two different colors $\alpha$, $\beta\in
M_{\Delta(G)}$ not used on any of these edges by $c$. Let us consider three
possible subcases.

    1. (a)

$\alpha=-\beta$ and $\Delta(G)=3$. Since $\Delta(G)=3$, $0\in M_{\Delta(G)}$
and $\alpha\neq 0$, $\beta\neq 0$. By $w$ we denote vertex in $G_{x}$ such
that $w$ is adjacent to $v_{1}$ and $w\neq u$. Incidences $v_{1}\colon v_{1}w$
and $w\colon v_{1}w$ of $G^{\prime}_{x}$ can be colored with color $0$. Let us
observe that other edges of $G_{x}$ form a path, so their incidences can be
colored with colors $\pm\alpha$ in the coloring of $(G^{\prime}_{x}$,
$\sigma|_{E(G^{\prime}_{x})})$.

    2. (b)

$\alpha=-\beta$ and $\Delta(G)>3$. Since $\Delta(G)>3$, there must be colors
$\gamma$, $-\gamma\in M_{\Delta(G)}$ such that $\gamma\neq 0$,
$\gamma\neq\alpha$, $\gamma\neq\beta$. Let us observe that edges $v_{1}u$,
$uv_{2}$ form a path in $G_{x}$, so their incidences can be colored with
colors $\pm\alpha$ in the coloring of $(G^{\prime}_{x}$,
$\sigma|_{E(G^{\prime}_{x})})$. Other edges of $G_{x}$ also form a path—can be
colored with colors $\pm\gamma$.

    3. (c)

$\alpha\neq-\beta$. Without loss of generality let us assume $\beta\neq 0$.
Incidence $u\colon uv_{1}$ can be colored with $\alpha$ in the coloring of
$(G^{\prime}_{x}$, $\sigma|_{E(G^{\prime}_{x})})$ and $v_{1}\colon
uv_{1}$—with $-\sigma(uv_{1})\alpha$. Edges of $G_{x}$ other than $uv_{1}$
form a path and can be colored with $\pm\beta$ in such a way that $u\colon
uv_{2}$ gets color $\beta$.

∎

$u$$v_{1}$$v_{2}$$w$$\alpha$$\pm\alpha$$-\alpha$$\pm\alpha$$0$$0$$\alpha$,
$-\alpha$Case 2a

$u$$v_{1}$$v_{2}$$\alpha$$\pm\alpha$$-\alpha$$\pm\alpha$$\gamma$,
$-\gamma$Case 2b

$u$$v_{1}$$v_{2}$$\alpha$$\pm\alpha$$\beta$$\pm\beta$$\beta$, $-\beta$Case 2c

Figure 2: Three possible edge colorings of $(G_{x}$,
$\sigma|_{E(G^{\prime}_{x})})$ considered in the case 2 of the proof of
Theorem 6.

The decomposition of an $n$-vertex cactus can be done in $O(n)$ time. This
implies that the coloring procedure being a part of the above proof is also
linear.

##  4 Wheels

Wheel $W_{n}$ is a graph on $n$ vertices consisting of a cycle $C_{n-1}$, a
vertex $v\notin V(C_{n-1})$ and edges between $v$ and all the vertices of a
cycle $C_{n-1}$.

######  Theorem 7.

All wheels are of class $1^{\pm}$.

###### Proof.

We consider three cases separately:

  1. 1.

$n=4$. Wheel $W_{4}$ is a complete graph $K_{4}$. It’s easy to observe that
$W_{4}$ has a decomposition into three perfect matchings and edges of any two
of them create a spanning cycle. Let us consider an arbitrary signed graph
$(W_{4}$, $\sigma)$ and it’s decomposition $D$ into three perfect matchings.
If there is an odd number of negative edges in $(W_{4}$, $\sigma)$, there must
be a matching in $D$ with an odd number of negative edges. Remaining edges
create a balanced spanning cycle. In the opposite case—when there is an even
number of negative edges in $(W_{4}$, $\sigma)$, there must be a matching in
$D$ with an even number of negative edges. Remaining edges create a balanced
spanning cycle. In both cases, $(W_{4}$, $\sigma)$ has a decomposition into a
perfect matching and a balanced spanning cycle. Obviously, $W_{4}$ is
$3$-regular, so it follows from Lemma 2 that $(W_{4}$, $\sigma)$ is
$\Delta$-edge-colorable.

  2. 2.

$n=2k+1$, $k\geq 2$. Let $V(W_{n})=\\{u$, $v_{0}$, …, $v_{n-2}\\}$ and
$E(G)=\\{uv_{0}$, …, $uv_{n-2}\\}\cup\\{v_{0}v_{1}$, $v_{1}v_{2}$, …,
$v_{n-2}v_{0}\\}$. For $0\leq i\leq k-2$, let $G_{i}$ be a subgraph of
$W_{n}$, such that $V(G_{i})=\\{v_{i}$, $v_{i+1}$, $u$, $v_{i+k}$,
$v_{i+k+1}\\}$ and $E(G_{i})=\\{v_{i+1}v_{i}$, $v_{i}u$, $uv_{i+k}$,
$v_{i+k}v_{i+k+1}\\}$. Clearly, $G_{i}$ is a path and for any different
$i_{1}$, $i_{2}$ paths $G_{i_{1}}$, $G_{i_{2}}$ are edge disjoint.

Let $P$ be a subgraph of $W_{n}$, such that $V(P)=\\{v_{k-1}$, $v_{k}$, $u$,
$v_{n-2}$, $v_{0}\\}$ and $E(P)=\\{v_{k}v_{k-1}$, $v_{k-1}u$, $uv_{n-2}$,
$v_{n-2}v_{0}\\}$. Clearly, $P$ is a path. We will show that paths $P$,
$G_{i}$ are edge disjoint for any $0\leq i\leq k-2$. It’s sufficient to show
that $\\{v_{i}u$, $uv_{i+k}\\}\cap\\{v_{k-1}u$, $uv_{n-2}\\}=\emptyset$ and
$\\{v_{i+1}v_{i}$, $v_{i+k}v_{i+k+1}\\}\cap\\{v_{k}v_{k-1}$,
$v_{n-2}v_{0}\\}=\emptyset$. The first equality follows from the fact that
$i<k-1<i+k<n-2$. Let’s assume that the second equality is false, so one of the
following cases must hold:

    1. (a)

$v_{i+1}v_{i}=v_{k}v_{k-1}$. Impossible because $i<k-1<k$.

    2. (b)

$v_{i+1}v_{i}=v_{n-2}v_{0}$. Impossible because $i<i+1<n-2$.

    3. (c)

$v_{i+k}v_{i+k+1}=v_{k}v_{k-1}$. Impossible because $k-1<i+k<i+k+1$.

    4. (d)

$v_{i+k}v_{i+k+1}=v_{n-2}v_{0}$. Impossible because $i+k\neq 0$ and $i+k+1\neq
0$.

Let’s observe that
$m(\bigcup\limits_{i=0}^{k-2}G_{i})+m(P)=4(k-1)+4=4k=m(W_{n})$, so
$\bigcup\limits_{i=0}^{k-2}G_{i}\cup P=W_{n}$ and $W_{n}$ has a decomposition
into exactly $k=\Delta(W_{n})/2$ paths. It follows that any signed graph with
$W_{n}$ as an underlying graph can be colored using $\Delta(W_{n})$ colors
because edges of each path can be colored with exactly two colors.

Figure 3: The decomposition of $W_{7}$ into three paths. Distinct paths are
marked with solid, dashed and dotted lines.

  3. 3.

$n=2k$, $k\geq 3$. Let us consider wheel $W_{n-1}$. By $u$ we denote the
center vertex of $W_{n-1}$—the one with degree $\Delta(W_{n-1})$ and by
$v_{1}$, $v_{2}$ we denote arbitrary vertices adjacent to $u$ such that
$v_{1}v_{2}\in E(W_{n-1})$. It follows from the previous case that $W_{n-1}$
admits a decomposition $D$ into $k-1$ paths. We construct graph
$W_{n-1}^{\prime}$ from $W_{n-1}$ by adding new vertex $v$ and replacing edge
$v_{1}v_{2}$ by path $v_{1}$, $v$, $v_{2}$. It’s easy to observe that
$W_{n-1}^{\prime}$ also admits some decomposition $D^{\prime}$ into $k-1$
paths. It can be constructed directly from $D$—path containing edge
$v_{1}v_{2}$ in $D$ contains edges $v_{1}v$, $vv_{2}$ in $D^{\prime}$.
Clearly, graph $W_{n}$ can be obtained from $W_{n-1}^{\prime}$ by adding edge
$vu$. It follows that $W_{n}$ admits a decomposition into $k-1$ paths and a
single edge, so every signed graph with $W_{n}$ as an underlying graph can be
colored using $2k-1=\Delta(W_{n})$ colors.

$u$$v_{1}$$v$$v_{2}$ Figure 4: The decomposition of $W_{8}$ into three paths
and a single edge. Edge is marked with a bold line and distinct paths are
marked with solid, dashed and dotted lines.

∎

##  5 Necklaces

Necklace is a connected graph having a decomposition into $k\geq 2$ paths, in
which all vertices except selected two—$u$, $v$—are different. Vertices $u$,
$v$ are starting and ending vertices of all paths. If $k=2$, a necklace is a
cycle, so it’s possible that a signed graph on such necklace is negative and
requires $\Delta+1$ colors to be properly colored. We prove necklaces are
$\Delta$-colorable in all other cases.

######  Theorem 8.

Let $G$ be a necklace. If $G$ is not a cycle, then $G$ is of class $1^{\pm}$.

###### Proof.

$G$ is not a cycle, so $\Delta(G)>3$. By $D=G_{1}$, …, $G_{\Delta(G)}$ we
denote the decomposition of $G$ into paths. By $u$, $v$ we denote the starting
and ending vertices of all the paths from $D$. Without loss of generality, we
assume that $m(G_{i})\leq m(G_{i+1})$ for $1\leq i<\Delta(G)$. It follows that
if there is a path of length $1$ in $D$, it must be $G_{1}$. By $u_{i}^{j}$ we
denote a vertex belonging to path $G_{i}$ such that the distance between
$u_{i}^{j}$ and $u$ in $G_{i}$ is $j$. The definition of $v_{i}^{j}$ is
analogous. By $S=(G$, $\sigma)$ we denote an arbitrary signed graph with $G$
being its underlying graph. We consider two cases separately:

  1. 1.

$\Delta(G)=2k+1$, $k\geq 1$. We will construct necklace $S$ starting with
necklace $S_{0}$ that contains three paths from $D$—$G_{1}$, $G_{2}$, $G_{3}$
and extending it with consecutive pairs of paths. By $S_{p}$ we denote the
necklace constructed from $S_{p-1}$ by adding paths $G_{2p+2}$, $G_{2p+3}$.
Clearly, $\Delta(S_{0})=3$. We color edges $uu_{2}^{1}$, $vv_{3}^{1}$ with
color $0$. Let us observe that the remaining edges of $S_{0}$ span a path that
contains following vertices: $u_{2}^{1}$, …, $v_{2}^{1}$, $v$, $v_{1}^{1}$, …,
$u_{1}^{1}$, $u$, $u_{3}^{1}$, …, $v_{3}^{1}$. It can be colored with colors
$\pm 1$.

Necklace $S_{p}$ is constructed from $S_{p-1}$ by adding paths $G_{2p+2}$,
$G_{2p+3}$. Clearly, $\Delta(S_{p})=\Delta(S_{p-1})+2$, so there are two new
colors $\pm\alpha$ available for coloring of $S_{p}$. Let us assume there is
an edge $uu_{l}^{1}$ in $S_{p-1}$ colored with color $0$. We can color edge
$uu_{2p+2}^{1}$ with color $0$ and path $u_{l}^{1}$, $u$, $u_{2p+3}^{1}$, …,
$v_{2p+3}^{1}$, $v$, $v_{2p+2}^{1}$, …, $u_{2p+2}^{1}$ with colors
$\pm\alpha$. That way edge $uu_{l}^{1}$, previously colored with $0$, was
recolored. Let us observe that this gives us a $\Delta(S_{p})$-edge-coloring
of $S_{p}$. Let us also observe that there is still an edge incident to $u$
such that it’s colored with color $0$ in the coloring of $S_{p}$, so such an
edge must exist in the colorings of all $S_{0}$, …, $S_{p}$.

$u$$v$$u_{2}^{1}$$v_{2}^{1}$$u_{1}^{1}$$v_{1}^{1}$$u_{3}^{1}$$v_{3}^{1}$
Figure 5: Necklace $S_{0}$ considered in case 1 of the proof of Theorem 8.
Edges colored with color $0$ are marked with bold lines. Remaining edges span
a path.

  2. 2.

$\Delta(G)=2k$, $k\geq 2$. We will construct necklace $S$ starting with
necklace $S_{0}$ that contains four paths from $D$—$G_{1}$, …, $G_{4}$ and
extending it with consecutive pairs of paths. By $S_{p}$ we denote the
necklace constructed from $S_{p-1}$ by adding paths $G_{2p+3}$, $G_{2p+4}$.
Clearly, $\Delta(S_{0})=4$. Let us observe that vertices $u_{3}^{1}$, $u$,
$u_{1}^{1}$, …, $v_{1}^{1}$, $v$, $v_{2}^{1}$ span a path in $S_{0}$ and its
edges can be colored with colors $\pm 1$. We can assume that incidence
$u\colon uu_{3}^{1}$ gets color $1$. Let us observe that the remaining edges
also span a path, end its edges can be colored with colors $\pm 2$.

Necklace $S_{p}$ is constructed from $S_{p-1}$ by adding paths $G_{2p+3}$,
$G_{2p+4}$. Clearly, $\Delta(S_{p})=\Delta(S_{p-1})+2$, so there are two new
colors $\pm\alpha$ available for coloring of $S_{p}$. Let us assume there is
an incidence $u\colon uu_{l}^{1}$ in $S_{p-1}$ colored with color $1$. We can
color incidence $u\colon uu_{2p+3}^{1}$ with color $1$ and $u_{2p+3}^{1}\colon
uu_{2p+3}^{1}$—with color $-\sigma(uu_{2p+3}^{1})$. Path $u_{l}^{1}$, $u$,
$u_{2p+4}^{1}$, …, $v_{2p+4}^{1}$, $v$, $v_{2p+3}^{1}$, …, $u_{2p+3}^{1}$ can
be colored with colors $\pm\alpha$. That way incidence $u\colon uu_{l}^{1}$,
previously colored with $1$, was recolored. Let us observe that this gives us
a $\Delta(S_{p})$-edge-coloring of $S_{p}$. Let us also observe that there is
still an incidence incident to $u$ such that it’s colored with color $1$ in
the coloring of $S_{p}$, so such an incidence must exist in the colorings of
all $S_{0}$, …, $S_{p}$.

$u$$v$$u_{3}^{1}$$v_{3}^{1}$$u_{1}^{1}$$v_{1}^{1}$$u_{2}^{1}$$v_{2}^{1}$$u_{4}^{1}$$v_{4}^{1}$$1$$\pm
1$ Figure 6: Necklace $S_{0}$ considered in case 2 of the proof of Theorem 8.
Edges colored with colors $\pm 1$ are marked with bold lines. Remaining edges
are colored with colors $\pm 2$.

∎

##  6 Complete bipartite graphs

A graph is bipartite if and only if its vertices can be divided into two sets
$V_{1}$, $V_{2}$ such that each edge has endpoints in both sets. These sets
are usually called _parts_. Graph is a complete bipartite graph if and only if
it’s bipartite and for every $u\in V_{1}$, $v\in V_{2}$ there is an edge $uv$.

######  Theorem 9.

Let $r$, $t$ be positive integers and $G$ be a complete bipartite graph
$K_{r,t}$. If $r\neq t$, then $G$ is of class $1^{\pm}$.

###### Proof.

Without loss of generality, we assume that $r<t$. Let $t=2s+k$,
$s\in\mathbf{N}$ and $k\in\\{0$, $1\\}$. Let $V(G)=\\{u_{0}$, …,
$u_{r-1}\\}\cup\\{v_{0}$, …, $v_{t-1}\\}$ and $E(G)=\\{u_{i}v_{j}\colon 0\leq
i\leq r-1$, $0\leq j\leq t-1\\}$.

Let $0\leq j\leq s-1$. Let $G_{j}$ be a subgraph of $G$ such that
$V(G_{j})=\\{u_{0}$, …, $u_{r-1}\\}\cup\\{v_{2j}$, …, $v_{(2j+r)\bmod t}\\}$
and $E(G_{j})=\\{u_{i}v_{(i+2j)\bmod t}\colon 0\leq i\leq
r-1\\}\cup\\{u_{i}v_{(i+2j+1)\bmod t}\colon 0\leq i\leq r-1\\}$. Let us
observe that:

  * 1.

$\deg_{G_{j}}(u_{i})=2$ for $i=0$, …, $r-1$;

  * 2.

$\deg_{G_{j}}(v_{2j})=\deg_{G_{j}}(v_{(2j+r)\bmod t})=1$;

  * 3.

$\deg_{G_{j}}(v_{(2j+i)\bmod t})=2$ for $i=1$, …, $r-1$.

It follows from the definition of $G_{j}$ and above observations that $G_{j}$
is a path. We will show that any two distinct paths $G_{j_{1}}$, $G_{j_{2}}$
are edge disjoint. Let us assume it’s not true. Then one of the following
cases must hold for some $i_{1}$, $i_{2}\in\\{0$, …, $r-1\\}$.

$u_{0}$$u_{1}$$u_{2}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$ Figure 7: Paths $G_{0}$
(solid lines) and $G_{1}$ (dashed lines) created in the procedure of coloring
of complete bipartite graph $K_{3,4}$ described in the proof of Theorem 9.

  1. 1.

$u_{i_{1}}v_{(i_{1}+2j_{1})\bmod t}=u_{i_{2}}v_{(i_{2}+2j_{2})\bmod t}$.
Clearly, $u_{i_{1}}=u_{i_{2}}$, so $i_{1}=i_{2}$. Moreover,
$v_{(i_{1}+2j_{1})\bmod t}$ = $v_{(i_{2}+2j_{2})\bmod t}$, so $2j_{1}\equiv
2j_{2}\pmod{t}$. It follows that $0\equiv 2(j_{1}-j_{2})\pmod{t}$. Let us
consider two cases separately:

    1. (a)

$t=2s+1$. Then $t\equiv 2s+1\pmod{t}$, so $0\equiv 2s+1\pmod{t}$ and
$2s\equiv-1\pmod{t}$. We observe that if $0\equiv 2(j_{1}-j_{2})\pmod{t}$,
then $0\equiv 2s(j_{1}-j_{2})\pmod{t}$, so $0\equiv j_{2}-j_{1}\pmod{t}$ and
$j_{1}\equiv j_{2}\pmod{t}$. It follows that $j_{1}=j_{2}$, a contradiction.

    2. (b)

$t=2s$. If $0\equiv 2(j_{1}-j_{2})\pmod{t}$, then $0\equiv
2(j_{1}-j_{2})\pmod{2s}$ and $0\equiv j_{1}-j_{2}\pmod{s}$, so $j_{1}\equiv
j_{2}\pmod{s}$. It follows that $j_{1}=j_{2}$, a contradiction.

  2. 2.

$u_{i_{1}}v_{(i_{1}+2j_{1}+1)\bmod t}=u_{i_{2}}v_{(i_{2}+2j_{2}+1)\bmod t}$.
We observe that $i_{1}=i_{2}$, so $2j_{1}+1\equiv 2j_{2}+1\pmod{t}$ and then
$2(j_{1}-j_{2})\equiv 0\pmod{t}$. The remaining part of that case is identical
to the previous case and leads to a contradiction.

  3. 3.

Either $u_{i_{1}}v_{(i_{1}+2j_{1})\bmod t}=u_{i_{2}}v_{(i_{2}+2j_{2}+1)\bmod
t}$ or $u_{i_{1}}v_{(i_{1}+2j_{1}+1)\bmod t}=u_{i_{2}}v_{(i_{2}+2j_{2})\bmod
t}$. Without loss of generality, we assume that the first of two holds.
Clearly, $i_{1}=i_{2}$, so $2j_{1}\equiv 2j_{2}+1\pmod{t}$ and then
$2(j_{1}-j_{2})\equiv 1\pmod{t}$. We consider two cases separately:

    1. (a)

$t=2s+1$. Then $2s\equiv-1\pmod{t}$. Let us observe that
$2s(j_{1}-j_{2})\equiv s\pmod{t}$, so $j_{2}-j_{1}\equiv s\pmod{t}$. It’s a
contradiction because $j_{1}$, $j_{2}\in\\{0$, …, $s-1\\}$.

    2. (b)

$t=2s$. We observe that $2(j_{1}-j_{2})-1\equiv 0\pmod{2s}$, so the odd number
$2(j_{1}-j_{2})-1$ is divisible by an even number $2s$, a contradiction.

All of the cases lead to a contradiction, so paths $G_{j_{1}}$, $G_{j_{2}}$
are edge disjoint. Clearly, $\bigcup\limits_{j=0}^{s-1}G_{j}\subseteq G$. We
will continue the proof separately for two cases:

  1. 1.

$t=2s$. Since $G$ is a complete bipartite graph, $m(G)=rt=2rs$. We observe
that $m(G_{j})=2r$ for $0\leq j\leq s-1$. It follows that
$m(\bigcup\limits_{j=0}^{s-1}G_{j})=\sum\limits_{j=0}^{s-1}m(G_{j})=2rs$, so
$m(G)=m(\bigcup\limits_{j=0}^{s-1}G_{j})$. Since paths $G_{j}$ are edge
disjoint, $G=\bigcup\limits_{j=0}^{s-1}G_{j}$, so $G$ admits a decomposition
into exactly $s$ paths. Let us observe that an arbitrary signed graph with $G$
being its underlying graph can be colored with $2s=\Delta(G)$ colors, since
each path can be colored with just two colors. It completes a proof for this
case.

  2. 2.

$t=2s+1$. It’s clear that $m(G)=rt=r(2s+1)$ and
$m(\bigcup\limits_{j=0}^{s-1}G_{j})=2rs$. Let $M$ be a subgraph of $G$ such
that $V(M)=\\{u_{0}$, …, $u_{r-1}\\}\cup\\{v_{(i-1)\bmod t}\colon 0\leq i\leq
r-1\\}$ and $E(M)=\\{u_{i}v_{(i-1)\bmod t}\colon 0\leq i\leq r-1\\}$. It’s
easy to observe that all the vertices of $M$ have degree equal to $1$, so $M$
is a matching.

We will show that $E(M)\cap E(\bigcup\limits_{j=0}^{s-1}G_{j})=\emptyset$. We
assume that it’s not true. Then for some $j$ and $i_{1}$, $i_{2}\in\\{0$, …,
$r-1\\}$ one of the following cases must hold:

    1. (a)

$u_{i_{1}}v_{(i_{1}-1)\bmod t}=u_{i_{2}}v_{(i_{2}+2j)\bmod t}$. Clearly,
$i_{1}=i_{2}$. We observe that $i_{1}-1\equiv i_{2}+2j\pmod{t}$, so
$2j+1\equiv 0\pmod{t}$ and then $2js+s\equiv 0\pmod{t}$. Since $t=2s+1$,
$2s\equiv-1\pmod{t}$, so $j\equiv s\pmod{t}$. It’s a contradiction because
$j\in\\{0$, …, $s-1\\}$.

    2. (b)

$u_{i_{1}}v_{(i_{1}-1)\bmod t}=u_{i_{2}}v_{(i_{2}+2j+1)\bmod t}$. It holds
that $i_{1}-1\equiv i_{2}+2j+1\pmod{t}$, so $2j\equiv-2\pmod{t}$ and then
$2js\equiv-2s\pmod{t}$. Since $t=2s+1$, $j+1\equiv 0\pmod{t}$. It’s a
contradiction because $t=2s+1$ and $j\in\\{0$, …, $s-1\\}$.

All of the cases lead to a contradiction, so $E(M)\cap
E(\bigcup\limits_{j=0}^{s-1}G_{j})=\emptyset$.

Since $m(M)=r$, $G=E(M)\cup E(\bigcup\limits_{j=0}^{s-1}G_{j})$, $G$ admits a
decomposition into exactly $s$ paths and one matching. Let us observe that an
arbitrary signed graph with $G$ being its underlying graph can be colored with
$2s+1=\Delta(G)$ colors, since each path can be colored with two non-zero
colors and a matching can be colored with color $0$.

∎

We briefly consider complete bipartite graphs with equal parts. Complete
bipartite graph $K_{r,r}$ is an $r$-regular graph, so it follows from Lemma 2
that if $r$ is even and $K_{r,r}$ has an odd number of negative edges, it
cannot be colored using $\Delta$ colors. We hypothesize that for all other
cases, complete bipartite graphs with equal parts are $\Delta$-colorable. If
the conjecture is true, graphs with odd $r$ must have a perfect matching $M$
such that $K_{r,r}\setminus M$ have an even number of negative edges and have
a decomposition into $(r-1)/2$ spanning $2$-regular subgraphs with positive
cycles being their components.

######  Conjecture 10.

Let $r\in\mathbf{N}$ and $S$ be a signed complete bipartite graph $K_{r,r}$.
$\chi^{\prime}(S)=\Delta(S)$ if one of the following conditions holds:

  1. 1.

$r$ is odd;

  2. 2.

$r$ is even and there is an even number of negative edges in $S$.

## References

  * [1] R. Behr, Edge coloring signed graphs, Discrete Mathematics 343 (2) (2020) 111654\.
  * [2] R. Diestel, Graph Theory, Springer-Verlag Berlin Heidelberg, 2017.
  * [3] F. Harary, On the notion of balance of a signed graph, Michigan Mathematical Journal 2 (1953) 143–146.
  * [4] R. Behr, Edge coloring signed graphs (2018).
URL https://arxiv.org/abs/1807.11465

  * [5] H. M. Mulder, Julius Petersen’s theory of regular graphs, Discrete Mathematics 100 (1-3) (1992) 157–175.
  * [6] R. Janczewski, K. Turowski, An ${O}(n\log n)$ algorithm for finding edge span of cacti, Journal of Combinatorial Optimization 31 (2016) 1373–1382.


# Hierarchical Dialogue Understanding with Special Tokens and Turn-level
Attention

Xiao Liu, Jian Zhang, Heng Zhang††footnotemark: , Fuzhao Xue, Yang You
Department of Computer Science, National University of Singapore
{liuxiao, zhang.jian, zhang_heng<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
This work was done during the author’s time as a student at National
University of SingaporeEqual contributions

###### Abstract

Compared with standard text, understanding dialogue is more challenging for
machines as the dynamic and unexpected semantic changes in each turn. To model
such inconsistent semantics, we propose a _simple but effective_ Hierarchical
Dialogue Understanding model, HiDialog. Specifically, we first insert multiple
special tokens into a dialogue and propose the turn-level attention to learn
turn embeddings hierarchically. Then, a heterogeneous graph module is
leveraged to polish the learned embeddings. We evaluate our model on various
dialogue understanding tasks including dialogue relation extraction, dialogue
emotion recognition, and dialogue act classification. Results show that our
simple approach achieves state-of-the-art performance on all three tasks
above. All our source code is publicly available at
https://github.com/ShawX825/HiDialog.

##  1 Introduction

Task-oriented dialogue system (TODS) plays a key role in assisting users to
complete tasks automatically, and a well-trained model in TODS can help to
save money and time for people. Different from the formal text, dialogues
(e.g., meetings, interviews, and debates) deliver intertwined, inconsistent
semantic information, where each turn forms a unit of information gain,
fulfilling the needs of participating interlocutors. This unfavorable dynamic
is caused by speaker intent disparity, conversation progression, and abrupt
change of thought. Such dynamics in dialogue are usually ignored by large pre-
trained language models. For BERT-style pre-trained models (Devlin et al.,
2018), $[CLS]$ token is applied to model the sentence-level semantics during
pre-training. However, dialogue-level natural language understanding requires
methods to capture both intra-turn and inter-turn information. Although there
are existing works using the special tokens method to enhance dialogue
understanding, most of them involve an additional pre-training stage (Shen et
al., 2021; Li et al., 2021; Chapuis et al., 2020). Given that the cost of such
a pre-training stage grows exponentially with model size, it is unlikely that
school labs would have the resources necessary to pre-train such models on
sizable dialogue datasets. Thus, we devote ourselves to bridging the gap
between BERT-style pre-training and dialogue understanding fine-tuning,
without extra computational cost and training data.

##  2 Related Work

Multi-Turn Dialogue Understanding. Various tasks and corresponding benchmarks
are proposed to evaluate the capacities of dialogue understanding models.
Dialogue-based relation extraction (RE) is a classification task that assigns
a pair of entities a relation label in a dialogue. Focusing on the word level,
Xue et al. (2021) constructed a multi-view graph with words in the dialogue as
nodes and proposed Dynamic Time Warping Pooling to automatically select words
in interest. SimpleRE (Xue et al., 2022) designed a novel input sequence
format and utilized a Relation Refinement Gate to filter the semantic
representation which is later fed into the classifier. TUCORE-GCN (Zahiri &
Choi, 2018) used a heterogeneous dialogue graph to encode the interaction
between speakers, arguments, and turns across the dialogues.

Emotion Recognition in Conversation (ERC) has been extensively studied in the
research community. It aims to attach an emotional label to every turn in a
given dialogue. Kratzwald et al. (2018) customized the recurrent neural
network with bidirectional processing to solve the problem of emotion
classification. Majumder et al. (2019) leveraged the Recurrent Neural Network
to extract the information of the party states and use it to predict the
emotion in conversations with two speakers. On top of the recurrent neural
network, COSMIC Ghosal et al. (2020) models the commonsense knowledge, mental
states, events, and actions to enhance emotion detection in dialogue.

Deep learning-based methods have been extensively studied in recent works (Lee
& Dernoncourt, 2016; Chen et al., 2018; Raheja & Tetreault, 2019) regarding
Dialogue Act classification (DAC). Chen et al. (2018) introduced a relation
layer into the shared hierarchical encoder to model the interaction between
the tasks of dialog act recognition and sentiment classification.

Context-Aware Representation Learning. To address dynamics and semantic
changes in multi-turn dialogue, previous works extend pre-trained large
language models to learn context-aware representations for turns (Lee & Choi,
2021; Shen et al., 2021; Li et al., 2021; Chapuis et al., 2020). TUCORE-GCN
(Lee & Choi, 2021) proposes the turn attention module, masking out distant
turns to learn the contextual embeddings. Instead of adding extra modules,
DialogXL (Shen et al., 2021) targets the encoder and incorporates four self-
attention mechanisms to different attention heads to capture diverse dialog-
aware information. Similarly, such dialogue-oriented self-attention can also
be found in MDFN (Liu et al., 2021) where it is defined as utterance-aware and
speaker-aware channels. However, most of them involve an additional pre-
training stage (Shen et al., 2021; Li et al., 2021; Chapuis et al., 2020).

##  3 Method

Problem Formulation. The dialogue understanding task aims at building a model
$f$ that can make a prediction on a query text given a dialogue. Specifically,
the input includes a multi-turn dialogue $(\\{s_{i}:t_{i}|i\in[1,m]\\})$, and
a query text $q$ with $k$ arguments $(q_{1},q_{2},...,q_{k})$, where
$i$,$s_{i}$,$t_{i}$ denotes $i^{th}$ turn, the corresponding speaker ID and
text. The output is predicted class $\hat{y}$ of the query text $q$.

Input Module. For a given multi-turn dialogue $d$ and a query $q$, we follow
Yu et al. (2020) to reconstruct $d$ as
$\hat{d}=\\{\zeta(s_{i}):t_{i}|i\in[0,m]\\}$, and the arguments in query $q$
as $\hat{q}_{j}=\zeta(a_{j})$, where $\zeta(\cdot)$ maps token $x_{i}$ and
argument $q_{j}$ to a special token $[S_{j}]$ when $x_{i}=q_{j}$. Then, we
concatenate reconstructed dialogue $\hat{d}$ and query $\hat{q}$ with a
special token $[CLS]$ and separator tokens $[SEP]$. To leverage speaker
information, we add speaker embedding (Gu et al., 2020) into our input
sequence.

Figure 1: Illustration of the proposed intra-turn modeling. In the turn-level
attention, the restriction is applied on turn-level special tokens, denoted as
$[T]$, where tokens outside the turn are masked out (colored in grey).

Intra-turn Modeling. Prior approaches have leveraged either a global $[CLS]$
token to capture sentence-level semantics (Devlin et al., 2018) or have
initialized turn embeddings by simply averaging over tokens (Lee & Choi,
2021). However, we argue that these methods have not sufficiently emphasized
the significance of certain tokens that carry crucial information (e.g.,
trigger words in DialogRE (Yu et al., 2020)), which may result in less
discriminative learned turn embeddings. To capture intra-turn information, we
insert a special token $\tau_{i}$ ahead of each turn $t_{i}$ and arguments,
where a weighted sum of token embeddings can be learned by the self-attention
mechanism in the encoder. Moreover, turn-level attention is proposed to avoid
these special tokens functioning as standard special tokens. Specifically,
tokens not belonging to a certain turn $t_{i}$ are masked out for their
corresponding turn-level special token $\tau_{i}$. This approach compels each
turn-level special token to act as an information aggregator of its own turn.
Note that a global $[CLS]$ token is placed ahead of the whole sequence, these
two types of special tokens then form a hierarchical way to gather information
in the encoder module. The proposed intra-turn modeling is illustrated in
figure 1.

Inter-turn Modeling. To model the interaction between turns and entities, we
establish a heterogeneous graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ from
the output of the encoder. $\mathcal{G}$ contains three types of nodes:
dialogue node, turn node, and argument node. The embedding of each node is
initialized from the corresponding special token, i.e., global classification
token $h_{[CLS]}$ for dialogue node, turn-level classification tokens
$h_{\tau}$ for turn nodes, and argument nodes. We follow Lee & Choi (2021) to
establish four different types of edges in graph $\mathcal{G}$: Dialogue edge,
to learn global information across the whole dialogue, all turn nodes are
connected to the dialogue node; Speaker edge, every pair of turn nodes belongs
to the same speaker are connected; Entity edge, an argument node is connected
to a turn node if it is mentioned in this turn. To enable the model to
directly learn the sequence information, every pair of turn nodes in a graph
is connected via sequence edge. To enable nodes to gather information from
their neighbors through different types of edges, we apply Graph Transformer
Network (Yun et al., 2019) to further polish the turn embeddings. To enable
nodes to gather information via different types of edges, we apply Graph
Transformer Network (Yun et al., 2019) to further polish the turn embeddings.

Classification. Dialogue and argument nodes obtained from $\mathcal{G}$ are
concatenated and fed into a linear classifier to generate the final
prediction. Cross entropy loss is used as the object function.

Method | DialogRE-Dev | DialogRE-Test | MELD
---|---|---|---
$F1$ | $F1_{c}$ | $F1$ | $F1_{c}$ | $F1$
BERT | 59.4 | 54.7 | 57.9 | 53.1 | 61.31
GDPNet | 61.8 | 58.5 | 60.2 | 57.3 | -
RoBERTas | 72.6 | 65.1 | 71.3 | 63.7 | 64.19
SimpleRE | - | - | 66.7 | - | -
TUCORE-GCN† | 74.3 | 67.0 | 73.1 | 65.9 | 65.36
HiDialog† |  77.8 +3.5 |  69.1 +2.1 | 77.1+4.0 | 68.2+2.3 | 66.96+1.6
Table 1: All methods performance on the DialogRE and MELD, averaged over five
runs, where the standard deviations are 0.4, 0.2, 0.4, 0.3, 0.2 respectively.
† uses RoBERTa as the encoder. Performance gains over the previous state-of-
the-art are highlighted in green.

##  4 Experiments

###  4.1 Datasets and Metrics

DialogRE (Yu et al., 2020) is a relation extraction task based on 1,788
dialogues from the Friends transcript. Each pair of arguments can be
classified as one of 36 possible relation types. For each of the 10,168 human-
annotated entity pairs, the trigger words are also provided.

EmoryNLP (Zahiri & Choi, 2018) is an emotion detection task based on 12,606
utterances from the Friends transcript. Each utterance can be classified as
one of seven emotions, e.g., joyful, scared.

DailyDialog (Li et al., 2017) is a dialogue database containing 13,118 simple
English dialogues. Each utterance can be assigned an emotion label from seven
categories (anger, surprise, etc.).

MELD (Poria et al., 2019) is an emotion detection task based on 13,000
sentences from the Friends transcript. Each utterance can be classified as one
of eight emotions, such as sad, disgust.

Method | MELD | ENLP | DDialog | MRDA | DialogRE-Test
---|---|---|---|---|---
$F1$ | $F1_{c}$
PHT | 61.90 | - | 60.14 | 92.4 | - | -
DialogXL | 62.41 | 34.73 | 54.93 | - | - | -
RoBERTas | 64.19 | 38.03 | 61.65 | 91.3 | 71.3 | 63.7
+Intra-turn | 65.64+1.45 | 38.13+0.1 | 61.83+0.28 | 91.5+0.2 | 74.4+3.1 | 66.6+2.9
Table 2: All methods performance on 5 multi-turn dialogue-based understanding
datasets: MELD, EmoryNLP, DailyDialog, MRDA, DialogRE, averaged over five
runs. Performance gains over the RoBERTas are highlighted in green.

Method | F1 | F1c
---|---|---
HiDialog | 77.1 | 68.2
w/o attention mask | 76.5 (-0.6) | 67.9 (-0.3)
w/o special tokens | 75.6 (-1.5) | 67.4 (-0.8)
only intra-turn | 74.4 (-2.7) | 66.6 (-1.6)

Table 3: Ablation Study on HiDialog components on DialogRE to evaluate the
individual effect of turn-level attention, turn-level special tokens, and
graph module.

Method | I | II | III
---|---|---|---
BERT | 42.5 | 60.7 | 65.6
GDPNet | 47.4 | 59.8 | 68.1
RoBERTas | 57.4 | 69.3 | 79.6
TUCORE-GCN | 62.3 | 71.3 | 79.9
HiDialog | 76.6 | 70.5 | 80.9
w/o graph module | 65.5 | 69.9 | 79.4

Table 4: All methods performance on DialogRE. We break down the performance
into three groups (I) asymmetric inverse relations, (II) symmetric inverse
relations, and (III) others.

MRDA (Shriberg et al., 2004) is a dialogue act task based on 75 hours of real-
life meeting transcript. Each sentence is assigned a general dialogue act
(topic change, repeat, etc.) and a specific dialogue act (apology, suggestion,
etc.).

Metrics. For DialogRE, F1 and F1c are used as evaluation metrics. F1c modifies
F1 by taking an early part of the dialogue as input Yu et al. (2020). For MELD
and EmoryNLP, we use weighted-F1 as metrics. For DailyDialog, the Micro-F1
score excluding the neutral class is used as the metric.

###  4.2 Results and Analysis

Overall Performance. We first evaluated HiDialog on the Dialogue Relation
Extract (DRE) dataset, DialogRE (Yu et al., 2020) and the Emotion Recognition
in Conversation (ERC) dataset, MELD (Poria et al., 2019). We selected BERT
(Devlin et al., 2018), GDPNet (Xue et al., 2021), RoBERTas (Yu et al., 2020),
SimpleRE (Xue et al., 2022), and TUCORE-GCN (Lee & Choi, 2021) as baselines.
As reported in Table 1, HiDialog established new state-of-the-art results on
both datasets. On the DialogRE test set, HiDialog surpassed the previous SOTA,
TUCORE-GCN, by 4% in F1 and 2.3% in F1c. On the MELD dataset, HiDialog
outperformed TUCORE-GCN by 1.5% in weighted F1.

Towards Generality. Our intra-turn modeling’s simplicity suggests its
potential as a valuable solution for enhancing dialogue understanding without
the need for extra pre-training. To assess this claim, we integrated it into
the baseline encoder without any additional components, such as an inter-turn
module or speaker embeddings. For fair comparisons, only the encoder’s global
$[CLS]$ token was used in a softmax classifier for prediction.

We conducted the experiment on 5 datasets from 3 different tasks: DRE
(DialogRE), ERC (MELD, EmoryNLP (Zahiri & Choi, 2018), DailyDialog (Li et al.,
2017)), and Dialogue Act Classification (MRDA (Shriberg et al., 2004)). We
chose RoBERTas, Pretrained Hierarchical Transformer (PHT) (Chapuis et al.,
2020), and DialogXL (Shen et al., 2021) as baselines. Compared to PHT and
DialogXL, both of which require additional pre-training to address the domain
adaption gap, the performance of proposed intra-turn modeling is surprisingly
good in all 5 datasets (Table 2).

Ablation study on components. We conducted an ablation study on DialogRE to
evaluate key components in HiDialog: turn-level attention, turn-level special
tokens, and inter-turn module (Table 3). First, after we removed the turn-
level attention mask, the performance slightly dropped. In this case, these
special tokens are able to aggregate information from the entire sequence,
thus they are not context-aware at the turn level. We experimented with
removing intra-turn modeling, resulting in only one difference from the final
HiDialog: here we used an average of corresponding token embeddings for
initialization. The $F1$ score decreases by 1.5% and the $F1_{c}$ score
declines by 0.8%.

Analysis of relations. We grouped the test set of DialogRE according to the
relation types into three subsets: (I) asymmetric, when a relation type
differs from its inversion (e.g. children and parents); (II) symmetric, when a
relation type is the same as its inversion (e.g. spouse); (III) other, when a
relation type does not have inversion (e.g. age). We compared the performance
of our model with baselines and report the results in Table 4. As we can
observe, there is a great performance increase in the asymmetric subset while
the F1 score drops moderately for symmetric relations. This trend reverses
when we remove the graph module in our method (i.e. symmetric $>$ asymmetric).

Analysis of robustness against increasing utterance length. With the
hierarchical aggregation in HiDialog, each turn-level special token is
enforced to capture intra-turn critical information regardless of the whole
dialogue. This nature enables our method to handle dialogues of various
lengths. Thus, we further divided the samples in the DialogRE test set into
six groups according to their lengths and compared HiDialog against the
previous SOTA, TUCORE-GCN. As shown in Figure 2, our method consistently
outperforms TUCORE-GCN in all groups, where the largest performance gap can be
found in the group with less than 100 tokens. Moreover, TUCORE-GCN shows a
great drop with an increase of length (i.e., from $[400,500)$ to
$[500,+\infty)$), while HiDialog maintains decent performance for long
sequences.

Figure 2: Analysis of robustness of HiDialog tackling increasing utterance
length compared to baseline TUCORE-GCN on DialogRE dataset.

##  5 Conclusion

In conclusion, our HiDialog provides a _simple yet effective_ approach to fill
the gap between general corpus pre-training and dialogue understanding,
without extra computational cost and training data while maintaining decent
performance. Therefore, we anticipate that it could serve as a compelling
baseline or plug-in module for future work in the community.

## Contribution

This work has been expanded upon from a course project that was undertaken by
the key authors, Xiao Liu, Jian Zhang, and Heng Zhang, during their time as
students at the National University of Singapore. Fuzhao Xue, the teaching
assistant, and project mentor played a role in guiding and shaping the outcome
of this work. We are grateful to Yang You for providing us with valuable
instructions and computational resources.

## Acknowledgement

Yang You’s research group is being sponsored by NUS startup grant
(Presidential Young Professorship), Singapore MOE Tier-1 grant, ByteDance
grant, ARCTIC grant, SMI grant and Alibaba grant. Our sincere appreciation
also goes out to Min-Yen Kan, our course lecturer, for his invaluable
suggestions during our enrollment.

## URM Statement

The authors acknowledge that the first author of this work meets the URM
criteria of ICLR 2023 Tiny Papers Track.

## References

  * Chapuis et al. (2020) Emile Chapuis, Pierre Colombo, Matteo Manica, Matthieu Labeau, and Chloe Clavel.  Hierarchical pre-training for sequence labelling in spoken dialog.  _arXiv preprint arXiv:2009.11152_ , 2020.
  * Chen et al. (2018) Zheqian Chen, Rongqin Yang, Zhou Zhao, Deng Cai, and Xiaofei He.  Dialogue act recognition via crf-attentive structured network.  In _The 41st international acm sigir conference on research & development in information retrieval_, pp. 225–234, 2018.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Ghosal et al. (2020) Deepanway Ghosal, Navonil Majumder, Alexander Gelbukh, Rada Mihalcea, and Soujanya Poria.  Cosmic: Commonsense knowledge for emotion identification in conversations.  _arXiv preprint arXiv:2010.02795_ , 2020.
  * Gu et al. (2020) Jia-Chen Gu, Tianda Li, Quan Liu, Zhen-Hua Ling, Zhiming Su, Si Wei, and Xiaodan Zhu.  Speaker-aware bert for multi-turn response selection in retrieval-based chatbots.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pp. 2041–2044, 2020.
  * Kratzwald et al. (2018) Bernhard Kratzwald, Suzana Ilić, Mathias Kraus, Stefan Feuerriegel, and Helmut Prendinger.  Deep learning for affective computing: Text-based emotion recognition in decision support.  _Decision Support Systems_ , 115:24–35, 2018.
  * Lee & Choi (2021) Bongseok Lee and Yong Suk Choi.  Graph based network with contextualized representations of turns in dialogue.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 443–455, 2021.
  * Lee & Dernoncourt (2016) Ji Young Lee and Franck Dernoncourt.  Sequential short-text classification with recurrent and convolutional neural networks.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 515–520, San Diego, California, June 2016. Association for Computational Linguistics.  doi: 10.18653/v1/N16-1062.  URL https://aclanthology.org/N16-1062.
  * Li et al. (2021) Lu Li, Chenliang Li, and Donghong Ji.  Deep context modeling for multi-turn response selection in dialogue systems.  _Information Processing & Management_, 58(1):102415, 2021.
  * Li et al. (2017) Yanran Li, Hui Su, Xiaoyu Shen, Wenjie Li, Ziqiang Cao, and Shuzi Niu.  Dailydialog: A manually labelled multi-turn dialogue dataset.  _arXiv preprint arXiv:1710.03957_ , 2017.
  * Liu et al. (2021) Longxiang Liu, Zhuosheng Zhang, Hai Zhao, Xi Zhou, and Xiang Zhou.  Filling the gap of utterance-aware and speaker-aware representation for multi-turn dialogue.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 13406–13414, 2021.
  * Majumder et al. (2019) Navonil Majumder, Soujanya Poria, Devamanyu Hazarika, Rada Mihalcea, Alexander Gelbukh, and Erik Cambria.  Dialoguernn: An attentive rnn for emotion detection in conversations.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pp. 6818–6825, 2019.
  * Poria et al. (2019) Soujanya Poria, Devamanyu Hazarika, Navonil Majumder, Gautam Naik, Erik Cambria, and Rada Mihalcea.  MELD: A multimodal multi-party dataset for emotion recognition in conversations.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 527–536, Florence, Italy, July 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1050.  URL https://aclanthology.org/P19-1050.
  * Raheja & Tetreault (2019) Vipul Raheja and Joel Tetreault.  Dialogue act classification with context-aware self-attention.  _arXiv preprint arXiv:1904.02594_ , 2019.
  * Shen et al. (2021) Weizhou Shen, Junqing Chen, Xiaojun Quan, and Zhixian Xie.  Dialogxl: All-in-one xlnet for multi-party conversation emotion recognition.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 13789–13797, 2021.
  * Shriberg et al. (2004) Elizabeth Shriberg, Raj Dhillon, Sonali Bhagat, Jeremy Ang, and Hannah Carvey.  The icsi meeting recorder dialog act (mrda) corpus.  Technical report, INTERNATIONAL COMPUTER SCIENCE INST BERKELEY CA, 2004\.
  * Xue et al. (2021) Fuzhao Xue, Aixin Sun, Hao Zhang, and Eng Siong Chng.  Gdpnet: Refining latent multi-view graph for relation extraction.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 14194–14202, 2021.
  * Xue et al. (2022) Fuzhao Xue, Aixin Sun, Hao Zhang, Jinjie Ni, and Eng-Siong Chng.  An embarrassingly simple model for dialogue relation extraction.  In _ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 6707–6711, 2022.  doi: 10.1109/ICASSP43922.2022.9747486.
  * Yu et al. (2020) Dian Yu, Kai Sun, Claire Cardie, and Dong Yu.  Dialogue-based relation extraction.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 4927–4940, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.444.  URL https://aclanthology.org/2020.acl-main.444.
  * Yun et al. (2019) Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim.  Graph transformer networks.  _Advances in neural information processing systems_ , 32, 2019.
  * Zahiri & Choi (2018) Sayyed Zahiri and Jinho D. Choi.  Emotion Detection on TV Show Transcripts with Sequence-based Convolutional Neural Networks.  In _Proceedings of the AAAI Workshop on Affective Content Analysis_ , AFFCON’18, pp. 44–51, New Orleans, LA, 2018.  URL https://sites.google.com/view/affcon18.