We propose a new random pruning method (called "submodular sparsification
(SS)") to reduce the cost of submodular maximization. The pruning is applied
via a "submodularity graph" over the $n$ ground elements, where each directed
edge is associated with a pairwise dependency defined by the submodular
function. In each step, SS prunes a $1-1/\sqrt{c}$ (for $c>1$) fraction of the
nodes using weights on edges computed based on only a small number ($O(\log
n)$) of randomly sampled nodes. The algorithm requires $\log_{\sqrt{c}}n$ steps
with a small and highly parallelizable per-step computation. An accuracy-speed
tradeoff parameter $c$, set as $c = 8$, leads to a fast shrink rate
$\sqrt{2}/4$ and small iteration complexity $\log_{2\sqrt{2}}n$. Analysis shows
that w.h.p., the greedy algorithm on the pruned set of size $O(\log^2 n)$ can
achieve a guarantee similar to that of processing the original dataset. In news
and video summarization tasks, SS is able to substantially reduce both
computational costs and memory usage, while maintaining (or even slightly
exceeding) the quality of the original (and much more costly) greedy algorithm.

本文提出的随机剪枝方法（称为 “子模函数稀疏化（SS）”）能够减少子模最大化的成本，并在新闻与视频摘要任务中显著降低计算成本和内存使用率，同时保持（甚至略微超过）处理原始数据集的成果。