{'fraction_non_alphanumeric': 0.04417648967232616, 'fraction_numerical': 0.007029306802206121, 'mean_word_length': 3.849239643418983, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Database Alignment with Gaussian Features

We consider the problem of aligning a pair of databases with jointly Gaussian features. We consider two algorithms, complete database alignment via MAP estimation among all possible database alignments, and partial alignment via a thresholding approach of log likelihood ratios. We derive conditions on mutual information between feature pairs, identifying the regimes where the algorithms are guaranteed to perform reliably and those where they cannot be expected to succeed.


Introduction
Consider the following setting: There are a large set of entities (e,g, users) with some measurable characteristics. Let the measures of these characteristics be jointly Gaussian, with known statistics. We refer to these measures as features. Consider two different sources, each providing a database with lists of features for these entities. Furthermore, let one these sources lack proper labeling for features that would allow for the identification of feature pairs from the two sources that correspond to the same entity. This might be due to privacy concerns, if the mentioned features provided by the source contain sensitive information that ought to remain anonymous, or it might simply be that a reliable labeling is not available.
If the correlation between features pairs is sufficiently strong, then it is possible to exploit this correlation to identify correspondences between the two databases and in fact generate a perfect alignment between the feature lists. Such a capability might be a valuable tool to recuperate missing information by labeling unlabeled features or by allowing the junction of measurements coming from distinct sources. However it also has serious implications in privacy as it makes anonymous data vulnerable to deanonymization attacks [1].
It then becomes critical to understand the limitations of database alignment and to identify the conditions that characterize these limitations. This allows us to assess the feasibility and reliability of alignment procedures as well as the vulnerability of deanonymization schemes. In this study we investigate the conditions that guarantee either the achievability of alignment or its infeasibility. We analyze these conditions for both partial alignments and as well as for complete alignments. Cullina et al. have recently analyzed this problem for the case of discrete random variables, introducing a new correlation measure characterizing the feasibility of alignment [2]. Takbiri et al. have investigated a related problem where the feature of each user is Gaussian with characteristic statistics and has correlation with other user features [3]. In this setting an adversary with perfect knowledge of system statistics attempts to match features with the characteristic user statistics. This follows the authors' previous studies of the same setting for discrete valued features and with data obfuscation [4], [5].
The database alignment problem is connected to the widely studied graph alignment problem. In that setting, each feature is associated with a pair of anonymized users. In the simplest case, the feature is a Bernoulli random variable indicating the presence or absence of an edge between the users. A recent line of work has characterized the information theoretic limits of the graph alignment problem [6,7,8]. The problem of aligning correlated Wigner matrices, in which each feature is a Gaussian random variable, has served as a proxy for understanding the effectiveness of graph alignment algorithms [9].

Model
Notation We denote random variables by capital letters and fixed values by lowercase letters. For a set S and finite sets T , U , we denote by S T ×U the set of matrices with entries in S, rows indexed by T and columns indexed by U . We mark vectors with arrows and write matrices in boldface. Given some matrix z, we denote its i-th row by z i * , j-th column by z * j and its (i, j)-th entry by z ij . We denote the identity matrix with rows and columns indexed by T by I T . When the indexing set is clear from context, we will drop the superscript. We denote the set of integers from 1 to n by [n].

General problem formulation
In this model, a database is just a function from a set of users to some space. The value of the function for a user u is the database entry for that user. Cullina, Mittal, and Kiyavash considered database entries in finite alphabets [2]. In this paper, we consider database entries that are finite dimensional real vectors sampled from a gaussian distribution.
We are given two sets of user identifiers, U and V, with |U | = |V| = n. We express the content of databases by matrices A ∈ R U ×[da] and B ∈ R V×[d b ] , so d a and d b are the lengths of feature vectors.
There exists a natural bijective correspondence between the identifier sets, i.e. each identifier in one set is related to exactly one identifier in the other set. We express this correspondence by the bijective matching M ⊆ U × V.
Let p X Y be the density of jointly gaussian random variables The density p AB|M is defined as follows. For each (u, v) ∈ M , (A u * , B v * ) ∼ p X Y and these n random variables are independent: The matching M is uniformly distributed over the n! bijective matchings between U and V.
The database alignment problem is to recover M from AB, given knowledge of p X Y .
Observe that the rows of A are i.i.d. and that A is independent of M . The same is true for B. In other words, by examining one database, an observer learns nothing about M .
A pair of databases are illustrated in Figure 1.  Canonical form of covariance Let d ′ a be the dimension of the support of X, i.e. the rank of Σ a . Let φ : R [da] → R d ′ a be an affine transformation that is injective on the support of X. If we apply φ to each row of A, which can be done without knowledge of M , we obtain an equivalent database alignment problem. Similarly, the database B can be transformed to obtain an equivalent problem.
For any gaussian database alignment problem, there is an equivalent problem with µ = 0 and . Thus the correlation structure of ( X, Y ) is completely summarized by the vector ρ ∈ R d . The explicit transformations that put Σ into this form are described in Appendix A.

Correlation measures
Let I X Y I(A u * , B v * , |(u, v) ∈ M ) denote the mutual information between any pair of related identifiers coming from (u, v) ∈ M . Then Under the canonical formulation where Σ a = Σ b = I d and Σ ab = diag( ρ) this becomes Given any (u, v) ∈ M and ( X, Furthermore under the canonical formulation where Σ a = Σ b = I d and Σ ab = diag( ρ) this simplifies to σ 2 X Y = ρ 2 i . These calculations are made explicit in our supplementary material.
Note that σ X Y is upper bounded by 2I X Y . This can easily be seen in the canonical formulation, where σ 2

Results
Our results identify conditions on I X Y and σ X Y , as defined in Section 2.2.

MAP estimation
The algorithm considers all possible alignments between the two sets and chooses the most likely one. The log likelihood of an alignment is, by the independence of correlated feature pairs, equal to the sum of the log likelihood of each aligned feature pair. MAP estimation can then be implemented by computing the joint likelihood for each feature pair in O(n 2 d)-time and computing the maximum weight matching between databases in O(n 3 )-time using the Hungarian algorithm.
Theorem 1. (Achievability) If mutual information between feature pairs I X Y ≥ 2 log n + ω(1), then the MAP estimator returns the proper alignment with probability 1 − o(1). (1)), then any for algorithm, the probability of returning the proper alignment is o(1).
Binary hypothesis testing The algorithm checks every possible pair of identifiers and uses a threshold-based method to decide whether to match the pair or not. This can be done in O(n 2 d)time, which is the complexity of computing joint likelihoods for each feature pair.

Theorem 3. (Achievability) If
then, choosing the threshold such that log(n 2 /ε F P ) ≤ τ ≤ I X Y −σ X Y n/ε F N , the binary hypothesis test gives no more than ε F N false negatives and ε F P false positives in expectation.
It follows that the following regimes are achievable: The next theorem holds for databases with any distribution of feature pairs, i.e. not only Gaussians.

Theorem 4. (Converse)
For any binary hypothesis test, the expected number of false negatives ε F N and false positives ε F P is lower bounded as It follows that, if I X Y ≤ log n 1 − Ω(1) , then any binary hypothesis test has expected number of errors ε F N + ε F P ≥ Ω(n).

MAP estimation
Matching algorithm The maximum a posteriori estimator is the optimal estimator for the exact matching M given F . Given some realization f = (a, b), where (a) follows from the fact that M has a uniform distribution.

Achievability analysis
We establish a sufficient condition on the mutual information I XY between feature pairs to achieve a perfect alignment. The rest of this section assumes the cannonical setting. However, by the equivalence between the general setting and the canonical setting (as shown in Appendix A), the result directly applies to the general setting. Our analysis goes as follows: Lemma 4.1 sets an upper bound on the error probability that a given matching is more likely than the actual one. This bound is in the form of a function R whose explicit value remains to be determined. Lemma 4.2 gives an expression of R that has a decomposition with terms corresponding to each cycle of 'mismatchings'. Finally Lemma 4.3 gives the explicit expression for each of these cycle-terms and Lemma 4.4 bounds their product by a function whose value only depends on the number of mismatchings. Joining these results gives us the achievability condition in Theorem 1. .
We simply write I (+) and I (−) when there is no need to specify the size of the matrix. For any ℓ ∈ N + , where s, t ∈ R.
For compactness, call the matrix that appears in (1) Σ(m). This gives us We obtain R(m 1 , m 2 ) by integrating this expression over the whole space: Observe that I z for any matrix z. Then det I z z ⊤ I = det I − z ⊤ z . Using this relation we have Notice that m ⊤ 1 m 2 ∈ {0, 1} U ×U is the permutation matrix corresponding to permutation π = m 1 •m ⊤ 2 described in the statement of the lemma. Let C be the set of cycles of π and {ℓ c } c∈C denote their lengths. Consider the cycle notation of this permutation, i.e. (u 1 , u 2 , · · · , u ℓc )(u ′ 1 , · · · , u ′ ℓ c ′ ) · · ·, and specify an ordering of U based on this expression: u 1 , u 2 , · · · , u ℓc , u ′ 1 , · · · , u ′ ℓ c ′ , · · ·. Given this ordering of rows and columns, the permutation matrix m ⊤ 1 m 2 has block diagonal matrix form, with one block for each cycle c ∈ C and every block having the form of a shifted identity matrix I (ℓc,+) . Then m ⊤ 2 m 1 = m ⊤ 1 m 2 ⊤ has the same block diagonal form with the shifted identity matrices I (ℓc,−) , since I (ℓc,−) = I (ℓc,+) ⊤ . The determinant of a block diagonal matrix is equal to the product of the determinants of each block. Then we have where k ℓ denotes the number of cycles of length ℓ in the permutation π. Combining this with (2) and (3) gives us the claimed result. s − t · cos j 2π ℓ .
In particular Proof. Let z k ∈ C ℓ denote a family of vectors such that for any k ∈ [ℓ], z k j = e 2πi jk ℓ , where i 2 = −1. Observe that Vectors z k are the eigenvectors of L k (s, t): We compute the determinant by taking the product of the ℓ eigenvalues (one for each k ∈ [ℓ]). We want to bound the determinant of the matrix L ℓ (s, t), which is equal to the product of its eigenvalues (λ j ) j∈ [ℓ] . The sum of eigenvalues is equal to the trace of the matrix, which is known, since all diagonal elements of L ℓ (s, t) equal s for any ℓ ≥ 2. So λ k = tr L ℓ (s, t) = sℓ. Furthermore, observe that all eigenvalues are in the range [s − t, s + t]. Consider a sequence formed of two copies of each eigenvalue λ i . This sequence has mean s and has all entries within the range [s − t, s + t]. Then, as it is proven in Lemma B.1, Taking the square root of both sides results in the claim. Proof. Recall the canonical setting where Σ a = Σ b = I and Σ ab = diag( ρ).
where (  , which gives us s − t = s 2 − t 2 = 1 − ρ 2 i . Given any k ∈ N there are exactly (!k) × n k different matchings m ′ such that k = n − |m ∩ m ′ |, where (!k) represents the number of derangements over a set of size k. We bound (!k) × n k ≤ n k . Thus (1), then by summing the geometric series, we see that the above expression is o(1). Therefore is a sufficient condition for exact recovery under the canonical setting. Taking the logarithm of both sides gives us the claimed result.

Converse analysis
We establish a necessary condition on the mutual information I XY between feature pairs to achieve a perfect alignment. (1)) .

Proof. Consider the conditional generating function
The generating function is minimized at θ = 1/2 in which case we get c i (θ) = R i (m 1 , m 2 ). We evaluate the value of this function using Lemmas 4.2 and 4.3 with s = 1−ρ 2 /2 and t = ρ 2 /2.

Binary hypothesis testing
Matching algorithm We consider an algorithm that does gives us a 'matching'm ⊆ U × V that is not necessarily bijective, i.e. any entry can have multiple matches in the other dataset.
Recall that we denote the j-th row of a matrix z by z j * . Given some a ∈ R U ×[d 1 ] and b ∈ R V×[d 2 ] and f = a, b the estimated 'matching' is given bŷ H τ is the log ratio test given by where p X and p Y denote the probability density functions of feature vectors associated with identifiers in U and V respectively, and τ ∈ R is some constant to be determined.

Achievability analysis
In our analysis we establish upper and lower bounds on the threshold τ that allow given probability bounds on false negatives and false positives. The mean and variance of the log ratio random variable were computed in Section 2.2. Using these values we get an upper bound on the probability of false negatives in Lemma 6.1 by the Chebyshev inequality. Lemma 6.2 gives an upper bound on the number of false positives. Finally, taking the intersection of the conditions on τ allows us to derive the achievability result given in Theorem 3.

Converse analysis
We present a converse on the performance of the binary hypothesis testing algorithm based on Fano's inequality. Then Finally I(A u ; B v ) ≥ 0 and H(M u,v ) = 1 n log n + n−1 n log n n−1 ≥ log n n .
Proof of Theorem 4 LetM u,v 1 A u , B v ∈ H τ denote the estimation on the relation between identifiers u and v. We have a correct estimation ifM Then by Fano's inequality, which gives the upper bound as H(E). Let ǫ Pr[E = 1]. This value can also be expressed as the expected frequency of false matches, i.e. given ε F N and ε F P the expected number of false negatives and false positives, ǫ = ε F N +ε F P |U ×V| = ε F N +ε F P n 2 . Let H b denote the binary entropy function. By Fano's inequality, using Lemma 6.3, we have We have Combining this with (4) gives us ε F N + ε F P ≥ n 2 log n − I X Y 2 log n + 1 and the claim follows.

A Transformation of feature vectors
By the invertibility of Σ a and Σ b , there exist Cholesky decompositions with invertible matrices L a and L b such that Σ a = L a L ⊤ a and −1 be a singular-value decomposition with U and V unitary matrices and Σ ′ ab a diagonal matrix of size d 1 × d 2 . Finally let µ a and µ b denote the mean of features from the two datasets. Let the feature transformations be defined as It can be verified that Both U ⊤ L −1 a and V ⊤ L −1 b are invertible matrices, therefore T a and T b are bijective functions with no loss of information.
Next we perform a non-reversible operation. Consider the zero rows and columns of Σ ′ ab . These correspond to transformed feature entries that have no correlation with features from the other dataset, hence they provide no information in identifying matching features. Simply dropping these results in no loss of information. Σ ′ ab is a diagonal matrix, therefore the number of features we keep from either dataset is simply equal to the number of non-zero entries in Σ ′ ab . Thus the final feature vectors are of equal size d. Let X ′′ and Y ′′ be the final features obtained after throwing away entries in X ′ and Y ′ , and Σ ′′ ab ∈ R d×d be the matrix obtained by removing zero rows and columns from Σ ′ ab . Then, Let ρ denote the diagonal entries in Σ ′′ ab .
be the covariance matrices of the original features and of the transformed features respectively. The mutual information between matched pairs of original features ( X, Y ) and matched pairs of transformed features ( X ′′ , Y ′′ ) is the same and given by Proof. Our transformation keeps all information from features that exhibits correlation with the other feature list. Therefore the mutual information between feature pairs is the same for original features and transformed features.
Notice that the right-hand side is specifically the block matrix expression for the determinant of Σ. So log(1 − ρ 2 i ).
Proof. Notice that the log likelihood ratio of the transformed features are the same as the log likelihood ratio for the original features. Thus we just assume that the original features vectors already have the covariance matrix of the specified form. We already know the mean of the log likelihood ratio, which is equal to the mutual information I XY . Then i ) 2 = ρ 2 i and Var log q(α,β) q(α)q(β) = ρ 2 i . Finally we derive the expression for this variance based on the original covariance matrix. We refer to matrices Σ ′′ ab , Σ ′ ab , L a , U as given in the description of the feature transformation.
Proof. We give an algorithmic proof. Consider a sequence z 1 , z 2 , · · · , z 2k with mean µ and all entries in the range [µ − δ, µ + δ]. Assume the product π of the sequence is not (µ − δ) k (µ + δ) k . Then there exists two entries z i , z j ∈ (µ − δ, µ + δ). Without loss of generality assume |z i − µ| ≥ |z j − µ| and z i ≤ z j . Modify the sequence by replacing z i with µ − δ and z j with z j + z i − µ + δ. The new sequence still has mean µ and entries within the same range. However observe that its product (µ−δ)(z j +z i −µ+δ) z i z j × π is strictly smaller.
Iteratively applying this modification on any initial sequence eventually (in at most 2k-1 modifications) turns the sequence into one with product (µ − δ) k (µ + δ) k , which cannot be larger than the product of any intermediary sequence or the initial sequence.