An Unweighted Vertex Cover Algorithm: An Alternative View(Hallucinated edges) (Salar Moarref)

28 Nov

Remember that in class we talked about the Vertex Cover problem in the framework of differential privacy. In original form of the problem, we want to pick a set S of vertices of minimal size so that every edge in the graph is incident to at least one vertex in S. In the privacy-preserving version of the problem, the private information we wish to conceal is the presence of absence of each edge. We talked about a randomized algorithm which outputs a permutation of all vertices of the graph, and the vertex cover will be defined by picking, for each edge, whichever of its endpoints appears first in the permutation. We saw that this vertex cover is (2+O(1/\epsilon))-approximate and \epsilon-differentially private. The algorithm was based on a simple non-private 2-approximation to vertex cover [2] that repeatedly selects an uncovered edge uniformly at random, and includes a random end-point of the edge which can be viewed as selecting a vertex at random with probability proportional to its uncovered degree. We took this formulation and mix in a uniform distribution over the vertices, using a weight that will grow as the number of remaining vertices decreases:

Algorithm 1: Unweighted Vertex Cover [1]
let n \leftarrow |V|, V_1 \leftarrow V, E_1 \leftarrow E
for i = 1,2,..,n
let w_i \leftarrow (4/\epsilon) \times \sqrt{n/(n-i+1)}
pick a vertex v \in V_i with probability proportional to d_{E_i}(v)+w_i
output v. let V_{i+1} \leftarrow V_i \backslash \{v\}, E_{i+1} \leftarrow E_i \backslash (\{v\} \times V_i)
end for

As stated the algorithm outputs a sequence of vertices, one per iteration. As remarked above, this permutation defines a vertex cover  by picking the earlier occurring end point of each edge.

There is a slightly different way to implement the intuition behind the above algorithm: imagine adding O(1/\epsilon) “hallucinated” edges to each vertex (the other endpoints of these hallucinated edges being fresh “hallucinated” vertices), and then sampling vertices without replacement proportional to these altered degrees. However, once (say) n/2 vetices have been sampled, output the remaining vertices in random order. More specifically, given a graph G=(V,E), we mimic the randomized proportional-to-degree algorithm for \alpha n rounds where \alpha < 1, and output the remaining vertices in random order. That is, in each of the first  \alpha n rounds, we select the next vertex i with probability proportional to d(i)+1/\epsilon: this is equivalent to imagining that each vertex has 1/\epsilon “hallucinated” edges in addition to its real edges. When we select a vertex, we remove it from the graph, together with the real and hallucinated edges adjacent to it. This is equivalent to picking a random (real or hallucinated) edge from the graph, and outputting a random real endpoint. Outputting a vertex affects the real edges in the remaining graph, but does not change the hallucinated edges incident to other vertices.

The privacy analysis is similar to that of theorem 5.1 of [1]: if we assume weights being w_i = 1/\epsilon for the first \alpha n rounds and w_i=\infty for the remaining rounds, we will have 2\sum_{i=(1-\alpha)n}^{n}\frac{1}{iw_i} \leq \epsilon(\frac{2\alpha}{1-\alpha})-differential privacy.

To analyze the utility, we couple the algorithm with a run of the 2-approximation non-private algorithm A that at each step picks an arbitrary edge of the graph and then picks a random endpoint. We refer to vertices that have non-zero “real” degree at the time they are selected by our algorithm as interesting vertices: the cost of our algorithm is simply the number of interesting vertices it selects in the
course of its run. Let I_1 denote the number of interesting vertices it selects during the first \alpha n steps, and I_2 denote the number of interesting vertices it selects during its remaining (1 - \alpha)n steps, when it is simply ordering vertices randomly. Clearly, the total cost is I_1 + I_2. We may view the first phase of our algorithm as selecting an edge at random (from among both real and hallucinated ones) and then outputting one of its endpoints at random. Now, for the rounds in which our
algorithm selects a real edge, we can couple this selection with one step of an imagined run of A (selecting the same edge and endpoint). Note that this run of A maintains a vertex cover that is a subset of our vertex cover, and that once our algorithm has completed a vertex cover, no interesting vertices remain. Therefore, while our algorithm continues to incur cost, A has not yet found a vertex cover. In the first phase of our algorithm, every interesting vertex our algorithm selects has at least one real edge adjacent to it, as well as 1/\epsilon hallucinated edges. Conditioned on selecting an interesting vertex, our algorithm had selected a real edge with probability at least \epsilon' = 1/(1+1/\epsilon). Let R denote the random variable that represents the number of steps A is run for. E[R] \leq 2OPT since A is a 2-approximation algorithm. By linearity of expectation:

2OPT \geq E[R] \geq \epsilon' . E[I_1]

Gupta et. al in [1] show that most of the algorithm’s cost comes from the first phase and hence that I_2 is not much larger than I_1:

E[I_1] \geq \ln(\frac{1}{1-\alpha}) . E[I_2]

Combining these facts, we get that:

\frac{E[cost]}{OPT} \leq \frac{2}{\epsilon'}(1+\frac{1}{\ln((1-\alpha)^-1)})

[1] A. Gupta, K. Ligett, F. McSherry, A. Roth, and K. Talwar. Differentially private combinatorial optimization. Nov 2009

[2] L. Pitt. A simple probabilistic approximation algorithm for vertex cover. Technical report, Yale University, 1985


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: