# Certified Data Removal in Sum-Product Networks

Alexander Becker
Chair of Artificial Intelligence, Computer Science
TU Dortmund University
Dortmund, Germany
<EMAIL_ADDRESS>&Thomas Liebig
Chair of Artificial Intelligence, Computer Science
TU Dortmund University
Dortmund, Germany
<EMAIL_ADDRESS>
###### Abstract

Data protection regulations like the GDPR or the California Consumer Privacy
Act give users more control over the data that is collected about them.
Deleting the collected data is often insufficient to guarantee data privacy
since it is often used to train machine learning models, which can expose
information about the training data. Thus, a guarantee that a trained model
does not expose information about its training data is additionally needed. In
this paper, we present UnlearnSPN – an algorithm that removes the influence of
single data points from a trained sum-product network and thereby allows
fulfilling data privacy requirements on demand.

_Keywords_ Sum-Product Networks $\cdot$ Data Privacy $\cdot$ Unlearning
$\cdot$ Forgetting $\cdot$ Trustworthy ML

This research has been funded by the Federal Ministry of Education and
Research of Germany and the state of North-Rhine Westphalia as part of the
competence center for machine learning ML2R (01–S18038A) and the Lamarr-
Institute for Machine Learning and Artificial Intelligence (LAMARR22B).

##  1 Introduction

Due to legal requirements like the European General Data Protection Regulation
(GDPR), the California Consumer Privacy Act, and many others, users gain more
control over their personal data collected daily. The right to be forgotten is
of particular importance, which states that collected data must be deleted
when requested. Deleting data is often insufficient to provide real data
privacy. This is especially the case if the data was used to train machine
learning models since they might expose information about their training data
via white-box or even black-box access. Motivated by this, the field of
Machine Unlearning and Forgetting gained more and more attention. So far,
research mostly focused on unlearning in deep neural networks [1, 2, 3, 4, 5]
and linear models [6, 2, 5], but also in random forests [7] and clustering
algorithms [8]. While some of those unlearning algorithms were only evaluated
empirically, some provide strong privacy guarantees. The privacy term that is
usually used in the domain of machine unlearning is that of certified removal
[5]. Similar to differential privacy [9], certified removal compares
unlearning results with retraining without the target data point. Simply put,
if the result of unlearning could also be obtained via retraining with a
similarly high chance, then the unlearning algorithm guarantees a certain
degree of privacy since the results cannot be told apart with high
probability.

In this work, we will present an unlearning algorithm for sum-product
networks, which is the first to our best knowledge. In contrast to Crypto-SPN
[10], which guarantees privacy-preserving inference, our unlearning algorithm
preserves privacy on the model level. This means that no information about the
sensitive data points can be gained, even if an attacker has white-box access
to the model.

This work is structured as follows. First, we will provide all necessary
foundations on sum-product networks (Section 2) and certified removal (Section
3). This includes sum-product networks, the training algorithm LearnSPN, and
$\epsilon$-certified removal. In Section 4, we then present some modifications
of LearnSPN that are necessary to obtain a model that allows for certified
removal, followed by our unlearning algorithm UnlearnSPN. Finally, we evaluate
the runtime of UnlearnSPN experimentally in Section 5 and give some directions
for future research in Section 6.

The contributions of this work can be summarized as follows:

  * •

We present a modified version of LearnSPN that produces sum-product networks
that allow for certified data removal.

  * •

We present the first unlearning algorithm for sum-product networks –
UnlearnSPN.

  * •

We prove that UnlearnSPN is a 0-certified removal algorithm and, therefore,
perfectly removes the influence of target data points.

  * •

In our experiments, we show that UnlearnSPN provides a speed-up of 10-58%
compared to retraining. At the same time, the modified training algorithm only
slightly increases the initial training duration.

##  2 Sum-Product Networks

Sum-product networks (SPNs) form a class of probabilistic graphical models
that gained popularity over the last few years and were first presented by
Poon and Domingos in 2011 [11]. The main idea is to represent a probability
distribution employing mixing and factorizing univariate distributions. This
allows the representation of more complex distributions by only using sums and
products, directly leading to the definition of SPNs.

######  Definition 1 (Sum-Product Network [11]).

Let $X$ be a dataset defined over variables $V$. An SPN $\Phi$ is a rooted
acyclic directed tripartite graph, where

  * •

every leaf node represents a univariate probability distribution $P(X_{|v})$
with $v\in V$,

  * •

each sum node $s$ represents a mixture of its children
$P_{s}(X_{|scope(s)})=\sum_{c\in
children(s)}\omega_{s,c}P_{c}(X_{|scope(c)})$,

  * •

each product node $p$ represents a factorization of its children
$P_{p}(X_{|scope(p)})=\prod_{c\in children(p)}P_{c}(X_{|scope(c)})$.

$\omega_{s,c}$ is a non-negative weight assigned to the edge $(s,c)$, and
$\sum_{c\in children(s)}\omega_{s,c}=1$ for each sum node $s$.

The scope of a node is defined as the subset of variables the node resp. the
corresponding distribution argues about. With $X_{|V^{\prime}}$ we denote the
dataset $X$, where only the variables $V^{\prime}\subseteq V$ are considered.

The sum nodes in an SPN represent mixture models, while the product nodes
represent factorizations. In order to obtain meaningful mixtures and
factorizations, the scopes of the corresponding distributions must be equal
for sum nodes and disjunct for product nodes. From a data perspective this
means that the dataset $X$ is split into $k$ partition sets
$X_{1},\dots,X_{k}$ at sum nodes, and sliced into $m$ sets
$X_{|V_{1}},\dots,X_{|V_{m}}$ at product nodes with
$\bigcap_{i\in[1,m]}V_{i}=\emptyset$ and $\bigcup_{i\in[1,m]}V_{i}=V$. The
root of an SPN then represents the complete joint distributions over all
variables in $V$ and with respect to the whole dataset $X$.

A common way to learn both the structure and the parameters of an SPN is the
LearnSPN algorithm (Algorithm 1) [12]. Here, we assume that all leaf nodes
must represent univariate distributions and that the dataset will not be split
any further if it is only defined over a single variable. Also, note that the
clustering algorithm and the independency analysis used in LearnSPN can be
chosen freely. There are five operations that are used to create nodes in an
SPN.

0: Dataset $X$ defined over variables $V$; threshold $t$

0: SPN $\Phi$

1: if $|V|=1$ then

2: return $\textsc{CreateLeaf}(X)$

3: if $\exists v\in V.\sigma^{2}(X_{v})=0$ then

4: if $\forall v\in V.\sigma^{2}(X_{v})=0$ then

5: return $\textsc{NaiveFactorization}(X)$

6: else

7: return $\textsc{SplitUninformativeVariables}(X)$

8: if $|X|\leq t\vee(\neg clusters\wedge\neg independencies)$ then

9: return $\textsc{NaiveFactorization}(X)$

10: if $\neg independencies$ then

11: return $\textsc{SplitData}(X)$

12: else

13: return $\textsc{SplitVariables}(X)$

Algorithm 1 LearnSPN

CreateLeaf estimates an univariate distribution from $X$. The kind of
distribution depends on the variable itself. Note that CreateLeaf will only be
called, if the dataset $X$ is defined over a single variable, i.e. $|V|=1$.

The NaiveFactorization creates a product node as the SPN’s root and a leaf
node for each variable in $V$. There are two cases in which a naive
factorization is performed. First, if all variables are uninformative,
$\forall v\in V.\sigma(X_{v})=0$. Second, if there is still more than one
variable present, and none is uninformative, but the number of data points $X$
is smaller than $t$. The threshold $t$ guarantees that the number of data
points used to estimate the univariate distributions in the leaf nodes is
large enough for reasonable estimation.

Similarly, SplitUninformativeVariables creates a product node as the root and
a leaf node for each uninformative variable, while $X$ with respect to the
remaining informative variables will be processed recursively.

SplitData first performs a clustering algorithm, which will result in a
partition of $X$. Then, a sum node will be created as the root, and each data
subset in the partition will be processed recursively. The edge weights are
defined as the ratio between the number of data points in the clusters and the
total number of data points.

SplitVariables performs a pairwise independence analysis of all variables.
Afterward, the coefficients from the analysis are used to build an adjacency
matrix indicating which variables are independent resp. dependent. The
variables are split into connected components using the adjacency matrix. For
each resulting variable subsets, the dataset $X$ is processed recursively.

Since we will often argue about the operation decision process of LearnSPN in
the following, we illustrate it in Figure 1 for easier comprehension.

$|V|=1$NaiveFactorizationSplitUninformativeVariablesSplitDataSplitVariables$\exists
v\in V.\ \sigma^{2}(X_{v})=0$111110000$\forall v\in V.\
\sigma^{2}(X_{v})=0$0$|X|\leq t\vee(\neg independencies\wedge\neg
clusters)$$\neg independencies$CreateLeafNaiveFactorization

Figure 1: Operation decision process in LearnSPN (Algorithm 1).

##  3 Certified Removal

In the domain of machine unlearning, privacy is usually described in the sense
of certified removal (Definition 2) as presented by Guo et al. [5].

######  Definition 2 ($\epsilon$-Certified Removal [5]).

Let $\mathcal{D}$ be a data space, $\mathcal{H}$ a hypothesis space,
$\mathcal{A}:\mathcal{P}(\mathcal{D})\rightarrow\mathcal{H}$ a learning
algorithm and $\mathcal{U}:\mathcal{H}\times\mathcal{D}\rightarrow\mathcal{H}$
an unlearning algorithm. $\mathcal{U}$ is called $\epsilon$-certified removal
($\epsilon$-CR), if and only if

$e^{-\epsilon}\leq\frac{P(\mathcal{U}(\mathcal{A}(X),x)\in\mathcal{T})}{P(\mathcal{A}(X\setminus\\{x\\})\in\mathcal{T})}\leq
e^{\epsilon}$

holds $\forall\mathcal{T}\subseteq\mathcal{H},X\subseteq\mathcal{D},x\in X$.

The intuition behind $\epsilon$-CR is that if the result of unlearning could
also likely be obtained by retraining, then the unlearning algorithm
successfully removes the influence of the target data point from the model.
Depending on the model class, it is neither necessary nor expected that
unlearning yields the exact same result as retraining. Therefore,
$\epsilon$-CR argues about arbitrary hypothesis sub-spaces
$\mathcal{T}\subseteq\mathcal{H}$ in which the results of unlearning and
retraining may fall. In order to guarantee $\epsilon$-CR, the ratio of the
chances for both results falling into $\mathcal{T}$ must be limited by
$e^{-\epsilon}$ and $e^{\epsilon}$. The closer $\epsilon$ is to 0, the higher
the privacy guarantees.

##  4 Remove Data from SPNs

In the following, we will describe which additions to the LearnSPN algorithm
are necessary to enable the resulting SPN for certified data removal.
Afterward, we present the revision function that maps an operation chosen
during training to the operation that would have been chosen if a specific
data point had not been present in the training data. With this being an
essential part of unlearning, we finally present UnlearnSPN – a 0-CR algorithm
that perfectly removes the influence of a data point.

###  4.1 Certified Removal Enabled SPNs

In order to obtain a certified removal enabled SPN, some small additions to
LearnSPN must be made. During training, we define a state for each node that
contains all the information necessary for efficiently performing unlearning
afterward. More precisely, for each node $n$ we define a state as an 8-tuple
$s=(sc$, $op$, $X$, $N$, $independencies$, $clusters$,
$exist\\_uninformative$, $all\\_uninformative)$, where $sc$ is the scope of
$n$, $op$ the operation chosen to create the sub-SPN rooted at $n$, $X$ the
dataset of size $N$ used for training, $independencies$ and $clusters$
indicate whether there exist independent variables or data clusters, and
$exist\\_uninformative$ and $all\\_uninformative$ indicate whether there exist
uninformative variables or if all variables are uninformative. For sum and
product nodes, we additionally store an instance of the clustering algorithm
and the independency analysis, respectively. For leaf nodes, we also store
additional information that will allow us to update the univariate
distribution quickly. Storing a state for each node in an SPN yields an
additional memory consumption of $\mathcal{O}(|V|+|X|)$ per node. The
additional memory consumption induced by storing the clustering and the
independency analysis depends on the choice of the splitting algorithms. Since
we keep track of the operations used during training, it is important that the
SPN must not be pruned afterward; otherwise, the operation used for creating a
sub-SPN becomes ambiguous. Except for the above additions, no further changes
to LearnSPN are necessary.

Also, note that even though arbitrary clustering algorithms and independency
analyses can be used, it is highly recommended to use algorithms that allow
0-certified data removal or can be updated in a reasonable amount of time to
reduce the cost of removing data from the SPN.

###  4.2 Revising the Choice of Operation

Next, we introduce the revision function $rev$ (Definition 3), which will be
an essential part of our unlearning algorithm.

######  Definition 3.

Let $X$ be a dataset defined over variables $V$. Let $x\in X$ be a data point
and $X^{\prime}=X\setminus\\{x\\}$. Let CreateLeaf (CL), NaiveFactorization
(NF), SplitUninformativeVariables (SU), SplitData (SD) and SplitVariables (SV)
be the operations used in LearnSPN (Algorithm 1). The revision function $rev$
takes an operation and maps it to another operation in the following manner:

$\displaystyle\text{CL}\mapsto\text{CL}$
$\displaystyle\text{NF}\mapsto\begin{cases}\text{NF},&\text{if }\forall v\in
V.\sigma^{2}(X_{v})=0\\\ \text{NF},&\text{if }\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0\\\ \text{SU},&\text{if }\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge\not\exists v\in
V.\sigma^{2}(X_{v})=0\\\ \text{NF},&\text{if }|X|\leq t\vee(\neg
clusters\wedge\neg independencies)\\\ \text{SD},&\text{if }\neg
independencies\\\ \text{SV},&\text{otherwise}\end{cases}$
$\displaystyle\text{SD}\mapsto\begin{cases}\text{SU},&\text{if }\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge\not\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0\\\ \text{NF},&\text{if }\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0\\\ \text{NF},&\text{if}\not\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge|X^{\prime}|\leq t\\\
\text{NF},&\text{if}\not\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge\neg clusters\\\ &\wedge\neg
independencies\\\ \text{SV},&\text{if}\not\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge|X^{\prime}|>t\\\ &\wedge
independencies\\\ \text{SD},&\text{otherwise}\\\ \end{cases}$
$\displaystyle\text{SV}\mapsto\begin{cases}\text{SU},&\text{if }\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge\not\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0\\\ \text{NF},&\text{if }\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0\\\ \text{NF},&\text{if}\not\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge|X^{\prime}|\leq t\\\
\text{NF},&\text{if}\not\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge\neg clusters\\\ &\wedge\neg
independencies\\\ \text{SD},&\text{if}\not\exists v\in
V.\sigma^{2}(X^{\prime}_{v})=0~{}\wedge|X^{\prime}|>t\\\
&\wedge~{}clusters\wedge\neg independencies\\\ \text{SV},&\text{otherwise}\\\
\end{cases}$ $\displaystyle\text{SU}\mapsto\begin{cases}\text{SU},&\text{if
}\exists v\in V.\sigma^{2}(X^{\prime}_{v})>0\\\ \text{NF},&\text{otherwise}\\\
\end{cases}$

$\sigma^{2}$ denotes the variance and $t$ is the data threshold used in
LearnSPN.

Note that the order of cases in Definition 3 matters. For each case, we expect
that the conditions for all cases above are falsified. In Theorem 1, we show
that $rev$ is sound and complete, i.e., it exactly corresponds to the change
in the chosen operation in LearnSPN when a certain data point would not have
been present during training.

######  Theorem 1.

Let $X$ be a dataset defined over variables $V$, $x\in X$ a data point,
$X^{\prime}=X\setminus\\{x\\}$ and $s$ be a random seed. The revision function
$rev$ maps an operation $op_{old}$ to $op_{new}$ such that

$\displaystyle
rev(op_{old})=op_{new}\Leftrightarrow~{}\textsc{LearnSPN}(X;s)\text{ chooses
}op_{old}\wedge\textsc{LearnSPN}(X^{\prime};s)\text{ chooses }op_{new}.$ (1)

###### Proof of Theorem 1.

Since LearnSPN is a randomized algorithm, we assume LearnSPN($X$; $s$) and
LeanrSPN($X^{\prime}$; $s$) to be seeded with the same random seed $s$. This
way LearnSPN becomes a deterministic algorithm. For reasons of simplicity we
omit the random seed $s$ in the further course. In the following, we prove the
equivalence stated in Theorem 1 for each input operation separately. To follow
the reasoning in this proof more easily, we refer to the operation decision
process illustrated in Figure 1.

Case Create Leaf (CL): LearnSPN($X$) chooses CL, if and only if $|V|=1$.
Removing an arbitrary data point $x$ from $X$ has no influence on the number
of variables $|V|$. Thus, $\textsc{LearnSPN}(X)\text{ chooses
}\textsc{CL}\Leftrightarrow~{}|V_{X}|=1\Rightarrow|V_{X^{\prime}}|=1\Leftrightarrow\textsc{LearnSPN}(X^{\prime})\text{
chooses }\textsc{CL}.$ If $op_{old}=\textsc{CL}$, then removing a data point
$x$ from $X$ does not change the chosen operation, i.e.
$op_{old}=\textsc{CL}=op_{new}$. Since $rev(\textsc{CL})=\textsc{CL}$, the
equivalence in Equation 1 holds.

Case NaiveFactorization (NF): There are two cases in which LearnSPN$(X)$
chooses NF (see Figure 1): 1) $|V|>1\wedge\forall v\in V.\sigma^{2}(X_{v})=0$,
and 2) $|V|>1\wedge\not\exists v\in V.\sigma^{2}(X_{v})=0\wedge|X|\leq
t\vee~{}(\neg clusters\wedge\neg independencies)$.

If NF was chosen due to case 1): The number of variables is unaffected by
removing $x$ from $X$, i.e. $|V_{X}|>1\Rightarrow|V_{X^{\prime}}>1|$. We know
that all points must be equal if the variance is 0: $\forall v\in
V.\sigma^{2}(X_{v})=0\Leftrightarrow\forall v\in V.\frac{1}{|X|}\sum_{p\in
X_{v}}(p-\mu_{v})^{2}=0\Leftrightarrow\forall v\in V.\forall p\in
X_{v}.(p-\mu_{v})^{2}=0\Leftrightarrow\forall v\in V.\forall p,q\in
X_{v}.p=q$, where $\mu_{v}$ is the mean value of $X_{v}$. After removing $x$
from $X$, we know that the remaining data points are still all equal.
Therefore, $\forall v\in V.\sigma^{2}(X_{v})=0\Leftrightarrow\forall v\in
V.\forall p,q\in X_{v}.p=q\Rightarrow\forall v\in V.\forall p,q\in
X^{\prime}_{v}.p=q\Leftrightarrow\forall v\in V.\sigma^{2}(X^{\prime}_{v})=0$.
So, if 1) holds, then both LearnSPN($X$) and LearnSPN($X^{\prime}$) choose NF.
This mapping is captured by the first case of $rev$(NF) (see Definition 3).

If NF was chosen due to case 2): Again, we know that the number of variables
$|V|$ is unaffected. This is the case if all data points except for $x$ are
identical w.r.t. a non-empty variable subset $V^{\prime}\subseteq V$.

If $V^{\prime}=V$, then $\not\exists v\in V.\sigma^{2}(X_{v})=0,\text{but
}\forall v\in V^{\prime}.\sigma^{2}(X^{\prime}_{v})=0$. Nonetheless,
LearnSPN($X^{\prime}$) would choose NF since falsifying $\not\exists v\in
V.\sigma^{2}(X_{v})=0$ is equivalent to accepting the second condition of 1)
for LearnSPN($X^{\prime}$). So, if 2) holds for $X$ and $\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0$ both LearnSPN($X$) and LearnSPN($X^{\prime}$)
choose NF. This mapping is captured by the second case of $rev$(NF).

If $V^{\prime}\neq V$, then there exist some variables that become
uninformative when removing $x$: $\not\exists v\in
V.\sigma^{2}(X_{v})=0,\text{but }\exists v\in
V^{\prime}.\sigma^{2}(X^{\prime}_{v})=0$. However, there are also variables
that are still informative since $V^{\prime}\neq V$. In this case
LearnSPN($X^{\prime}$) would choose to split the uninformative variables
rather than performing a naive factorization (see Figure 1). Note that this
decision is independent of $|X|\leq t\vee(\neg clusters\wedge\neg
independencies)$. This mapping is captured by the third case of $rev$(NF).

Finally, it is also possible that all variables stay informative. In this
case, the chosen operation only depends on $|X|\leq t$ and the existence of
clusters and independencies. If $|X|\leq t\vee~{}(\neg clusters\wedge\neg
independencies)$ holds due to $|X|\leq t$, then we know that it also holds
after removing $x$ since $|X^{\prime}|<|X|\leq t$. The chosen operation would
still be NF. This is also the case if $|X|=t+1$. If it holds due to $\neg
clusters\wedge\neg independencies$, removing $x$ might induce the existence of
clusters or independent variables. Therefore, instead of a naive
factorization, SD or SV is chosen by LearnSPN. The three cases above are
captured by the last three cases of $rev(\textsc{NF})$.

Since $rev$(NF) correctly captures all of the above four cases, we know that
the equivalence stated in Equation 1 holds in this case.

Case SplitUninformativeVariables (SU): LearnSPN($X$) chooses to split
uninformative variables, if and only if $|V|>1\wedge\exists v\in
V.\sigma^{2}(X_{v})=0~{}\wedge\not\forall v\in V.\sigma^{2}(X_{v})=0$. Again
the number of variables is unaffected. Furthermore, we know that $\exists v\in
V.\sigma^{2}(X_{v})=0$ also holds after removing $x$, since for those
variables with variance 0 all data points must be equal. Thus, we only have to
distinguish the two cases in which $\not\forall v\in V.\sigma^{2}(X_{v})=0$ is
either satisfied or falsified after removing $x$: 1) $\not\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0$, and 2) $\forall v\in
V.\sigma^{2}(X^{\prime}_{v})=0$.

If 1) holds, we know that both LearnSPN($X$) and LearnSPN($X^{\prime}$) must
choose to split uninformative variables, since there exist uninformative
variables, i.e. $\exists v\in V.\sigma^{2}(X_{v})=0$, but not all variables
are uninformative (see Figure 1). In case that 2) holds,
LearnSPN($X^{\prime}$) would choose NF instead, since no informative variables
would be left. $rev$(SU) captures both cases and therefore, we know that the
equivalence in Equation 1 holds in this case.

Case SplitData (SD): LearnSPN($X$) chooses to split data, if and only if
$|V|>1\wedge\not\exists v\in V.\sigma^{2}(X_{v})=0\wedge|X|>t\wedge
clusters\wedge\neg independencies$.

The number of variables is again unaffected. As already argued above, removing
$x$ might yield a variance of 0 for some variables. Thus, it is possible that
$\exists v\in V.\sigma^{2}(X^{\prime}_{v})=0$. This implies that
LearnSPN($X^{\prime}$) would either choose a naive factorization or splitting
uninformative variables, depending on whether all variables become
uninformative. Both cases are covered by the first two cases of $rev$(SD).

In the following, we assume $\not\exists v\in V.\sigma^{2}(X_{v})=0$ to hold
after removing $x$. The condition $|X|>t$ can be falsified after removing $x$,
if $|X|=t+1>t=|X^{\prime}|$. In this case LearnSPN($X^{\prime}$) would choose
NF instead of SD, because $|X^{\prime}|$ goes below the minimum number of
required data points $t$. This is captured in the third case of $rev$(SD).

If the $|X|>t$ still holds after removing $x$, it can still be the case that
the $clusters$ condition is falsified afterward. This happens if removing $x$
results in a clustering, where all remaining data points belong to the same
cluster. At this point, we have to further distinguish between the two cases
where $\neg independencies$ is satisfied or falsified. If $\neg
independencies$ is still satisfied after removing $x$, then we know that
LearnSPN($X^{\prime}$) would choose NF, since there exists more than one
variable, no variables are uninformative, the dataset consists of at least
$t+1$ data points and there neither exist independent variables nor clusters
in the data. However, if removing $x$ induces the existence of independencies,
then LearnSPN($X^{\prime}$) would choose SV instead of SD. This will also be
the case if $clusters$ is still satisfied after removing $x$. These three
cases are all covered by the third to fifth case of $rev(\textsc{SD})$.

If there still exist clusters after removing $x$, then the decision of
LearnSPN($X^{\prime}$) only depends on the existence of independencies. If
there exist any independent variables, i.e. $independencies$ holds, then
LearnSPN($X^{\prime}$) would choose SV over SD. Otherwise,
LearnSPN($X^{\prime}$) would not revise the operation and stick with SD. This
is captured by the last two cases in $rev$(SD), which therefore satisfies the
equivalence in Equation 1 in case of $op_{old}=\textsc{SD}$.

Case Split Variables (SV): LearnSPN($X$) chooses to split variables, if and
only if $|V|>1\wedge\not\exists v\in V.\sigma^{2}(X_{v})=0\wedge|X|>t\wedge
independencies$.

The first three cases of $rev$(SV) are equivalent to $rev$(SD) (see above). In
case that removing $x$ also removes independencies such that $\neg
independencies$ holds, the decision of LearnSPN($X^{\prime}$) depends on the
existence of clusters. If no clusters exist, i.e. $\neg clusters$ holds, then
LearnSPN($X^{\prime}$) chooses NF (see Figure 1). On the other hand,
LearnSPN($X^{\prime}$) would choose SD over SV. If $independencies$ still
holds after removing $x$, then LearnSPN($X^{\prime}$) would also choose SV.
This is captured by the last three cases of $rev$(SV), which therefore
satisfies the equivalence in Equation 1 in case of $op_{old}=\textsc{SV}$.

In conclusion, we showed that for each of the five operations, the revision
function $rev$ correctly captures all changes in choosing an operation in
LearnSPN when removing a data point $x$ from the dataset $X$. Therefore
Theorem 1 holds in general. ∎

###  4.3 UnlearnSPN

Finally, we introduce UnlearnSPN – an unlearning algorithm for certified
removal enabled SPNs (Algorithm 2).

0: SPN $\Phi$, data point $x\in X$

0: SPN $\Phi$ without the influence of $x$

1: $st\leftarrow\textsc{State}(\Phi)$

2: if $x\notin st.data$ then

3: return $\Phi$

4: $op_{old}\leftarrow st.operation$

5: $op_{new}\leftarrow\textsc{ReviseOperation}(st,x)$

6: if ($op_{old}=$ SD $\wedge$ $op_{new}=$ SV) $\vee$($op_{old}=$ SV $\wedge$
$op_{new}=$ SD) $\vee$ ($op_{old}\in\\{$SV, SD$\\}$ $\wedge$ $op_{new}=$
SU)$\vee(op_{old}=\textsc{NF}\wedge op_{new}\in\\{\textsc{SD},\textsc{SV}\\})$
then

7: return LearnSPN($st.data\setminus\\{x\\}$)

8: if $op_{old}\neq op_{new}$ then

9: return NaiveFactorization$(st.data\setminus\\{x\\})$

10: switch ($op_{old}$)

11: /* call unlearning algorithm corresponding to $op_{old}$ */

12: end switch

Algorithm 2 UnlearnSPN

The key idea behind UnlearnSPN is that we reevaluate the decisions made during
training by using our revision function from Definition 3. If the chosen
operation does not change when removing the target data point $x$, we only
have to update the state and parameters of the root node and proceed with the
child nodes. If the chosen operation changes, we have to retrain the sub-SPN
rooted at the current node. If $x$ is not present in the data of the current
sub-SPN, then nothing has to be done. The conditions in lines 6-9 correspond
to the cases in $rev$, where the input operation differs from the output
operation. Note that lines 8-9 handle all cases where the new operation is a
naive factorization. Thus, instead of calling LearnSPN we directly perform the
naive factorization. If the old and new operation are the same, the updates
that must be made depend on the operation that created the current sub-SPN. We
refer to these updates as UnlearnCreateLeaf, UnlearnSplitData and so forth
(Algorithms 3, 4, 5, 6 and 7).

0: SPN $\Phi$, data point $x\in X$

0: SPN $\Phi$ without the influence of $x$

1: $st\leftarrow$State($\Phi$)

2: $st.num\\_data\leftarrow st.num\\_data-1$

3: $st.data\leftarrow st.data\setminus\\{x\\}$

4: for all $child\in st.children$ do

5: UnlearnCreateLeaf$(child,x)$

6: if $st.all\\_uninformative$ then

7: return $\Phi$

8: $\sigma^{2}\leftarrow\textsc{Variances}(st.data)$

9: if $\sigma^{2}_{V}=0$ for all $V\in st.scope$ then

10: $st.all\\_uninformative\leftarrow true$

11: $st.exist\\_uninformative\leftarrow true$

12: return $\Phi$

Algorithm 3 UnlearnNaiveFactorization

0: SPN $\Phi$, data point $x\in X$

0: SPN $\Phi$ without the influence of $x$

$st\leftarrow$State($\Phi$)

$st.num\\_data\leftarrow st.num\\_data-1$

$st.data\leftarrow st.data\setminus\\{x\\}$

UpdateUnivariateDistribution($\Phi$, $x$)

return $\Phi$

Algorithm 4 UnlearnCreateLeaf

0: SPN $\Phi$, data point $x\in X$

0: SPN $\Phi$ without the influence of $x$

$st\leftarrow$State($\Phi$)

$st.num\\_data\leftarrow st.num\\_data-1$

$st.data\leftarrow st.data\setminus\\{x\\}$

for all $child\in st.children$ where $child$ is a leaf node do

UnlearnCreateLeaf$(child,x)$

$\Psi\leftarrow$ non-leaf child of $\Phi$

$\sigma^{2}\leftarrow\textsc{Variances}(st.data)$

if $\sigma^{2}_{V}=0$ for any $V\in\textnormal{State}(\Psi).scope$ then

for all $V\in\textsc{State}(\Psi).scope\text{ with }\sigma^{2}_{V}=0$ do

$leaf\leftarrow\textsc{CreateLeaf}(st.data,V)$

Append($\Phi.children$, $leaf$)

$\Psi\leftarrow$ LearnSPN($st.data$ with remaining scope)

else

$\Psi\leftarrow$ UnlearnSPN($\Psi$, $x$)

return $\Phi$

Algorithm 5 UnlearnSplitUninformative Algorithm 6 UnlearnSplitData

0: SPN $\Phi$, data point $x\in X$

0: SPN $\Phi$ without the influence of $x$

$st\leftarrow$ State($\Phi$)

$clustering_{old}\leftarrow st.clustering$

$clustering_{new}\leftarrow$ Remove($clustering_{old}$, $x$)

if $clustering_{old}\neq clustering_{new}$ then

return SplitData($st.data\setminus\\{x\\}$)

$st.num\\_data\leftarrow st.num\\_data-1$

$st.data\leftarrow st.data\setminus\\{x\\}$

UpdateWeights($\Phi$, $x$)

$\Psi\leftarrow child\in\Phi.children$ with $x\in$ State$(child).data$

$\Psi\leftarrow$ UnlearnSPN($\Psi$, $x$)

return $\Phi$

Algorithm 7 UnlearnSplitVariables

0: SPN $\Phi$, data point $x\in X$

0: SPN $\Phi$ without the influence of $x$

$st\leftarrow$ State($\Phi$)

$variable\\_split_{old}\leftarrow st.variable\\_split$

$variable\\_split_{new}\leftarrow$ Remove($variable\\_split_{old}$, $x$)

if $variable\\_split_{old}\neq variable\\_split_{new}$ then

return SplitVariables($st.data\setminus\\{x\\}$)

$st.num\\_data\leftarrow st.num\\_data-1$

$st.data\leftarrow st.data\setminus\\{x\\}$

for all $child\in\Phi.children$ do

$child\leftarrow$UnlearnSPN($child$, $x$)

return $\Phi$

UnlearnNaiveFactorization updates a node that was created with NF. First, the
data point is removed from the data set. Then UnlearnCreateLeaf is called for
all child nodes. Next, we have to ensure that the indicators for uninformative
variables are also correctly updated. If all variables were already
uninformative, we do not have to make any changes since removing data points
cannot make variables informative again. Otherwise, we have to check if any or
all variables have a variance of 0 and update the indicators accordingly.

UnlearnCreateLeaf updates a leaf node by simply removing $x$ and updating the
univariate distribution such that it corresponds to the dataset without $x$.

UnlearnSplitUninformative updates a node that was created with SU. Again, we
have to remove $x$ from the dataset first. For SU we know that all but one
child are leaf nodes. All leaf nodes are updated by calling UnlearnCreateLeaf.
Next, we have to check if removing $x$ induced further uninformative
variables. If this is the case, we create new leaf nodes, estimate the
univariate distributions and add them as new child nodes. We have to retrain
the corresponding sub-SPN from scratch for the remaining informative variables
by calling LearnSPN. In case no new uninformative variables are introduced
when removing $x$, we process the non-leaf child by calling UnlearnSPN
recursively.

UnlearnSplitData is the only algorithm that is used for updating sum nodes.
Here, we remove $x$ from the clustering by either recomputing the clustering
with the same initialization on the remaining data or by actually removing it
if the clustering allows certified removal. If the clusters have changed due
to removing $x$, we have to retrain the sub-SPN starting with a SD operation.
Otherwise, we remove $x$ from the state, update the edge weights accordingly,
and call UnlearnSPN for the child node that was trained on the data subset
containing $x$.

UnlearnSplitVariables updates nodes that split variables by actually using the
SV operation. Here, we remove $x$ from the independency analysis by either
recomputing or updating if possible. If the independencies are affected by the
data removal, we retrain the sub-SPN from scratch, starting with SV, since the
variables split has changed. If the independencies are unaffected, we must
remove $x$ from the state and call UnlearnSPN recursively for all child nodes.

Next, we show in three steps that UnlearnSPN is a $\epsilon$ certified removal
algorithm with $\epsilon=0$. For this we separately handle the cases where the
operations chosen during training are preserved (Proposition 1) or changed
(Theorem 2) by UnlearnSPN.

######  Proposition 1.

Let $X$ be a dataset, $x\in X$ a data point, $X^{\prime}=X\setminus\\{x\\}$,
$s$ a random seed, $\Phi=$ LearnSPN(X; s) an SPN and
$\mathcal{T}\subseteq\mathcal{H}$ a hypothesis sub-space. If
$\textsc{LearnSPN}(X;s)$ chooses operation $op$ and
$\textsc{LearnSPN}(X^{\prime};s)$ chooses operation $op^{\prime}$ with $op\neq
op^{\prime}$, then

$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T}).$
(2)

###### Proof of Proposition 1.

From Theorem 1, we know that the revision function $rev$ is equivalent to the
change of the chosen operation when removing a data point $x$, i.e.
$rev(op)=op^{\prime}$. For UnlearnSPN($\Phi,x$) we know that if $op\neq
rev(op)=op^{\prime}$, the SPN will be retrained from scratch calling
LearnSPN($X^{\prime}$) (see Algorithm 2 lines 5-9). Note that in lines 8-9, we
explicitly perform a naive factorization, since we know that the new operation
that would be performed when calling LearnSPN($X^{\prime}$) would be a naive
factorization anyway. Therefore, we see that in all cases where $op\neq
rev(op)=op^{\prime}$ UnlearnSPN just calls LearnSPN and returns its result,
which concludes that UnlearnSPN($\Phi,x$) = LearnSPN($X^{\prime}$). This
implies
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$
for any hypothesis sub-space $\mathcal{T}$. ∎

In Proposition 1, we proved that updating a model via UnlearnSPN will result
in the same SPN as retraining it from scratch on the remaining data if the
chosen operations are different. For the retraining, we assume that the same
random seed is used as in the original training; otherwise, the results would
not be comparable.

In Theorem 2, we utilize our result from Proposition 1 and show that the
result obtained via UnlearnSPN also could have been obtained via retraining
with an equal chance in general.

######  Theorem 2.

Let $X$ be a dataset, $x\in X$ a data point, $X^{\prime}=X\setminus\\{x\\}$,
$\Phi=$ LearnSPN(X) an SPN and $\mathcal{T}\subseteq\mathcal{H}$ a hypothesis
sub-space, then
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$.

###### Proof of Theorem 2.

From Proposition 1 we already know that
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$
holds, if $op\neq rev(op)=op^{\prime}$, where $op$ is the operation chosen by
$\textsc{LearnSPN}(X;s)$ and $op^{\prime}$ the operation chosen by
$\textsc{LearnSPN}(X^{\prime};s)$ for random seed $s$. Thus, we only have to
prove the equation in Theorem 2 in case of $op=op^{\prime}$. We prove this
equality via structural induction over the structure of $\Phi$.

Base case: $\Phi$ only consists of a single node. This node must then be a
leaf node and represent an univariate distribution over $X$. From $rev$(CL) =
CL, we know that if LearnSPN($X$) creates a leaf node, so does
LearnSPN($X^{\prime}$). UnlearnSPN updates the univariate distribution of the
leaf node such that $P(X)\mapsto P(X^{\prime})$. Therefore, we know that
UnlearnSPN($\Phi$, $x$) = LearnSPN($X^{\prime}$), which implies
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$.

Induction hypothesis: Let $\Phi$ be an SPN with subSPNs
$\Phi_{1},...,\Phi_{k}$. $P(\textsc{UnlearnSPN}(\Phi_{i},x)\in\mathcal{T})$ =
$P(\textsc{LearnSPN}(X_{i}^{\prime})\in\mathcal{T})$ holds for all
$i\in[1,k]$, where $X_{i}^{\prime}$ corresponds to the remaining data used for
training $\Phi_{i}$.

Induction step: In the following, we distinguish the four remaining operations
that are used to build an SPN.

Case NaiveFactorization: In case of a naive factorization, we know that all
children must be leaf nodes. UnlearnSPN preserves the root and processes all
children recursively. Since all children are leafs, we know from our base case
that UnlearnSPN yields the same result as retraining. In conclusion,
UnlearnSPN($\Phi$, $x$) = LearnSPN($X^{\prime}$), which implies
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$.

Case SplitUninformativeVariables: In case of splitting uninformative
variables, the SPN will consist of a product node as a root, where all but one
child are leaf nodes. The non-leaf sub-SPN $\Psi$ is arbitrary. UnlearnSPN
preserves the product root node. We know that if a variable is uninformative
in $\Phi$ it will still be uninformative after removing $x$. Therefore,
UnlearnSPN preserves all leafs and updates them according to the base case.
For the non-leaf sub-SPN we further distinguish two cases.

First, all informative variables stay informative. This means that the
variable split is the same for LearnSPN($X$) and LearnSPN($X^{\prime}$).
UnlearnSPN($\Phi$, $x$) will preserve the split as well. In this case
UnlearnSPN processes the non-leaf sub-SPN $\Psi$ recursively. By the induction
hypothesis, we assume that UnlearnSPN($\Psi$, $x$) =
LearnSPN($X^{\prime}_{\Psi}$), where $X^{\prime}_{\Psi}$ corresponds to the
remaining training data $X^{\prime}$ in the remaining scope of the sub-SPN
$\Psi$.

Second, we consider the case where some informative variables become
uninformative. This adds $m<|scope(\Psi)|-1$ new leaf nodes to the root. The
corresponding distributions are estimated from scratch. For the remaining
variables UnlearnSPN calls LearnSPN. In conclusion, for both cases (split
changes / is preserved), we can conclude that
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$
holds.

Case SplitData: First, UnlearnSPN removes $x$ from the clustering. This is
either done via recomputing the clustering with the same initialization or by
updating it if possible.

If removing $x$ preserves the clusters, UnlearnSPN only adapts the weights of
the edges and processes the sub-SPNs recursively. Since $x$ will only be part
of one cluster, UnlearnSPN is only called for the sub-SPN $\Psi$ corresponding
to the subset containing $x$. By the induction hypothesis, we assume that
$P(\textsc{UnlearnSPN}(\Psi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime}_{\Psi})\in\mathcal{T})$,
where $X^{\prime}_{\Psi}$ corresponds to the remaining data used for training
$\Psi$.

If removing $x$ changes the clusters, UnlearnSPN retrains the SPN from scratch
on $X^{\prime}$ starting with a split data operation. In conclusion,
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$
in all cases.

Case Split Variables: Let $V_{1},...,V_{k}$ be the variable partition and
$\Phi_{1},...,\Phi_{k}$ the corresponding sub-SPNs. First, UnlearnSPN
recomputes or updates the independencies if possible. If removing $x$ has no
influence on the matrix, then UnlearnSPN processes all sub-SPNs recursively.
By the induction hypothesis, we assume that UnlearnSPN($\Phi_{i}$, $x$) =
LearnSPN($X^{\prime}_{i}$), for all $i\in[1,k]$, where $X^{\prime}_{i}$
corresponds to the remaining data in the scope of $\Phi_{i}$. If removing $x$
changes the adjacency matrix, then UnlearnSPN retrains the SPN from scratch
starting with the split variable operation. In all cases
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$.

Conclusion: If $rev(op)=op$, then
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$.

The proof via structural induction for $op\neq rev(op)=op^{\prime}$, together
with Proposition 1 conclude that
$P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$
holds in general. ∎

From Theorem 2 we can directly conclude Corollary 1, which states a strong
privacy guarantee of UnlearnSPN in the sense of $\epsilon$-certified removal.

######  Corollary 1.

Let $X$ be a dataset, $x\in X$ a data point, $X^{\prime}=X\setminus\\{x\\}$,
and $\Phi=\textsc{LearnSPN}(X)$. UnlearnSPN$(\Phi,x)$ is 0-CR for
$\mathcal{A}=$ LearnSPN.

###### Proof of Corollary 1.

$\displaystyle~{}P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})=P(\textsc{LearnSPN}(X^{\prime})\in\mathcal{T})$
$\displaystyle\Leftrightarrow$
$\displaystyle~{}\frac{P(\textsc{UnlearnSPN}(\Phi,x)\in\mathcal{T})}{P(\textsc{LearnSPN}(X\setminus\\{x\\})\in\mathcal{T})}=1=e^{0}$
$\displaystyle\Leftrightarrow$
$\displaystyle~{}e^{0}\leq\frac{P(\textsc{UnlearnSPN}(\textsc{LearnSPN}(X),x)\in\mathcal{T})}{P(\textsc{LearnSPN}(X\setminus\\{x\\})\in\mathcal{T})}\leq
e^{0}$

∎

##  5 Experiments

In the following, we will empirically show that UnlearnSPN provides a better
runtime than retraining an SPN from scratch and that the runtime of the here
presented modified version of LearnSPN does not significantly differ from that
of the original LearnSPN. All experiments were performed on a MacBook Pro with
a 2.3 GHz Quad-Core Intel Core i7 processor and 32GB RAM. The implementation
of our modified training algorithm, as well as UnlearnSPN, are based on SPFlow
[13] and are publicly available on
GitHub111https://github.com/ROYALBEFF/UnlearnSPN.

For the former, we train an initial SPN on a random subset of 1000 data points
of the training data and consecutively remove 100 data points at random
afterward. Then, we compare the accumulated runtime of the 100 removal
operations with that of retraining the model 100 times on the corresponding
remaining data. We repeat this experiment 10 times and consider the mean as
well as the standard deviation of the runtimes for comparison. The datasets
used were Abalone, Adult, MSNBC, Plants, and Wine from the UCI Machine
Learning Repository [14]. A short summary of the variables in each dataset is
given in Table 1. All numerical variables were considered Gaussian.

Table 1: Number and types of variables in each dataset. Dataset | # Categorical | # Gaussian | # Total
---|---|---|---
Abalone | 1 | 8 | 9
Adult | 9 | 6 | 15
MSNBC | 17 | 0 | 17
Plants | 71 | 0 | 71
Wine | 1 | 13 | 14

Variables were split by computing the randomized dependency coefficient (RDC)
[15] for each pair of variables, which gives us a symmetric coefficient
matrix. Using a dependency threshold, we obtained an adjacency matrix. The
connected components induced by this matrix form the variable split. Since RDC
does not allow certified removal, we store the adjacency matrix and the random
projections for each SplitVariables node, recompute the adjacency matrix and
check if any of the connected components changed. If this is not the case,
UnlearnSPN updates the state of the corresponding node. Otherwise, the sub-SPN
must be retrained.

The data splits were computed using Q-$k$-Means [8] with $k=2$, which is a
modified version of $k$-Means that allows certified data removal. The main
idea behind Q-$k$-Means is that quantizing the cluster centroids reduces the
impact each data point can have. Therefore, multiple data points can be
removed without affecting the resulting centroids.

Table 2: Runtime comparison of removing 100 random data points via retraining and UnlearnSPN. Dataset | Retraining [s] | Unlearning [s]
---|---|---
Abalone | 152.450 ± 10.217 | 111.540 ± 5.725
Adult | 529.350 ± 64.865 | 466.950 ± 45.061
MSNBC | 71.898 ± 19.101 | 55.636 ± 8.381
Plants | 6880.890 ± 605.628 | 6159.860 ± 609.329
Wine | 0.249 ± 0.012 | 0.105 ± 0.003

Table 2 contains the runtimes of unlearning and retraining for 100 random data
points. We observe that in all of our experiments, removing data via
unlearning is faster than retraining the model on the remaining data. The time
improvements vary between approximately 58% for the Wine dataset and 10% for
the Plants dataset. We also see that the time needed for unlearning varies
less than for retraining.

Table 3: Comparing the training duration of the original LearnSPN and the modified, removal enabled LearnSPN. Dataset | Original LearnSPN [s] | Modified LearnSPN [s]
---|---|---
Abalone | 1.463 ± 0.138 | 2.378 ± 0.247
Adult | 4.7838 ± 0.783 | 6.238 ± 0.881
MSNBC | 0.995 ± 0.171 | 1.578 ± 0.547
Plants | 68.107 ± 7.927 | 71.312 ± 10.349
Wine | 0.311 ± 0.013 | 0.0054 ± 0.001

For the runtime comparison of the original LearnSPN and our removal enabled
version, we use the same datasets as above and perform both training
algorithms 10 times on all data sets. The original LearnSPN algorithm uses RDC
for splitting variables and $k$-Means with $k=2$ for splitting data points.
Note that the SPFlow implementation of LearnSPN performs pruning by default.
We explicitly omit the pruning step for a fairer comparison. Table 3 contains
the runtimes of training an SPN with the original LearnSPN implementation in
SPflow, and our modified, removal enabled version. In Table 3 we state our
results of the runtime comparison, which show that the time needed to train an
SPN using the removal enabled version of LearnSPN is only slightly longer than
with the original LearnSPN algorithm. Other than the retraining and
unlearning, the initial training is usually only performed once. Thus, the
increase of the initial training duration amortizes after only a few data
removals.

##  6 Conclusion and Future Work

We presented the first unlearning algorithm for SPNs, namely UnlearnSPN, which
allows deleting the influence of specific data points perfectly on demand.
With this, SPNs match the necessary requirements to comply with legal
regulations such as the right to be forgotten (GDPR). For this, we introduced
a modified version of LearnSPN, which yields removal enabled SPNs. The major
differences to the standard LearnSPN algorithm are the additional state that
is stored for each node in the SPN and the fact that the SPN must not be
pruned afterward. Our experiments showed that our modified version of LearnSPN
slightly increases the training duration. However, the additional time needed
in training is quickly amortized by the speed up UnlearnSPN provides over
retraining the SPN from scratch when removing data points. Note that even
though we only argued about removing single data points, this approach can
easily be generalized to sets of data points and therefore allows batch
removal. Furthermore, the approach can also be adapted so that data points can
be removed and added to the SPN. This is especially interesting in online
scenarios.

There are still some open questions that could be addressed in future work.
Here, we assumed the leaf nodes to represent univariate distributions.
However, leaf nodes are generally not restricted to univariate distribution
but could also represent multivariate distribution or be replaced by Chow-Liu
trees. UnlearnSPN could also be adapted to handle other kinds of leaf nodes
and thus be applicable in even more scenarios.

Another point that could be addressed in future work is that UnlearnSPN only
works on unpruned SPNs, which implies larger models and possibly slower
inference. UnlearnSPN might be able to work on pruned SPNs as well if we find
a way to combine states during pruning such that all information necessary for
removal is preserved and applicable.

Finally, it would be interesting to compare unlearning to full differential
private training since unlearning can be seen as a trade-off between
retraining and differential privacy. However, to our best knowledge, there is
no differential private training algorithm for SPNs yet.

## References

  * [1] L. Bourtoule, V. Chandrasekaran, C. A. Choquette-Choo, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot, “Machine unlearning,” in _2021 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2021, pp. 141–159.
  * [2] A. Golatkar, A. Achille, and S. Soatto, “Eternal sunshine of the spotless net: Selective forgetting in deep networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 9304–9312.
  * [3] A. Golatkar, A. Achille, A. Ravichandran, M. Polito, and S. Soatto, “Mixed-privacy forgetting in deep networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 792–801.
  * [4] L. Graves, V. Nagisetty, and V. Ganesh, “Amnesiac machine learning,” _arXiv preprint arXiv:2010.10981_ , 2020.
  * [5] C. Guo, T. Goldstein, A. Hannun, and L. Van Der Maaten, “Certified data removal from machine learning models,” _arXiv preprint arXiv:1911.03030_ , 2019.
  * [6] N. Aldaghri, H. Mahdavifar, and A. Beirami, “Coded machine unlearning,” _IEEE Access_ , vol. 9, pp. 88 137–88 150, 2021.
  * [7] J. Brophy and D. Lowd, “Machine unlearning for random forests,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 1092–1104.
  * [8] A. Ginart, M. Guan, G. Valiant, and J. Y. Zou, “Making ai forget you: Data deletion in machine learning,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [9] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy.” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3-4, pp. 211–407, 2014.
  * [10] A. Treiber, A. Molina, C. Weinert, T. Schneider, and K. Kersting, “Cryptospn: Privacy-preserving sum-product network inference,” _arXiv preprint arXiv:2002.00801_ , 2020.
  * [11] H. Poon and P. Domingos, “Sum-product networks: A new deep architecture,” in _2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops)_. IEEE, 2011, pp. 689–690.
  * [12] R. Gens and D. Pedro, “Learning the structure of sum-product networks,” in _International conference on machine learning_. PMLR, 2013, pp. 873–880.
  * [13] A. Molina, A. Vergari, K. Stelzner, R. Peharz, P. Subramani, N. D. Mauro, P. Poupart, and K. Kersting, “Spflow: An easy and extensible library for deep probabilistic learning using sum-product networks,” 2019.
  * [14] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * [15] D. Lopez-Paz, P. Hennig, and B. Schölkopf, “The randomized dependence coefficient,” _Advances in neural information processing systems_ , vol. 26, 2013.