Monotone and Separable Set Functions: Characterizations and Neural Models

• URL: http://arxiv.org/abs/2510.23634v1
• Date: Fri, 24 Oct 2025 09:59:07 GMT
• Title: Monotone and Separable Set Functions: Characterizations and Neural Models
• Authors: Soutrik Sarangi, Yonatan Sverdlov, Nadav Dym, Abir De,
• Abstract summary: We call functions satisfying the property Monotone and Separating (MAS) set functions.<n>We show that MAS functions do not exist, but provide a model called our which provably enjoys a relaxed MAS property.<n>We also show that MAS functions can be used to construct universal models that are monotone by construction and can approximate all monotone set functions.
• Score: 30.064497768159068
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Motivated by applications for set containment problems, we consider the following fundamental problem: can we design set-to-vector functions so that the natural partial order on sets is preserved, namely $S\subseteq T \text{ if and only if } F(S)\leq F(T) $. We call functions satisfying this property Monotone and Separating (MAS) set functions. % We establish lower and upper bounds for the vector dimension necessary to obtain MAS functions, as a function of the cardinality of the multisets and the underlying ground set. In the important case of an infinite ground set, we show that MAS functions do not exist, but provide a model called our which provably enjoys a relaxed MAS property we name "weakly MAS" and is stable in the sense of Holder continuity. We also show that MAS functions can be used to construct universal models that are monotone by construction and can approximate all monotone set functions. Experimentally, we consider a variety of set containment tasks. The experiments show the benefit of using our our model, in comparison with standard set models which do not incorporate set containment as an inductive bias. Our code is available in https://github.com/yonatansverdlov/Monotone-Embedding.

Related papers

• On the (Non) Injectivity of Piecewise Linear Janossy Pooling [3.396731589928944]
  We consider the family of k-ary Janossy pooling, which includes many of the most popular multiset models, and prove that no piecewise linear Janossy pooling function can be injective.<n>On the positive side, we show that when restricted to multisets without multiplicities, even simple deep-sets models suffice for injectivity and bi-Lipschitzness.
  arXiv  Detail & Related papers  (2025-05-26T15:53:09Z)
• Universal Representation of Permutation-Invariant Functions on Vectors and Tensors [11.345796608258434]
  A main object of our study is multiset functions -- that is, permutation-invariant functions over inputs of varying sizes. Deep Sets, proposed by citezaheer 2017deep, provides a emphuniversal representation for continuous multiset functions on scalars via a sum-decomposable model. We prove that universal representation is guaranteed for continuous and discontinuous multiset functions though a latent space dimension of $O(ND)$.
  arXiv  Detail & Related papers  (2023-10-20T22:00:59Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSets is the most widely used neural network architecture for set representation. We present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE)
  arXiv  Detail & Related papers  (2023-07-08T16:00:59Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization. We propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions.
  arXiv  Detail & Related papers  (2022-10-20T06:00:45Z)
• Pairwise independent correlation gap [2.0979696058875446]
  We show that for any nonnegative monotone submodular set function defined on $n$ elements, this ratio is upper bounded by $4/3$.<n>This differs from the bound on the correlation gap'' which holds with mutual independence and showcases the fundamental difference between pairwise independence and mutual independence.
  arXiv  Detail & Related papers  (2022-09-18T13:11:44Z)
• Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
  We show that for many standard submodular algorithms one can prove new approximation guarantees that depend on the monotonicity ratio. This leads to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming and image summarization.
  arXiv  Detail & Related papers  (2022-02-07T10:35:40Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Learning Aggregation Functions [78.47770735205134]
  We introduce LAF (Learning Aggregation Functions), a learnable aggregator for sets of arbitrary cardinality. We report experiments on semi-synthetic and real data showing that LAF outperforms state-of-the-art sum- (max-) decomposition architectures.
  arXiv  Detail & Related papers  (2020-12-15T18:28:53Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.