Minimum Robust Multi-Submodular Cover for Fairness

Lan N. Nguyen, My T. Thai

Abstract

The Minimum Robust Multi-Submodular Cover for Fairness (MINRF) problem addresses the challenge of selecting a minimum-sized set that satisfies multiple submodular constraints simultaneously, even under adversarial element removal. This paper establishes the computational hardness of MINRF and introduces bicriteria approximation algorithms—RANDGR, ALG1, and ALGR—designed for varying levels of robustness. Experimental results on information propagation and movie recommendation datasets demonstrate that these algorithms significantly reduce query complexity while maintaining high solution quality compared to standard greedy and disjoint heuristics.

Introduction

In many selection problems, such as identifying influential nodes in a social network or recommending products, the goal is to satisfy a utility threshold with the smallest possible set. This is typically modeled as a submodular cover problem. However, real-world applications often demand fairness—ensuring multiple groups or objectives are satisfied—and robustness—ensuring the solution remains valid if some elements fail or are removed.

The authors formalize this as the Minimum Robust Multi-Submodular Cover for Fairness (MINRF) problem. Given $m$ monotone submodular functions $f_1, \dots, f_m$ and thresholds $T_1, \dots, T_m$, the goal is to find a set $S$ of minimum size such that for every group $i$ and every subset $A \subseteq S$ of size at most $r$, $f_i(S \setminus A) \geq T_i$.

Algorithmic Framework

The paper proposes a tiered approach based on the robustness parameter $r$.

RANDGR for $r=0$

When no failures are expected ($r=0$), the problem reduces to a multi-submodular cover. The standard greedy approach evaluates all functions at every step, which is computationally expensive. RANDGR (Random Greedy) optimizes this by randomly selecting a subset of unsatisfied constraints in each iteration and picking an element that best satisfies them. This randomization drastically reduces the number of function evaluations (queries).

ALG1 and ALGR for $r \geq 1$

For $r=1$, ALG1 starts with a non-robust solution and "patches" it by identifying critical elements whose removal would violate a threshold. For general $r$, ALGR builds robustness incrementally. It ensures the set is robust against $t$ removals in each round $t$, eventually reaching $r$. These algorithms are bicriteria approximations, allowing for a small slack in threshold satisfaction to maintain tractability.

Experimental Evaluation

The algorithms were tested on two datasets:

  1. Information Propagation (IP): Using the Facebook SNAP dataset, the task was to spread information across different demographic groups under a Linear Threshold model.
  2. Movie Recommendation (MR): Using MovieLens 20M, the goal was to recommend movies to users such that each user's utility (similarity-based) is met even if some recommendations are ignored.
Performance comparison of RANDGR, GREEDY, THRESGR, and SEP across IP and MR datasets. The plots show set size $|S|$ and query complexity as a function of threshold $T$.

Key Results

As shown in the experimental results, the proposed algorithms offer a superior balance of efficiency and solution quality:

  • Query Efficiency: In the IP task, RANDGR significantly outperformed the standard Greedy algorithm in terms of query count while achieving nearly identical set sizes. In the MR task, THRESGR showed even greater efficiency in query reduction.
  • Solution Quality: The proposed methods consistently produced smaller sets than the SEP baseline (which solves for each group independently). This is evident in the $|S|$ plots where SEP results in much larger set sizes for the same threshold.
  • Scalability: While the complexity increases with $r$, the algorithms remain practical for fixed $r$, providing a scalable solution for robust fair coverage.

Conclusion

The MINRF framework provides a robust foundation for fair selection problems. By leveraging randomization and incremental robustness, the proposed algorithms overcome the exponential complexity of verifying robust sets. Future work may explore extensions to non-monotone functions or tighter approximation bounds.

Summary updated

Abstract

In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MinRF), as follows: given a ground set V; m monotone submodular functions f_1,...,f_m; m thresholds T_1,...,T_m and a non-negative integer r; MinRF asks for the smallest set S such that f_i(S \ X) ≥ T_i for all i ∈ [m] and |X| ≤ r. We prove that MinRF is inapproximable within (1- ε) ln m; and no algorithm, taking fewer than exponential number of queries in term of r, is able to output a feasible set to MinRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for r = 0, one for r = 1, and one for general r. We further investigate our algorithms' performance in two applications of MinRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.
BibTeX
@inproceedings{nguyen2021minimum,
  author = {Lan N. Nguyen and My T. Thai},
  title = {{Minimum Robust Multi-Submodular Cover for Fairness}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i10.17100},
}
Figure