Fast Distributed Submodular Cover: Public-Private Data Summarization
In this paper, we introduce the public-private framework of data summarization motivated by privacy concerns in personalized recommender systems and online social services. Such systems have usually access to massive data generated by a large pool of users. A major fraction of the data is public and is visible to (and can be used for) all users. However, each user can also contribute some private data that should not be shared with other users to ensure her privacy. The goal is to provide a succinct summary of massive dataset, ideally as small as possible, from which customized summaries can be built for each user, i.e. it can contain elements from the public data (for diversity) and users' private data (for personalization). To formalize the above challenge, we assume that the scoring function according to which a user evaluates the utility of her summary satisfies submodularity, a widely used notion in data summarization applications. Thus, we model the data summarization targeted to each user as an instance of a submodular cover problem. However, when the data is massive it is infeasible to use the centralized greedy algorithm to find a customized summary even for a single user. Moreover, for a large pool of users, it is too time consuming to find such summaries separately. Instead, we develop a fast distributed algorithm for submodular cover, FASTCOVER, that provides a succinct summary in one shot and for all users. We show that the solution provided by FASTCOVER is competitive with that of the centralized algorithm with the number of rounds that is exponentially smaller than state of the art results. Moreover, we have implemented FASTCOVER with Spark to demonstrate its practical performance on a number of concrete applications, including personalized location recommendation, personalized movie recommendation, and dominating set on tens of millions of data points and varying number of users.
The paper considers the submodular cover problem in the MapReduce setting. In this problem, given a submodular function f(S), the goal is to find a set S of size as small as possible while satisfying the constraint that the function value f(S) is at least a given value Q. In the previous work, an algorithm named DISCOVER is proposed for this problem but it needed sqrt(m, |OPT|) rounds, where m is the number of machines and OPT is the optimal solution. In this work, a new algorithm is proposed that needs only a polylogarithmic number of rounds.  The basic idea is to simulate the descending threshold algorithm in the centralized setting. The elements are distributed on m machines. Given the same threshold and the current solution, all machines return elements whose marginal gains exceed the threshold. If the number of such element is too large, each machine only returns a small random subset of the ones it finds.  The paper also gives 3 motivating examples of submodular cover with multiple simultaneous constraints, which can be reduced to the above case via known reduction.
The new algorithm significantly improves over the previous work [13] in both theoretical bounds and experimental performance.  The motivation seems strange to me as it is optimizing the size of the union of the summaries of the users. It would not be surprising that this size is much larger than the size of the summary each user might see and the two sizes might not even be correlated.  The privacy motivation confuses me as it seems the reduction from multiple functions to the single function setting is known (the paper cites [15,16] for this reduction). It would be much better to position the paper as an improved algorithm for distributed submodular cover as it is the main contribution of the paper. The model considered in this paper is centralized computation in the sense that the system has access to all relevant information (no private information is withheld from the system) and no formalization of privacy is considered so the discussion regarding privacy is rather distracting from the main message (e.g. the solution presented to an user is affected by the present of other users due to the joint objective, how much privacy is lost?).   After the rebuttal, I am still very confused about the privacy consideration. The authors claim in the rebuttal that the presence or absence of user B does not affect summary for user A but I think this is not true. Consider a simple scenario where the ground set is simply {1,2}, both 1 and 2 are public. The utility functions are both modular. For user A, it is f_A({1}) = 2, f_A({2}} = 1. For user B, it is f_B({1}) = 0 and f_B({2}) = 1. The target utility is Q=1. If the system only has user A, it can return {1}. However, if the system supports both A and B, it will return {2}. Thus, user A can detect the presence of user B based on the his summary.