Department of Computer Science, University of Helsinki,
Finlandshahbaz.khan@helsinki.fihttps://orcid.org/0000-0001-9352-0088
Department of Computer Science, University of Helsinki,
Finlandalexandru.tomescu@helsinki.fihttps://orcid.org/0000-0002-5747-8350
Shahbaz Khan and Alexandru I. Tomescu [500]Mathematics of computing Graph
algorithms [500]Mathematics of computing Network flows [500]Theory of
computation Network flows [500]Networks Network algorithms

###### Acknowledgements.

We thank Romeo Rizzi and Edin Husić for helpful discussions. This work was
partially funded by the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No.
851093, SAFEBIO) amd partially by the Academy of Finland (grants No. 322595,
328877). John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# Safety of Flow Decompositions in DAGs

Shahbaz Khan  Alexandru I. Tomescu

###### Abstract

Network flows are some of the most studied combinatorial optimization problems
with innumerable applications. Any flow on a directed acyclic graph (DAG) $G$
having $n$ vertices and $m$ edges can be decomposed into a set of $O(m)$
paths, with applications ranging from network routing to the assembly of
biological sequences. In some of these applications, the flow decomposition
corresponds to some particular data that need to be reconstructed from the
flow. Thus, such applications require finding paths (or subpaths) appearing in
all possible flow decompositions, referred to as safe paths.

Recently, Ma, Zheng, and Kingsford [WABI 2020] addressed a related problem in
a probabilistic framework. In a follow-up work, they gave a quadratic-time
algorithm based on a global criterion, for a generalized version (AND-Quant)
of the corresponding verification problem, i.e., reporting if a given flow
path is safe. Our contributions are as follows:

  1. 1.

A simple characterization for the safety of a given path based on a local
criterion, which can be directly adapted to give an optimal linear time
verification algorithm.

  2. 2.

A simple enumeration algorithm that reports all maximal safe paths on a flow
network in $O(mn)$ time. The algorithm reports all safe paths using a compact
representation of the solution (called ${\cal P}_{c}$), which is $\Omega(mn)$
in the worst case, but merely $O(m+n)$ in the best case.

  3. 3.

An improved enumeration algorithm where all safe paths ending at every vertex
are represented as funnels using $O(n^{2}+|{\cal P}_{c}|)$ space. These can be
computed and used to report all maximal safe paths, using time linear in the
total space required by funnels, with an extra logarithmic factor.

Overall we present a simple characterization for the problem leading to an
optimal verification algorithm and a simple enumeration algorithm. The
enumeration algorithm is improved using the funnel structures for safe paths,
which may be of independent interest.

###### keywords:

safety, flows, networks, funnel, directed acyclic graphs

###### category:

##  1 Introduction

Network flows are a central topic in computer science, with countless
practical applications. Assuming that the flow network has a unique source $s$
and a unique sink $t$, every flow can be decomposed into a collection of
weighted $s$-$t$ paths and cycles [12]. For DAGs such a decomposition contains
only paths. Such path (and cycle) view of a flow indicates how information
optimally passes from $s$ to $t$. For example, this decomposition is a key
step in network routing problems (e.g. [16, 9, 15, 23]), transportation
problems (e.g. [24, 25]), or in the more recent and prominent application of
reconstructing biological sequences (_RNA transcripts_ , see e.g. [26, 31, 14,
6, 30, 36], or _viral quasi-species genomes_ , see e.g. [3, 2]).

Finding the decomposition with the minimum number of paths (and cycles) is NP-
hard, even if the flow network is a directed acyclic graph (DAG) [33]. On the
theoretical side, this hardness result lead to research on approximation
algorithms [15, 29, 27, 23, 4, 5], and FPT algorithms [17]. On the practical
side, many approaches usually employ a standard _greedy width_ heuristic [33],
of repeatedly removing an $s$-$t$ path carrying the most amount of flow.
Another pseudo-polynomial-time heuristic was recently proposed by [28], in
connection with biological data, that tries to iteratively simplify the graph
such that the flow decomposition problem can be solved locally at some
vertices.

In the routing and transportation applications, an optimal flow decomposition
indicates how to send some information from $s$ to $t$, and thus any optimal
decomposition is satisfactory. However, this is not the case in the prominent
application of reconstructing biological sequences, since each flow path
represents a reconstructed sequence: a different optimal set of flow paths
encodes different biological sequences, which may differ from the real ones.
For a concrete example, consider the following application. In complex
organisms, a gene may produce more RNA molecules (_RNA transcripts_ , i.e.,
strings over an alphabet of four characters), each having a different
abundance. Currently, given a sample, one can read the RNA transcripts and
find their abundances using _high-throughput sequencing_ [35]. This technology
produces short overlapping substrings of the RNA transcripts. The main
approach for recovering the RNA transcripts from such data is to build an
edge-weighted DAG from these fragments and to transform the weights into flow
values by various optimization criteria, and then to decompose the resulting
flow into an “optimal” set of weighted paths (i.e., the RNA transcripts and
their abundances in the sample) [21]. Clearly, if there are multiple optimal
flow decomposition solutions, then the reconstructed RNA transcripts may not
match the original ones, and thus be incorrect.

###  1.1 Problem Definition and Related Work

Recently, Ma et al. [19] were the first to address the issue of multiple
solutions to the flow decomposition problem, under a probabilistic framework.
Later, they [20] solve a problem (_AND-Quant_), which, in particular, leads to
a quadratic-time algorithm for the following problem: given a flow in a DAG,
and edges $e_{1},e_{2},\dots,e_{k}$, decide if in _every_ flow decomposition
there is always a decomposed flow path passing through all of
$e_{1},e_{2},\dots,e_{k}$. Thus, by taking the edges $e_{1},e_{2},\dots,e_{k}$
to be the edges of a path $P$, the AND-Quant problem can decide if a path $P$
(i.e., a given biological sequence) appears in all flow decompositions. This
indicates that $P$ is likely part of some original RNA transcript.

We build upon the AND-Quant problem, by addressing the flow decomposition
problem under the _safety_ framework [32]. For a problem admitting multiple
solutions, a partial solution is said to be _safe_ if it appears in all
solutions to a problem. For example, a path $P$ is safe for the flow
decomposition problem, if for _any_ flow decomposition into paths
$\\{P_{1},\dots,P_{k}\\}$, it holds that $P$ is a subpath of some $P_{i}$. In
this paper, we will consider _any_ flow decomposition as a valid solution, not
only the ones of minimum cardinality. Dropping the minimality criterion is
motivated by both theory and practice. On the one hand, since finding one
minimum-cardinality flow decomposition is NP-hard, we believe that finding all
safe paths for them is also intractable. On the other hand, given the various
issues with sequencing data, practical methods usually incorporate different
variations of the minimum-cardinality criterion, see e.g. [6, 3, 2]. Thus,
safe paths for _all_ flow decompositions are likely correct to many practical
variations of the flow decomposition problem.

The safety framework was introduced by Tomescu and Medvedev [32] for the
genome assembly problem from bioinformatics, where e.g. a solution may be a
circular walk covering every edge of a graph at least once. Safety has
precursors in combinatorial optimization, under the name of _persistency_. For
example, persistent edges present in all maximum bipartite matching were
studied by Costa [10]. Incidentally, persistency has also been studied for the
maximum flow problem, by finding persistent edges always having a non-zero
flow value in any maximum flow solution ([8] acknowledges [18] for first
addressing the problem); which is easily verified if the maximum flow
decreases after removing the corresponding edge.

###  1.2 Our Results

Our contributions can be succinctly described as follows

  1. 1.

A simple local characterization resulting in an optimal verification
algorithm: We give a characterization for a safe path $P$ based on excess
flow, a local property of $P$.

######  Theorem 1.1.

A path $P$ is $w$-safe iff its excess flow $f_{P}\geq w>0$.

The previous work [20] on AND-Quant describes a global characterization using
the maximum flow of the entire graph transformed according to $P$, requiring
$O(mn)$ time. The excess flow is a local property of $P$ which is thus
computable in time linear in the length of $P$. This also directly gives a
simple verification algorithm which is optimal.

######  Theorem 1.2.

Given a flow graph (DAG) having $n$ vertices and $m$ edges, it can be
preprocessed in $O(m)$ time to verify the safety of any path $P$ in
$O(|P|)=O(n)$ time.

  2. 2.

Simple Enumeration Algorithm: The characterization results in a simple
algorithm for reporting all maximal safe paths using a flow decomposition of
the graph.

######  Theorem 1.3.

Given a flow graph (DAG) having $n$ vertices and $m$ edges, all its maximal
safe paths can be reported in $O(|{\cal P}_{f}|)=O(mn)$ time, where ${\cal
P}_{f}$ is some flow decomposition.

This approach starts with a candidate solution and simply uses the
characterization on its subpaths in an efficient manner (a similar approach
was previously used by [10, 1]). The solution of the algorithm is reported
using a compact representation (referred as ${\cal P}_{c}$), whose size can be
$\Omega(mn)$ is the worst case but merely $O(m+n)$ in the best case.

  3. 3.

Improved enumeration algorithm: The enumeration algorithm can be improved by
collectively considering all the safe paths ending at a vertex, which form a
unique structure called a funnel [22], that can be used to report all maximal
safe paths.

######  Theorem 1.4.

Given a flow graph (DAG) with $n$ vertices and $m$ edges, the funnel
structures for the left maximal safe paths ending at its vertices

    1. (a)

requires total $O(n^{2}+|{\cal P}_{c}|)$ space for all vertices,

    2. (b)

can be computed in $O(m\log n+n^{2}+|{\cal P}_{c}|)$ time,

    3. (c)

can be used to report all maximal safe paths in $O(n^{2}+|{\cal P}_{c}|\log
n)$ time,

where ${\cal P}_{c}$ is the concise representation of the solution.

This approach exploits the structure of the safe paths (unlike the simple
algorithm) to identify how maximal safe solutions overlap, and thus results in
efficient algorithms. This often leads to _output sensitive_ enumeration
algorithms, whose running time is parametrized by the size of the output (a
similar approach was previously used by [7]).

##  2 Preliminaries and Notations

We consider a DAG $G=(V,E)$ with $n$ vertices and $m$ edges, where each edge
$e$ has a flow $f(e)$ passing through it (also called its weight). Any two
edges are called siblings if they share either their source vertex, or their
target vertex. For each vertex $u$, $f_{in}(u)$ and $f_{out}(u)$ denotes the
total flow on its incoming edges and total flow on its outgoing edges,
respectively. A vertex $v$ in the graph is called a source if $f_{in}(v)=0$
and a sink if $f_{out}(v)=0$. Every other vertex $v$ satisfies the
conservation of flow $f_{in}(v)=f_{out}(v)$, making the graph a flow graph.

For a path $P$ in the graph, $|P|$ represents the number of its edges. For a
set of paths ${\cal P}=\\{P_{1},\cdots,P_{k}\\}$ we denote its total size
(number of edges) by $|{\cal P}|=|P_{1}|+\cdots+|P_{k}|$. Similarly, for any
subgraph ${\cal F}$ of the graph, we denote its total size (number of edges)
by $|{\cal F}|$.

For any flow graph (DAG), its flow decomposition is a set of weighted paths
${\cal P}_{f}$ such that the flow on each edge in the flow graph equals the
sum of the weights of the paths containing it. A flow decomposition of a graph
can be computed in $O(|{\cal P}_{f}|)=O(mn)$ time using the classical Ford
Fulkerson algorithm [12].

A path $P$ is called _$w$ -safe_ if, in every possible flow decomposition, $P$
is a subpath of some paths in ${\cal P}_{f}$ whose total weight is at least
$w$. If $P$ is $w$-safe with $w>0$, we call $P$ a safe flow path, or simply
safe path. Intuitively, for any edge $e$ with non-zero flow, we consider where
did the flow on $e$ come from? We would like to report the maximal path ending
with $e$ along which at least $w>0$ weight always “flows” to $e$ (see Figure
1). A safe path is left maximal (or right maximal) if extending it to the left
(or right) with any edge makes it unsafe. A safe path is maximal if it is both
left and right maximal.

Figure 1: Prefix of the blue path up to $e$ contributes at least $2$ units of
flow to $e$, as the rest may enter the path by the edges (red) with flow $4$
and $2$. Similarly, the suffix of the blue path from $e$ maintains at least
$1$ unit of flow from $e$, as the rest may exit the path from the edges (red)
with flow $5$ and $2$. Both these safe paths are maximal as they cannot be
extended left or right.

##  3 Characterization and Properties of Safe Paths

The safety of a path can be characterized by its _excess flow_ (see Figure 2),
defined as follows.

Figure 2: The excess flow of a path is the incoming or outgoing flow (blue)
that passes through the path despite the flow (red) leaking at its internal
vertices.

######  Definition 3.1 (Excess flow).

The _excess flow_ $f_{P}$ of a path $P=\\{u_{1},u_{2},...,u_{k}\\}$ is

$f_{P}=f(u_{1},u_{2})-\sum_{\begin{subarray}{c}u_{i}\in\\{u_{2},...,u_{k-1}\\}\\\
v\neq
u_{i+1}\end{subarray}}f(u_{i},v)=f(u_{k-1},u_{k})-\sum_{\begin{subarray}{c}u_{i}\in\\{u_{2},...,u_{k-1}\\}\\\
v\neq u_{i-1}\end{subarray}}f(v,u_{i})$

where the former and later equations are called diverging and converging
criterion, respectively.

The converging and diverging criteria are equivalent by the conservation of
flow on internal vertices. The idea behind the excess flow $f_{P}$ is the
amount of the incoming flow (or outgoing flow) of a path $P$ necessitates
$f_{P}$ flow to pass through $P$ despite the flow leaking on internal vertices
(Figure 2). Since the path decomposition before entering a vertex does not
affect the path decomposition on leaving a vertex, the absence of positive
excess flow renders the path unsafe. The following results give the simple
characterization and some additional properties of safe paths.

See 1.1

######  Proof 3.2.

The excess flow $f_{P}$ of a path $P$ trivially makes it $w\leq f_{P}$-safe as
it is necessitated by conservation of flow. If $f_{P}<w$, then $P$ is surely
not $w$-safe, because a path decomposition can have the paths entering $P$
which exit $P$ using out-edge of an intermediate note without passing
completely through $P$. In the worst-case, such exiting paths would leave only
$f_{P}$ flow (by definition) passing completely through $P$, which is $<w$.
Additionally, for a path to be safe, it must hold that $w>0$.

######  Lemma 3.3.

For any path in a flow graph (DAG), we have the following properties:

  1. (a)

Any subpath of a $w$-safe path is also at least $w$-safe.

  2. (b)

The converging and diverging criteria for a path $P=\\{u_{1},\cdots,u_{k}\\}$
are equivalent to

$f_{P}=\sum_{i=1}^{k-1}f(u_{i},u_{i+1})-\sum_{i=2}^{k-1}f_{out}(u_{i})=\sum_{i=1}^{k-1}f(u_{i},u_{i+1})-\sum_{i=2}^{k-1}f_{in}(u_{i}).$

  3. (c)

Adding an edge $(u,v)$ to the start, or the end, of a path reduces its excess
flow by
$f_{in}(v)-f(u,v)$, or $f_{out}(u)-f(u,v)$, respectively.

  4. (d)

A safe path starting (or ending) with an edge $e$ implies that the path
replacing $e$ with its maximum weight sibling is also safe.

  5. (e)

Two safe paths cannot merge at an intermediate vertex (or vertices) and then
diverge.

######  Proof 3.4.

  1. (a)

Since all flows are positive, any suffix subpath $P^{\prime}$ of $P$ has
$f_{P^{\prime}}\geq f_{P}$ by truncating the corresponding negative terms in
the diverging criterion of the excess flow. Similarly, any prefix subpath
$P^{\prime}$ of $P$ has $f_{P^{\prime}}\geq f_{P}$ by truncating the
corresponding negative terms in the converging criterion of the excess flow.

  2. (b)

Expanding the values of $f_{in}(u_{i})$ and $f_{out}(v_{i})$ results in the
original criteria.

  3. (c)

Using the converging criterion in b adding an edge at the start of a path
modifies its excess flow by $f(u,v)-f_{in}(v)$. Similarly, using the diverging
criterion in b adding an edge at the end of a path modifies its excess flow by
$f(u,v)-f_{out}(u)$.

  4. (d)

Let the safe path $P$ start (or end) with $e$, and consider an alternate path
that replaces $e$ with its maximum weight sibling $e^{*}$. The excess flow of
the alternate path can be computed by the diverging (or converging) criterion
to be $f_{P}-f(e)+f(e^{\prime})\geq f_{p}>0$, making it safe.

  5. (e)

Let two safe paths $P$ and $P^{\prime}$ merge at a vertex $v_{1}$, entering
$v_{1}$ respectively by $e_{1}$ and $e^{\prime}_{1}$, and then diverge at a
vertex $v_{2}$, leaving $v_{2}$ respectively by $e_{2}$ and $e^{\prime}_{2}$
(see Figure 3).

Figure 3: The diverging and converging criterion applied to path $P$ and
$P^{\prime}$ respectively.

Using Lemma 3.3a, the subpaths $\\{e_{1}\cdots,e_{2}\\}$ and
$\\{e^{\prime}_{1},\cdots,e^{\prime}_{2}\\}$ of safe paths $P$ and
$P^{\prime}$ respectively, are also safe. By diverging criterion of the safe
path $P$ we have $f(e_{1})>f(e^{\prime}_{2})$. On the other hand, by
converging criterion of the safe path $P^{\prime}$ we have
$f(e^{\prime}_{2})>f(e_{1})$, which is a contradiction.

##  4 Simple Verification and Enumeration Algorithms

The characterization of a safe path in a flow graph can be directly adapted to
simple algorithms for verification and enumeration of safe paths.

###  4.1 Verification Algorithm

The characterization (Theorem 1.1) can be directly adapted to verify the
safety of a path optimally. We preprocess the graph to compute the incoming
flow $f_{in}(u)$ and outgoing flows $f_{out}(u)$ for each vertex $u$ in total
$O(m)$ time. Using Lemma 3.3b the time taken to verify the safety of any path
$P$ is $O(|P|)=O(n)$, resulting in following theorem.

See 1.2

###  4.2 Enumeration of All Maximal Safe Paths

The maximal safe paths can be reported in $O(mn)$ time by computing a
candidate decomposition of the flow into paths, and verifying the safety of
its subpaths using the characterization and a scan with the commonly used two-
pointer approach.

The candidate flow decomposition can be computed in $O(mn)$ time using the
classical flow decomposition algorithm [12] resulting in $O(m)$ paths ${\cal
P}_{f}$ each of $O(n)$ length. Now, we compute the maximal safe paths along
each path $P\in{\cal P}_{f}$ by a two-pointer scan as follows. We start with
the subpath containing the first two edges of the path $P$. We compute its
excess flow $f$, and if $f>0$ we append the next edge to the path on the right
and incrementally compute its excess flow by Lemma 3.3c. Otherwise, if $f\leq
0$ we remove the first edge of the path from the left and incrementally
compute the excess flow similarly by Lemma 3.3c (removing an edge $(u,v)$
would conversely modify the flow by $f_{in}(v)-f(u,v)$). We stop when the end
of $P$ is reached with a positive excess flow.

The excess flow can be updated in $O(1)$ time when adding an edge to the
subpath on the right or removing an edge from the left. If the excess flow of
a subpath $P^{\prime}$ is positive and on appending it with the next edge it
ceases to be positive, we report $P^{\prime}$ as a maximal safe path by
reporting only its two indices on the path $P$. Thus, given a path of length
$O(n)$, all its maximal safe paths can be reported in $O(n)$ time, and hence
require total $O(mn)$ time for the $O(m)$ paths in the flow decomposition
${\cal P}_{f}$, resulting in the following theorem.

See 1.3

#### Concise representation

The solution can be reported using a concise representation (referred as
${\cal P}_{c}$) having a set of paths as follows. We add to ${\cal P}_{c}$
every subpath of each path $P\in{\cal P}_{f}$ that contains maximal safe
paths, along with the indices of the solution on the path. Thus, for one or
more overlapping maximal safe subpaths from $P$ we add a single path in ${\cal
P}_{c}$ which is the union of all such maximal safe paths, making the paths
added to ${\cal P}_{c}$ of minimal length. Finally, we also remove the
duplicates among the maximal safe subpaths reported from different paths in
${\cal P}_{f}$ using a Trie [11], making the set of paths in ${\cal P}_{c}$
minimal. Thus, we define ${\cal P}_{c}$ as follows.

######  Definition 4.1 (Concise representation ${\cal P}_{c}$).

A minimal set of paths having a minimal length such that every safe path of
the flow network is a subpath of some path in the set.

######  Remark 4.2.

In the worst case, the algorithm is optimal for some DAGs having $|{\cal
P}_{c}|=|{\cal P}_{f}|=\Omega(mn)$, but in general $|{\cal P}_{c}|$ can be as
small as $O(m+n)$ (see Figure 4). Thus, improving this bound requires us to
not use a flow decomposition (and hence a candidate solution).

Figure 4: The example demonstrates the worst case (left) and the best case
(right) graphs where the simple enumeration algorithm is optimal, and
inefficient, respectively. We have two paths $A=\\{a_{1},\cdots,a_{k}\\}$ and
$B=\\{b_{1},\cdots,b_{k}\\}$. The set $C=\\{c_{1},\cdots,c_{k}\\}$ has edges
from $a_{k}$ and the set $D=\\{d_{1},\cdots,d_{k}\\}$ has edges to $b_{1}$.
Choosing $k=n/4$ and any subset of connections between $C\times D$ we get a
graph with any $n$ and $m$. Let there be flow $k$ on the black edges and unit
flow on the red edges. (a) In the worst case graph (left) the flow on
remaining edges is according to flow conservation assuming $a_{1}$ as the
source and $b_{k}$ as the sink. Each edge in $C\times D$ necessarily has a
separate path in ${\cal P}_{f}$ from $a_{1}$ to $b_{k}$, with $k$ maximal safe
paths between $\\{a_{i},b_{i}\\}$ for all $1\leq i\leq k$ because every path
between $a_{i}$ to $b_{1}$ has excess flow $i$. This ensures that $|{\cal
P}_{c}|=|{\cal P}_{f}|=\Omega(mn)$. (b) In the best case graph (right) the two
edges from $a_{k-1}$ to $a_{k}$ and from $b_{1}$ to $b_{2}$ carry equal flow,
and the remaining edges have flow according to conservation of flow. Each edge
in $C\times D$ has a safe path of $O(1)$ size from $a_{k}$ to $b_{1}$. Here we
have still have $|{\cal P}_{f}|=\Omega(mn)$ but $|{\cal P}_{c}|=O(m+n)$.

##  5 Efficient Computation of All Maximal Safe Paths

We compute the maximal safe paths more efficiently by using dynamic
programming along the topological ordering in DAGs. Lemma 3.3e gives a unique
structure to the left maximal safe paths ending at a vertex $v$ because there
is no possibility of two safe paths diverging after converging. Such a
structure was previously studied for an entire DAG satisfying the no diverging
after converging property, and referred to as a _funnel_ [22].

We shall first describe the funnel structure ${\cal F}_{u}$ of the left
maximal safe paths ending at a vertex $u$. Thereafter, we will describe how
this ${\cal F}_{u}$ can be efficiently used to incrementally build ${\cal
F}_{v}$ for each out-neighbour $v$ of $u$. Finally, we will describe how to
report all the maximal safe paths ending at a vertex $v$ using ${\cal F}_{v}$.
The key idea behind the efficiency of our algorithm is bounding the overall
size of the funnel structures on all the vertices and associating the work
done with the total size of all the funnel structures. Our algorithm computes
all maximal safe paths of a DAG in $O(n^{2}+(m+|{\cal P}_{c}|)\log n)$ time,
where ${\cal P}_{c}$ is the concise representation of the solution reported by
the simple algorithm.

###  5.1 Funnel Structure of Safe Paths Ending at a Vertex

We describe ${\cal F}_{v}$ using the notion of source or sink paths of a
vertex $v$ in a DAG. A source path is any path to the vertex $v$ from a source
of the DAG, whereas the sink path is any path from the vertex $v$ to a sink of
the DAG. The funnel structure (see Figure 5) and its properties are described
as follows, which also proves Theorem 1.43a.

Figure 5: The funnel structures of safe paths ending at $v$ having the
diverging trees (blue) and a converging tree (green). The characteristic edge
(black) of a path is the first edge incident on the converging tree.

######  Theorem 5.1 (Funnel).

The left maximal safe paths entering a vertex $v$ form a funnel, where:

  1. (a)

Every vertex has either a unique source path or a unique sink path, or both.

  2. (b)

The funnel has a single converging tree (having vertices with unique sink
path) succeeding possibly multiple diverging trees (having remaining vertices
with unique source path).

  3. (c)

The characteristic edge of each flow path is its first edge incident on the
converging tree.

The size of the funnel structure ${\cal F}_{v}$ at $v$ is $O(n_{v}+m_{v})$,
where $n_{v}$ is the number of vertices having a safe path ending at $v$, and
$m_{v}$ is the number of paths in ${\cal P}_{c}$ containing $v$. For all $v\in
V$, the total size is $O(n^{2}+|{\cal P}_{c}|)$.

######  Proof 5.2.

We first prove the properties of the funnel (also derivable from previous work
[22]) and then the space complexity.

  1. (a)

Any vertex having both multiple source paths and multiple sink paths has two
different safe paths that merge at (or before) the vertex and then diverge at
(or after) it, which contradicts Lemma 3.3e.

  2. (b)

All the vertices having a unique sink path (terminating at $v$ as the funnel
contains only the safe paths ending at $v$), form a single converging tree
rooted at $v$ (see Figure 5). Similarly, the remaining vertices having unique
sink paths (Theorem 5.1a) form a set of disjoint diverging trees since there
can be multiple sources. Finally, since a vertex with a unique sink path
cannot reach a vertex with multiple sink paths, the vertices of the converging
tree always succeed those of diverging trees in any path.

  3. (c)

The first incident edge on the converging tree for a path in ${\cal F}_{v}$
would be from a vertex with a unique source path to a vertex with a unique
sink path. So the edge can be a part of exactly one path, which it
characterizes (see Figure 5). Such an edge always exists for a path because it
always starts from a source (hence with a unique source path) and ends at $v$
(hence with a unique sink path).

The number of vertices (and hence edges of the converging and diverging trees)
in the funnel is $O(n_{v})$ (by definition). Further, the non-tree edges (if
any) are the characteristic edges for some safe path containing $v$, and each
such safe path is present in a unique path in ${\cal P}_{c}$ (as each path
contains $v$ exactly once). Thus, each characteristic edge is uniquely
associated with a path in ${\cal P}_{c}$ containing $v$, resulting in total
$O(m_{v})$ non-tree edges in the funnel. Overall, since $n_{v}=O(n)$ and $v$
contributes to the length of at least $m_{v}$ paths in ${\cal P}_{c}$, that
total size of all funnels is $O(n^{2}+|{\cal P}_{c}|)$.

###  5.2 Incremental Construction of All Funnels

The funnel of a vertex is incrementally built on processing its incoming
neighbours. We process the vertices of the DAG in topological order, ensuring
that before we process a vertex its funnel is completely built while
processing its incoming neighbours.

We now describe how we build the funnels of the out neighbours of a vertex $u$
using ${\cal F}_{u}$ (see Algorithm 1). Since every edge is trivially safe,
every outgoing edge $(u,v)$ of $u$ is added to corresponding ${\cal F}_{v}$.
For updating any ${\cal F}_{v}$ with the safe paths through $u$, we traverse
${\cal F}_{u}$ in the reverse topological order and verify the safety of each
such path using the converging criterion. An edge from ${\cal F}_{u}$ is thus
added to ${\cal F}_{v}$ if some safe path contains the edge and $(u,v)$. We
distinguish the unique maximum weighted outgoing edge $(u,v^{*})$ of $u$ (if
any), and use different approaches to incrementally build ${\cal F}_{v^{*}}$
and ${\cal F}_{v}$ ($v\neq v^{*}$). This is because being unique we spend
$O(|{\cal F}_{u}|)$ time for ${\cal F}_{v^{*}}$, and only $O(|\Delta{\cal
F}_{v}|)$ time for other ${\cal F}_{v}$, where $\Delta{\cal F}_{v}$ are the
new edges added to ${\cal F}_{v}$ while processing $u$. Thus, the time
required to build all ${\cal F}_{v}$ is bounded by the total size of all
${\cal F}_{v}$, i.e., $O(n^{2}+|{\cal P}_{c}|)$.

Build-Funnels():

forall  _$u\in V$ in topological order_ do Build-From$(u)$

Build-From$(u):$

forall  _$(u,v)\in E$_ do Add $(u,v)$ to ${\cal F}_{v}$

/* Computing ${\cal F}_{v^{*}}$ */

$(u,v^{*})\leftarrow$ Maximum weight out-edge of $u$

forall  _$x\in{\cal F}_{u}$_ do

$f[x]\leftarrow 0$ // max safe flow leaving $x$

$f[u]\leftarrow f(u,v^{*})$

forall  _$y\in{\cal F}_{u}$ in reverse topological order_ do

forall  _$(x,y)\in{\cal F}_{u}$_ do

/* Safe flow $f^{\prime}$ leaving $x$ */

$f^{\prime}\leftarrow f[y]-f_{in}[y]+f(x,y)$

$f[x]\leftarrow\max(f[x],f^{\prime})$

if  _$f^{\prime} >0$ and $(x,y)\notin{\cal F}_{v^{*}}$_ then

Add $(x,y)$ to ${\cal F}_{v^{*}}$

/* Computing ${\cal F}_{v}$ for $v\neq v^{*}$ */

forall  _$(u,v\neq v^{*})\in E$_ do Add $v$ to ${\cal N}_{s}$, ${\cal N}_{p}$

Sort $v\in{\cal N}_{p}$ by weights of $(u,v)$

$y\leftarrow u$, $P\leftarrow\\{y\\}$

while  _${\cal N}_{p}\neq\emptyset$_ do

$(x,y)\leftarrow$ Max weight edge entering $y$

$P\leftarrow\\{x\\}\cup P$

$f[x]\leftarrow f[x]-f(u,v^{*})$

forall  _$v\in{\cal N}_{s}$_ do

$f^{\prime}\leftarrow f[x]+f(u,v)$

if  _$f^{\prime} >0$ and $(x,y)\notin{\cal F}_{v}$_ then

Add $(x,y)$ to ${\cal F}_{v}$

// suffix path

else Remove $v$ from ${\cal N}_{s}$

while  _$f[x]+f(u,head({\cal N}_{p})) <0$_ do

$v\leftarrow$ $pop({\cal N}_{p})$, $y^{\prime}\leftarrow z\leftarrow y$

while  _$y^{\prime}\notin{\cal F}_{v}$_ do

$y^{\prime}\leftarrow$ Next of $y^{\prime}$ in $P$

Add $P[z,y^{\prime}]$ in ${\cal F}_{v}$

// prefix path

$y\leftarrow x$

Algorithm 1 Incrementally building funnels

#### Building ${\cal F}_{v^{*}}$

We traverse ${\cal F}_{u}$ in reverse topological order, computing the maximum
excess flow $f[x]$ of a path from $x$ to $v^{*}$ through $u$. This is computed
by considering $f[y]$ of each out-neighbour $y$ of $x$ in ${\cal F}_{u}$,
where the excess flow of $x$-$v^{*}$ path is computed in $O(1)$ time using the
$y$-$v^{*}$ path by adding the edge $(x,y)$ to its start (Lemma 3.3c). Every
such edge $(x,y)$ resulting in a safe $x$-$v^{*}$ path is added to ${\cal
F}_{v^{*}}$, if not already present (may have been added while processing some
other ${\cal F}_{u^{\prime}}$). Note that if $x$ is in the converging tree,
there is a unique sink path from $x$ (Theorem 5.1b), hence $x$ considers a
single $y$ where $f[y]$ represents a single safe $y$-$v^{*}$ path. However, in
the diverging trees $y$ may have multiple sink paths (Theorem 5.1b), but we
process only $f[y]$ representing the $y$-$v^{*}$ safe path with the maximum
excess flow. This is because such a path would always be extendable to add
$(x,y)$ if any other $y$-$v^{*}$ path is extendable (Lemma 3.3c). Since we
cannot process $y$ for each path separately in $O(|{\cal F}_{u}|)$ time, we
process $y$ only once using $f[y]$ for its $y$-$v^{*}$ safe path with the
maximum excess flow. Thus, we process each edge of ${\cal F}_{u}$ once to
build ${\cal F}_{v^{*}}$ taking total $O(|{\cal F}_{u}|)$ time.

#### Building ${\cal F}_{v}$ for $v\neq v^{*}$

We limit the paths in ${\cal F}_{u}$ that are processed to build ${\cal
F}_{v}$ using the following property.

######  Lemma 5.3.

For a vertex $u$ and an edge $(u,v)$ where $v\neq v^{*}$, ${\cal F}_{u}$ adds
a single path to ${\cal F}_{v}$.

######  Proof 5.4.

If ${\cal F}_{u}$ adds multiple paths to ${\cal F}_{v}$, by Lemma 3.3d such
paths are also extendable to some maximum weighted outgoing edge
$(u,v^{\prime})$ of $u$, where $v^{\prime}\neq v$. This contradicts Lemma 3.3e
as two safe paths containing $u$ converge in ${\cal F}_{u}$ and then diverge
to $v$ and $v^{\prime}$.

Thus, we process exactly one path in ${\cal F}_{u}$ to be added to ${\cal
F}_{v}$ in the reverse topological order. Using Lemma 3.3d, this path, say
$P$, contains $(u,v)$ preceded by the maximum weight incoming edge $(y,u)$ of
$u$, and the maximum weight incoming edge $(x,y)$ of $y$, and so on. For a
vertex $v$, a suffix of this path, say $P_{v}$, is safe as long as its excess
flow is positive. This can be verified efficiently using Lemma 3.3c (similar
to ${\cal F}_{v^{*}}$). Moreover, maximum excess flow of a safe $x$-$v$ path
can be computed using $f[x]$ (computed for ${\cal F}_{v^{*}}$) by reducing
$f(u,v^{*})$ and adding $f(u,v)$ (Lemma 3.3c). However, $P_{v}$ cannot be
simply added to ${\cal F}_{v}$ using $O(|P_{v}|)$ time, because as described
earlier we aim to use only $O(|\Delta{\cal F}_{v}|)$ time.

Figure 6: $P_{v}$ overlaps a path (black) in ${\cal F}_{v}$ except at its
suffix (green) and its prefix (blue).

Consider Figure 6, if $P_{v}$ has a subpath already present in ${\cal F}_{v}$,
we cannot traverse the entire $P_{v}$ independently for $v$. So, we traverse
(and add to ${\cal F}_{v}$) only the suffix and the prefix (if any) of $P_{v}$
not in ${\cal F}_{v}$ independently, and the rest only once for all out-
neighbours of $u$. The suffix of $P_{v}$ is simply added in the reverse order
until it reaches a vertex $y$ already present in ${\cal F}_{v}$. Using Lemma
3.3e, $y$ is in the diverging tree of ${\cal F}_{v}$ as the new suffix
containing $(u,v)$ always exists. Hence $y$ has a unique source path which
either contains the rest of $P_{v}$, or begins from some vertex $y^{\prime}\in
P_{v}$. For the later case, we compute the start (say $z$) of $P_{v}$ for all
out-neighbours of $u$ together, and then add the corresponding prefix of
$P_{v}$, say $P_{v}[z,y^{\prime}]$, for each $P_{v}$ independently. Note that
the out-neighbours of $u$ may have different $y$, $y^{\prime}$, and $z$.

To compute $y$, $y^{\prime}$, and $z$ for all out-neighbours of $u$, we add
the out-neighbours to lists ${\cal N}_{s}$ and ${\cal N}_{p}$ to compute the
corresponding suffix and prefix, respectively. We traverse $P$ backwards,
adding the suffix edges to ${\cal F}_{v}$ for all $v\in{\cal N}_{s}$. When for
some $v$, the corresponding $y\in{\cal F}_{v}$ is reached we simply remove $v$
from ${\cal N}_{s}$ and continue for the other vertices adding each suffix
path to the corresponding ${\cal F}_{v}$ (until ${\cal N}_{s}=\emptyset$). For
adding prefix paths we need to compute $z$ for each $P_{v}$, beyond which
$P_{v}$ is not safe. Thus, we traverse backwards in $P$ together for all $v$
until some $P_{v}$ is unsafe. This $v$ would always be the one with lowest
weight $(u,v)$ among $(u,x)$ for $x\in{\cal N}_{p}$ by Lemma 3.3d, as the
remaining path is the same for all. Hence we initially sort $v\in{\cal N}_{p}$
in the increasing order of the weights of $(u,v)$, so that while traversing
$P$ backwards we check the safety of $P_{v}$ only for the first element in
${\cal N}_{p}$ ($head({\cal N}_{p})$). When $P_{v}$ for $head({\cal N}_{p})$
becomes unsafe we repeatedly remove the $head({\cal N}_{p})$ from ${\cal
N}_{p}$ until $P_{v}$ is safe for the rest of $v\in{\cal N}_{p}$. For a
removed vertex $v$, we traverse its prefix path (if any) forwards from $z$
until we reach $y^{\prime}\in{\cal F}_{v}$ and add it to ${\cal F}_{v}$.
Again, we continue traversing back on $P$ until all prefixes are added (until
${\cal N}_{p}=\emptyset$). The process thus requires $O(|\Delta{\cal F}_{v}|)$
for adding only new edges (prefixes and suffixes) to ${\cal F}_{v}$, $O(|{\cal
F}_{u}|)$ for traversing the path $P$, and $O(deg(u)\log n)$ for considering
all out-neighbours independently and sorting them.

Since topological sort takes linear time (edges), the total time required to
build all the funnels is $O(m\log n+\sum_{v}|{\cal F}_{v}|)=O(m\log
n+n^{2}+|{\cal P}_{c}|)$ (Theorem 5.1), proving Theorem 1.43b.

######  Theorem 5.5.

Given a flow graph (DAG) with $n$ vertices and $m$ edges, the funnel
structures for the left maximal safe paths ending at its vertices can be
computed in $O(m\log n+n^{2}+|{\cal P}_{c}|)$, where ${\cal P}_{c}$ is the
concise representation of the solution.

###  5.3 Reporting Maximal Safe Paths from a Funnel

The funnel ${\cal F}_{u}$ contains all the left maximal safe paths ending at
the vertex $u$. To report all maximal safe paths ending at $u$, we need to
address the following two issues:

  1. 1.

Some of these safe paths may not start from a source of ${\cal F}_{u}$, rather
some vertex $v$ in a diverging tree where residual source path was added by
some overlapping safe path, as there can be multiple sink paths for $v$
(Theorem 5.1b). Thus, to represent a maximal safe path ending at $u$ we report
its characteristic edge (Theorem 5.1) along with its start vertex in ${\cal
F}_{u}$. For completeness, we also report its excess flow.

Thus, all maximal safe paths ending at $u$ are reported in $\textsc{Sol}_{u}$
containing triplets (characteristic edge, start vertex, excess flow) for each
such path.

  2. 2.

Some of these paths may not be right maximal if the path from its start vertex
is extendable to the right of $u$ while remaining safe. Such paths must be
removed from the solution, hence we create another funnel ${\cal F}^{*}_{u}$
(initialized with ${\cal F}_{u}$) and remove such paths from it without
affecting the other maximal safe paths.

Thus, the funnel ${\cal F}^{*}_{u}$ and $\textsc{Sol}_{u}$ are reported as the
solution.

#### Approach

The start vertices of these maximal safe paths can be easily computed by
visiting the vertices of ${\cal F}_{u}$ in the reverse topological order,
computing their excess flow incrementally using that of its suffix path (Lemma
3.3c). When such a path becomes unsafe, we know that it’s suffix path is left
maximal. Also, if a safe path reaches a source of ${\cal F}_{u}$, it is left
maximal. To verify if any such path is also right maximal, we compute its
excess flow after adding the edge $(u,v^{*})$ (Lemma 3.3d) to its right using
Lemma 3.3c. If the new path is not safe, the suffix path is reported as
maximal safe using its characteristic edge, start vertex, and excess flow.
Otherwise, the path is not right maximal (and hence not maximal), so we delete
its characteristic edge with left and right extensions (not shared with any
maximal safe paths) from ${\cal F}^{*}_{u}$ (see Figure 7).

Figure 7: Multiple safe paths (red) starting at a vertex $v$ in the diverging
tree. Extensions (purple, dashed) of characteristic edges $e_{1}$ and $e_{2}$
to be deleted if their safe paths are not right maximal.

Note that verifying if a path is right maximal safe takes $O(1)$ time. If it
is not right maximal safe, ${\cal F}^{*}_{u}$ is updated by deleting some
edges, taking overall $O(|{\cal F}_{u}|)$ time. However, computing the start
vertex for each maximal safe path independently is not efficient because a
vertex $v$ in the diverging tree (see Figure 7) will be processed multiple
times as it can have multiple sink paths (Theorem 5.1b). Total time for
processing such vertices in ${\cal F}_{u}$ can be $O(m_{u}n_{u})$ (recall
Theorem 5.1). We instead process $v$ once for all such safe paths containing
$v$ as follows. While extending the safe paths starting from $v$ to the left,
if the path $P$ with the minimum excess flow is safe, the remaining paths are
also safe. Otherwise, $P$ is either removed from ${\cal F}^{*}_{v}$ if it is
not right maximal, or is reported as maximal. In either case, we evaluate the
next minimum weight path, and so on. Thus, processing a vertex either proceeds
backward from it or removes a safe path to be evaluated, taking total
$O(n_{u}+m_{u})$ time.

#### Heap Structure ${\cal H}_{v}$

For processing the diverging trees having multiple safe paths starting at each
vertex, we use any mergeable-heap [13, 34] structure, which is a min-heap
where all operations including merging two heaps take amortized $O(\log n)$
time. Additionally, we use the standard lazy update propagation technique,
where some value can be added to every element of the heap in $O(1)$ time,
which is propagated to individual elements when they are accessed. Now, every
element of a heap characterizing a safe path contains:

  * •

$edg$: Denotes the characteristic edge of the safe path.

  * •

$val$: The excess flow of the path without applying the lazy update.

  * •

$upd$: The lazy update which is to be reduced from the $val$.

For each vertex $v\in{\cal F}_{u}$, we maintain such a mergeable-heap
structure ${\cal H}_{v}$ which stores an element corresponding to each safe
path from $v$ to $u$. For a vertex $v$ in the converging tree, having a single
sink path (Theorem 5.1b) and hence $|{\cal H}_{v}|=1$, we do not need lazy
update, so we keep $upd=-1$ for its element. Also, for such vertices in the
converging tree inserting an element takes $O(1)$ time, being inserted into an
empty heap. Similarly, for a vertex $x$ with a single out-neighbour $y$ in a
diverging tree merging ${\cal H}_{y}$ into an empty ${\cal H}_{x}$ takes
$O(1)$ time.

forall  _$(x,u)\in{\cal F}_{u}$_ do Add $[(x,u),f(x,u),-1]$ to empty ${\cal
H}_{x}$

$upd^{*}\leftarrow f_{out}(u)-f(u,v^{*})$

/* update to check right maximal */

forall  _$y\neq u\in{\cal F}_{u}$ in reverse topological order_ do

forall  _$(x,y)\in{\cal F}_{u}$_ do

$upd\leftarrow f_{in}(y)-f(x,y)$

if  _${\cal H}_{y}\neq\emptyset$_ then // extendable safe paths in ${\cal
H}_{y}$

if  _$head({\cal H}_{y}).upd=-1$_ then // $y$ in converging tree

if  _$x$ has unit out-degree in ${\cal F}_{u}$_ then // $x$ in converging tree

Add $[(x,y),head({\cal H}_{y}).val-upd,-1]$ to empty ${\cal H}_{x}$

else Add $[(x,y),head({\cal H}_{y}).val,upd]$ to ${\cal H}_{x}$

// $x$ in diverging tree

else // $y$ in diverging tree

while  _$head({\cal H}_{y}).val-head({\cal H}_{y}).upd-upd\leq 0$_ do // path
unsafe

$top\leftarrow$ Extract min from ${\cal H}_{y}$

if  _ $top.val-top.upd-upd^{*}>0$_ then // path not maximal

Remove $top.edg$ with extensions from ${\cal F}^{*}_{u}$

else Add $[top.edg,y,top.val-top.upd]$ to $\textsc{Sol}_{u}$ // path maximal

$head({\cal H}_{y}).upd\leftarrow head({\cal H}_{y}).upd+upd$

if  _$x$ has unit out-degree in ${\cal F}_{u}$_ then Merge ${\cal H}_{y}$ into
empty ${\cal H}_{x}$

else Merge ${\cal H}_{y}$ into ${\cal H}_{x}$

forall  _source $v\in{\cal F}_{u}$_ do

while  _${\cal H}_{v}\neq\emptyset$_ do

$top\leftarrow$ Extract min from ${\cal H}_{y}$

if  _ $top.val-top.upd-upd^{*}>0$_ then // path not maximal

Remove $top.edg$ with extensions from ${\cal F}^{*}_{u}$

else Add $[top.edg,v,top.val-top.upd]$ to $\textsc{Sol}_{u}$ // path maximal

Report ${\cal F}^{*}_{u}$ and $\textsc{Sol}_{u}$

Algorithm 2 Reporting maximal safe paths in ${\cal F}_{u}$

#### Algorithm

Our algorithm first adds a single edge path $(u,v)$ to the heap of each in-
neighbour $v$ of $u$ (see Algorithm 2). Now, moving from $y$ to $x$ through an
edge $(x,y)$ we consider two cases.

  1. (a)

If $y$ is in the converging tree, then adding $(x,y)$ is always safe (recall
that a different start vertex is only possible for the paths starting from a
diverging tree). So for the current path $edg$ is updated to $(x,y)$ (being
incident on $y$). The change in the excess flow on adding $(x,y)$ (Lemma 3.3c)
is updated either in $val$ (if $x$ is in converging tree) or in $upd$ (if $x$
is in diverging tree). This updated element is inserted to ${\cal H}_{x}$.

  2. (b)

If $y$ is in a diverging tree, first we verify the safety of adding $(x,y)$ to
the minimum excess flow path in ${\cal H}_{y}$ ($head({\cal H}_{y})$). If it
is not safe, it is extracted from the heap and dealt with (explained later).
We continue to check for unsafe paths in ${\cal H}_{y}$ and extract them until
$head({\cal H}_{y})$ is safe. When all paths in ${\cal H}_{y}$ are safe, the
change in excess flow by adding $(x,y)$ (Lemma 3.3c) is updated in $head({\cal
H}_{y}).upd$, and ${\cal H}_{y}$ is merged into ${\cal H}_{x}$.

The unsafe paths extracted from the heaps and the safe paths in the heaps of
the sources of ${\cal F}_{u}$, are processed so that they are either removed
from ${\cal F}^{*}_{v}$ (if not right maximal) or added to the solution after
applying the lazy update.

#### Analysis

Now, each of $m_{u}$ safe paths in ${\cal F}_{u}$ uses one insert and one
extract min operation in a non-empty heap, while moving from converging tree
to diverging tree, and while adding to (or discarding from) the solution
respectively, using $O(m_{u})$ operations. Also, every merge operation into
non-empty heaps combines at least two different safe paths in a heap, using
total $O(m_{u})$ operations. The remaining operations (including those on
empty heaps) take $O(1)$ time while traversing ${\cal F}_{u}$ taking $O(|{\cal
F}_{u}|)$ time. Thus, processing each funnel takes $O(m_{u}\log n+|{\cal
F}_{u}|)$ time, requiring total $O(n^{2}+|{\cal P}_{c}|\log n)$ time, which
also proves Theorem 1.43c.

######  Theorem 5.6.

Given a flow graph (DAG) with $n$ vertices and $m$ edges and the funnel
structures for the left maximal safe paths ending at its vertices, the maximal
safe paths can be reported in $O(n^{2}+|{\cal P}_{c}|\log n)$ time, where
${\cal P}_{c}$ is the concise representation of the solution.

##  6 Conclusion

We study the safety of flow paths in a given flow graph (DAG), which has
applications in various domains, including the more prominent assembly of
biological sequences. The previous work characterized such paths (and their
generalizations) using a global criterion.

We presented a simpler characterization based on a more efficiently computable
local criterion, that can be directly adapted into an optimal verification
algorithm. Also, it results in a simple enumeration algorithm, which is
optimal for some worst-case examples. However, it is inefficient if the size
of the concise representation of the solution is small. We improve this
algorithm by exploiting a unique structure of a set of safe paths, called a
funnel, resulting in a running time parameterized by the size of this concise
representation of the solution,

Our improved enumeration algorithm improved the running time of the simple
algorithm only when the size of flow decomposition $O(|\mathcal{P}_{c}|)$ is
larger than $O(n^{2})$. Also, it uses extra space if $|{\cal
P}_{c}|=o(n^{2})$. In the future, it would be interesting to see if it is
possible to report the solution using optimal space, because both the paths in
${\cal P}_{c}$ and different ${\cal F}_{v}$ may have a lot of redundancy.
Ideally, we would like to see an algorithm taking linear time in addition to
the optimal output size (similar to what was achieved by [7] for a different
problem). Another interesting extension to this problem having practical
significance is finding safe paths for those flow decompositions whose paths
have a certain minimum weight threshold.

## References

  * [1] Nidia Obscura Acosta, Veli Mäkinen, and Alexandru I. Tomescu.  A safe and complete algorithm for metagenomic assembly.  Algorithms Mol. Biol., 13(1):3:1–3:12, 2018.  doi:10.1186/s13015-018-0122-7.
  * [2] Jasmijn A. Baaijens, Bastiaan Van der Roest, Johannes Köster, Leen Stougie, and Alexander Schönhuth.  Full-length de novo viral quasispecies assembly through variation graph construction.  Bioinform., 35(24):5086–5094, 2019.  doi:10.1093/bioinformatics/btz443.
  * [3] Jasmijn A. Baaijens, Leen Stougie, and Alexander Schönhuth.  Strain-aware assembly of genomes from mixed samples using flow variation graphs.  In Russell Schwartz, editor, Research in Computational Molecular Biology - 24th Annual International Conference, RECOMB 2020, Padua, Italy, May 10-13, 2020, Proceedings, volume 12074 of Lecture Notes in Computer Science, pages 221–222. Springer, 2020.  doi:10.1007/978-3-030-45257-5\\_14.
  * [4] Georg Baier, Ekkehard Köhler, and Martin Skutella.  On the k-splittable flow problem.  In European Symposium on Algorithms, pages 101–113. Springer, 2002\.
  * [5] Georg Baier, Ekkehard Köhler, and Martin Skutella.  The k-splittable flow problem.  Algorithmica, 42(3-4):231–248, 2005.
  * [6] Elsa Bernard, Laurent Jacob, Julien Mairal, and Jean-Philippe Vert.  Flipflop: Fast lasso-based isoform prediction as a flow problem, 2013\.
  * [7] Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu, and Elia C. Zirondelli.  From omnitigs to macrotigs: a linear-time algorithm for safe walks – common to all closed arc-coverings of a directed graph, 2020.  arXiv:2002.10498.
  * [8] Katarína Cechlárová and Vladimír Lacko.  Persistency in combinatorial optimization problems on matroids.  Discret. Appl. Math., 110(2-3):121–132, 2001.  doi:10.1016/S0166-218X(00)00279-1.
  * [9] Rami Cohen, Liane Lewin-Eytan, Joseph Seffi Naor, and Danny Raz.  On the effect of forwarding table size on sdn network utilization.  In IEEE INFOCOM 2014-IEEE conference on computer communications, pages 1734–1742. IEEE, 2014.
  * [10] Marie-Christine Costa.  Persistency in maximum cardinality bipartite matchings.  Operations Research Letters, 15(3):143 – 149, 1994.  URL: http://www.sciencedirect.com/science/article/pii/0167637794900493, doi:http://dx.doi.org/10.1016/0167-6377(94)90049-3.
  * [11] Rene De La Briandais.  File searching using variable length keys.  In Papers Presented at the the March 3-5, 1959, Western Joint Computer Conference, page 295–298, New York, NY, USA, 1959. Association for Computing Machinery.  doi:10.1145/1457838.1457895.
  * [12] D. R. Ford and D. R. Fulkerson.  Flows in Networks.  Princeton University Press, USA, 2010.
  * [13] Michael L. Fredman and Robert Endre Tarjan.  Fibonacci heaps and their uses in improved network optimization algorithms.  J. ACM, 34(3):596–615, July 1987.  doi:10.1145/28869.28874.
  * [14] Thomas Gatter and Peter F Stadler.  Ryūtō: network-flow based transcriptome reconstruction.  BMC bioinformatics, 20(1):190, 2019.
  * [15] Tzvika Hartman, Avinatan Hassidim, Haim Kaplan, Danny Raz, and Michal Segalov.  How to split a flow?  In 2012 Proceedings IEEE INFOCOM, pages 828–836. IEEE, 2012.
  * [16] Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Vijay Gill, Mohan Nanduri, and Roger Wattenhofer.  Achieving high utilization with software-driven wan.  In Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM, pages 15–26, 2013.
  * [17] Kyle Kloster, Philipp Kuinke, Michael P O’Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D Sullivan, and Andrew van der Poel.  A practical fpt algorithm for flow decomposition and transcript assembly.  In 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 75–86. SIAM, 2018.
  * [18] Vladimí Lacko.  Persistency in optimization problems on graphs and matroids.  Master’s thesis, UPJŠ Košice, 1998.
  * [19] Cong Ma, Hongyu Zheng, and Carl Kingsford.  Exact transcript quantification over splice graphs.  In Carl Kingsford and Nadia Pisanti, editors, 20th International Workshop on Algorithms in Bioinformatics, WABI 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 172 of LIPIcs, pages 12:1–12:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.WABI.2020.12.
  * [20] Cong Ma, Hongyu Zheng, and Carl Kingsford.  Finding ranges of optimal transcript expression quantification in cases of non-identifiability.  bioRxiv, 2020.  URL: https://www.biorxiv.org/content/early/2020/02/16/2019.12.13.875625, arXiv:https://www.biorxiv.org/content/early/2020/02/16/2019.12.13.875625.full.pdf, doi:10.1101/2019.12.13.875625.
  * [21] Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, and Alexandru I. Tomescu.  Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing.  Cambridge University Press, 2015.  doi:10.1017/CBO9781139940023.
  * [22] Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge.  Efficient algorithms for measuring the funnel-likeness of dags.  J. Comb. Optim., 39(1):216–245, 2020.
  * [23] Brendan Mumey, Samareh Shahmohammadi, Kathryn McManus, and Sean Yaw.  Parity balancing path flow decomposition and routing.  In 2015 IEEE Globecom Workshops (GC Wkshps), pages 1–6. IEEE, 2015\.
  * [24] Jan Peter Ohst.  On the Construction of Optimal Paths from Flows and the Analysis of Evacuation Scenarios.  PhD thesis, University of Koblenz and Landau, Germany, 2015.
  * [25] Nils Olsen, Natalia Kliewer, and Lena Wolbeck.  A study on flow decomposition methods for scheduling of electric buses in public transport based on aggregated time–space network models.  Central European Journal of Operations Research, 2020.  doi:10.1007/s10100-020-00705-6.
  * [26] Mihaela Pertea, Geo M Pertea, Corina M Antonescu, Tsung-Cheng Chang, Joshua T Mendell, and Steven L Salzberg.  Stringtie enables improved reconstruction of a transcriptome from rna-seq reads.  Nature biotechnology, 33(3):290–295, 2015.
  * [27] Krzysztof Pieńkosz and Kamil Kołtyś.  Integral flow decomposition with minimum longest path length.  European Journal of Operational Research, 247(2):414–420, 2015\.
  * [28] Mingfu Shao and Carl Kingsford.  Theory and a heuristic for the minimum path flow decomposition problem.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 16(2):658–670, 2017.
  * [29] Vorapong Suppakitpaisarn.  An approximation algorithm for multiroute flow decomposition.  Electronic Notes in Discrete Mathematics, 52:367 – 374, 2016.  INOC 2015 – 7th International Network Optimization Conference.  URL: http://www.sciencedirect.com/science/article/pii/S1571065316300531, doi:https://doi.org/10.1016/j.endm.2016.03.048.
  * [30] Alexandru I. Tomescu, Travis Gagie, Alexandru Popa, Romeo Rizzi, Anna Kuosmanen, and Veli Mäkinen.  Explaining a weighted DAG with few paths for solving genome-guided multi-assembly.  IEEE ACM Trans. Comput. Biol. Bioinform., 12(6):1345–1354, 2015\.  doi:10.1109/TCBB.2015.2418753.
  * [31] Alexandru I Tomescu, Anna Kuosmanen, Romeo Rizzi, and Veli Mäkinen.  A novel min-cost flow method for estimating transcript expression with rna-seq.  BMC bioinformatics, 14(S5):S15, 2013.
  * [32] Alexandru I. Tomescu and Paul Medvedev.  Safe and complete contig assembly through omnitigs.  Journal of Computational Biology, 24(6):590–602, 2017.  Preliminary version appeared in RECOMB 2016.
  * [33] Benedicte Vatinlen, Fabrice Chauvet, Philippe Chrétienne, and Philippe Mahey.  Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths.  European Journal of Operational Research, 185(3):1390–1401, 2008\.
  * [34] Jean Vuillemin.  A data structure for manipulating priority queues.  Communications of the ACM, 21(4):309–315, 1978.  URL: https://doi.org/10.1145/359460.359478.
  * [35] Zhong Wang, Mark Gerstein, and Michael Snyder.  RNA-Seq: a revolutionary tool for transcriptomics.  Nature Reviews Genetics, 10(1):57–63, 2009.
  * [36] Lucia Williams, Gillian Reynolds, and Brendan Mumey.  Rna transcript assembly using inexact flows.  In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 1907–1914. IEEE, 2019.


Yunsong<EMAIL_ADDRESS>Na Zhaohttps://na-z.github.io2 Gim Hee
Leehttps://www.comp.nus.edu.sg/ leegh/1 School of Computing
National University of Singapore
Singapore  Information Systems Technology and Design
Singapore University of Technology and Design
Singapore  UNDER REVIEW

# Syn-to-Real Unsupervised Domain Adaptation for Indoor 3D Object Detection

###### Abstract

The use of synthetic data in indoor 3D object detection offers the potential
of greatly reducing the manual labor involved in 3D annotations and training
effective zero-shot detectors. However, the complicated domain shifts across
syn-to-real indoor datasets remains underexplored. In this paper, we propose a
novel Object-wise Hierarchical Domain Alignment (OHDA) framework for syn-to-
real unsupervised domain adaptation in indoor 3D object detection. Our
approach includes an object-aware augmentation strategy to effectively
diversify the source domain data, and we introduce a two-branch adaptation
framework consisting of an adversarial training branch and a pseudo labeling
branch, in order to simultaneously reach holistic-level and class-level domain
alignment. The pseudo labeling is further refined through two proposed schemes
specifically designed for indoor UDA. Our adaptation results from synthetic
dataset 3D-FRONT to real-world datasets ScanNetV2 and SUN RGB-D demonstrate
remarkable mAP25 improvements of $9.7\%$ and $9.1\%$ over Source-Only
baselines, respectively, and consistently outperform the methods adapted from
2D and 3D outdoor scenarios. The code will be publicly available upon paper
acceptance.

##  1 Introduction

3D object detection is a fundamental yet challenging task that plays a crucial
role in numerous applications such as autonomous driving and augmented
reality. In recent years, several deep learning approaches [Hou et
al.(2019)Hou, Dai, and Nießner, Qi et al.(2019)Qi, Litany, He, and Guibas,
Zhang et al.(2020)Zhang, Sun, Yang, and Huang, Liu et al.(2021)Liu, Zhang,
Cao, Hu, and Tong, Zheng et al.(2022)Zheng, Duan, Lu, Zhou, and Tian]
developed for 3D object detection have achieved promising performance.
However, the performance heavily relies on large amounts of well-annotated
training data, and an in-distribution assumption between training and testing
data. When the testing environment (target domain) follows a different
distribution from the training environment (source domain), the performance
would suffer from a significant drop, as shown by the prediction from the
source-only model in Figure 1. This out-of-distribution phenomenon is caused
by the domain shift due to a variety of reasons such as different sensor
configurations [Tsai et al.(2022)Tsai, Berrio, Shan, Worrall, and Nebot] or
geographical locations [Wang et al.(2020)Wang, Chen, You, Li, Hariharan,
Campbell, Weinberger, and Chao] during training and testing data collection.

To deal with the domain shift between the training and testing environments,
unsupervised domain adaption (UDA) is proposed by learning domain-invariant
knowledge from both the labeled source domain data and the unlabeled target
domain data. Recently, a few domain adaptive 3D object detection methods
[Saltori et al.(2020)Saltori, Lathuiliére, Sebe, Ricci, and Galasso, Wang et
al.(2020)Wang, Chen, You, Li, Hariharan, Campbell, Weinberger, and Chao, Yang
et al.(2021)Yang, Shi, Wang, Li, and Qi, DeBortoli et al.(2021)DeBortoli,
Fuxin, Kapoor, and Hollinger] have been devised to avoid requiring heavy 3D
annotations on the target domains. Nonetheless, these works predominantly
focus on outdoor 3D object detection. Directly applying these techniques to
indoor settings, as referenced in Table 1 and Table 2, often yields suboptimal
outcomes. The root of such underperformance mainly lies in the distinct domain
shifts characterizing outdoor and indoor contexts. Outdoor datasets normally
focus on detecting cars and the major domain shift is the average sizes of
cars [Wang et al.(2020)Wang, Chen, You, Li, Hariharan, Campbell, Weinberger,
and Chao]. In contrast, indoor environments present intricate domain gaps
across diverse object categories, and demand further investigations.

Figure 1: Pipelines of Source-Only and OHDA.

To this end, we focus on unsupervised domain adaptation for indoor 3D object
detection. Compared to outdoor scenarios, different indoor datasets can have
much larger and more complicated cross-domain gaps due to different capturing
patterns (single-view vs multi-view) and diverse object categories with
various shape distributions, which lead to the difficulty of using real-world
datasets as source domain. In contrary, synthetic data offers large quantity
of complete scene-level point clouds with labor-free 3D labels, covering
common object categories with diverse shapes, which is suitable for the
challenge of indoor UDA and has the potential of training an effective zero-
shot 3D detectors without real-world 3D labels. Therefore, in this work we
study the Synthetic-to-Real Unsupervised Domain Adaptation (SR-UDA) for indoor
3D object detection.

We adopt the synthetic datatset 3D-FRONT [Fu et al.(2021)Fu, Cai, Gao, Zhang,
Wang, Li, Zeng, Sun, Jia, Zhao, et al.] as the source domain, which contains
18,968 rooms furnished by 13,151 furniture objects with high-quality textures.
To narrow down the syn-to-real domain gap, we introduce an object-aware
augmentation strategy, which effectively diversifies the synthetic scenes and
is seamlessly integrated with a virtual scan simulation (VSS) technique [Ding
et al.(2022)Ding, Yang, Jiang, and Qi] for data augmentation. To adapt the
knowledge across syn-to-real domain shift, we propose an Object-wise
Hierarchical Domain Alignment (OHDA) framework, which comprises of an
proposal-level domain adversarial training branch and a pseudo-labeling
branch, which aligns the cross-domain proposal features and performs more
effective joint training on cross-domain data. We further refine the pseudo
labeling through two proposed modules: a simple-yet-effective adaptive
thresholding strategy to resist the class-specific domain gaps, and a
reweighting scheme on pseudo labels based to their consistency towards model
perturbation. We assess our methodology using two benchmark datasets for
indoor 3D object detection, namely ScanNetV2 [Dai et al.(2017)Dai, Chang,
Savva, Halber, Funkhouser, and Nießner] and SUN RGB-D [Song et al.(2015)Song,
Lichtenberg, and Xiao]. In these evaluations, our OHDA method consistently
showcases significant improvements. In summary, our key contributions include:

  * •

To the best of our knowledge, this is the first study that delves into UDA for
indoor 3D object detection using a syn-to-real approach, which eliminates the
need for large-scale 3D labels that are notably costly and challenging to
acquire for 3D object detection.

  * •

We propose OHDA as the first solution to the SR-UDA task, which benefits from
the two-branch structure that leads to holistic-level and class-level domain
alignment. We further propose specific strategies to adapt OHDA to the SR-UDA
setting, including object-aware augmentation and two pseudo label refinement
modules.

  * •

We establish new benchmarks for 3D-FRONT $\rightarrow$ ScanNetV2 and 3D-FRONT
$\rightarrow$ SUN RGB-D, improving mAP25 by $9.7\%$ and $9.1\%$ over the
Source-Only baseline, respectively, consistently surpassing existing UDA
methods adapted from different contexts.

##  2 Related Work

Indoor 3D Object Detection. Benefiting from the well preserved spatial
information in point clouds, methods that directly process on point clouds
have become the majority in state-of-the-art indoor 3D object detection. Early
methods transform the raw 3D point clouds into voxels [Maturana and
Scherer(2015), Zhou and Tuzel(2018)] or use the 2D priors [Qi et al.(2018)Qi,
Liu, Wu, Su, and Guibas, Lahoud and Ghanem(2017)] to tackle the difficulties
of working on 3D data. Inspired by Hough Voting in 2D object detection [Gall
et al.(2011)Gall, Yao, Razavi, Van Gool, and Lempitsky, Radopoulou et
al.(2012)Radopoulou, Sun, Dai, Brilakis, and Savarese], VoteNet [Qi et
al.(2019)Qi, Litany, He, and Guibas] proposes to predict the offsets from
sampled points to their corresponding bounding box centers, which is followed
by clustering and PointNet [Qi et al.(2017)Qi, Yi, Su, and Guibas]-based
grouping. Following VoteNet, several recent methods further incorporate 3D
primitives [Zhang et al.(2020)Zhang, Sun, Yang, and Huang], back-tracing
strategy [Cheng et al.(2021)Cheng, Sheng, Shi, Yang, and Xu], or object-level
attention [Liu et al.(2021)Liu, Zhang, Cao, Hu, and Tong].

Unsupervised Domain Adaptation. Given the labeled source domain data and the
unlabeled target domain data, unsupervised domain adaptation (UDA) aims to
effectively adapt knowledge from the source to target domain. This task has
been largely explored in 2D, where the discrepancy-based methods [Long et
al.(2015)Long, Cao, Wang, and Jordan, Long et al.(2016)Long, Zhu, Wang, and
Jordan, Long et al.(2017)Long, Zhu, Wang, and Jordan, Saito et al.(2018)Saito,
Watanabe, Ushiku, and Harada] learn to minimize the domain discrepancy, the
domain adversarial training methods [Ganin and Lempitsky(2015), Ganin et
al.(2017)Ganin, Ustinova, Ajakan, Germain, Larochelle, Laviolette, Marchand,
and Lempitsky, Ganin et al.(2016)Ganin, Ustinova, Ajakan, Germain, Larochelle,
Laviolette, Marchand, and Lempitsky, Tzeng et al.(2017)Tzeng, Hoffman, Saenko,
and Darrell, Huang et al.(2022)Huang, Guan, Xiao, and Lu] address it by
jointly training a domain classifier with min-max optimization, and self-
training (i.e. pseudo labeling) methods [Guan et al.(2021)Guan, Huang, Lu, and
Xiao, Huang et al.(2021)Huang, Guan, Xiao, and Lu, Li et al.(2019)Li, Yuan,
and Vasconcelos, Wang et al.(2021b)Wang, Dai, Hoyer, Van Gool, and Fink, Zou
et al.(2019)Zou, Yu, Liu, Kumar, and Wang] iteratively train the model using
both the labeled source and pseudo-labeled target domain data. Most existing
methods focus on unsupervised domain adaptation for image classification and
semantic segmentation tasks, which are less challenging than the object
detection task that requires the precise regression of the bounding boxes.

Domain Adaptive Object Detection. For domain adaptive 2D object detection,
most of previous work leverage domain adversarial training to align the cross-
domain global feature or proposals [Chen et al.(2020)Chen, Zheng, Ding, Huang,
and Dou, Su et al.(2020)Su, Wang, Zeng, Tang, Chen, Qiu, and Wang, Xu et
al.(2020)Xu, Zhao, Jin, and Wei, Chen et al.(2018)Chen, Li, Sakaridis, Dai,
and Van Gool]. Recently, several approaches also convert this task to the
semi-supervised learning problem and utilize advanced pseudo labeling
techniques such as Mean Teacher [Cai et al.(2019)Cai, Pan, Ngo, Tian, Duan,
and Yao, Deng et al.(2021)Deng, Li, Chen, and Duan, Wang et al.(2021a)Wang,
Cong, Litany, Gao, and Guibas] to address the domain shift problem. For domain
adaptive 3D object detection, existing works mainly address it under the
outdoor scenarios, through bounding box size adaptation [Wang et
al.(2020)Wang, Chen, You, Li, Hariharan, Campbell, Weinberger, and Chao],
pseudo label time-consistency [Saltori et al.(2020)Saltori, Lathuiliére, Sebe,
Ricci, and Galasso], Mean Teacher [Yang et al.(2021)Yang, Shi, Wang, Li, and
Qi] and global-level domain adversarial training [DeBortoli et
al.(2021)DeBortoli, Fuxin, Kapoor, and Hollinger]. In contrast, the UDA of 3D
object detection in indoor scenarios, which consist of more diverse object
categories with class-specific domain gaps across datasets, is more
challenging and pragmatic yet underexplored. Thus, this work focuses on this
pragmatic task and adopts a large-scale and manual-annotation-free synthetic
dataset as the source domain.

Figure 2: Proposed Framework. Our framework consists of three parts: cross-
domain data alignment, Object-wise Hierarchical Domain Alignment (consisting
of Class-Level Alignment (CLA) and Holistic-Level Alignment (HLA)), and Pseudo
Label Refinement (PLR).

##  3 Our Approach

###  3.1 Overview

The framework of OHDA is shown in Figure 2. Formally, we denote the detector
backbone as $\bm{\mathcal{M}}$, which predicts the object proposals, and
$\bm{\varphi}$ is the proposal decoder that predicts the bounding box
attributes. We denote the student and teacher model as
$\bm{\varphi}^{S}(\bm{\mathcal{M}}^{S}(\cdot))$ and
$\bm{\varphi}^{T}(\bm{\mathcal{M}}^{T}(\cdot))$, respectively. Both student
and teacher are initialized by a pre-trained model trained on the augmented
source domain data. During adaptation, the student model is updated using
gradient decent, and the teacher model is detached and is updated by
Exponential Moving Average (EMA) of the student model. In SR-UDA, we are given
$N_{s}$ labeled point clouds from the synthetic source domain
$\bm{\mathcal{D}}_{s}=\\{\bm{X}_{s},\bm{Y}_{s}\\}^{N_{s}}$ and $N_{t}$
unlabeled point clouds from the real-world target domain
$\bm{\mathcal{D}}_{t}=\\{\bm{X}_{t}\\}^{N_{t}}$.

###  3.2 Cross-Domain Data Alignment

The syn-to-real domain gaps in indoor 3D scenes are mainly caused by the
change of two aspects: the RGB-D camera scanning pattern and the room layout.
The first type of domain gap can be largely solved by VSS [Ding et
al.(2022)Ding, Yang, Jiang, and Qi], which is a recent technique that
simulates sensor noise and occlusion similarly to real-world scenes. In this
paper, we propose an Object-Aware Augmentation (OAA) strategy that can narrow
down the second type of domain gap and is compatible with VSS.

Scene-Object Mixture. Although 3D-FRONT benefits from its large quantity of
individual scenes, it still suffers from regular localization of objects.
Besides, the class-imbalance problem can also lead to inferior performance of
detector. We therefore propose to mix the scenes and the synthetic objects.
Specifically, we randomly sample objects from 3D-FRONT [Fu et al.(2021)Fu,
Cai, Gao, Zhang, Wang, Li, Zeng, Sun, Jia, Zhao, et al.] and randomly place
them into the scene on-the-fly. The objects are placed on the floor, with no
collision with original scene. Furthermore, we set the probability of sampling
each object category to be inversely proportional to their frequencies in
3D-FRONT [Fu et al.(2021)Fu, Cai, Gao, Zhang, Wang, Li, Zeng, Sun, Jia, Zhao,
et al.], so as to mitigate the class-imbalance problem.

Local Pattern Preserved Augmentation. To diversify the synthetic source
domain, the local augmentation on object level is essential, which includes
random scaling, rotating and translating the objects. To prevent the
generation of unrealistic scenes, it is crucial to perform collision checks
between objects during object augmentation. However, collision checks in
indoor scenes are more complex than those in outdoor scenes [Reuse et
al.(2021)Reuse, Simon, and Sick] due to the intricate local spatial patterns
between objects. For example, some objects such as chairs and tables have
naturally overlapping bounding boxes in the original scenes. Therefore,
directly checking the overlap of bounding boxes may not be sufficient to
validate object collision. To address this challenge, we propose preserving
local patterns by merging overlapped objects. Specifically, before
augmentation, we identify existing collided bounding boxes (where IoU$>0.01$)
and merge all points from the corresponding collided bounding boxes to obtain
new object points. The collided bounding boxes are replaced by a minimum axis-
aligned bounding box that covers them. We then iteratively merge the collided
objects until there are no more collisions. We then perform local augmentation
on the merged objects.

###  3.3 Object-wise Hierarchical Domain Alignment

To enhance the domain adaptation under the indoor scenario with more
complicated object distributions and cross-domain shifts, we propose a
hierarchical domain alignment framework performed on object-level, which
includes class-level and holistic-level alignment.

####  3.3.1 Class-Level Alignment

We first build a pseudo labeling branch to facilitate the domain alignment
using labeled source domain data and unlabeled target domain data. Formally,
the supervised loss on the labeled source domain samples is computed as
$\mathcal{L}_{sup}=\mathcal{L}^{l}\left(\hat{\bm{Y}}_{s},\bm{Y}_{s}\right)$,
where
$\hat{\bm{Y}}_{s}=\bm{\varphi}^{S}\left(\bm{\mathcal{M}}^{S}(\bm{X}_{s})\right)$
are the student predictions on source domain samples. The Class-Level
Alignment (CLA) loss on the pseudo-labeled target domain data is computed as:

$\displaystyle\mathcal{L}_{cla}=\frac{1}{M}\sum_{m=1}^{M}\mathcal{L}^{u}\left(\hat{\bm{Y}}_{t}^{m},\bm{\bar{Y}}_{t}^{m}\right),$
(1)
$\displaystyle\bm{\hat{Y}}_{t}^{m}=\left[\bm{\varphi}^{S}(\bm{\mathcal{M}}^{S}(\bm{X}_{t}))\right]^{m},\bar{\bm{Y}}_{t}^{m}=\mathcal{S}\left(\mathcal{F}(\bm{\varphi}^{T}(\bm{\mathcal{M}}^{T}(\bm{X}_{t}))),\bm{\hat{Y}}_{t}^{m}\right),\vspace{-2mm}$
(2)

where $M$ the number of proposals, $\mathcal{F}(\cdot)$ the pseudo label
filtering strategy, $\bm{\hat{Y}}_{t}^{m}$ the $m$-th bounding box predicted
by student model, $\bm{\bar{Y}}_{t}^{m}$ the teacher’s prediction that is
matched with $\bm{\hat{Y}}_{t}^{m}$ using distance-based scheme $\mathcal{S}$
similarly to [Qi et al.(2019)Qi, Litany, He, and Guibas]. We supervise the
student’s predictions that are within $0.3m$ of pseudo bounding box centers.
$\mathcal{L}^{l}$ is the standard supervised loss used in [Qi et al.(2019)Qi,
Litany, He, and Guibas], and $\mathcal{L}^{u}$ only contains the box loss and
the semantic loss.

####  3.3.2 Holistic-Level Alignment

The aforementioned Class-Level Alignment is similar to the standard mean
teacher [Tarvainen and Valpola(2017)] in 2D semi-supervised learning, which
however could lead to suboptimal performance due to the domain gap between
synthetic and real domains under UDA setting. Therefore, we propose to further
encourage the cross-domain proposals to share the same feature space, such
that the ground truth labels on the source domain and pseudo labels on the
target domain can achieve better joint-supervision on the student model.
Specifically, we add a Proposal Discriminator $\bm{\mathcal{D}_{p}}(\cdot)$ to
predict the domain label (0 for source, 1 for target domain) on the object
proposal level. The Holistic Level Alignment (HLA) loss is implemented as a
cross-entropy loss on all object proposals:

$\mathcal{L}_{hla}=\max_{\bm{\mathcal{M}}^{S}}\min_{\bm{\mathcal{D}_{p}}}\left\\{-\text{log}\left(1-\bm{D}^{S}\right)-\text{log}\left(\bm{D}^{T}\right)\right\\},\\\
$ (3)

where
$\bm{D}^{S}=\bm{\mathcal{D}_{p}}(\bm{\mathcal{M}}^{S}\left(\bm{X}_{s}\right))$
and $\bm{D}^{T}=\bm{\mathcal{D}_{p}}(\bm{\mathcal{M}}^{S}(\bm{X}_{t}))$ are
the predicted possibilities of the aggregated proposal features
$\bm{\mathcal{M}}^{S}\left(\bm{X}_{s}\right),\bm{\mathcal{M}}^{S}(\bm{X}_{t})$
coming from target domain.

###  3.4 Pseudo Label Refinement

####  3.4.1 Progressive Class-Aware Thresholding

One issue that arises when devising the mean teacher paradigm under UDA
settings for indoor 3D object detection is the occurrence of class-specific
domain gaps, for which we first develop a straightforward class-aware
thresholding strategy that accounts for various confidence distributions
during the pseudo label filtering to handle the class-specific domain gaps.
Initially, all target domain data is fed into the initialized teacher model to
predict pseudo labels, and we store the per-class pseudo label confidence
scores:

$\left[\bm{Q}_{obj}^{c},\bm{Q}_{cls}^{c},\bm{Q}_{iou}^{c}\right]=\left[\bm{\tau}_{obj}^{c}(\bm{\bar{Y}}_{t}),\bm{\tau}_{cls}^{c}(\bm{\bar{Y}}_{t}),\bm{\tau}_{iou}^{c}(\bm{\bar{Y}}_{t})\right],$
(4)

where $\bm{\tau}_{obj}^{c}(\bm{\bar{Y}}_{t})$,
$\bm{\tau}_{cls}^{c}(\bm{\bar{Y}}_{t})$,
$\bm{\tau}_{iou}^{c}(\bm{\bar{Y}}_{t})$ denote the objectness score, maximum
classification score, and IoU score of the proposals in $\bm{\bar{Y}}_{t}$
with class $c$, respectively. We calculate the class-aware thresholds as:

$\bm{T}_{c,m}=\operatorname{Clamp}\left(\operatorname{Percentile}_{\alpha}\left(\bm{Q}_{m}^{c}\right),T_{l}^{m},T_{h}^{m}\right),$
(5)

where $m\in\\{obj,cls,iou\\}$ is the confidence metric,
$\operatorname{Percentile}_{\alpha}\left(\cdot\right)$ is percentile function
that outputs the value higher than $\alpha\%$ of input, and
$\operatorname{Clamp}(\cdot,T_{l},T_{h})$ is clamping between $T_{l}^{m}$ and
$T_{h}^{m}$. On top of the class-aware thresholds, we further perform
progressive updates such that the thresholds are dynamically fit to the pseudo
label confidence distributions, which leads to our Progressive Class-Aware
Thresholding (PCAT). Denoting $\bm{\bar{T}}_{c,m}^{k}$ as the progressive
class-aware threshold for epoch $k$, we update it by:

$\bm{\bar{T}}_{c,m}^{k}=\begin{cases}\quad\quad\quad\quad\bm{T}_{c,m},&k=0,\\\
\beta\cdot\bm{\bar{T}}_{c,m}^{k-1}+(1-\beta)\cdot\bm{T}_{c,m}^{k-1},&\text{otherwise}.\end{cases}$
(6)

Here, $T_{c,m}^{k-1}$ is computed with Eq. (5) using the confidence scores in
epoch $k-1$, and $\beta$ is the update momentum.

####  3.4.2 Model Perturbation based Reweighting

Although the aforementioned PCAT enables adaptively filtering pseudo labels
for diverse object classes, the pseudo labeling loss still assigns uniform
weights for all valid pseudo labels after score filtering. To further mine the
high-quality pseudo labels, we propose the Model Perturbation based
Reweighting (MPR) module, which reweights the pseudo labels according to the
pseudo label consistency. Specifically, given each batch of data, we first
perform random dropout on the teacher detector backbone to get a set of
perturbed teacher models $\\{\bm{\mathcal{M}}^{T}_{p}\\}_{p=1}^{P}$, where $P$
is the number of perturbed models. We then feed it with target domain data and
go through Non-Maximum Suppression (NMS) and PCAT similarly to get the
perturbed pseudo labels $\\{\bar{\bm{Y}}_{t,p}\\}_{p=1}^{P}$. Consequently, we
assess the robustness of $\bar{\bm{Y}}_{t}$ according to their IoU with
$\\{\bar{\bm{Y}}_{t,p}\\}_{p=1}^{P}$, such that each pseudo bounding box is
reweighted based on their consistency w.r.t model perturbation. Formally, we
compute:

$\displaystyle\bm{\mathcal{U}}^{m}=\frac{1}{P}\sum_{p=1}^{P}\max_{n}\
\text{IoU}(\bar{\bm{Y}}_{t}^{m},\bar{\bm{Y}}_{t,p}^{n}),\;\bm{\omega}(\bm{\mathcal{U}}^{m})=1+\lambda_{mpr}\cdot\bm{\mathcal{U}}^{m},$
(7)
$\displaystyle\begin{split}\mathcal{L}_{cla}^{mpr}=&\frac{\sum_{m=1}^{M}\bm{\omega}(\bm{\mathcal{U}}^{m})\cdot\mathcal{L}^{u}\left(\hat{\bm{Y}}_{t}^{m},\bm{\bar{Y}}_{t}^{m}\right)}{\sum_{m=1}^{M}\bm{\omega}(\bm{\mathcal{U}}^{m})}.\end{split}$
(8)

Consequently, the MPR is aimed at mining the consistent pseudo labels, which
is seamlessly integrated with the score filtering to further enhance pseudo
labeling.

###  3.5 Training Objective

The overall loss is given by:

$\mathcal{L}=\mathcal{L}_{sup}+\lambda_{hla}\mathcal{L}_{hla}+\lambda_{cla}\mathcal{L}_{cla}^{mpr},$
(9)

where $\lambda_{hla}$ and $\lambda_{cla}$ are weights to balance different
losses. The losses work synergically on object proposal level, aiming to
achieve hierarchical cross-domain alignments.

##  4 Experiments

###  4.1 Implementations Details

Dataset settings. For the data preprocessing of 3D-FRONT [Fu et al.(2021)Fu,
Cai, Gao, Zhang, Wang, Li, Zeng, Sun, Jia, Zhao, et al.], we obtain point
clouds by uniformly sampling on the mesh surfaces, and select scenes with
$3\sim 20$ interested objects, getting 10,515 scenes for training and 1,104
scenes for validation. As for the label mapping, we select 10 and 7 object
categories for 3D-FRONT $\rightarrow$ ScanNetV2 and 3D-FRONT $\rightarrow$ SUN
RGB-D settings, respectively.

Experiment settings. We leverage VoteNet [Qi et al.(2019)Qi, Litany, He, and
Guibas] as the detector and first train it on 3D-FRONT for 50 epochs, then
adapt it to target domains ScanNetV2 and SUN RGB-D individually. We regard
traversing target domain as one epoch, and respectively train 100 and 50
epochs for ScanNetV2 and SUN RGB-D.

###  4.2 Baselines

We set up baselines under source-only and UDA settings. For UDA setting, we
use OAA+VSS for source domain augmentation. Since there is no prior work
focusing on the UDA problem for indoor 3D object detection, we set up the
following baselines:

Naive MT [Tarvainen and Valpola(2017)]: Based on the mean teacher paradigm, we
reproduce the losses in VoteNet [Qi et al.(2019)Qi, Litany, He, and Guibas]
for the unlabeled target domain data, using the pseudo labels provided by the
mean teacher.

| Method | cab | bed | chair | sofa | tabl | door | wind | bkshf | desk | nigst |  mAP25 |  mAP50
---|---|---|---|---|---|---|---|---|---|---|---|---|---
SO |  _w/o Aug._ [Qi et al.(2019)Qi, Litany, He, and Guibas] | 2.1 | 50.1 | 63.9 | 45.7 | 36.3 | 2.5 | 0.7 | 25.1 | 23.1 | 15.8 | 26.5 | 13.5
VSS [Ding et al.(2022)Ding, Yang, Jiang, and Qi] | 9.3 | 61.3 | 55.2 | 67.3 | 37.4 | 2.4 | 4.8 | 28.3 | 25.7 | 40.6 | 33.2 | 19.1
OAA+VSS | 9.7 | 61.7 | 55.3 | 74.8 | 41.0 | 1.8 | 4.4 | 29.9 | 29.8 | 42.6 | 35.1 | 20.3
UDA |  Naive MT† [Tarvainen and Valpola(2017)] | 7.6 | 60.7 | 65.5 | 63.3 | 40.4 | 2.1 | 3.3 | 30.5 | 11.9 | 44.3 | 33.0 | 20.0
ST3D† [Yang et al.(2021)Yang, Shi, Wang, Li, and Qi] | 10.7 | 54.9 | 66.5 | 77.0 | 39.2 | 3.0 | 5.9 | 32.7 | 27.1 | 49.1 | 36.3 | 22.6
Global-DAT† [DeBortoli et al.(2021)DeBortoli, Fuxin, Kapoor, and Hollinger] | 6.0 | 63.4 | 57.3 | 66.6 | 42.9 | 1.6 | 3.6 | 22.3 | 40.7 | 25.3 | 32.9 | 19.3
Ours w/o PLR | 12.0 | 60.8 | 69.1 | 77.9 | 41.3 | 2.0 | 6.5 | 31.2 | 29.2 | 55.2 | 38.5 | 23.9
| Ours | 12.2 | 58.8 | 71.0 | 80.2 | 45.7 | 4.4 | 16.0 | 35.4 | 42.7 | 64.6 | 42.9 | 27.6
FS | Oracle | 32.0 | 87.4 | 86.3 | 88.3 | 55.5 | 39.1 | 34.7 | 39.0 | 69.6 | 76.7 | 60.9 | 39.9
Table 1: 3D-FRONT $\rightarrow$ ScannetV2 with per object category<EMAIL_ADDRESS>results. We compare the results under Source-Only (SO), UDA and Fully-Supervised (FS) settings. Aug. denotes data augmentations. We indicate the best and runner-up adaptation results by bold and underline, respectively. | Method | bed | tabl | sofa | chair | desk | nigst | bkshf |  mAP25 |  mAP50
---|---|---|---|---|---|---|---|---|---|---
SO |  _w/o Aug._ [Qi et al.(2019)Qi, Litany, He, and Guibas] | 35.3 | 28.1 | 19.6 | 40.2 | 7.3 | 1.4 | 4.4 | 19.5 | 6.4
VSS [Ding et al.(2022)Ding, Yang, Jiang, and Qi] | 58.2 | 30.9 | 39.9 | 45.5 | 11.7 | 5.4 | 5.4 | 28.2 | 11.0
OAA+VSS | 61.5 | 29.9 | 42.4 | 45.2 | 13.8 | 15.2 | 4.8 | 30.4 | 14.1
UDA |  Naive MT† [Tarvainen and Valpola(2017)] | 64.4 | 27.3 | 37.9 | 41.0 | 5.3 | 26.2 | 4.1 | 29.5 | 10.6
ST3D† [Yang et al.(2021)Yang, Shi, Wang, Li, and Qi] | 70.3 | 33.4 | 37.7 | 50.4 | 11.4 | 26.9 | 5.8 | 33.8 | 15.1
Global-DAT† [DeBortoli et al.(2021)DeBortoli, Fuxin, Kapoor, and Hollinger] | 55.3 | 27.9 | 37.6 | 39.8 | 8.9 | 5.1 | 4.9 | 25.6 | 9.6
Ours w/o PLR | 71.8 | 35.7 | 42.5 | 54.0 | 8.5 | 29.4 | 6.2 | 35.5 | 15.6
| Ours | 73.7 | 36.2 | 46.1 | 54.7 | 12.0 | 28.8 | 9.8 | 37.3 | 18.3
FS | Oracle | 84.1 | 50.6 | 60.7 | 74.2 | 23.5 | 56.9 | 28.0 | 54.0 | 29.1
Table 2: 3D-FRONT $\rightarrow$ SUN RGB-D with per object category<EMAIL_ADDRESS>results.

(a)

(b)

(c)

(d)

(e) VSS Source Only (f) ST3D (g) Ours (h) Ground Truth

Figure 3: Qualitative results on ScanNetV2 (first row) and SUN RGB-D (second
row).

ST3D [Yang et al.(2021)Yang, Shi, Wang, Li, and Qi]: We reproduce their
adaptation results for indoor object detection using their consistency
ensemble, where we only use box loss and semantic loss for self-training,
similarly to our $\mathcal{L}_{cla}$. Their consistency ensemble can be
regarded as a variant of our MPR module.

Global-DAT [DeBortoli et al.(2021)DeBortoli, Fuxin, Kapoor, and Hollinger]: We
average the seed point features and feed to a global discriminator to predict
the domain, and perform min-max optimization similarly.

###  4.3 Main Results

3D-FRONT $\rightarrow$ ScanNetV2 results. As shown in Table 1, for data
augmentation, OAA enhances mAP by $1\%\sim 2\%$ upon integration with VSS
[Ding et al.(2022)Ding, Yang, Jiang, and Qi]. In the UDA scenario, the direct
application of naive MT [Tarvainen and Valpola(2017)] and Global-DAT
[DeBortoli et al.(2021)DeBortoli, Fuxin, Kapoor, and Hollinger] to the SR-UDA
problem results in performance drop, and the ST3D only boosts mAP marginally
by $1\sim 2\%$. In contrast, our OHDA w/o PLR already yields substantial
gains, and the introduction of PLR elevates the mAP by $\sim 4\%$, surpassing
the VSS Source-Only baseline by $9.7\%$ mAP.

3D-FRONT $\rightarrow$ SUN RGB-D results. In Table 2, under the 3D-FRONT
$\rightarrow$ SUN RGB-D setting, our approach achieves an mAP increase of
$9.1\%$ compared to the VSS-augmented source-only baseline, outperforming
other UDA methods adapted from different contexts. Note that the results
demonstrate the necessity of our proposed Local Pattern Preserved Augmentation
strategy, which significantly benefits the model in learning the object
headings.

Qualitative results. The qualitative comparisons are shown in Figure 3. We
demonstrate qualitative improvements where we predict more precise bounding
boxes with higher recall.

(a) w/o Aug

(b) w/o CLA

(c) w/o HLA

(d) w/o PLR

(e) Ours

(f) Ground Truth

Figure 4: Qualitative results for ablation study. Better viewed in color with
zoom in.

###  4.4 Ablation Study

The ablation study is detailed both quantitatively in Table 3 and
qualitatively in Figure 4.

Aug. | CLA | HLA | PLR | ScanNetV2 | SUN RGB-D
---|---|---|---|---|---
mAP25 |  mAP50 |  mAP25 |  mAP50
✘ | ✓ | ✓ | ✓ | 37.0 | 22.2 | 29.3 | 13.5
✓ | ✘ | ✓ |  ✓∗ | 35.6 | 22.0 | 31.6 | 13.4
✓ | ✓ | ✘ | ✘ | 35.9 | 21.0 | 33.1 | 14.7
✓ | ✓ | ✘ | ✓ | 39.3 | 24.1 | 35.5 | 16.8
✓ | ✓ | ✓ | ✘ | 38.5 | 23.9 | 35.5 | 15.6
✓ | ✓ | ✓ | ✓ | 42.9 | 27.6 | 37.3 | 18.3
Table 3: Ablation study. ∗: PLR is invalid without CLA.

The results substantiate the necessity of each component in our proposed
methodology. Furthermore, an integration of the results from Table 1 and Table
2 reveals a notable insight: while domain adversarial training and naive
pseudo labeling might lead to only marginal improvements or even a decline in
performance when implemented separately, their integration markedly boosts
overall performance, underscoring the merits of OHDA framework.

##  5 Conclusion

In this paper we present OHDA framework, a pioneering solution to the SR-UDA
challenge in indoor 3D object detection. Our key contribution is the
integration of proposal-level domain adversarial training and pseudo labeling,
which simultaneously align cross-domain proposal feature space and perform
effective joint-training under complicated domain shifts. Extensive
experiments underline the impressive efficacy of our approach in tackling the
SR-UDA problem, where we achieve $9\%$ $\sim$ $10\%$ consistent mAP gains over
Source-Only baselines and consistently surpass existing UDA methods adapted
from outdoor scenario.

## References

  * [Cai et al.(2019)Cai, Pan, Ngo, Tian, Duan, and Yao] Qi Cai, Yingwei Pan, Chong-Wah Ngo, Xinmei Tian, Lingyu Duan, and Ting Yao.  Exploring object relation in mean teacher for cross-domain detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11457–11466, 2019.
  * [Chen et al.(2020)Chen, Zheng, Ding, Huang, and Dou] Chaoqi Chen, Zebiao Zheng, Xinghao Ding, Yue Huang, and Qi Dou.  Harmonizing transferability and discriminability for adapting object detectors.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8869–8878, 2020.
  * [Chen et al.(2018)Chen, Li, Sakaridis, Dai, and Van Gool] Yuhua Chen, Wen Li, Christos Sakaridis, Dengxin Dai, and Luc Van Gool.  Domain adaptive faster r-cnn for object detection in the wild.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3339–3348, 2018.
  * [Cheng et al.(2021)Cheng, Sheng, Shi, Yang, and Xu] Bowen Cheng, Lu Sheng, Shaoshuai Shi, Ming Yang, and Dong Xu.  Back-tracing representative points for voting-based 3d object detection in point clouds.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8963–8972, 2021.
  * [Dai et al.(2017)Dai, Chang, Savva, Halber, Funkhouser, and Nießner] Angela Dai, Angel X Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 5828–5839, 2017.
  * [DeBortoli et al.(2021)DeBortoli, Fuxin, Kapoor, and Hollinger] Robert DeBortoli, Li Fuxin, Ashish Kapoor, and Geoffrey A Hollinger.  Adversarial training on point clouds for sim-to-real 3d object detection.  _IEEE Robotics and Automation Letters_ , 6(4):6662–6669, 2021.
  * [Deng et al.(2021)Deng, Li, Chen, and Duan] Jinhong Deng, Wen Li, Yuhua Chen, and Lixin Duan.  Unbiased mean teacher for cross-domain object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4091–4101, 2021.
  * [Ding et al.(2022)Ding, Yang, Jiang, and Qi] Runyu Ding, Jihan Yang, Li Jiang, and Xiaojuan Qi.  Doda: Data-oriented sim-to-real domain adaptation for 3d indoor semantic segmentation.  _arXiv preprint arXiv:2204.01599_ , 2022.
  * [Fu et al.(2021)Fu, Cai, Gao, Zhang, Wang, Li, Zeng, Sun, Jia, Zhao, et al.] Huan Fu, Bowen Cai, Lin Gao, Ling-Xiao Zhang, Jiaming Wang, Cao Li, Qixun Zeng, Chengyue Sun, Rongfei Jia, Binqiang Zhao, et al.  3d-front: 3d furnished rooms with layouts and semantics.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10933–10942, 2021.
  * [Gall et al.(2011)Gall, Yao, Razavi, Van Gool, and Lempitsky] Juergen Gall, Angela Yao, Nima Razavi, Luc Van Gool, and Victor Lempitsky.  Hough forests for object detection, tracking, and action recognition.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(11):2188–2202, 2011.
  * [Ganin and Lempitsky(2015)] Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In _International conference on machine learning_ , pages 1180–1189. PMLR, 2015.
  * [Ganin et al.(2016)Ganin, Ustinova, Ajakan, Germain, Larochelle, Laviolette, Marchand, and Lempitsky] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky.  Domain-adversarial training of neural networks.  _The journal of machine learning research_ , 17(1):2096–2030, 2016.
  * [Ganin et al.(2017)Ganin, Ustinova, Ajakan, Germain, Larochelle, Laviolette, Marchand, and Lempitsky] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Francois Laviolette, Mario Marchand, and Victor Lempitsky.  _Domain-Adversarial Training of Neural Networks_.  09 2017.
  * [Guan et al.(2021)Guan, Huang, Lu, and Xiao] Dayan Guan, Jiaxing Huang, Shijian Lu, and Aoran Xiao.  Scale variance minimization for unsupervised domain adaptation in image segmentation.  _Pattern Recognition_ , 112:107764, 2021.
  * [Hou et al.(2019)Hou, Dai, and Nießner] Ji Hou, Angela Dai, and Matthias Nießner.  3d-sis: 3d semantic instance segmentation of rgb-d scans.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 4421–4430, 2019.
  * [Huang et al.(2021)Huang, Guan, Xiao, and Lu] Jiaxing Huang, Dayan Guan, Aoran Xiao, and Shijian Lu.  Cross-view regularization for domain adaptive panoptic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10133–10144, 2021.
  * [Huang et al.(2022)Huang, Guan, Xiao, and Lu] Jiaxing Huang, Dayan Guan, Aoran Xiao, and Shijian Lu.  Multi-level adversarial network for domain adaptive semantic segmentation.  _Pattern Recognition_ , 123:108384, 2022.
  * [Lahoud and Ghanem(2017)] Jean Lahoud and Bernard Ghanem.  2d-driven 3d object detection in rgb-d images.  In _Proceedings of the IEEE international conference on computer vision_ , pages 4622–4630, 2017.
  * [Li et al.(2019)Li, Yuan, and Vasconcelos] Yunsheng Li, Lu Yuan, and Nuno Vasconcelos.  Bidirectional learning for domain adaptation of semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6936–6945, 2019.
  * [Liu et al.(2021)Liu, Zhang, Cao, Hu, and Tong] Ze Liu, Zheng Zhang, Yue Cao, Han Hu, and Xin Tong.  Group-free 3d object detection via transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2949–2958, 2021.
  * [Long et al.(2015)Long, Cao, Wang, and Jordan] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan.  Learning transferable features with deep adaptation networks.  In _International conference on machine learning_ , pages 97–105. PMLR, 2015.
  * [Long et al.(2016)Long, Zhu, Wang, and Jordan] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I Jordan.  Unsupervised domain adaptation with residual transfer networks.  _Advances in neural information processing systems_ , 29, 2016.
  * [Long et al.(2017)Long, Zhu, Wang, and Jordan] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I Jordan.  Deep transfer learning with joint adaptation networks.  In _International conference on machine learning_ , pages 2208–2217. PMLR, 2017.
  * [Maturana and Scherer(2015)] Daniel Maturana and Sebastian Scherer.  Voxnet: A 3d convolutional neural network for real-time object recognition.  In _2015 IEEE/RSJ international conference on intelligent robots and systems (IROS)_ , pages 922–928. IEEE, 2015.
  * [Qi et al.(2018)Qi, Liu, Wu, Su, and Guibas] Charles R Qi, Wei Liu, Chenxia Wu, Hao Su, and Leonidas J Guibas.  Frustum pointnets for 3d object detection from rgb-d data.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 918–927, 2018.
  * [Qi et al.(2019)Qi, Litany, He, and Guibas] Charles R Qi, Or Litany, Kaiming He, and Leonidas J Guibas.  Deep hough voting for 3d object detection in point clouds.  In _proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 9277–9286, 2019.
  * [Qi et al.(2017)Qi, Yi, Su, and Guibas] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  _Advances in neural information processing systems_ , 30, 2017.
  * [Radopoulou et al.(2012)Radopoulou, Sun, Dai, Brilakis, and Savarese] SC Radopoulou, M Sun, F Dai, I Brilakis, and S Savarese.  Testing of depth-encoded hough voting for infrastructure object detection.  In _Computing in Civil Engineering (2012)_ , pages 309–316. 2012.
  * [Reuse et al.(2021)Reuse, Simon, and Sick] Matthias Reuse, Martin Simon, and Bernhard Sick.  About the ambiguity of data augmentation for 3d object detection in autonomous driving.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 979–987, 2021.
  * [Saito et al.(2018)Saito, Watanabe, Ushiku, and Harada] Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.  Maximum classifier discrepancy for unsupervised domain adaptation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3723–3732, 2018.
  * [Saltori et al.(2020)Saltori, Lathuiliére, Sebe, Ricci, and Galasso] Cristiano Saltori, Stéphane Lathuiliére, Nicu Sebe, Elisa Ricci, and Fabio Galasso.  Sf-uda 3d: Source-free unsupervised domain adaptation for lidar-based 3d object detection.  In _2020 International Conference on 3D Vision (3DV)_ , pages 771–780. IEEE, 2020.
  * [Song et al.(2015)Song, Lichtenberg, and Xiao] Shuran Song, Samuel P Lichtenberg, and Jianxiong Xiao.  Sun rgb-d: A rgb-d scene understanding benchmark suite.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 567–576, 2015.
  * [Su et al.(2020)Su, Wang, Zeng, Tang, Chen, Qiu, and Wang] Peng Su, Kun Wang, Xingyu Zeng, Shixiang Tang, Dapeng Chen, Di Qiu, and Xiaogang Wang.  Adapting object detectors with conditional domain normalization.  In _European Conference on Computer Vision_ , pages 403–419. Springer, 2020.
  * [Tarvainen and Valpola(2017)] Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  _Advances in neural information processing systems_ , 30, 2017.
  * [Tsai et al.(2022)Tsai, Berrio, Shan, Worrall, and Nebot] Darren Tsai, Julie Stephany Berrio, Mao Shan, Stewart Worrall, and Eduardo Nebot.  See eye to eye: A lidar-agnostic 3d detection framework for unsupervised multi-target domain adaptation.  _IEEE Robotics and Automation Letters_ , 7(3):7904–7911, 2022.
  * [Tzeng et al.(2017)Tzeng, Hoffman, Saenko, and Darrell] Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell.  Adversarial discriminative domain adaptation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 7167–7176, 2017.
  * [Wang et al.(2021a)Wang, Cong, Litany, Gao, and Guibas] He Wang, Yezhen Cong, Or Litany, Yue Gao, and Leonidas J Guibas.  3dioumatch: Leveraging iou prediction for semi-supervised 3d object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14615–14624, 2021a.
  * [Wang et al.(2021b)Wang, Dai, Hoyer, Van Gool, and Fink] Qin Wang, Dengxin Dai, Lukas Hoyer, Luc Van Gool, and Olga Fink.  Domain adaptive semantic segmentation with self-supervised depth estimation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 8515–8525, 2021b.
  * [Wang et al.(2020)Wang, Chen, You, Li, Hariharan, Campbell, Weinberger, and Chao] Yan Wang, Xiangyu Chen, Yurong You, Li Erran Li, Bharath Hariharan, Mark Campbell, Kilian Q Weinberger, and Wei-Lun Chao.  Train in germany, test in the usa: Making 3d object detectors generalize.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11713–11723, 2020.
  * [Xu et al.(2020)Xu, Zhao, Jin, and Wei] Chang-Dong Xu, Xing-Ran Zhao, Xin Jin, and Xiu-Shen Wei.  Exploring categorical regularization for domain adaptive object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11724–11733, 2020.
  * [Yang et al.(2021)Yang, Shi, Wang, Li, and Qi] Jihan Yang, Shaoshuai Shi, Zhe Wang, Hongsheng Li, and Xiaojuan Qi.  St3d: Self-training for unsupervised domain adaptation on 3d object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10368–10378, 2021.
  * [Zhang et al.(2020)Zhang, Sun, Yang, and Huang] Zaiwei Zhang, Bo Sun, Haitao Yang, and Qixing Huang.  H3dnet: 3d object detection using hybrid geometric primitives.  In _European Conference on Computer Vision_ , pages 311–329. Springer, 2020.
  * [Zheng et al.(2022)Zheng, Duan, Lu, Zhou, and Tian] Yu Zheng, Yueqi Duan, Jiwen Lu, Jie Zhou, and Qi Tian.  Hyperdet3d: Learning a scene-conditioned 3d object detector.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5585–5594, 2022.
  * [Zhou and Tuzel(2018)] Yin Zhou and Oncel Tuzel.  Voxelnet: End-to-end learning for point cloud based 3d object detection.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4490–4499, 2018.
  * [Zou et al.(2019)Zou, Yu, Liu, Kumar, and Wang] Yang Zou, Zhiding Yu, Xiaofeng Liu, BVK Kumar, and Jinsong Wang.  Confidence regularized self-training.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5982–5991, 2019.