# Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2014.

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

- [Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization](https://mlsanity.com/paper/2108.00219/) (2021)
- [multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning](https://mlsanity.com/paper/2106.01354/) (2021)
- [R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User Intents](https://mlsanity.com/paper/2303.00732/) (2023)
- [A Weighted K-Center Algorithm for Data Subset Selection](https://mlsanity.com/paper/2312.10602/) (2023)
- [Less is more: Selecting informative and diverse subsets with balancing constraints](https://mlsanity.com/paper/2104.12835/) (2021)
- [DIVINE: Diverse Influential Training Points for Data Visualization and Model Refinement](https://mlsanity.com/paper/2107.05978/) (2021)
- [On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions](https://mlsanity.com/paper/2402.16442/) (2024)
- [Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity](https://mlsanity.com/paper/2108.08758/) (2021)
- [Differentiated Relevances Embedding for Group-based Referring Expression Comprehension](https://mlsanity.com/paper/2203.06382/) (2022)
- [Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization](https://mlsanity.com/paper/2406.14876/) (2024)
- [Discovering Implicit Large Language Model Alignment Objectives](https://mlsanity.com/paper/2602.15338/) (2026)

## Abstract (arXiv)

To cope with the high level of ambiguity faced in domains such as Computer Vision or Natural Language processing, robust prediction methods often search for a diverse set of high-quality candidate solutions or proposals. In structured prediction problems, this becomes a daunting task, as the solution space (image labelings, sentence parses, etc.) is exponentially large. We study greedy algorithms for finding a diverse subset of solutions in structured-output spaces by drawing new connections between submodular functions over combinatorial item sets and High-Order Potentials (HOPs) studied for graphical models. Specifically, we show via examples that when marginal gains of submodular diversity functions allow structured representations, this enables efficient (sub-linear time) approximate maximization by reducing the greedy augmentation step to inference in a factor graph with appropriately constructed HOPs. We discuss benefits, tradeoffs, and show that our constructions lead to significantly better proposals.