An Efficient Streaming Algorithm for the Submodular Cover Problem

Ashkan Norouzi-Fard, Abbas Bazzi, Ilija Bogunovic, Marwa El Halabi, Ya-Ping Hsieh, Volkan Cevher

Overview

This paper introduces ESC-Streaming, the first efficient single-pass algorithm for the Submodular Cover (SC) problem in a data streaming setting. Because the authors prove that achieving a perfect cover with limited memory is mathematically impossible in one pass, they propose a "bicriteria" approach: achieving a near-total cover (e.g., 99% utility) using a set size that is theoretically competitive with the best possible offline solutions.

The Challenge of Streaming Submodular Cover

The Submodular Cover (SC) problem is a classic optimization task: given a large collection of items and a utility function (which exhibits "diminishing returns" or submodularity), find the smallest possible subset that reaches a target utility score $Q$.

While we have highly effective "offline" greedy algorithms for this, they require iterating over the entire dataset multiple times. In the era of "Big Data," this is often impossible. Data might be streaming in real-time, or the dataset (like a social network graph with billions of edges) might be too massive to fit into a computer's RAM.

The core challenge is: Can we find a small, high-utility subset while only looking at each data point once and using very little memory?

Methodology: The ESC-Streaming Algorithm

The authors first establish a foundational "hardness" result: they prove that any single-pass algorithm seeking a perfect cover must use memory proportional to the size of the entire stream. This renders exact streaming algorithms useless for truly massive data.

To bypass this limitation, they develop ESC-Streaming (Efficient bicriteria Submodular Cover Streaming), which uses a bicriteria relaxation. Instead of hitting exactly 100% of the target utility $Q$, it aims for $(1-\epsilon)Q$.

The algorithm operates in two distinct phases:

  1. Sieving: As elements arrive in the stream, the algorithm maintains a small collection of "representative sets." Each set has a different "marginal gain" threshold. If a new element provides a gain above a set's threshold (and the set isn't too full), the element is added. This requires only $O(\log M)$ operations per element, making it highly efficient.
  2. Querying: Once the stream ends, the user provides a tolerance $\epsilon$. The algorithm performs a quick binary search over its representative sets to find the smallest one that meets the $(1-\epsilon)Q$ utility requirement.

Evaluation Datasets

The authors evaluated ESC-Streaming on three distinct tasks to test its versatility and scalability:

  • Active Set Selection: A quantum chemistry dataset containing 7,000 organic molecules. The goal is to select a small "active set" to predict atomization energy using kernel ridge regression.
  • Massive Graph Cover (uk-2014): A snapshot of the .uk web domain with 787 million nodes and 47.6 billion edges. This dataset is so large (190GB+) that standard offline algorithms cannot process it.
  • Social Network Analysis (Friendster): A graph with 65.6 million nodes and 1.8 billion edges, used to compare the streaming approach against a limited-run offline greedy algorithm.

Empirical Results

Speed vs. Accuracy: On the molecule dataset, ESC-Streaming demonstrated a massive reduction in computational overhead. It used less than 3.15% of the computational effort (measured in oracle calls) required by the standard offline greedy algorithm, yet produced solutions only about twice as large.

Performance comparison on the active set selection task, showing ESC-Streaming requires significantly fewer oracle calls than greedy baselines.

Extreme Scalability and Superiority over Random: The algorithm successfully processed the massive 47.6-billion-edge "uk-2014" graph. On the "Friendster" graph, it achieved utility nearly identical to the offline greedy algorithm while using less than 30MB of memory. In all graph experiments, ESC-Streaming significantly outperformed random selection, proving that its thresholding strategy effectively identifies the most "informative" nodes in a network.

Graph cover performance showing ESC-Streaming significantly outperforms random selection and closely tracks offline greedy in the early stages (inset).

Theoretical Guarantees: Beyond empirical success, the authors prove that for a given tolerance $\epsilon$, the algorithm provides a $2/\epsilon$-approximation of the optimal set size while successfully hitting the $(1-\epsilon)Q$ utility target.

Limitations and Future Work

  • Partial Cover Only: The primary limitation is that it cannot guarantee a 100% cover. In applications where missing even 1% of the utility is unacceptable, this algorithm isn't applicable (though no sublinear memory algorithm can solve that anyway).
  • Memory-Approximation Tradeoff: To get a better approximation (a smaller $\epsilon$), the algorithm needs to maintain more representative sets, which linearly increases memory usage.
  • Future Directions: This work opens the door for multi-pass streaming algorithms that might bridge the gap between this single-pass approach and the optimal offline greedy results, potentially offering tighter approximations with slightly more passes over the data.

Summary updated

Abstract

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESC-Streaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large-scale graph cover problems.
BibTeX
@inproceedings{norouzifard2016efficient,
  author = {Ashkan Norouzi-Fard and Abbas Bazzi and Ilija Bogunovic and Marwa El Halabi and Ya-Ping Hsieh and Volkan Cevher},
  title = {{An Efficient Streaming Algorithm for the Submodular Cover Problem}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=By4-TDWdWr},
}
Figure