# Maximizing Approximately $k$-Submodular Functions††thanks: Partially
supported by NSFC Project 11771365.

Leqian Zheng Hau Chan Grigorios Loukides Minming Li City University of Hong
Kong, Hong Kong SAR<EMAIL_ADDRESS>of Nebraska-
Lincoln, USA<EMAIL_ADDRESS>College London, UK,
<EMAIL_ADDRESS>University of Hong Kong, Hong Kong SAR, and
City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R.
China<EMAIL_ADDRESS>
###### Abstract

We introduce the problem of maximizing _approximately_ $k$-submodular
functions subject to size constraints. In this problem, one seeks to select
$k$-disjoint subsets of a ground set with bounded total size or individual
sizes, and maximum utility, given by a function that is “close” to being
$k$-submodular. The problem finds applications in tasks such as sensor
placement, where one wishes to install $k$ types of sensors whose measurements
are noisy, and influence maximization, where one seeks to advertise $k$ topics
to users of a social network whose level of influence is uncertain. To deal
with the problem, we first provide two natural definitions for approximately
$k$-submodular functions and establish a hierarchical relationship between
them. Next, we show that simple greedy algorithms offer approximation
guarantees for different types of size constraints. Last, we demonstrate
experimentally that the greedy algorithms are effective in sensor placement
and influence maximization problems.

##  1 Introduction

A $k$-submodular function is a natural generalization of a submodular function
to $k$ arguments or dimensions [15]. Recently, there has been an increased
theoretical and algorithmic interest in studying the problem of maximizing
(monotone) _$k$ -submodular functions_, with [21] or without [15, 25, 16] size
constraints. The problem finds applications in sensor placement [21],
influence maximization [21], coupled feature selection [24], and network cut
capacity optimization [16]. In these applications, one wishes to select $k$
_disjoint_ subsets from a ground set that maximize a given function with $k$
arguments subject to an upper bound on the total size of the selected subsets
or the size of each individual selected subset [21]. Such a function of
interest often has a _diminishing returns property_ with respect to each
subset when fixing the other $k-1$ subsets [15].

More formally, let $V=\\{1,...,n\\}=[n]$ be a finite ground set of $n$
elements and $(k+1)^{V}=\\{(X_{1},X_{2},\dots,X_{k})\mid X_{i}\subseteq
V,\forall i\in[k],X_{i}\cap X_{j}=\emptyset\\}$ be the set of $k$-disjoint
subsets. A function $f:(k+1)^{V}\to\mathbb{R}^{+}$ is $k$-submodular if and
only if, for any $\boldsymbol{x},\boldsymbol{y}\in(k+1)^{V}$,

$\displaystyle
f(\boldsymbol{x})+f(\boldsymbol{y})\geq{}f(\boldsymbol{x}\sqcap\boldsymbol{y})+f(\boldsymbol{x}\sqcup\boldsymbol{y}),$

where
$\boldsymbol{x}\sqcap\boldsymbol{y}=(X_{1}\cap{}Y_{1},X_{2}\cap{}Y_{2},\ldots,X_{k}\cap{}Y_{k})$
and

$\displaystyle\boldsymbol{x}\sqcup\boldsymbol{y}=(X_{1}\cup{}Y_{1}\setminus(\bigcup_{i\neq{1}}X_{i}\cup{}Y_{i}),\ldots,X_{k}\cup{}Y_{k}\setminus(\bigcup_{i\neq{k}}X_{i}\cup{}Y_{i})).$

A $k$-submodular function $f$ is _monotone_ if and only if, for any
$\boldsymbol{x},\boldsymbol{y}\in(k+1)^{V}$ such that
${\boldsymbol{x}}\preceq{\boldsymbol{y}}$ (i.e., $X_{i}\subseteq Y_{i},$
$\forall i\in[k]$), $f(\boldsymbol{x})\leq f(\boldsymbol{y})$. The problem of
maximizing a monotone $k$-submodular function $f$ subject to the _total size_
(TS) and _individual size_ (IS) constraints [21] is

$\displaystyle\max_{\boldsymbol{x}\in(k+1)^{V}:|\cup_{i\in[k]}X_{i}|\leq
B}f(\boldsymbol{x})~{}~{}\text{ and
}~{}~{}\max_{\boldsymbol{x}\in(k+1)^{V}:|X_{i}|\leq B_{i}\;\forall
i\in[k]}f(\boldsymbol{x}),$

respectively, for some positive integers $B\in\mathbb{Z}^{+}$ and
$B_{i}\in\mathbb{Z}^{+}$ for all $i\in[k]$. While recent results [21] show
that the above two problems can be well-approximated using greedy algorithms
(with an approximation ratio of $\frac{1}{2}$ and $\frac{1}{3}$ for total size
and individual size constraints, respectively) under the value oracle model,
not much is known when the function is not entirely $k$-submodular, which can
result from the oracle being inaccurate or the function itself not being
$k$-submodular by default (see examples and applications below). In fact,
often there is no access to the exact value of the function but only to noisy
values of it. In this paper, we initiate the study of the above maximization
problems for non-$k$-submodular functions and pose the following questions:

> Q1. _How to define an approximately $k$-submodular function?_
>
> Q2. _What approximation guarantees can be obtained when maximizing such a
> function under total size or individual size constraints?_

|  $\varepsilon$-AS |  $\varepsilon$-ADR
---|---|---
$F$’s Solution |  $F$’s Solution |  $f$’s Solution |  $F$’s Solution
$k=1$ |  $\frac{1}{1+\frac{4B\varepsilon}{(1-\varepsilon)^{2}}}\left(1-\left(\frac{1-\varepsilon}{1+\varepsilon}\right)^{2B}\left(1-\frac{1}{B}\right)^{B}\right)$ [14] | $\frac{1-\varepsilon}{1+\varepsilon}\left(1-\frac{1}{e}\right)$ | $\left(1-e^{-\frac{(1-\varepsilon)}{(1+\varepsilon)}}\right)$
$k\geq 2$ | TS | $\frac{(1-\varepsilon)^{2}}{2(1-\varepsilon+\varepsilon B)(1+\varepsilon)}$ | $\frac{1-\varepsilon}{2(1+\varepsilon)}$ | $\frac{1-\varepsilon}{2}$
IS | $\frac{(1-\varepsilon)^{2}}{(3-3\varepsilon+2\varepsilon B)(1+\varepsilon)}$ | $\frac{1-\varepsilon}{3(1+\varepsilon)}$ | $\frac{1-\varepsilon}{3+\varepsilon}$

Table 1: Approximation ratios of the greedy algorithms of [21] for maximizing
$\varepsilon$-approximately $k$-submodular ($\varepsilon$-AS) and
$\varepsilon$-approximately diminishing returns ($\varepsilon$-ADR) function
$F$ under a total size (TS) constraint $B$, or individual size (IS)
constraints $B_{1},...,B_{k}$ with $B=\sum_{i\in[k]}B_{i}$, when they are
applied to $F$ or to $f$. An algorithm has approximation ratio $\alpha\leq 1$
if and only if it returns a (feasible) solution $\boldsymbol{x}\in{(k+1)^{V}}$
such that $f(\boldsymbol{x})\geq\alpha f(\boldsymbol{x}^{*})$, where
$\boldsymbol{x}^{*}$ is an optimal solution.

Applications. Answering Q1 and Q2 could be important in optimization, machine
learning, and beyond. Let us first consider the case of $k=1$. In many
applications, a function $F$ is _approximately submodular_ rather than
submodular (i.e., $(1-\varepsilon)f(x)\leq F(x)\leq(1+\varepsilon)f(x)$, for
an $\varepsilon>0$, where $f$ is a monotone submodular function) [14, 13, 23].
These applications include subset selection which is fundamental in areas such
as (sequential) document summarization, sensor placement, and influence
maximization [21, 9]. For example, in sensor placement, the objective is to
select a subset of good sensors and the approximation comes from sensors
producing noisy values due to hardware issues, environmental effects, and
imprecision in measurement [10, 2]. In influence maximization, the objective
is to select a subset of good users to start a viral marketing campaign over a
social network and the approximation comes from our uncertainty about the
level of influence of specific users in the social network [17, 11, 26]. Other
applications are PMAC learning [5, 4, 1], where the objective is to learn a
submodular function, and sketching [3], where the objective is to find a good
representation of a submodular function of polynomial size.

In many of these applications, it is often needed to select $k$ disjoint
subsets of given maximum total size or sizes, instead of a single subset,
which gives rise to size-constrained $k$-submodular function maximization
[21]. This is the case for sensor placement where $k$ types of sensors need to
be placed in disjoint subsets of locations, or influence maximization where
$k$ viral marketing campaigns, each starting from a different subset of users,
need to be performed simultaneously over the same social network. Again, a
function may not be exactly $k$-submodular, due to noise in sensor
measurements and uncertainty in user influence levels. Thus, by answering
question Q1, we could more accurately model the quality of solutions in these
applications and, by answering Q2, we could obtain solutions of guaranteed
quality.

Our Contributions. We address Q1 by introducing two natural definitions of an
approximately $k$-submodular function. To the best of our knowledge,
approximately $k$-submodular functions have not been defined or studied before
for general $k>1$. Namely, we define a function $F:(k+1)^{V}\to\mathbb{R}^{+}$
as $\varepsilon$-_approximately $k$-submodular_ ($\varepsilon$-AS) or
_$\varepsilon$ -approximately diminishing returns_ ($\varepsilon$-ADR) for
some small $\varepsilon>0$, if and only if there exists a monotone
k-submodular function $f$ such that for any $\boldsymbol{x}\in{(k+1)^{V}}$,
$u\not\in\bigcup_{l\in[k]}X_{l}$, $u\in V$ and $i\in[k]$

$\displaystyle\varepsilon\text{-AS}:$
$\displaystyle~{}(1-\varepsilon)f(\boldsymbol{x})\leq
F(\boldsymbol{x})\leq(1+\varepsilon)f(\boldsymbol{x})\text{ or }$
$\displaystyle\varepsilon\text{-ADR}:$
$\displaystyle~{}(1-\varepsilon)\Delta_{u,i}f(\boldsymbol{x})\leq{}\Delta_{u,i}F(\boldsymbol{x})\leq{}(1+\varepsilon)\Delta_{u,i}f(\boldsymbol{x}),$

where
$\Delta_{u,i}f({\boldsymbol{x}})=f(X_{1},\ldots,X_{i-1},X_{i}\cup\\{u\\},X_{i+1},\ldots,X_{k})-f(X_{1},\ldots,X_{k})$
and $\Delta_{u,i}F(\boldsymbol{x})$ is defined similarly. Our $\varepsilon$-AS
definition generalizes the approximately submodular definition of [14] from
$k=1$ to $k\geq 1$ dimensions. The $\varepsilon$-ADR definition is related to
the _marginal gain_ of the functions $F$ and $f$ and implies
$\alpha$-submodularity when $k=1$ [12]. As we will show, an $\varepsilon$-ADR
function $F$ is also $\varepsilon$-AS. However, the converse is not true.
Thus, we establish a novel approximately $k$-submodular hierarchy for $k\geq
1$.

We address Q2 by considering the maximization problems on a function $F$ that
is $\varepsilon$-AS or $\varepsilon$-ADR, subject to the total size (TS) or
individual size (IS) constraint. We show that, when applying the simple greedy
algorithms of [21] for TS and IS, we obtain approximation guarantees that
depend on $\varepsilon$. Table 1 provides an overview of our results. Note
that there are two cases with respect to an $\varepsilon$-AS $F$ and $f$ where
we can apply greedy algorithms to $F$ or $f$ (when $f$ is known). A surprising
observation is that we can derive better approximation ratios by applying the
greedy algorithms to $f$ and using the solutions to approximate $F$. When only
$F$ is known (e.g., through a noisy oracle, an approximately learned
submodular function, or a sketch), we provide approximation ratios of the
greedy algorithms being applied to $F$. When the function $F$ is
$\varepsilon$-ADR, we provide better approximation guarantees, compared to
when $F$ is $\varepsilon$-AS.

We conduct experiments on two real datasets to evaluate the effectiveness of
the greedy algorithms in a $k$-type sensor placement problem and a $k$-topic
influence maximization problem for our setting. We provide three approximately
$k$-submodular function generation/noise methods for generating function
values. Our experimental results are consistent with the theoretical findings
of the derived approximation ratios and showcase the impact of the type of
noise on the quality of the solutions.

Organization. Section 2 discusses related work. Section 3 provides some
preliminaries and establishes a strong relationship between $\varepsilon$-AS
and $\varepsilon$-ADR. Section 4 and Section 5 considers the approximation
ratios of the greedy algorithms for maximizing an $\varepsilon$-AS and
$\varepsilon$-ADR function for $k=1$ and $k>1$, respectively. Section 6
discusses the approximation ratios of $f$’s greedy solutions to $F$. Section 7
presents experimental results. In Section 8, we conclude and present
extensions.

##  2 Related Work.

The works of [13, 23] and [14] consider the problem of maximizing an
approximately submodular function (e.g., $\varepsilon$-AS definition with
$k=1$) subject to constraints under stochastic errors (e.g., $\varepsilon$)
drawn i.i.d. from some distributions and sub-constant (bounded) errors,
respectively. Our paper focuses on the latter setting with $k\geq 1$ and
considers the performance of greedy algorithms with respect to errors (e.g., a
fixed $\varepsilon$). In particular, [14] shows that, for some
$\varepsilon=\frac{1}{n^{1/2-\beta}}$ for $\beta>0$, no algorithm can obtain
any constant approximation ratio using polynomially many queries of the value
oracle. The same lower bound can be applied to our setting. However, when
$\varepsilon$ is sufficiently small with respect to the size constraint (e.g.,
$\varepsilon=\frac{\delta}{B}$), the standard greedy algorithm [19] provides
an (almost) constant approximation ratio of $(1-1/e-O(\delta))$.

Under the stochastic noise assumptions, [13] shows that, when the size
constraint $B\in\Omega(\log\log n)$ is sufficiently large, there is an
algorithm that achieves $(1-1/e)$ approximation ratio with high probability
(w.h.p.) and also shows some impossibility results for the existence of
randomized algorithms with a good approximation ratio using a polynomial
number of queries w.h.p. The work of [23] shows that good approximation ratios
are attainable (e.g., an approximation ratio of $(1-1/e)$) w.h.p. and/or in
expectation for arbitrary size constraint $B$ using greedy algorithms (with or
without randomization) under different size constraints. Additionally, [23]
considers general matroid constraints and provides an approximation ratio that
depends on the matroid constraints. Another work [22] considers the
approximate function maximization problem (with $f$ that is not necessarily
submodular) under the cardinality constraint and derives several approximation
ratios that depend on the submodularity ratio [8], $\varepsilon$, and $B$
using the greedy algorithm, as well as an algorithm based on the Pareto
Optimization for Subset Selection (POSS) strategy.

A recently published work [20] explores the problem of maximizing approximate
$k$-submodular functions in the streaming context, where the elements of $V$
are scanned at most once, under the total size constraint. The approximate
notion, introduced independently, is that of our $\varepsilon$-AS. However,
[20] aims to optimize $f$ instead of $F$, which is the main focus of our work,
and it does not consider $\varepsilon$-ADR nor individual size constraints.

##  3 Preliminaries

We denote the vector of $k$ empty subsets by ${\bf
0}=(X_{1}=\\{\\},\ldots,X_{k}=\\{\\})$. Without loss of generality, we assume
that the functions $F$ and $f$ are normalized such that
$F(\textbf{0})=f(\textbf{0})=0$. We define $k$-submodular functions as those
that are monotone and have a diminishing returns property in each dimension
[25].

######  Definition 3.1 ($k$-submodular function [25])

A function $f:(k+1)^{V}\rightarrow\mathbb{R}$ is $k$-_submodular_ if and only
if: (a) $\Delta_{u,i}f({\boldsymbol{x}})\geq\Delta_{u,i}f({\boldsymbol{y}})$,
for all ${\boldsymbol{x}},{\boldsymbol{y}}\in(k+1)^{V}$ with
${\boldsymbol{x}}\preceq{\boldsymbol{y}}$, $u\notin\cup_{\ell\in[k]}Y_{i}$,
and $i\in[k]$, and (b)
$\Delta_{u,i}f({\boldsymbol{x}})+\Delta_{u,j}f({\boldsymbol{x}})\geq 0$, for
any ${\boldsymbol{x}}\in(k+1)^{V}$, $u\notin\cup_{\ell\in[k]}X_{i}$, and
$i,j\in[k]$ with $i\neq j$.

Part (a) of Definition 3.1 is known as the _diminishing returns_ property and
part (b) as _pairwise monotonicity_. We assume that the function is monotone,
and this implies pairwise monotonicity directly. Moreover, $k$-submodular
functions are _orthant submodular_ [25].

For consistency, we use the following notations as used by [21]. Namely, with
a slight abuse of notation, we associate each
$\boldsymbol{x}=(X_{1},\ldots,X_{k})\in(k+1)^{V}$ with
$\boldsymbol{x}\in\\{0,1,\ldots,k\\}^{V}$ where
$X_{i}=\\{e\in{}V\mid\boldsymbol{x}(e)=i\\}$ for $i\in[k]$. We define the
_support_ or _size_ of $\boldsymbol{x}\in(k+1)^{V}$ as
$supp(\boldsymbol{x})=\\{e\in{}V\mid\boldsymbol{x}(e)\neq{0}\\}$. Similarly,
we define $supp_{i}(\boldsymbol{x})=\\{e\in{}V\mid{}\boldsymbol{x}(e)=i\\}$.

In the following, we show that when the function $f$ is $\varepsilon$-ADR, the
function is also $\varepsilon$-AS. The proof is in Appendix A.

###### Theorem 3.1

If $F$ is $\varepsilon$-approximately diminishing returns, then $F$ is
$\varepsilon$-approximately $k$-submodular.

The converse is not true (as shown below). One could attempt to upper bound
$\Delta_{u,i}F(\boldsymbol{x})\leq(1+\varepsilon)f(X_{1},...,X_{i}\cup\\{u\\},...,X_{k})-(1-\varepsilon)f(\boldsymbol{x})=(1+\varepsilon)\Delta_{u,i}f(\boldsymbol{x})+2\varepsilon
f(\boldsymbol{x})$ using the definition of $\varepsilon$-AS for each term.
However, the resultant function does not appear to be $\varepsilon$-ADR.

###### Theorem 3.2

If $F$ is $\varepsilon$-approximately $k$-submodular, then $F$ is not
necessarily $\varepsilon$-approximately diminishing returns.

  * Proof.

To prove the statement, we construct a function $F$ that is $\varepsilon$-AS
but not $\varepsilon$-ADR for $k=1$. Let $V=\\{e_{1},e_{2}\\}$. By the
$\varepsilon$-AS definition, we have that
$(1-\varepsilon)f(\boldsymbol{x})\leq
F(\boldsymbol{x})\leq(1+\varepsilon)f(\boldsymbol{x})$ for any
$\boldsymbol{x}\in{(k+1)^{V}}$. We define $F$ partially as follows. Let
$F(\\{e_{1}\\})=(1+\varepsilon)f(\\{e_{1}\\})$ and
$F(\\{e_{1},e_{2}\\})=(1-\varepsilon)f(\\{e_{1},e_{2}\\})$. Consider the
marginal gain of adding $e_{2}$ to the set $\\{e_{1}\\}$. We have that
$\Delta_{e_{2}}F(\\{e_{1}\\})=(1-\varepsilon)f(\\{e_{1},e_{2}\\})-(1+\varepsilon)f(\\{e_{1}\\})<(1-\varepsilon)\left[f\left(\\{e_{1},e_{2}\\}\right)-f\left(\\{e_{1}\\}\right)\right]=(1-\varepsilon)\Delta_{e_{2}}f(\\{e_{1}\\})$,
where the first equality holds due to our construction, the inequality is due
to $\varepsilon>0$, and the last equality is from the lower bound of the
$\varepsilon$-ADR definition.

##  4 Approximately $k$-Submodular Function Maximization: $k=1$

When $k=1$, $k$-submodular functions coincide with the standard submodular
functions [19]. Thus, the total size and individual size constraints are the
same. We are interested in the maximization problem with a size constraint
with parameter $B$. For an $\varepsilon$-AS $F$, [14] proves the following
approximation ratio when applying the greedy algorithm [19], which iteratively
adds into $F$ an element that achieves the highest marginal gain.

######  Corollary 4.1 (Theorem 5 [14])

Suppose $F$ is $\varepsilon$-approximately submodular. The greedy algorithm
provides an approximation ratio of
$\frac{1}{1+\frac{4B\varepsilon}{(1-\varepsilon)^{2}}}\left(1-\left(\frac{1-\varepsilon}{1+\varepsilon}\right)^{2B}\left(1-\frac{1}{B}\right)^{B}\right)$
for the size constrained maximization problem.

When $F$ is $\varepsilon$-ADR, we obtain the following approximation ratio
using its connection to the notions of a-submodularity, weakly submodularity,
and submodularity ratio (see e.g., [12, 8, 6]).

###### Theorem 4.1

Suppose $F$ is $\varepsilon$-approximately diminishing returns. The greedy
algorithm provides an approximation ratio of $(1-e^{-a})$ for the size
constrained maximization problem where $a=(1-\varepsilon)/(1+\varepsilon)$.

  * Proof.

We note that if $F$ is $\varepsilon\text{-ADR}$, then $F$ is $a$-submodular
[12] via the fact that
$\varepsilon\text{-ADR}:(1-\varepsilon)\Delta_{u,i}f(\boldsymbol{x})\leq{}\Delta_{u,i}F(\boldsymbol{x})\leq{}(1+\varepsilon)\Delta_{u,i}f(\boldsymbol{x}),$
which implies
$\Delta_{u,i}F(\boldsymbol{y})(1-\varepsilon)/(1+\varepsilon)\leq(1-\varepsilon)\Delta_{u,i}f(\boldsymbol{y})\leq(1-\varepsilon)\Delta_{u,i}f(\boldsymbol{x})\leq\Delta_{u,i}F(\boldsymbol{x})$
for any $\boldsymbol{x}\leq\boldsymbol{y},u\not\in\bigcup_{l\in[k]}X_{l}$ and
$i\in[k]$ with $a=(1-\varepsilon)/(1+\varepsilon)$ (i.e., a function, say $g$,
is $a$-submodular if and only if $\Delta_{u,i}g(\boldsymbol{x})\geq
a\Delta_{u,i}g(\boldsymbol{y})$ for any $\boldsymbol{x}\leq\boldsymbol{y}$
[12]). As any $a$-submodular function is weakly submodular (Proposition 8
[12]), the greedy algorithm provides an approximation of $(1-e^{-a})$ [8, 6].

##  5 Approximately $k$-Submodular Function Maximization: $k>1$

In this section, we consider the problems of maximizing approximately
$k$-submodular functions under the $\varepsilon$-AS and $\varepsilon$-ADR
definitions subject to the total size,
$\max\limits_{\boldsymbol{x}:|supp(\boldsymbol{x})|\leq{B}}F(\boldsymbol{x})$,
or individual size constraints,
$\max\limits_{\boldsymbol{x}:|supp_{i}(\boldsymbol{x})|\leq{B_{i}},\forall{}i\in[k]}F(\boldsymbol{x})$,
for some function $F$ and $B,B_{1},...,B_{k}\in\mathbb{Z}^{+}$. We show that
the greedy algorithms [21] $k$-Greedy-TS (see Algorithm 1) and $k$-Greedy-IS
(see Algorithm 2) provide (asymptotically tight as $\varepsilon\to 0$ for TS)
approximation ratios to function $F$. Algorithm 1 and Algorithm 2 essentially
add a single element with the highest marginal gain to one of the $k$ subsets
at each iteration without violating the TS and IS constraints, respectively.
Algorithm 1 and Algorithm 2 requires evaluating the function $O(knB)$ and
$O(kn\sum_{i\in[k]}B_{i})$ times, respectively.

Input: a $\varepsilon$-approximately $k$-submodular function
$F:(k+1)^{V}\mapsto\mathbb{R}^{+}$ and $B\in\mathbb{Z}^{+}$.

Output: a vector $\boldsymbol{x}$ with $|supp(\boldsymbol{x})|=B$.

1

2$\boldsymbol{x}\leftarrow\boldsymbol{0}$;

3for  _$j=1$ to $B$_ do

4
$(e,i)\leftarrow{}\operatorname*{arg\,max}_{e\in{}V\setminus{supp(\boldsymbol{x})},i\in[k]}\Delta_{e,i}F(\boldsymbol{x})$;

5

6 $\boldsymbol{x}(e)\leftarrow{}i$;

7

8

Algorithm 1 $k$-Greedy-TS (Total Size)

Input: a $\varepsilon$-approximately $k$-submodular function
$F:(k+1)^{V}\mapsto\mathbb{R}^{+}$ and $B_{1},\cdots,B_{k}\in\mathbb{Z}^{+}$.

Output: a vector $\boldsymbol{x}$ with $|supp_{i}(\boldsymbol{x})|=B_{i}$
$\forall i\in[k]$.

1 $\boldsymbol{x}\leftarrow\boldsymbol{0}$; $I\leftarrow[k]$;

2

3while  _$I\neq\emptyset$_ do

4
$(e,i)\leftarrow{}\operatorname*{arg\,max}_{e\in{}V\setminus{}supp(\boldsymbol{x}),i\in
I}\Delta_{e,i}F(\boldsymbol{x})$;

5

6 $\boldsymbol{x}(e)\leftarrow{}i$;

7

8 if  _$|supp_{i}(\boldsymbol{x})=B_{i}|$_ then

9 $I\leftarrow{}I\setminus\\{i\\}$;

10

Algorithm 2 $k$-Greedy-IS (Individual Size)

The proof techniques in this section use similar ideas from [21]. However, the
proofs in [21] do not apply trivially and directly without our carefully
designed lemmas and appropriate derivations.

###  5.1 Maximizing $\varepsilon$-AS and $\varepsilon$-ADR Functions with the
TS Constraint

We consider the problem of maximizing $\varepsilon$-AS or $\varepsilon$-ADR
function $F$ subject to the total size constraint $B$ using Algorithm 1 on
function $F$. We use the following notations as in [21]. Let
$\boldsymbol{x}^{(j)}$ be the solution after the $j$-th iteration of Algorithm
1. For each $j$, we let $(e^{(j)},i^{(j)})\in{}V\times[k]$ be the selected
pair. Let
$\boldsymbol{o}\in\operatorname*{arg\,max}\limits_{\boldsymbol{x}:|supp(\boldsymbol{x})|\leq{B}}F(\boldsymbol{x})$
be an optimal solution.

Our goal is to compare the greedy solution $\boldsymbol{x}$ and an optimal
solution $\boldsymbol{o}$. To begin, we define
$\boldsymbol{o}^{(0)}=\boldsymbol{o},\boldsymbol{o}^{(\frac{1}{2})},\boldsymbol{o}^{(1)},\cdots,\boldsymbol{o}^{(B)}$
iteratively. Let
$S^{(j)}=supp(\boldsymbol{o}^{(j-1)})\setminus{}supp(\boldsymbol{x}^{(j-1)})$
with $\boldsymbol{x}^{(0)}=\boldsymbol{0}$. We set $o^{(j)}$ to be an
arbitrary element in $S^{(j)}$ if $e^{(j)}\notin{}S^{(j)}$, and set
$o^{(j)}=e^{(j)}$ otherwise. We construct $\boldsymbol{o}^{(j-\frac{1}{2})}$
from $\boldsymbol{o}^{(j-1)}$ by assigning $0$ to the $o^{(j)}$-th element.
Next, we define $\boldsymbol{o}^{(j)}$ from $\boldsymbol{o}^{(j-\frac{1}{2})}$
by assigning $i^{(j)}$ to the $e^{(j)}$-th element. As such, we have
$|supp(\boldsymbol{o}^{(j)})|=B$ for all $j\in[B]$ and
$\boldsymbol{o}^{(B)}=\boldsymbol{x}^{(B)}=\boldsymbol{x}$. Finally, we note
that $\boldsymbol{x}^{(j-1)}\preceq\boldsymbol{o}^{(j-\frac{1}{2})}$ for every
$j\in[B]$.

####  5.1.1 $\varepsilon$-AS Functions with the TS Constraint

###### Theorem 5.1

Suppose $F$ is $\varepsilon$-approximately $k$-submodular. The $k$-Greedy-TS
algorithm provides an approximation ratio of
$\frac{(1-\varepsilon)^{2}}{2(1-\varepsilon+\varepsilon{}B)(1+\varepsilon)}$
for the total size constrained maximization problem.

To prove the above theorem, we first need to prove the following key lemma
(see Appendix B).

###### Lemma 5.1

For any $j\in[B]$,
$\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})\geq{}f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})$.

  * Proof.

[Proof of Theorem 5.1] We have

$\displaystyle
f(\boldsymbol{o})-f(\boldsymbol{x})=\sum_{j\in[B]}\left(f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})\right)$
$\displaystyle\leq\sum_{j\in[B]}\left(\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})\right)$
$\displaystyle=\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x})+\sum_{j=1}^{B-1}\left(\frac{2\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})\right)$
$\displaystyle\leq\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x})+\sum_{j=1}^{B-1}\left(\frac{2\varepsilon}{1-\varepsilon}f(\boldsymbol{x})\right)=\frac{1-\varepsilon+2\varepsilon{}B}{1-\varepsilon}f(\boldsymbol{x}),$

where the first inequality is by Lemma 5.1. Thus,
$f(\boldsymbol{x})\geq\frac{1-\varepsilon}{2-2\varepsilon+2\varepsilon{}B}f(\boldsymbol{o})$.
We have
$F(\boldsymbol{x})\geq\frac{(1-\varepsilon)^{2}}{2(1-\varepsilon+\varepsilon{}B)(1+\varepsilon)}F(\boldsymbol{o})$
after applying the $\varepsilon$-AS definition.

####  5.1.2 $\varepsilon$-ADR Functions with the TS Constraint

###### Lemma 5.2

For any $j\in[B]$, it holds that
$\frac{1}{1-\varepsilon}\left[F(\boldsymbol{x}^{(j)})-F(\boldsymbol{x}^{(j-1)})\right]\geq{}\frac{1}{1+\varepsilon}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})\right]$.

  * Proof.

See Appendix B.

###### Theorem 5.2

Suppose $F$ is $\varepsilon$-approximately diminishing returns. The
$k$-Greedy-TS algorithm provides an approximation ratio of
$\frac{1-\varepsilon}{2}$ for the total size constrained maximization problem.

  * Proof.

We have

$\displaystyle F(\boldsymbol{o})-F(\boldsymbol{x})$
$\displaystyle=\sum_{j\in[B]}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{j})\right]$
$\displaystyle\leq{}\frac{1+\varepsilon}{1-\varepsilon}\sum_{j\in[B]}\left[F(\boldsymbol{x}^{(j)})-F(\boldsymbol{x}^{j-1})\right]\leq\frac{1+\varepsilon}{1-\varepsilon}F(\boldsymbol{x}),$

where the first inequality is due to Lemma 5.2. Thus, we have
$F(\boldsymbol{x})\geq{}\frac{1-\varepsilon}{2}F(\boldsymbol{o})$.

###  5.2 Maximizing $\varepsilon$-AS and $\varepsilon$-ADR Functions with the
IS Constraints

We consider the problem of maximizing an $\varepsilon$-AS or $\varepsilon$-ADR
function $F$ subject to the individual size constraints $B_{1},...,B_{k}$
using Algorithm 2 on the function $F$. In the individual size constraints
maximization problem, we are given $B_{1},...,B_{k}$ restricting the maximum
number of elements one can select for each subset. We define
$B=\sum_{j\in[k]}B_{j}$. We simply state our main results here (see Appendix
B.1 for key lemmas and proofs).

###### Theorem 5.3

Suppose $F$ is $\varepsilon$-approximately $k$-submodular. The $k$-Greedy-IS
algorithm provides an approximation ratio of
$\frac{(1-\varepsilon)^{2}}{(3-3\varepsilon+2\varepsilon{}B)(1+\varepsilon)}$
for the individual size constrained maximization problem.

###### Theorem 5.4

Suppose $F$ is $\varepsilon$-approximately diminishing returns. The
$k$-Greedy-IS algorithm provides an approximation ratio of
$\frac{1-\varepsilon}{3+\varepsilon}$ for the individual size constrained
maximization problem.

##  6 Improved Greedy Approximation Ratios When $f$ is Known

In this section, we consider the case where $f$ is a known monotone function
that can be constructed directly. We investigate the question of whether we
can use such information to obtain alternative, possibly better, approximation
ratios for maximizing an $\varepsilon$-AS or $\varepsilon$-ADR function $F$
subject to the total size or individual size constraints. We answer the
question affirmatively via the following result (see Appendix C for details).

###### Theorem 6.1

Let $f$ be a $k$-submodular function and $F$ be an $\varepsilon$-approximately
$k$-submodular function that is bounded by $f$. If there is an algorithm that
provides an approximation ratio of $\alpha$ for maximizing $f$ subject to
constraint $\mathbb{X}$, then the same solution yields an approximation ratio
of $\frac{1-\varepsilon}{1+\varepsilon}\alpha$ for maximizing $F$ subject to
constraint $\mathbb{X}$.

This theorem implies the following: (1) By applying the greedy algorithm [19]
on a submodular function $f$ subject to a size constraint, we obtain a
solution providing an approximation ratio of
$\frac{1-\varepsilon}{1+\varepsilon}(1-\frac{1}{e})$ to the size constrained
maximization problem of an approximately submodular function $F$. (2) By
applying $k$-Greedy-TS on a $k$-submodular function $f$ subject to a total
size constraint, we obtain a solution providing an approximation ratio of
$\frac{1-\varepsilon}{2(1+\varepsilon)}$ to the total size constrained
maximization problem of an $\epsilon$-AS function $F$. (3) By applying
$k$-Greedy-IS on a $k$-submodular function $f$ subject to individual size
constraints, we obtain a solution providing an approximation ratio of
$\frac{1-\varepsilon}{3(1+\varepsilon)}$ to the individual size constrained
maximization problem of an $\epsilon$-AS function $F$. For $F$ that is
$\varepsilon$-ADR, since it is also $\varepsilon$-AS $F$, these three results
apply immediately.

##  7 Experiments

We evaluate the real-world performance of the algorithms for maximizing $F$
directly, or indirectly through the use of a bounding $k$-submodular function
$f$, by applying them to a variant of the $k$-sensor placement problem with IS
constraints and a variant of the $k$-topic influence maximization problem with
the TS constraint. In both problems, we used $\varepsilon$-AS $k$-submodular
functions. Appendix D contains additional experiments with $\varepsilon$-AS
and with $\varepsilon$-ADR $k$-submodular functions, whose results are similar
to those reported here.

###  7.1 Experimental Setup

In our experiments, we consider an $\varepsilon$-AS function $F$ and generate
the value of $F$ according to the bounding $k$-submodular function $f$, which
is given explicitly in our application domains. In particular, for each
$\boldsymbol{x}\in(k+1)^{V}$, the value of $F$ of $\boldsymbol{x}$ should be
generated such that $(1-\varepsilon)f(\boldsymbol{x})\leq
F(\boldsymbol{x})\leq(1+\varepsilon)f(\boldsymbol{x})$. When $f$ is known, we
can compute the value of $f$ for a given $\boldsymbol{x}$ directly and then
generate the value of $F$ according to some predefined generation methods. To
highlight the performance or solution quality of $F$ and $f$ under the greedy
algorithms, we considered the following three types of generation methods. The
functions $F$ and $f$ will be defined later for the appropriate domains.

Adversarial Generation (AG). To stress-test the greedy algorithms applied to
$f$, we identify the worst-case values of $F$ where, when applying these
algorithms, $f$’s solution obtains a better approximation ratio than the
solution generated when applying the greedy algorithms to $F$. We first run a
greedy algorithm on $f$ and obtain its solution $\boldsymbol{x_{f}}$. We let
$F(\boldsymbol{x_{f}})=(1+\varepsilon)f(\boldsymbol{x_{f}})$ which yields
higher weight to $f$’s solution. For the remaining $\boldsymbol{x}$, we let
$F(\boldsymbol{x})=\xi(\boldsymbol{x})\cdot f(\boldsymbol{x})$ where
$\xi(\boldsymbol{x})$ is selected uniformly at random in $[1-\varepsilon,1]$.

Max and Mean Generation (MaxG and MeanG). Our goal is to consider a more
structured error/noise generation setting where each (selected) element
contributes some uncertainty to the value of $F$. In MaxG,
$F(\boldsymbol{x})=\xi(\boldsymbol{x})\cdot f(\boldsymbol{x})$, where
$\xi(\boldsymbol{x})=\max_{x\in{supp(\boldsymbol{x})}}\xi(x)$ and
$\xi(x)\in[1-\varepsilon,1]$. Thus, we weigh $f$ with the maximum value of
noise over the elements of ${\boldsymbol{x}}$. In MeanG,
$\xi({\boldsymbol{x}})=\frac{\sum_{x\in
supp(\boldsymbol{x})}\xi(x)}{|supp(\boldsymbol{x})|}$ and
$\xi(x)\in[1-\varepsilon,1]$. Thus, we weigh $f$ with the expected value of
noise over ${\boldsymbol{x}}$.

Clearly, $F$ is $\varepsilon$-AS. It is also non $k$-submodular for all
generation methods (see Appendix D.1).

We implemented $k$-Greedy-TS, $k$-Greedy-IS, as well as baselines (details
below) in C++ and executed them on an Intel Cascade Lake @ 2.6GhZ with 48GB
RAM. These algorithms employed the lazy evaluation technique [18] (i.e., we
maintain an upper bound on the gain of inserting each element in each
dimension w.r.t. $F$ or $f$, to efficiently select the element in each
iteration). We report results of the quality of these algorithms with respect
to function $F$ (specifically, the mean and standard deviation of results for
$10$ different runs of value generations; each with a different seed). We do
not report runtime because the choice of function $F$ or $f$ did not
substantially affect the runtime of the algorithms (for efficiency results of
the algorithms see [21]). Our source code and the datasets that we used are
available at: https://github.com/55199789/approx_kSubmodular.git.

###  7.2 Sensor Placement with Approximately $k$-Submodular Functions and the
IS Constraints

The objective is to install a sufficiently large number of sensors of $k$
types into locations, so that each sensor is installed in a single location
and all installed sensors together collect measurements of low uncertainty. We
first define the entropy of a vector ${\boldsymbol{x}}$ of sensors, following
[21]. Let $\Omega=\\{X^{u}_{i}\\}_{i\in[k],u\in V}$ be the set of random
variables for each sensor type $i\in[k]$ and each location $u\in V$. Each
$X^{u}_{i}$ is the random variable representing the measurement collected from
a sensor of type $i$ that is installed at location $u$. Thus,
$X_{i}=\\{X^{u}_{i}\\}\subseteq\Omega$ is the set representing the
measurements for all locations at which a sensor of type $i\in[k]$ is
installed. The entropy of a vector
${\boldsymbol{x}}=(X_{1},\ldots,X_{k})\in(k+1)^{V}$ is given by the monotone
$k$-submodular function
$H({\boldsymbol{x}})=H(\cup_{i\in[k]}X_{i})=-\sum_{\mathbf{s}\in\text{dom}~{}\cup_{i\in[k]}X_{i}}Pr[\mathbf{s}]\cdot\log
Pr[\mathbf{s}]$, where $\text{dom}~{}\cup_{i\in[k]}X_{i}$ is the domain of
$\cup_{i\in[k]}X_{i}$ [21].

The work of [21] considered the problem of maximizing $H({\boldsymbol{x}})$
subject to individual size constraints for ${\boldsymbol{x}}$, using
$H({\boldsymbol{x}})$ to capture the uncertainty of measurements. Sensor
measurements often have random noise due to hardware issues, environmental
effects, and imprecision in measurement [10], and weighted entropy functions
are used to capture such errors [2]. As such, we consider a noisy variant of
the problem of [21], where the uncertainty of measurements is captured by a
weighted function $\tilde{H}({\boldsymbol{x}})=\xi(\boldsymbol{x})\cdot
H({\boldsymbol{x}})$ and $\xi()$ is generated by our AG, MaxG, or MeanG
generation method.

(a)

(b)

(c)

(d)

Figure 1: $\tilde{H}$ in AG setting vs: (a) number of dimensions $k$, (b)
individual size threshold $b$, (c,d) $\varepsilon$.

(a)

(b)

(c)

(d)

Figure 2: $\tilde{H}$ in MeanG setting vs: (a) number of dimensions $k$, (b)
individual size threshold $b$, (c,d) $\varepsilon$.

(a)

(b)

(c)

(d)

Figure 3: $\tilde{H}$ in MaxG setting vs: (a) number of dimensions $k$, (b)
individual size threshold $b$, (c,d) $\varepsilon$.

Algorithms. We first apply $k$-Greedy-IS using $H$ as $f$ and then using
$\tilde{H}$ as $F$, and we compare their solutions in terms of $\tilde{H}$. We
refer to these algorithms as $Gr$-$H$ and $Gr$-$\tilde{H}$ respectively. Since
no algorithms can address our problem, we compare against a baseline, Random
(referred to as $R$), which outputs as a solution a vector ${\boldsymbol{x}}$
with $B_{i}$ randomly selected elements in each dimension. Random was also
used in [21]. In our experiments, each $B_{i}$ has the same value $b$. We
configured the algorithms with $k\in\\{1,2,3\\}$,
$\varepsilon\in\\{0,0.1,\ldots,1\\}$, and $B_{i}\in\\{1,3,\ldots,15\\}$.
Unless otherwise stated, $k=1$, $\varepsilon=0.3$, and $b=9$. Other parameter
settings showed similar behaviors.

Dataset. We used the Intel Lab dataset which is available at
http://db.csail.mit.edu/labdata/labdata.html and is preprocessed as in [21].
The dataset is a log of approximately 2.3 million values that are collected
from 54 sensors installed in 54 locations in the Intel Berkeley research lab.
There are three types of sensors. Sensors of type 1, 2, and 3 collect
temperature, humidity, and light values, respectively. $F$ or $f$ take as
argument a vector: (1) $\boldsymbol{x}=(X_{1})$ of sensors of type 1, when
$k=1$; (2) $\boldsymbol{x}=(X_{1},X_{2})$ of sensors of type 1 and of type 2,
when $k=2$, or (3) $\boldsymbol{x}=(X_{1},X_{2},X_{3})$ of sensors of type 1
and of type 2 and of type 3, when $k=3$.

(a)

(b)

(c)

Figure 4: $\tilde{I}$ for varying $k$ in: (a) AG, (b) MeanG, and (c) MaxG
setting.

Results. Fig. 1 shows that, in the AG setting, $Gr$-$H$ substantially
outperformed $Gr$-$\tilde{H}$ across all $k$, $b$, and $\varepsilon$ values.
This can be explained by the fact that, in the AG setting, $Gr$-$H$ is favored
by the construction of $F$, because $F$ is based on its solution
$\boldsymbol{x_{f}}$. Both $Gr$-$H$ and $Gr$-$\tilde{H}$ outperformed $R$ (the
latter by a smaller margin due to the adversarial noise construction). This
happened even when $\varepsilon=1$, the case in which they do not offer
approximation guarantees. The performance of $Gr$-$\tilde{H}$ suffers as
$\varepsilon$ goes to 1, due to the uniform range $[1-\varepsilon,1]$ used to
generate $F$’s values.

Figs. 2 and 3 show that, in the MaxG and MeanG settings, $Gr$-$\tilde{H}$
outperformed $Gr$-$H$ in almost all tested cases on average, and especially
for larger $b$ and $\varepsilon$. This is because the noise is more structured
and suggests that $Gr$-$\tilde{H}$ may be a practical algorithm (e.g., in
applications where the maximum or expected noise of sensors is taken as an
aggregate of the noise of sensors). We also observe that $Gr$-$\tilde{H}$ has
a larger performance gain and less variability (low standard deviation bars)
over $Gr$-$H$ under MeanG than under MaxG.

###  7.3 Influence Maximization with Approximately $k$-Submodular Functions
and the TS Constraint

The objective is to select a sufficiently large number of users in a social
network who would influence the largest expected number of users in the social
network through word-of-mouth effects. The selected users are called _seeds_.
To measure influence, we adapt the $k$-IC influence diffusion model proposed
in [21]. In the $k$-IC model, $k$ different topics spread through a social
network independently. At $t=0$, there is a vector
$\boldsymbol{x}=(X_{1},\ldots,X_{k})$ of seeds who are influenced. Each $u$ in
$X_{i}$, $i\in[k]$, is influenced about topic $i$ and has a single chance to
influence its out-neighbor $v$, if $v$ is not already influenced. The node $v$
is influenced at $t=1$ by $u$ on topic $i$ with probability $p_{u,v}^{i}$.
Also, $v$ is influenced by any of its in-neighbors (other seeds) at time $t=1$
on topic $i$. When $v$ becomes influenced, it stays influenced and has a
single chance to influence each of its out-neighbors that is not already
influenced. The process proceeds until no new nodes are influenced. The
expected number of influenced users (_spread_) is
$I(\boldsymbol{x})=\mathrm{E}[|\cup_{i\in[k]}A_{i}(X_{i})|]$, where
$A_{i}(X_{i})$ is a random variable representing the set of users influenced
about topic $i$ through $X_{i}$.

Our adapted $k$-IC model differs from the $k$-IC model in that we measure
spread by $\tilde{I}(\boldsymbol{x})=\xi(\boldsymbol{x})\cdot
I({\boldsymbol{x}})$, instead of $I(\boldsymbol{x})$, where $\xi()$ is the
noise function in the AG, MaxG, or MeanG setting. The noise models empirical
evidence that the spread may be non-submodular and difficult to quantify
accurately. This happens because users find information diffused by many in-
neighbors as already known and less interesting, in which case the noise
depends on the data [11]. Furthermore, it happens because the combined
influence of subsets of influenced in-neighbors of a node also affects the
influence probability of the node and hence the spread, in which case the
noise depends on the subset of influenced in-neighbor of a user [26].
$\tilde{I}({\boldsymbol{x}})$ is an $\varepsilon$-AS function, since
$(1-\varepsilon)\cdot
I({\boldsymbol{x}})\leq\tilde{I}({\boldsymbol{x}})\leq(1+\varepsilon)\cdot
I({\boldsymbol{x}})$ and $I(\boldsymbol{x})$ is monotone $k$-submodular [21].

Algorithms. We first apply $k$-Greedy-TS using $I$ as $f$ and then using
$\tilde{I}$ as $F$, and we compare their solutions in terms of $\tilde{I}$. We
refer to them as $Gr$-$I$ and $Gr$-$\tilde{I}$. We also evaluate $Gr$-$I$ and
$Gr$-$\tilde{I}$ against two baselines, also used in [21]: (1) Random (R),
which outputs a random vector ${\boldsymbol{x}}$ of size $B$, and (2) Degree
(D), which sorts all nodes in decreasing order based on their out-degree and
then assigns each of them to a random topic (dimension). We simulated the
influence process based on Monte Carlo simulation as in [21]. We configured
the algorithms with $k\in\\{2,4,\ldots,10\\}$,
$\varepsilon\in\\{0,0.1,\ldots,1\\}$, and $B\in\\{5,10,\ldots,100\\}$. By
default, $k=8$, $\varepsilon=0.3$, and $B=75$.

Dataset. We used the Digg social news dataset that is available at
http://www.isi.edu/~lerman/downloads/digg2009.html, following the setup of
[21]. The dataset consists of a graph and a log of user votes for stories.
Each node represents a user and each edge $(u,v)$ represents that user $u$ can
watch the activity of node $v$. The edge probabilities $p_{u,v}^{i}$ for each
edge $(u,v)$ and topic $i$ were obtained from [21].

Results. The results in Fig. 4 are similar to those of Section 7.2. That is,
in the AG setting $Gr$-$I$ outperformed $Gr$-$\tilde{I}$ (see Fig. 4(a)). This
is because $F$ is based on the solution of $Gr$-$I$ and thus this algorithm is
favored over $Gr$-$\tilde{I}$. On the other hand, in the MaxG and MeanG
setting $Gr$-$\tilde{I}$ outperformed $Gr$-$I$ in all tested cases (see Figs.
4(b) and 4(c)). This is because the noise is more structured and suggests that
$Gr$-$\tilde{I}$ may be a practical algorithm, when the noise is structured
and not adversarially chosen. In all tested cases, as expected, both $Gr$-$I$
and $Gr$-$\tilde{I}$ outperformed $R$ and $D$. We observed similar trends,
when we varied the parameters $B$ and $\varepsilon$ (see Appendix D.2).

##  8 Conclusion and Discussion

In this paper, we show that simple greedy algorithms can obtain reasonable
approximation ratios for an $\varepsilon$-AS or $\varepsilon$-ADR function $F$
subject to total size and individual size constraints. The analysis (i.e.,
proofs of Theorem 5.3 and Theorem 5.4) for the individual size constraint can
be extended to capture a _group_ size constraint. Let $G_{1},...,G_{m}$ be a
partition of $\\{1,...,k\\}$ and $B_{1},...,B_{m}$ be some positive integer
numbers. The maximization problem of an $\varepsilon$-AS or $\varepsilon$-ADR
function $F$ subject to the group size constraint is defined to be
$\max_{\boldsymbol{x}\in(k+1)^{V}:\sum_{j\in
G_{i}}|supp_{j}(\boldsymbol{x})|\leq B_{i}\;\forall
i\in[m]}F(\boldsymbol{x})$, where the total size of all of subsets within a
group $G_{i}$ is at most $B_{i}$. The same approximation ratios from Theorem
5.3 and Theorem 5.4 can be obtained for $\varepsilon$-AS and $\varepsilon$-ADR
function $F$, respectively, using a modified greedy algorithm (similar to
Algorithm 2) where the condition in line 5 can be changed to account for the
group constraint.

Our definitions for $\varepsilon$-AS and $\varepsilon$-ADR depend on the lower
bound constant, $(1-\varepsilon)$ and upper bound constant, $(1+\varepsilon)$.
Similar approximation ratio results can be derived when replacing
$(1-\varepsilon)$ with some lower bound constant $a$ and upper bound constant
$b$ where $0<a\leq b$. The approximation ratios will depend on $a$ and $b$ and
can be obtained following the same proof ideas.

Finally, it would be interesting to evaluate our algorithms using datasets
that are inherently noisy.

## References

  * [1] Representation, approximation and learning of submodular functions using low-rank decision trees.  In COLT, volume 30, pages 711–740, 2013.
  * [2] Darryl K. Ahner.  A normalized weighted entropy measure for sensor allocation within simulations.  In WSC, pages 1753–1763, 2009.
  * [3] Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden.  Sketching valuation functions.  In SODA, pages 1025–1035, 2012.
  * [4] Maria Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang.  Learning valuation functions.  In COLT, volume 23, pages 4.1–4.24, 2012.
  * [5] Maria-Florina Balcan and Nicholas J.A. Harvey.  Learning submodular functions.  In STOC, pages 793–802, 2011.
  * [6] Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek.  Guarantees for greedy maximization of non-submodular functions with applications.  In ICML, volume 70, pages 498–507, 2017.
  * [7] Gerard Cornuejols, Marshall L. Fisher, and George L. Nemhauser.  Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms.  Management Science, 23(8):789–810, 1977.
  * [8] Abhimanyu Das and David Kempe.  Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection.  In ICML, pages 1057–1064, 2011.
  * [9] Ehsan Elhamifar.  Sequential facility location: Approximate submodularity and greedy algorithm.  In ICML, pages 1784–1793, 2019.
  * [10] Eiman Elnahrawy and Badri Nath.  Cleaning and querying noisy sensors.  In WSNA, pages 78–87, 2003.
  * [11] Shanshan Feng, Xuefeng Chen, Gao Cong, Yifeng Zeng, Yeow Meng Chee, and Yanping Xiang.  Influence maximization with novelty decay in social networks.  In AAAI, pages 37–43, 2014.
  * [12] Marwa El Halabi, Francis Bach, and Volkan Cevher.  Combinatorial penalties: Which structures are preserved by convex relaxations?  In AISTATS, volume 84, pages 1551–1560, 2018.
  * [13] Avinatan Hassidim and Yaron Singer.  Submodular optimization under noise.  In COLT, volume 65, pages 1069–1122, 2017.
  * [14] Thibaut Horel and Yaron Singer.  Maximization of approximately submodular functions.  In NIPS, pages 3045–3053. Curran Associates, Inc., 2016.
  * [15] Anna Huber and Vladimir Kolmogorov.  Towards minimizing k-submodular functions.  In COCOA, pages 451–462, 2012.
  * [16] Satoru Iwata, Shin-ichi Tanigawa, and Yuichi Yoshida.  Improved approximation algorithms for k-submodular function maximization.  In SODA, pages 404–413, 2016.
  * [17] Qiang Li, Wei Chen, Xiaoming Sun, and Jialin Zhang.  Influence maximization with $\varepsilon$-almost submodular threshold functions.  In NIPS, pages 3801–3811. 2017.
  * [18] Michel Minoux.  Accelerated greedy algorithms for maximizing submodular set functions.  In Optimization Techniques, pages 234–243, Berlin, Heidelberg, 1978\.
  * [19] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher.  An analysis of approximations for maximizing submodular set functions—I.  Mathematical Programming, 14(1):265–294, 1978.
  * [20] Lan Nguyen and My T. Thai.  Streaming k-submodular maximization under noise subject to size constraint.  In ICML, volume 119 of PMLR, pages 7338–7347. PMLR, 2020\.
  * [21] Naoto Ohsaka and Yuichi Yoshida.  Monotone k-submodular function maximization with size constraints.  In NIPS, pages 694–702, 2015.
  * [22] Chao Qian, Jing-Cheng Shi, Yang Yu, Ke Tang, and Zhi-Hua Zhou.  Subset selection under noise.  In NIPS, pages 3560–3570. 2017.
  * [23] Yaron Singer and Avinatan Hassidim.  Optimization for approximate submodularity.  In NeurIPS, pages 396–407. 2018.
  * [24] Ajit Singh, Andrew Guillory, and Jeff Bilmes.  On bisubmodular maximization.  volume 22 of PMLR, pages 1055–1063, 2012.
  * [25] Justin Ward and Stanislav Živný.  Maximizing k-submodular functions and beyond.  ACM Trans. Algorithms, 12(4):47:1–47:26, 2016.
  * [26] Jianming Zhu, Junlei Zhu, Smita Ghosh, Weili Wu, and Jing Yuan.  Social influence maximization in hypergraph in social networks.  IEEE TNSE, 6(4):801–811, 2019.

##  A Proofs in Section 3

  * Proof.

[Proof of Theorem 3.1] To prove the theorem, it is sufficient to show that the
claim holds for any $\boldsymbol{x}\in(k+1)^{V}$. For any
$\boldsymbol{x}=(X_{1},...,X_{k})\in(k+1)^{V}$, for each $i\in[k]$, we order
the elements of $X_{i}$ such that
$X_{i}=\\{e_{i1},e_{i2},...,e_{i|X_{i}|}\\}$. It follows that

$\displaystyle F(\boldsymbol{x})$ $\displaystyle=F(X_{1},\ldots,X_{k})$
$\displaystyle=\sum_{i\in[k]}\sum_{j=1}^{|X_{i}|}\Delta_{e_{j},i}F(X_{1},...,X_{i}\setminus\\{e_{i1},...,e_{ij}\\},...,X_{k}),$

where the equality is from adding/subtracting common terms. Since $F$ is
$\varepsilon$-ADR, we have

$\displaystyle(1-\varepsilon)f(\boldsymbol{x})$
$\displaystyle=(1-\varepsilon)\cdot\sum_{i\in[k]}\sum_{j=1}^{|X_{i}|}\Delta_{e_{j},i}f(X_{1},...,X_{i}\setminus\\{e_{i1},...,e_{ij}\\},...,X_{k})$
$\displaystyle\leq F(\boldsymbol{x})$
$\displaystyle\leq(1+\varepsilon)\cdot\sum_{i\in[k]}\sum_{j=1}^{|X_{i}|}\Delta_{e_{j},i}f(X_{1},...,X_{i}\setminus\\{e_{i1},...,e_{ij}\\},...,X_{k})$
$\displaystyle\leq(1+\varepsilon)f(\boldsymbol{x}),$

where the inequality is due to the application of $\varepsilon$-ADR definition
to each summation term. Thus, we have shown that $F$ is $\varepsilon$-AS under
the same $k$-submodular function $f$.

##  B Proofs in Section 5

  * Proof.

[Proof of Lemma 5.1] First note that
$\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}F(\boldsymbol{x}^{(j-1)})$
as $(e^{(j)},i^{(j)})$ is selected by the greedy algorithm, which must provide
as much marginal gain as $(o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)}))$. By using
the definition of $\varepsilon$-AS on the above inequality, we have that
$(1+\varepsilon)f(\boldsymbol{x}^{(j)})\geq(1-\varepsilon)f\left(\left(X^{(j-1)}_{1},\cdots,X^{(j-1)}_{\boldsymbol{o}^{(j-1)}(o^{(j)})}\cup\\{o^{(j)}\\},\cdots,X^{(j-1)}_{k}\right)\right)$.
By submodularity and $\boldsymbol{x}^{(j-1)}\preceq\boldsymbol{o}^{(j-1)}$, we
have that
$\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}f(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}f(\boldsymbol{o}^{(j-\frac{1}{2})})=f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j-\frac{1}{2})})\geq
f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})$. Our result follows
immediately after combining the above inequalities.

  * Proof.

[Proof of Lemma 5.2] First note that
$\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}F(\boldsymbol{x}^{(j-1)})$
as $(e^{(j)},i^{(j)})$ is selected by the greedy algorithm, which must provide
as much marginal gain as $(o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)}))$. By
submodularity and $\boldsymbol{x}^{(j-1)}\preceq\boldsymbol{o}^{(j-1)}$, we
have
$\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}f(\boldsymbol{o}^{(j-\frac{1}{2})})\geq\frac{1}{1+\varepsilon}\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}F(\boldsymbol{o}^{(j-\frac{1}{2})})$
(the last inequality is by the $\varepsilon$-ADR definition) and
$\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}F(\boldsymbol{o}^{(j-\frac{1}{2})})-\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})=F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})$.
It follows that
$\frac{1}{1-\varepsilon}\Delta_{o^{(j)},\boldsymbol{o}^{(j-1)}(o^{(j)})}F(\boldsymbol{x}^{(j-1)})\geq{}\frac{1}{1+\varepsilon}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})\right]$
by the definition of $\varepsilon$-ADR. Our claim follows immediately from the
last inequalities.

###  B.1 Maximizing $\varepsilon$-AS and $\varepsilon$-ADR Functions with the
Individual Size Constraints

In this subsection, we consider the problem of maximizing $\varepsilon$-AS or
$\varepsilon$-ADR function $F$ subject to the individual size constraint
$B_{1},...,B_{k}$ using Algorithm 2 on the function $F$. Recall that in the
individual size constraint maximization problem, we are given
$B_{1},...,B_{k}$ restricting the maximum number of elements one can select
for each subset. We define $B=\sum_{j\in[k]}B_{j}$. We use the following
notations as in [21] and the same notations $e^{(j)}$, $i^{(j)}$, and
$\boldsymbol{x}^{(j)}$ from Section 5.1.

As before, we iteratively define
$\boldsymbol{o}^{(0)}=\boldsymbol{o},\boldsymbol{o}^{(1)},\cdots,\boldsymbol{o}^{(B)}$
as follows. For each $j\in[B]$, we let
$S^{(j)}_{i}=supp_{i}(\boldsymbol{o}^{(j-1)})\setminus{}supp_{i}(\boldsymbol{x}^{(j-1)})$.
We consider the following two cases.

  * C1:

Suppose there exists $i^{\prime}\neq i^{(j)}$ such that
$e^{(j)}\in{}S_{i^{\prime}}^{(j)}$. In this case, we set $o^{(j)}$ to be an
arbitrary element in $S_{i^{(j)}}^{(j)}$. We construct
$\boldsymbol{o}^{(j-\frac{1}{2})}$ from $\boldsymbol{o}^{(j-1)}$ by assigning
$0$ to the $e^{(j)}$-th element and the $o^{(j)}$-th element. Then we
construct $\boldsymbol{o}^{(j)}$ from $\boldsymbol{o}^{(j-\frac{1}{2})}$ by
assigning $i^{(j)}$ to the $e^{(j)}$-th element and $i^{\prime}$ to the
$o^{(j)}$-th element. We may use $\boldsymbol{o}^{(j-\frac{1}{2})}_{(e,i)}$ to
denote $\boldsymbol{o}^{(j-\frac{1}{2})}$ with $i$ assigned to the $e$-th
element.

  * C2:

Suppose, for any $i^{\prime}\neq i^{(j)}$, we have
$e^{(j)}\notin{}S_{i^{\prime}}^{(j)}$. In this case, we let $o^{(j)}=e^{(j)}$
if $e^{(j)}\in S_{i^{(j)}}^{(j)}$, and let $o^{(j)}$ be an arbitrary element
in $S_{i^{(j)}}^{(j)}$ otherwise. We construct
$\boldsymbol{o}^{(j-\frac{1}{2})}$ from $\boldsymbol{o}^{(j-1)}$ by assigning
$0$ to the $o^{(j)}$-th element. We then construct $\boldsymbol{o}^{(j)}$ from
$\boldsymbol{o}^{(j-\frac{1}{2})}$ by assigning $i^{(j)}$ to the $e^{(j)}$-th
element.

By construction, we have $|supp_{i}(\boldsymbol{o}^{(j)}|=B_{i}$ for each
$i\in[k]$ and $j\in\\{0,1,\cdots,B\\}$. Moreover,
$\boldsymbol{x}^{(j-1)}\preceq\boldsymbol{o}^{(j-\frac{1}{2})}$ for each
$j\in[B]$.

We first consider $\varepsilon$-AS Functions with the Individual Size
Constraints in Section B.1.1. Then, we consider $\varepsilon$-ADR functions
with the Individual Size constraints in Section B.1.2.

####  B.1.1 $\varepsilon$-AS Functions with the Individual Size Constraints

###### Lemma B.1

For any $j\in[B]$,
$2\left[\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})\right]\geq{}f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})$.

  * Proof.

[Proof of Lemma B.1] The arguments for Case 1 and Case 2 are similar. We begin
with Case 1.

Case 1. First note that
$\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})$
and
$\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{e^{(j)},i^{\prime}}F(\boldsymbol{x}^{(j-1)})$
because $(e^{(j)},i^{(j)})$ is selected by the greedy algorithm.

It follows that $(1+\varepsilon)f(\boldsymbol{x}^{(j)})\geq\\\
(1-\varepsilon)f\left(\left(X^{(j-1)}_{1},\cdots,X^{(j-1)}_{i^{(j)}}\cup\\{o^{(j)}\\},\cdots,X^{(j-1)}_{k}\right)\right)$
and $(1+\varepsilon)f(\boldsymbol{x}^{(j)})\geq\\\
(1-\varepsilon)f\left(\left(X^{(j-1)}_{1},\cdots,X^{(j-1)}_{i^{\prime}}\cup\\{e^{(j)}\\},\cdots,X^{(j-1)}_{k}\right)\right)$
by using the definition of approximate submodularity. Since
$\boldsymbol{x}^{(j-1)}\preceq\boldsymbol{o}^{(j-\frac{1}{2})}\preceq\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})}$,
we have that
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$,
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})})$,
and
$\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$
from orthant submodularity. From the above inequalities, we have that
$\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})$
is greater than or equal to
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$,
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})})$,
and $\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$. As a
result, we have

$\displaystyle f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})$
$\displaystyle=\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{o}^{(j-\frac{1}{2})})-\Delta_{o^{(j)},i^{\prime}}f(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{(j)})})$
$\displaystyle+\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})})-\Delta_{e^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$
$\displaystyle\leq\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{o}^{(j-\frac{1}{2})})+\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{(j)})})$
$\displaystyle\leq
2\left[\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})\right].$

Case 2. The argument follows similarly as Case 1 where one can show
$\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})$
is greater than or equal to
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$. Therefore, we
have

$\displaystyle f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})$
$\displaystyle=\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})-\Delta_{e^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$
$\displaystyle\leq\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})$
$\displaystyle\leq
2\left[\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{(j-1)})\right].$

  * Proof.

[Proof of Theorem 5.3] We have

$\displaystyle f(\boldsymbol{o})-f(\boldsymbol{x})$
$\displaystyle=\sum_{j\in[B]}\left(f(\boldsymbol{o}^{(j-1)})-f(\boldsymbol{o}^{(j)})\right)$
$\displaystyle\leq
2\sum_{j\in[B]}\left(\frac{1+\varepsilon}{1-\varepsilon}f(\boldsymbol{x}^{(j)})-f(\boldsymbol{x}^{j-1})\right)$
$\displaystyle\leq\frac{2-2\varepsilon+2\varepsilon{}B}{1-\varepsilon}f(\boldsymbol{x}),$

where the first inequality is due to Lemma B.1. Hence, we have
$F(\boldsymbol{x})\geq\frac{(1-\varepsilon)^{2}}{(3-3\varepsilon+2\varepsilon{}B)(1+\varepsilon)}F(\boldsymbol{o})$.

####  B.1.2 $\varepsilon$-ADR Functions with the Individual Size Constraints

###### Lemma B.2

For any $j\in[B]$,
$2\left[F(\boldsymbol{x}^{(j)})-F(\boldsymbol{x}^{(j-1)})\right]\geq\frac{1-\varepsilon}{1+\varepsilon}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})\right]$.

  * Proof.

[Proof of Lemma B.2] The arguments for Case 1 and Case 2 are similar. We begin
with Case 1.

Case 1. First note that since $(e^{(j)},i^{(j)})$ is selected by the greedy
algorithm, we have
$\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})$
and
$\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})\geq{}\Delta_{e^{(j)},i^{\prime}}F(\boldsymbol{x}^{(j-1)})$.
Since
$\boldsymbol{x}^{(j-1)}\preceq\boldsymbol{o}^{(j-\frac{1}{2})}\preceq\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})}$,
we have that
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})})\geq\frac{1}{1+\varepsilon}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})$,
$\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{o^{(j)},i^{(j)}}f(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})})\geq\frac{1}{1+\varepsilon}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})})$,
and
$\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{x}^{(j-1)})\geq\Delta_{e^{(j)},i^{\prime}}f(\boldsymbol{x}^{(j-1)})\geq\frac{1}{1+\varepsilon}\geq\Delta_{e^{(j)},i^{\prime}}F(\boldsymbol{x}^{(j-1)})$
from orthant submodularity.

Therefore, we obtain that
$\frac{1}{1-\varepsilon}\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})$ is
greater than or equal to
$\frac{1}{1+\varepsilon}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})$,
$\frac{1}{1+\varepsilon}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})$,
and
$\frac{1}{1+\varepsilon}\Delta_{e^{(j)},i^{\prime}}F(\boldsymbol{x}^{(j-1)})$
by the definition of $\varepsilon$-ADR.

$\displaystyle\frac{1}{1+\varepsilon}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})\right]$
$\displaystyle=$
$\displaystyle\frac{1}{1+\varepsilon}\left[\Delta_{e^{(j)},i^{\prime}}F(\boldsymbol{o}^{(j-\frac{1}{2})})-\Delta_{o^{(j)},i^{\prime}}F(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{(j)})})\right.$
$\displaystyle~{}~{}\quad\quad\quad\left.+\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{\prime})})-\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{1+\varepsilon}\left[\Delta_{e^{(j)},i^{\prime}}F(\boldsymbol{o}^{(j-\frac{1}{2})})+\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})}_{(e^{(j)},i^{(j)})})\right]$
$\displaystyle\leq$
$\displaystyle\frac{2}{1-\varepsilon}\left[F(\boldsymbol{x}^{(j)})-F(\boldsymbol{x}^{(j-1)})\right].$

Case 2. The argument follows similarly as Case 1 where one can show
$\frac{1}{1-\varepsilon}\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{x}^{(j-1)})$ is
greater than or equal to
$\frac{1}{1+\varepsilon}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})$.
Therefore, we have

$\displaystyle\frac{1}{1+\varepsilon}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})\right]$
$\displaystyle=$
$\displaystyle\frac{1}{1+\varepsilon}\left[\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})-\Delta_{e^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{1+\varepsilon}\Delta_{o^{(j)},i^{(j)}}F(\boldsymbol{o}^{(j-\frac{1}{2})})$
$\displaystyle\leq$
$\displaystyle\frac{2}{1-\varepsilon}\left[F(\boldsymbol{x}^{(j)})-F(\boldsymbol{x}^{(j-1)})\right].$

  * Proof.

[Proof of Theorem 5.4] We have

$\displaystyle F(\boldsymbol{o})-F(\boldsymbol{x})$
$\displaystyle=\sum_{j\in[B]}\left[F(\boldsymbol{o}^{(j-1)})-F(\boldsymbol{o}^{(j)})\right]$
$\displaystyle\leq\frac{2(1+\varepsilon)}{1-\varepsilon}\sum_{j\in[B]}\left[F(\boldsymbol{x}^{(j)})-F(\boldsymbol{x}^{(j-1)})\right]$
$\displaystyle\leq\frac{2(1+\varepsilon)}{1-\varepsilon}F(\boldsymbol{x})$

where the first inequality is due to Lemma B.2. Hence, we have
$F(\boldsymbol{x})\geq{}\frac{1-\varepsilon}{3+\varepsilon}F(\boldsymbol{o})$.

##  C Improved Greedy Approximation Ratios When $f$ is Known: Additional
material

We start by restating the theorem presented in Section 6.

###### Theorem C.1

Let $f$ be a $k$-submodular function and $F$ be an $\varepsilon$-approximately
$k$-submodular function that is bounded by $f$. If there is an algorithm that
provides an approximation ratio of $\alpha$ for maximizing $f$ subject to
constraint $\mathbb{X}$, then the same solution yields an approximation ratio
of $\frac{1-\varepsilon}{1+\varepsilon}\alpha$ for maximizing $F$ subject to
constraint $\mathbb{X}$.

  * Proof.

Let $\boldsymbol{o}_{f}$ and $\boldsymbol{o}_{F}$ be the optimal solutions of
$f$ and $F$, respectively, subject to constraint $\mathbb{X}$. Let
$\boldsymbol{x}_{f}$ be a solution of $f$ returned by an algorithm with an
approximation ratio of $\alpha$. We have

$\displaystyle\frac{1}{1-\varepsilon}F(\boldsymbol{x}_{f})\geq
f(\boldsymbol{x}_{f})\geq\alpha f(\boldsymbol{o}_{f})\geq\alpha
f(\boldsymbol{o}_{F})\geq\frac{1}{1+\varepsilon}\alpha F(\boldsymbol{o}_{F}),$

where the first inequality is by applying the definition of $\varepsilon$-AS,
the second inequality is by the definition of approximation ratios, the third
inequality is by replacing $\boldsymbol{o}_{f}$ with a less optimal solution
$\boldsymbol{o}_{F}$, and the last inequality is by the definition of
$\varepsilon$-AS.

The above theorem provides a set of results for our settings.

###### Corollary C.1

Suppose $F$ is approximately submodular. By applying the greedy algorithm on
$f$ subject to a size constraint, we obtain a solution providing an
approximation ratio of $\frac{1-\varepsilon}{1+\varepsilon}(1-\frac{1}{e})$ to
the size constrained maximization problem of $F$.

The above result follows from the known approximation ratio of greedy
algorithms for monotone submodular functions [7, 19]. Comparing to the
$\varepsilon$-AS result of [14], when
$B\geq\frac{1}{4(e-1)\varepsilon}+\frac{1}{2}$
111$B\geq\frac{1}{4(e-1)\varepsilon}+\frac{1}{2}$ implies
$B\geq\frac{1}{4(1-1/e)}\left(\frac{1}{\varepsilon}-\varepsilon-\left(1-\frac{1}{e}\right)\left(\frac{1}{\varepsilon}-2+\varepsilon\right)\right)$.
Thus,
$B\geq\frac{1-\varepsilon^{2}-(1-1/e)(1-\varepsilon)^{2}}{4(1-1/e)\varepsilon}$.
Then we have
$\frac{1}{1+\frac{4B\varepsilon}{(1-\varepsilon)^{2}}}\leq\frac{1-\varepsilon}{1+\varepsilon}(1-\frac{1}{e})$,
Corollary C.1 yields a better approximation ratio. Specifically, we obtain the
corollaries of Section 6 which we copy below for convenience.

###### Corollary C.2

Suppose $F$ is approximately $k$-submodular. By applying the $k$-Greedy-TS
algorithm on $f$ subject to a total size constraint, we obtain a solution
providing an approximation ratio of $\frac{1-\varepsilon}{2(1+\varepsilon)}$
to total size constrained maximization problem of $F$.

###### Corollary C.3

Suppose $F$ is approximately $k$-submodular. By applying the $k$-Greedy-IS
algorithm on $f$ subject to an individual size constraint, we obtain a
solution providing an approximation ratio of
$\frac{1-\varepsilon}{3(1+\varepsilon)}$ to individual size constrained
maximization problem of $F$.

The above corollaries follow from the results of [21] where one can obtain
approximation ratios of $\frac{1}{2}$ and $\frac{1}{3}$ for total size and
individual size constraints, respectively, for maximizing monotone
$k$-submodular functions. It turns out that, for any value of $\varepsilon$,
we can derive better theoretical guarantees using the the greedy solutions
from $f$ according to the above corollaries for $\varepsilon$-AS $F$. For $F$
that is $\varepsilon$-ADR, since it is also $\varepsilon$-AS $F$, the above
results apply immediately. However, the above results provide a weaker
guarantee than applying greedy algorithms on $F$ directly.

##  D Additional Experiment Details

###  D.1 Non-submodularity

To see that the F constructed in the AG setting is not k-submodular, consider
$k=1$, $\xi(u)=1-\varepsilon$, $\xi(v)=1$, $\xi(\\{u,v\\})=1$, as well as
$f(\\{u,v\\})-f(\\{v\\})=f(\\{u\\})$. It follows that
$F(\\{u\\})-F(\mathbf{0})<F(\\{u,v\\}-F(\\{v\\})\Leftrightarrow(1-\varepsilon)f(\\{u\\})=(1-\varepsilon)(f(\\{u,v\\}-f(\\{v\\}))<f(\\{u,v\\}-f(\\{v\\})=F(\\{u,v\\}-F(\\{v\\})$
for $\varepsilon>0$.

To see that $F(\boldsymbol{x})=\max_{x\in{supp(\boldsymbol{x})}}\xi(x)\cdot
f(\boldsymbol{x})$ constructed in the MaxG setting is not $k$-submodular,
consider $k=1$ and two elements $\\{u,v\\}$, $\xi(u)=1-\varepsilon$,
$\xi(v)=1$, and $f(\\{u,v\\})-f(\\{v\\})=f(\\{u\\})$ for some $u,v$. It
follows that
$F(\\{u\\})-F(\mathbf{0})<F(\\{u,v\\})-F(\\{v\\})\Leftrightarrow(1-\varepsilon)f(\\{u\\})<f(\\{u,v\\})-f(\\{v\\})$
for $\varepsilon>0$.

To see that $F(\boldsymbol{x})=\xi(\boldsymbol{x})\cdot f(\boldsymbol{x})$
with $\xi({\boldsymbol{x}})=\frac{\sum_{x\in
supp(\boldsymbol{x})}\xi(x)}{|supp(\boldsymbol{x})|}$, which is constructed in
the MeanG setting, is not $k$-submodular, consider $k=1$,
$\xi(u)=1-\varepsilon$, and $\xi(v)=1$, as well as
$f(\\{u,v\\})=\frac{3}{2}f(\\{u\\})$ and $f(\\{u,v\\})-f(\\{v\\})=f(\\{u\\})$
for some $u,v$. It follows that
$F(\\{u\\})-F(\mathbf{0})<F(\\{u,v\\}-F(\\{v\\})\Leftrightarrow(1-\varepsilon)f(\\{u\\})<(1-\frac{3}{4}\varepsilon)f(\\{u\\})=f(\\{u\\})-\frac{3\varepsilon}{4}f(\\{u\\})=f(\\{u,v\\})-f(\\{v\\})-\frac{\varepsilon}{2}f(\\{u,v\\})=\frac{2-\varepsilon}{2}f(\\{u,v\\})-f(\\{v\\})=F(\\{u,v\\})-F(\\{v\\})$
for $\varepsilon>0$.

###  D.2 Influence Maximization with Approximately $k$-Submodular Functions
and the TS Constraint

In the main paper, we considered Influence Maximization with the impact of
$k$. Here, we present results in Figs. 5, 6 and 7 for the same problem with
the impact of $B$ and $\varepsilon$. The trends are similar to those for
parameter $k$ reported in the paper; $Gr$-$H$ outperformed $Gr$-$\tilde{H}$ in
the AG setting, and the opposite happened in the MeanG and MaxG settings.

(a)

(b)

Figure 5: $\tilde{I}$ in AG setting vs: (a) $B$, (b) $\varepsilon$.

(a)

(b)

Figure 6: $\tilde{I}$ in Mean setting vs: (a) $B$, (b) $\varepsilon$.

(a)

(b)

Figure 7: $\tilde{I}$ in MaxG setting vs: (a) $B$, (b) $\varepsilon$.

###  D.3 Sensor Placement with Approximately $k$-Submodular Functions and the
TS Constraint

In the main paper, we considered Sensor Placement with IS constraints. Here,
we present results for the same problem with TS constraint in Figs. 8, 9 and
10. As can be seen, the results are qualitatively similar to those for the
problem with IS constraints. That is, $Gr$-$H$ outperformed $Gr$-$\tilde{H}$
in the AG setting, and the opposite happened in the MeanG and MaX settings.

(a)

(b)

(c)

Figure 8: $\tilde{H}$ in AG setting vs: (a) $k$, (b) $B$, (c) $\varepsilon$.

(a)

(b)

(c)

Figure 9: $\tilde{H}$ in MeanG setting vs: (a) $k$, (b) $B$, (c)
$\varepsilon$.

(a)

(b)

(c)

Figure 10: $\tilde{H}$ in MaxG setting vs: (a) $k$, (b) $B$, (c)
$\varepsilon$.

###  D.4 Sensor Placement and Influence Maximization with Approximately
Diminishing Returns $k$-Submodular Functions

We constructed $\varepsilon$-ADR functions for each setting, as follows.

In the AG setting, we ran $k$-Greedy-TS on $f$ and set
$\Delta_{e,i}F(\boldsymbol{x_{f}})=(1+\varepsilon)\Delta_{e,i}f(\boldsymbol{x_{f}})$
for its solution $\boldsymbol{x_{f}}$. For any other
$\boldsymbol{x}\neq\boldsymbol{x_{f}}$, we selected $\xi(\boldsymbol{x})$
uniformly at random in $[1-\varepsilon,1]$ and set
$\Delta_{e,i}F(\boldsymbol{x_{f}})=\xi(\boldsymbol{x})\cdot\Delta_{e,i}f(\boldsymbol{x_{f}})$,
for each $(e,i)$. Then, we summed up
$\max_{(e,i)}\Delta_{e,i}F(\boldsymbol{x})$ in each iteration to obtain
$F(\boldsymbol{x})$.

In the MaxG setting, we set
$\Delta_{e,i}F(\boldsymbol{x})=\xi(\boldsymbol{x},e)\cdot\Delta_{e,i}f(\boldsymbol{x})$,
where $\xi(\boldsymbol{x},e)=\max(\xi(e),\max_{x\in
supp(\boldsymbol{x})}\xi({x}))$ and $\xi(x)\in[1-\varepsilon,1]$. We then
summed up $\max_{(e,i)}\Delta_{e,i}F(\boldsymbol{x})$ in each iteration to
obtain $F(\boldsymbol{x})$. Similarly, in the MeanG setting, we used
$\xi(\boldsymbol{x},e)=\frac{\xi(e)+\sum_{x\in
supp(\boldsymbol{x})}\xi(x)}{|supp(\boldsymbol{x})|+1}$, where
$\xi(x)\in[1-\varepsilon,1]$.

####  D.4.1 Non Submodularity

To see that the function $F$ constructed in the AG setting is not
k-submodular, consider $k=1$, $\xi(\\{v\\},u)=1$,
$\xi(\mathbf{0},u)=1-\varepsilon$, as well as
$f(\\{u,v\\})-f(\\{v\\})=f(\\{u\\})$ for some $u,v$. It follows that
$F(\\{u\\})-F(\mathbf{0})<F(\\{u,v\\}-F(\\{v\\})\Leftrightarrow\Delta_{u}F(\mathbf{0})=(1-\varepsilon)\Delta_{u}f(\mathbf{0})<f(\\{u,v\\}-f(\\{v\\})=\Delta_{u}F(\\{v\\})=F(\\{u,v\\}-F(\\{v\\})$
for $\varepsilon>0$.

To see that the $F$ function constructed in the MaxG setting is not
$k$-submodular, consider $k=1$ and two elements $\\{u,v\\}$,
$\xi(u)=1-\varepsilon$, $\xi(v)=1$, and $f(\\{u,v\\})-f(\\{v\\})=f(\\{u\\})$
for some $u,v$. It follows that
$F(\\{u\\})-F(\mathbf{0})<F(\\{u,v\\})-F(\\{v\\})\Leftrightarrow\Delta_{u}F(\mathbf{0})=(1-\varepsilon)\Delta_{u}f(\mathbf{0})<f(\\{u,v\\})-f(\\{v\\})=\Delta_{u}f(\\{v\\})=F(\\{u,v\\})-F(\\{v\\})$
for $\varepsilon>0$.

To see that the $F$ function constructed in the MeanG setting is not
$k$-submodular, consider $k=1$, $\xi(u)=1-\varepsilon$, and $\xi(v)=1$, as
well as $\Delta_{u}f(\\{v\\})=\Delta_{u}f(\mathbf{0})$ for some $u,v$. It
follows that
$F(\\{u\\})-F(\mathbf{0})<F(\\{u,v\\}-F(\\{v\\})\Leftrightarrow\Delta_{u}F(\mathbf{0})=(1-\varepsilon)\Delta_{u}f(\mathbf{0})<\frac{2-\varepsilon}{2}\Delta_{u}f(\mathbf{0})=\frac{2-\varepsilon}{2}\Delta_{u}f(\\{v\\})=\Delta_{u}F(\\{v\\})=F(\\{u,v\\})-F(\\{v\\})$
for $\varepsilon>0$.

We first considered sensor placement with the TS constraint, but with an
$\varepsilon$-ADR instead of an $\varepsilon$-AS function. $k$-Greedy-TS using
$H$ as $f$ is denoted with $Gr$-$H$-$ADR$, and $k$-Greedy-TS using $\tilde{H}$
as $F$ is denoted with $Gr$-$\tilde{H}$-$ADR$. The results in Figs. 11, 12,
and 13 are analogous to those for the $\varepsilon$-AS function in Section D.3
and confirm our analysis in Section 6.

(a)

(b)

(c)

Figure 11: $\tilde{H}$ in AG setting vs: (a) $k$, (b) $B$, (c) $\varepsilon$.

(a)

(b)

(c)

Figure 12: $\tilde{H}$ in MeanG setting vs: (a) $k$, (b) $B$, (c)
$\varepsilon$.

(a)

(b)

(c)

Figure 13: $\tilde{H}$ in MaxG setting vs: (a) $k$, (b) $B$, (c)
$\varepsilon$.

We then considered sensor placement with IS constraints using $k$-Greedy-IS.
$k$-Greedy-IS using $H$ as $f$ is denoted with $Gr$-$H$-$ADR$, and $k$-Greedy-
IS using $\tilde{H}$ as $F$ is denoted with $Gr$-$\tilde{H}$-$ADR$. As
expected from the analysis in Section 6, the results in Figs. 14, 15, and 16
are similar to those in Figs. 11, 12, and 13.

(a)

(b)

(c)

Figure 14: $\tilde{H}$ in AG setting vs: (a) $k$, (b) $b$, (c) $\varepsilon$.

(a)

(b)

(c)

Figure 15: $\tilde{H}$ in MeanG setting vs: (a) $k$, (b) $b$, (c)
$\varepsilon$.

(a)

(b)

(c)

Figure 16: $\tilde{H}$ in MaxG setting vs: (a) $k$, (b) $b$, (c)
$\varepsilon$.

Last, we considered influence maximization with IS constraints and an
$\varepsilon$-ADR function. $k$-Greedy-TS using $I$ as $f$ is denoted with
$Gr$-$I$-$ADR$, and $k$-Greedy-TS using $\tilde{I}$ as $F$ is denoted with
$Gr$-$\tilde{I}$-$ADR$. The obtained results are similar to those for the case
of $\varepsilon$-AS function (see Section 7.3 and Appendix D.2).

(a)

(b)

(c)

Figure 17: $\tilde{I}$ in AG setting vs: (a) k, (b) $B$, (c) $\varepsilon$.

(a)

(b)

(c)

Figure 18: $\tilde{I}$ in Mean setting vs: (a) k, (b) $B$, (c) $\varepsilon$.

(a)

(b)

(c)

Figure 19: $\tilde{I}$ in MaxG setting vs: (a) k, (b) $B$, (c) $\varepsilon$.


# Lung Segmentation and Nodule Detection in Computed Tomography Scan using a
Convolutional Neural Network Trained Adversarially using Turing Test Loss

Rakshith Sathish1, Rachana Sathish1, Ramanathan Sethuraman2 and Debdoot Sheet1
*This work supported through a research grant from Intel India Grand Challenge
2016 for Project MIRIAD1Rakshith Sathish, Rachana Sathish and Debdoot Sheet
are with the Department of Electrical Engineering, Indian Institute of
Technology Kharagpur, India-721302 {rsatish<EMAIL_ADDRESS><EMAIL_ADDRESS>Sethuraman is with Intel Technology India Pvt.
Ltd. Bangalore, India

###### Abstract

Lung cancer is the most common form of cancer found worldwide with a high
mortality rate. Early detection of pulmonary nodules by screening with a low-
dose computed tomography (CT) scan is crucial for its effective clinical
management. Nodules which are symptomatic of malignancy occupy about 0.0125 -
0.025% of volume in a CT scan of a patient. Manual screening of all slices is
a tedious task and presents a high risk of human errors. To tackle this
problem we propose a computationally efficient two stage framework. In the
first stage, a convolutional neural network (CNN) trained adversarially using
Turing test loss segments the lung region. In the second stage, patches
sampled from the segmented region are then classified to detect the presence
of nodules. The proposed method is experimentally validated on the LUNA16
challenge dataset with a dice coefficient of $0.984\pm 0.0007$ for 10-fold
cross-validation.

##  I Introduction

Lung cancer is the most common form of cancer worldwide, accounting for about
2.1 million new cases and 1.8 million deaths annually [1]. Presence of nodules
is considered to be one of the precursors for lung cancer. Pulmonary nodules
are radiographically opaque and measure up to 30 millimeter in diameter. Low-
dose CT based imaging is performed to detect the presence of nodules [2]. The
chances of survival increases significantly when diagnosed at an early stage
of the cancer, thus rendering the task of nodule detection a critical one.

Manual screening of nodules in CT scans is a time consuming and stressful task
which requires the expertise of an experienced radiologist. A standard CT
volume has 200-400 slices while the nodules are present in only 3-5 slices.
Radiologists have to manually screen the slices, identify the suspicious
slices and later detect nodules. Manual screening is often plagued with false
negative classifications, due to the very small size of nodules. Automation of
this task can lessen the workload of manual screening and also reduce false
negatives and improve cancer management outcomes through early diagnosis.

Figure 1: Overview of the proposed method

Challenges: One of the major challenges associated with the detection of lung
nodules is the wide variation in appearance and spatial distribution. Nodules
can be present either completely isolated within the lung parenchyma or
attached to the lung walls. Characteristics of a nodule, such as texture,
shape, opacity, size, etc have high variance which makes its detection a
complex task.

Related works: Most of the existing methods propose to solve the problem of
lung nodule detection through separate stages for lung and nodule
segmentation. In one such method [3], lung segmentation has been performed
using U-Net [4]. Recurrent residual convolutional neural network (RRCNN) [5]
have also been used for the same. An improved version of U-Net [6], termed
multi-scale prediction network (MPN) was proposed to solve lung area
segmentation problems on thoracic CT scans. A fast and efficient 3D lung
segmentation method based on V-net was proposed by [7]. In [8] the nodule
detection task is performed in two stages. In the first stage, all possible
candidate regions in CT slices are detected and in the later stage a 3D fully
convolutional neural network (FCN) is used to detect nodules in the candidate
regions with high certainty. Though this method presents high performance
metrics, it also incurs high computational load in both stage for 3D
processing.

Our approach: Considering the constraints and challenges associated with lung
nodule detection, we propose a two stage framework as shown in Fig. 1
involving only 2D convolutional neural networks (CNNs). In the first stage we
implement a fully convolutional network trained adversarially to segment the
lung region and in the second stage a classifier network is trained to
identify presence of nodules in image patches extracted from within the
segmented lung region. The proposed method involves 2D processing with a
compute complexity of $157.320\times 10^{9}$ FLOPS (floating point operations)
and $2.796\times 10^{6}$ FLOPS per slice for first and second stage
respectively.

##  II Problem Statement

Consider a CT volume $\mathbf{V}$ consisting of $N$ number of axial 2D slice
$\mathbf{S}$. We model the problem of nodule detection in two stages. In
_Stage 1_ , each pixel of the slice $\mathbf{S_{n}}$ is classified into one of
the two classes $\\{lung,background\\}$, to obtain a segmentation map. In
_Stage 2_ a two class classification problem is formulated where patches from
the region identified as lungs in slice $\mathbf{S_{n}}$ is classified into a
class $C_{i}\in\\{C_{1},C_{2}\\}$. $C_{1}$ corresponds to presence of nodules
and $C_{2}$ indicates its absence.

##  III Method

The overall workflow is divided into two stages. In _Stage 1_ , lung area is
segmented followed by detection of nodules in _Stage 2_. Overview of the
method is shown in Fig. 1.

Stage 1: Lung segmentation

A modified version of SUMNet [9] with batch-normalization is trained in _Stage
1_ for segmentation of lungs in 2D slices of CT. The encoder of the network is
similar to VGG16 [10] and is initialized with ImageNet pre-trained weights.
The network has feature concatenation across convolutional blocks and
propagation of indices across pooling layers from encoder to decoder. In
addition to the structural segmentation loss, the network is trained using an
additional adversarial loss similar to a generative adversarial network [11].
Fig. 3 shows the two steps of training involved in $Stage1$.

In each iteration of training, the discriminator is first trained to performs
a Turing test to identify the ground truth (GT) and the segmentation map
(Pred.) by presenting them together as the input to the network [12]. The
concatenated input tensor of size $2\times 512\times 512$ is shuffled along
the depth to randomize the order of the two channels as shown in Fig. 3(a).
This ensures that the discriminator doesn’t leverage the order of
concatenation to differentiate between GT and Pred. The network is trained by
minimizing the loss $J_{Adv}$, which is computed as the binary cross-entropy
loss between its prediction ($\mathbf{o}_{d}$) and the true label
($\mathbf{t}_{d}$).

$J_{Adv}=\mathbf{o}_{d}\log(\mathbf{t}_{d})+(\mathbf{1}-\mathbf{o}_{d})\log(\mathbf{1}-\mathbf{t}_{d})$
(1)

where $\mathbf{t}_{d}\in\\{[1,0],[0,1]\\}$ and depends on the order of
shuffling. The architecture of discriminator is show in Fig. 2.

Figure 2: Architecture of discriminator

Next, the segmentation network is trained as shown in Fig. 3(b) using
$J_{Net}$ given as,

$J_{Net}=J_{Seg}-\alpha J_{Adv}$ (2)

where $J_{Seg}$ is the cross entropy loss computed between the ground truth
($GT$) and the segmentation map ($Pred$). The hyper-parameter $\alpha$, is
chosen empirically to ensure similar magnitude of two losses.

(a) Training discriminator

(b) Training segmentation network

Figure 3: Figure shows training of (a) discriminator and (b) segmentation
network in _Stage 1_.

Stage 2: Detection of lung nodules

The nodules are significantly smaller in size in comparison with lungs.
Therefore, patches of size $64\times 64$ are extracted from the region
segmented as lungs in each slice in _Stage 1_ for further processing in _Stage
2_. A LeNet [13] based classifier is used to detect the presence of nodules in
the patches as shown in Fig. 4. The third convolutional layer of the standard
LeNet architecture is modified to have a kernel size of $5$. An additional
fully-connected layer having $256$ neurons is introduced after the last sub-
sampling layer. Also, the number of neurons in last layer is changed from $10$
to $2$. Thus, by evaluating patches within the lung region, the presence of
nodules in each slice of the CT volume is determined

Figure 4: Figure shows the overview of _Stage 2_. Class $C_{1}$ corresponds to
presence of nodules and class $C_{2}$ corresponds to its absence.

##  IV Experiments

Datasets: The proposed method is experimentally validated by performing
10-fold cross-validation on the LUNA16 challenge
dataset111https://luna16.grand-challenge.org/. The dataset consists of CT
volumes from 880 subjects, provided as ten subsets for 10-fold cross-
validation. In each fold of the experiment, eight subsets from the dataset was
used for training and one each for validation and testing. The annotations
provided includes binary masks for lung segmentation and, coordinates and
spherical diameter of nodules present in each slice. LIDC-IDRI
dataset222http://doi.org/10.7937/K9/TCIA.2015.LO9QL9SX from which LUNA16 is
derived has nodule annotations in the form of contours which preserves its
actual shape. Therefore, we use annotations from LUNA dataset only in _Stage
1_. The annotations for the nodules from the LIDC dataset is used in _Stage 2_
(nodule detection) to determine presence of nodules in image patches. The
ground truth annotations were marked in a two-phase image annotation process
performed by four experienced thoracic radiologists. Systematic sampling of
slices from the CT volumes was performed to ensure equal distribution of
slices with and without the presence of nodules.

Stage 1: Lung segmentation

Baselines: The following baselines were used for comparison of performance of
_Stage 1_. BL1: UNet [4] trained using only $J_{Seg}$. BL2: R2UNet [5] trained
using only $J_{Seg}$. BL3: SUMNet [9] trained using only $J_{Seg}$.

Training: The segmentation network and the discriminators were trained using
Adam optimizer [14] for 35 epochs, with a learning rate of $10^{-4}$. The loss
scaling factor $\alpha$ in Eq. 2 was set as $0.001$.

Stage 2 : Detection of lung nodules

The classification network for nodule detection was trained using $32,594$
patches of size $64\times 64$ extracted from the lung region in the CT images,
including the lung walls. Out of these patches, $16,440$ had partial or entire
nodules accounting to $3,288$ in number. The model was trained for 50 epochs
using Adam optimizer, with a learning rate of $10^{-4}$.

##  V Results and Discussion

Evaluation of lung segmentation

Quantitative evaluation: The performance of the proposed method and the
baselines listed in Sec. IV for segmentation was evaluated using dice
similarity coefficient (DSC),Area under the ROC Curve (AUC) and Hausdorff
distance (HD).

$DSC=\frac{2|Pred.\cap GT|}{|Pred.|+|GT|}$ (3)

TABLE I: Quantitative metrics for lung segmentation (_Stage 1_).  Architecture | DSC | AUC | HD
---|---|---|---
BL1 | 0.979 | 0.9948 | 3.9424
BL2 | 0.983 | 0.9950 | 3.8754
BL3 | 0.980 | 0.9945 | 3.9596
Proposed method | 0.983 | 0.9948 | 3.8989

Tab. I presents the DSC, AUC Score and HD for fold 1 of the experimental
setup. Due to the computational complexity of BL1 and BL2 which results in
longer training duration, the performance evaluation was performed on only
fold 1 of the dataset for these two methods. The mean and standard deviation
of DSC across all ten folds of the experiments for BL3 and the proposed method
is $0.980\pm 0.0018$ and $0.984\pm 0.0007$ respectively. The adversarial
learning framework improves the performance consistently across all folds.

Computational complexity: The number of trainable parameters and total
floating point operations (TFLOPS) for the baselines and proposed method are
shown in Tab. II. TFLOPS calculation was done for a sample input of size
$512\times 512$. It can be seen from Tab. II that the proposed method has
lesser trainable parameters and involves significantly less number operations
in comparison with the popularly used UNet (BL1) and R2UNet (BL2). Time taken
to train the baselines and the corresponding model size is shown in Tab. III.
All the networks were trained for 35 epochs on a GeForce GTX 1080 with 11GB
RAM. Though the performance of the proposed method is comparable to that of
BL2, it is computationally more efficient. The proposed framework can be
trained $6\times$ faster with $1.6\times$ lesser memory requirement.

TABLE II: Total number of trainable parameters and FLOPS during inference.

Architecture | Parameters | TFLOPs
---|---|---
BL1 | 34,525,952 (34.526M) | 261,901,254,656 (261.901G)
BL2 | 39,091,328 (39.091M) | 612,076,355,584 (612.076G)
BL3 | 23,863,336 (23.863M) | 153,538,789,376 (153.539G)
| Proposed
---
method
24,997,032 (24.997M) | 153,538,789,376 (153.539G)

TABLE III: Comparison of computational complexity based on the total training time (35 epochs) and trained model size Architecture | Training time | Model size
---|---|---
BL1 | 709m 37s | 138.2 MB
BL2 | 2153m 11s | 156.5 MB
BL3 | 326m 40s | 95.5 MB
| Proposed
---
method
458m 17s | 95.5 MB

Qualitative evaluation: The qualitative result of the segmentation of lungs
for the proposed framework on a randomly chosen test image is shown in Fig. 5.
The result of segmentation in the hilar region of lungs improves significantly
with the proposed method.

(a) Test image

(b) Ground truth

(c) Prediction of _Stage 1_

(d) Result of image processing

Figure 5: Figure shows (a) a sample test image, (b) the corresponding ground
truth (c) prediction of _Stage 1_ and (d) result of classical image
processing.

Evaluation of nodule detection

Quantitative performance: The performance of the proposed method in detecting
nodules is reported in terms of accuracy, sensitivity, and specificity of
classification. Scores obtained are presented in Tab. IV. Explainability of ML
based methods is crucial in the field of medical image analysis. We have
evaluated the trained classification network using RISE [15] to obtain a
saliency map which assigns an importance score to each pixel of the input
towards the model’s prediction. Fig. 6 shows the saliency map for a randomly
selected input patch which contains a nodule.

TABLE IV: Performance of the classification network Metric | Score
---|---
Accuracy | 98.00%
Sensitivity | 0.9902
Specificity | 0.9688

(a) Image patch

(b) Saliency map

Figure 6: Figure shows (a) sample image patch given as an input to the
classifier network with the nodule marked in yellow (b) saliency map generated
using RISE for positive prediction. In the colormap, red depicts high
importance score and blue corresponds to a low score.

Computational performance: Classification network is computationally lighter
in comparison with the segmentation network with a total of 50,162 (50.162K)
trainable parameters and 2,796,448 (2.796M) floating point operations.

##  VI CONCLUSION

In this paper, we propose a two stage framework for detection of lung nodules
in CT slices. In the first stage, we segment the lung region using an
adversarially trained CNN followed by detection of presence of lung nodules in
image patches extracted from the lung region. We have achieved results
comparable to the state-of-the-art architectures in terms of dice-coefficient
score for segmentation and in terms of accuracy, specificity and sensitivity
for the classification task, while being significantly less computationally
expensive in terms of total number of parameters, total floating point
operations, training time and model size. The additional loss from a
discriminator used to train the network helps in improving the performance
with very less increment in the computational complexity. Further, RISE based
evaluation of explainability shows that the network attends to the relevant
regions in an image while detecting the presence of a nodule.

## References

  * [1] WHO _et al._ , “World health organization cancer fact sheet,” 2009.
  * [2] N. L. S. T. R. Team, “Reduced lung-cancer mortality with low-dose computed tomographic screening,” _New England J. Med._ , vol. 365, no. 5, pp. 395–409, 2011.
  * [3] B. A. Skourt, A. El Hassani, and A. Majda, “Lung ct image segmentation using deep neural networks,” _Proc. Comp. Sci._ , vol. 127, pp. 109–113, 2018\.
  * [4] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _Int. Conf.n Med. Image Comput. Comp.-Assist. Interv._ , 2015, pp. 234–241.
  * [5] M. Z. Alom, M. Hasan, C. Yakopcic, T. M. Taha, and V. K. Asari, “Recurrent residual convolutional neural network based on u-net (r2u-net) for medical image segmentation,” _arXiv preprint arXiv:1802.06955_ , 2018.
  * [6] Y. Gu, Y. Lai, P. Xie, J. Wei, and Y. Lu, “Multi-scale prediction network for lung segmentation,” in _Int. Symp. Biomed. Imag._ , 2019, pp. 438–442.
  * [7] M. Negahdar, D. Beymer, and T. Syeda-Mahmood, “Automated volumetric lung segmentation of thoracic ct images using fully convolutional neural network,” in _Med. Imag.: Comp.-Aided Dia._ , vol. 10575, 2018, p. 105751J.
  * [8] L. Fu, J. Ma, Y. Chen, R. Larsson, and J. Zhao, “Automatic detection of lung nodules using 3d deep convolutional neural networks,” _J. Shanghai Jiaotong Uni._ , vol. 24, no. 4, pp. 517–523, 2019.
  * [9] S. Nandamuri, D. China, P. Mitra, and D. Sheet, “Sumnet: Fully convolutional model for fast segmentation of anatomical structures in ultrasound volumes,” in _Int. Symp. Biomed. Imag._ , 2019, pp. 1729–1732.
  * [10] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _Int. Conf. Learning. Repr._ , 2015.
  * [11] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in _Adv. Neu. Info. Proc. Sys._ , 2014, pp. 2672–2680.
  * [12] R. Sathish, R. Rajan, A. Vupputuri, N. Ghosh, and D. Sheet, “Adversarially trained convolutional neural networks for semantic segmentation of ischaemic stroke lesion using multisequence magnetic resonance imaging,” in _Ann. Int. Conf. IEEE Engg. Med. Bio. Soc._ , 2019, pp. 1010–1013.
  * [13] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proc. IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [14] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _Int. Conf. Learning Repr._ , 2015.
  * [15] V. Petsiuk, A. Das, and K. Saenko, “Rise: Randomized input sampling for explanation of black-box models,” _Brit. Mach. Vis. Conf._ , 2018.