Minimum Robust Multi-Submodular Cover for Fairness

Lan N. Nguyen, My T. Thai

In many real-world optimization tasks, the goal is to select a small set of items to satisfy a specific objective. For instance, in Information Propagation, one might seek a few "seed" users to maximize message spread. In Recommendation Systems, the aim is to suggest a small set of items that a user will find useful. However, these standard formulations often overlook two critical dimensions: fairness (satisfying multiple demographic groups or stakeholders simultaneously) and robustness (ensuring the solution remains effective even if some elements are removed or fail).

This paper, presented at AAAI 2021, introduces the Minimum Robust Multi-Submodular Cover for Fairness (MINRF) problem. MINRF asks for the smallest set $S$ such that for every group $i$, a target threshold $T_i$ is met even if any $r$ items are removed from $S$.

Theoretical Hardness and Verification

The authors prove that MINRF is computationally challenging. Specifically, it is inapproximable within a factor of $(1-\epsilon)\ln m$, where $m$ is the number of groups. Furthermore, verifying whether a set is robust against the removal of $r$ elements is inherently difficult, as a brute-force check involves evaluating $\binom{|S|}{r}$ subsets, which grows exponentially with $r$.

Proposed Algorithms

To address these challenges, the paper proposes three bicriteria approximation algorithms:

  1. RANDGR (Random Greedy): Designed for the non-robust case ($r=0$). It optimizes efficiency by randomly selecting a subset of unsatisfied constraints at each step, significantly reducing the number of computational queries compared to a standard greedy approach.
  2. ALG1: A specialized algorithm optimized for robustness against the removal of a single element ($r=1$).
  3. ALGR: A general algorithm for any $r$. It iteratively "hardens" a solution by identifying specific vulnerabilities—removals that cause the set to fail—and adding elements to patch those gaps.

Experimental Evaluation

The algorithms were evaluated on two real-world datasets: the Facebook (SNAP) dataset for Information Propagation (IP) and the MovieLens 20M dataset for Movie Recommendation (MR).

Comparison of solution size (|S|) and computational cost (# queries) across Information Propagation (IP) and Movie Recommendation (MR) tasks.

As shown in the experimental results, the proposed algorithms consistently outperform baseline heuristics. In terms of solution quality, the algorithms find much smaller sets $|S|$ than the "SEP" baseline (which represents a disjoint-set approach to robustness). In terms of efficiency, RANDGR and THRESGR (a threshold-based greedy variant) require significantly fewer queries than the standard GREEDY approach, particularly in the Movie Recommendation task.

The Robustness Bottleneck

While the algorithms are effective for small $r$, the computational cost increases drastically as the robustness requirement grows. This "verification bottleneck" is a key limitation of robust optimization.

Computational cost (# queries) as a function of robustness parameter r for the Movie Recommendation task.

The query count for most algorithms grows exponentially as $r$ increases from 2 to 6, reflecting the combinatorial explosion of possible failure subsets. This highlights the trade-off between achieving high levels of adversarial robustness and maintaining computational tractability.

Conclusion

The MINRF framework provides a robust and fair approach to multi-objective submodular optimization. By leveraging randomization and iterative hardening, the proposed algorithms achieve near-optimal solution sizes while maintaining practical efficiency for moderate robustness requirements. Future work may explore "average-case" robustness, where elements fail stochastically rather than adversarially, potentially offering further efficiency gains.

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 for all $i \in [m]$, $\min_{|X| \leq r} f_i(S \setminus X) \geq T_i$. We prove that MinRF is inapproximable within $(1-\epsilon)\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