Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection
Authors: Abir De
Soumen Chakrabarti
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural set function
data selection

Abstract: Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization.  Many recent approaches to learn submodular functions suffer from limited expressiveness. In this work, we propose FlexSubNet, a family of flexible neural models for both monotone and non-monotone submodular functions. To fit a latent submodular function from (set, value) observations, our method applies a concave function on modular functions in a recursive manner. We do not draw the concave function from a restricted family, but rather learn from data using a highly expressive neural network that implements a differentiable quadrature procedure. Such an expressive neural model for concave functions may be of independent interest.  Next, we extend this setup to provide a novel characterization of monotone $\alpha$-submodular functions, a recently introduced notion of approximate submodular functions.  We then use this characterization to design a novel neural model for such functions. Finally, we consider learning submodular set functions under distant supervision in the form of  (perimeter, high-value-subset) pairs.  This yields a novel subset selection method based on an order-invariant, yet greedy sampler built around the above neural set functions. Our experiments on synthetic and real data show that FlexSubNet outperforms several baselines.


Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection
Soumen Chakrabarti Indian Institute of Technology Bombay (abir, soumen) iitbbac. ac.
Abir De
Abstract
Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged key tool for data selection and summarization. Many recent approaches to learn submodular functions suffer from limited ex- pressiveness. In this work, we propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions. To fit a latent submodular function from (set, value) observations, FLEXSUBNET applies concave function on modular functions in a recursive manner. We do not draw the concave function from restricted family, but rather learn from data using highly expressive neural network that implements a differentiable quadrature procedure. Such an expressive neural model for concave functions may be of independent interest. Next, we extend this setup to provide a novel characterization of monotone a-submodular functions, recently introduced notion of approximate submodular functions. We then use this characterization to design novel neural model for such functions. Finally, we consider learning submodular set functions under distant supervision in the form of (perimeter-set, novel subset selection method based on an order-invariant, yet greedy sampler built around the above neural set functions. Our experiments on synthetic and real data show that FUBES outperforms several baselines.
righ-value-subeee
pairs. This yields a
1 Introduction
Owing to their strong characterization of diversity and coverage, submodular functions and their extensions, viz., weak and approximate submodular functions, have emerged as powerful machinery in data selection tasks [46, 84, 35, 66, 1, 63, 5, 23, 75]. We propose trainable parameterized families of submodular functions under two supervision regimes. In the first setting, the goal is estimate the submodular function based on (set, value) pairs, where the function outputs the value of an input set. This problem is hard in the worst case for poly(n) value oracle queries [31]. This has applications in auction design where one may like to leam player's 's valuation function based on her bids [6]. In the second setting, the task high-value seth-value-subsed pairs, where sigh-value-subset potentially maximizes the underlying function against all other subsets of perimeter-set. The trained function is expected to extract high-value subsets from freshly-specffied perimeter sets. This scenario has applications in itemset prediction in recommendation [78, 79], data summarization [50, 2, 4, 10, 74], etc.
learn the submodular function under the supervision of (perimeter-set
1.1
Our contributions
Driven by the above motivations, we propose (i) novel family of highly expressive neural models for submodular and o-submodular functions which can be estimated under the supervisions of both (set, value) and (perimeter-set, high-value-subset) pairs; (ii) novel permutation adversarial training method for differentiable subset selection, which efficiently trains submodular and a-submodular functions based on (perimeter-set, high-value-subsel pairs. We provide more details below.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Neural models for submodular functions. We design FLEXSUBNET, a family of flexible neural models for monotone, non- monotone submodular functions and monotone a-submodular functions.
Monotone submodular functions. We model a monotone submodular function using a recursive neural model which outputs concave composed submodular function [27, 76, 52] at every step of recursion. Specifically, it first computes a linear combination of the submodular function computed in the previous step and a modular function and, then applies a concave function to the result to output the next submodular function.
Monotone a-submodulaar function. Our proposed model for submodular function rests the principle that a concave composed submodular function is always submodular. However, to the best of our knowledge, there is no known result for a-submodular function. We address this gap by showing that an a-submodular function can be represented by applying a mapping yp on a positive modular set function, where yp satisfies second-order differential inequality. Subsequently, we provide a neural model representing the universal approximator of yo, which in turn is used for modeling an a-submodular function.
Non-monotone submodular functions. By applying a non-monotone concave function on modular function, we extend our model to non-monotone submodular functions.
Several recent models learn subclasses of submodular functions [53, 77, 79]. Bilmes and Bai [7] present thorough theoretical characterization of the benefits of network depth with fixed concave functions, in a general framework called deep submodular functions (DSF). DSF leaves open all design choices: the number of layers, their widths, the DAG topology, and the choice of concave functions. All-to-all attention has replaced domain- topology design in much of NLP [18]. Set transformers [51] would therefore be natural alternative to compare against DSF, but need more memory and computation. Here we explore the following third, somewhat extreme trade-off: we restrict the topology to single recursive chain, thus providing an effectively plug-and-play model with no topology and minimal hyperparameter choices (mainly the length of the chain). However, compensate with more expressive, trainable concave function that is shared across all nodes of the chain. Our experiments show that our strategy improves ease of training and predictive accuracy beyond both set transformers and various DSF instantiations with fixed concave functions.
Permutation insensitive differentiable subset selection. is common 177, 70, 63] to select a subset from a given dataset by sequentially sampling elements using softmax distribution obtained from the outputs of a set function on various sets of elements. At the time of learning set functions based on (perimeter-set, high-value-subset) pairs, this protocol naturally results in order-sensitivity in the training process for learning set functions. To mitigate this, we propose a novel max-min optimization. Such a formulation sets forth a game between an adversarial permutation generator and the set function learner- - where the former generates the worst-case permutations to induce minimum likelihood of training subsets and the latter keeps maximizing the likelihood function until the estimated parameters become permutation--gnootiic. To this end, we use a neural network [57, 68, 17, 69] as neural surrogate of hard permutations, that expedites the underlying training process and allows us to avoid combinatorial search on large permutation spaces.
Experiments. We first experiment with several submodular set functions and synthetically gener- ated examples, which show that FLEXSUBNET recovers the function more accurately than several baselines. Later experiments with several real datasets on product recommendation reveal that FLEXSUBNET can predict the purchased items more effectively and efficiently than several baselines.
2 Related work
Deep set functions. Recent years have witnessed a surge of interest in deep learning of set functions. Zaheer et al. [86] showed that any set function can be modeled using symmterie aggregator on the feature vectors associated with the underlying set members. Lee et al. [51] proposed a transformer based neural architecture to model set functions. However, their work do not focus on modeling or learning submodular functions in particular. Deep set functions enforce permutation invariance by using symmetric aggregators [86, 65, 64], which have several applications, egg., character counting [51], set anomaly detection [51], graph embedding design [34, 47, 80, 71], etc. However, they often suffer from limited expressiveness as shown by Wagstaff et al. [82]. Some work aims to overcome this limitations by sequence encoder followed by learning permutation invariant network structure [62, 68). However, none of them learns an underlying submodular model in the context of subset selection.
2

---

Learning functions with shape constraints. Our double-quadratur strategy for concavity is in- spired by a series of recent efforts to fit functions with shape constraints suit various learning tasks. Wehenkel and Louppe [83] proposed universal monotone neural networks (UMNN) was a significant early step in learning univariate monotone functions by numerical integration of a non-negative integrand returned by a 'universal" network - this paved the path for universal monotone function modeling. Gupta et al. [33] extended to multidimensional shape constraints for supervised learning tasks, for situations were features complemented or dominated others, or a learnt function y = f(x) should be unimodal. Such constraints could be expressed as linear inequalities, and therefore possible to optimize using projected stochastic gradient descent. Gupta et al. [32] widened the scope further to situations where more general constraints had to be enforced on gradients. In the context of density estimation and variational inference, a popular technique is to transform between simple and complex distributions via invertible and differentiable mappings using normalizing flows [48], where coupling functions can be implemented as monotone networks. Our work provides bridge between shape constraints, universal concavity and differentiable subset selection.
Deep submodular functions (DSF). Early work predominantly modeled a trainable submodular function as a mixture of fixed submodular functions [53, 77J. If training instances do not fit their "basis" of hand-picked submodular functions, limited expressiveness results. In the quest for 'universal" submodular function networks, Bilmes and Bai [7] and Bai et al. [3] undertook a thorough theoretical inquiry into the effect of network structure expressiveness. Specifically, they modeled submodular functions as an aggregate of concave functions of modular functions, computed in a topological order along directed acyclic graph (DAG), driven by the fact that concave function of monotone submodular function is a submodular function [26, 27, 76). But DSF provides no practical prescription for picking the concave functions. Each application of DSF will need extensive search over these design spaces.
Subset selection. Subset selection especially under submodular or approximate submodular profit enjoys an efficient greedy maximization routine which admits an approximation guarantee. Con- sequently, wide variety of set function optimization tasks focus representing the underlying objective as an instance of submodular function. At large, subset selection has a myriad of applica- tions in machine learning. c.g., data summarization [4], feature selection [44], influence maximization in social networks [43, 13, 14, 87]. opinion dynamics [11, 12, 14, 89, 49], efficient learning [20, 45], human assisted learning [16, 15, 60), etc. However, these works do not aim to learn the underlying submodular function from training subsets.
Set prediction. Our work is also related to set prediction. Zhang et al. [90] use encoder-decoder architecture for set prediction. Rezatofighi et al. [67] provide a deep probabilistic model for set prediction. However, they aim to predict an output set rather than the set function.
Differentiable subset selection. Existing trainable subset selection methods [77, 50] often adopt a max- margin optimization approach. However, it requires solving one submodular optimization problem at each epoch. which renders it computationally expensive. On the other hand, Tschi- atschek et al. [79] provide a probabilistic a permutation of subset elements. But then, the trained model becomes sensitive to this specific permutations. Tschiatschek et al. [79] overcome this challenge by presenting several permutations to the learner, which can be inefficient.
model which can generate and be trained on
One sided smoothness. We would like to highlight that our characterization for a-submodular function is a special case of one-sided smoothness (OSS) proposed in [29, 28). However, the significance of these characterizations are different between their and our work. First, they consider y-meta submodular function which is a different generalisation of submodular functions compared to a-submodular functions. Second, the OSS characterization they provide is for the multilinear extension of 7-meta submodular function, whereas we provide the characterization of a-submodular functions itself, which allows direct construction of our neural models.
Sample complexity in the context of learning submodular functions. Goemans et al. [31] pro- vided an algorithm which outputs a function f(S) that approximates an arbitrary monotone sub- modular function f(S) within a factor O log n) using poly(n) queries on f. Their algorithm considers powerful active probe setting where can be queried with arbitrary sets. In contrast, Balcan and Harvey [6] consider more realistic passive setup used in supervised learning scenario, and designed an algorithm which obtains an approximation of (S) within factor O(yn).
3

---

3 Design of FLEXSUBNET
In this section, first present our notations and then propose family of flexible neural network models for monotone and non-monotone submodular functions and a-submodular functions.
3.1 Notation and preliminary results
We denote V 21, [V]} the ground set universal set of elements and S, C V as subsets of V. Each element E V may be associated with a feature vector 2,- Given a set function F(S). The function F is called monotone if F(s S) 2 O whenever S C V and & E VVS; ; F is called a-submodular with 0 F(s () 2 (F (T)) whenever S T and s E ( [35, 88, 21]. As special case, F' is submodular if a = 1 and F is modular if F(s S) F(s T). Here, F(-) is called normalized if Unless otherwise stated,
F: : 2 R. we define the marginal utility F(s| .S) == F(S U (s))
F(Ø) Similarly, real function f RR + R is normalized f(0) we only consider normalized set functions in this paper. We quote a key result often used for neural modeling for submodular functions [27, 76, 52].
Proposition 1. Given the set function F 2 + R. and a real valued function o R - R, (i) the set function ((F()) monotone submodular if monotone submodular and 6 is an increasing concave function; and, (ii) of (F)()) is non-monotone submodular if F is positive modular and á is non-monotone.
3.2 Monotone submodular functions
Overview. Our model for monotone submodular functions consists of a neural network which cascades the underlying functions in a recursive manner for N steps. Specifically, to compute the submodular function F() (-) step n, it first linearly combines the submodular function (-)-))()
computed in the previous step and trainable positive modular function (-) and then, applies monotone concave activation function 6 on it.
Recursive model. We model the submodular function Fa(() as follows:
(() ma (0) (S); (() de bo(AA (AF (S) + (1 A)m, (m) (S)); Fo(S) = ((): (1)
S N, fm (1)) (.)] is sequence of positive modular functions, driven by a neural network with parameter 8. E [0. 1] a tunable or trained parameter. We apply linear layer with positive weights
where the iterations are indexed by 1
the each feature vector z, to compute the value (m) (s). Moreover, de is an increasing concave shall see later, is modeled using neural networks. Under these conditions, one
(n) (.) and then compute mi (n) (S) = E.es mg
of mg
function which, can use Proposition ((i) to easily show that Fo (S) is monotone submodular function (Appendix B).
3.3 Monotone-o-submodulla functions
Our characterization for submodular functions in Eq. (1) are based on Proposition 1(i), which implies that concave composed submodular function is submodular. However, to the best of our knowledge, similar characterization of a-submodular functions is lacking in the literature. To address this gap, we first introduce a novel characterization monotone a-submodular functions and then use it to design recursive model for such functions.
Novel characterization of a-submodular function. In the following, we show how we can charac- terize an a-submodular function using differential inequality (proven in Appendix B).
Theorem 2. Given the function vp I R+ and modular function : V [0, the set function F(S) = s0 (.Es m(s)) is monotone a-submodular for (S] & k, if (f(x)) is increasing in x and p()) dz < } log de(x)
dr
The above theorem also implies that given a = 1, then F(S) = >(E m(s) is monotone submodular (xx)) concave in æ, which reduces to particular case of Proposition 1(i). Once we design F(S) by applying &p a modular function, our next goal is to design more expressive and flexible modeling recursive manner similar to Eq. (1). To this end, we extend Proposition the case for a-submodular functions.

---

Proposition 3. Given a monotone a-submodular function F(.), ((F(S)) is monotone a-submodular, (() is an increasing concave function. Here, a remains the same for F and ((F(-)).
Note that, when F(S) is submodular, i..,, = 1, the above result reduces to Proposition 1 in the context of concave composed modular functions.
Recursive model. Similar to Eq. (1) for submodular functions, our model for a-submodular functions is also driven by an recursive model which maintains a-submodular function and updates its value recursively for N iterations. However, in contrast to FLEXSUBNET, where the underlying submodular function is initialized with a positive modular function, initialize the corresponding
o-submodular function (5) with po(ma) (0) (S)). where oo is a trainable function satisfying the conditions of Theorem 2. Then recursively apply trainable monotone concave function (S) for n E [N] to build a flexible model for a-submodular function. Formally, we have:
F ( (0) (8)); (S) = 0e (XF(m-1((S)
A)mp") (5)) Fo(S) (S):
with À E [0, 1]. Here, mg. Pe and da are realized using neural networks parameterized by 0. Then, using Proposition 3 and Theorem 2, we can show that (a(S) is a-submodular in S (proven in Proposition 6 in Appendix B).
3.4 Non-monotone submodular functions
In contrast to monotone set functions, non monotone submodular functions can be built by applying concave function on top of only one modular function rather than submodular function (Proposition (i) vs. (ii)). To this end, model non-monotone submodular function Fa as follows:
(S) = the (m))
(3)
where m-(-) is positive modular function but (-)()) can be non-monotone concave function. Both and thg are trainable functions realized using neural networks parameterized by 0. One can use Proposition (ii) show that Fe (S) is non-monotone submodular function.
3.5 Neural parameterization of ma, do, v/a, PPa
We complete the neural parameterization introduced in Sections 3.2-3.4. Each model has two types of component functions: (i) the modular set function mø; and, (ii) the concave functions du (Eq, (1) and (2)) and tha (Eq. (3)) and the non-concave function ye (Eq. (2)). While modeling my is simple and straightforward, designing neural models for the other components, i.e., Φe, dy and pe is non- trivial. As mentioned before, because we cannot rely the structural complexity of our 'network' (which is a simple linear recursion) or a judiciously pre-selected library concave functions [7], we need invest
capacity in the concave function, effectively making it universal.
Monotone submodular function. Our model for monotone submodular function deseribed in Eq. (1) consists of two neural components: the sequence of modular functions {mg (n)) and di.
Parameterization of mg. We model the modular function mg
2V R+ in Eq. (1) as
(m) (S) = E.es 0 2s, where z, is the feature vector for each element E S and both f, 2, are non-negative.
Parameterization of óu- Recall that de is an increasing concave function. We model it using the fact that differentiable function is coneave if its second derivative is negative. We focus capturing the second derivative of the underlying function using a complex neural network of arbitrary capacity, providing negative output. Hence, we use positive neural network he to model the second derivative
d²)o(() -ho(x) S dx
Now, since Φo is increasing, we have:
dō dx
b=oc
he(b) db > = Φ0(x)
hb(b) db da.
(5)
Jaz0
b=o
Here, (-) is normalized, i.e., (0) = 0, which ensures that (F(")) in Eq. (1) are also normalized.
An offset in Eq. (5) allows nonzero initial value of (g(-), if required. Note that monotonicity and
5

---

concavity of Φgg can be achieved by the restricting positivity of hig Such constraint can be ensured by setting he(-) R (-)), where A. (-) is any complex neural network. Hence, db represents class of universal approximators of normalized increasing concave functions, if A (.) is an universal approximator of continuous functions [36]. For a monotone submodular function of the form of concave composed modular function, we have the following result (Proven in Appendix B).
Proposition Given an universal set V, constant c > and a submodular function F(S) = o(E m(zz)) where 2s RR, S V, 0 S m(z) oc for all z E R Then there exists two fully connected neural networks ma, and he, of width d + 4 and 5 respectively, each with ReLU
activation function, such that the following conditions hold:
E= mo, (z.) b=zo
F(S)
h62 db.
Se ASCV
(6)
a==
Monotone a-submodular model. An a-submodular model described in Eq. (2) has three trainable
components: (i) the sequence of modular functions (m (.)) (ii) the concave function (-) and (iii) (-). For the first two components, reuse the parameterizations used for monotone submodular functions. In the following, we describe our proposed neural parameterization of ppa
Parameterization of (po(-). From Theorem 2, we note that (-)(-) is increasing and satisfies d'va(a)) dx²
k(a) deo(a)
where, k(a) & log (1/a). It implies that dir
=x(()) d² (o x(aa)e =m(a) (x) I = dæ
(c-
=x((() dpp(z)
S
(7)
dr²
dæ
dæ
Driven by the last inequality, we have
e e=zx(a) dxp(x)
go(b) db = po(x) / car(a)
b=
(b( db
(8)
dr
a=0
Parameterizing non-monotone submodular model. As suggested by Eq. (3), model for non- monotone submodular function contains non-monotone concave function the and a modular function
mg. We model me using the same parameterization used for the monotone set functions. We parameterize the the as follows.
Parameterization of thg. Modeling a generic (possibly non- monotone) submodular function requires a general form of concave function the which is not necessarily increasing. The trick is to design (-(()) in such a way that its second derivative is negative everywhere, whereas its first derivative can have any sign. For x E [0, Fmax) we have:
b=oc
vo(x))
hbbb) db
go (b) db
b=a
where ho. Go 2 O. Moreover, assume that Jo (b) db and Ja (b) db are convergent. We use Tmax in the upper limit of the second integral ensure that the is normalized, i.e. (0) Next, we compute the first derivative of (o( as:
dxb((=)
b=00
he (b) db
go (b) db,
(10)
dx b=x
b=
which can have any sign, since both integrals are positive, Here, the second derivative of the becomes
d² ())))())
hx((x) go (x x) < 0
(11)
dx²
which implies that the is concave. Similar to he(-), we can model ge (.) = ReLU(Ag(-)). Such representation makes (.)()) universal approximator of normalized concave functions. As suggested
by Eq. (3), the takes mS) as input. Therefore, in practice, we set Tmax max (S))
3.6 Parameter estimation from (set, value) pairs
In this section, our goal is to learn 0 from a set of pairs {(S, vi) | E [4]}, such that ys ~ Fo...). Hence, our task is solve the following optimization problem: ming Every (y: (S,))2
(12)
In the following, discuss methods to solve this problem.

---

Backpropagation through double integral. Each of our proposed set function models consists of one or more double integrals. Thus computation of the gradients of the loss function in Eq. (12) re- quires gradients of these integrals. To compute them, we leverage the methods proposed by Wehenkel and Louppe [83]. which specifically provide forward and backward procedures for neural networks involving integration. Specifically, we use the Clenshaw-Cure
(CC) quadrature or Trapezoidal Rule for numerical computation of (-) and (-) (.). On the other hand, we compute the gradients Ve db and Va (.) by leveraging Leibniz integral rule [24]. In practice, we replace the upper limit (6 oo) of the inner integral in Eqs. (5), (8) and (9) with bmxx = Tmax during training.
Decoupling into independent integrals. The aforementioned end-to-ens training can be challenging practice, since the gradients are also integrals which can make loss convergence elusive. Moreover, it is also inefficient, since for each step of CC quadrature of the outer integral, we need to perform numerical integration the entire inner integral. To tackle this limitation, we decouple the underlying double integral into two single integrals, parameterized using two neural networks.
Monotone submodular functions. During training our monotone submodular function model in Eq. (I), we model dy in Eq. (5) as:
Φ0 (z) = --" %)(a) da, {xx)= hs(a) da
(13)
In contrast to end-to-end training of where Φo was realized only via neural network of he, here we two decoupled networks, i.e., 6 and hg. Then, we learn A and 33 by minimizing the regularized sum of squared error, i.e.
min Σ Σ 8,8
(())(
- S Somiss he(a) da)² 2 + (ys Fo(
(14)
KE[T MEIN
Here, (S) = A (F))= +1 (1-)mm, is the input to de in the recursion (1). Recall that N is the number of steps the recursion. Since the monotone, need d'g 2 0 which is ensured by %% (x) ReLU(A (x)). In principle, we would like to have (x) = _ ha(a) da for all æ E IR. In practice, we approximate this by penalizing the regularizer values in the domain of interest- values which are fed as input to dg.
While there are potential hazards such approximation, in experiments, the benefits out- weighed the risks. The above parameterization involves only single integrals. The use of an auxiliary network h2 allows more flexibility, leading to improved robustness during training optimization. The above minimization task achieves approximate concavity of & via training, whereas backpropagat- ing through double integrals enforces concavity by design. Appendix C extends this method for a-submodular and non-monotone submodular functions.
4
Differentiable subset selection
In Section 3.6, we tackled the problem of learning Fa from (set, value) pairs. this section, we consider learning Fg from given set of (perimeter-set, high-value-subset) pair instances.
4.1 Learning P/ from (perimeter-set, high-valuc-subset)
Let us assume that the training set consists of ((V,S) pairs, where V is some arbitrary subset of the universe of element, and S C V is a high-value subset of V. Given set function model Fe. our goal is to estimate 0 so that, across all possible cardinality constrained subsets in S' C with |S"| SS), (-).) attains its maximum value at S. Formally, we wish to estimate 0 so that, for all possible (V,S) E Ud we have:
S argmax Fo(S"), subject to S = -S]-
(15)
4.2 Probabilistic greedy model
The problems of maximizing both monotone submodular and monotone a-submodular functions rely on a greedy heuristic [59]. sequentially chooses elements maximizing the marginal gain and hence, cannot directly support backpropagation. Tschiatschek et al. [79] tackle this challenge with probabilistic model which greedily samples elements from softmax distribution with the marginal gains input. Having chosen the first j elements of high-value-subsee from perimeter-set V, it
7

---

draws the (j + 1)th element from the remaining candidates in V with probability proportional to the marginal utility of the candidate. If the elements of S under permutation π are written as ι (S); for
j E [[S]]] then the probability of selecting the elements of the set S in the sequence ग (SS) is given by
|5|-1
exp(TFo(7(S))) | ((S)ss)
(ro(
II j=0
(16)
Σ E (xp(T/ (5)
Here, Fo is the underlying submodular function, r is a temperature parameter and So = 0.
Bottleneck in estimating 0. Note that, the above model (16) generates the elements in sequential
manner and is sensitive to т. Tschiatschek al. [79] attempt to remove this sensitivity by maximizing
the sum of probability (16) over all possible ..
e*
argmax
Σ log Σ Pr Pro(T(() (V,S) (ETT(S
(17)
However, enumerating all such permutations for even medium-sized subset is expensive both terms of time and space. They attempt to tackle this problem by approximating the mode and the mean of Pr(+) over the permutation space I|. But, it still require searching over the entire permutation space, which extremely time consuming.
4.3 Proposed approach
Here, we describe our proposed method of permutation adversarial parameter estimation that avoids enumerating all possible permutations of the subset elements, while ensuring that the learned parame- ter 0 remains permutation invariant.
Max-min optimization problem. We first set up max-min game between a permutation generator and the maximum likelihood estimator (MLE) of 0, similar to other applications [68, 62). Here, for each subset S, the permutation generator produces adversarial permutation [[s) which induces a low value of the underlying likelihood. On the other hand, MLE learns 0 in the face of these adversarial permutations. Hence, we have the following optimization problem:
max min Evv.seeu log Pr (TT((()))))) (V) 0 SEll
(18)
Differentiable surrogate for permutations. Solving the inner minimization in (18) requires search- ing for π over 1|s)) which appears to confer no benefit beyond (17). To sidestep this limitation, we relax the inner optimization problem by using doubly stochastic matrix P PE? Pist as an approxima- tion for the corresponding permutation æ. Suppose Zg = [zs]ses is the feature matrix where each row corresponds to an element of S. Then Zx(s) F PZz. Thus, (r)( V) can be evaluated by iterating down the rows of PZg and, therefore, written in the form Pr (P, (P,S). Thus, we get a continuous approximation to (18): max min E(vi)eeu log oro è PEP
(19)
so that we can learn by continuous optimization. We generate the soft permutation matrices P using Gumbel-Sinkhorn network [57]. Given subset S, it takes seed matrix Bg as input and generates ps in a recursive manner:
p0_ exp( Bs/1); p === (D, (D.((ttt)))) (p(t-1))
(20)
Here, t is temperature parameter; and, DD and Dd, provide column-wise and row-wise normalization. Thanks these two operations, pł tends to doubly stochastic matrix for sufficiently large Denoting p = lim +00 Pk, one can show [57] that
p arrgmax TT(PTT Bs) ' P P(i,j) log P(i.j) PEP|a)
1.j
where the temperature controls the 'hardness' of the "soft permutation" P. Ast P tends to be a hard permutation matrix [9]. The above procedure demands different seeds Bs across different pairs of (V.S)= E U, which makes the training computationally expensive in terms of both time and space. Therefore, we model Bs by feeding the feature matrix Zs into additional neural network Gn which shared across different (V,S) pairs. Then the optimization (19) reduces to maxę min, E(v log Pra (w, S), with w taking the place of P.
8

---

Log
LogDet
FL
Ocale-o.1
LogxSqq
LogxLogbet
Gculs-D.s 0.5
FLEXSUBNET
0,015
0.000
0.013
0.000
0.022
0.000
0.004 0.000
0,032 0.000
0,025 0.000
0.068 0.001
Set-rransformer
0.060 + 0.001
0.029 + 0,000
0.063
0.001
0.014 + 0.000
0.037 + 0.900
0.051
0.001
0.121 + 0.002
Decp-ect
0.002
0.000
0.179
0.003
0.058
0.079 0.000
0.070
0.001
DSF
0,258 0.003
0.684
0.007
0 0.003
0.778 8: 0.009
0.240 1: 0.003
0.274
0.003
0.970 1: 0.010
SubMix
0.148 + 0.002
0.063 0.001
0.172 0.002
0.018 0.000
0.158 + 0.002
0:154 0.002
1.722 0.015
Table Performance measured terms of RMSE on synthetically generated examples using several
set functions. Number in bold font (underline) indicate the best (second best) performers.
5
Experiments
In this section, we first evaluate FLEXSUBNET using a variety of synthesized set functions and show that it is able to fit them under the supervision of (set, value) pairs more accurately than the state-of tfate-of-the-art methods. Next, we use datasets gathered from Amazon baby registry [30] to show that FLEXSUBNET can learn to select data from (perimeter-set, sethh--alu-ssbseee pairs more effectively than several baselines. Our code is in htt:::/iinuull.ooo/leexxxs///
5.1 Training by (set, value) pairs
Dataset generation. We generate |V|=10* samples, where we draw the feature vector 2, for each sample s uniformly at random, i.e., z, Z.iff 1]
with d-10. Then, we generate subsets S of dif- ferent sizes by randomly gathering elements from the set V. Finally, we compute the values of F(S) for different submodular functions F. Specifically, we consider seven planted set functions: (i) Log: E.es 2 2,2g) ) [73, 8), (iii) Facility lo- cation (FL):F(S) = ((15))=Evv max x 2=//([=,, / II) [58. 25, 19, 61], (iv) Monotone graph cut (Geut,=0.1)>
F(S)= (0 1 2,), (ii) LogDet: F(S) = log det(T +
general, Gcut, is computed using F(S) == EnEV,es = z, z, Ew Zyj Z measures the weighted cut across (S. ())) when the weight of the edge (u.v) com- puted as z]] 2y [37, 72, 39, 40, 41]. Here, a trades off between diversity and representa- tion. We set σ = 0.1. Note that Gcut, is monotone (non-monotone) submodular when <<0.. (0>..5). (v) LogxSqrt: F(S)- = [log(E.es 1 1". 1/2 (vi) LogXLo F(S) = [log(E Exes ==]]]] [log det(I + E.es 2xz,)) and (vii) Non monotone graph cut (Gcut,=o.s): s): It is the graph cut function in (iv) with
0.8. Among above set functions, (i)- (iv) are monotone submodular functions, (v)- are monotone a-submodular functions and (vii) is a
non-monotone submodular function. We set the number of steps in the recursions (I), (2) as N 2.
Evaluation protocol. We sample V|=10000 (set, value) instances as described above and split them into train, dev and test folds of equal size. We present the train and dev folds to the set function model and measure the performance in terms of RMSE on test fold instances. In the first four datasets, we used our monotone submodular model described in Eq. (1); in case of Logx and Log Legte,,,, we used our a-submodularr model described in Eq. (2); and, for Geuta- we used our non-monotone submodular model in Eq. (3). For a-submodular model, we tuned a using cross validation. Appendix provides hyperparameter tuning details for all methods.
Baselines. We compare FLEXSUBNET against four state-of-ther art models, viz., Set-transformer [51]. 1]]. Deep-set [86], deep submodular function (DSF) [7] and mixture submodular function (SubMix) [77]. In principle, set transformer shows high expressivity due to its ability to effectively incorporate the interaction between elements. No other method including FLEXSUBNET is able to incorporate such interaction. Thus, given sufficient network depth and width, Sea-transformer should show higher accuracy than any other method. However, Set-transformer consumes significantly higher GPU memory even with a small number of parameters. Therefore, to have a fair comparison with the rest non-interaction methods, we kept the parameters of Set-transformer to be low enough so that it consumes same amount of GPU memory, as with other non-interaction based methods.
Results. We compare the performance of FLEXSUBNET against the above four basclines in terms of RMSE on the test fold. Table summarizes the results. We make the following observations. (1) FLEXSUBNET outperforms the baselines by a substantial margin across all datasets. (2) Even with reduced number of parameters, Set-transformer outperforms all the other baselines. Set-transformer allows explicit interactions between set elements via all-to-all attention layers. As a result, outperforms all other baselines even without explicitly using the knowledge of submodularity in its network architecture. Note that, like Deep-set, FLEXSUBNET does not directly model any interaction between the elements. However, it explicitly models submodularity or a-submodularity in the network architecture, which helps it outperform the baselines. We observe improvement of the performance of frtsfraanfor,rr, if we allow more number of parameters (and higher GPU memory).

---

Mean Jaccard Coefficient (MJC)
Mean NICG
FLEXSUBNET
DSF
SubMix
FL
DPP
DisMin
FLEXSUBNET
DSF
SubMix
FL
DPP
DisMin
Gear
0.101
0.099
0,028
0.019
0.014
0.013
0.539
0.538
0.449
0.433
0.425
0.426
Bath
0.038
0.427
0.422
Health
0.153
0.142
0,022
0.084
0.011
0.015
0.597
0.549
0.449
0.540
0.425
0.435
Disper
0.134
0.115
0,023
0.018 0.013
0.012
0.562
0.546
0.447
0.40
0.435
0.435
Toys
0.157
0.150
0.025
0.064 0.029
0.029
0,577
0.446
0.722
0.448
0.449
Bedding
0.20.3
0,191
0,028
0.015 0.043
0.047
0.643
0.623
0.437
0438
0.456
0.461
Feeding
0,100
0.026
0.023
0.550
0.459
0.454
0,452
Apparel 0.101
0.093
0.096
0.022
0.016
0.016
0.558
0,550
0.459
0.452
0.446
0.444
Media 0.135
0.130
0.029
0.055 0.029
0.025
0.578
0,578
0.474
0.470
0.461
0.461
Table 2: Prediction of subsets in product recommendation task. Numbers in bold (underline) indicate
best (second best) performer.
(3) While, in principle, DSF function family contains that of FLEXSUBNET, standard multilayer instantations of DSF with fixed concave functions cannot learn well from (set, value) training.
5.2 Training by (perimeter-set, high-value-subset)
Datasets. We use the Amazon baby registry dataset [30] which contains 17 product categories. Among them, we only consider those categories where [V] > 50, where V is the total number of items in the universal set. These categories are: (i) Gear, (ii) Bath, (iii) Health, (iv) Diaper, (v) Toys, (vi) Bedding, (vii) Feeding, (viii) Apparel and (ix) Media. They are also summarized in Appendix F.
Evaluation protocol. Each dataset contains universal set V and a set of subsets S = {S). Each item 8 characterized by a short textual description such as "bath: Skip Hop Moby Bathtub Elbow Rest, Blue Bathtub Side Bumpers: Baby". From this text, we compute using BERT [18]. We split S into equal- sizel training (Sugin, dev (Savv) and test (Swat folds. We disclose the training and dev sets to the submodular function models, which trained using our proposed permutation adversarial approach (Section 4). Then the trained model is used to sample item sequence S' with prefix S'-p- (S1,.... 8K) }. Here, 8; is the item selected at the 7th step of the greedy algorithm. We assess the quality of the sampled sequence using two metrics.
Mean Jaccard coefficient (MJC). Given set T in the test set, we first measure the overlap between T and the first [T] elements of S' using Jaccard coefficient, ie., JC(T) = | 0TI/1 UT| and then average over all subsets in the test set, i.e., T E Siest to compute mean Jaccard coefficient [38].
Mean NDCG@ 10. The greedy sampler outputs item sequence S' For each T E &Seat: we compute the NDCG given by the order of first elements of S', where E S is assigned a gold relevance label 1, if i E T and 0, otherwise. Finally, we average over all test subsets to compute Mean NDCG@ @ 10.
Our method vs. baselines. We compare the subset selection ability of FLEXSUBNET against several baselines which include two trainable submodular models: (i) Deep submodular function (DSF) and (ii) Mixture of submodular functions (SubMix) described in Section 5.1; two popular non-trainable submodular functions which include (iii) Facility location (FL) [58, 25], (iv) Determinantal point process (DPP) [8]; and, a non-submodular function (v) Disparity Min (DisMin) which often used in data summarization [10]. Here, we use the monotone submodular model of FLEXSUBNET. Appendix F contains more details about the baselines. We did not consider general purpose set functions, e.g.. Set-transformer, Deep-set, etc., because they cannot be maximized using greedy-like algorithms and therefore, we cannot apply our proposed method in Section 4.
Results. Table 2 provides a comparative analysis across all candidate set functions, which shows that: (i) NET outperforms all the baselines across all the datasets; (ii) DSF is the second best performer across all datasets; and, (iii) the performance of non-trainable set functions is poor, as they are not trained to mimic the set selection process.
Conclusion
We introduced FLEXSUBNET: family of submodular functions, represented by neural networks that implement quadrature-based numerical integration, and supports end-to-end backpropagation through these integration operators. We designed a permutation adversarial subset selection method, which ensures that the estimated parameters are independent of greedy item selection order. On both synthetic and real datasets, FLEXSUBNET improves upon recent competitive formulations. Our work opens up several avenues of future work. One can extend our work for 7-weakly submodular functions [22]. Another extension of our work is to leverage other connections to convexity, egg., the Lovasz extension [54, 1] similar to Karalias et al. [42].
10

---

References
[1] Francis Bach. Learning with submodular functions: A convex optimization perspective. arXiv 2011.
preprint
[2] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization the fly. In P Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 000 071-680, 2014.
[3] Wenruo Bai, William S Noble, and Jeff A Bilmes. Submodular maximization via gradient ascent: the case of deep submodular functions. Advances in neural information processing systems, 2018:7989, 2018.
[4] Ramakrishna Bairi, Rishabh Iyer, Ganesh Ramakrishnan, and Jeff Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures. In ACL, pages 553-563, 2015.
[5] Maria-Florina Balcan and Nicholas JA Harvey. Submodular functions: Learnability, structure, and optimization. arXiv preprint arXiv: 259, 2010.
[6] Maria-Florina Balcan and Nicholas JA Harvey. Learning submodular functions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 2011.
[7] Jeffrey Bilmes and Wenruo Bai. Deep submodular functions. arXiv preprint 17oxiiv:1010.08000 2017.
[8] Alexei Borodin. Determinantal point processes. arXiv preprint arXiv:0911.1153. 2009.
[9] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport, Advances in neural information processing systems, 26:2292-2300, 2013.
[10] Anirban Dasgupta, Ravi Kumar, and Sujith Ravi. Summarization through submodularity and dispersion. In Proceedings of the 51 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 1014-1022, 2013.
[11] Abir De, Isabel Valera, Niloy Ganguly, Sourangshu Bhattacharya, and Manuel Gomez Ro- driguez. Learning and forecasting opinion dynamics in social networks. Advances in neural information processing systems, 29, 2016.
[12] Abir De, Sourangshu Bhattacharya, and Niloy Ganguly. Demarcating endogenous and exoge- nous opinion diffusion process on social networks. In Proceedings of the 2018 World Wide Web Conference, pages 549-558, 2018.
[13] Abir De, Sourangshu Bhattacharya, and Niloy Ganguly. Shaping opinion dynamics in social networks. In Proceedings of the 17th international conference on autonomous agents and multiagent systems, pages 1336-1344 2018
[14] Abir De, Sourangshu Bhattacharya, Parantapa Bhattacharya, Niloy Ganguly, and Soumen Chakrabarti. Learning linear influence models social networks from transient opinion dynamics, ACM Transactions on the Web (TWEB), 13(3):1-33, 2019.
2019.
[15) Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez Regression under human assistance. AAAI, 2020.
[16] Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez-Rodriguez. Classification under human assistance. AAAI, 2021.
[17] Indradyumna Roy Soumen Chakrabarti Abir De. Maximum common subgraph guided graph retrieval: Late and early interaction networks.
[18] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
[19] Donglei Du, Ruixing Lu, and Dachuan Xu. primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica, 63(1):191-200, 2012.
[20] S Durga, Rishabh Iyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for regression with controlled generalization error. International Conference on Machine Learning, pages 9202-9212. PMLR, 2021.

---

[21] Marwa El Halabi and Stefanie Jegelka. Optimal approximation for unconstrained non- submodular minimization. In International Conference on Machine Learning, pages 3961-3972. PMLR, 2020.
[22] Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. arXiv preprint arXiv: 2016.
[23] Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45(3): 2016.
[24] Harley Flanders. Differentiation under the integral sign. The American Mathematical Monthly, 80(6):615-63) 627, 1973.
[25] Alan M Frieze. A cost function property for plant location problems. Mathematical Program- ming, 7(1):245-2444 1974.
[26] Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
[27] Satoru Fujishige and Satoru Iwata. Minimizing a submodular function arising from a concave function. Discrete applied mathematics, 92(2-3):211-215 1999.
[28] Mehrdad Ghadiri, Richard Santiago, and Bruce Shepherd. A parameterized family of meta- submodular functions. arXiv preprint urXiv:2006. 13754, 2020.
[29] Mehrdad Ghadiri, Richard Santiago, and Bruce Shepherd. Beyond submodular maximization via one-sided smoothness. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1025- SIAM, 2021.
[30] Jennifer A Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar. for learning determinantal point processes. Advances in Neural Information Processing Systems, 27:31 97:3149-3157, 2014.
[31] Michel X Goemans, Nicholas JA Harvey, Satoru Twata, and Vahab Mirrokni. Approximat- ing submodular functions everywhere. Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithmss, pages 535-544. SIAM, 2009.
[32] Akhil Gupta, Lavanya Marla, Ruoyu Sun, Naman Shukla, and Arinbjöm Kolbeinsson. Pen- der: Incorporating shape constraints via penalized derivatives. In AAAI, 2021. URL
GuptaA,pdf.
[33] Maya R. Gupta, Erez Louidor Ilan, Olexander Mangylov, Nobuyuki Morioka, Taman Narayan, and Sen Zhao. Multidimensional shape constraints. In ICMI,, 2020. URL httpr/ceeeding....rreeeesee
/9/gupta200//upta2Db.....
[34] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[35] Abolfazl Hashemi, Mahsa Ghasemi, Haris Vikalo, and Ufuk Topcu. Submodular observation selection and information gathering for quadratic models. arXiv preprint 2019.
09919,
[36] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366. 1989.
[37] Rishabh lyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combina- torial information measures with applications in machine learning. Algorithmic Learning Theory, pages 722-754. PMLR, 2021.
[38] Paul Jaccard. 'E comparative study of floral distribution in a portion of the alps and jura. Bull Soc Vaudoise Sci Nat, 37:547-579, 1901.
[39] Stefanie Jegelka and Jeff Bilmes. Notes graph cuts with submodular edge weights. In NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity Polyhedra (DISCML), pages 1-6, 2009.
[40] Stefanie Jegelka and Jeff Bilmes. Cooperative cuts: Graph cuts with submodular edge weights. 2010.
[41] Stefanie Jegelka and Jeff Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR 20/1, pages 1897-1904. IEEE, 2011.
[42] Nikolaos Karalias, Joshua David Robinson, Andreas Loukas, and Stefanie Jegelka. Neural extensions: Training neural networks with set functions. 2021.
12

---

[43] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[44] Rajiv Khanna, Ethan Elenberg, Alexandros G Dimakis, Sahand Negahban, and Jaydeep Ghosh. Scalable greedy feature selection via weak submodularity. arXiv preprint (70300227 2017.
[45] Krishnateja Killamsetty, Durga Sivasubramanian, Baharan Mirzasoleiman, Ganesh Ramakrish- nan, Abir De, and Rishabh Iyer. Grad-match: A gradient matching based data subset selection for efficient learning, arXiv preprint arXiv:2103.0011 2021.
[46] Krishnateja Killamsetty, Durga Subramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: generalization based data selection framework for efficient and robust learning. In AAAI, 2021.
[47] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[48] Ivan Kobyzev, Simon Prince, and Marcus A. Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions Pattern Analysis and Machine Intelligence, 43:3964-399 3979, 2021. URL http://arxxvv.org/pfff/ hwtpp/////..0..00 1908009277.
[49] Paramita Koley, Avirup Saha, Sourangshu Bhattacharya, Niloy Ganguly, and Abir De. Demar- cating endogenous and exogenous opinion dynamics: An experimental design approach. arXiv preprint 2rxiv:2102.05955 2021.
[50] Suraj Kothawade, Jiten Girdhar, Chandrashckhar Lavania, and Rishabh Iyer. Deep submodular networks for extractive data summarization. arXiv preprint arXiv:2010008599 2020.
[51] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-base permutation-invant -nnvrriinn neural networks. In ICML, 2019.
[52] Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies, pages 510-520, 2011.
[53] Hui Lin and Jeff A Bilmes. Learning mixtures of submodular shells with application to document summarization. arXiv preprint arXiv: 121.::210 100.4871, 2012.
[54] László Lovász. Submodular functions and convexity. In Mathematical programming the state of the art, pages 235-257, Springer, 1983.
[55] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems,
30, 2017.
[56] Piyushi Manupriya, Tarun Ram Menta, Sakethanath N. Jagarlapudi, and Vineeth N. Bala- subramanian. Improving attribution methods by learning submodular functions. In Gus- tau Camps-Valls Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceed- ings of Machine Learning Research, pages 2173-2190. PMLR, 28-30 Mar 2022. URL httpss//procceedings. wttp:/inn........ssiiiiise 1
[57] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with gumbel-sinkhen networks. arXiv preprint arXiv: 086650 2018.
[58] Pitu Mirchandani and Richard L Francis. Discrete location theory. 1990.
[59] George L Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions i. Mathematical programming, (4(1):265-44 1978.
[60] Nastaran Okati, Abir De, and Manuel Rodriguez. Differentiable learning under triage. Advances in Neural Information Processing Systems, 34:9140-9155 2021.
[61] Camilo Ortiz-Astorquiza Ivan Contreras, and Gilbert Laporte. Multi-level facility location as the maximization of submodular set function. European Journal of Operational Research, 24133):0113-1166 2015.
13

---

[62] Chirag Pabbaraju and Prateek Jain. Learning functions over sets via permutation adversarial networks. arXiv preprint arXiv:1907.05638, 2019. URL https://arxiv.orrgppaa 0ttp//9970.0555 056338.
[63] Thomas Powers, Rasool Fakoor, Siamak Shakeri, Abhinav Sethy, Amanjit Kainth, Abdel- rahman Mohamed, and Ruhi Sarikaya. Differentiable greedy networks. arXiv preprint arXiv: 12464, 2018.
[64] Charles R Qi. Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[65] Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Deep learning with sets and point clouds. arXiv preprint arXiv:1611.04330
2016.
[66] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference on Machine Learning, pages 4334 4343, 2018.
[67] Hamid Rezatofighi, Roman Kaskman, Farbod T Motlagh, Qinfeng Shi, Anton Milan, Daniel Cremers, Laura Leal-Taixé, and Ian Reid. Learn predict sets using feed-forward neural networks. arXiv preprint arXiv:2001. 1845, 2020.
[68] Indradyumna Roy, Abir De, and Soumen Chakrabarti. Adversarial permutation guided node representations for link prediction. In arXiv:2012.08974, 2021.
[69] Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Inter- pretable neural subgraph matching for graph retrieval. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9115-8123, 2022.
[70] Shinsaku Sakaue. Differentiable greedy algorithm for monotone submodular maximization: Guarantees, gradient estimators, and applications. In International Conference on Artificial Intelligence and Statistics, pages 28 18-36. PMLR, 2021.
[71] Bidisha Samanta, Abir De, Gourhari Jana, Vicenç Gómez, Pratim Kumar Chattaraj, Niloy Ganguly, and Manuel Gomez-Rodriguez. Nevae: A deep generative model for molecular graphs. Journal of machine learning research. 2020 Apr; 21 (114): 1-33, 2020.
[72] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science Business Media, 2003.
[73] Manohar Shamaiah, Siddhartha Banerjee, and Haris Vikalo. Greedy sensor selection: Leverag- ing submodularity. In 49th IEEE conference on decision and control (CDC), pages 2572-2577.
IEEE, 2010.
[74] Adish Singla, Sebastian Tschiatschek, and Andreas Krause. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In AAAI, 2016.
[75] Ruben Sipos, Pannaga Shivaswamy, and Thorsten Joachims. Large-margin learning of submod- ular summarization models. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224-233, 2012.
[76] Peter Stobbe and Andreas Krause. Efficient minimization of decomposable submodular func- tions. arXiv preprint arXiv: 1010.551, 2010.
[77] Sebastian Tschiatschek, Rishabh Iyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. In Advances in neural information processing systems, pages 1413-1421, 2014.
[78] Sebastian Tschiatschek, Josip Djolonga, and Andreas Krause. Learning probabilistic submodular diversity models via noise contrastive estimation. In Artificial Intelligence and Statistics, pages 770-779. PMLR, 2016.
[79] Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause. Differentiable submodular maxi- mization. arXiv preprint
2018.
[80] Tathagat Verma, Abir De. Yateesh Agrawal, Vishwa Vinay, and Soumen Chakrabarti. Varscene: deep generative model for realistic scene graph synthesis. In International Conference on Machine Learning, pages 22168 2188-22183.2 PMLR, 2022.
[81] Jan Vondrák. Submodularity and curvature: the optimal algorithm.
14

---

[82] Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. On the limitations of representing functions on sets. In Proceedings of the 36th International Conference Machine Learning. 2019.
[83] Antoine Wehenkel and Gilles Louppe. Unconstrained monotonic neural networks. NeurlPS, 2019.
[84] Kai Wei, Rishabh lyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963, 2015.
[85] Jiaqian Yu and Matthew Blaschko. Learning submodular losses with the lovász hinge. In International Conference on Machine Learning, pages 1623-1631. PMLR, 2015.
[86] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. arXiv preprint arXiv:/703.000 14, 2017.
[87] Ali Zarezade, Abir De, Hamid Rabiee, and Manuel Gomez Rodriguez. Cheshire: An online algorithm for activity maximization in social networks. arXiv preprint 1rXii::1708 700..0209, 2017.
[88] Haifeng Zhang and Yevgeniy Vorobeychik. Submodular optimization with routing constraints. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
[89] Ping Zhang, Rishabh Iyer, Ashish Tendulkar, Gaurav Aggarwal, and Abir De. Learning to select exogenous events for marked temporal point process. Advances in Neural Information Processing Systems, 34:347-361, 2021.
[90] Yan Zhang, Jonathon Hare, and Adam Prugel- -ongeltBennet..... Deep set prediction networks. Advances in Neural Information Processing Systems, 2:3212-3222, 2019.
[91] Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, pages 8778 -8788, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix A in supplemental material
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B in supplemental material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] Code is included as part of supplemental material. Further details are in Appendix D and F in supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5, Appendix D and F supplemental material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Table and Appendix in supplemental material.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix F in supplemental material.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
15

---

(b) Did you mention the license of the assets? [Yes] See Appendix F in supplemental material.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Yes, provided code URL.
(d) Did you discuss whether and how consent obtained from people whose data you'le rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A] No such information present the data used in this paper.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "q_UsHTgpwxQ", "reviewer": "Reviewer_z5K8", "summary": "The paper propose a family of neural models for monotone and non-monotone submodular functions and monotone approximately submodular functions, which can be estimated both from (set, value) observations and (perimeter-set, high-value subset) observations. The model proposed for monotone submodular functions consists of recursively applying an increasing concave activation function on a linear combination of the submodular function from the previous step and a positive modular function. This model is extended to a class of monotone approximately submodular functions by replacing the increasing concave activation function by an activation function satisfying a second-order differential inequality (which is stricter than concavity). The model proposed for non-monotone submodular functions consists of the composition of a concave activation function (not necessarily increasing) on only one positive modular function. Unlike prior work which use a fixed concave function, the authors choose to model the concave activation functions using a neural network which involve double integrals and propose methods to train it.  The authors also propose an order-invariant greedy sampling method for learning set functions from (perimeter-set, high-value subset) observations based on a max-min game between an adversarial permutation generator and the set function learner. Finally, they present some experiments showing that their models outperform other baselines in both supervision settings.", "questions": "- For a more fair comparison with the DSF baseline, it would be good to consider few other popular choices for the concave function.\n- How are high-value subsets chosen in the Amazon baby registry dataset?", "limitations": "Authors discuss limitations of their work in Appendix A, but do not discuss potential negative societal impact.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n- Designing a practical method for learning submodular and approximately submodular functions is useful for a number of ML applications.\n- Proposing a neural network model for the concave activation function which can be learned from data is a good alternative to having to choose a fixed one.\n- Paper is well written with clearly presented results\n\nWeaknesses:\n- Unlike some prior work, the proposed models are only shown to be good estimators of monotone submodular function of the form of concave composed modular function, which is too limited.\n- The proposed model for non-monotone submodular functions is too simple to capture complex functions.\n- The empirical comparison with the deep submodular function (DSF) baseline is limited (see questions).\n- Missing related work: \n\n\tBalcan, Maria-Florina, and Nicholas JA Harvey. Submodular functions: Learnability, structure, and optimization. SIAM Journal on Computing 47.3: 703-754, 2018.\n\n\tVitaly Feldman and Jan Vondrak. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45(3):1129–1170, 2016. \n\n\tR. Sipos, P. Shivaswamy, and T. Joachims. Large-margin learning of submodular summarization mod- els. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224–233. Association for Computational Linguistics, 2012.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XE4ysj_CTd", "reviewer": "Reviewer_cuUV", "summary": "The paper considers the problem of learning submodular functions using neural networks. More precisely the paper considers two different settings.\n\n1 - There exists an oracle that given a set $S$, responds with the value of the function $f$ for $S$.\n\n2- There exists an oracle function that given a set $S$, returns $\\argmax_{T\\subseteq S} f(T)$.\n\nThe first setting is known as the value oracle in the literature and the second one can be simulated by demand oracle (put the price of infinity on any item not in set $S$). For the first setting, the goal is to minimize $\\sum_{i \\in [I]} (f(S) - F_\\theta(S))$ over the parameters $\\theta$ of a neural network. The paper proposes a specific class of submodular functions that arise from concave combination of modular functions in a recursive way and a neural network based on this class of functions. They deal with some issues for learning these functions such as permutation invariance in the input sets and dealing with the non-positivity of the second-order derivative. They also show that their approach can be extended to the class of $\\alpha$-submodular functions and non-monotone submodular functions. The experiments also illustrates that on some synthetic data and a real-world dataset (Amazon baby registry dataset), they outperform other neural networks such as transformers, deep submodular functions, and deep sets.", "questions": "- The characterization of \\alpha-submodular functions described in Theorem 2 is very similar to the recently introduced notions of one-sided smoothness and meta-submodularity. Please see [2] and [3]. These notions also consider functions where the second-order derivative is bounded by some factor of the first-order derivative. Please add a discussion about the connections. Is this a special case of one-sided smoothness? I'm asking because the regularization with the size of the set is looser than $1/k$.\n\n- What is exactly the objective function for the second setting with (perimeter-set, high-value-subset) setting. Is it some ordering function? Please add a discussion about this. I don't think it is clear in the paper.\n\nComments:\n\n- I think it is worth mentioning in the paper that learning submodular functions with poly(n) number of value oracle queries is hard in the worst case. Please see [1].\n\n- Moreover, some discussion on the difference of theoretical upper bounds and lower bounds of approximation for the two different setting considered in the paper is useful, i.e., value-oracle setting and demand oracle setting.\n\n- In Line 84, “and” is repeated.\n\nReferences:\n\n[1] Goemans, Michel X., Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. \"Approximating submodular functions everywhere.\" In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pp. 535-544. Society for Industrial and Applied Mathematics, 2009.\n\n[2] Ghadiri, Mehrdad, Richard Santiago, and Bruce Shepherd. \"Beyond submodular maximization via one-sided smoothness.\" In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1006-1025. 2021.\n\n[3] Ghadiri, Mehrdad, Richard Santiago, and Bruce Shepherd. \"A Parameterized Family of Meta-Submodular Functions.\" arXiv preprint arXiv:2006.13754 (2020).\n", "limitations": "The paper does not have any negative societal impact since it considers a fundamental problem.\n", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper considers an interesting and fundamental problem. The paper is mostly written clearly and cleanly, but some discussions regarding the below topics could help understand its position in the literature better. \n\nI think the paper makes a good case regarding its approach, but I'm not sure if some of the empirical comparisons make sense. For example, my understanding is that the deep sets essentially suggest a layer of a neural network that guarantees invariance/equivariance for datasets comprising of sets. This does not give a specific neural network but rather can be used as a component of more complicated networks. I wonder how the suggested method would interact with such a layer to guarantee order invariance. Please let me know if there is an issue that prevents this combination. Another concern is that all of the considered functions are simple concave/submodular functions. I'm wondering how these methods would compare on more extreme examples. For example, one candidate could be the worst-case example mentioned in [1] to prove the lower bound for approximation submodular functions.\n\nMoreover, some discussion on the learnability of the functions could improve the paper. For example, in Proposition 4, it is mentioned that there exists a neural network with a certain width to learn a certain submodular function, but there is no mention of the number of samples needed or the running time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OaDgyY1ujHH", "reviewer": "Reviewer_9tyR", "summary": "This paper proposes new families of submodular (and $\\alpha$ approximate submodular) functions which can be parameterized efficiently by neural networks. Then the authors use this formulation to learn submodular functions given (set, value) examples. Additionally, they propose a new max-min method to learn to sample high-value subsets from a submodular function given (perimeter-set, high-value subset) examples. The inner min objective uses a Gumbel-Sinkhorn network to encourage permutation invariance.", "questions": "- How wide is each FlexSubNet layer? More generally, how many parameters does FlexSubNet have compared to baselines?\n- The hyperparameter configuration looks very similar across most methods, how were these selected? If cross validation, what was the range of values for $N$, $\\alpha$, number of hidden layers, etc.\n- What values of $\\alpha$ do ground truth planted set functions (v) and (vi) have?\n- In Table 2, is N=1 with Decoupling or End-end?\n- When using the Amazon baby registry dataset, how large are the sampled sets and prefixes?", "limitations": "The authors could have commented on the tradeoff between using (set, value) and (perimeter-set, high-value subset) datasets. The latter appears to have a higher risk of introducing bias into the learned model", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n- Novel combination of previous work (Deep Submodular Functions, Gumbel-Sinkhorn NNs, Unconstrained Monotonic NNs) with new insights and techniques. \n- Cites previous related work where appropriate, except that Reference [42] in the Appendix does not appear in main paper\n\n## Quality\n- Several technical contributions: parameterizing (alpha) submodular functions efficiently, max-min formulation of selecting a greedy sequence via adversarial permutation\n- Experimental results look impressive, but I have some concerns with experimental setup/evaluation of baseline methods:\n    - For experiments involving with set transformer, using a batch size less than 66 could have reduced gpu memory consumption\n    - On the Amazon baby registry dataset, can still use other baselines such as set transformer to predict the next element, even if submodularity is not enforced\n    - The paper would be stronger if it evaluated performance in additional ways; for example, training time and sample complexity\n    - Unclear why NDCG is an appropriate metric when it depends on order. The problem is designed to be permutation invariant\n\n## Significance\n- This paper presents interesting, potentially high-impact ideas for an important, relevant problem of learning submodular functions from data.\n- In addition to the 2 planted $\\alpha$-submodular set functions, the paper would be improved if it motivated this family of functions with practical applications\n\n## Clarity\n- This paper is organized well and is generally a pleasure to read\n- While the theoretical details are quite clear, there are many missing details from the experimental evaluation. For example, no details on how the max-min objective is trained. Also it is somewhat unclear how the product recommendation dataset is converted into a (perimeter set, high-value subset) format.\n- Note that some references such as [1] use $1 - \\alpha$ in the definition of approximate submodularity.\n\n\n[1]  Gatmiry and Gomez Rodriguez. Non-submodular Function Maximization subject to a Matroid Constraint, with Applications. https://arxiv.org/abs/1811.07863", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept