Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

At a high level, core numbers measure the relative importance of vertices in a graph. Formally, given a graph $G$, the core number (or, coreness) of a vertex $v$ in $G$ is the largest $k_G(v)\in \mathbb{N}$ (or $k(v)$ if $G$ is clear from context) for which there exists a subgraph $H$ of $G$ containing $v$ such that every vertex in $H$ has induced degree $\ge k_G(v)$. In the $k$-core decomposition problem, the goal is to output core numbers of all vertices in G.²²2We note that the $k$-core decomposition problem in the literature is sometimes used to refer to the problem of computing a hierarchy of $k$-cores, which are subgraphs of $G$ induced by vertices with core number at least $k$ [49]; note that it is not possible to emit such a hierarchy privately, so we (and prior work) focus on privately emitting core numbers for every vertex.

This problem has recently received much attention from the database and systems communities due its applications in community detection [1, 28, 31], clustering and data mining [16, 51], and other machine learning and graph analytic applications [37, 18, 19]; for a more comprehensive survey, see [43]. Due to the rapid increase of applications using sensitive user data, designing private algorithms for this problem is becoming increasingly important.

An algorithm is a $(\varphi ,\zeta )$-approximation for the $k$-core decomposition problem if, for every vertex $v$ in the given graph, the estimate of the core number of $v$, as returned by the algorithm, lies between $k(v)-\zeta$ and $\varphi \cdot k(v)+\zeta$. Dhulipala et al. [20] gave the first differentially private $(2+\eta ,O({\epsilon }^{-1}{\log }^{3}n))$-approximation algorithm for $k$-core decomposition in the $\epsilon$-LEDP model, which runs in $O(\log n)$ rounds. They left it as an open question whether their multiplicative and additive approximation factors can be improved.

Our contributions. We answer their question in the affirmative. In particular, we give an exact (i.e., 1-approximate) algorithm and a $(2+\eta )$-approximate algorithm, both with $O({\epsilon }^{-1}\log n)$ additive error, which run in $O(n)$ and $O({\log }^{2}n)$ rounds, respectively.

Furthermore, we show that the additive errors of our algorithms are tight, by proving a matching lower bound of $\mathrm{\Omega }({\epsilon }^{-1}\log n)$ on the additive error of any constant-approximation algorithm in the centralized model (EDP), where the algorithm has full access to user data (here, the input graph). Since the centralized model is less restricted than the local model, the same bound holds in the LEDP model, regardless of round complexity. We also show that interactivity is needed if one wants an exact algorithm with polylogarithmic additive error, by proving a lower bound of $\mathrm{\Omega }(\sqrt{n})$ on the additive error of any exact, 1-round algorithm, when $\epsilon$ is a constant.

Another measure of importance, defined on subsets of vertices in a graph, is density. Formally, the density of a set of vertices $S$ in a graph $G$, denoted ${\rho }_G(S)$ (or simply $\rho (S)$), is the ratio of the number of edges in the subgraph induced by $S$ and the number of vertices in $S$, i.e., $|E(S)|/|S|$. In the densest subgraph problem, the goal is to output a set of vertices with the maximum density in a given graph.

This problem has been studied in the (centralized) private [29, 48], LEDP [21, 20], dynamic [13, 50], streaming [3, 12, 27, 46], and distributed [4, 53] settings; for a recent survey on densest subgraph and its variants, see [39].

An algorithm is a $(\varphi ,\zeta )$-approximation to the densest subgraph problem if the set of vertices $S$ returned by the algorithm has density $\rho (S)\ge {\rho }^{\ast }/\varphi -\zeta$, where ${\rho }^{\ast }$ is the maximum density. In the $\epsilon$-LEDP setting, Dhulipala et al. [20] gave a $(4+\eta ,O({\epsilon }^{-1}{\log }^{3}n))$-approximation for the densest subgraph problem. More recently, and concurrently with this work, Dinitz et al. [21] gave a $(2+\eta ,O({(\epsilon \eta )}^{-1}{\log }^{2}n))$-approximation algorithm, which runs in $O(\log n)$ rounds, in the $\epsilon$-LEDP setting, and as well as an $(1,O({\epsilon }^{-1}\sqrt{\log {\delta }^{-1}}\log n))$-approximation, which runs in $O(n^2\log n)$ rounds in the $(\epsilon ,\delta )$-LEDP setting. On the other hand, there is a lower bound of $\mathrm{\Omega }({\varphi }^{-1}\sqrt{{\epsilon }^{-1}\log n})$ on the additive error of any $\varphi$-approximate algorithm for densest subgraph that satisfies $(\epsilon ,\delta )$-edge differential privacy in the centralized model [29, 48] (when $\delta \le n^{-O(1)}$).

Our contributions. We give a condition on when a (private) $(\varphi ,\zeta )$-approximation algorithm for $k$-core decomposition can be transformed into a (private) $(2\varphi ,\zeta )$-approximation algorithm for densest subgraph. We show that our algorithms for $k$-core decomposition satisfy the condition, obtaining the following improved bounds for densest subgraph.

We also give a simple 1-round algorithm using the randomized response technique together with brute-force, exponential time search. We believe this algorithm serves as an interesting example of what a lower bound for 1-round algorithms must be able to reason about.

A low out-degree orientation of a (undirected) graph is an orientation of the edges of the graph such that the out-degree of any vertex is minimized. A low out-degree ordering is a permutation of the vertices, which implicitly encodes a low out-degree orientation, i.e., each edge is oriented from its earlier endpoint to its later endpoint (with respect to the permutation). In the low out-degree ordering problem, the goal is to output a low out-degree ordering of a given graph.

Differentially private low out-degree ordering was introduced by [20] as a way to release an implicit solution to the low out-degree orientation problem. The latter has attracted a lot of attention in the non-private setting (see, e.g., [9, 13, 38, 53] and references therein) and has been used to improve the running time of algorithms for matching [47, 33], coloring [34], and subgraph counting [7, 8, 42].

The degeneracy of a graph is the maximum core number of any vertex in the graph. It is known that degeneracy is equal to the minimum out-degree that is achievable through any ordering. Hence, we state the out-degree obtained through our algorithms in terms of $\alpha$, the degeneracy of the input graph. An algorithm is a $(\varphi ,\zeta )$-approximation for the low out-degree ordering problem if the algorithm’s output encodes an orientation where each vertex has out-degree at most $\le \varphi \cdot \alpha +\zeta$. In the $\epsilon$-LEDP model, Dhulipala et al. [20] gave a $(2+\eta ,O({\epsilon }^{-1}{\log }^{3}n))$-approximation to the low out-degree ordering problem, which runs in $O(\log n)$ rounds.

Our contributions. We improve the multiplicative factor and the additive error by giving an exact algorithm and a $(2+\eta )$-approximate algorithm, both with additive error $O({\epsilon }^{-1}\log n)$, which run in $O(n)$ and $O(\log n)$ rounds, respectively.

A (vertex) coloring of a graph $G$ is an assignment of labels (or, colors) from the set $\{1,\mathrm{\dots },n\}$ to the vertices of $G$. A coloring is $(c,d)$-defective if it uses at most $c$ different colors, and each vertex has at most $d$ neighbors with the same color; $d$ is the defectiveness of the coloring. In the defective coloring problem, the goal is to output a $(c,d)$-defective coloring of a given graph with small $c$ and $d$.

This problem (especially the case $d=0$) has been widely studied in a variety of settings including the (centralized) private [15], dynamic [11, 34, 35, 52], distributed [30, 32, 45], and streaming [2, 10, 6] settings. In the $\epsilon$-edge differential privacy setting, [15] recently gave the first $(c,d)$-defective coloring algorithm with $c=O(\mathrm{\Delta }/\log n+{\epsilon }^{-1})$ and $d=O(\log n)$, where $\mathrm{\Delta }$ is the maximum degree of the input graph. They also showed that $d=\mathrm{\Omega }(\log n/(\log c+\log \mathrm{\Delta }))$ defectiveness is necessary if $\le c$ colors are used. Although not explicitly stated, we believe their coloring algorithm can be also adapted to the $\epsilon$-LEDP setting with the same bounds.

Our contributions. Using the approximate low out-degree ordering results and MAT, we give new algorithms for defective coloring under LEDP. In particular, the number of colors used by our algorithms scales with the arboricity $\alpha$ instead of the maximum degree. In small-arboricity graphs, the number of colors used by our algorithm can be significantly smaller than that of [15].

All of the bounds in the above theorems are stated for $\epsilon$-LEDP algorithms but also are algorithms in the centralized model with the same approximation and additive error guarantees. All of our algorithms based on MAT can be implemented in the centralized model in near-linear time if we lose an additional multiplicative factor of $1+\eta$ for any given constant $\eta >0$. This nearly matches the best running times for sequential non-private $k$-core decomposition algorithms, while maintaining a near-optimal utility for private algorithms.

The recent concurrent, independent work of Dinitz et al. [21] provides a large set of novel results on $(\epsilon ,\delta )$-DP, $\epsilon$-LEDP, and $(\epsilon ,\delta )$-LEDP densest subgraph, improving on the approximation guarantees of previous results. Their work is based on a recent result of Chekuri, Quanrud, and Torres [14] and the parallel densest subgraph algorithm of Bahmani, Kumar, and Vassilvitskii [4]. They offer improvements in the bounds in the central DP setting via the private selection mechanism of Liu and Talwar [41]. Note that their techniques are different from those presented here; furthermore, any $c$-approximate algorithm for densest subgraph translates to a $2c$-approximate algorithm for finding the degeneracy of the input graph (which is the value of the maximum $k$-core). Thus, no densest subgraph algorithm can obtain a better than $2$-approximation of the maximum $k$-core value.

Using the MAT framework of this work, Dinitz et al. [22] gave new algorithms for node-differentially private bipartite matching, improving upon the results of [36]. They also gave the first algorithms for maximum matchings in general graphs under local edge-differential privacy, also crucially using the MAT framework. Complementing their algorithms, they show a matching lower bound for edge-private maximum matchings. This follow up work highlights the wide applicability of the MAT framework, giving nearly tight algorithms for various combinatorial problems under differential privacy.

Our new Multidimensional AboveThreshold (MAT) mechanism generalizes the AboveThreshold mechanism [24] to support a $d$-dimensional vector of queries. Conceptually, one may think of MAT as running $d$ copies of AboveThreshold in parallel, one per dimension. More precisely, suppose that the input dataset for (single-dimensional) AboveThreshold was from some domain $𝒳$, then the input for our mechanism is $X=(x_1,\mathrm{\dots },x_d)\in {𝒳}^d$, a $d$-tuple of elements from $𝒳$. Our mechanism takes as input an adaptively chosen sequence ${\overrightarrow{f}}_1,{\overrightarrow{f}}_2,\mathrm{\dots }$ of query vectors and a threshold vector $\overrightarrow{T}=(T_1,\mathrm{\dots },T_d)$. Each query vector specifies $d$ queries, one for each dimension of the dataset, i.e., ${\overrightarrow{f}}_i=(f_{i,1},\mathrm{\dots },f_{i,d})$ and query $f_{i,j}:𝒳\to ℝ$ is on element $x_j$. The goal is to (privately) return, after each query vector ${\overrightarrow{f}}_i$, a response vector ${\overrightarrow{a}}_i\in {\{\perp ,\top \}}^d$ indicating whether each query $f_{i,j}$ in the vector has crossed corresponding threshold $T_j$, i.e., ${\overrightarrow{a}}_i=(a_{i,1},\mathrm{\dots },a_{i,d})$ and $a_{i,j}$ indicates whether $f_{i,j}(x_j)\ge T_j$ ($\perp$ for “no”, $\top$ for “yes”). After some query $f_{i,j}$ has crossed its threshold, then all future queries $f_{i^{\prime },j}$, for $i^{\prime }>i$, on element $x_j$ are ignored (e.g., the response is always $\perp$). It is assumed that new query vectors are submitted until each element has had a query that has crossed its corresponding threshold. In a nutshell, MAT allows one to infer, for each element $x_j$, an estimate $\tilde{r}(j)$ of the index $r(j)$ of the first query $f_{r(j),j}$ on $x_j$ that crosses the threshold $T_j$.

We define a fairly technical condition on the sensitivity of the queries, generalizing the ${\mathrm{\ell }}_1$ sensitivity in the $1$-dimensional case, such that the error of MAT can be bounded in terms of the sensitivity. For intuition, we first describe a simple case of our sensitivity condition.

Suppose that two datasets $X=(x_1,\mathrm{\dots },x_d)$ and $X^{\prime }=(x_1^{\prime },\mathrm{\dots },x_d^{\prime })$ are neighboring only if they differ on at most $k\ll d$ coordinates, i.e., there exists a set $S\subseteq [d]$ of at most $k$ indices such that $x_i=x_i^{\prime }$ for all $i\notin S$ and $x_i\sim x_i^{\prime }$ for all $i\in S$. Furthermore, suppose that the absolute difference of each query (on the appropriate element in $X$ and $X^{\prime }$) is bounded by 1, i.e., for any query vector $\overrightarrow{f}=(f_1,\mathrm{\dots },f_d)$, each query $f_j$ satisfies $|f_j(x_j)-f_j(x_j^{\prime })|\le 1$. Since MAT runs $d$ copies of AboveThreshold in parallel and the queries are adaptive, applying concurrent composition [54] in this case would predict that the privacy loss is proportional to $d$. However, by coupling the outputs of the queries on the indices not in $S$ (where $X$ and $X^{\prime }$ are identical), it seems fairly intuitive that the actual privacy loss should be proportional to $k$. Hence, as the error of AboveThreshold is inversely proportional to the privacy loss parameter, to obtain $\epsilon$-differential privacy, we should have at most $k\ll d$ times the original error of AboveThreshold in this setting, i.e., $O(k{\epsilon }^{-1}\log n)$ with high probability.

More generally, for an arbitrary neighboring relation and arbitrary queries, roughly speaking, we define the sensitivity $D$ as the worst-case (over pairs of neighboring datasets $X$ and $X^{\prime }$) sum of the maximum absolute difference in the outputs of the queries (on $X$ and $X^{\prime }$); see Section 4 for a formal definition. In particular, for the simple case described above, $D=k$. Using this definition, we formalize the above intuition and prove that MAT guarantees an error of $O(D{\epsilon }^{-1}\log n)$ in our applications, with high probability.

We apply MAT to get new private algorithms for the $k$-core decomposition, densest subgraph, low out-degree ordering, and defective coloring problems. In each case, given a graph $G=(V,E)$ with $n$ vertices, we show that some non-private algorithm can be simulated via MAT, for suitable definitions of “dataset” and “queries”.

As a simple example, for the core decomposition problem, a dataset $X=(x_u:u\in V)$ is an $n$-tuple containing the set of neighbors $x_u$ of each vertex $u$ in $G$. (Hence, the domain $𝒳$ is the set of all subsets of $V$.) A query $f_S:𝒳\to ℝ$ counts the number of neighbors of the vertex that are not among some fixed set of vertices $S\subseteq V$, shifted by some fixed amount $i$, and “mirrored” by $n$, i.e., $f_S(x)=n-(|x\setminus S|-i)$. (Notice that $f_S(x_u)\ge n$ means that vertex $u$ has at most $i$ neighbors that are not among $S$.) In this case, the absolute difference of each query on two neighboring datasets (i.e., graphs that differ by at most an edge) is at most 1 and there are at most two elements that differ for two neighboring datasets (namely, at the endpoints of the differing edge). Hence, the simple case mentioned above applies and MAT guarantees an error of $O({\epsilon }^{-1}\log n)$, with high probability.

For core decomposition, we apply MAT to analyze a variant of the classic peeling algorithm of Matula and Beck [44], which iteratively peels (removes) the lowest degree vertex in the graph. In our variant of the classical algorithm, we view the algorithm as running $n$ iterations of a peeling process. In the $i$th iteration, the algorithm repeatedly peels all vertices with (induced) degree less than $i$ until none are left. It is known that, at the end of the $i$th iteration, a vertex is alive (has not been peeled) if and only if it is in the $i$-core. It can be shown that the peeling process can be simulated by MAT via the queries mentioned above. Hence, with some post-processing, we can obtain core numbers with no multiplicative factor and the optimal (up to a constant factor against our lower bound) additive error of $O({\epsilon }^{-1}\log n)$, with high probability. Similarly, we apply MAT to analyze the more round-efficient $(2+\eta )$-approximate core decomposition algorithm of [20], obtaining optimal error, with high probability.

Using our new core decomposition algorithms, we achieve improved additive error bounds for both the densest subgraph and low out-degree ordering problems. In particular, we show that the $2$-approximate densest subgraph with additive error $O({\epsilon }^{-1}\log n)$ is contained in the subgraph consisting of all vertices with the maximum estimated core numbers (as we run the peeling algorithm, it can be shown that these vertices necessarily induce a subgraph with sufficiently high minimum degree). Furthermore, all of our core decomposition algorithms directly return a low out-degree ordering with the same multiplicative and additive errors as the original core decomposition algorithms by taking the order in which the nodes are peeled.

We also apply MAT to defective coloring by using MAT to greedily pick colors for each vertex from the available colors that have not yet been occupied by too many neighbors. In particular, each dimension represents a vertex and color pair consisting of all vertices in the graph and all available colors. For dimension $j$ representing pair $(v,c)$, the queries ask whether the number of neighbors of $v$ colored with $c$ exceeded our defectiveness threshold $O({\epsilon }^{-1}\log n)$. If it has, we will remove $c$ from $v$’s available set of colors. Our low round coloring algorithm follows a similar structure, and is inspired by the non-private algorithm of [34] and uses our low out-degree ordering algorithm to implement a separate set of available colors for each of $O({\log }^{2}n)$ groups of vertices of similar core numbers.

Our lower bound for 1-round, exact core decomposition in the local model is obtained by reduction to a problem in the centralized model, for which there is a strong lower bound. Specifically, it is known that, to privately answer $\mathrm{\Theta }(n)$ random inner product queries on a secret ${\{0,1\}}^n$ vector, most responses need to have $\mathrm{\Omega }(\sqrt{n})$ additive error [17]. Recently, [26] gave an elegant lower bound on the additive error of 1-round triangle counting algorithms in the local model using similar techniques.

In our case, we define a class of “query graphs”, one per inner product query, in which the core number of a fixed vertex $x$ is (roughly) the answer to the query. In addition to $x$, there are some secret vertices (and other vertices). For each secret vertex $v$, the existence of the edge $\{v,x\}$ is private information (which depends on the secret vector). Crucially, all neighborhoods of $x$ and the secret vertices in any possible query graph appear in two specific query graphs, namely, ones corresponding to the all-ones and all-zeros query vectors, respectively. The neighborhoods of the remaining vertices do not depend on the secret vector.

Our approach to solving the inner product problem is now as follows. The centralized algorithm first simulates the 1-round local core decomposition algorithm on the two fixed graphs to determine the messages that $x$ and the secret vertices would send in any query graph and saves these messages. Subsequently, when answering a query, the centralized algorithm reuses the saved messages for $x$ and the secret vertices (without further privacy loss) when it simulates the core decomposition algorithm on the corresponding query graph. This allows it to answer many queries correctly.

Originally, we had a more complex, direct argument. We briefly mention it here to give an idea of what is going on “under the hood” of the reduction. Specifically, we showed that, on a class of random graphs (similar to the query graphs instantiated in our reduction), most transcripts of a 1-round core decomposition algorithm have the property that, conditioned on seeing the transcript, the coreness of some (fixed) vertex still has high variance, $\mathrm{\Omega }(n)$. This implies that the standard deviation of the additive error is $\mathrm{\Omega }(\sqrt{n})$. We prefer the reduction argument, as it is simpler and gives a stronger result.

In our single-round exact densest subgraph algorithm, the vertices send the server a noisy version of the incidence matrix of the graph by using randomized response. In particular, each vertex sends its row of the incidence matrix and, for each bit, it sends the actual bit with probability $p=e^{\epsilon }/1+e^{\epsilon }$; the flipped bit is sent with probability $1-p$. Using this, the server can create an unbiased estimator $\tilde{E}(S)$ for the number of edges $E(S)$ inside any fixed subset of vertices $S$. The key observation is that the standard deviation $\sigma$ of the estimated density, i.e., $\tilde{E}(S)/|S|$, is $O(1+{\epsilon }^{-1})$ and the estimated density is distributed binomially. Hence, by a Chernoff bound, the estimated density is $\mathrm{\Omega }(\sqrt{\log t})$ standard deviations away from the actual density with probability at most $1/t$. By taking a union bound over all $S$, we can upper bound the total error over all (exponentially many) subsets by $\alpha =O(\sigma \sqrt{n})$ with high probability. Hence, a brute-force, exponential-time search, which computes the maximum $\tilde{E}(S)/|S|$ over all subsets $S$, finds a subset whose density is at most $\alpha$ from the maximum density, with high probability. The union bound appears to be necessary, but it is conceivable that there are more clever search strategies that do not require looking at exponentially many subsets $S$.

Fix $G\sim G^{\prime }$ to be arbitrary edge-neighboring graphs. Let $𝒜(G)$ and $𝒜(G^{\prime })$ denote the random variable representing the output of Algorithm 1 when run on $G$ and $G^{\prime }$, respectively. For each coordinate $j\in [d]$, there is some $r(j)\in \{1,\mathrm{\dots },n+1\}$ such that the output satisfies $a_{\cdot j}\in {\{\top ,\perp \}}^{r(j)}$ and has the form that for all , $a_{i,j}=\perp$. We can assume without loss of generality that $a_{r(j),j}=\top$; if , this must be the case and if $r(j)=n+1$, we can simply ask an additional query which evaluates to $\mathrm{\infty }$, independent of the dataset. Our goal is to show that for any output $a$, we have

Observe that there are two sources of randomness in the algorithm: the noisy thresholds ${\widehat{T}}_j$ for each $j\in [d]$ and the perturbations of the queries ${\nu }_{i,j}$ for each $j\in [d]$, $i\in [r(j)]$. We fix the random variables ${\nu }_{i,j}$ for each $j\in [d]$ and by simply conditioning on their randomness; for neighboring graphs, we have a coupling between corresponding variables. For simplicity, we omit this from notation. The remaining random variables are ${\widehat{T}}_j$ and ${\nu }_{r(j),j}$ for each $j\in [d]$; we will be taking probabilities over their randomness. The main observation needed is that the output of $𝒜$ is uniquely determined by the values of $r(j)$ for each $j\in [d]$. Thus, we can define the (deterministic, due to conditioning on the probabilities) quantity

for each $j\in [d]$ so that the event that $𝒜(G)=a$ is equivalent to the event where

Let $p(\cdot )$ and $q(\cdot )$ denote the density functions of the random vectors consisting of $\widehat{T}(j)$ and ${\nu }_{r(j),j}$ for each $j\in [d]$. Thus,

Using $v_j^{\prime }$ to denote the value of ${\nu }_{r(j),j}$ and $t_j^{\prime }$ to denote the value of ${\widehat{T}}_j$,

Now, we make a change of variables from $\overrightarrow{v^{\prime }}$ to $\overrightarrow{v}$ and $\overrightarrow{t^{\prime }}$ to $\overrightarrow{t}$, with the change given by

for each $j\in [d]$. We have that $d{\overrightarrow{t^{\prime }}}_j=d{\overrightarrow{t}}_j$, and $d{\overrightarrow{v^{\prime }}}_j=d{\overrightarrow{v}}_j$ since the new variables differ from the old ones by a constant that is independent of $\overrightarrow{v}$ and $\overrightarrow{t}$. The term inside the indicator function in the integral now becomes

which on subtracting $g_j(G)-g_j(G^{\prime })$ gives

Thus, we can apply the change of variables to rewrite (3) as

Since we have conditioned on the randomness of ${\nu }_{i,j}$ for each $j\in [d]$ and , we have ${\Vert \overrightarrow{v^{\prime }}-\overrightarrow{v}\Vert }_1\le 2D$ and ${\Vert \overrightarrow{t^{\prime }}-\overrightarrow{t}\Vert }_1\le D$ since the vectors $f_{i\cdot }(G)$ have sensitivity $D$, implying that the vectors $g_{\cdot }(G)$ also have sensitivity $D$. This implies that $p({\overrightarrow{t}}^{\prime })\le \exp (\epsilon /2)\cdot p(\overrightarrow{t})$ and $q({\overrightarrow{v}}^{\prime })\le \exp (\epsilon /2)\cdot q(\overrightarrow{v})$ by the properties of the Laplace distribution. We can thus upper bound the above integral by

Rewriting the integral as the probability of an event, we get

Finally, by our observation in (2), this is equal to

Putting the inequalities together, we get

Since $G,G^{\prime }$ were arbitrary edge-neighboring graphs, this completes the proof. $◀$