Robust Sequence Networked Submodular Maximization

Authors

  • Qihao Shi Zhejiang University
  • Bingyang Fu Zhejiang University
  • Can Wang Zhejiang University
  • Jiawei Chen Zhejiang University
  • Sheng Zhou Zhejiang University
  • Yan Feng Zhejiang University
  • Chun Chen Zhejiang University

DOI:

https://doi.org/10.1609/aaai.v37i12.26762

Keywords:

General

Abstract

In this paper, we study the Robust optimization for sequence Networked submodular 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 and calls for new robust algorithms. In this paper, we take the first step to study the RoseNets problem. We design a robust greedy algorithms, 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.

Downloads

Published

2023-06-26

How to Cite

Shi, Q., Fu, B., Wang, C., Chen, J., Zhou, S., Feng, Y., & Chen, C. (2023). Robust Sequence Networked Submodular Maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 37(12), 15100-15108. https://doi.org/10.1609/aaai.v37i12.26762

Issue

Section

AAAI Special Track on Safe and Robust AI