LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale

Introduction

LinkedIn’s Audience Engagement API is a platform that enables marketers (analysts) aggregated insights about members’ content engagements while ensuring member (user) data is protected. Consider an advertiser that is selling a cloud solution and wants to create a sponsored post on LinkedIn. The advertiser might use the Audience Engagement API to do research and find that the target audience engages with GDPR articles. Hence, the advertiser should write about how their cloud solution adheres to GDPR standards, thus increasing engagement. By design, the Audience Engagement API is secure, aggregated, and uses state of the art differentially private algorithms to provide rigorous privacy guarantees. The data honors user privacy settings and only contains information that is approved as outlined by GDPR. Further, data is purged within 30 days of a user leaving the ecosystem because it has a 30 day retention.

The primary reason to leverage differential privacy is due to differencing attacks, where the difference between two queries reveals an individual’s content. For example, one query can be for the top articles by engagement from CEOs in India and then another query asks for the top articles by engagement from CEOs in India or LinkedIn. This attack makes aggregation and thresholding approaches insufficient — two results having counts above a threshold does not mean that their difference cannot uniquely identify an individual. Rather than limiting the scope of the Audience Engagement API by reducing the ways the dataset can be sliced in an ad hoc way, we instead worked to include differentially private algorithms to prevent such differencing attacks. To make such a product private, it is apparent that one must add noise, to prevent differencing attacks, and limit the number of accesses to the API, to prevent reconstructing the dataset, despite the noise that is added. Differential privacy then formalizes these approaches via randomized algorithms and its composition properties.

To incorporate differential privacy, we carefully balance various resources, including data storage distributed across several servers, real-time query computation, privacy loss quantified by the differential privacy parameters $(\varepsilon,\delta)$, and accuracy. We describe here the overall privacy system deployed at LinkedIn that balances these resources to provide a product that surfaces audience engagement insights while putting members first by safeguarding their data.

Providing scalable, real-time analytics with low latency without differential privacy is challenging enough. Luckily, we have the open source real-time distributed OLAP datastore, called Apache Pinot (incubating) . Pinot enables use cases like Job and Publisher Analytics and Who Viewed My Profile. In order to develop a differentially private system, we need to think how it can be used in conjunction with a (distributed) OLAP system such as Pinot. This would enable us to have scalable privacy systems. Furthermore, we need to implement a budgeting tool into the API so that analysts cannot repeatedly query the dataset thus making noise addition pointless. Our goal is twofold: implement differentially private algorithms that can be used with real-time distributed OLAP systems and incorporate a privacy budget management service to restrict the amount of information an analyst can retrieve. For the privacy budget management service, we incorporate the latest composition bounds for our particular algorithms to extract more utility subject to a given differential privacy budget.

We make several contributions toward making practical privacy systems that leverage differential privacy.

We describe a suite of differentially private algorithms that cover the data analytics tasks for LinkedIn’s Audience Engagement API, which provide user-level privacy guarantees.

We detail our privacy budget management service that is able to track each analyst’s privacy budget over multiple data centers. Hence, we can ensure the budget is enforced across large scale systems in real-time.

We showcase empirical results of our algorithms on LinkedIn’s data for various privacy parameters on our deployed system.

We provide a discussion about the considerations in our privacy system, in particular how we rationalize certain parameters. We hope that this discussion will help guide practitioners in how parameters might be set and provide transparency into our deployed system.

Although the private algorithms and privacy budget formulas were known in prior work, the main contribution of this work is in combining both algorithms and budget management into a system that can easily scale to large datasets and multiple analysts querying the system while applying the privacy system in the Audience Engagement API product at LinkedIn. In particular, we developed a library of private algorithms and a privacy budget management system separately so that each could scale according to their own requirements; see Section 4 for more detail. Further, we propose two units of budget, information and call budgets, that can be deducted for each analyst depending on each result she receives. We can then use the latest, state of the art privacy composition formulas that tightly bound the overall privacy loss. We also state our assumptions for the privacy system in Section 8, including analysts not colluding and data churn for refreshing privacy budgets.

2 Related Work

Differential privacy has become the standard privacy benchmark for data analytics on sensitive datasets. Despite its popularity in the academic literature, the number of actually implemented differential privacy systems is limited, but growing. Several of the currently implemented systems with differential privacy are in the local model, where data is individually privatized prior to being aggregated on a central server. The main local differentially private systems include Google’s RAPPOR on their Chrome browser , Apple’s iOS and MacOS diagnostics , and Microsoft’s telemetry data in Windows 10 Fall Creators Update .

The privacy model we are interested in for this work is the global privacy setting, where data is already stored centrally, but we want to ensure each result computed on the data is privatized. In this less restrictive privacy setting, the main industrial differential privacy systems include Microsoft’s PINQ , Uber’s FLEX for its internal analytics , LinkedIn’s PriPeARL for its ad analytics , Google’s recent differential privacy open source project , and the 2020 U.S. Census . In this work, we present a privacy system that incorporates a privacy budget management service to ensure user-level privacy, whereas LinkedIn’s PriPeARL system provides event-level privacy and was focused on providing consistent results, which we also incorporate. The FLEX system points out that a privacy budget management service can be implemented but does not provide a strategy for how to do it. Further, our system is part of an API that allows for adaptively chosen queries computed in real-time, which is, to our knowledge, a different model from the future U.S. Census Bureau’s system.

The main difference between the approach recently proposed in and this work is that we do not bound user contributions across and within different partitions.Note that a caveat in the Google open-source code is that the “implementation assumes that each user contributes only a single row to each partition.‘”, https://github.com/google/differential-privacy Such an approach would create a significant bottleneck in processing queries in a real-time system, since each online query can require a pre-processing step over the dataset to bound user contributions. For Audience Engagement, we are dealing with terabytes of data. The UnkGumb algorithm provides user-level privacy guarantees for count distinct queries without pre-processing, thus handling similar queries-per-second (QPS) as without privacy. See Section 3 for more detail. Although Wilson et al. do discuss a privacy budget, it does not consider optimized privacy loss bounds for the data analytics tasks we consider. Our system takes into account the various privacy algorithms to take advantage of the state of the art privacy composition bounds, such as pay-what-you-get composition and improved composition bounds for exponential mechanisms .

There are other open source libraries for differentially private algorithms, such as PrivateSQL and the recent collaboration project between Harvard’s IQSS and Microsoft . The former work generates a synthetic dataset, private synopses, that is based on all queries that are posed in advance. Such an approach is very appealing, but would not be feasible in our setting due to the size of the underlying dataset and the set of all possible queries that can be asked by an analyst also being large.

Another related privacy system is PSI ($\Psi$) from the Harvard Privacy Tools Project . PSI is a private data sharing interface to “enable researchers in the social sciences and other fields to share and explore privacy-sensitive datasets with the strong privacy protections of differential privacy.” Although they support several commonly used statistics, our system covers the necessary algorithms to privatize queries in the Audience Engagement API. Further, our system allows for handling highly distributed datasets via Pinot while enforcing a strict privacy budget that is eventually consistent across data centers.

Preliminaries

In our algorithms, we will add noise to the histogram counts. The noise distributions we consider are from a Gumbel distribution where $\texttt{Gumbel}(b)$ has PDF $p_{\texttt{Gumbel}}(z;b)$ or a Laplace distribution where $\texttt{Lap}(b)$ has PDF $p_{\texttt{Lap}}(z;b)$, and

As an analyst interacts with private algorithms, the resulting privacy parameters increase with each returned result. Hence, we need to account for the overall privacy budget that an analyst can exhaust before the privacy loss is deemed to be too large. We then use the composition property of DP to bound the resulting privacy parameters. We will use bounded range in our composition analysis, which was introduced by Durfee and Rogers . Note that $\varepsilon$-BR mechanisms are $\varepsilon$-DP and $\varepsilon$-DP mechanisms are $2\varepsilon$-BR.

where we use the density function instead for continuous outcomes.

We now state the result from Dong et al. that tightens the composition bound from Durfee and Rogers which itself improved on the more general optimal DP composition bounds .

Let $\mathcal{M}_{1},\mathcal{M}_{2},\cdots,\mathcal{M}_{t}$ each be $\varepsilon$-BR where the choice of mechanism $\mathcal{M}_{i}$ at round $i$ may depend on the previous outcomes of $\mathcal{M}_{1},\cdots,\mathcal{M}_{i-1}$, then the resulting composed algorithm is $(\varepsilon^{\prime}(\delta),\delta)$-DP for any $\delta\geq 0$ where $\varepsilon^{\prime}(\delta)$ is the minimum of $t\varepsilon$ and

We also can use the more complicated composition bound for BR mechanisms . However we cannot use the optimal composition bound from because it only applies to the non-adaptive setting. Here we are interested in the API setting which allows the user to ask adaptive queries, meaning the queries can depend on previous results.

Private Data Analytics

To incorporate differential privacy, we needed to consider the various tasks we want the application to handle. We will be focusing on data analytics based on histograms or counts over different domain elements. We will discuss each query type our privacy system handles, but first we need to set up some notation.

Scaling our privacy system across several analysts with queries that require data from multiple servers requires algorithms that can run efficiently with runtime that does not scale with the entire data domain size $d$. For example, for the top-10 articles engaged with by staff software engineers, we do not want to query over all articles, since there could potentially be billions of articles and would be computationally expensive and slow. For this reason, we distinguish the case where the data domain is reasonably sized and known, i.e. known domain, from when the data domain is very large or unknown, i.e. unknown domain.

We then summarize in Table 1 the set of queries that we want our privacy system to handle into unrestricted sensitivity or $\Delta$-restricted sensitivity as well as known domain or unknown domain with the corresponding algorithms we will use for each setting. Recall that we can interpolate between distinct count queries and non-distinct count queries with the $\tau\geq 1$ parameter, so we include $\tau$ as a parameter to each of our algorithms. Furthermore, each algorithm takes a privacy parameter ${\varepsilon_{\texttt{per}}}$.

The primary difference between querying the OLAP datastore for results with privacy as opposed to without privacy is that when querying for the top-$k$ in the unknown domain setting, we instead fetch the top-$\bar{d}$ and then use $\texttt{UnkGumb}^{k,\bar{d},\tau}$ or $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{d},\tau}$. Ideally, we would want to set $\bar{d}=d$ to get the full dataset, but that is not practical when the number of elements is large and the existing architecture potentially trims the results for efficiency. The choice of algorithm for each query can be a simple look up of the group by clause where if no additional information is given, then we default to the unknown domain and unrestricted sensitivity.

Privacy System Architecture

Existing OLAP datastores are designed to provide real-time data analytics over distributed datasets, with differential privacy not necessarily being incorporated from the beginning. Pinot is the analytics platform of choice at LinkedIn for site-facing use cases. In this section, we detail how we incorporated differential privacy with Pinot and the application. Figure 1 presents the overall system.

The application entity, based on the request received from the analyst, generates queries to the underlying database. The queries typically ask for a histogram grouped by some column. In order to apply the right algorithm for the query, the application needs to know the sensitivity and domain setting of the column as shown in Table 1. Also, the query is to be modified to fetch a potentially larger number of rows from the database.

We designed generic interfaces that are implemented by a suite of algorithms. The interfaces allow the application to:

Retrieve modified query parameters (e.g. change $k$ to $\bar{d}$).

Estimate privacy cost of the query (e.g. return $\Delta$ or $k$).

Add noise to results based on configured parameters.

Compute the actual cost of the query, e.g. the number of items returned in the unrestricted sensitivity setting.

The application can independently invoke budget management functions, such as the following:

Getting the available budget for an analyst to verify whether a query can even start to execute.

Depleting the available budget with the executed query.

The cost of a query could be multi-dimensional, including the cost of making the call and of information retrieved (see Section 6).

Given the query from the analyst and the selected DP algorithm, the application will then interact with the DP library. It will first determine the expected cost of the resulting query to show the application, which is a function of the query that is asked and the selected algorithm. The application then calls the DP library to translate the query to a DP version that will be used to query Pinot. For example, if the query is for top-$k$ and the algorithm is in the unknown domain setting, then the translation could simply modify $k$ to $2k$, in which case $\bar{d}=2k$ in $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{d},\tau}$ and $\texttt{UnkGumb}^{k,\bar{d},\tau}$. On the other hand, if the query is over the known domain setting, then we will want to translate $k$ to $d$ in order to get counts over the full domain, including elements with zero counts.

We built the algorithms module and the budget management module to be independent of each other for the following reasons:

While DP algorithms are running on the application layer, budget management operations require a remote call to a distributed system because the budget management service needs to provide a consistent view to all application instances. Therefore, keeping the budget management independent of algorithms will allow us to scale them independently. The algorithms will need to scale to minimize memory and CPU usage, whereas the budget management service will need to scale in terms of handling higher query-per-second (QPS), while minimizing latency.

We require that newer (as yet unknown) algorithms still be able to use and manage budgets.

Multiple implementations of the budget manager are possible depending on system requirements. We need to be able to iterate on these independently and quickly.

Pinot is a distributed, real-time, columnar OLAP data store, currently incubating in Apache. At LinkedIn, we have two main categories of analytics applications: internal applications (such as dashboards, anomaly detection platform, A/B testing, etc.) and site-facing applications (such as Who viewed my profile, Talent Insights, etc.). Internal dashboards need to process a large volume of data (trillions of records), but can tolerate latencies in hundreds of milliseconds. They also have a relatively low query volume. The site-facing applications, on the other hand, serve hundreds of millions of LinkedIn members, and therefore have a very high query volume with a latency budget of a few to perhaps tens of milliseconds.

Pinot has a flexible architecture and supports a wide variety of applications in the spectrum. Pinot production clusters at LinkedIn are serving tens of thousands queries per second, supporting more than 50 analytical use cases, and ingesting over millions of records per second. Other companies such as Uber, Microsoft, and Weibo are also operating production Pinot clusters.

As shown in Figure 2, Pinot has three different components: controller, broker, and server. Controllers handle cluster wide coordination, run periodic tasks for cluster state validation and retention management, and provide a REST API for managing cluster metadata. Brokers receive queries and federate them to servers so as to cover all the segments (shards) of a table. Servers execute the query on the segments. Offline servers host segments that are batch ingested while real-time servers host the segments that are ingested from streaming sources, such as Kafka .

For the privacy system at LinkedIn, we naturally decided to use Pinot as an OLAP data store because Pinot already supported a lot of customer-facing analytics applications like Audience Engagement. However, it is noteworthy that our architecture keeps the the budget management service and Pinot as separate components so that we can easily provide DP features to other analytical query engines such as Presto and Spark SQL.

2 Key-value Based Budget Management System in Espresso

We now describe our key-value based budget management system. We create one key per analyst of a table (or per use case which may have multiple tables), and the data against the key is atomically changed when we need to update the budget. The store needs to provide ways to do the read-modify-write operations, and the latency should be relatively low.

The value record will contain the following items:

The time period over which this budget is allowed (typically the time period during which the data is refreshed completely).

The total budget used so far (or, that remain).

The timestamp when the used budget was reset to 0 (e.g. for a monthly refresh, this will be the 1st of the month).

There are three methods that the budget manager needs to support:

To check whether an analyst’s ID has enough budget to run a query that will consume at most a given cost, we use $\texttt{checkBudget}(\text{ID},\text{cost})$, which returns either true or false.

To deduct an analyst’s budget, with a given ID, after getting a DP result, with a given cost, we use $\texttt{updateBudget}(\text{ID},\text{cost})$.

To get the current budget of an analyst, with a given ID, we use $\texttt{getBudget}(\text{ID})$, which returns either the analyst’s current budget that has been used or the maximum budget allowed if there has been a budget refresh.

We use an Espresso key-value store to manage the budget. The read requests should be fast, given it is only a primary key lookup. So, a call to get the current usage (currently coming in at an unknown rate) can be fast. Espresso was chosen due to several reasons: eventual consistency in cross-datacenter replication to ensure an analyst does not exceed a given budget, capability to scale to millions of users while still keeping a fairly constant response time, control over the refresh time period, and flexibility to change per-analyst maximum upon demand.

Differentially Private Algorithms

We detail the algorithms for the various tasks in Table 1. These algorithms consist of previous work from , , and , or slightly modified forms. Each algorithm takes a ${\varepsilon_{\texttt{per}}}$ privacy parameter, which determines the amount of noise to add, while each algorithm in the unknown domain setting has an additional $\delta>0$ privacy parameter. We point out that $\texttt{UnkGumb}^{k,\bar{d},\tau}$ is the default algorithm to use when no other information is known. However, the benefit of knowing the domain is that when $k$ results are requested, $k$ results will be returned each time, whereas the unknown domain setting may return fewer than $k$. The benefit of the $\Delta$-restricted sensitivity setting is that the budget depletes by only $\Delta$, rather than by the number of elements returned, from as in the unrestricted setting.

We now discuss the Exponential Mechanism in full generality and use the range of a quality score rather than the global sensitivity of the score, as was presented in .

Note that the Exponential Mechanism is equivalent to adding Gumbel noise $\texttt{Gumbel}(S_{q}/{\varepsilon_{\texttt{per}}})$ to $q(x,y)$ for each $y\in\mathcal{Y}$ and reporting the largest noisy counts . We then have the following result from

The Exponential Mechanism is ${\varepsilon_{\texttt{per}}}$-BR and, hence ${\varepsilon_{\texttt{per}}}$-DP.

In our case, the quality score will simply be the heights of the histogram. Note that we have only discussed the Exponential Mechanism to return a single element. In the case where we want to return $k$-elements, we can iteratively apply the Exponential Mechanism by removing the element that is returned in each round and then run the Exponential Mechanism again without the previously returned elements, also known as peeling. However, we can implement this more efficiently by adding Gumbel noise to all the counts and then releasing the top-$k$ elements in a single shot . However, we need to also include counts, so we add independent Laplace noise to the counts of the elements in the noisy top-$k$. We then formally present the $\texttt{KnownGumb}^{k,\tau}$ procedure in Algorithm 2.

We then have the following result which follows from Dwork et al. , as well as from McSherry and Talwar .

Assume that $||\mathbf{h}-\mathbf{h}^{\prime}||_{\infty}\leq\tau$ and $||\mathbf{h}-\mathbf{h}^{\prime}||_{0}\leq\Delta$ for any neighbors $\mathbf{h},\mathbf{h}^{\prime}$. The procedure $\texttt{KnownLap}^{\Delta,\tau}$ is $\Delta{\varepsilon_{\texttt{per}}}/2$-DP and $\Delta{\varepsilon_{\texttt{per}}}$-BR. Further, if $\Delta$ is large or unknown then $\texttt{KnownGumb}^{k,\tau}$ is $3k{\varepsilon_{\texttt{per}}}/2$-DP and $2k{\varepsilon_{\texttt{per}}}$-BR.

2 Unknown Domain with ΔΔ\Delta-Restricted Sensitivity

For our unknown domain algorithms, we introduce a $\bot$ character to denote a null element that is not part of the domain and whose count is a noisy threshold where no element with smaller noisy count is returned. We present the $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{d},\tau}$ procedure in Algorithm 3 in a more general form than in , which only considered the distinct count case, i.e. $\tau=1$. Further, the proof of privacy remains true if we release the counts as well as the indices. For completeness, the proof of the following result is presented in the appendix.

Assume that $||\mathbf{h}-\mathbf{h}^{\prime}||_{\infty}\leq\tau$ and $||\mathbf{h}-\mathbf{h}^{\prime}||_{0}\leq\Delta$ for any neighbors $\mathbf{h},\mathbf{h}^{\prime}$, then the procedure $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{d},\tau}$ is $({\varepsilon_{\texttt{per}}}/2,\delta)$-DP.

3 Unknown Domain with Unrestricted Sensitivity

We present the $\texttt{UnkGumb}^{k,\bar{d},\tau}$ procedure in Algorithm 4 in a more general form than in , which only considered the distinct count case, i.e. $\tau=1$. The proof of the following theorem follows the same analysis as in . Note that we use the optimal threshold index procedure from Algorithm 6 in Durfee and Rogers by default and return counts by adding Laplace noise to the discovered elements in the top-$k$.

Assume $||\mathbf{h}-\mathbf{h}^{\prime}||_{\infty}\leq\tau$ for any neighbors $\mathbf{h},\mathbf{h}^{\prime}$. Then $\texttt{UnkGumb}^{k,\bar{d},\tau}$ is $((2k+1){\varepsilon_{\texttt{per}}},\delta)$-DP.

Privacy Budget Management Service

As mentioned in Section 4, the budget manager needs to be a distributed system so that it can be accessed/updated from different application execution platforms. Each analyst may access data from multiple data centers and each access must deduct from the same budget. Hence, the budget manager maintains eventual consistency across data centers.

2 Differential Privacy Composition

We present pseudocode for the privacy budget management service in Algorithm 5. We then present a way to compute the privacy guarantee of our overall system, which largely follows the analysis from Durfee and Rogers . Essentially, the analysis follows from the fact that each algorithm can be represented as an iterative sequence of ${\varepsilon_{\texttt{per}}}$-BR algorithms. Note that the algorithms in the unknown domain setting have a probability $\delta$ of larger privacy loss, which we account for in the overall $\delta^{\star}$ in the privacy guarantee.

In order to allow for the budget management service to return counts in the unrestricted sensitivity setting, we need to account for that in our overall budget. Further, in the unknown domain/unrestricted sensitivity setting, if the last element of $o_{i}$, denoted as $o_{i}$, is $\bot$ at round $i$ then adding Laplace noise with parameter $2\tau_{i}/{\varepsilon_{\texttt{per}}}$ to the counts of each of the discovered $|o_{i}|-1$ elements. will ensure ${\varepsilon_{\texttt{per}}}$-BR for each count. We can then apply our privacy loss bounds to get an overall DP guarantee by updating $k^{\star}\leftarrow k^{\star}-2|o_{i}|$ and when the last element in $o_{i}$ is not $\bot$, then we instead update $k^{\star}\leftarrow k^{\star}-(2|o_{i}|+1)$. Note that if we did not require counts in the results and need only return an ordered list of elements in the top-$k$, then we need only update $k^{\star}\leftarrow k^{\star}-(|o_{i}|+1)$.

Results

We now present some preliminary results of our privacy system for the Audience Engagement API. In Figure 3 we present curves for the number of discovered elements in a top-$50$ query with varying ${\varepsilon_{\texttt{per}}}$ and $\bar{d}$, i.e. the number of elements to collect, in procedure $\texttt{UnkGumb}^{50,\bar{d},1}$ from Algorithm 4 with a fixed $\delta=10^{-10}$. The query is to find the top articles that distinct members from the San Francisco area are engaging with. We provide intervals that contain the 25th and 75th percentiles over 1000 independent trials. Note that the randomness in each trial is solely from the noise generation and we are using the same dataset each time. We see that with the same level of privacy, increasing the number of elements to fetch allows us to discover more elements. Hence, we see a natural tradeoff not just between privacy $({\varepsilon_{\texttt{per}}})$ and utility (number of elements returned), but also between run time (fetching more results) and utility. For example, we can return twice as many elements if we fetch four times more elements with Pinot and setting ${\varepsilon_{\texttt{per}}}=0.08$.

We also empirically evaluate procedure $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{d},1}$ from Algorithm 3 in the unknown domain, $\Delta$-restricted sensitivity setting. In Figure 4 we show both the proportion of times in 1000 trials that each element was returned (right vertical axis) as well as the comparison between the noisy counts (in green) and the true counts (in red) that are returned for the discovered elements for a single trial (left vertical axis). In each plot there is a privacy parameter ${\varepsilon_{\texttt{per}}}\in\{0.1,0.2\}$, with fixed $\delta=10^{-10}$. We ask for the top primary job titles of members that engaged with articles about privacy or California. We assume that any one member cannot have more than one primary job title, hence $\Delta=1$, and fetch $\bar{d}=1000$ results from Pinot.

For the budget manager, we have a fixed budget for each marketing partner. Once the privacy budget is depleted, a marketing partner would recycle old queries to get the same results or wait some fixed amount of time for the privacy budget to be refreshed. This policy decision for the rate in which to refresh the budget is dependent on how often the underlying dataset gets renewed and the characteristics of the underlying dataset. In order to maintain consistency across the same queries on the same dataset, we use the same seed in the pseudorandom noise, as in .

Deployment Considerations

We now discuss our approach in deploying such a system that integrated multiple components, including Pinot for data analytics, differentially private algorithms, and a privacy budget management system. Not knowing how external marketing partners would respond to budgeting access to queries and noisy results, we proceeded with a phased approach deploying our privacy system, first by turning on our privatized algorithms and only tracking usage of budget and then moving to enforce a given privacy budget. Recall that there are multiple parameters to set in our system and we detail the approach that we took to set them. Ultimately, our privacy approach was guided by developing differentially private algorithms so that privacy loss could be quantified and we focused on specific attacks for how to set parameters. Currently, the Audience Engagement API is still only available to a set of trusted users and pre-general availability (pre-GA).

Given the multiple teams and components that made up our privacy system, we wanted to better understand the impact to the customer when the various components were enabled. The main questions we faced included: how would external partners react with getting fewer results than they asked for (due to our private algorithms setting a data dependent threshold), and how much budget should we set without drastically modifying the behavior of how the external marketing partners interacted with the API. We then sought to answer each question separately, with a phased approach of turning on each component. The Audience Engagement API was planned to go through a soft launch period, followed by onboarding trusted partners, to then full scale deployment. This allowed us to use the stages to deploy the different components of our privacy system.

The main takeaway from the plots in Figure 5 is that we can set information and call budgets in a way that does not limit a vast majority of users. In particular, setting information budget to 3000 would not impact more than 93% of users and a call budget of 30 would not impact more than 95% of users.

2 Consistency and Data Refresh

It is important to point out, from a product utility perspective, that data consistency is crucial. Although this might seem to contradict the inherent randomness of differential privacy, we still want to ensure that if someone asks the same query, then they get the same result. To ensure consistent results, we use the pseudorandom seed generation from for our randomized algorithms. Hence, with the same query, we will use the same pseudorandom seed and hence the results will be the same, unless the underlying dataset has changed. The trusted parties who were granted access to the API all built UIs to facilitate access to their users, which prevents arbitrary query construction with small syntactic changes that leaves the semantics of the query unchanged.

This pseudorandom seed has an extra benefit for privacy as well, since if an analyst asks the same query multiple times, the random answers will not concentrate to the true answer. Ensuring that private answers do not concentrate to the true result is one of the primary reasons for the privacy budget management, but setting information cost and call cost to ensure that the exact same query ran repeatedly does not concentrate to the true value would lead to overly pessimistic budgets to the point that the privacy system is not usable.

The data for Audience Engagement is being placed into Pinot on a daily basis and retained for 30 days. Hence, each day the data can potentially change, but not within the same day. We then use the query and the date to determine the pseudorandom seed, otherwise if we only use the query, then the noise added to a specific query would always be the same, despite the data changing. Note that we further use a secure key in the pseudorandom seed so that one cannot determine the seed only from the query and the date.

Recall that we are assuming analysts do not collude with each other and do not share the privatized results they receive, since this would mean essentially multiplying the information and call budgets that we enforced. However, with the pseudorandom seed being generated the same way for all analysts, we know that each analyst is receiving the same result so that even if they colluded, they could not average their results to get more confidence in the true result.

3 Rationale for Parameters in our Privacy System

Part of the appeal of differential privacy is that it provides a worst case guarantee against privacy attacks, and can be simply stated as preventing an adversary from distinguishing whether a target’s data was used in the analysis or not. This strong protection stops being very meaningful once the privacy loss parameter $\varepsilon$ becomes large, say even larger than 1. However, deployments of differential privacy have quoted much larger privacy parameters than 1, see for example , and more recent works in private ML have used much larger parameters . Further, these quoted parameters are for a one time calculation, rather than over multiple queries. Only deploying privacy systems that incorporate differential privacy with small $\epsilon$ would limit its applicability. In particular, in our setting we might only be able to allow for a single top-10 result before an analyst has exhausted his or her budget. Boiling down the entire privacy considerations of a complicated system to whether a couple of parameters stay below some arbitrary privacy threshold for all deployments seems overly simplistic. Other privacy safeguards can be added to increase the overall privacy, such as subsampling the dataset, as is done in this application. Further, the parameters in our system allow us to easily improve the overall privacy gains by modifying parameters. Providing the tuning knob between 100% utility and 100% privacy is incredibly helpful in showing the impact that differential privacy has on the overall product.

The question then is, what protections can differential privacy provide, even with large $\epsilon$ parameters. For this, we consider several different attacks, each used to set a certain parameter. This is not meant as an exhaustive list of all the attacks we considered, nor does it mean that these certain attacks are expected. This is merely to provide additional context to how privacy parameters can be set and might be useful for other privacy practitioners to use.

We consider the scenario where the dataset remains the same over the course of the data retention period (30 days) and each day an analyst asks the same query on that dataset. Recall how we set a pseudorandom seed for the same query and that it changes each day. Thus, the analyst would get 30 different noisy results on the same count. We then want to know the probability that the average of these noisy values will be within a tolerance of the true value. We set this tolerance to $1/2$, since this would mean that the analyst rounding to the nearest integer would reveal the true count. We then want to determine the following probability where $X_{1},\cdots X_{30}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\texttt{Lap}(2/{\varepsilon_{\texttt{per}}})$,

We approximate this probability with a Normal distribution, so that we have

Our aim is to reduce the chance of this attack, while also not adding too much noise to each count. We then sought to ensure roughly a 90% chance of no such attack. Plugging in ${\varepsilon_{\texttt{per}}}=0.15$ leads to about an 11% probability of this attack being successful. Also recall that this attack will only be successful if the data does not change for the query over 30 days.

3.2 Determining Information Budget

One of the primary reasons for exploring differential privacy for this use case was differencing attacks. Consider the setting where an analyst asks two queries where they know that there is a single person different between the two in the unrestricted sensitivity setting. Despite the noise that we add to each count in each query, it is possible that the noise is small for some elements so it is clear what the true count was before noise. This happens when the noise is smaller than $1/2$ for a single count. Hence we want to compute the following probability, which can be written in terms of an exponential random variable Exp,

For a top-$k$ query, we can expect to see $pk$ (assume integer valued) many elements that have noisy count within half of the true count. If an adversary were to do a differencing attack, she would ask another top-$k$ query and there would be fresh noise added. Hence, there would again be an expected $pk$ many noisy counts that are close to the true counts. The adversary does not know which elements in both queries have noisy counts within $1/2$ of the true count, but we want to make sure these sets of elements do not overlap. If these elements with small noise do overlap in the two top-$k$ results, then a difference between the two results might show the actual difference between the two.

We now want to prevent the possibility of these small count elements to overlap in the two top-$k$ queries. Let’s fix the set of $pk$ elements that had noisy counts within half of the true counts in the first top-$k$. In the second top-$k$, we know that again there are expected to be $pk$ elements, but where they are is random. Hence we get a uniformly random set of $pk$ elements in the second top-$k$ result and want to know what is the expected size of the intersection between this set of $pk$ elements and the $pk$ elements from the first top-$k$. The probability that this intersection is of size $s$ is the following:

This is a hypergeometric distribution and has expectation $p^{2}k$. To reduce the chance that these two sets of size $pk$ overlap, we set the expected size of the intersection to be less than $1$, i.e. $k<1/p^{2}$.

Recall from the previous attack that we have ${\varepsilon_{\texttt{per}}}=0.15$, we get $p=0.0368$ and we then can use $k=738$. Our information cost is the total number of results that can be returned plus one for the optimized threshold calculation in the unknown domain setting, which would bound the information cost by $2k+2$, from these two top-$k$ results. Note that we also return counts for the elements that we find, which also increases the total information cost by $2k$. Hence, we can set information budget $k^{*}=4\cdot 738+2\approx 3000$, which from Figure 5, we see that more than 93% of analysts would not be impacted.

3.3 Determining δ𝛿\delta and Call Budget

Our unknown domain algorithms include a threshold so that elements with a single user contribution (unique count) should not be shown in any result. However, noise is added to the threshold to ensure differential privacy, so we want to be able to control the chance that a unique count with noise becomes larger than the noisy threshold. Hence, we want to bound the probability that this can occur for a single count and then take a union bound over all $\bar{d}$ counts that can be returned from Pinot. For the UnkGumb algorithm, we will write $Z_{1},Z_{2}\sim\texttt{Gumbel}(1/{\varepsilon_{\texttt{per}}})$ and $h_{(i)}$ as the $i$th ranked count in the input histogram $\mathbf{h}$. We then consider the following probability of a bad single event $B_{i}$ where $i\leq\bar{d}$

The worst case scenario is where every element in the histogram has count equal to 1, meaning only one user contributed to the counts and so each count is a unique count. Note that in UnkGumb, the threshold actually uses $\ln(\bar{k}/\delta)$ where there is an additional step to optimize from $\bar{d}$ to a smaller $\bar{k}$, but here we use the larger $\bar{d}$ to be more pessimistic. Noting that the difference $Z_{1}-Z_{2}$ is distributed as a logistic random variable Log, we have the following

We then want to bound the event that any of the $\bar{d}$ elements can appear above the threshold, hence

4 Overall Privacy Guarantee

In Table 2, we identify different use cases that have adopted differential privacy and have released their privacy parameters along with how often data and reports are refreshed, thus allowing us to compute daily and monthly DP parameters. We focused on deployments where data is continually updated in both local and global models of privacy. It is important to point out that each privacy system includes additional safeguards beyond differentially private algorithms. Some of these differences include subsampling users, permuting records, and the use of memoization, as in Google’s RAPPOR and Microsoft’s telemetry collection , to prevent longitudinal attacks when the same record is privatized with fresh noise repeatedly. What we account for in the table is if a user’s data changes in the local model then fresh noise would be added to each result and hence the privacy loss accumulates.

Conclusion

We have presented a privacy system that incorporates state of the art algorithms for releasing histograms and top-$k$ results in a differentially private way. Also, we have shown how we track the privacy budget for multiple analysts that can query our API. Combining the budget management service with DP algorithms allows us to make strong privacy guarantees of the overall system for any external partner that is allowed to make multiple, adaptively selected queries. This privacy system allows us to track the amount of information that is being released to external partners via the API in a precise way so that we can make informed decisions in how we can balance privacy safeguards with the usefulness of the product. We hope that this work demonstrates the feasibility of providing rigorous DP guarantees in systems that can scale.

We would like to thank Adrian Cardoso, Mark Cesar, Stephen Lynch, Sofus Macskassy, Koray Mancuhan, Sajjad Moradi, Sergey Yekhanin, and the entire LinkedIn Data Science Applied Research team for their helpful feedback on this work. Further, we thank Igor Perisic and Ya Xu for their support throughout this project.

References

Appendix A Omitted Analysis for Section 5.2

We now go through the analysis for Algorithm 3, in particular the proof of Lemma 5.3. The differences between Algorithm 3 and the version that appeared as Algorithm 4 in is that we are returning counts as well as indices, we do not limit the number of outcomes to be at most $k$ (since it is not a parameter), and we allow for counts to increase or decrease by $\tau\geq 1$ in neighboring datasets. As we will mainly be borrowing the analysis in we will change $\bar{d}$ to $\bar{k}$ to better match the statements in that work. We then introduce the following algorithm, which we will show has the same distribution as $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{k},\tau}(\mathbf{h})$.

We have the following that connects $\texttt{LapMax}^{\bar{k},\tau}$ with $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{k},\tau}$.

For any histogram $\mathbf{h}$, we have that both mechanisms $\texttt{LapMax}^{\bar{k},\tau}(\mathbf{h},\mathbf{d}^{\bar{k}}(\mathbf{h}))$ and $\texttt{Unk}\texttt{Lap}^{\bar{k},\tau}(\mathbf{h})$ produce outcomes that are equal in distribution.

If we fix a domain $\mathbf{d}$ beforehand, then we have the following privacy statement. Note that the privacy of $\texttt{LapMax}^{\bar{k},\tau}(\mathbf{h},\mathbf{d})$ follows from the Laplace mechanism being ${\varepsilon_{\texttt{per}}}$-DP. This is what allows us to output the counts as well as the indices. We just need to ensure that $i_{(\bar{k}+1)}\notin\mathbf{d}$ because then if it was, then changing one index would change the count of both $h_{(\bar{k}+1)}$ and $h_{\bot}=h_{(\bar{k}+1)}+\tau\left(1+\Delta\ln(\Delta/\delta)/{\varepsilon_{\texttt{per}}}\right)$.

For any fixed $\mathbf{d}\subseteq[d]$ and neighbors $\mathbf{h},\mathbf{h}^{\prime}$ such that $i_{(\bar{k}+1)},i^{\prime}_{(\bar{k}+1)}\notin\mathbf{d}$, then for any set of outcomes $T$,

As was done in Durfee and Rogers , we can carefully account for the good (can bound the privacy loss) and bad (can bound these events with small probability) sets. Note that the outcome set of $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{k},\tau}$ is a superset of Algorithm 4 in when $k=\bar{k}$, and it is straightforward to see that these algorithms have the same distribution with respect to index output (ignoring the counts output from $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{k},\tau}$). Therefore, all the bounds on the bad outcomes will still hold for our setting, and the analysis then follows from results in Section 6 of , where we state each result here.

Given two neighboring histograms $\mathbf{h},\mathbf{h}^{\prime}$, we define $\mathcal{S}_{\texttt{Lap}}$ as the outcome set of $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{k},\tau}(\mathbf{h},\mathbf{d}^{\bar{k}}(\mathbf{h}))$ (both indices and counts) and the outcome set of $\texttt{Unk}\texttt{Lap}^{\Delta,\bar{k},\tau}(\mathbf{h}^{\prime},\mathbf{d}^{\bar{k}}(\mathbf{h}^{\prime}))$ as $\mathcal{S}^{\prime}_{\texttt{Lap}}$.

We then define the bad outcomes as $\mathcal{S}^{\delta}_{\texttt{Lap}}:=\mathcal{S}_{\texttt{Lap}}\setminus\mathcal{S}^{\prime}_{\texttt{Lap}}$ and $\mathcal{S}^{\prime\delta}_{\texttt{Lap}}:=\mathcal{S}^{\prime}_{\texttt{Lap}}\setminus\mathcal{S}_{\texttt{Lap}}.$

For $\Delta$-restricted sensitivity neighbors $\mathbf{h},\mathbf{h}^{\prime}$, we have

For any neighboring histograms $\mathbf{h},\mathbf{h}^{\prime}$ and for any $S\subseteq\mathcal{S}_{\texttt{Lap}}\cap\mathcal{S}^{\prime}_{\texttt{Lap}}$, we let $\mathbf{d}^{\varepsilon_{\texttt{per}}}=\mathbf{d}^{\bar{k}}(\mathbf{h})\cap\mathbf{d}^{\bar{k}}(\mathbf{h}^{\prime})$ and we must have the following for $\bar{\delta}$ given in (3)

For any neighboring histograms $\mathbf{h},\mathbf{h}^{\prime}$ and any $S\subseteq\mathcal{S}_{\texttt{Lap}}$, then for $\bar{\delta}$ given in (3),

We use the above results to get the following inequalities.