On String and Graph Sanitization

The Combinatorial String Dissemination (CSD) model was introduced by Bernardini et al [3]. In this model, we have a string $W$ that we would like to disseminate for analysis. Toward effective dissemination, a dissemination that achieves a good trade-off between privacy and utility, we need to specify a set of privacy-related constraints and a set of utility-related properties, to then determine the best possible sequence of edit operations to be applied to $W$ so that the utility-related properties are satisfied subject to the privacy-related constraints.

A specific CSD setting that has been considered by Bernardini et al [3] is the following. The set of constraints (C1) is defined using an integer $k>0$ and a set of length-$k$ strings, known as the set of sensitive patterns; in particular, it consists in strictly forbidding the occurrence of any sensitive pattern in $W^{\prime }$, the string to be constructed from $W$. The set of properties is defined using two widely used string properties. The first one (P1) says that the order of occurrence of the length-$k$ non-sensitive patterns is preserved in $W^{\prime }$; the second (P2) says that the frequency of the length-$k$ non-sensitive patterns is also preserved in $W^{\prime }$.

This model leads to interesting combinatorial problems on strings [4, 3, 15, 6, 9, 5, 16, 2]. We define a few such problems in the following subsections and briefly describe optimal algorithms for solving them or solid evidence as to why they are unlikely to be solved exactly.

In the TFS (Total order, Frequency, Sanitization) problem, we are given a string $W=W[1]\mathrm{\dots }W[n]$ of length $n$ over an alphabet $\mathrm{\Sigma }$, and we are asked to output a shortest string $X:=W^{\prime }$ that satisfies C1, P1, and P2. The following example shows a TFS instance.

(Note that since $\text{\#}\notin \mathrm{\Sigma }$, one could use the occurrences of # in $X$ to learn about potential occurrences of sensitive patterns in $W$; see Section 2.3.) The following result is known.

The algorithm proceeds by reading $W$ from left to right and constructs $X$, which is initially empty. When the length-$k$ substring $S$ read is non-sensitive, it merges it with $X$. Otherwise, it applies two rules. In the first rule (R1), given $S$, it constructs the string:

Note that the letter # is a special letter that does not belong to the alphabet $\mathrm{\Sigma }$ of $W$.

In the second rule (R2), given $S^{\prime }$ of length $2(k-1)+1$ obtained from R1, the algorithm tries to check if a shorter string $S^{\prime }$ is possible. In particular, when the $k-1$ letters before # are the same as the $k-1$ letters after it, we remove the # and the $k-1$ subsequent letters. One can easily notice that the above edit operations on $S^{\prime }$ will violate neither P1 nor P2.

Instead of $S$, the string $S^{\prime }$, produced by rules R1 and R2, is merged with $X$.

By carefully implementing R1 and R2, we can construct string $X$ in $𝒪(kn)$ time. As for the length of $X$ in the worst case, it suffices to construct the de Bruijn sequence of order $k-1$ as the input string $W$, and assign every other consecutive length-$k$ substring to be a sensitive pattern. Recall that a de Bruijn sequence of order $k^{\prime }$ over an alphabet $\mathrm{\Sigma }$ is a string in which every possible length-$k^{\prime }$ string over $\mathrm{\Sigma }$ occurs exactly once as a substring. Thus, for such an input string $W$, $X$ must be of length $\mathrm{\Omega }(kn)$ because R2 cannot be applied.

The question that now arises naturally is whether we can hope for a shorter string $W^{\prime }$ by relaxing the constraints of the TFS problem. In response, Bernardini et al. [3] introduced the following related problem. In the PFS (Partial order, Frequency, Sanitization) problem, we are given a string $W$ of length $n$, and we are asked to output a shortest string $Y:=W^{\prime }$ that satisfies C1, $\mathrm{\Pi }1$, and P2, where the $\mathrm{\Pi }1$ property is a relaxation of the P1 property: it replaces the total order by a partial order saying that the order of occurrence of the length-$k$ non-sensitive patterns in maximal fragments with no # occurring remains the same.

The following result is known.

(Note that the $|Y|$ term in Theorem 7 accounts for the fact that $Y$ can be longer than $W$.) We briefly explain how we can arrive at Theorem 7. Consider that we have (a representation of) string $X$ obtained via TFS. If any two maximal #-free fragments of $X$, called blocks, overlap by $k-1$ letters, then we can further apply R2 while still satisfying $\mathrm{\Pi }1$ and P2.

Now, it might seem that we must solve the famously NP-hard Shortest Common Superstring (SCS) problem [11] on the set of blocks originating from $X$ to construct $Y$. Fortunately, this is not the case as the allowed overlaps are of fixed length $k-1$. To solve this problem, we map the prefix and suffix of length $k-1$ of every block to an integer identifier. We can then ignore the middle part of each block, thus transforming every block to a string of length 2. After this reduction, we can solve SCS on a collection of two-letter strings in linear time [3].

Say we have completed the task in Section 2.2: sanitizing the occurrences of all sensitive patterns by means of a special letter that we represent by #. Although sensitive patterns are no longer present in the sanitized sequence, the occurrences of # reveal the locations where they used to occur. It is not hard to imagine that a malicious adversary could use this information to try and reconstruct the concealed information from the context surrounding the #s. This is because, although the adversary cannot know precisely which special letter has been used in the sanitization process, they know that it is (by definition) not part of the original alphabet, and thus it can be relatively easily identified. Imagine that the dataset consists of a sequence of locations: # could be a non-existing location or a location far away from those in the original sequence. In a sequence of online purchases, # could be an item not sold in a certain online store; in a genomic sequence, # is a letter that does not correspond to any nucleotide base. In all such examples, it is not hard for an attacker to identify # with a simple scan of the database and thus partially retrieve the concealed information.

Therefore, a complete sanitization pipeline should eventually replace the occurrences of # with letters of the original alphabet. This immediately poses a problem: each replacement introduces $k$ new “spurious” occurrences of length-$k$ patterns over the original alphabet, which might influence downstream analysis results based on the frequency of length-$k$ substrings. This kind of analysis extracts length-$k$ substrings that appear at least $\tau$ times, for some fixed integer $\tau$, assuming that these $\tau$-frequent patterns carry important information.

The natural problem arising is to decide whether it is possible to replace every occurrence of # with some letter from the original alphabet such that: (i) no sensitive pattern is reintroduced; and (ii) the set of $\tau$-frequent non-sensitive patterns before and after sanitization is the same. We term this problem Hide and Mine (HM). Intuitively, HM is hard because replacements are not independent of one another: making a choice at one position could prevent feasible choices from being available at other positions, while this would not have been the case when making a different choice in the first place. But how does one prove its hardness?

The answer came from a brilliant idea by Prof. Grossi: we should reduce from the famous Bin Packing [14] problem! More precisely, we should reduce from a variant of the problem called Unique-Weights Bin Packing (UWBP). The reduction is far from being trivial: we will provide a friendly, informal description of the proof in the rest of this section.

The community structure is a fundamental property of a graph, and understanding how this structure can be maintained or disrupted is crucial. In our graph sanitization work, we introduced the following general Community Breaking (CB) problem: Given an undirected graph $G(V,E)$, a set of nodes $U\subseteq V$, and a notion of community, identify a smallest subset $E^{\prime }$ of $E$, so that no community in $G^{\prime }=G(V,E\setminus E^{\prime })$ contains a node in $U$.

In [8], we considered a specific community notion, namely the $k$-truss. A $k$-truss is a subgraph of a graph in which every edge is part of at least $k-2$ triangles formed entirely within the subgraph; see Fig. 1(a) for an example.

Building on the CB problem and the $k$-truss notion, we defined MIN-$k$-TBS (Minimum $k$-Truss Breaking Set): Given an undirected graph $G(V,E)$ and a parameter $k$, find a smallest subset $E^{\prime }$ of $E$ such that $G(V,E\setminus E^{\prime })$ contains no $k$-truss. MIN-$k$-TBS is obtained from the CB problem by considering communities based on the notion of $k$-truss and $U=V$.

The MIN-$k$-TBS problem is intuitively challenging: there are up to $2^{|E|}$ edge subsets that one may consider; and $k$-trusses have a hierarchical structure. For example, a $(k+i)$ truss, for any $k$ and $i\ge 0$, is also a $k$-truss and contains at least $\left(\genfrac{}{}{0pt}{}{k+i}{k}\right)$ smaller $k$-trusses. Finding a minimum set of edges to delete to make a graph triangle-free is known to be NP-hard [17], and that is exactly the MIN-$3$-TBS problem. Assuming the Exponential Time Hypothesis, we cannot even solve this problem in $2^{o(|E^{\prime }|)}\cdot n^{O(1)}$ time [1]. We proved that MIN-$k$-TBS is also NP-hard for $k>3$ using a reduction from MIN-3-TBS.

Here is a brief sketch of our proof. We prove that for every $k\ge 3$, the MIN-$k$-TBS problem is NP-hard by reducing from the known NP-hard MIN-$3$-TBS problem, which involves making a graph triangle-free. In our reduction, for each triangle in the original graph, we add $k-3$ extra nodes to form a clique with the triangle’s vertices. This construction ensures that a $k$-truss exists in the new graph $G_k$ if and only if a triangle exists in the original graph. It follows that solving MIN-$3$-TBS for $G$ is equivalent to solving MIN-$k$-TBS for $G_k$. Therefore, the problem MIN-$k$-TBS is NP-hard for every $k\ge 3$.

We also presented an exact exponential-time algorithm to solve the MIN-$k$-TBS problem. The algorithm first enumerates all minimal $k$-trusses (i.e., a $k$-truss for which removing any single edge would destroy the $k$-truss) and then computes a minimum transversal of the corresponding hypergraph. Consequently, its overall time complexity is exponential in the number $|E|$ of edges. To practically improve on the efficiency of this algorithm, we developed three heuristics, MBH${}_{\text{S}}$, MBH${}_{\text{C}}$, and SNH, which run in polynomial time; see [8] for details.

Due to the exponential-time complexity of our exact algorithm, computing the optimal solution is a heavy task even for small graphs with a few hundred nodes. Prof. Grossi designed an algorithm to compute a lower bound on the size of the optimal solution, which facilitates the evaluation of our heuristic algorithms.

The main idea is to use cliques as a “proxy” for trusses. Since a $k$-clique (i.e., a complete subgraph consisting of $k$ vertices, where every pair of vertices is directly connected by an edge) is a $k$-truss, we must at the very least make the input graph $G$ free from $k$-cliques to solve MIN-$k$-TBS. The algorithm works in three phases:

1. 1.

   Computes an edge clique partition of $G$. We partition the graph into edge-disjoint cliques. This partitioning ensures that each edge belongs to exactly one clique, allowing us to analyse dense substructures individually.

2. 2.

   Applies the best available lower bound on each clique. For each clique, we estimate the minimum number of edges that must be removed to eliminate all $k$-trusses within it. We employ two complementary approaches: (1) a bound derived from Turan’s theorem [7], which limits the maximum number of edges in a graph that avoids a clique of size $k$; and (2) a triangle-based approach, as each edge in a $k$-truss must belong to at least $k$ -2 triangles – counting the number of triangles gives an estimate of the minimum deletions required.

3. 3.

   Outputs a lower bound on the size of the optimal solution by summing the bounds of the cliques. This is possible because the cliques are all edge-wise disjoint.

The overall time complexity of our LB algorithm is $O(q{\mathrm{\Delta }}^2|E|)$, where $q$, $\mathrm{\Delta }$, and $|E|$ are the size of the largest clique, the highest degree, and the number of edges in $G$, respectively.

Interestingly, the lower bound produced by the above algorithm helped us demonstrate that our heuristics were very competitive to the exact algorithm on large instances in terms of solution quality, even if we were unable to run the exact algorithm on these instances!