extfieldsofstudy:
Computer Science
Physics

text:
Amplitude Amplification for Optimization via Subdivided Phase Oracle

We propose an algorithm using a modified variant of amplitude amplification to solve combinatorial optimization problems via the use of a subdivided phase oracle. Instead of dividing input states into two groups and shifting the phase equally for all states within the same group, the subdivided phase oracle changes the phase of each input state uniquely in proportion to their objective value. We provide visualization of how amplitudes change after each iteration of applying the subdivided phase oracle followed by conventional Grover diffusion in the complex plane. We then show via numerical simulation that for normal, skew normal, and exponential distribution of objective values, the algorithm can be used to amplify the probability of measuring the optimal solution to a significant degree independent of the search space size. In the case of skew normal and exponential distributions, this probability can be amplified to be close to unity, making our algorithm near deterministic. We then modify our algorithm in order to demonstrate how it can be extended to a broader set of objective value distributions. Finally, we discuss the speedup compared to classical schemes using the query complexity model, and show that our algorithm offers a significant advantage over these classical approaches.

I. INTRODUCTION
Grover's search algorithm [1] is one of the most celebrated quantum algorithms which demonstrated the computational power of quantum computers that classical computers cannot reach. The problem that Grover's algorithm solves can be explained as finding one of the t inputs among N total inputs that matches some certain constraints, f (x) = 1, given by an oracle function f (x). The assumption about the oracle is that nothing is known about its construction or whether the problem has any structure we can exploit to infer the solution from previously seen inputs and outputs. Grover's algorithm can accomplish this task in just O( N/t) queries, compared to the classical approach which requires O(N/t) queries as we need to exhaustively check all inputs.
Since the original algorithm proposed by Grover in 1996, there have been multiple advancements to the algorithm. It is shown that Grover's algorithm is a special case, and is optimal [2]- [4], of a more general approach, later known as "amplitude amplification" technique [5]- [9]. The use of a non-π phase shift in place of the usual π-flip of Grover oracle was investigated in [10]- [13] and later generalized into a technique to increase the success probability of Grover to unity [14], [15]. It also finds applications in solving the souffle problem, too few or too many iterations deteriorates the success probability, which is known as the fixed-point searching [16]- [19].
In recent years, there have been investigations on the viability of using amplitude amplification technique with a new variant of non-trivial phase shift oracle, one that does not simply recognize two classes of inputs but rather acts on each input uniquely depending on some cost functions [20]- [22]. In this paper, we aim to extend the use of this non-trivial phase shift oracle to solve combinatorial optimization problems, instead of the usual adaptive Grover's algorithm [23]- [25] where we try to find better solutions by running the algorithm repeatedly until we cannot find a better solution.
The contribution of this paper is to introduce the use of a non-trivial phase shift oracle which we refer to as a subdivided phase oracle (SPO) [20], replacing the canonical Grover oracle in the amplitude amplification process, to solve combinatorial optimization problems. We show that this approach can be used to efficiently find the solutions of a large class of optimization problems, characterized by a number of objective functions.
We describe the setting of maximization problems (section II) which we then discuss one approach to construct a subdivided phase oracle operator from the given objective function and how the objective values can be embedded into the phase of each basis state (section III). We define our algorithm and provide visualization of how amplitudes change after each iteration of applying the subdivided phase oracle followed by conventional Grover diffusion (inverse around the average). This modified amplitude amplification process is complex and non-trivial to mathematically derive closed form expressions. Instead, we give intuitions on how it can amplify the probability of measuring the solution states and discuss the relationship between the distribution of objective values, oracle construction, and performance of the algorithm (section IV). We then analyze the performance of the algorithm and show results via simulations of applying it to several classes of objective functions, plotting the probability of measuring the solutions with respect to the number of iterations (section V). We also discuss a dynamic approach where the oracle operator changes at each iteration depending on current amplitude values, although this approach is purely theoretical since it is impossible to keep track of all amplitudes in large space, it suggests that a heuristic or variational [26] approach may exist in selecting parameters to construct the oracle. We then propose a sampling scheme based on the modified amplitude amplification process, plot the trade-off between the number of sampling trials and iterations, and derive conditions to which the sampling scheme gives a better expected run time than classical sampling or exhaustive search (section VI). We end the paper by discussing possible ways of extending the ideas we present here, pointers to efficiently realize the subdivided phase oracle in circuit models, connections to QAOA [27]- [29] and pointers to make it variational, and utilizing the visualization we developed to create a more suitable diffusion operator to increase the performance of our algorithm (section VII).

II. OPTIMIZATION PROBLEM SETTING
The problem we consider is the combinatorial optimization problem. For example, "what is the shortest route starting from city A to city B given a map of roads currently available?". An optimization problem can be described by three elements; a set of all possible inputs X, an objective function f (x) defined over part of the input space, and a Boolean function g(x) which checks for the feasibility of the input. Using the above example, X refers to all possible routes connecting A and B, f (x) refers to the distance of each route, and since some roads might be closed due to constructions or accidents, g(x) refers to the state of whether a route can be used at the time of travel. The task is to find an input x ∈ X such that f (x) is the maximum or the minimum while g(x) = 1, arg max x∈X f (x) such that g(x) = 1. (1) In this study, we will focus on the combinatorial optimization problem, where the input is defined over the set of binary string x = {0, 1} n of length n, which gives N = 2 n possible inputs. The properties of problems we consider in this work and their objective functions are as follow: • We will only study the task of maximizing f (x). Since the minimization can be transformed into maximization by multiplying every objective value by −1. • We assume that all N inputs are feasible. Since the constraint function g(x) can be absorbed into where C is a positive constant chosen such that any feasible input has higher objective value than all unfeasible inputs (f (x) > f (y) for all x, y when g(x) = 1 and g(y) = 0). • We assume the range of f (x) are non-negative real values. Since we are considering finite search space, the objective values are bounded and minimum value exists.

III. SUBDIVIDED PHASE ORACLE
Here in place of the two-class recognition oracle O G which is used in amplitude amplification for canonical Grover, we will define O φ which changes the phase of each input in proportion to its objective value given by the objective function f (x). Even though the word "oracle" normally refers to a black-box Boolean function which recognizes solutions to decision or search problems, we will keep using it to refer to this phase shift operator to reflect the modification from amplitude amplification technique, and to be consistent with [20]- [22]. We will refer to the oracle used in this paper as the subdivided phase oracle or just the phase oracle, as taken from [20], since we subdivided the objective value into the phase of each state with equal proportion. In this section we will explain how one could construct a subdivided phase oracle from a given objective function.
The action of the phase oracle O φ is to embed the objective value into the phase of each computational basis state, where φ(x) is a function that maps the set of possible inputs {0, 1, 2, · · · , N − 1} to the phase angle with which each state is shifted in the range [θ, 2π + θ]. The mapping from objective where k is a parameter we can adjust and θ is the minimum objective value. The action of θ is to introduce a global phase which can be ignored, meaning the action of the phase oracle can be written as follows, We make a distinction between f (x) and φ(x) so that f (x) is always referred to the objective function while φ(x) is the mapped function that will be used to perform the phase shift to the computational bases. When the context is clear which k is used or when it is not important to denote the selected k value, we will omit the k and write the oracle as just O φ . From Eq. (4), it can be seen that the action of the oracle is invariant under shift of the objective values. Furthermore, the nature of the oracle does not depend nor exploit the structure of the problem, which leads to the following two simplifications: can be taken to be a non-decreasing function, f (x) ≤ f (y) for all x < y, since the action of oracle is invariant under input permutation. • We take the minimum objective value to be 0, f (x min ) = 0. As we have shown in Eq. (3) and Eq. (4) that the subdivided phase oracle is invariant under shift to the objective values.

IV. AMPLITUDE AMPLIFICATION USING PHASE ORACLE
Having established the problem definition, we now present our algorithm as below. Apply O φ (k) (Subdivided Phase Oracle) 5: Apply D (Diffusion Operator) 6: It has the same structure as Grover's algorithm but uses the subdivided phase oracle O φ (k) in place of the binary oracle operator. The diffusion operator is given by where I is the identity operator.
A. Visualizing the effect of subdivided phase oracle Before applying our algorithm to various optimization problems, it is in order to gain visual intuition about how it leads to amplitude amplification. Unlike the Grover's algorithm, where all vector amplitudes are real numbers, the subdivided phase oracle produces complex amplitudes. Therefore each amplitude corresponding to a computational basis state |x can be represented as a vector in the complex plane. Figure 1(a) represents the amplitudes of the equal superposition state |Ψ 0 , where all vectors are real and have the same length given by 1/ √ N , where N = 2 n . The action of the phase oracle O φ (k) is to rotate each vector corresponding to all the computational basis states around the origin as seen in Figure 1(b). This introduction of relative phases does not change the probabilities of measuring the individual computational basis state. The amplitude amplification occurs after the application of the diffusion operator D, which can be visualized in the following three steps: 1) Find the mean amplitude vector and scale its length by two, represented by a yellow arrow in Figure 1(c). 2) Compute the vector differences between the amplitude vectors and the scaled mean amplitude vector, depicted by purple arrows in Figures 1(d) and (e). 3) Finally, replace the old amplitude vectors with the newly computed vectors from Step 2. This effectively shifts these updated amplitude vectors to the origin, as shown in Figure 1(f). The vector corresponding to the probability amplitude of the optimal computational basis state representing the solution to the optimization problem is given by the most saturated red color in Fig. 1. We can see that application of the subdivided phase oracle followed by the diffusion operator increases its magnitude, amplifying the probability of measuring the optimal solution.

B. Amplifiability via subdivided phase oracle
Grover oracle, when viewed in the same picture can be tracked easily, as the π phase flip would make the group of marked state's amplitude vectors point to the reverse direction. When the diffusion operator is applied, the mean would lie on the real number line and after the difference vectors are created, all amplitude vectors would still lie on the real number line. It is noteworthy that when everything stays on the real number line, the amplitude of the marked states only gets larger when the mean vector is pointing in the opposite direction. The mean vector would get smaller and smaller after each iteration until it stops pointing in the opposite direction and starts to point in the same direction as vectors of marked states.
Sequences of applying O φ (k) followed by the diffusion operator lead to a more complex scenario than the Grover oracle, as both the directions and norm of the amplitude vectors and the mean vectors largely depend on the choice of O φ (k). The visualization that we discussed in the previous subsection however offers an intuitive picture when and how the subdivided phase oracles leads to amplitude amplification. Since we are interested in using this algorithm to solve optimization problems, we are only interested in the optimal state vector. The optimal state solution will grow larger up to a certain point and then shrink back and repeat this process in cycles. The condition when the vector gets larger after diffusion is only when ||2 where − → α denotes the amplitude vector. This means the angle between the mean vector and the amplitude vector of the optimal state θ( − → α best , − → α mean ) should be between π/2 and 3π/2 in order to observe significant amplitude amplification after every iteration of our algorithm. For angles outside this range, amplitude amplification occurs but its magnitude is only marginal. As we will see later, the choice of k affects this angle and hence the level of amplitude amplification.

V. RESULTS
Before we dive into the simulations and their results, we first need to discuss the connections between the objective function f (x) and the distribution of its mapped objective values. Recall that we want to have the angle between the best state amplitude vector and the mean vector be as close as opposite direction as possible, this success condition of the amplification relies heavily on the distribution of the objective values. Hence we will categorize the sets of simulations based on the density of the objective function.
In addition to the normal, skew normal, and exponential distributions, we consider the case where the objective function follows basic classes of polynomials and exponential. Although these objective functions are artificially generated and probably will not come up from natural real-world problems, we include them in our study to look at a more general behavior of the algorithm.

A. Normally distributed objective values
We begin by considering the objective values to be normally distributed according to the probability density function, where µ denotes the mean and σ the standard deviation of the distribution, as shown in Fig. 2(a). This is a natural assumption as many instances of NP-hard optimization problems can be transformed into the Ising problem [30]. Such problems can be described by using local interactions between a small number of bits of the entire bit string. This property in turn allows for the distribution of objective values of a randomly generated large instance of such NP-hard problems with local cost term sampled from a single distribution to be well approximated by a normal distribution. This approximation becomes more accurate with increasing size of the problem due to the central limit theorem and the law of large numbers.
Normal distribution is symmetric, which makes it possible for the phase difference between the mean amplitude vector and the optimal solution to be π, leading to excellent amplification results. In fact, using the visualization technique discussed in subsection IV-A, it is straightforward to observe that the mean amplitude vector and the vector corresponding to the optimal solution |N − 1 can be made to always lie on the real axis for appropriately chosen k.
Choosing k such that the mean amplitude vector and the solution vector to lie on the real axis is actually the optimal k value. Since the normal distribution is symmetric, it is the case that applying the algorithm does not only amplify the best state |N − 1 but it also amplify the worst state |0 to the same probability.

B. Skew normal distribution
We have demonstrated that optimization problems with normally distributed objective values can be tackled easily by our algorithm. The key property that made this possible was the symmetry of the normal distribution. Real-world optimization problems on the other hand are unlikely to possess such nice property. In this and the following subsections, we evaluate the performance of our algorithm for optimization problems with objective value distributions which are not symmetric. We show that not only do they not pose an obstacle to our algorithm, asymmetry in the distributions works in our favor.
To capture the deviation from normally distributed objective values we now turn to skew normal distributions, where φ norm (x) is the probability density function of the normal distribution given in Eq. (6), and The parameter α controls the shape of the distribution, as seen in Fig. 2(b)-(c). For α = 0, φ skew (x; α) becomes the normal distribution of Eq. (6), while for |α| > 0, the distribution in Eq. (7) becomes asymmetric. In the limit of α → ∞, φ skew (x; α) becomes a half-normal distribution. We observe that as for the case of a normal distribution, there is always an optimal parameter k which amplifies the amplitude of the optimal solution to a significant degree as depicted in Fig 2(e).

C. Exponential distribution
We have seen that our algorithm can be applied to optimization problems involving normal and skew normal distributions of objective values. In order to assess the applicability of the algorithm further, we expand our discussion to exponential distribution, where λ is the rate parameter, as depicted in Fig. 2(d).
Despite their rather different definitions, all three objective distribution functions described above share a number of important features when it comes to amplitude amplification, which we discuss in the following subsection.

D. Common observations
We have seen how Algorithm 1 can be applied to optimization problems with normal, skew normal, and exponential distribution of objective values. In Fig. 2(e), we display how the probability of measuring the optimal value, P solution , gets amplified with every successive application of the subdivided phase oracle O φ (k) and the diffusion operator D. Initially, P solution = 1/N ≈ 0, as the input size of the optimization problem is set to N = 2 25 . We observe that the type of distribution affects both how many iterations are needed to achieve the maximum amplitude amplification, given by P * solution , as well as the value of P * solution . Interestingly, when the objective values are distributed according to the normal distribution, Algorithm 1 yields P * solution ≈ 0.5. For the case of the two asymmetric objective value distributions on the other hand, the probability of measuring the optimal value gets amplified more strongly. P * solution = 0.94 for the skew normal distribution, and P * solution = 0.97 for the exponential distribution. Figure 2(e) displays the number of iterations needed to achieve maximum amplification of the optimal solution. Extending the number of iterations further reveals that P solution begins to oscillate as depicted in Fig. 3. This is reminiscent of the behavior observed in amplitude amplification using the conventional binary oracle. Unlike the binary oracle, the oscillations of P solution display amplitude modulation not observed previously, leading to a number of oscillations of P solution before the value of P * solution is reached again. This beating behavior is a consequence of the fact that the subdivided phase oracle introduces complex probability amplitudes into the state vector |Ψ j . This basic pattern is observed for all distributions and tested objective functions. Increasing k in the subdivided phase oracle O φ (k) leads to decreased frequency of these oscillations.
As discussed in Section IV, in order to obtain the maximum probability P * solution , we have to choose the optimal k in the subdivided phase oracle O φ (k). Algorithm 1 is sensitive to this choice and deviating from the optimal k rapidly decreases the achievable amplitude amplification. In Fig. 4, we show how the maximum amplified probability P * solution depends on the deviation of k from its optimal value for normal and skew normal distributions.
In Grover's algorithm or the usual amplitude amplification algorithm, if the diffusion operator is kept the same, being the inversion around the mean operator 2 |Ψ 0 Ψ 0 | − I, it is known that in large search space, only π phase shift on the solution states are acceptable. And if one were to change the oracle to use phase angle other than π, one would need to change the diffusion operator to match the angle of the oracle under some constraints as explored in [10], [12]. The same effect can also be seen in our results in Fig 3. The sensitivity to the angle or the k value is not just for the efficiency in terms of number of iterations but is crucial in order to make algorithm 1 work.
An important observation to make at this point is that the effectiveness of our algorithm is not affected by the size of the input space. This is a desired feature and signifies the applicability of our subdivided phase oracle approach to optimization even for extremely large data sets. Below, we discuss optimization problems which do not share this property and the degree of amplitude amplification diminishes with increasing input space. This will lead to a modified algorithm which overcomes this issue.

E. Overcoming size-induced limits to amplifiability
We have seen above that Algorithm 1 possesses a number of desired properties when applied to common distributions of objective values. One such property is that its effectivity does not diminish with increasing size of the input space of the optimization problem. In this subsection we demonstrate that this is not always the case and introduce a modification to Algorithm 1 that counteracts this issue.
We focus on the following group of objective functions, They map each state to a unique object value, therefore we refer to them as injective objective functions. These injective objective functions are not likely to appear naturally in optimization problems in this simple form. However, they serve the purpose of demonstrating an important property of Algorithm 1 that may be encountered when using objective functions not explicitly covered in our manuscript. The primary quantity that we are concerned about in this subsection is the relative amplified probability of the optimal solution, P solution , with its initial value, P initial = 1/N , before the first iteration of Algorithm 1. In particular, we are interested in determining how the ratio P solution /P initial behaves for increasing input size space N . Figure 5 displays the scaling of this probability ratio as a function of the number of iterations of Algorithm 1 for increasing N . Interestingly, we can observe that the ratio P solution /P initial converges to a single curve for increasing N . This is in stark contrast to behavior observed for normal, skew normal, and exponential distributions where the optimal solution amplitude could be amplified easily independently of the input space size N .
One might suspect that we would see a different picture if we fix the objective value ranges but increase the possible data points in between while keeping the density fixed (sampling more from the same density). Instead of mapping |x to x, we map |x to x/m where m is some constant and our total states then become mN instead of N . We would still see the same picture, the highest achievable probability relative to initial 1/N approach a certain limit. Figure 5 shows the behavior of f q (x) = x 2 but identical observations were made for the remaining injective objective functions as well. In the remainder of this section, we present a modification that overcomes this size-induced limit to amplification.
So far we have only considered applying O φ (k) with constant k for all iterations of the algorithm. There are no real restrictions that this must be the case, and in fact, we can show that by changing the parameter k to the operator O φ (k) for each iteration, we can achieve better results and overcome the above mentioned issue. Recall that in Fig 3, the general trend is that the smaller the phase angle we choose, the shorter the period of the oscillating probability. This gives us some intuition that a smaller angle can be used in early iterations to quickly boost the amplitude of the solution state then later use a larger angle which allows it to get past the amplification limit of the smaller angle. An interesting effect of varying the k at each iteration is that it allows the injective objective functions case to get past the negligible boosted probability limit by a single fixed k. We show in Fig 6 for injective families the probability of measuring the solution state at each iteration when using a greedy approach. O φ at each iteration is chosen such that the P (|N − 1 ) is highest by scanning the range of k.  26 . O φ (k) for each line is constructed using the same k which is optimal or very close to optimal. Different colors denote different size in state space. The highest probability relative to initial probability approach a certain value when N grows. Noted that the optimal state |N − 1 for each line is different but the objective functions are the same.
Although the greedy approach to dynamically choose k is not the optimal strategy, it serves as one point in favor of evidence that in general even the injective families of objective functions which cannot be boosted via a fixed choice of O φ (k) are boostable with this amplitude amplification technique.
One way to avoid dealing with the complexity when using the subdivided phase oracle O φ is to alternate the direction of the rotation for each iteration which can be done by applying O φ (k) on the even iteration and O φ (−k) on the odd iteration. This way the mean vector can be tracked easily as it always stays on the same axis throughout all iterations. Although this approach solves the problem of choosing the optimal k since the algorithm performs best when k approaches 0, the number of iterations requires to amplify the probability grows much quicker than the fixed k method, and the magnitude of the solution state is smaller. One interesting side effect of this approach is that the states with objective value f (x) higher than the mean get larger while those lower than the mean get smaller. This approach of alternating between O φ (k) and O φ (−k) was explored in detail in [21] with the help of an interference pattern created by adding one ancilla qubit to select the rotation direction in superposition which can be thought of as doubling the number of amplitude vectors and splitting them into two groups. Having them rotate in opposite directions forces the mean vector to always stay on the real number line.

VI. QUANTUM ADVANTAGE
We have shown that using our modified amplitude amplification algorithm, it is possible to raise the probability of measuring the solution to a significant degree depending on the distribution of objective values. Since the amplified probability does not reach unity, we still need to resort to classical random sampling after applying the amplitude amplification algorithm. If we look at Fig 2(e), the increase in probability P solution is faster for the first half than the later half of the iterations required to reach the peak which means that there is an optimal stopping point in which would give us smaller total overall complexity.
In order to properly quantify the speedups against classical scheme, we will use 'expected number of trials' to compare quantum and classical schemes. Let us define: where P C (P Q ) is the probability of measuring the solution classically (quantumly using Algorithm 1), and E C (E Q ) is the expected number of queries to get (measure) the solution classically (quantumly), t is the number of iterations or time step count for each trial in the quantum case, and P(|N − 1 ) is the probability of measuring the optimal solution state |N − 1 .
We make a reasonable simplification that we treat one iteration of the amplitude amplification algorithm as a single query. Query complexity is the most used metric to quantify the speedups of Grover's algorithm and amplitude amplification thus we will use this in the same manner.  Fig. 2. Location of the minimum of E Q indicates the optimal stopping point for the Algorithm 1 after which sampling the state vector |Ψ j leads to the best result.
As we have seen in the previous sections, the increase in probability does not scale linearly with number of iterations, hence it is not always the optimal strategy to sample after boosting the probability of the solution state to the highest but rather boost it enough such that the expected number of trials is minimum. Using the simulations and objective functions mentioned in the previous section, Fig 7 shows the expected number of queries and the trade-off between further amplifying the probability and the number of sampling. Now that we have defined the expected number of trials to get the optimal solution, we will look at another metric, the success probability of finding the solution. Since one trial has the success probability P (|N − 1 ), the success probability when we sample for p trials is Using the values obtained in Section V, we see that even a very small number of trials p yields probability of success to be very close to unity.

VII. CONCLUSION
Even though Amplitude amplification has been known since its discovery decades ago as one of the key quantum tools for achieving an advantage over classical computers, there are still many things to be learned from it. In this paper, we showed evidence that the amplitude amplification algorithm in combination with subdivided phase oracle can be used to solve optimization problems, and depending on the structure and distribution of their objective values, an advantage can be gained over classical schemes. Using a fixed angle oracle O φ (k), normal distribution of objective values can be amplified such that the probability of observing the solution state is of a significant degree. In the case of skew normal and exponential distributions, this probability becomes near unity. If changing k at each time-step is allowed, the algorithm is general enough to amplify other distributions of objective values, such as those that are uniform or the injective objective functions. The process of choosing an optimal k is non-trivial and needs further study but it has shown promising path in the next step to the more general amplitude amplification of more than two classes of inputs.
There are still so many things to be learned from using the subdivided phase oracle with the diffusion operator, such as the mathematical derivation of the process explained in section III or the methods of choosing k when little is known about the problem. The visualization technique that we developed and propose in this paper, albeit a simple approach, should be proved useful in designing a better suited diffusion operator to be used with respect to the choice of O φ (k) and the distribution. As with past research on Grover's algorithm, it is known that there is a relationship between the choice of phase shift operator and the angle of diffusion operator for the unstructured search. It will be interesting to see if the same thing can be derived when the oracle does not separate two groups of states but each of them uniquely.
From another perspective, the whole process can be viewed as a form of QAOA [27], [29], replacing the mixer layer with the diffusion operator [28]. Applying the low-depth QAOA might be a good starting point for selecting k and from there we can vary k using some heuristic algorithm.
Another approach to ease the sensitivity of the choice of k and to improve the potency of the algorithm is to transform the objective function f (x) into another function that exhibits better characteristics. So far we have only discussed the theoretical aspect of using this algorithm without mentioning the implementation. The embedding of objective function could be referred to the ideas presented in [24], [25] where techniques of directly embedding polynomials can be done without the need for ancilla qubits which might enable the idea of transforming the objective function without an excessively complex circuit design.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation

This paper addresses active re-identification attacks in the context of privacy-preserving social graph publication. Active attacks are those where the adversary can leverage fake accounts, a.k.a. sybil nodes, to enforce structural patterns that can be used to re-identify their victims on anonymised graphs. In this paper we present a new probabilistic interpretation of this type of attacks. Unlike previous privacy properties, which model the protection from active adversaries as the task of making victim nodes indistinguishable in terms of their fingerprints with respect to all potential attackers, our new formulation introduces a more complete view, where the attack is countered by jointly preventing the attacker from retrieving the set of sybil nodes, and from using these sybil nodes for re-identifying the victims. Under the new formulation, we show that the privacy property $k$-symmetry, introduced in the context of passive attacks, provides a sufficient condition for the protection against active re-identification attacks leveraging an arbitrary number of sybil nodes. Moreover, we show that the algorithm K-Match, originally devised for efficiently enforcing the related notion of $k$-automorphism, also guarantees $k$-symmetry. Empirical results on several collections of synthetic graphs corroborate that our approach allows, for the first time, to publish anonymised social graphs (with formal privacy guarantees) that effectively resist the strongest active re-identification attack reported in the literature, even when it leverages a large number of sybil nodes.

Introduction
The last decade has witnessed a formidable explosion in the use of social networking sites. Although the discipline of social network analysis has existed already for quite some time, today's scientists potentially have access as never before to massive amounts of social network data. Social graphs are a particular example of this type of data, in which vertices typically represent users (e.g. Facebook or Twitter users, e-mail addresses) and edges represent relations between these users (e.g. becoming "friends", following someone, exchanging e-mails). The analysis of social graphs can help scientists and other actors to discover important societal trends, study consumption habits, understand the spread of news or diseases, etc. For these goals to be achievable, it is necessary that the holders of this information, e.g. online social networks, messaging services, among others, release samples of their social graphs. However, ethical considerations, increased public awareness, and reinforced legislation 1 place an increasingly strong emphasis on the need to protect individuals' privacy via anonymisation.
Social graphs have proven themselves a challenging data type to anonymise. Even a simple undirected graph, with arbitrary node labels and no attributes on vertices or edges, is susceptible of leaking private information, due to the existence of unique structural patterns that characterise some individuals, e.g. the number of friends or the relations in the immediate vicinity [31]. Many privacy attacks that solely rely on the underlying graph topology of the social graph exist [1], and they are still effective [28], despite advances on social graph anonymisation. A particularly effective privacy attack is the so-called active attack, which uses a strategy consisting in inserting fake accounts, commonly referred to as sybils, into the real network. Once inserted, these fake users interact with legitimate users and among themselves, and create structures that allow the adversary to retrieve the sybil nodes from a sanitised social graph and use the connection patterns between sybils and legitimate nodes to re-identify the original users and infer sensitive information about them, such as the existence of relations.
The publication of social graphs that effectively resist active attacks was initially addressed by Trujillo-Rasua and Yero [40]. They introduced the notion of (k, )-anonymity, the first privacy property to explicitly model the protection of published graphs against active adversaries. A graph satisfying (k, )-anonymity ensures that an adversary leveraging up to sybil nodes and knowing the pairwise distances of all victims to all sybil nodes, is still unable to distinguish each victim from at least k − 1 other vertices in the graph. This privacy property served as the basis for defining several anonymisation methods for a particular case, namely the one where either k > 1 or > 1 [29,26]. In other words, nontrivial anonymity (k > 1) was only guaranteed against an adversary leveraging exactly one sybil node. Later, the introduction of the notion of (k, )-adjacency anonymity [27] allowed to arbitrarily increase the values of k for which a formal privacy guarantee can be provided, but the proposed methods remained unable to address scenarios where the adversary can leverage more than two sybil nodes. In consequence, until now no anonymisation method with theoretically sound privacy guarantees against active attackers leveraging three or more sybil nodes has been made available to data publishers.
To remedy the aforementioned situation, in this paper we take a different approach to the problem of anonymising a graph that may have been victim of an active attack. Our approach differs from the ones based on (k, )-(adjacency) anonymity in the fact that it quantifies the combined probability of success of the attacker in re-identifying her sybil nodes and using them to re-identify the victims, whereas (k, )-(adjacency) anonymitybased methods implicitly assume that the adversary cannot be prevented from retrieving the sybil nodes, and (over-)compensate for this by quantifying the probability that victims are re-identified in terms of any vertex subset satisfying some minimal constraints. Our new approach leverages a new probabilistic interpretation of the adversary's success probability in the two stages of re-identification. This new formulation allowed us to point out some mismatches between the goal of privacy-preserving publication, namely ensuring some upper bound on the probability of each victim being re-identified, and the actual guarantees provided by existing privacy properties. As an interesting observation, we noticed that there exist graphs that, despite failing to satisfy existing formal privacy properties, are in fact secure against active attackers. More importantly, our new formulation allowed us to prove that k-symmetry [44], an existing privacy property originally introduced for the scenario of passive attacks, i.e. attacks that do not use sybil accounts, guarantees an 1/k upper bound on the re-identification probability of each victim, regardless of the number of sybil nodes used by the adversary. This finding is of paramount importance, as it enables the use of any known anonymisation method ensuring k-symmetry for preventing active re-identification attacks via sybil subgraph obfuscation. In this sense, we additionally show that the algorithm K-Match [48], originally devised for efficiently enforcing the notion of k-automorphism, also provides a sufficient condition for ensuring k-symmetry. Summary of contributions: • We show that no privacy property in the literature characterises all anonymous graphs with respect to active attacks.
• We introduce a general definition of resistance to active attacks that can be used to analyse the actual resistance of a graph.
• We use the introduced privacy model to prove that k-symmetry, the strongest notion of anonymity against passive attacks, also protects against active attacks.
• Of independent interest is our proof that k-automorphism does not protect against active attacks. This is a surprising result, considering that k-automorphism and k-symmetry have traditionally been deemed as conceptually equivalent.
• We prove that the algorithm K-Match, devised to ensure a sufficient condition for k-automorphism, also guarantees k-symmetry.
• We provide empirical evidence on the effectiveness of K-Match as an anonymisation strategy against the strongest active attack reported in the literature, namely the robust active attack presented in [28], even when it leverages a large number of sybil nodes.
Structure of the paper. We discuss related work in Section 2, and describe our new probabilistic interpretation of the adversarial model for active re-identification attacks in Section 3. Then we discuss the applicability of k-symmetry for modelling protection against active attackers in Section 4, and show in Section 5 that the algorithm K-Match efficiently provides a sufficient condition for k-symmetry. Finally, we empirically demonstrate the effectiveness of K-Match against the robust active attack from [28] in Section 6 and give our conclusions in Section 7.

Related work
In this paper we focus on a particular family of properties for privacy-preserving publication of social graphs: those based on the notion of k-anonymity [38,39]. These privacy properties depend on assumptions about the type of knowledge that a malicious agent, the adversary, possesses. According to this criterion, adversaries can be divided into two types. On the one hand, passive adversaries rely on information that can be collected from public sources, such as public profiles in online social networks, where a majority of users keep unmodified default privacy settings that pose no access restrictions on friend lists and other types of information. A passive adversary attempts to re-identify users in a published social graph by matching this information to the released data. On the other hand, active adversaries not only use publicly available information, but also attempt to interact with the real social network before the data is published, with the purpose of forcing the occurrence of unique structural patterns that can be retrieved after publication and used for learning sensitive information. k-anonymity models against passive attacks. k-anonymity is based on a notion of indistinguishability between users in a dataset, which is used to create equivalence classes of users that are pair-wise indistinguishable to the eyes of an attacker. Formally, given a symmetric, reflexive and transitive indistinguishability relation ∼ on the users of a graph G, G satisfies k-anonymity with respect to ∼ if and only if the equivalence class with respect to ∼ of each user in G has cardinality at least k. Several graph-oriented notions of indistinguishably appear in the literature. For example, Liu and Terzi [21] consider two users indistinguishable if they have the same degree. Their model is known as k-degree anonymity and gives protection against attackers capable of accurately estimating the number of connections of a user. The notion of k-degree anonymity has been widely studied, and numerous anonymisation methods based on it have been proposed, e.g. [22,4,10,42,23,36,34,5]. Zhou and Pei [47] assume a stronger attacker able to determine not only the connections of a user u, but also whether u's friends (i.e. those users that u is connected to) are connected. This means that the adversary is assumed to know the induced subgraphs created by the users and their neighbours. It is simple to see that Zhou and Pei's model, known as k-neighbourhood anonymity, is stronger than k-degree anonymity.
The notion of k-automorphism [48] was introduced with the goal of modelling the knowledge of any passive adversary. Two users u and v in a graph G are said to be automorphically equivalent, or indistinguishable, if ϕ(u) = v for some automorphism ϕ in G. The notion of k-automorphism ensures that every vertex in the graph is automorphically equivalent to k − 1 other vertices. Although k-automorphism itself does not in general imply all other privacy properties (as we will show in Appendix A), the method proposed in [48] for enforcing the (stronger) k different matches principle does achieve this goal. Similar formulations of indistinguishability in terms of graph automorphisms were presented independently in the work on k-symmetry [44] and k-isomorphism [9]. While ksymmetry and k-automorphism have traditionally been viewed as equivalent, k-symmetry is actually stronger, and it does imply all other privacy properties for passive attacks. In this paper, we additionally show that, in the context of active attacks, k-symmetry always guarantees a 1/k upper bound on the re-identification probability for each vertex, which k-automorphism does not.
A natural trade-off between the strength of the privacy notions and the amount of structural disruption caused by the anonymisation methods based on them has been empirically demonstrated in [48]. The three privacy models described above form a hierarchy, which is displayed in the left branch of Figure 1. Privacy models tailored to active attacks also form a hierarchy, displayed in the right branch of Figure 1, which we describe next. Interrogation marks in Figure 1 indicate that connections between properties tailored for passive attacks and those tailored for active attacks have not been established yet, neither directly nor via some additional property. k-anonymity models against active attacks. Backstrom et al. were the first to show the impact of active attacks in social networks back in 2007 [2]. Their attack has been optimised a number of times, see [32,33,28], and two privacy models particularly tailored to measure the resistance of social graphs to this type of attack have been recently proposed [40,27]. The first of those models is (k, )-anonymity, introduced in 2016 by Trujillo-Rasua and Yero [40]. They consider adversaries capable of re-identifying their own sets of sybil nodes in the anonymised graph. Adversaries are also assumed to know or able to estimate the distances of the victims to the set of sybil nodes. This last assumption was weakened later in [27] by restricting the adversary's knowledge to distances between victims and sybil nodes of length one. That is, the adversary only knows whether the victim is connected to a sybil node. That restriction led to a weaker version of (k, )-anonymity called (k, )-adjacency anonymity, as displayed in Figure 1.
There exist three anonymisation algorithms [29,26,27] that aim to create graphs satisfying (k, )-(adjacency) anonymity. Their approach consists in determining a candidate set of sybil vertices in the original graph that breaks the desired anonymity property, and forcing via graph transformation that every vertex has a common pattern of connections with the sybil vertices shared by at least k − 1 other vertices. A common shortcoming  Figure 1: A hierarchy of privacy properties. An arrow has the standard logical interpretation, i.e. P =⇒ P means that a graph satisfying P also satisfies P . Left side: models for passive attacks. Right side: models for active attacks. Interrogation marks indicate connections that have not been established yet.
of these methods is that they only provide formal guarantees against attackers leveraging a very small number of sybil nodes (no more than two). This limitation seems to be an inherent shortcoming of the entire family of properties of which (k, )-anonymity and (k, )-adjacency anonymity are members. Indeed, for large values of , which are required in order to account for reasonably capable adversaries, anonymisation methods based on this type of property face the problem that any change introduced in the original graph to render one vertex indistinguishable from others, in terms of its distances to a vertex subset, is likely to render this vertex unique in terms of its distances to other vertex subsets. An approach that has been used against both types of attack, passive and active, consists in randomly perturbing the graph. While intuition suggests that the task of reidentification becomes harder for the adversary as the amount of random noise added to a graph grows, no theoretically sound privacy guarantees have been provided for this scenario. Moreover, it has been shown in [28] that active attacks can be made robust against reasonably large amounts of random perturbation. Other privacy models. For the sake of completeness, we finish this brief literature survey by mentioning privacy models that aim to quantify the probability that the adversary learns any sort of sensitive information. A popular example is differential privacy (DP) [11], a semantic privacy notion which, instead of anonymising the dataset, focuses on the methods accessing the sensitive data, and provides a quantifiable privacy guarantee against an adversary who knows all but one entry in the dataset. In the context of graph data, the notion of two datasets differing by exactly one entry can have multiple interpretations, the two most common being edge-differential privacy and vertex-differential privacy. While a number of queries, e.g. degree sequences [18,14] and subgraph counts [46,17], have been addressed under (edge-)differential privacy, the use of this notion for numerous very basic queries, e.g. graph diameter, remains a challenge. Recently, differentially private methods leveraging the randomized response strategy for publishing a graph's adjacency matrix were proposed in [37]. While these methods do not necessarily view vertex ids as sensitive, data holders whose goal in preventing re-identification attacks is to prevent the adversary from learning the existence of relations may view this approach as an alternative to kanonymity-based methods. Another DP-based alternative to k-anonymity-based methods consists in learning the parameters of a graph generative model under differential privacy and then using this model to publish synthetic graphs that resemble the original one in some structural properties [30,35,43,45,16,8].
Other privacy models rely on the notion of adversary's prior belief, defined as a probability distribution on sensitive values. For example, t-closeness [20] measures attribute protection in terms of the distance between the distribution of sensitive values in the anonymised dataset with respect to the distribution of sensitive attribute values in the original table. Such definition of prior belief is different to other works, such as (ρ 1 , ρ 2 )privacy [13] and -privacy [24], where prior belief represents the adversary's knowledge in the absence of knowledge about the dataset. In either case, estimating the prior belief of the adversary is challenging, as discussed in [11]. Concluding remarks. As illustrated in Figure 1, the development of k-anonymity models against passive and active attacks have been traditionally split and had no apparent intersection. This article provides, to the best of our knowledge, the first connection between the two developments. This is achieved by introducing a probabilistic model for active attacks that characterises all graphs that resists active attacks, of which k-symmetry and (k, )-anonymity are proven to be sufficient, yet not necessary, conditions.

Probabilistic adversarial model
Our adversarial model is a generalisation of the model introduced in [28], which captures the capabilities of an active attacker and allows one to analyse the resistance of anonymisation methods to active attacks. Such analysis is expressed as a three-step game between the attacker and the defender. In the first step the attacker is allowed to interact with the network, insert sybil accounts, and establish links with other users (called the victims). The defender uses the second step to anonymise and perturb the network, which was previously manipulated by the attacker. Lastly, the attacker receives the anonymised network and makes a guess on the pseudonyms used to anonymise the victims. Each of these steps is formalised in what follows.
Attacker subgraph is recovered, victims are reidentified, and the existence of a relation is revealed.

Attacker subgraph creation
The attacker-defender game starts with a graph G = (V, E) representing a snapshot of a social network, as in Figure 2(a). The attacker knows a subset of the users, called the victims and denoted I, but not the connections between them. The attacker is allowed to insert a set of sybil nodes S into G and establish connections with their victims.
This step of the attack transforms the original graph G = (V, E) into a graph G + = (V , E ) satisfying the following two properties: The second condition says that relations established by the adversary are constrained to the set of sybil and victim nodes. We call the resulting graph G + the sybil-extended graph of G. An example of a sybil-extended graph is depicted in Figure 2 The attacker does not know the entire graph G + , unless the original graph was empty. The adversary knows, however, the subgraph formed by the set of sybil nodes S, their connections to the victims, and the victim set I. This notion of adversary knowledge is formalised next.
Definition 1 (Adversary knowledge). Let G = (V, E) be an original graph and G + = (V ∪ S, E ) the sybil-extended graph created by an adversary that targets a set of victims I ⊆ V . The adversary knowledge is defined as the subgraph G S,I of G defined by Note that connections between victims are not part of the adversary knowledge.

Pseudonymisation and perturbation
When the defender decides to publish the graph G + , she pseudonymises it by replacing the real user identities with pseudonyms. That is to say, the defender obtains G + and constructs an isomorphism ϕ from G + to ϕG + . An isomorphism between two graphs Two graphs are isomorphic, denoted by G ϕ G , or briefly G G , if there exists an isomorphism ϕ between them. Given a subset of vertices S ⊆ V , we will often use ϕS to denote the set {ϕ(v)|v ∈ S}. In Figure 2(c) we illustrate a pseudonymisation of the graph in Figure 2(b).
We call ϕG + the pseudonymised graph. Pseudonymisation serves the purpose of removing personally identifiable information from the graph. Because pseudonymisation is insufficient to protect a graph against re-identification, the defender is also allowed to perturb the graph. This is captured by a non-deterministic procedure t that maps graphs to graphs. The procedure t modifies ϕG + , resulting in the transformed graph t(ϕG + ). We assume that t(ϕG + ) is ultimately made available to the public, hence it is known to the adversary.

Re-identification
The last step of the attacker-defender game is where the attacker analyses the published graph t(ϕG + ) to re-identify her own sybil accounts and the victims (see Figure 2(d)). This allows her to acquire new information, which was supposed to remain private, such as the fact that E and F are friends.
We define the output of the adversary re-identification attempt as a mapping ρ from the set of vertices S ∪ I to the set of vertices in t(ϕG + ). This represents the adversary's belief on the pseudonyms used to anonymise the attacker and victim vertices in t(ϕG + ). To account for uncertainty on the adversary's belief, we consider that the adversary assigns a probability value p(ρ) to each mapping, denoting the probability that the adversary chooses ρ as the output of the re-identification attack. Let Φ S,I be the universe of mappings from the set of vertices in S ∪ I to the set t(ϕG + ). The law of total probability allows us to quantify the adversary's probability of success in re-identifying one victim as follows.
Proposition 1. Let G = (V, E) be an original graph, G + = (V ∪ S, E ) the sybil-extended graph created by an adversary that targets a set of victims I ⊆ V , and t(ϕG + ) the anonymised version of G + created by the defender. Then, the probability A S,I t(ϕG + ) (u) that the adversary successfully re-identifies a victim u ∈ I in t(ϕG + ) is In our analyses, we restrict the function p to be a probability distribution on the domain Φ S,I , i.e. ρ∈Φ S,I p(ρ) = 1. We also assume that p satisfies the standard random worlds assumption enunciated in [6,25], which expresses that, in the absence of any information in addition to t(ϕG + ), any two isomorphic subgraphs in t(ϕG + ) are indistinguishable for the adversary. We enunciate the random worlds assumption next, adapting the terminology to the one used in this paper.
Assumption 1 (Random worlds assumption [6,25]). Let G = (V, E) be an original graph, G + = (V ∪ S, E ) the sybil-extended graph created by an adversary that targets a set of victims I ⊆ V , and G = t(ϕG + ) the anonymised version of G + created by the defender. Let ρ 1 and ρ 2 be two bijective functions from S ∪ I to the set of vertices V G in G . Let G ρ 1 S,ρ 1 I and G ρ 2 S,ρ 2 I be the two attacker subgraphs in G that correspond to the adversary's guesses ρ 1 and ρ 2 , respectively. If G ρ 1 S,ρ 1 I and G ρ 2 S,ρ 2 I are isomorphic, then p(ρ 1 ) = p(ρ 2 ).
In the remainder of this article, we will analyse the effectiveness of various anonymisation procedures by calculating the success probability of the adversary based on Proposition 1, and we will often resort to Assumption 1 when reasoning about the adversary's belief ρ.

Applicability of current privacy properties against active attacks
In this section we make, to the best of our knowledge, the first connection between passive and active attacks by formally proving that k-symmetry provides protection against active attacks. We also prove that k-symmetry is incomplete, just like (k, )-anonymity, in the sense that none of them characterises all anonymous graphs with respect to active attacks.
Last, but not least, we show that neither k-symmetry implies (k, )-anonymity, nor the other way around.

k-symmetry: an effective privacy model against active attacks
We use the introduced privacy model to prove that k-symmetry, the strongest notion of anonymity against passive attacks, also protects against active attacks.
Definition 2 (k-symmetry [44]). Let Γ G be the universe of automorphisms in G. Two vertices u and v in G are said to be automorphically equivalent, denoted u ∼ = v, if there exists an automorphism γ ∈ Γ G such that γ(u) = v. Because the relation ∼ = is an equivalence relation in the set of vertices of G, let [u]∼ = be the equivalence class of u. G is said to satisfy k-symmetry if for every vertex u it holds that |[u]∼ = | ≥ k.
Theorem 1. Let G = (V , E ) be an original graph, G + = (V ∪ S, E ) the sybil-extended graph created by an adversary that targets a set of victims I ⊆ V , and t(ϕG + ) = (V, E) the anonymised version of G + created by the defender. If t(ϕG + ) satisfies k-symmetry, then for every vertex u ∈ I the probability of the adversary guessing the output of ϕ(u) is lower than or equal to 1/k.
The last proof step consists of using the formula to calculate adversary success to obtain a probability bound. The adversary's probability of success in re-identifying a victim u ∈ I is calculated by, ρ∈Φ S,I ,ρ(u)=ϕ(u) p(ρ).

k-symmetry versus (k, )-anonymity
As proven in Theorem 1, k-symmetry provides protection against active attacks regardless of the number of sybil nodes inserted by the attacker, as opposed to (k, )-anonymity which uses as a parameter on the maximum number of sybil nodes. In spite of that, (k, )anonymity is not weaker than k-symmetry. As we prove next, they are in fact incomparable.
Theorem 2. Let G k, be the universe of anonymised graphs such that no adversary with sybil nodes or less can re-identify a victim with probability lower or equal than 1/k. There exist k > 1 and graphs G, G , G ∈ G k, such that: • G satisfies k-symmetry, but G does not satisfy (k, )-anonymity for some ≥ 1.
• G satisfies (k, )-anonymity for some ≥ 1, but G does not satisfy k-symmetry.
Proof. Figure 3(a) shows a 2-symmetric graph G which, for 2 ≤ ≤ 8, does not satisfy (k, )-anonymity for any k > 1. Moreover, Figure 3(b) shows a (2, 1)-anonymous graph G which can be verified not to satisfy k-symmetry for any k > 1. In fact, this graph even fails to satisfy k-degree anonymity for any k > 1. An example of a graph G proving the correctness of the last statement is displayed in Figure 3(c). That graph is neither 2-symmetric nor (2, 2)-anonymous. Of independent interest is our proof that k-automorphism [48] does not protect against active attacks. This is a surprising result, given that k-automorphism and k-symmetry have traditionally been considered equivalent. We refer the interested reader to Appendix A.

Algorithm K-Match guarantees k-symmetry
In this section we prove that the algorithm K-Match, proposed in [48] as a sufficient condition to achieve k-automorphism, also guarantees k-symmetry. Given a graph G and a value of k, the K-Match algorithm obtains a supergraph G of G satisfying the following conditions: 2. There exist k − 1 automorphisms γ 1 , γ 2 , . . . , γ k−1 of G such that: (c) For every v ∈ V G and every i, j such that 1 ≤ i < j ≤ k − 1, γ i+j (v) = γ i (γ j (v)) = γ j (γ i (v)), with addition taken modulo k.
To obtain G , the algorithm first splits the vertices of G into k groups and arranges them in a k-column matrix M called the vertex alignment table (VAT for short). If |V G | is not a multiple of k, a number of dummy vertices is added to achieve this property. The VAT is organised in such a manner that the number of graph editions to perform in the second step of the process is close to the minimum. For convenience, in what follows we will denote by v ij the vertex of G placed in position M ij of the VAT. The second step of the method consists in adding edges to E G in such a way that conditions 2.a to 2.c are enforced. To that end, for every edge (v ij , v pq ), all edges of the form (v i,j+t , v p,q+t ), additions modulo k, are added to E G if they did not previously exist. Figure 4 shows an example of a VAT allowing to enforce 3-automorphism on the graph of Figure 2 that is, a function such that the image of every element is the one located two columns to its right (modulo 3) on the same row. Figure 4: An example of a VAT for the graph shown in Figure 2(b).
In general, these functions are not automorphisms of G upon creation of the VAT. It is the second step of the method that will transform them into automorphisms by performing all necessary edge-copying operations. For example, the edge (C, A) needs to be added to G because (A, B) ∈ E G but (f 2 (A), f 2 (B)) = (C, A) / ∈ E G ; and (A, 3) needs to be added because (B, E) ∈ E G but (f 2 (B), f 2 (E)) = (A, 3) / ∈ E G . Once the method is executed, each automorphism γ t , t ∈ {1, . . . , k − 1}, defined in item 2 above is completely specified by the VAT, as γ t (v ij ) = v i,j+t , with addition modulo k, for every i ∈ 1, . . . , |V G | k and every j ∈ {1, . . . , k}.
We now show the link between the K-Match method and k-symmetry.
Theorem 3. Let G = (V, E) be a graph and let G = (V , E ) the result of applying algorithm K-Match to G for some parameter k. Then, G satisfies k-symmetry.
Proof. Let u ∈ V G be an arbitrary vertex of G , and let v 1 = γ 1 (u), v 2 = γ 2 (u), . . . , v k−1 = γ k−1 (u) be the images of u by the automorphisms γ 1 , γ 2 , . . . , γ k−1 enforced on G by the execution of K-Match. By definition, we have that u ∼ = v 1 ∼ = v 2 ∼ = . . . ∼ = v k−1 and, by conditions 2.a and 2.b, they are pairwise different. Thus, The most relevant consequence of Theorem 3 is that algorithm K-Match can also be used for protecting graphs against active adversaries, as it will ensure that no victim is re-identified with probability greater than 1/k.

Experiments
The purpose of these experiments 3 is to demonstrate the effectiveness and usability of ksymmetry, enforced using the K-Match algorithm, for protecting graphs against active adversaries leveraging a sufficiently large number of sybil nodes and the strongest attack strategy reported in the literature, namely the robust active attack introduced in [28]. Effectiveness is assessed in terms of the success rate measure used in previous works on active attacks [29,26,27,28], whereas usability is assessed in terms of several structural utility measures. In what follows, we describe the experimental setting, display the empirical results obtained and conclude the section with a discussion of these results.

Experimental setting
In order to make the results reported in this section comparable to previous works on active attacks and countermeasures against them [27,28], we study the behaviour of our proposed method on two types of randomly generated synthetic graphs. In the first case, we use Erdős-Rényi (ER) random graphs [12]. We generated 200, 000 ER graphs, 10, 000 for each density value in the set {0.1, 0.15, . . . , 0.95, 1.0}. The second group of synthetic graphs was generated according to the Barabási-Albert (BA) model [3], which generates scalefree graphs. We used seed graphs of order 50 and every graph was grown by adding 150 vertices, and performing the corresponding edge additions. The BA model has a parameter m defining the number of new edges added for every new vertex. We generated 10, 000 graphs for every value of m in the set {5, 10, . . . , 50}. In generating each graph, the type of the seed graph was randomly selected among the following choices: a complete graph, an m-regular ring lattice, or an ER random graph of density 0.5. The probability of selecting each choice was set as 1 /3. In both cases, the generated synthetic graphs have 200 nodes.
Based on the discussion on the plausible number of sybil nodes in Section 3, we make the number of sybils = log 2 200 = 8.
We analyse three values for the privacy parameter k: a low value, k = 2; a high value, k = = 8; and an intermediate value, k = 5. For every value of k, we compare the behaviour of the K-Match algorithm, which ensures k-symmetry, and Mauw et al.'s algorithm for enforcing (k, Γ G,1 )-adjacency anonymity [27]. In order to build the vertex alignment table, algorithm K-Match requires the vertex set of the input graph to be partitioned into k subsets such that the number of edges linking vertices in different subsets is close to the minimum. We used the multilevel k-way partitioning method reported in [19], in specific its implementation included in the METIS library 4 , for efficiently obtaining such a partition. The effectiveness of the anonymisation methods is measured in terms of their resistance to the robust active attack described in [28]. Thus, following the attackerdefender game described in Section 3, for every graph we first run the attacker subgraph creation stage. Then, for every resulting graph, we obtain the two variants of anonymised graphs. Finally, for each perturbed graph, we simulate the execution of the re-identification stage and compute its success rate as defined in [28], that is where X is the set of equally-most-likely sybil subgraphs retrieved in t(ϕG + ) by the third phase of the attack, and with Y X containing all equally-most-likely fingerprint matchings according to X. In order to obtain the scores used for comparing the effectiveness of the different approaches, we compute for every method the average of the success rates over every group of 10, 000 graphs sharing the same set of parameter choices. The anonymisation methods are also compared in terms of utility. To that end, we measure the distortion caused by each method on a number of global graph statistics, namely the global clustering coefficient, the averaged local clustering coefficient, and the similarity between the degree distributions, measured in terms of the cosine of the angle between the degree vectors, following the approach introduced in [15,26]. Regarding the effectiveness of the anonymisation methods, the results in Figure 5 clearly show that K-Match is considerably more effective against the robust active attack than (k, Γ G,1 )-adjacency anonymity. These results are particularly relevant in light of the fact that (k, Γ G,1 )-adjacency anonymity was until now the sole formal privacy property to provide non-negligible protection against the original active attack and some instances of the robust active attack [27,28]. Finally, the experiments shown here are the first ones where the robust active attack leveraging log 2 n sybils is shown to be consistently thwarted by anonymisation methods based on formal privacy properties. So far, this had only been achieved via the addition of (large amounts of) random noise [28].

Results and discussion
Regarding utility, both methods have a small impact on the overall similarities of the degree distributions, as illustrated in Figure 6. This does not mean that the degrees are not affected by the methods. In fact, both methods make most degrees increase, but in a manner that does not significantly affect the ordering of vertices in terms of their degrees. Regarding clustering coefficient-based utilities, we can observe in Figures 7 and 8 that the superior effectiveness of K-Match does come at the price of a larger degradation in the values of local and global clustering coefficients.
The main takeaway from the experimental results presented in this section is that our refinement of the notion of re-identification probability for active adversaries has led to identifying, for the first time, an anonymisation method satisfying two key properties: (i) featuring a theoretically sound privacy guarantee against active attackers, and (ii) having this privacy guarantee translate into effective resistance to the strongest active attack reported so far, even when the attacker leverages a large number of sybil nodes.

Conclusions
We have introduced a new probabilistic interpretation of active re-identification attacks on social graphs. This enables the privacy-preserving publication of social graphs in the presence of active adversaries by jointly preventing the attacker from unambiguously retrieving the set of sybil nodes, and from using the sybil nodes for re-identifying the victims. Under the new formulation, we have shown that the privacy property k-symmetry provides a sufficient condition for the protection against active re-identification attacks. Moreover, we have shown that a previously existing efficient algorithm, K-Match, provides a sufficient condition for ensuring k-symmetry. Through a series of experiments, we have demonstrated that our approach allows, for the first time, to publish anonymised social graphs with formal privacy guarantees that effectively resist the robust active attack introduced in [28], which is the strongest active re-identification attack reported in the literature, even when it leverages a large number of sybil nodes.
The active adversary model addressed in this paper assumes that the (inherently dynamic) social graph is published only once. A more general scenario, where snapshots of a dynamic social network are periodically published in the presence of active adversaries, has recently been proposed in [7], and the robust active attack from [28] has been adapted to benefit from this scenario. Our main direction for future work consists in leveraging our methodology to propose anonymisation methods suited for this new publication scenario.
Acknowledgements: The work reported in this paper received funding from Luxembourg's Fonds National de la Recherche (FNR), via grant C17/IS/11685812 (PrivDA). Part of this work was conducted while Yunior Ramírez-Cruz was visiting the School of Information Technology at Deakin University.
However, a missing condition in Definition 3, namely requiring every ϕ i to satisfy ϕ i (v) = v, invalidates this claim. Consider the graph shown in Figure 9. This graph satisfies k-automorphism as defined in Definition 3, as can be verified by the existence of the non-trivial automorphism γ = {(v 1 , v 5 ), (v 2 , v 6 ), (v 3 , v 4 ), (u, u)}, yet the graph is vulnerable even to the simplest structural attack, the degree-based attack, as vertex u is the sole vertex with degree 2. It is worth noting that this limitation of k-automorphism does not necessarily invalidate existing anonymisation methods. This is exemplified by the K-Match algorithm itself, which does provide the intended protection because the property it directly enforces is the so-called k different matches principle (see [48]), which in turn is not equivalent to k-automorphism, but stronger.