# Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection

arXiv: https://arxiv.org/abs/2210.11033 · HTML: https://mlsanity.com/paper/2210.11033/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 103 references that are in the map.
- First posted on arXiv 20 Oct 2022.

## Builds on (most cited first, 30 of 38)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [Learning to Reweight Examples for Robust Deep Learning](https://mlsanity.com/paper/1803.09050/) (2018)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Unconstrained Monotonic Neural Networks](https://mlsanity.com/paper/1908.05164/) (2019)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Submodular Combinatorial Information Measures with Applications in Machine Learning](https://mlsanity.com/paper/2006.15412/) (2020)
- [Differentiable Learning Under Triage](https://mlsanity.com/paper/2103.08902/) (2021)
- [Deep Set Prediction Networks](https://mlsanity.com/paper/1906.06565/) (2019)
- [NeVAE: A Deep Generative Model for Molecular Graphs](https://mlsanity.com/paper/1802.05283/) (2018)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Classification Under Human Assistance](https://mlsanity.com/paper/2006.11845/) (2020)
- [Regression Under Human Assistance](https://mlsanity.com/paper/1909.02963/) (2019)
- [Learning and Forecasting Opinion Dynamics in Social Networks](https://mlsanity.com/paper/1506.05474/) (2015)
- [Expectation-Maximization for Learning Determinantal Point Processes](https://mlsanity.com/paper/1411.1088/) (2014)
- [Scalable Greedy Feature Selection via Weak Submodularity](https://mlsanity.com/paper/1703.02723/) (2017)
- [Differentiable Submodular Maximization](https://mlsanity.com/paper/1803.01785/) (2018)
- [Training Data Subset Selection for Regression with Controlled Generalization Error](https://mlsanity.com/paper/2106.12491/) (2021)
- [Deep Submodular Functions](https://mlsanity.com/paper/1701.08939/) (2017)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Optimal approximation for unconstrained non-submodular minimization](https://mlsanity.com/paper/1905.12145/) (2019)
- [Learn to Predict Sets Using Feed-Forward Neural Networks](https://mlsanity.com/paper/2001.11845/) (2020)
- [Submodular Observation Selection and Information Gathering for Quadratic Models](https://mlsanity.com/paper/1905.09919/) (2019)
- [Deep Submodular Networks for Extractive Data Summarization](https://mlsanity.com/paper/2010.08593/) (2020)

## Built on by (most cited first, 6 of 6)

- [Advances in Set Function Learning: A Survey of Techniques and Applications](https://mlsanity.com/paper/2501.14991/) (2025)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Learning Set Functions with Implicit Differentiation](https://mlsanity.com/paper/2412.11239/) (2024)
- [Extended Deep Submodular Functions](https://mlsanity.com/paper/2409.12053/) (2024)
- [Monotone and Separable Set Functions: Characterizations and Neural Models](https://mlsanity.com/paper/2510.23634/) (2025)
- [Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions](https://mlsanity.com/paper/2607.11555/) (2026)

## Abstract (arXiv)

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, FLEXSUBNET 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 α-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-set, 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.