# From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

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

- [How Interpretable Are Interpretable Graph Neural Networks?](https://mlsanity.com/paper/2406.07955/) (2024)
- [Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning](https://mlsanity.com/paper/2106.02938/) (2021)
- [Learning Neural Set Functions Under the Optimal Subset Oracle](https://mlsanity.com/paper/2203.01693/) (2022)
- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)
- [Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice](https://mlsanity.com/paper/2111.10175/) (2021)

## Abstract (arXiv)

Submodular functions have been studied extensively in machine learning and data mining. In particular, the optimization of submodular functions over the integer lattice (integer submodular functions) has recently attracted much interest, because this domain relates naturally to many practical problem settings, such as multilabel graph cut, budget allocation and revenue maximization with discrete assignments. In contrast, the use of these functions for probabilistic modeling has received surprisingly little attention so far. In this work, we firstly propose the Generalized Multilinear Extension, a continuous DR-submodular extension for integer submodular functions. We study central properties of this extension and formulate a new probabilistic model which is defined through integer submodular functions. Then, we introduce a block-coordinate ascent algorithm to perform approximate inference for those class of models. Finally, we demonstrate its effectiveness and viability on several real-world social connection graph datasets with integer submodular objectives.