Will Sharing Metadata Leak Privacy?
Danning Zhan

Rihan Hai

Web Information System
TU Delft

Web Information System
TU Delft

Abstract—In the dynamic field of data management andmachine learning, achieving a balance between effective data
use and privacy preservation is increasingly crucial. Federated
learning exemplifies this challenge by training machine learningmodels on data distributed across isolated silos while adhering
to privacy regulations like GDPR. A key aspect of this process
involves sharing metadata, such as feature names, essential formodel accuracy. Yet, the privacy implications of this metadata
exchange have been largely unexplored.
This paper examines the potential privacy risks of communicating detailed metadata in federated learning frameworks. While
metadata is critical for enhancing data utility and supporting
advanced analytics, we address the paradox that it might inadvertently lead to privacy violations. We focus on functional dependencies (FDs) and relaxed functional dependencies (RFDs), which
are crucial metadata types in database design and data quality.
We aim to define data privacy formally and investigate how
sharing these dependencies affects privacy preservation, using
probabilistic methods and analytical discussions to understandtheir impact.
Index Terms—Privacy, Relaxed Functional Dependencies

I. I NTRODUCTION
The accumulation of data has heightened data privacy
concerns, prompting stricter enforcement of regulations such
as GDPR [24], HIPAA [5], IPA [2], and PIPL [3]. Data
collectors are mandated to ensure the confidentiality of theiramassed data, leading to the formation of data silos. Despite the potential insights from cross-silo data processing,regulatory measures to safeguard data privacy hinder suchcollaborations. Federated learning emerges as a viable dataprocessing approach that upholds privacy standards amidst
these constraints.
Federated learning involves training ML models using
data residing in isolated silos while preserving data privacy.
According to how the feature space and sample space arepartitioned among the data sources, federated learning canbe categorized as vertical federated learning (VFL) [15] andhorizontal federated learning (HFL) [26]. For VFL, data silos share overlapping data instances but disjointed attributes,
whereas for HFL, data silos share overlapping attributes withdifferent data instances. HFL typically operates under thesame or similar database schema among participants. This
paper focuses on the more complex scenario of VFL, whereparticipants with differing database schemas must exchange
metadata before model training.
Fig. 1 shows a fintech scenario involving two distinct
parties: party A is a bank, and party B is an e-commerce company. Each has accumulated distinct datasets about a common

Fig. 1. Vertical Federated Learning between a bank and a e-commercecompany.

population. This presupposes that the dataset originates froma homogeneous population that is known. Recognizing thevalue that data heterogeneity can bring to their analysis, both
entities might consider engaging in vertical federated learning
to process their data collaboratively. An essential preliminary
step in this process involves metadata exchange between theparties to enhance mutual understanding of data, which is vitalto ensuring the utility of any downstream models.
Metadata, covering information about a dataset, such as
attribute name, range, and type, as well as constraints between
attributes, such as functional dependency (FD) and relaxedfunctional dependencies (RFD) [6], [9], [13], [18], play a
crucial role in data processing tasks such as data cleaning[7] and data integration [25]. Yet, the privacy implicationsof metadata exchange, particularly functional and relaxeddependencies, remain unexplored in VFL literature. This study
investigates the privacy impacts of sharing these dependencies,
comparing them to the situation where this information iswithheld. We concentrate on VFL due to the predominance ofFDs and RFDs identified within the data. VFL exhibits distinct
metadata dependencies among participants, contrasting with
HFL, where metadata are similar. Our analysis will leveragecommunicated metadata to assess data privacy implications
quantitatively using probabilistic methods.
Contributions Our contributions are outlined as follows.
We will provide a formal definition of privacy leakage inthe context of vertical federated learning.
• Using probabilistic methods, we will examine if sharing
various metadata types, including attribute names, domains, functional dependencies, and relaxed functional
dependencies, could result in privacy leakage.

•

II. P RELIMINARIESIn this section, we will formally define concepts that wewill use throughout this work.

TABLE I
N OTATION DEFINITIONS
Notation
Rreal
Rsyn
A⊂R
a∈A
ti , ri , uiti [A]d()θE()
Dy , Dom(Y)|.|Definition
The real relations
Generated/Synthesized relations
Subset of attributes of the relations
Any value a in the domain of attribute A
Tuple at index i, index being the row index
Attribute A associated with the tuple i
Any valid metric (distance) function
Probability value
Expected value of random variable
Domain of attribute Y
Cardinality or Size of the set
TABLE IIE XAMPLES TABLE : EMPLOYEE

Name
Alice
Bob
Charlie
Danny

Age
18
22
22
26

Department
Sales
Customer Service
Sales
Management

Salary
20000
25000
27000
35000

A. Functional Dependencies
Functional dependencies (FDs) are one of the most important constraints in relational database design, e.g., normalization [19]. A functional dependency X → Y specifies that
attributes Y depend on attributes X. We use the following
definition of functional dependency on relation R of party A
in Figure 1 [13]. If we consider the attributes X, Y ⊂ R suchthat X → Y is a functional dependency if and only if ∀ tuplest, r ∈ R, t[X] = r[X] =⇒ t[Y ] = r[Y ]. This means that forany tuple in the relation of party A, the attribute X of party
A will allow us to determine the value for attribute Y. We candefine the same definitions for party B’s data if we consider
the data scenario of VFL in Figure 1.
Relaxed functional dependencies (RFDs) hold under lessconstrained conditions than functional dependencies [9]. Because of the less-constrained definition of the dependencies,
this would imply that more functions and conditions can beutilized for RFDs.
Example 2.1: TABLE II is an example table of employeeswith four attributes: name, age, department, and salary. In
the example, we assume the attribute ‘name’ is unique. Two
possible functional dependencies are N ame → Age andN ame → Salary. The table also shows relaxed functional
dependencies N ame → Salary and Age → Salary.
B. Privacy Leakage
In the context of vertical federated learning, employing
an adjusted definition of privacy leakage that aligns moreclosely with regulatory standards, particularly those outlinedin the GDPR [1], [5] is imperative. To effectively address
this requirement, we propose establishing a quantitatively
measurable definition of privacy leakage. This definition aims
to accurately assess the extent of data privacy breaches or
exposures that may occur within the framework of verticalfederated learning, ensuring compliance with GDPR mandates.
This approach adheres to regulatory prerequisites and provides
a standardized metric for evaluating privacy risks in a federated
learning environment.
Participating parties exchange dataset-related information in
the preliminary stage of model training within a vertical federated learning framework, specifically metadata that describes
the content of their respective data. This metadata exchange,
while necessary, poses a potential risk for privacy leakage.
Consider a scenario involving two parties, A and B. Whenparty A communicates its metadata with party B, there arises
a possibility that party B might use this metadata to constructa synthetic dataset, essentially an inferred approximation of
A’s real dataset. We denote A’s real dataset as Rreal and thesynthetic dataset generated by B as Rsyn . Privacy leakage is aconcern if we can identify data points or values in Rsyn thatclosely match or replicate those in Rreal .
To understand and measure the privacy risk, we define‘identifiability’ – a fundamental concept in the GDPR1 .
Definition 2.1: (Identifiability) We say a tuple t is identifiable if, for the relation Rreal of the real data, ∃A ⊂ Rreal
such that for any value a ∈ A, ∃!t ∈ R such that t[A] = a.
The above definition of identifiability hinges on whether
a unique data point can be isolated based on a specific setof values for a given set of attributes A. If such a set exists
where only one data point equals the tuple value of A, thedata point is classified as identifiable. Thus, anonymization
techniques [11] aims to ensure that shared data remain nonidentifiable, upholding privacy standards and aligning withdata protection regulations like the GDPR.
Identifiability pertains to the ability to link specific data
elements within a dataset (in this case, Rsyn ) to their counterparts in another dataset (Rreal ) during data sharing. Next, we
discuss privacy in the context of vertical federated learning,which has a different characteristic than data sharing.
Privacy for VFL. Federated learning aims to train machinelearning models across multiple data sources, or ‘silos’, while
preserving privacy. Before the training begins, data fromvarious parties is synchronized using private set intersection
techniques [10], [12]. This process ensures that the identity ofthe data tuples is known only to the parties involved in the
training. This unique aspect of Vertical Federated Learning
calls for a more nuanced understanding of privacy leakage.
To address this, we propose a distinct definition of privacy
leakage for VFL. Since categorical and continuous data types
have different impacts on privacy risks, we will define theprivacy leakage for each data type separately.
Definition 2.2: (Categorical data privacy leakage for VFL)
Consider the scenario where Rreal and Rsyn represent therelations in the real dataset and synthetic dataset, respectively.
Let A be a subset of categorical attributes in Rreal . For any
given tuple ti , which exists at the same index i in both
Rreal and Rsyn , we observe a privacy leakage if the attribute
1 https://gdpr-info.eu/art-5-gdpr/

values of ti in A are identical in both Rsyn and Rreal , i.e.,
real
tsyn
i [A] = ti [A].
The proposed definition of privacy leakage considers thecorrespondence between the ith tuple in the real and the synthetic dataset. Privacy leakage occurs if values match withinthese tuples, as distinct values for categorical attributes carry
divergent meanings. The index assumes critical importance inthe context of VFL due to its source being the intersection ofcollaborating entity’s datasets.
For continuous attributes, a more nuanced definition of data
privacy is required. Given the extensive variability inherent
in continuous variables, theoretically, they possess infinite
possible exact values. Consequently, if a generated value falls
within a parameterized neighborhood of the real attributevalue, measured using a specified distance metric d() suchas Euclidean distance [8], it should be classified as a privacy
leakage, which leads to the below definition.
Definition 2.3 (Continuous Data Privacy Leakage in VFL):
Consider the scenario where Rreal and Rsyn represent therelations in the real dataset and synthetic dataset, respectively.
Let A be a subset of continuous attributes in Rreal , and ϵ be agiven error threshold. For any given tuple ti , which exists atthe same index i in both Rreal and Rsyn , we observe a privacy
realleakage if the distance d between tsyn
i [A] and ti [A] is within
synreal
the error threshold, i.e., d(ti [A], ti [A]) ≤ ϵ.
III. P RIVACY A NALYSIS OF M ETADATA
Metadata describes the data, for example, attributes anddomains, and outlines the table’s dimensions. FDs and RFDs
indicate the dependencies among attribute values and inherent data structures. In current federated learning frameworks[12], [16], metadata such as attribute names and domains
are commonly exchanged among different parties. However,the potential privacy implications of sharing this expanded
metadata scope remain unexplored.
A critical concern is that sharing metadata can jeopardize
data privacy. This risk stems from having access to metadata, allowing for data generation based on the underlying
data structures. This process of data generation, informedby the knowledge of metadata, poses a significant threat todata privacy. Therefore, our study aims to examine whether
sharing various types of metadata, including attribute names
and domains (Section III-A), functional dependencies (Section III-B), and relaxed functional dependencies (Section IV),might inadvertently lead to privacy breaches.
A. Attribute Name and Domain
We first discuss whether sharing attribute (feature) names
and domains will leak privacy.
Privacy Analysis. When generating a synthetic dataset, thegeneration of each tuple is independent; this implies thatgenerating the entire data set will follow a binomial distribution. Given attribute A, we denote θA as the probability ofgenerating the actual value of A correctly, i.e., the same as
the real dataset. Letting DA = Dom(A), we can see that for
random generation from a uniform distribution, θA = |D1A | .

The binomial distribution will give us the expected number ofcorrect generations as N θA , where N is the total number ofdata instances. As N , and θA are non-zero, a positive numberof values can be generated correctly, so following Definition
2.2, if N θA ≥ 1, we will have privacy leakage.
Example 3.1: Considering the attributes in Table II andthe attribute Age and department, which has a domain from
[18,26] containing 9 values. So then the probability of generating a tuple with the identical age value as the real dataset is 91 .
Given there are only 4 data points, there will be a probabilityof 94 of generating any age correctly within the table, so thelikelihood of privacy leakage is low. However, for the domainof department, there are only 3 departments, so the probabilityof random generating the department is 13 , so the expectedvalue would be 43 , meaning that we would expect there to be
one correct guess.
B. Functional Dependency
Consider a functional dependency from attribute A → B,
having of domains DA = Dom(A), DB = Dom(B) respectively; we can infer the probability of correct generation to be
θA = |D1A | and θB = |D1B | . The expected value of generating
the correct value of A will be N θA .
Privacy Analysis. Givena functional dependency A → B
Sand ai ∈ DA , B = πA . For generating the mappings thatsatisfy the dependencies A → B, the probability of generating
the mapping from A to B is P (B|A = ai ) = D1B . Data
generation occurs once across the dataset, which are determined by functional dependencies. An FD A → B reveals
underlying relationships A and B, allowing for their onetime initialization throughout the dataset without necessitating
explicit knowledge of each dependency, thereby facilitating thederivation of relationships directly from their definitions.
The FD A → B indicates that A refines B, meaningthat |DA | ≥ |DB |. Following a binomial distribution, thenumber of correctly generated dependencies is E(B|A) =|DA |=⇒ E(B|A) ≥ 1. It means there will be at least|DB |one correct mapping between A and B. However, the total
expected value of generating the correct values of A and B is
N θA E(B|A)|A| , which would be the same as random generation.
The generation of the values of attributes A, B will solely
depend on the values of the synthetic dataset; we have theexpected value of |DnA | values are correct. Then, for all of thecorrect values, we assume the number of correct values will
be dependent on the domain of A.
Example 3.2: Consider the example in Table II, and the
FD Salary → Age. Assuming the domain of Age is in therange of values [18, 26] and the salary is in the range [20, 35]
in thousands; there is an FD between salary and age. We cangenerate values for salary such as {20, 25, 30, 35}, and then the
mappings can be generated as 20 → 20, 25 → 23, 25 → 25,
35 → 26. This mapping satisfies the definition of functional
dependency. From the mapping, if tuples have a salary of 20k,
then the age value is 20.
A correct mapping would mean the mapping is always
correct; consequently, if the mapping is incorrect, it would

always be incorrect. Whereas, for random generation, correctly
generating the age attribute will not depend on the generationof the salary attribute.
The above argument can be extended to more than one functional dependency. Consider 3 attributes A, B, C ⊂ R, of relation R , with domain DA = Dom(A), DB = Dom(B), DC =Dom(C). The property of transitivity, states that if A → B
and B → C, then the value of A will decide B, which in turndecides the value of C. The mapping generation between B
and C is an identical procedure to that utilized for A andB, given the independence of these dependencies. Relative
to the current information disclosure level, communicating
functional dependencies, in conjunction with attribute names
and domains, does not exacerbate privacy leakage.
IV. P RIVACY A NALYSIS OF RFD S
Extensive research has been conducted on relaxed functional
dependencies (RFDs), with 35 prominent types of RFDs
compared in a survey [9]. However, a significant proportion ofthese RFDs represent variations of a core set. Therefore, in thissection, we have selectively conducted a privacy analysis of asubset of representative RFDs, with the arguments applicableto their variations.
A. Approximate Functional Dependency
Approximate functional dependency (AFD) is a common
variation of regular function dependency with the inclusionof the g3 error [14]. The g3 error states that given relations
R, there is a subset of relations ∃R1 ∈ R such that for
attributes A, B ⊂ R the functional dependency A → B holdson the relation R without excluding R1 . The error term is
1|, meaning that for this RFD, if
defined to be ϵ = |R|−|R|R|
an ϵ proportion of points are removed from relation R thenthe functional dependency would hold. This can be seen tobe similar to the probabilistic functional dependency (PFD)
definition, except being defined on the entire schema, it isdefined on the partitions of A [21].
Privacy Analysis. The expected value will include a factor for1
ϵ to the expected value of strict functional dependency. ImplyNϵ
ing that we will have an |A||B|of random generated data andNϵ|A||B| . The total amount of correct data generated will be thesame as strict functional dependency and random generation.
Similar to functional dependency, the 1 − ϵ proportion will
belong to a subset of partitions of A, and the ϵ proportion ofdata generated correctly will be scattered across all partitions.
We will arrive at the same expression for FD, so the privacy
conclusion for AFD is the same as FD.
B. Numerical Dependency
Numerical Dependency enforces a cardinality constraint on
attribute X, stipulating that each value of X is associated withno more than K values in attribute Y. This constraint meansthat given the domain of Y, there are at most K unique values
that each value of X can map to.
Privacy Analysis. For each attribute of X, we would have the1probability θX = |X|of correctness leading to the expectedvalue of N θX , and generating mapping from X → Y follows
a hyper-geometric distribution [20]. Generation of the mappingfrom X to Y would depend on random selection, or we canassume that the mappings all have the same cardinality. As foreach value of X, the domain of attribute Y is partitioned into
one that is valid in the original and one that is not. Throughrandom selection, the expected value of correct mappings
is n KN , where N = |DY |, DY = Dom(Y ) and K is the
cardinality of the partition of X, n is the number of samples
we are selecting.
For the generation of attribute Y, the mappings generated
that would be correct would be k K
N , where the assumption isthat N >> K. For each value of X, by the hyper-geometric
distribution, the expected value of generating correct mappings
2
is |DkY | . The probability of finding at least one correct mapping((|DYK|−K)). The
that satisfies the dependency is thus 1 −(|DKY |)
probability of selecting the correct map from the generated
mappings is selecting |DKY | . As the selection is independent,
the probability of selecting X and Y values both correctly has
a probability of |DY K||DX | . This means that the expected valueof generating the pair of attributes X and Y both correctly is
NK|DX ||DY | . However, there is the possibility that that is not
the case, that if k > N2 , then there would be guaranteed
at least | N2 − k| dependencies correct. This situation would
significantly increase the expected value for privacy leakage.
C. Order Dependency
Unlike approximate and functional dependencies predicatedon equality, order dependency is established based on inequality and ordering. This applies to categorical and continuous
attributes, as ordering is definable across all variable types.
We can define the dependency to be for a relation R if we
let X, Y ⊂ R, such that ∀t, u ∈ R if t[X] ≤ u[X] →t[Y ] ≤ u[Y ]. If there is an order dependency from attribute
X to Y, for any tuple, if X increases, attribute Y’s value will
increase, i.e., the ordering attribute X will also order attribute
Y. Suppose we consider the order dependency from categorical
X to continuous Y attributes. In that case, this implies that
we know the number of intervals, as the definition of theorder dependency gives this. Thus, we can create a sequenceof yi , i ∈ 1, ...n where n is the size of the domain of X.
Forming partitions of the domain of Y into intervals denotedby [yi , yi+1 ].
The alternative would be if we have the order dependency
defined between continuous attributes X and Y, we can similarly discretize the domain of X. We can create intervals within
the domain of Y that satisfy order dependency. The discussion
for categorical attributes is discussed in Section IV-E.
′

Privacy Analysis. Suppose there are two sequences, {yi } and{yi } over the same domain. We want to obtain the probabilityof the intersections of the intervals created by the sequence′′[yi , yi+1 ] over the domain of the attribute Y. For the first′interval we re generating y1 against y1 . The probability that
′

y −y

1
1
we generate within the right interval is |D. This probabilityY|overlap of the intervalof correctness will be given by total remaining
size of the domain . We
are generating conditions on the previous interval for the next′and hereafter intervals. For generating y2 we know that it will′
be greater than y1 , so we must consider what will happen if we′′are generating y2 < y1 and when y1 > y2 , then the overlap of′′
the intervals [y1 , y2 ] and [y1 , y2 ] is ∅. If the overlap is theempty set, this would imply a zero probability; otherwise,
the probability would be non-zero. The probability that thevalue for attribute ′Y will be generated given value xi becomesmax(y−y ,0)

i+1
i
.
θyi =
ymax −yiThis probability will be used for each of the intervals tofind the probability is θxi ∗ θyi overlap between the initial
and terminal intervals due to a fixed domain. Consequently,
the probability that at least two partitions of attribute A will
exhibit non-zero values is guaranteed. The expected value forthe number of data instances that we will be able to generate
is given by two binomial distributions, with N θX θY numberof
P points generated correctly. The total expected value will be
i N θxi θyi , where θyi is defined as above.
Because of the high variance in this dependency definedfor continuous features, we would expect the error to be quite
high implying that the privacy leakage would be quite low.
It would also depend very heavily on the partitioning of thedomain of Y depends very heavily on the distribution of Y.
However, this distribution is not communicated, so we willassume a uniform distribution for our experiments.

D. Differential Dependencies
These dependencies arise from the principle of differentiation, where, given a metric for attribute X, a corresponding
dependency is established for a metric defined on attributes Y.
[22]. As we are working with continuous variables, we willconsider that having an error of ϵ would still leak privacy.
So we would have the expected value of n |D2ϵX | of correctly
generated points, where DX = Dom(X).
To fulfill this requirement, it is necessary that for a given
metric applied to attributes X, the attributes Y must meet theircorresponding metric criteria. This implies that if values of X
in tuples are proximal, then the Y values in those tuples should
also be proximal. To uphold this principle, intervals within thedomain of Y can be established to mirror the intervals on thedomain of X. In other words, given relation R, we have ∀t ∈ Rsuch that ∀ϵ > 0, ∃δ; ∀t[X] ∈ [xi − ϵ, xi + ϵ] =⇒ t[Y ] ∈[yi − δ, yi + δ].
Privacy Discussion of Differential Dependency. For every
value of X, a ball can be constructed around it, ensuringthat any value within this ball is mapped to a value withina corresponding ball centered around the Y attribute’s value.
A ball is a set of values of the attribute that are within an
equal distance from a specific value. We generate the correct
value with respect to the interval [x − ϵ, x + ϵ], this has aprobability of |D2ϵX | . Similarly, the probability of generating
the correct Y would follow a Markov process [17], as theinterval would be defined relative to previous intervals. If avalue resides within an interval previously generated, thenthe intervals of attribute X will exhibit overlap, leading toa consequent overlap in the intervals of attribute Y. The
likelihood of accurately generating the overall mappings isdetermined by the product of overlaps, normalized by therange. The generation of the attribute X will have a probability
2ϵx. For the attribute Y there is a probability ofof range(x)′y ∈ Rsyn , y ∈ Rreal the probability of generating the′′+ϵ]∩[y−ϵ,y+ϵ]
correct Y attribute value is [y −ϵ,yrange(Y. Giving us)
an overall
probabilityofgenerating
thecorrect
value to be′′
2ϵx [y −ϵ,y +ϵ]∩[y−ϵ,y+ϵ].
Theexpression
fortheexpectedvalue
range(X)range(Y )is similar to order dependency. It will heavily rely on theoverlapping of the generated intervals of the domain with theintervals of the real data.

E. Ordered Functional Dependencies (OFD)
An ordered functional dependency combines functional andorder dependency and can be defined as follows [18]. It isan OFD, X → Y , if we consider relation R and attributes
X, Y ⊂ R, and ∀ tuples t, u ∈ R, if t[X] = u[X] → t[Y ] =u[Y ] but also satisfying t[X] < u[X] =⇒ t[Y ] < u[Y ].
Privacy Discussion of Ordered Function Dependency. This
relationship imposes more significant restrictions compared tofunctional and order dependencies. Consequently, the mapping
generation adheres to a continuous time Markov chain model[17], facilitating the modeling of dependency transitions. Thismodel is characterized by a transition matrix that specifies
state change probabilities; the state changes are similar to themap for ordered functional dependencies. The target statescorrespond to the domain values of attribute B, rendering the
mapping generation akin to a time-variant, one-dimensional
directed random walk [23].
The probability of being correct depends on the transition
probabilities, and it turns from making a high-dimensional
choice to a binary one. But similar to other dependencies, thecorrectness will still follow a binomial distribution, except theprobability for the dependency is time-dependent; thus, theexpected value of the number of correct relations generated
is given by N θX θYt . A sample probability could be createdfrom a uniform distribution with respect to the total numberof remaining partitions Pi,i+1 = 1 − |X|−t|Y | . This will give us
a transition probability of 1 if we have reached the maximum
remaining partitions of A so that the relation will be preserved
as all values in the domain need to be covered. Following theargument in order and differential dependency, the distribution
within the attributes is unknown, meaning that we will also
assume the transition probability will be uniform.
The derivations allow us to conclude the data privacy
implications of the analyzed dependencies. The focus has
been on the implications on data privacy of functional andrelaxed functional dependency in conjunction with featurename and domain.

TABLE III
P RIVACY L EAKAGE OF C ONTINUOUS ATTRIBUTES
Dep
Rand Gen
Func Dep
Ord Dep
Num Dep

Attr 0580.49580.25581.43708.58Attr 21169.961172.41383.86NA

Attr 4
0.43
0.43
0.24
NA

Summary- Metadata, such as the domain of an attribute, enables
random generation with the risk of privacy leakage.
- Metadata such as functional and relaxed functional
dependencies can be communicated without extra privacy
leakage.

Attr 5114.17
114
17.33
NA

Attr 6
10.14
10.11
9.63
NA

Attr 7138.69138.6
139.44NA

Attr 8
1.71
1.71
1
NA

Attr 9
0.93
NA
1.41
NA

TABLE IV
P RIVACY L EAKAGE OF C ATEGORICAL ATTRIBUTES
Dependency
Random Generation
Functional Dep
Order Dep
Numerical Dep

Attr 14444.082
44
56

Attr 34443.95432
NA

Attr 1133
32.81529
NA

Attr 12
44
NA
47
NA

V. E VALUATIONThis section shows the preliminary experimental evaluationof our main contribution: privacy analysis over relaxed functional dependencies. The evaluation will be bifurcated basedon data types: categorical and continuous, as delineated earlier.
Dataset. To assess the practical utility of our solution, we test
over a commonly used dataset, echocardiogram [4] from the
FD/RFD repeatability project2 . We chose the echocardiogram
dataset as we can discover functional dependencies, orderdependencies, and numerical dependencies from this dataset.
From other datasets, we can only discover trivial dependencies
or oversimplified mappings, which do not serve the purposeof our discussion. Echocardiogram contains 132 rows and 13
attributes. We present the results of the categorical attributesin Table IV and those of the continuous attributes in Table III.
We have performed the validation based on the definitions forprivacy leakage from Section II. The validation metric will be
exact matching and the mean squared error (MSE) for categorical and continuous attributes. All generations derive from thepredefined dependencies. The dependencies form a directed
graph between the attributes which is used for generation. A
fundamental assumption underlying our methodology is thatthe distribution remains undisclosed. The original raw data
will remain in possession of the original possessor.
Table IV shows the number of positive matches for eachmethod using random generation or with functional dependencies, order dependencies, or numerical dependencies. Amongthe four attributes, values expressed by NA are the attributes
that were not discovered for the specific dependency; thus,
the dependency cannot be utilized for generating the attribute.
The results of positive matches with functional dependencies
and order or numerical dependencies are close to a random
generation, indicating these dependencies add little value if amalicious party tries to generate a syntactic dataset to mimic
the real dataset. Such an observations are consistent with ourderivations and conclusions from Section III-B and IV.
The precise index of the appropriate generation may not be
critically important, contingent upon the context. To illustrate,
2 https://hpi.de/naumann/projects/repeatability/data-profiling/fds.html

consider a collaboration between a financial institution and an
e-commerce platform with the goal of loan approval classification. The latter may aim to implement targeted advertising,which does not align with the primary objective. The accurate
generation of information can culminate in more effective
targeted advertisements compared to no advertisements. Operating under the presumption that all data values are accurate,
a proportion of recommendations will facilitate appropriate
recommendations. Conversely, inaccurate advertisements yield
results comparable to scenarios without available data.
Table III shows the MSE of the generated attribute values
against the real values for the discovered dependencies. The
MSE is the mean error over many generation rounds todecrease the variance of the error. Following our assumptions,this would be the expected value over this dataset. Different
data ranges will, of course, lead to very different MSE values.
We can interpret these values as an indicator of a value ofepsilon to indicate leakage. Comparing the values in the table,
we can conclude that the privacy leakage caused by having
dependencies is not more than guessing. Because a larger
MSE and fewer exact matches mean less privacy leakage. The
outcomes for FDs and RFDs corroborate our prior discussions
regarding continuous variables. It is more evident for thecontinuous variables regarding certain RFDs within datasets.
VI. C ONCLUSION
Our examination addressed various metadata characteristics
of datasets pertinent to the preparation phase for VFL. The
metadata we discussed are feature names, feature domains,functional dependencies, and relaxed functional dependencies.
Our findings indicate that specific amalgamations of metadata
can precipitate privacy breaches. Notably, privacy leakage
was observed to be analogous to instances where featurenames, domains, and types were disclosed. We have shownthat functional and relaxed functional dependencies do notleak more privacy. We can conclude that feature names anddependencies should be communicated without the domain
and type. We have shown that RFDs can be communicatedas metadata for VFL without leaking more privacy.

R EFERENCES[1] General Data Protection Regulation (GDPR) – Official Legal Text —gdpr-info.eu. https://gdpr-info.eu/. [Accessed 01-11-2023].
[2] Information privacy act 2009. https://www.legislation.qld.gov.au/view/
pdf/inforce/current/act-2009-014. (Accessed on 08/31/2023).
[3] Personal information protection law of the people’s republic of china.
http://en.npc.gov.cn.cdurl.cn/2021-12/29/c 694559.htm. (Accessed on
08/31/2023).
[4] Echocardiogram. UCI Machine Learning Repository, 1989. DOI:
https://doi.org/10.24432/C5QW24.
[5] Health Insurance Portability and Accountability Act of 1996 (HIPAA)— CDC, Nov 1996.
[6] Tobias Bleifuß, Susanne Bülow, Johannes Frohnhofen, Julian Risch,Georg Wiese, Sebastian Kruse, Thorsten Papenbrock, and Felix Naumann. Approximate discovery of functional dependencies for large
datasets. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, CIKM ’16, page
1803–1812, New York, NY, USA, 2016. Association for Computing
Machinery.
[7] Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios
Kementsietsidis. Conditional functional dependencies for data cleaning.
In 2007 IEEE 23rd International Conference on Data Engineering,
pages 746–755, 2007.
[8] D. Burago, Y. Burago, and S. V. Ivanov. A course in metric geometry.
Graduate Studies in Mathematics, 2001.
[9] Loredana Caruccio, Vincenzo Deufemia, and Giuseppe Polese. Relaxedfunctional dependencies—a survey of approaches. IEEE Transactions
on Knowledge and Data Engineering, 28(1):147–165, 2016.
[10] Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, Dimitrios
Papadopoulos, and Qiang Yang. Secureboost: A lossless federated
learning framework. IEEE Intelligent Systems, 36(6):87–98, nov 2021.
[11] Aloni Cohen. Attacks on deidentification’s defenses. In 31st USENIX
Security Symposium (USENIX Security 22), pages 1469–1486, Boston,
MA, August 2022. USENIX Association.
[12] Fangcheng Fu, Huanran Xue, Yong Cheng, Yangyu Tao, and Bin
Cui. Blindfl: Vertical federated machine learning without peeking into
your data. In Proceedings of the 2022 International Conference on
Management of Data, SIGMOD ’22, page 1316–1330, New York, NY,
USA, 2022. Association for Computing Machinery.
[13] Ykä Huhtala, Juha Kärkkäinen, Pasi P. Porkka, and Hannu (TT)Toivonen. Tane: An efficient algorithm for discovering functional andapproximate dependencies. Comput. J., 42:100–111, 1999.
[14] Jyrki Kivinen and Heikki Mannila. Approximate inference of functional dependencies from relations. Theoretical Computer Science,
149(1):129–149, 1995. ICDT.
[15] Yang Liu, Yan Kang, Tianyuan Zou, Yanhong Pu, Yuanqin He, Xiaozhou Ye, Ye Ouyang, Ya-Qin Zhang, and Qiang Yang. Verticalfederated learning: Concepts, advances and challenges. arXiv preprint
arXiv:2211.12814, 2022.
[16] Xinjian Luo, Yuncheng Wu, Xiaokui Xiao, and Beng Chin Ooi. Featureinference attack on model predictions in vertical federated learning. In
2021 IEEE 37th International Conference on Data Engineering (ICDE),
pages 181–192, 2021.
[17] A. A. Markov. The theory of algorithms. Journal of Symbolic Logic,
18(4):340–341, 1953.
[18] Wilfred Ng. Ordered functional dependencies in relational databases.
Information Systems, 24(7), 1999.
[19] Raghu Ramakrishnan, Johannes Gehrke, and Johannes Gehrke.
Database management systems, volume 3. McGraw-Hill New York,
2003.
[20] J.A. Rice. Mathematical Statistics and Data Analysis. Advanced series.
Cengage Learning, 2007.
[21] Dan Simovici, Dana Cristofor, and Laurentiu Cristofor. Impurity
measures in databases. Acta Informatica, 38, 10 2002.
[22] Shaoxu Song and Lei Chen. Differential dependencies: Reasoning anddiscovery. ACM Trans. Database Syst., 36(3), aug 2011.
[23] H. M. Taylor and S. Karlin. Markov chains. An Introduction to
Stochastic Modeling, pages 79–163, 2011.
[24] Paul Voigt and Axel Von dem Bussche. The eu general data protection
regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152676):10–5555, 2017.

[25] Daisy Zhe Wang, Xin Luna Dong, Anish Das Sarma, Michael J.
Franklin, and Alon Y. Halevy. Functional dependency generation andapplications in pay-as-you-go data integration systems. In International
Workshop on the Web and Databases, 2009.
[26] Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated
machine learning: Concept and applications. ACM TIST, 10(2), jan 2019.