Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fashion, and (ii) m items from the algorithm's memory are removed after the stream is finished. We develop a robust submodular algorithm STAR-T. It is based on a novel partitioning structure and an exponentially decreasing thresholding rule. STAR-T makes one pass over the data and retains a short but robust summary. We show that after the removal of any m elements from the obtained summary, a simple greedy algorithm STAR-T-GREEDY that runs on the remaining elements achieves a constant-factor approximation guarantee. In two different data summarization tasks, we demonstrate that it matches or outperforms existing greedy and streaming methods, even if they are allowed the benefit of knowing the removed subset in advance.
This paper studies the problem of submodular maximization in a streaming and robust setting. In this setting, the goal is to find k elements of high value among a small number of elements retained during the stream, where m items might be removed after the stream. Streaming submodular maximization has been extensively studied due to the large scale applications where only a small number of passes over the data is reasonable. Robustness has also attracted some attention recently and is motivated by scenarios where some elements might get removed and the goal is to obtain solutions that are robust to such removals. This paper is the first to consider jointly the problem of streaming and robust submodular maximization.
The authors develop the STAR-T algorithm, which maintains O((m log k + k )log^2 k) elements after the stream and achieves a constant (0.149) approximation guarantee while being robust to the removal of m elements. This algorithm combines partitioning and thresholding techniques for submodular optimization which uses buckets. Similar ideas using buckets were used in previous work for robust submodular optimization, but here the buckets are filled in a different fashion. It is then shown experimentally that this algorithm performs well in influence maximization and movie recommendation applications, even against streaming algorithms which know beforehand which elements are removed. 
With both the streaming and robustness aspects, the problem setting is challenging and obtaining a constant factor approximation is a strong result. However, there are several aspects of the paper that could be improved. It would have been nice if there were some non-trivial lower bounds to complement the upper bound. The writing of the analysis could also be improved, the authors mention an “innovative analysis” but do not expand on what is innovative about it and it is difficult to extract the main ideas and steps of the analysis from the proof sketch. Finally, the influence maximization application could also be more convincing. For the experiments, the authors use a very simplified objective for influence maximization which only consists of the size of the neighborhood of the seed nodes. It is not clear how traditional influence maximization objectives where the value of the function depends on the entire network for any set of seed nodes could fit in a streaming setting.