# Robust Sequence Networked Submodular Maximization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 28 Dec 2022.

## Builds on (most cited first, 12 of 12)

- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [HERO: HiErarchical spatio-tempoRal reasOning with Contrastive Action Correspondence for End-to-End Video Object Grounding](https://mlsanity.com/paper/2208.05818/) (2022)
- [Robust Monotone Submodular Function Maximization](https://mlsanity.com/paper/1507.06616/) (2015)
- [Adaptive Sequence Submodularity](https://mlsanity.com/paper/1902.05981/) (2019)
- [String Submodular Functions with Curvature Constraints](https://mlsanity.com/paper/1303.3018/) (2013)
- [Resilient Monotone Submodular Function Maximization](https://mlsanity.com/paper/1703.07280/) (2017)
- [Submodularity on Hypergraphs: From Sets to Sequences](https://mlsanity.com/paper/1802.09110/) (2018)
- [Robust and Adaptive Sequential Submodular Optimization](https://mlsanity.com/paper/1909.11783/) (2019)
- [Resilient Monotone Sequential Maximization](https://mlsanity.com/paper/1803.07954/) (2018)
- [Robust Sequence Submodular Maximization](https://mlsanity.com/paper/2011.00542/) (2020)

## Abstract (arXiv)

In this paper, we study the underlineRobust underlineoptimization for underlinesequence underlineNetworked underlinesubmodular maximization (RoseNets) problem. We interweave the robust optimization with the sequence networked submodular maximization. The elements are connected by a directed acyclic graph and the objective function is not submodular on the elements but on the edges in the graph. Under such networked submodular scenario, the impact of removing an element from a sequence depends both on its position in the sequence and in the network. This makes the existing robust algorithms inapplicable. In this paper, we take the first step to study the RoseNets problem. We design a robust greedy algorithm, which is robust against the removal of an arbitrary subset of the selected elements. The approximation ratio of the algorithm depends both on the number of the removed elements and the network topology. We further conduct experiments on real applications of recommendation and link prediction. The experimental results demonstrate the effectiveness of the proposed algorithm.