# On Rainbow Cycles and Proper Edge Colorings of Generalized Polygons

Matt Noble
Department of Mathematics and Statistics
Middle Georgia State University
<EMAIL_ADDRESS>
###### Abstract

An edge coloring of a simple graph $G$ is said to be proper rainbow-cycle-
forbidding (PRCF, for short) if no two incident edges receive the same color
and for any cycle in $G$, at least two edges of that cycle receive the same
color. A graph $G$ is defined to be PRCF-good if it admits a PRCF edge
coloring, and $G$ is deemed PRCF-bad otherwise. In recent work, Hoffman, et
al. study PRCF edge colorings and find many examples of PRCF-bad graphs having
girth less than or equal to 4. They then ask whether such graphs exist having
girth greater than 4. In our work, we give a straightforward counting argument
showing that the Hoffman-Singleton graph answers this question in the
affirmative for the case of girth 5. It is then shown that certain generalized
polygons, constructed of sufficiently large order, are also PRCF-bad, thus
proving the existence of PRCF-bad graphs of girth 6, 8, 12, and 16.

Keywords and phrases: edge coloring, rainbow subgraph, Moore graph,
generalized polygon

##  1 Introduction

All graphs will be finite and simple. The notation and terminology used will
be for the most part standard, and for clarification, one may consult any
introductory text. A few graph parameters deserve special mention, as they
will be central to our discussion. For a graph $G$, define the girth of $G$,
notated as $g(G)$, to be the minimum length of a cycle in $G$. For $a,b\in
V(G)$, the distance $d(a,b)$ is the minimum length of a path beginning at $a$
and terminating at $b$. The diameter of a connected graph $G$, which we will
notate as $diam(G)$, is equal to the maximum distance taken over all pairs of
vertices in $G$.

For a graph $G$ and a set of colors $C$, let $\varphi:E(G)\to C$ be an edge
coloring. A subgraph $H$ of $G$ is said to be rainbow (with respect to
$\varphi$) if every edge of $H$ receives a different color. Define $\varphi$
to be proper rainbow-cycle-forbidding if no two incident edges of $G$ receive
the same color (that is, $\varphi$ is proper), and no cycle in $G$, regardless
of length, is rainbow. Define a graph $G$ to be PRCF-good if it admits a PRCF
edge coloring, and deem $G$ to be PRCF-bad otherwise. Just to be clear, note
that in a PRCF edge coloring of $G$, there is no stipulation on how many
colors are actually used. For $G$ to be PRCF-good, it may be that $G$ has a
PRCF edge coloring using a number of colors equal to the chromatic index
$\chi^{\prime}(G)$, or it may be that $G$ has a PRCF edge coloring using some
other number of colors. However, for $G$ to be PRCF-bad, no matter the number
of colors used in a proper edge coloring, $G$ is guaranteed to have at least
one rainbow cycle.

In recent work [5], Hoffman, et al. study PRCF edge colorings and produce
numerous examples of PRCF-bad graphs – some of these found by computer search,
some generated through constructive methods, and some found through nothing
more than pencil and paper efforts. The complete graph $K_{3}$ is a trivial
example of a PRCF-bad graph, as is any $G$ having $K_{3}$ as a subgraph. It is
fairly easy to see that the complete bipartite graph $K_{2,4}$ is also PRCF-
bad, and we invite curious readers to take a moment to verify this fact for
themselves. A this point, it should be noted, however, that every PRCF-bad
graph given in [5] has girth equal to 3 or 4. This begs the question, does
there exist a PRCF-bad graph of girth 5? More generally, do there exist a
PRCF-bad graphs of arbitrarily large girth?

We will in our work prove that the Hoffman-Singleton graph answers the above
question in the affirmative in the case of girth 5. We will then show that the
family of generalized polygons contains PRCF-bad graphs $G$ with $g(G)=y$ for
each $y\in\\{6,8,12,16\\}$. Such graphs are well-studied in the literature,
and although their construction can be somewhat laborious to explicitly
describe, our argument showing that a generalized polygon of sufficiently
large order is indeed PRCF-bad employs nothing more than elementary counting
techniques. We will close with a few questions and observations which may
hopefully guide future efforts to answer the above question in general.

##  2 The Hoffman-Singleton Graph

The Hoffman-Singleton graph was discovered by the eponymous A. J. Hoffman and
R. R. Singleton and introduced in [4]. Although it will not be fully described
here, there are numerous sources detailing its construction (see [3], page 92
or see [8] for a visual depiction). The graph is very well-studied and many of
its parameters have been established. Here, will we be concerned with the
following aspects of the Hoffman-Singleton graph. It has order 50, it is
7-regular, it has girth 5, and it has diameter 2.

The diameter and girth of the Hoffman-Singleton graph are important. Let $G$
denote the Hoffman-Singleton graph, and consider the path $P_{4}$ appearing as
a subgraph of $G$. Let the vertex set of this path be
$\\{v_{1},v_{2},v_{3},v_{4}\\}$, labeled as in the diagram below.

Since $g(G)=5$, $v_{1}v_{4}\not\in E(G)$. As $diam(G)=2$, there exists $x\in
V(G)$ adjacent to both $v_{1}$ and $v_{4}$. Furthermore, this vertex $x$ must
be unique, as the existence of another vertex $y$ adjacent to $v_{1}$ and
$v_{4}$ would induce a 4-cycle in $G$ on vertices $v_{1},x,v_{4},y$. Putting
these observations together, we have that in $G$, every $P_{4}$ is a subgraph
of exactly one 5-cycle. This is, of course, a simple observation, but it will
be fundamental to the argument that follows.

###### Theorem 2.1

The Hoffman-Singleton graph is PRCF-bad.

###### Proof.

Let $G$ be the Hoffman-Singleton graph, and suppose to the contrary that a
PRCF edge coloring $\varphi$ has been implemented on $G$. Let $S$ be the set
of all $P_{4}$’s in $G$, and partition $S$ into subsets $R$ and $T$ where $R$
contains all $P_{4}$’s whose three edges are colored with three different
colors, and $T$ contains all $P_{4}$’s whose three edges are colored with only
two colors. In other words, with respect to $\varphi$, $R$ is the set of
rainbow $P_{4}$’s and $T$ is the set of non-rainbow $P_{4}$’s. Our goal is to
now find lower and upper bounds on the order of $T$.

Consider a subgraph $H$ of $G$, where $H$ is isomorphic to the cycle $C_{5}$.
Two edges of $H$ must receive the same color under $\varphi$, and it follows
that at least one of the five $P_{4}$’s that are subgraphs of $H$ is an
element of $T$. As previously seen, each $P_{4}$ in $G$ can be extended into
exactly one 5-cycle in $G$. This means that at least one out of every five
elements of $S$ is an element of $T$, giving us a lower bound of
$\left(\frac{1}{5}\right)|S|\leq|T|$.

Now let $e=ab$ be an arbitrary edge of $G$. As $G$ is 7-regular, let
$c_{1},\ldots,c_{6}$ be the other six edges of $G$ having endpoint $a$, and
$d_{1},\ldots,d_{6}$ be the other six edges of $G$ having endpoint $b$.
Without loss of generality, suppose $\varphi(e)=0$ and $\varphi(c_{i})=i$ for
each $i\in\\{1,\ldots,6\\}$ as is done in the figure below.

There are 36 distinct $P_{4}$’s in $G$ having $e$ as the “middle” edge. For
each $i\in\\{1,\ldots,6\\}$, there is at most one $j\in\\{1,\ldots,6\\}$ such
that $\varphi(d_{j})=i$, which means that at most 6 of those 36 $P_{4}$’s are
elements of $T$. As $e$ was arbitrary, we have the upper bound
$|T|\leq\left(\frac{1}{6}\right)|S|$.

Combining the lower and upper bounds established for $|T|$, we have
$\left(\frac{1}{5}\right)|S|\leq|T|\leq\left(\frac{1}{6}\right)|S|\implies\frac{1}{5}\leq\frac{1}{6}$.
From this contradiction, we conclude that $G$ has no PRCF edge coloring.∎∎

Define a PRCF-bad graph to be critical if all of its proper subgraphs are
PRCF-good. We close in this section by observing that the Hoffman-Singleton
graph is not critical. Again, let $G$ denote the Hoffman-Singleton graph, and
for some $v\in V(G)$, let $G^{\prime}=G\setminus\\{v\\}$. As is done in the
proof of Theorem 2.1, suppose that a PRCF edge coloring $\varphi$ has been
implemented on $G^{\prime}$, and let $S^{\prime}$ be the set of all $P_{4}$’s
in $G^{\prime}$, with $T^{\prime}\subset S^{\prime}$ the set of all $P_{4}$’s
which are non-rainbow with respect to $\varphi$.

As $G$ is a 7-regular graph of order 50, we have $|E(G)|=175$, and since each
edge of $G$ is the “middle” edge of 36 distinct $P_{4}$’s, it follows that
$|S|=36(175)=6300$. It was previously seen that each $P_{4}$ of $G$ appears as
a subgraph of exactly one 5-cycle of $G$, so $G$ contains
$\frac{6300}{5}=1260$ distinct 5-cycles. It is known that $G$ is vertex-
transitive, so from this, we conclude that, in $G$, vertex $v$ appears in
$\frac{5(1260)}{50}=126$ distinct 5-cycles. This gives us a lower bound of
$1260-126=1134\leq|T^{\prime}|$. From the proof of Theorem 2.1, we had
$|T|\leq\left(\frac{1}{6}\right)|S|=\left(\frac{1}{6}\right)\left(6300\right)=1050$,
and this upper bound for $|T|$ in $G$ is also an upper bound for
$|T^{\prime}|$ in $G^{\prime}$. Combining our bounds into one inequality, we
have the contradiction $1134\leq|T^{\prime}|\leq 1050$.

We call attention to the fact that the Hoffman-Singleton graph is not
critically PRCF-bad, because ultimately, we were unable to decide whether or
not there exists a critically PRCF-bad graph of girth 5. It seems extremely
unlikely that, in forming a critically PRCF-bad subgraph of the Hoffman-
Singleton graph, one would be forced to delete so many edges and vertices that
the resulting graph $H$ had girth $g(H)\geq 6$, and we would be interested in
seeing an argument resolving this point.

##  3 Generalized Polygons

Graphs having diameter $d$ and girth $2d+1$ (like the Hoffman-Singleton graph
where $d=2$) are called Moore graphs. This relationship between diameter and
girth was particularly convenient for the proof of Theorem 2.1 as it allowed
us to immediately find a lower bound on $|T|$. Moore graphs have been
extensively studied in the literature (see [6] for a historical perspective),
but unfortunately, they are quite rare. In light of Theorem 2.1, we now desire
to find PRCF-bad graphs of girth larger than 5, and the only Moore graphs
fitting that bill are odd cycles $C_{n}$, which for $n>3$ are PRCF-good. We
now instead turn our attention to the family of graphs known as generalized
polygons.

A generalized polygon is a graph $G$ where $diam(G)=d$ and $g(G)=2d$. In such
graphs, a vertex $v$ is referred to as being thick if $\deg(v)\geq 3$ and thin
otherwise. A thick generalized polygon is one in which every vertex is thick.
Like Moore graphs, generalized polygons are well-studied, and for background
given from a graph-theoretic standpoint, we recommend [3]. Theorem 3.1 is the
celebrated result of Feit and Higman showing the possible $d$ for which a
thick generalized polygon exists.

###### Theorem 3.1

Let $G$ be a thick generalized polygon of diameter $d$. Then
$d\in\\{2,3,4,6,8\\}$.

We will focus our discussion on two generalized polygons. The split Cayley
hexagon is bipartite, has diameter 6 and girth 12, and is regular of degree
$r$ where $r-1$ can be taken to be any prime power. The Ree-Tits octagon is
bipartite with diameter 8 and girth 16. It is semiregular, and letting $(A,B)$
be the bipartition of its set of vertices, all vertices in $A$ have degree
$q+1$ and all vertices of $B$ have degree $q^{2}+1$ where $q$ can be taken as
any odd power of 2. In Theorems 3.2 and 3.3, we will show that each of these
graphs, when $r$ and $q$ are made sufficiently large, are PRCF-bad. Each proof
will have the same outline as the proof of Theorem 2.1.

###### Theorem 3.2

A sufficiently large split Cayley hexagon is PRCF-bad.

###### Proof.

Let $G$ be a split Cayley hexagon which is regular of degree $r$. Assume that
a PRCF edge coloring $\varphi$ has been implemented on $G$. Consider a path
$P_{8}$ with vertices labeled as below.

Since $diam(G)=6$, there exists a path $P$ in $G$ beginning at $v_{8}$,
terminating at $v_{1}$, and having length less than or equal to 6. Note that
$P$ cannot contain any vertex $v_{i}$ for $i\in\\{2,\ldots,7\\}$, and as well,
$P$ cannot be of length less than or equal to 4, seeing as either of these
characteristics would violate $g(G)=12$. Also, this path $P$ cannot have
length 6 because $G$ is bipartite, and such a path would produce an odd cycle
in $G$. We conclude that $P$ has length exactly equal to 5. Furthermore, it
must be the case that $P$ is unique, as two distinct paths of length 5, each
beginning at $v_{8}$ and terminating at $v_{1}$, would imply $g(G)\leq 10$.
From these observations, we conclude that every $P_{8}$ in $G$ is a subgraph
of exactly one 12-cycle.

Let $S$ be the set of all $P_{8}$’s in $G$. Let $R\subset S$ be the set of all
$P_{8}$’s that are rainbow with respect to $\varphi$, and let $T=S\setminus R$
be the set of all $P_{8}$’s that are not rainbow. Our goal is to now find
lower and upper bounds for $\frac{|T|}{|S|}$ – that is, the proportion of
$P_{8}$’s in $G$ that are not rainbow. As $\varphi$ is a PRCF edge coloring,
each 12-cycle in $G$ must have at least two edges colored the same color. For
any two edges of $C_{12}$, there are at least two subgraphs of that $C_{12}$
which are isomorphic to $P_{8}$ and contain those two edges. From the previous
observation that every $P_{8}$ in $G$ is a subgraph of exactly one 12-cycle,
we conclude that at least two out of every twelve $P_{8}$’s in $G$ are
elements of $T$. Thus $\frac{1}{6}\leq\frac{|T|}{|S|}$.

In the proof of Theorem 2.1, we found an upper bound for $|T|$ directly. Here,
it is easier to first determine $|S|$, and then find a lower bound for $|R|$,
which will suffice for our argument since $|T|=|S|-|R|$. For any $v\in V(G)$,
the number of paths having length 7 and beginning at $v$ is given by
$r(r-1)^{6}$. It follows that $|S|=\left(\frac{1}{2}\right)|V(G)|r(r-1)^{6}$.
Note that the presence of the coefficient $\frac{1}{2}$ is to avoid counting
each $P_{8}$ twice.

To find a lower bound for $|R|$, again suppose $v\in V(G)$, and let us think
about forming a rainbow $P_{8}$ starting at $v$. There are $r$ neighbors of
$v$, and any of them may be chosen to be on the path. For any vertex $x_{1}$
in the open neighborhood $N(v)$, there are $r-1$ vertices in
$N(x_{1})\setminus\\{v\\}$ that may be chosen to continue the path. For any
vertex $x_{2}\in N(x_{1})\setminus\\{v\\}$, there are $r-1$ vertices in
$N(x_{2})\setminus\\{x_{1}\\}$, but it may be the case that for some $y\in
N(x_{2})\setminus\\{x_{1}\\}$, $\varphi(vx_{1})=\varphi(x_{2}y)$. This means
that, from $x_{2}$, there are at least $r-2$ vertices to extend the rainbow
path. Continuing in this fashion, we find a lower bound
$|R|\geq\left(\frac{1}{2}\right)|V(G)|r(r-1)(r-2)(r-3)(r-4)(r-5)(r-6)$. Note
that the coefficient $\frac{1}{2}$ prevents double counting, just as it did in
our formula for $|S|$.

We now have the following upper bound for $|T|$.

$|T|\leq|S|-\left(\frac{1}{2}\right)|V(G)|r(r-1)(r-2)(r-3)(r-4)(r-5)(r-6)$
(3.1)

Now divide each side of Inequality 3.1 by $|S|$ and simplify the right-hand
side through use of our earlier expression for $|S|$. Combining the result
with our lower bound for $\frac{|T|}{|S|}$, we arrive at Inequality 3.2.

$\frac{1}{6}\leq\frac{|T|}{|S|}\leq
1-\frac{(r-2)(r-3)(r-4)(r-5)(r-6)}{(r-1)^{5}}$ (3.2)

As $r\to\infty$, the expression on the right-hand side of Inequality 3.2 goes
to 0. In constructing a split Cayley hexagon, our only restriction on the
selection of $r$ is that $r-1$ must be a power of a prime, so we are free to
select $r$ arbitrarily large and establish a contradiction.∎∎

In the statement of Theorem 3.2, we did not say how large the order of a split
Cayley hexagon must be to actually have the graph be PRCF-bad. It turns out
that the smallest value of $r$ which results in the contradiction being
present in the proof above – that is, for the right-hand side of Inequality
3.2 to dip below $\frac{1}{6}$ – is $r=90$. The order of a 90-regular graph
$G$ with $diam(G)=6$ and $g(G)=12$ is given by the expression $\displaystyle
1+\sum_{i=0}^{5}90(89)^{i}=508,276,320,301$. Quite large indeed!

We omit proofs showing that PRCF-bad graphs exist among the families of
generalized polygons of girth 6 and 8 as they proceed similarly to the proof
of Theorem 3.2. We will, however, formally show that there exists a PRCF-bad
graph of girth 16. Theorem 3.3 will also follow the same outline as Theorem
3.2, but since the Ree-Tits octagon is not regular, the counts that are
involved are carried out slightly differently.

###### Theorem 3.3

A sufficiently large Ree-Tits octagon is PRCF-bad.

###### Proof.

Let $G$ be a Ree-Tits octagon with bipartition $(A,B)$. In other words,
$V(G)=A\cup B$ with each vertex of $A$ having degree $q+1$ and each vertex of
$B$ having degree $q^{2}+1$. Assume $\varphi$ is a PRCF edge coloring of $G$.
Let $S$ be the set of all $P_{10}$’s in $G$, with $R,T$ being the sets of
rainbow $P_{10}$’s and non-rainbow $P_{10}$’s, respectively, with respect to
$\varphi$. By the same reasoning displayed in the proof of Theorem 3.2, each
$P_{10}$ in $G$ is a subgraph of exactly one 16-cycle in $G$. Since no cycle
in $G$ is rainbow, any 16-cycle has at least two edges colored the same color
under $\varphi$, and it follows that, for any 16-cycle in $G$, at least two of
the sixteen $P_{10}$’s that are subgraphs of that 16-cycle are elements of
$T$. Hence $\frac{1}{8}\leq\frac{|T|}{|S|}$.

Note that any $P_{10}$ in $G$ has one of its two end vertices in $A$ and the
other in $B$, and furthermore, any path must alternate between vertices of $A$
and vertices of $B$. An expression for the order of $S$ is therefore given by
$|S|=|A|(q+1)(q^{2})(q)(q^{2})(q)(q^{2})(q)(q^{2})(q)=|A|q^{12}(q+1)$.

As in the proof of Theorem 3.2, we find an upper bound for $|T|$ by first
finding a lower bound for $|R|$. Here, we have
$|R|\geq|A|(q+1)(q^{2})(q-1)(q^{2}-2)(q-3)(q^{2}-4)(q-5)(q^{2}-6)(q-7)$. Our
upper bound for $|T|$ is given by Inequality 3.3.

$|T|\leq|S|-|A|(q+1)(q^{2})(q-1)(q^{2}-2)(q-3)(q^{2}-4)(q-5)(q^{2}-6)(q-7)$
(3.3)

After dividing both sides by $|S|$ and then simplifying, we may combine
Inequality 3.3 with our lower bound for $\frac{|T|}{|S|}$ to obtain Inequality
3.4.

$\frac{1}{6}\leq\frac{|T|}{|S|}\leq
1-\frac{(q-1)(q^{2}-2)(q-3)(q^{2}-4)(q-5)(q^{2}-6)(q-7)}{q^{10}}$ (3.4)

The right-hand side of Inequality 3.4 goes to 0 as $q\to\infty$, and since $q$
could be taken as any odd power of 2, we do indeed have a contradiction.∎∎

##  4 Looking Ahead

From the results of the previous two sections, we have that a PRCF-bad graph
of girth $g$ exists for all $g\in\\{3,4,5,6,8,12,16\\}$. We suppose that one
could trivially fill in the gaps in this statement by, for each
$n\in\\{7,9,10,11,13,14,15\\}$, letting $G$ be a disconnected graph with two
components, one being a PRCF-bad Ree-Tits octagon and the other being the
cycle $C_{n}$. This feels like a cheat, though. We are still drawn, however,
to the question of determining whether or not PRCF-bad graphs exist of
arbitrarily large girth. In this section, we will put together a few scattered
thoughts on how an attack on this problem may possibly proceed.

With regard to the proofs of Theorems 2.1, 3.2, and 3.3, the most convenient
aspect of the Hoffman-Singleton graph and the generalized polygons was the
fact that, in those respective graphs, all paths of a certain length could be
uniquely extended to minimum cycles. Unfortunately, there are no other Moore
graphs or thick generalized polygons to look at as we try to find PRCF-bad
graphs of girth greater than 16. Other generalized polygons – that is, those
that are not thick – are not candidates for consideration, which we will
demonstrate in Theorem 4.2. Its proof will use Lemma 4.1, which can be seen
with proof in [3]. Note that a $k$-fold subdivision of a graph $G$ is a graph
$G^{\prime}$ formed by replacing each edge of $G$ with a path of length $k+1$.
One could visualize this process of $k$-fold subdivision as simply placing $k$
vertices of degree 2 on each edge of $G$. For reference, a graph $G$ along
with its 2-fold subdivision $G^{\prime}$ is given in the figure below.

###### Lemma 4.1

A generalized polygon that is not thick is either an even cycle, the $k$-fold
subdivision of a multiple edge, or the $k$-fold subdivision of a thick
generalized polygon.

###### Theorem 4.2

Let $G$ be a generalized polygon that is not thick. Then $G$ is PRCF-bad if
and only if $G$ is isomorphic to the complete bipartite graph $K_{2,n}$ for
some $n\geq 4$.

###### Proof.

Lemma 4.1 categorizes those generalized polygons that are not thick. Even
cycles are PRCF-good. Note that if $H$ is any graph, and $G$ is a $k$-fold
subdivision of $H$ for some $k\geq 2$, then $G$ is guaranteed to be PRCF-good.
To see this, for each path of length $k+1$ in $G$ that replaced an edge of
$H$, choose two adjacent vertices of degree 2, and color the edge containing
them red. In any proper edge coloring of $G$ which has those edges colored
red, all cycles will have two or more red edges.

Now suppose that $G$ is a 1-fold subdivision of a thick generalized polygon
$P$. Let $diam(P)=d$ and $g(P)=2d$. Consider a breadth-first search tree of
$P$ rooted at some $v\in V(P)$. Label the levels of this tree as
$L_{0},\ldots,L_{d}$ where $L_{0}=\\{v\\}$, $L_{1}=N(v)$,
$L_{2}=N(L_{1})\setminus\\{v\\}$, and so on. For any edge $xy$ in $P$, let
$z_{x,y}\in V(G)$ be the vertex of degree 2 that is adjacent to each of $x,y$.
Consider all edges of the form $z_{x,y}y$ where $x\in L_{i}$ and $y\in
L_{i+1}$ with $i\in\\{0,\ldots,d-2\\}$. Place a partial edge coloring on $G$
by coloring these edges all the same color, say $c_{1}$. This partial coloring
is proper as none of these edges are incident, and it guarantees that, should
it be extended to a full edge coloring of $G$, no vertex of
$L_{0}\cup\cdots\cup L_{d-2}$ will be contained by a rainbow cycle in $G$. We
may then delete from $G$ all vertices of $L_{0}\cup\cdots\cup L_{d-2}$ to form
a new graph $G^{\prime}$. We then choose a new $v\in V(G^{\prime})$ and repeat
the above process, this time using color $c_{2}$. Continuing in this manner,
we see that no vertex of $G$ will appear in a rainbow cycle.

Finally, note that if $G$ is a 1-fold subdivision of a multiple edge, $G$ is
isomorphic to $K_{2,n}$. It is seen in [5] that $K_{2,n}$ is PRCF-bad if and
only if $n\geq 4$.∎

∎

So where to look now? Ideally, we would be able to adapt the line of proof
used in Theorems 2.1, 3.2, and 3.3 to find PRCF-bad graphs of larger girth,
and it seems a good bet to focus our attention on the family of graphs known
as cages. An $(r,g)$-cage is defined to be a graph of minimum order among all
$r$-regular graphs of girth $g$. Such graphs are shown to exist for all $r\geq
2$, $g\geq 3$ in [7]. In the literature, the order of an $(r,g)$-cage is
typically denoted $n(r,g)$. See [1] for an expansive history.

The method of proof used in Theorems 2.1, 3.2, and 3.3 essentially consisted
of two parts. Once it was assumed that a graph $G$ had been given a PRCF edge
coloring $\varphi$, we defined $S$ to be the set of all paths $P_{k}$ in $G$
of a certain length, and let $T\subset S$ contain all non-rainbow paths. If
this method is to be generalized, note that $k$ would be equal to
$\frac{g+3}{2}$ when $g$ is odd and $\frac{g+4}{2}$ when $g$ is even. Our two
tasks were to find lower and upper bounds for the order of $T$, eventually
reaching a contradiction. If $G$ is a cage, it is by definition regular, so an
upper bound for the corresponding $|T|$ should be relatively easy to find.
When $G$ was a Moore graph or a generalized polygon as in Theorems 2.1, 3.2,
and 3.3, it was straightforward to find a lower bound for $|T|$, with the
reason being that every path $P_{k}$ was a subgraph of exactly one minimum
cycle in $G$. If instead $G$ is a cage that is not a Moore graph or
generalized polygon, this will not be the case. Each $P_{k}$ will be a
subgraph of at most one minimum cycle, but there will be some of these paths
that are not subgraphs of any minimum cycles at all. That said, since an
$(r,g)$-cage has the smallest order among all $r$-regular graphs of girth $g$,
it may be that such a graph $G$ ends up having a large enough “threshold” of
minimum cycles that, should we be able to count them, a contradiction may
still present itself regarding the lower and upper bounds for $|T|$.

Unfortunately, there are a number of issues which must be addressed for the
above plan to work. First of all, not many cages are actually known. The value
$n(r,g)$ is precisely given when there exists a Moore graph or a generalized
polygon that is $r$-regular with girth $g$, and $n(r,g)$ has also been
determined for a few selections of small $r,g$. However, at this point in our
search for PRCF-bad graphs of higher girth, we require $g\geq 17$, and we also
need $r\geq g-1$. The reason for this latter condition is that a graph $G$
which is $r$-regular with $r\leq g-2$ is automatically PRCF-good. By Vizing’s
Theorem, $\chi^{\prime}(G)=r\text{ or }r+1$, and so $G$ could be properly
colored with fewer than $g(G)$ colors, thus guaranteeing that no cycle is
rainbow. At present, determination of $n(r,g)$ for any $r\geq 16$, $g\geq 17$
seems beyond the ability of the mathematical community.

In the literature, various upper bounds are given for $n(r,g)$ for general
$r,g$. The survey [1] gives a detailed compilation of many. Our second source
of difficulty comes from the fact that the methods used to describe the graphs
realizing these upper bounds are algebraic and are typically non-constructive.
It seems quite difficult to count the number of minimum cycles in such graphs.
We leave these questions for future work.

###### Question 1

In terms of $r$ and $g$, what is the maximum number of $g$-cycles among all
$(r,g)$-cages?

A precise answer to Question 1 seems well beyond our current reach, but even a
lower bound on the number of distinct $g$-cycles that can be found in an
$(r,g)$-cage may be of use in finding PRCF-bad girths of higher order.

###### Question 2

Suppose $G$ is an $(r,g)$-cage. Let $S$ be the set of all paths $P_{k}$ in $G$
where $k=\frac{g+3}{2}$ if $g$ is odd and $k=\frac{g+4}{2}$ if $g$ is even.
Let $S_{0}\subset S$ be the set of all $P_{k}$ that appear as a subgraph of
some $g$-cycle in $G$. As $r\to\infty$, is is true that
$\frac{|S_{0}|}{|S|}\to b$ for some $b>0$?

We close by remarking that if Question 2 could be answered in the affirmative,
it would likely confirm the existence of PRCF-bad graphs of arbitrarily large
girth.

## References

  * [1] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. 20 (2013), Dynamic Survey DS16.
  * [2] W. Feit and G. Higman, The nonexistence of certain generalized polygons, J. Algebra 1 (1964), 114 – 131.
  * [3] C. D. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.
  * [4] A. J. Hoffman and R. R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960), 497 – 504.
  * [5] D. G. Hoffman, P. Johnson, M. Noble, A. Owens, G. Puleo, and N. Terry, Proper rainbow-cycle-forbidding edge colorings of graphs, preprint.
  * [6] M. Miller and J. S̆irán̆, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20 (2013), Dynamic Survey DS14.
  * [7] H. Sachs, Regular graphs with given girth and restricted circuits, J. London Math. Soc. 38 (1963), 423 – 429.
  * [8] E. W. Weisstein, “Hoffman-Singleton Graph”, from Mathworld – A Wolfram Web Resource. http://mathworld.wolfram.com/Hoffman-SingletonGraph.html


#  LaTeX Author Guidelines for ICCV Proceedings

First Author
Institution1
Institution1 address
<EMAIL_ADDRESS>Second Author
Institution2
First line of institution2 address
<EMAIL_ADDRESS>
###### Abstract

The ABSTRACT is to be in fully-justified italicized text, at the top of the
left-hand column, below the author and affiliation information. Use the word
“Abstract” as the title, in 12-point Times, boldface type, centered relative
to the column, initially capitalized. The abstract is to be in 10-point,
single-spaced type. Leave two blank lines after the Abstract, then begin the
main text. Look at previous ICCV abstracts to get a feel for style and length.

##  1 Introduction

Recent development in deep neural networks, especially in convolutional neural
networks (CNN) [LeCun99CNN], has led to improved performance on perception
tasks. For instance, in the field of image classification, AlexNet
[Krizhevsky2012], VGG [Simonyan2015] and ResNet [He2015] achieved ever higher
performance on ImageNet by introducing new techniques such as pooling layers,
ReLU activation [Krizhevsky2012], and residual learning [He2015]. In the field
of object detection, there has also been advancement in both 2D [Girshick2015,
Girshick2013, He2017, He2015, Liu16, Redmon2015, Ren2015] and 3D
[Lang_2019_CVPR, Shi_2020_CVPR, Shi_2019_CVPR, Zhou_2018_CVPR] spaces.
However, there exists a trade-off between interpretability of a machine
learning model and its performance: simple and human-interpretable models such
as decision trees and linear classifiers cannot perform well on complex tasks,
while high-performance models are too complex to be interpreted by human. The
lack of interpretability of complex models has sparked interest in
_explainable artificial intelligence_ (XAI). The primary goal of these XAI
approaches is to uncover the logic behind the model’s decisions.

Advancements in 3D object detection is particularly important for autonomous
vehicles, as these methods can be applied to sensor data (camera and LiDAR) to
detect, localize, and classify road objects. In such safety-critical
application of deep neural networks, it would be important to understand the
logic behind the model’s decisions to gain more trust in the model.
[Selvaraju_2017_ICCV] showed one such example where a VGG-16 model used the
wrong features (facial features and hairstyle) to distinguish nurses and
doctors, such model should not be trusted even when the accuracy is high.
Recently, there has been a lot of new methods designed and applied to 2D image
classification, such as saliency map [simonyan2014deep], Deconvolution
[zeiler2013visualizing], guided-backprop [springenberg2015striving], Grad-CAM
[Selvaraju_2017_ICCV], and Integrated Gradients [IG_2017_ICML], but there have
been relatively few works in applying XAI to perception for autonomous
vehicles [Kim2017cluster, Kim2019advice, Xu2020ActionInducing,
xiong2019deformable]. To the best of our knowledge, there has been no work
dedicated to using XAI methods for model diagnoses or training specific to 3D
LiDAR-based object detection for road scenes. The closest relevant work is in
[xiong2019deformable] where guided-backprop [springenberg2015striving] was
applied to a LiDAR-based semantic segmentation network to visualize learned
features.

Motivated by the lack of research in XAI related to 3D object detection, we
generate visual explanations in the form of attribution maps for a 3D object
detector, PointPillar [Lang_2019_CVPR], create a new set of metrics to
quantify attribution concentration, and exploit these metrics for false
positive detection. _Attributions_ , in the context of XAI, denote the
influence of input or intermediate features on model output. If an input
feature has large influence on model output, then this feature would be
assigned an attribution of large magnitude and vice versa. The attribution map
for each LiDAR frame is generated using Integrated Gradients [IG_2017_ICML]
due to its axiomatic properties. We propose a set of metrics called
_Explanation Concentration_ , or _XC_ in short, which measures the
concentration of attributions within the detected object itself. It was
discovered that the true positive (TP) predictions tend to have noticeably
higher XC values than the false positive (FP) predictions. To quantify the
discriminating capability of XC, we first compute XC metrics for predictions
generated from KITTI [Geiger2012CVPR] training set and evaluate XC metrics’
performance on the binary classification task of distinguishing TP and FP
predictions. All XC metrics outperformed random scoring by a large margin,
with area under precision-recall curve (AUPR) up to 0.6676 and area under the
receiver operating characteristics curve (AUROC) up to 0.8634. These results
indicate that there is value in quantifying the concentration of attributions
and the XC metrics might be exploited for more purposes.

##  2 Related Work

This section covers related work in the field of Explainable AI (XAI), LiDAR-
based object detection, and false positive (FP) detection. The XAI technique
applied in this work is Integrated Gradients [IG_2017_ICML] (IG), and the
object detector used is PointPillars [Lang_2019_CVPR].

###  2.1 Explainable AI (XAI)

The existing XAI methods can be categorized into the following 3 types based
on the way how explanations are generated: surrogate model, perturbation
analysis, and gradient-based. The surrogate model refers to a simpler model
being used to generate explanations for a more complex black-box model. One
example is LIME [LIME2016], where a linear surrogate model is used.
Explanations may also be generated by perturbing the model input. One example
can be found in [zeiler2013visualizing], where explanation is generated by
repeatedly partially occluding the input.

Currently, the gradient-based explanation approaches are more popular than
other ones. The most simple gradient-based explanation would be an input
feature saliency map [simonyan2014deep] based on backpropagation. Unlike
backprop for training a model, where the partial derivative of the loss is
computed with respect to the model’s parameters, to generate a saliency map
matching input dimensions, one would compute the partial derivatives of the
model output with respect to the input features instead. These partial
derivatives are used as a measure of importance (also called _attributions_)
for each of the input features. Deconvolution [zeiler2013visualizing] is a
similar method which ignores negative gradients. Guided-backprop
[springenberg2015striving] combines backprop and Deconvolution to filter out
both negative activations in the forward pass and the negative gradients in
the backward pass, highlighting input features that positively influence the
model output.

For our work, we adopt Integrated Gradients (IG) [IG_2017_ICML] as the method
for generating explanations. IG uses a baseline input to help generate input
feature attributions. A baseline input does not trigger any output activation.
For image related tasks, a black image is used as a baseline. Unlike most
gradient-based explanations, [IG_2017_ICML] claimed that IG satisfies several
desirable properties, including: 1) Sensitivity: influential input features
are guaranteed to have non-zero attributions and input features which do not
influence the output are guaranteed to have zero attributions; 2)
Completeness: the sum of attributions for a certain input equals to the
difference between $f(baseline)$ and $f(input)$, where $f(\cdot)$ is the
model. One disadvantage of IG, however, is the increased computational cost
due to computing input gradients for many intermediate inputs equally spaced
out between the baseline and the input.

###  2.2 LiDAR-based Object Detection

Object detection is a more challenging task than image classification, as
there can be multiple detected objects in an image or a LiDAR point cloud, and
for each detection, both classification (for labelling the detection) and
regression (for determining the detection box parameters) need to be
performed. In 2D object detection, recent works mainly adopted two strategies:
1) A two-stage network where region proposals are generated in the first
stage, then refined and filtered into box predictions in the second stage,
R-CNN [Girshick2013] and its derivatives [Girshick2015, Ren2015, He2017] fall
into this category; 2) A single-stage network where a fixed set of anchor
boxes are filtered and refined to generate box predictions, YOLO [Redmon2015]
and SDD [Liu16] fall into this category.

Since LiDAR point cloud is scattered in a 3D space, object detection using
LiDAR data is a 3D perception problem. One popular technique for 3D object
detection is to first voxelize the 3D point cloud into either 3D grids or 2D
bird’s eye view grids, then apply 3D or 2D convolutional layers to the voxel-
wise features to learn higher level features. Techniques used for 2D object
detection, such as region proposal and anchor boxes, can then be applied to
the extracted feature maps. MV3D [chen2017MV3D], Pixor [yang2018pixor],
VoxelNet [Zhou_2018_CVPR], SeCOND [yan2018second], and PointPillars
[Lang_2019_CVPR] all partly adopted this strategy.

On the other hand, there are ways to extract features from point cloud without
voxel feature extraction or any convolutional networks. PointNet
[qi2017pointnet] learns 3D features directly from point cloud and is invariant
to point ordering, translation, and rotation. PointNet++ [qi2017pointnetpp]
further improves PointNet by capturing local structures. Recent 3D object
detectors have been using PointNet or PointNet++ as part of the network. For
example, PointRCNN [Shi_2019_CVPR] uses PointNet++ as point feature extractor,
PV-RCNN [Shi_2020_CVPR] uses PointNet++ to extract 3D convolutional features
at different scales, and PointPillars [Lang_2019_CVPR] also uses PointNet as
part of its voxel feature encoding process.

For this work, PointPillars [Lang_2019_CVPR] is selected for experiments due
to its superior performance on KITTI [Geiger2012CVPR] LiDAR dataset and its
fast inference speed. It is a 3-stage network consists of a pillar feature
net, a 2D CNN backbone, and an SSD [Liu16] as the detection head.

###  2.3 False positive detection

Several attempts have been made to effectively identify false positive (FP)
predictions. [Hendrycks2017] demonstrated that the softmax predicted class
probability could effectively distinguish true positive (TP) and false
positive (FP) predictions in various image classification, sentiment
classification, and text categorization datasets, with performance far
exceeding random guess baselines. The intuition is that the model should have
higher prediction confidence for the TP samples than for the FP ones.

On the other hand, [chen2021box] used a similar but more sophisticated
approach to suppress false positives and uncover false negatives for
pedestrian detection. They first run a pretrained model $M_{s}$ and group the
predictions into two sets, $P$ containing the boxes with softmax score
exceeding a high threshold $h$ ( 0.95), and $N$ containing the remaining
boxes. Then they 1) retrain $M_{s}$ to obtain a new model $M_{i}$ and feed
inputs from $N$ through $M_{i}$, and 2) add a cluster of new predictions
generated by $M_{i}$ with high softmax score into $P$. In essence, the boxes
are re-ranked based on softmax score in each iteration. The process is
repeated until $|P|$ meets a preset threshold. Their method was proven to be
effective in improving model performance on KITTI and Cityscapes
[Cordts2016Cityscapes].

Besides the two above mentioned works which applied techniques specifically
for detecting/suppressing FPs, there are some other works focusing on handling
adversarial attacks or detecting out-of-distribution (OOD) samples. The
techniques proposed in these works might also be applied to detect FPs. Some
notable works are feature squeezing [Xu2018squeeze], LID [Ma2018LID], and GraN
[Lust2020GraN] for detecting adversarial samples, ODIN [Liang2018ODIN] for OOD
detection, and [Lee2018Mahala] who used Mahalanobis distance to detect both
adversarial and OOD detection.

##  3 Explanation Concentration (XC)

This section describes the XC metrics in details, from how explanations for
model predictions are presented in the form of input feature attributions, to
how the degree of concentration of the attributions are summarized by the XC
metrics.

Figure 1: Overview of the XC pipeline: in Stage 1, the LiDAR point cloud is
fed through PointPillars to obtain the pseudo image representation of the
point cloud as well as the predictions; in Stage 2, IG computes feature
attribution map for the pseudo image, and XC metrics are obtained from the
attribution map and the predictions.

###  3.1 Explanation in the form of Attributions

As mentioned before in 2.1, explanation can be presented in the form of input
feature attributions, where the magnitude of the attributions indicates
feature importance. In our experiments, attributions are generated by IG
[IG_2017_ICML] for the psuedo image produced by PointPillars [Lang_2019_CVPR].
PointPillars has 3 parts as shown in 1: a pillar feature net which learns a 2D
bird’s eye view (BEV) feature map called the _psuedo image_ from the original
point cloud, a backbone 2D CNN to extract more features from the psuedo image,
and SSD [Liu16] as detection head to generate box predictions. In our
experiments, the BEV pseudo image size is $496\times 432\times 64$,
representing features learned in a cropped point cloud in a $79.36m\times
69.12m\times 4.00m\,(width\times length\times height)$ 3D space. Each pixel in
the pseudo image has 64 channels, which are features learned from all LiDAR
points in a $0.16m\times 0.16m\times 4.00m\,(width\times length\times height)$
pillar in 3D space. The attribution map generated for a pseudo image would
have the same dimensions and orientation as the pseudo image.

IG’s effectiveness on images is well-recognized, with a black image (same
dimensions as the input image, but all channel values in all pixels are set to
zero) as the baseline image. However, it is unclear how IG could be properly
applied to point cloud. Note that in an image, there are a fixed number of
pixels at fixed locations, channel values in each pixel are the only variable
features; whereas in a point cloud, in addition to the varying point intensity
values, both the quantity and location of the points can also vary greatly. IG
performs affine transformations input values before analyzing gradients
induced by the transformed input values. Due to differences in image and point
cloud data structures, IG’s input transformations may not be meaningful for
point cloud and could lead to undesirable results. Hence, we chose to generate
attributions for the pseudo image so that IG could be directly applied.

As shown in Fig. 1, the pseudo image and the PointPillars model parameters are
fed into IG to generate an attribution map, which is the same size as the
pseudo image. Values in the attributions map can be either positive or
negative, denoting positive or negative influence on model outputs, and the
magnitude corresponds to the degree of influence. Note that since the pseudo
image is the input for which IG generates attributions, the attribution map
only explains the 2D CNN and the SSD detection head’s reasoning, the pillar
feature net isn’t analyzed. There could be many predicted boxes emerging from
the same pseudo image, and each box would have a predicted score for each of
the possible class labels. To reason about the different predictions
separately, in all our experiments, each attribution map is generated for a
specific prediction and a specific class label. For example, if one wish to
get some insights as to why box 28 gets labeled as a class 2 object, one would
pass the tuple $(28,2)$ as the target for IG’s explanation. Unless otherwise
specified, for all experiments, the attribution map for each predicted box are
generate for the class with the highest prediction score. Say predicted box 28
got higher score for class 1 than for all other classes, we would use the
tuple $(28,1)$ to obtain attribution map for box 28. In Fig. 2, the
attributions generated for a car prediction is shown.

For PointPillars, we chose to use OpenPCDet’s [openpcdet2020] implementation.
The implementation of IG is from Captum [captum2020], an open source model
interpretability library developed by Facebook for PyTorch [NEURIPS2019_9015].
Since OpenPCDet uses PyTorch to build the models, Captum is a suitable choice
for the implementation of explanation methods.

Figure 2: Attribution map visualization for a car prediction. The blue boxes
in the point cloud are bounding boxes for ground truth objects. The red box in
the attribution map is the 2D projection of the car prediction bounding box.
Note that the attribution map has the same resolution as the pseudo image.

###  3.2 Evaluating the Concentration of Attributions

We propose a new set of metrics called _Explanation Concentration_ (XC) which
measure the degree of concentration of the attributions assigned to the pseudo
image for a given predicted box. Referring to Fig. 2, one can observe that
although there are a substantial number of attributions assigned to LiDAR
points within the predicted box (the large red box), some attributions are
also assigned to LiDAR points outside of the box. This indicates that some
features outside of the predicted box also contributed to the network
classifying this object as a car. In other words, sometimes the context of an
object, in addition to the object itself, influences the model’s decision. One
previous study done by [Shetty2018] demonstrated that when a 2D image
classifier relies too much on the context rather than the object of interest,
it can make many mistakes; but model performance is improved when model
dependency on context is reduced. [Shi_2019_CVPR] (citet) also did an ablation
study on their PointRCNN model and demonstrated that although small amount of
context features can be helpful, too much context information can be
detrimental. It would be interesting to see if PointPillars would also have
better performance when it does not rely heavily on the context around the
objects of interest.

Figure 3: The process of computing the XC metrics.

To quantify how much the model focuses on the object itself rather than the
context, the XC metrics are proposed. The process of computing the XC metrics
is illustrated in Fig. 3. First, denote $Pred_{i}$ as the $i^{th}$ predicted
box in an image. Then denote $a^{+}_{(x,y)}$ as the sum of positive
attributions across all 64 channels at location $(x,y)$ of the attribution map
(i.e., if a channel has attribution $<0$, then its attribution will not be
added to this sum). The _aggregated positive attributions_ in Fig. 3 represent
the $a^{+}_{(x,y)}$ values. The idea is to avoid having positive and negative
channel values cancelling each other out at a specific pixel. Note that the
attribution map has the same dimensions and orientation as the pseudo image,
thus, any $(x,y)$ location in the attribution map corresponds to the same
$(x,y)$ location in the pseudo image.

Denote $a_{thresh}$ as a pixel-wise threshold (note this is not a channel-wise
threshold) for filtering out insignificant attributions (in other words, the
sum $a^{+}_{(x,y)}$ can be called _significant_ if it exceeds $a_{thresh}$).
An indicator function $I^{+}_{(x,y)}$ can be defined such that it equals to
$1$ if $a^{+}_{(x,y)}>=a_{thresh}$, $0$ otherwise. The result of applying a
threshold to $a^{+}_{(x,y)}$ is illustrated by _filtered positive
attributions_ in Fig. 3. One way to quantify the concentration of attributions
within the predicted box $Pred_{i}$ is by summing. Two new metrics are defined
for each $Pred_{i}$ in an image:

$A\\_sum\\_in^{+}_{i}=\sum{a^{+}_{(x,y)}\times I^{+}_{(x,y)}},\ \forall(x,y)\
in\ Pred_{i}$

(1)

$A\\_sum\\_all^{+}_{i}=\sum{a^{+}_{(x,y)}\times I^{+}_{(x,y)}},\ \forall(x,y)\
in\ pseudo\;image$

(2)

$A\\_sum\\_in^{+}_{i}$ is the sum of all significant positive attributions in
a predicted box, whereas $A\\_sum\\_all^{+}_{i}$ is the sum of all significant
positive attributions across the entire pseudo image. We use a _box-wise
binary mask_ to indicate if a specific pixel is inside $Pred_{i}$ or not, as
illustrated in Fig. 3. Note that although $A\\_sum\\_all^{+}_{i}$ is summing
across the entire image, it is still a metric pertaining to $Pred_{i}$,
because the attributions are generated specifically for the box $Pred_{i}$.
Now the stage is set for defining an XC metric by summing:

$XC\\_sum^{+}_{i}=A\\_sum\\_in^{+}_{i}/A\\_sum\\_all^{+}_{i}$ (3)

$XC\\_sum^{+}_{i}$ is thus the proportion of the attributions assigned to
$Pred_{i}$ which lay within $Pred_{i}$.

The other way to quantify the concentration of attributions within $Pred_{i}$
is by counting. We are now counting the number of pixels in the pseudo image
having significant attributions, rather than summing them:

$A\\_cnt\\_in^{+}_{i}=\sum{I^{+}_{(x,y)}},\ \forall(x,y)\ in\ Pred_{i}$ (4)
$A\\_cnt\\_all^{+}_{i}=\sum{I^{+}_{(x,y)}},\ \forall(x,y)\ in\ pseudoimage$
(5) $XC\\_cnt^{+}_{i}=A\\_cnt\\_in^{+}_{i}/A\\_cnt\\_all^{+}_{i}$ (6)

The above XC metrics are for the positive attributions only. One may compute a
similar set of metrics by considering the negative attributions only, these
metrics would be denoted as $XC\\_sum^{-}_{i}$ and $XC\\_cnt^{-}_{i}$ for a
certain box $Pred_{i}$.

It was observed that, there are often many LiDAR points located close to the
boundaries of predicted boxes. As a result, IG often assigns significant
attributions to pixels at the boundary of predicted boxes (see the middle red
box in Fig. 2). It is clear that these pixels belong to the predicted object,
not to any context objects. Hence, when calculating any XC metrics, a margin
of $0.2m$ is added to all sides of the predicted box (i.e., a 1.5m by 1.7m 2D
predicted box is now enlarged to 1.9m by 2.1m), so that attributions at object
boundaries are considered as inside the predicted box in calculation.

##  4 TP and FP Detection

This section explains how TP and FP instances are defined for this study, as
well as the evaluation metrics we use to assess performance on the task of
detecting TP v.s. FP instances.

###  4.1 TP and FP Definition

In this study, the KITTI dataset [Geiger2012CVPR] is being used and
PointPillar has been configured to detect 3 classes of objects: car,
pedestrian, and cyclist. The predicted boxes are categorized as TP or FP. In
short, a TP prediction has a matching ground truth object, whereas a FP
prediction does not. The algorithm to categorize the predictions into TP and
FP is shown in Algorithm 1. Firstly, in each frame, predictions with top class
score lower than a fixed score threshold _score_thresh_ are filtered out.
Then, for each of the remaining predictions to be TP, the following conditions
need to be met: 1) there exists a ground truth box whose IoU with the
prediction exceeds a class-specific threshold; 2) that ground truth has the
same class label as the prediction. Otherwise, the prediction is FP. For our
experiments, we use a score_thresh of 0.1. 3D instead of 2D IoUs are computed
and the class-specific IoU thresholds _IoU_thresh_3d_ $=[0.5,0.25,0.25]$ for
the car, pedestrian, and cyclist predictions.

$Preds\leftarrow all\ predicted\ boxes\ in\ a\ frame$;

$GTs\leftarrow all\ ground\ truth\ boxes\ in\ a\ frame$;

$TP\leftarrow\emptyset$;

$FP\leftarrow\emptyset$;

$Ignore\leftarrow\emptyset$;

foreach  _pred ∈Preds_ do

$pred\\_scores\leftarrow class\ scores\ for\ pred$;

$pred\\_IoU\leftarrow IoU\ (pred,gt)\ \forall gt\in GTs$;

$top\\_score\leftarrow{\max}\ pred\\_scores$;

$pred\\_label\leftarrow{\operatorname*{\arg\\!\max}}\ pred\\_scores$;

$top\\_IoU\leftarrow{\max}\ pred\\_IoU$;

if  _$top\\_score >=score\\_thresh$_ then

if  _$top\\_IoU >=IoU\\_thresh\\_3d[pred\\_label]$_ then

$gt\\_id\leftarrow{\operatorname*{\arg\\!\max}}\ pred\\_IoU$;

$gt\\_label\leftarrow class\ label\ for\ gt\\_id$;

if  _$pred\\_label=gt\\_label$_ then

$\mathbf{add}\ pred\ to\ TP$;

else

$\mathbf{add}\ pred\ to\ FP$;

end if

else

$\mathbf{add}\ pred\ to\ FP$;

end if

else

$\mathbf{add}\ pred\ to\ Ignore$;

end if

end foreach

Algorithm 1 Categorizing predictions in a LiDAR frame into TP or FP.

###  4.2 Evaluation Metrics

As mentioned before in Section 2.3, the predicted score could be used to
distinguish FP and TP instances, it would be interesting to know if the XC
scores would have similar performance in the same task. In essence, the task
of detecting TP v.s. FP instances is a binary classification task. To evaluate
the performance of different scores on this task, we use area under the
precision recall curve (AUPR) [Manning1999] or area under the receiver
operating characteristics curve (AUROC) [Davis2006].

To avoid confusions, it is necessary to define some terminologies for this
TP/FP box binary classification task explicitly. First, define the TP boxes as
the _positive_ instances, and define the FP boxes as the _negative_ instances.
Now, _in the context of this binary classification task_ , true positive,
false positive, false negative, and true negatives are defined as in Table 1.
Note that these are not to be confused with the TP, FP, and TN in the object
detection context.

Table 1: Categories of predictions for binary classification

| Positive Instances | Negative Instances
---|---|---
Positive Predictions | TP | FP
Negative Predictions | FN | TN

The receiver operating characteristics (ROC) curve is a plot of the true
positive rate (TPR = TP/(TP+FN)) against the false positive rate (FPR =
FP/(FP+TN)). The ROC curve is obtained by evaluating TPR and FPR across
different thresholds. For example, one can use 0.1 as a threshold: when a box
has top class score exceeding $0.1$, it is labelled as positive, otherwise it
is labelled as negative. One can then compare the predicted labels with the
ground truth labels to obtain TPR and FPR for this specific threshold. TPR and
FPR for other thresholds can be obtained similarly to create the ROC curve.
High TPR and low FPR are desirable, but there is a trade off between TPR and
FPR: to reduce FPR by increasing the threshold, TPR would decrease too; to
improve TPR by lowering the threshold, FPR would rise too. AUROC is simply the
area under ROC curve, which is a threshold-independent performance measure for
a specific score in binary classification. Random score would have an AUROC of
$0.5$ and a perfectly performing score would have AUROC equal to $1.0$.

The precision recall (PR) curve is a plot of precision (TP/(TP+FP)) against
recall (same as TPR). Similar to the ROC curve, the PR curve can also be
obtained by computing precision and recall at different score thresholds. AUPR
is thus another threshold-independent performance measure for binary
classification. A slight difference is that when computing AUPR, among the
correct predictions, only TP are considered, whereas for AUROC, all correct
predictions are taken into account, both TP and TN. Thus AUPR places more
emphasis on correctly identifying the positive instances.

##  5 Results

We use a PointPillars [Lang_2019_CVPR] model from the OpenPCDet
[openpcdet2020] for experiments. It was trained for 80 epochs on the KITTI
[Geiger2012CVPR] dataset, with 3712 frames for training and 3769 frames for
validation.

Figure 4: $XC\\_cnt^{+}$ value and top class score different classes of
predicted boxes in the KITTI validation set. Each point represents the top
class score and the $XC\\_cnt^{+}$ value obtained from one predicted box.
Color indicates point density, red meaning dense, dark blue means sparse.

###  5.1 Distribution of XC Values

In our experiment, four XC scores are analyzed: $XC\\_sum^{+}$ and
$XC\\_cnt^{+}$ applied to the positive attributions (described in Equation 3
and Equation 6), and $XC\\_sum^{-}$ and $XC\\_cnt^{-}$ applied to the negative
attributions. These scores were obtained on the 3769 validation frames using
$a_{thresh}=0.1$. There are in total 63528 predicted boxes analyzed, of which
15633 are TP and 47895 are FP. In addition to the $XC\\_cnt^{+}$ values and
class labels for each predicted box, the top class score, distance to the
sensor, as well as the number of LiDAR points in the predicted box are also
recorded. The number of predictions and the proportion of TP vs. FP
predictions for each object class are shown in Table 2.

Table 2: Distribution of TP and FP predictions for different classes. Class | % TP | % FP | # Predicted Boxes
---|---|---|---
All | 24.61 | 75.39 | 63528
Car | 39.84 | 60.16 | 32983
Pedestrian | 7.81 | 92.19 | 23328
Cyclist | 9.30 | 90.70 | 7217

As shown in Fig. 4, for all 3 classes, there is a clear distinction between
the distribution of top class score among the TP boxes and the FP boxes, the
TP predictions tend to have a lot higher prediction scores than the FP
predictions. The same can be said for the $XC\\_cnt^{+}$ values as well. But
the Car class demonstrates the most significant difference in XC values
between TP and FP boxes, whereas such differences in XC values among TP and FP
instances in the Pedestrian and Cyclist classes are less significant. Such
difference is correlated to difference in model performance on the different
classes. For the model used in this experiment, the mAP values for the Car,
Pedestrian, and Cyclist classes are $77.28\%$, $52.29\%$, and $62.28\%$ among
the moderate difficulty objects in KITTI validation set, evaluated using 11
bins for the precision recall curves [openpcdet2020]. So the model performs
best on the Car objects, followed by Cyclist, and does the worst on
Pedestrian. It is possible that as the model gets better at detecting a class
of object, it also tends to focus more on the data inside the predicted object
itself for the high confidence predictions (usually TP), allowing LiDAR data
inside the predicted bounding box to have more influence on model output.

###  5.2 Using XC to Identify TP and FP Predictions

To compare the performance of the 4 XC scores proposed: $XC\\_sum^{+}$,
$XC\\_cnt^{+}$, $XC\\_sum^{-}$, and $XC\\_cnt^{-}$ values for each predicted
box from the KITTI validation set are computed with $a_{thresh}=0.1$, a
threshold selected based on experiments with $XC\\_cnt^{+}$ to better
distinguish TP and FP predicted boxes. The results for TP vs. FP box
classification are shown in Table 3, both the overall and the class-wise
performance are presented for each of the evaluation metrics, resulting in 16
metrics in total. Note that AUPR_op refers to the AUPR value obtained by
flipping the class labels, treating the TP predicted boxes as negative
instances and the FP predicted boxes as positive instances. In essence, AUPR
measures how good the score is at detecting the TP predicted boxes, whereas
AUPR_op measures how good the score is at detecting the FP predicted boxes.
The baseline performance refers to performance of a random score. Note that
the expected AUPR value from random score would equal to the proportion of the
positive class among the population, hence the reason why the baseline AUPR
values match the proportion of TP or FP predictions shown in Table 2.

Table 3: Comparison of $XC\\_sum^{+}$, $XC\\_cnt^{+}$, $XC\\_sum^{-}$, and
$XC\\_cnt^{-}$’s ability to classify TP and FP predictions for different
object types. The best value of each score is highlighted in bold. Note that
for FPR, lower values are more desirable, whereas for all other metrics,
higher values are preferred.

Metrics | Baseline | $XC\\_sum^{+}$ | $XC\\_cnt^{+}$ | $XC\\_sum^{-}$ | $XC\\_cnt^{-}$
---|---|---|---|---|---
AUROC All | 0.5 | 0.8362 | 0.8634 | 0.8184 | 0.8616
Car | 0.5 | 0.8439 | 0.8597 | 0.8246 | 0.8607
Pedestrian | 0.5 | 0.7052 | 0.7386 | 0.7083 | 0.7762
Cyclist | 0.5 | 0.7935 | 0.7785 | 0.8090 | 0.8167
FPR @ 0.95 TPR All | 0.95 | 0.5996 | 0.5852 | 0.5930 | 0.5371
Car | 0.95 | 0.5353 | 0.5485 | 0.5463 | 0.4977
Pedestrian | 0.95 | 0.7675 | 0.7347 | 0.7955 | 0.7184
Cyclist | 0.95 | 0.6835 | 0.7393 | 0.6476 | 0.5882
AUPR All | 0.2461 | 0.5910 | 0.6676 | 0.5465 | 0.6369
Car | 0.3984 | 0.7316 | 0.7652 | 0.7024 | 0.7572
Pedestrian | 0.0781 | 0.1492 | 0.1900 | 0.1749 | 0.2320
Cyclist | 0.0930 | 0.2446 | 0.2434 | 0.3004 | 0.3128
AUPR_op All | 0.7539 | 0.9354 | 0.9446 | 0.9307 | 0.9461
Car | 0.6016 | 0.8946 | 0.9008 | 0.8844 | 0.9055
Pedestrian | 0.9219 | 0.9643 | 0.9688 | 0.9632 | 0.9735
Cyclist | 0.9070 | 0.9687 | 0.9674 | 0.9745 | 0.9764

All 4 XC scores out-perform the baseline by a clear margin on all metrics
evaluated, indicating that XC’s ability to distinguish TP and FP predictions
is non-trivial. Also, computing XC by counting is more likely to better
distinguish the TP and FP predicted boxes than computing XC by summing.
$XC\\_cnt^{+}$ out-performs $XC\\_sum^{+}$ in 11 out of the 16 metrics, and
$XC\\_cnt^{-}$ out-performs $XC\\_sum^{-}$ in all 16 metrics. Based on visual
observation of the attribution maps, here is one possible explanation for the
difference between the summing and counting schemes: although the attributions
for the TP predictions generally are more concentrated inside the bounding box
than the attributions for FP predictions, often there are a few outlier pixels
with high attribution values outside of the bounding bounding box. When XC is
computed by counting, these outliers won’t have a big effect, because one
pixel just increment the count by 1, regardless of the attribution magnitude
for the pixel; but when XC is computed by summing, the values of these outlier
pixels can skew the resulting XC value towards the lower end, reducing the
difference between XC values for TP and FP predictions.

It is uncertain whether using positive attributions is better than using
negative attributions. $XC\\_sum^{+}$ out-performs $XC\\_sum^{-}$ in 9 out of
16 metrics, showing a slight gain by using positive instead of negative
attributions, but on the other hand $XC\\_cnt^{-}$ out-performs $XC\\_cnt^{+}$
in 13 out of the 16 metrics, which shows the advantage of using the negative
attributions. Further investigation is required to draw a concrete conclusion.

###  5.3 Using XC and Top Class Score to Identify TP and FP Predictions

It is interesting know whether combining top class score with an XC score
would have some synergistic result, producing a score that can better
distinguish the TP and FP predictions than both of the original scores. To
answer this question, an experiment using the following weighted sum
formulation has been performed:

$W\\_sum=(w\\_XC\times XC)+(w\\_cls\times top\\_class\\_score)$ (7)

The $XC$ term in Equation 7 could be any one of the 4 XC scores described in
Section 3.2. We chose to experiment with $XC\\_cnt^{+}$ and $XC\\_cnt^{-}$ due
to their superior capability in differentiating the TP and FP predictions
compare to that of $XC\\_sum^{+}$ and $XC\\_sum^{-}$. The $w\\_XC$ values vary
from 0 to 1 in 0.01 increments, and $w\\_cls$ values vary from 1 to 0 in 0.01
increments, so that $w\\_XC+w\\_cls=1$ always holds true. For both
$XC\\_cnt^{+}$ and $XC\\_cnt^{-}$, the combination of $w\\_XC$ and $w\\_cls$
which maximizes $W\\_sum$’s overall AUROC for all predicted objects is
$[0.11,0.89]$. Using $XC\\_cnt^{+}$ led to slightly better results. Hence the
results of combining $XC\\_cnt^{+}$ with top class score are shown in Table 4.

All 3 scores clearly out-performed the baseline. Although top class score
beats $XC\\_cnt^{+}$ in every single metric, when it is combined with
$XC\\_cnt^{+}$ to produce $W\\_sum$, the new score even out-performed top
class score on 12 out of the 16 metrics, and tied on 1 metric. These results
prove that synergistic effect between XC score and top class score can be
achieved. Although the effect is not very strong for the task of TP vs. FP
prediction detection, it might be a lot more pronounced in other tasks such as
training the model. Another interesting observation is that out of the 4
metrics where $W\\_sum$ under-performed or tied top class score, 3 are related
to the Pedestrian class. This is understandable as $XC\\_cnt^{+}$’s
performance on the Pedestrian class is not so great compare to its performance
on the Car class, so there is no surprise that when $XC\\_cnt^{+}$ is combined
with top class score, the synergistic effect is less on the Pedestrian
predictions than on the Car predictions.

Table 4: Comparison of top class socre, $XC\\_cnt^{+}$, and $W\\_sum$’s
ability to classify TP and FP predictions for different object types. For
$W\\_sum$, $w\\_cls$ = 0.89 and $w\\_XC$ = 0.11. The best value of each score
is highlighted in bold.

Metrics | Baseline |  Top class score | $XC\\_cnt^{+}$ | $W\\_sum$
---|---|---|---|---
AUROC All | 0.5 | 0.9683 | 0.8634 | 0.9692
Car | 0.5 | 0.9616 | 0.8597 | 0.9624
Pedestrian | 0.5 | 0.9571 | 0.7386 | 0.9569
Cyclist | 0.5 | 0.9596 | 0.7785 | 0.9600
FPR @ 0.95 TPR All | 0.95 | 0.1542 | 0.5852 | 0.1461
Car | 0.95 | 0.1905 | 0.5485 | 0.1822
Pedestrian | 0.95 | 0.2270 | 0.7347 | 0.2317
Cyclist | 0.95 | 0.2285 | 0.7393 | 0.2215
AUPR All | 0.2461 | 0.9249 | 0.6676 | 0.9250
Car | 0.3984 | 0.9458 | 0.7652 | 0.9455
Pedestrian | 0.0781 | 0.7614 | 0.1900 | 0.7640
Cyclist | 0.0930 | 0.8223 | 0.2434 | 0.8245
AUPR_op All | 0.7539 | 0.9876 | 0.9446 | 0.9883
AUPR_op Car | 0.6016 | 0.9715 | 0.9008 | 0.9731
AUPR_op Pedestrian | 0.9219 | 0.9955 | 0.9689 | 0.9955
AUPR_op Cyclist | 0.9070 | 0.9948 | 0.9674 | 0.9949

###  5.4 Training Binary Classifiers

Results evaluated so far are all obtained by performing binary classification
by applying some set threshold to a score. It would be interesting to know if
the XC scores could provide more benefit when they are used as features for a
more complex binary classifier. To answer this question, we trained 3 types of
binary classifiers: linear support vector machine (SVM), k-nearest neighbours
(KNN), and a 3-layer multi-level perceptron (MLP), all for the task of
classifying TP vs. FP predicted boxes. An ablation study on the number of box-
wise features fed into the classifier was conducted: starting training with
just the top class score for each predicted box, then incrementally introduce
the $XC\\_cnt^{+}$ value of each box, the number of LiDAR points in box, the
other 3 XC scores, class scores for all 3 object classes, distance of the
predicted box to the ego vehicle, and the class label assigned to the box as
new training features. This amounts to a maximum of 11 features for each
predicted box. In essence, the model performance when training using only the
top class score is the baseline for comparison with other settings.

Table 5: Ablation study on the features used to help classify TP vs. FP predictions. The best performance for each classifier is highlighted in bold. The term ”other features” include: distance to ego vehicle, all 3 class scores, and the predicted label of the predicted object. Features Used | Validation Accuracy
---|---
Top class score | $XC\\_cnt^{+}$ |  # Points in object |  Other 3 XC scores | Other features | Linear SVM | KNN | 3-layer MLP
✓ |  |  |  |  | 0.9285 | 0.9247 | 0.9280
✓ | ✓ |  |  |  | 0.9280 | 0.9256 | 0.9288
✓ | ✓ | ✓ |  |  | 0.9286 | 0.9259 | 0.9288
✓ | ✓ |  | ✓ |  | 0.9289 | 0.9259 | 0.9118
✓ | ✓ | ✓ | ✓ | ✓ | 0.9281 | 0.9291 | 0.9122

We did a 0.6/0.4 train/test split on the 63528 predicted boxes obtained from
the 3769 validation frames on KITTI, which leaves 38117 samples for training.
The idea is that if one particular setting produces a model that out-performs
the baseline by a large margin (e.g., 5% improvement in accuracy) on the
validation set, then this model should be tested on the left-alone test set to
further validate its effectiveness. To avoid any artifacts due to particular
frame sequences, the training samples are shuffled. For each particular
setting (a particular combination of input features, model structure, model
and optimizer hyperparameters), 5-fold cross validation is performed on the
training samples, and the average validation accuracy across the 5 different
train/validation splits is recorded to rule-out randomness in the results.
Before being fed into the model, the feature values are normalized based on:

$z=(x-\mu)/s$ (8)

where $x$ is the original feature value, $\mu$ is the feature mean and $s$ is
the feature standard deviation. The average validation accuracy values
obtained for the 3 types of models are presented in LABEL:t:classifiers. The
following paragraphs explain the experiment settings in detail.

For the linear SVM, we use the svm.LinearSVC module from scikit learn
[sklearn_api] with default hyperparameters except for the regularization term
C. The role of C in training is demonstrated by the loss function shown below:

$C\sum_{i=1,n}\mathcal{L}\left(f\left(x_{i}\right),y_{i}\right)+\Omega(w)$ (9)

One can observe that with small C, the regularization term $\Omega$ would have
a large influence on the overall loss, but with large C, $\Omega$’s
regularization effect would be diminished. The following C values are
experimented: $[0.1,0.5,1,2,5,10,20,50]$ and the average validation accuracy
of all these different settings are shown in LABEL:t:classifiers. Also note
that, for each setting, 5-fold cross validation is performed. So all the
values in the table are first averaged over 5 different train/validation
splits for each setting, then averaged over different settings.

For KNN, we use the neighbors.KNeighborsClassifier module from scikit learn
[sklearn_api] with default hyperparameters except for the number of
neighbours. We experiment with the following number of neighbours
$[5,10,20,50]$ and report the average validation accuracy.

The 3-layer MLP was built using PyTorch [NEURIPS2019_9015]. Layer 1 is of size
($\\#features\times 3$), layer 2 is ($3\times 3$), and layer 3 is ($3\times
1$). All layers are fully connected with ReLU activation applied to layer 1
and 2 outputs. The loss function is binary cross entropy loss implemented with
torch.nn.BCEWithLogitsLoss. Two runs of experiment are conducted, one with
stochastic gradient descent optimizer with momentum = 0.9 and the other one
with Adam optimizer. For both experiments, the learning rate is set to be
0.001, other hyperparameters not previously mentioned are set to default
values. The average result of the two experiments are recorded.

##  6 Conclusion

###  6.1 References

List and number all bibliographical references in 9-point Times, single-
spaced, at the end of your paper. When referenced in the text, enclose the
citation number in square brackets, for example [Authors14]. Where
appropriate, include the name(s) of editors of referenced books.

###  6.2 Illustrations, graphs, and photographs

All graphics should be centered. Please ensure that any point you wish to make
is resolvable in a printed copy of the paper. Resize fonts in figures to match
the font in the body text, and choose line widths which render effectively in
print. Many readers (and reviewers), even of an electronic copy, will choose
to print your paper in order to read it. You cannot insist that they do
otherwise, and therefore must not assume that they can zoom in to see tiny
details on a graphic.

When placing figures in LaTeX, it’s almost always best to use
`\includegraphics`, and to specify the figure width as a multiple of the line
width as in the example below

       \usepackage[dvips]{graphicx} ...
       \includegraphics[width=0.8\linewidth]
                       {myfile.eps}

###  6.3 Color

Please refer to the author guidelines on the ICCV 2021 web page for a
discussion of the use of color in your document.

##  7 Final copy

You must include your signed IEEE copyright release form when you submit your
finished paper. We MUST have this form before your paper can be published in
the proceedings.