Monotone and Separable Set Functions: Characterizations and Neural Models
Soutrik SarangiIIT Bombay, Yonatan SverdlovTechnionNadav DymTechnionAbir DeIIT Bombay · 2025
Read Monotone and Separable Set Functions: Characterizations and Neural Models by Soutrik SarangiIIT Bombay, Yonatan SverdlovTechnionNadav DymTechnionAbir DeIIT Bombay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-23634.txt.
Introduction
Soutrik Sarangi and three co-authors ask when sets can be turned into vectors without scrambling their containment order. For set containment problems, a useful embedding would keep smaller sets below bigger ones exactly: one set contains another precisely when its vector sits below the other's in every coordinate. Functions with that property, called monotone and separating, are the subject here.
The authors bound the vector dimension such functions need, based on the sizes of the multisets and the ground set. With an infinite ground set, exact versions cannot exist at all. They therefore build a neural model with a relaxed version of the property, plus smooth stability in the Hölder sense. Such functions also yield universal models that are monotone by construction and can mimic any monotone set function. Experiments on containment tasks favor their model over standard set networks that ignore containment as a built-in bias.
Catalog record
| CREATOR | Soutrik SarangiIIT Bombay, Yonatan SverdlovTechnionNadav DymTechnionAbir DeIIT Bombay |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 126 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23634
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Monotone and Separable Set Functions: Characterizations and Neural Models Soutrik SarangiIIT Bombay, Yonatan SverdlovTechnionNadav DymTechnionAbir DeIIT Bombay 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 ⊆ T if and only if F ( S ) ≤ F ( T ) 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 MASNet 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 MASNet model, in comparison with standard set models which do not incorporate set containment as an inductive bias. Our code is available in GitHub . * * footnotetext: Soutrik and Yonatan contributed equally. Contact emails of the authors: [email protected], [email protected] , [email protected], [email protected] 1 Introduction A multiset \{\!\!\{x_{1},\ldots,x_{n}\}\!\!\} is an unordered collection of vectors, where order does not matter (like sets) and repetitions are allowed (unlike sets). In recent years, there has been increased interest in neural networks that can map multisets to vectors, with applications for physical simulations [ 1 ] , processing point clouds [ 2 ] , and graph neural networks [ 3 ] . Another important application of multiset-to-vector maps is set-containment search [ 4 , 5 , 6 ] . Here the goal is to check whether a given multiset S is (approximately) a subset of T , and this is often carried out by learning a multiset-to-vector mapping F , and then checking whether F(S)\leq F(T) (element-wise), in which case, one deduces that S is a subset of T . In this paper, we look into this problem from a theoretical perspective. Monotone and Separable functions: We begin our analysis with some definitions: we say that a function F mapping sets to vectors is monotone if S\subseteq T\subseteq V implies that F(S)\leq F(T) , and we will say that F is separable if F(S)\leq F(T) implies that S\subseteq T . When F is simultaneously monotone and separable , we call it a MAS function. When F is a MAS function, we can safely test whether F(S)\leq F(T) , and this will be fully equivalent to checking whether S\subseteq T . Motivation for MAS functions: It is natural to ask why we’re interested in functions that are MAS instead of just being monotone or just separable. For this, we begin with a couple of real-life applications based on the set-containment task: (I) In recommendation system design, one problem is to recommend item having a particular set of features, S . Here, we represent each item as a set of corresponding features T , and the problem is to find all sets T such that approximately, S\subseteq T . (II) Text entailment where we are given a small query sentence q nd the goal is to find the set of corpus items c from a large corpus C , where q\implies c or c entails q . Here, q and c are typically represented as sets of contextual embeddings ( S for q and T for c ) and the entailment problem can be cast as the problem of checking if S\subset T . In a neural network setting, such problems require us to design a function F such that the "order" between F(S) and F(T) can serve as a boolean test for whether S is a subset of T . For this, F needs to satisfy two conditions: (A) F(S)\leq F(T) implies S\subseteq T (B) F(S)\not\leq F(T) implies S\not\subseteq T . Here, we like to emphasize that, for high accuracy, F needs to satisfy both conditions A and B as above. Monotone functions satisfy condition (B) without necessarily satisfying condition (A). As a result, if we predict S\subseteq T based on F(S)\leq F(T) when F is monotone but not separable, it will give large number of false positives. Similarly, if F is separable but not monotone, then F satisfies condition (A) without satisfying condition (B). Thus, using such for checking S\subseteq T results in a large number of false negatives. Hence, both monotonicity and separability are necessary to develop an accurate test for set-containment Related works: Monotone set functions have been extensively studied from theoretical perspective, e.g. , in the context of theory of capacities [ 7 ] , game theory [ 8 ] , fuzzy systems [ 9 ] , combinatorial auctions [ 10 , 11 , 12 ] and learning theory [ 13 , 14 , 15 , 16 , 17 , 18 ] . However, to the best of the knowledge, the notion of functions which are jointly monotone and separable multiset (MAS), is entirely new, albeit some related works on partial order of sets can be traced in mathematics literature, such as [ 19 ] . Our goal in this paper is to understand whether it is possible to construct MAS multiset functions, and if so, develop differentiable models that are MAS by construction and are appropriate for multiset containment tasks. Our inquiry is also motivated by the study of multiset injective functions. This has been extensively studied in recent works [ 20 , 3 ] , including characterization of the vector dimension needed to enable injectivity [ 21 , 22 , 23 ] and the development of differentiable injective multiset models [ 24 , 25 , 26 ] . In this work, we aim to attain similar results for the more challenging problem of MAS multiset functions (more details in Subsection 2.1 ). An additional goal of this work is stability: in most learning scenarios, we are looking for S , which is only approximately a subset of T . Accordingly, we would like to design functions F that are not only MAS but also stable, in the sense that when S is approximately a subset of T , then F(S) is approximately dominated by F(T) . Summary of our goal In summary, in this work, we aim to characterize (MAS) set functions that output finite-dimensional set representations and subsequently design neural networks for such functions. At a high level, we seek to address the following questions: (1) What are the conditions for existence of a finite dimensional MAS functions? (2) What are the permissible relaxations to monotonicity and separability if the existential conditions identified in (1) are not satisfied? (3) What are the possible neural architectures for these functions? (4) Are these functions stable? We expect that the design of trainable models with built-in guarantees of monotonicity, separability, and stability will significantly enhance the inductive bias for