# Heterogeneous Federated Knowledge Graph Embedding Learning and Unlearning

Xiangrong Zhu  State Key Laboratory for Novel Software TechnologyNanjing
University China<EMAIL_ADDRESS>,  Guangyao Li  State Key Laboratory for
Novel Software TechnologyNanjing University China<EMAIL_ADDRESS>and  Wei
Hu  State Key Laboratory for Novel Software TechnologyNational Institute of
Healthcare
Data ScienceNanjing University China<EMAIL_ADDRESS>
(2023)

###### Abstract.

Federated Learning (FL) recently emerges as a paradigm to train a global
machine learning model across distributed clients without sharing raw data.
Knowledge Graph (KG) embedding represents KGs in a continuous vector space,
serving as the backbone of many knowledge-driven applications. As a promising
combination, federated KG embedding can fully take advantage of knowledge
learned from different clients while preserving the privacy of local data.
However, realistic problems such as data heterogeneity and knowledge
forgetting still remain to be concerned. In this paper, we propose FedLU, a
novel FL framework for heterogeneous KG embedding learning and unlearning. To
cope with the drift between local optimization and global convergence caused
by data heterogeneity, we propose mutual knowledge distillation to transfer
local knowledge to global, and absorb global knowledge back. Moreover, we
present an unlearning method based on cognitive neuroscience, which combines
retroactive interference and passive decay to erase specific knowledge from
local clients and propagate to the global model by reusing knowledge
distillation. We construct new datasets for assessing realistic performance of
the state-of-the-arts. Extensive experiments show that FedLU achieves superior
results in both link prediction and knowledge forgetting.

federated learning, knowledge graph embedding, unlearning

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
ACM Web Conference 2023; April 30-May 4, 2023; Austin, TX, USA††booktitle:
Proceedings of the ACM Web Conference 2023 (WWW ’23), April 30-May 4, 2023,
Austin, TX, USA††price: 15.00††doi: 10.1145/3543507.3583305††isbn:
978-1-4503-9416-1/23/04††ccs: Computing methodologies Neural networks††ccs:
Computing methodologies Semantic networks

##  1\. Introduction

_Federated Learning_ (FL) (Yang et al., 2019; Li et al., 2021b) is a new
machine learning paradigm, where multiple devices with local data samples work
together to train a global machine learning model. FL differs significantly
from classic centralized machine learning scenarios in that it does not need
all local data to be uploaded to a central server. It also stands in contrast
to traditional distributed methods which often assume that local data samples
are identically distributed. _Knowledge Graph_ (KG) is a structured knowledge
base that describes real-world entities and their relations in the form of
triplets. Recent advances in representation learning techniques hasten the
advent of _KG embedding_ (Ji et al., 2021; Wang et al., 2017), which projects
entities and relations into a unified semantic space to mitigate the symbolic
heterogeneity and support various knowledge-driven applications. _Federated KG
embedding learning_ (Chen et al., 2021b, 2022; Meng et al., 2021; Peng et al.,
2021; Zhang et al., 2022) is an emerging field that leverages FL and multi-
source KGs for collaborative KG embedding.

Figure 1. A motivating example, where different KGs (e.g., DBpedia,
MusicBrainz and IMDb) provide complementary knowledge about the NBA all-star
Damian Lillard.

Example 1. Let us see the example in Figure 1. The NBA all-star, Damian
Lillard, has made great achievements in basketball, sport business, film and
music, documented in distributed KGs like DBpedia, IMDb and MusicBrainz. Based
on FL, we can learn the above knowledge jointly and securely to better model
the overall image of Damian Lillard. However, federated KG representation
learning needs to address realistic challenges like data heterogeneity and
knowledge forgetting.

Challenge 1: Data heterogeneity. A major difference between FL and traditional
distributed learning is that the data feature and distribution in FL are
unknown and uncontrollable, while traditional distributed learning assumes
that local data samples are identically distributed. KGs combine the
characteristics of relational databases and graph data, so their heterogeneity
is particularly significant. On one hand, the schemata of different KGs
describe various domains with uneven abstraction levels. As illustrated in
Figure 1, the entities and relations instantiating these KGs also do not fully
overlap. On the other hand, the graph features of different KGs such as degree
distribution and clustering coefficient are inconsistent. Local data with
strong heterogeneity make local KG embedding models difficult to be
aggregated, leading to the drift between local optimization and global
convergence, and therefore reduce the overall accuracy of federated KG
embedding learning. For example, as a basketball player, Damian Lillard’s
status may make him more likely to be associated with the sport drama “The Way
Back”, while suppress the prediction that he is a voice actor in the comedy
animation “We Bare Bears”.

Challenge 2: Knowledge forgetting. As the symbolic abstraction of real-world
domains, local KGs on clients can be outdated or erroneous, leading to the
global model change over time. For example, Damian Lillard and CJ McCollum are
no longer teammates in the Portland Trail Blazers, as CJ McCollum was traded
to the New Orleans Pelicans. Another need for knowledge forgetting is privacy
protection in healthcare, finance, insurance, etc. For instance, the EU
General Data Protection Regulation (GDPR) guarantees users’ right to be
forgotten,111https://gdpr-info.eu/art-17-gdpr/ i.e., the data subject shall
have the right to obtain from the controller the erasure of personal data
concerning him or her without undue delay and the controller shall have the
obligation to erase personal data without undue delay. It is easy to remove
triplets in a KG, but hard to eliminate their impact on the trained embedding
model. Moreover, re-training the model again on the remaining data is time-
consuming and computationally expensive. The difficulty of making the KG
embedding model forget specific triplets lies in that it is hard to quantify
and recover the influence of a triplet on the model due to the correlation
with other triplets and the randomness of training. Given that local data are
not visible to the global view, how to propagate the unlearning results to the
global model is quite challenging.

Current approaches. Existing work mainly focuses on the migration and
customization from FL to KG embedding, which can be divided into client-server
(Chen et al., 2021b; Zhang et al., 2022; Meng et al., 2021; Chen et al., 2022)
and peer-to-peer (Peng et al., 2021) based on the communication architecture
of nodes in the whole system. The client-server architecture typically
consists of one server and multiple clients with their own local KGs. The
server initializes the embeddings of entities and relations, distributes the
embeddings to clients for training, and aggregates the clients’ locally-
trained embedding models after each round of local training. In contrast, the
peer-to-peer architecture allows clients to exchange embeddings and learn from
each other in a generative adversarial manner. As far as FL is concerned, the
client-server architecture has higher communication efficiency and can
eventually produce a common and effective global model for general use.
However, it is difficult for existing federated KG embedding learning methods
to deal with non-IID data with strong heterogeneity. See Section 5.1 for an
analysis of the datasets used in existing work. Furthermore, to our best
knowledge, we have not seen any exploration in KG embedding unlearning, let
alone making the global model forget specific triplets from clients under the
FL setting.

Our framework. In this paper, we consider the realistic challenges in
federated KG embedding, and propose a novel FL framework for heterogeneous KG
embedding learning and unlearning, dubbed FedLU. To address the data
heterogeneity of multi-source KGs, we propose mutual knowledge distillation to
transfer local knowledge to global, and absorb global knowledge back.
Furthermore, to achieve knowledge forgetting, we present an unlearning method
to erase specific knowledge from local embeddings and propagate to the global
embedding by reusing knowledge distillation. To validate the effectiveness of
the proposed framework, we construct three new datasets based on FB15k-237 and
carry out extensive experiments with varied number of clients.

The main contributions of this paper are summarized as follows:

  * •

We propose a FL framework for KG embedding learning. In particular, we design
a mutual knowledge distillation method to cope with the drift between local
optimization and global convergence caused by data heterogeneity. (See Section
4.1)

  * •

Based on cognitive neuroscience, we present a novel KG embedding unlearning
method, which combines retroactive interference and passive decay to achieve
knowledge forgetting. (See Section 4.2)

  * •

We conduct extensive experiments on newly-constructed datasets with varied
number clients. Experimental results show that FedLU outperforms the state-of-
the-arts in both link prediction and knowledge forgetting. (See Section 5)

##  2\. Preliminaries

Federated learning. FL is a computing paradigm where disperse clients
collaboratively train models using multi-party datasets without data leakage.
Instead of centrally collecting data into a machine learning server or sharing
training data across parties, FL only involves an exchange of model parameters
or gradients. FedAvg (McMahan et al., 2017) is a very popular FL algorithm due
to its simplicity and effectiveness, where each client trains its local model
with private data, and the server aggregates the uploaded local models by a
weighted sum. The procedure can be denoted by $\mathbf{w}_{t+1}=\sum_{k\in
K}\frac{n_{k}}{n}\mathbf{w}^{k}_{t}$, where $\mathbf{w}_{t}$ denotes the
aggregated global model at the $t$-th iteration, and $\mathbf{w}_{t}^{k}$
denotes the optimized local model for client $k$. $\frac{n_{k}}{n}$ is the
aggregation weight considering the proportion of the dataset size for each
client. It is proved that FedAvg can converge on non-IID data under necessary
conditions (Li et al., 2020a). In the real world, the system and statistical
heterogeneity widely exists, such as device failures and data biases. In order
to alleviate such heterogeneity, FedProx (Li et al., 2020b) introduces a
proximal term to the local training process as a minor modification to FedAvg.
The local update can be denoted by
$\mathbf{w}^{k}_{t+1}=\operatorname*{arg\,min}_{\mathbf{w}}F_{k}(\mathbf{w})+\frac{\mu}{2}||\,\mathbf{w}-\mathbf{w}_{t}\,||^{2}$,
where $F_{k}(\cdot)$ is the original local objective function, and $\mu$ is a
weight to balance the two terms. MOON (Li et al., 2021a) presents a model-
level contrastive learning to solve the heterogeneity in images with deep
learning models. It adds a model-contrastive loss into local optimization to
decrease the distance between the local and global models. In addition,
researches increasingly turn to knowledge distillation (Li and Wang, 2019; Seo
et al., 2022; Wu et al., 2022) instead of direct model substitution. We refer
readers to a recent survey (Li et al., 2021b) for more progress.

KG embedding. KG embedding models embed entities and relations into a
continuous vector space while expecting to reveal the inherent semantics of
KGs. Existing work can be categorized into three groups: (i) Translational
distance models (Bordes et al., 2013; Sun et al., 2019; Zhang et al., 2020)
view a relation as a translation operation from the head entity to the tail
entity, and exploit a distance-based scoring function to measure the
plausibility of a triplet. TransE (Bordes et al., 2013) adopts vector
translation to model such an operation. Its scoring function is defined as
$\mathcal{S}_{\text{TransE}}(h,r,t)=-||\,\mathbf{h}+\mathbf{r}-\mathbf{t}\,||$,
while RotatE (Sun et al., 2019) interprets a relation as a vector rotation.
(ii) Semantic matching models (Yang et al., 2015; Trouillon et al., 2016;
Balazevic et al., 2019) match latent semantics of entities and relations in
their scoring functions. ComplEx (Trouillon et al., 2016) captures pairwise
interactions between entities and relations along the same dimension in a
complex vector space. The scoring function is defined as
$\mathcal{S}_{\text{ComplEx}}(h,r,t)=\text{Re}\big{(}\langle\mathbf{h},\mathbf{r},\mathbf{\bar{t}}\rangle\big{)}$,
where $\text{Re}(\cdot)$ denotes the real vector component.
$\langle\cdot\rangle$ denotes a generalized dot product. $\bar{\cdot}$ is the
conjugate of a complex vector. (iii) Deep models leverage deep neural networks
to dig into the underlying structures of KGs, such as convolutional neural
networks (Dettmers et al., 2018; Nguyen et al., 2018) and graph neural
networks (Schlichtkrull et al., 2018; Vashishth et al., 2020).

Machine unlearning. Different from machine learning, machine unlearning aims
to make models forget specific samples. The work in (Cao and Yang, 2015)
transforms the original machine learning algorithm into a statistical query
learning form. Therefore, unlearning can be realized by updating the
summations for queries instead of re-training from scratch. The work in
(Ginart et al., 2019) further leverages k-means clustering to make the
unlearning algorithm in (Cao and Yang, 2015) more deletion-efficient. Inspired
by ensemble learning and incremental learning, SISA (Bourtoule et al., 2021)
first splits the whole dataset into shards to train different submodels, and
then splits each shard into slices to feed into the individual submodels
sequentially while storing checkpoints. To the best of our knowledge, there is
no prior work exploring KG embedding unlearning.

##  3\. Related Work

There is only a few studies on federated KG embedding learning. To protect
data privacy and sensitivity, FedE (Chen et al., 2021b) simply adapts FedAvg
to KG embedding by sharing entity embeddings. The adaptation of delivery and
aggregation is defined as follows:

(1)
$\displaystyle\mathbf{E}_{t}^{k}=\mathbf{P}^{k}\mathbf{E}_{t},\quad\mathbf{E}_{t+1}=\Big{(}\mathbb{1}\oslash\sum_{k=1}^{K}\mathbf{v}^{k}\Big{)}\otimes\sum_{k=1}^{K}{\mathbf{P}^{k}}^{\top}\mathbf{E}_{t}^{k},$

where $\mathbf{E}_{t}$ is the global embedding at the $t$-th communication
round, $\mathbf{P}^{k}$ is the permutation matrix from the global embedding to
the local embedding in client $k$ and ${\mathbf{P}^{k}}^{\top}$ is its
transpose, $\mathbf{E}^{k}_{t}$ is the local embedding of client $k$ at this
communication round, $\mathbf{v}^{k}$ is an existence vector indicating which
entities exist in client $k$, $\mathbb{1}$ refers to an all-one vector, and
$\oslash,\otimes$ are respectively element-wise division for vectors and
element-wise multiplication with broadcasting. $\mathbf{P}^{k}$ and
$\mathbf{v}^{k}$ can be calculated by the server without sharing raw data
through techniques such as private data matching (Scannapieco et al., 2007).
FedE empirically validates that the locally-computed embeddings can achieve
better performance by aggregating with the global embedding.

FedR (Zhang et al., 2022) pays attention to the scenario where clients have
high overlapping not only in entities but also in relations. The clients in
its framework share relation embeddings globally and represent entity
embeddings based on relations locally. In this paper, we do not assume
relation overlapping.

FKGE (Peng et al., 2021) proposes a peer-to-peer federated embedding learning
framework for KGs in various domains, based on a differentially-privacy
generative adversarial model. Borrowing the idea of MUSE (Lample et al., 2018)
to align two manifolds with a translational mapping matrix, FKGE is able to
generate refined embeddings after generative adversarial training. For
communication efficiency, we do not adopt the peer-to-peer architecture.

Inspired by MOON (Li et al., 2021a), FedEC (Chen et al., 2022) uses embedding-
contrastive learning to guide the embedding optimization for addressing data
heterogeneity. It increases the similarity between local and global embeddings
by incorporating a contrastive loss into the local loss.

##  4\. The Proposed Framework

Figure 2. FedLU follows the client-server architecture, and each client
contains a learning module and an unlearning module.

We aim to train a KG embedding model based on the FL architecture composed of
a central server and a set of clients $K$. Each client $k\in K$ has a local KG
$G^{k}=\\{(h,r,t)\,|\,h,t\in E^{k},r\in R^{k}\\}$, where $E^{k},R^{k}$ denote
the entity and relation sets, respectively. Local KGs have overlapping
entities (i.e., $\forall i,\exists j\neq i,E^{i}\cap E^{j}\neq\emptyset$), and
the whole dataset is denoted by $G=\bigcup_{k\in K}G^{k}$. Furthermore, we do
not assume the overlap of relations.

At each communication round $t$, the server first samples $K_{t}\subseteq K$
to collaborate, and then distributes the corresponding local avatar
$\mathbf{P}^{k}\mathbf{E}_{t}$ of global embedding $\mathbf{E}_{t}$ to each
sampled client $k\in K_{t}$. Next, the selected client $k$ updates its local
embedding $\mathbf{E}^{k}_{t}$ assisted by $\mathbf{P}^{k}\mathbf{E}_{t}$
which is received from the server. At the end of communication round $t$, the
server receives the uploaded local avatars of the global embedding and
aggregates them into $\mathbf{E}_{t+1}$. The objective of federated KG
embedding learning is to generate a global embedding which minimizes the
average local loss:

(2) $\displaystyle\mathbf{E}=\operatorname*{arg\,min}_{\mathbf{E}}\sum_{k\in
K}\frac{|G^{k}|}{|G|}\mathcal{L}(\mathbf{P}^{k}\mathbf{E};G^{k}),$

where $\mathcal{L}(\cdot)$ is the self-adversarial negative sampling loss of
the embedding $\mathbf{P}^{k}\mathbf{E}$ on the local KG $G^{k}$.

After rounds of communication and training, the framework of FedLU gets the
best global embedding $\mathbf{E}$ and local embeddings $\mathbf{E}^{k},k\in
K$. Later, the local KG $G^{k}$ of client $k$ may have a forgetting triplet
set $G^{k}_{u}$ and its complementary triplet set $G^{k}_{c}$. To define the
goal of unlearning, the local objective is to optimize

(3)
$\displaystyle\mathbf{E}^{k-}=\operatorname*{arg\,min}_{\mathbf{E}^{k}}\Big{(}-\frac{|G^{k}_{u}|}{|G^{k}|}\mathcal{L}(\mathbf{E}^{k};G^{k}_{u})+\frac{|G^{k}_{c}|}{|G^{k}|}\mathcal{L}(\mathbf{E}^{k};G^{k}_{c})\Big{)}.$

Under the FL setting, a subset of clients $K_{u}\subseteq K$ have their own
forgetting sets $\big{\\{}G^{k}_{u}\big{\\}}_{k\in K_{u}}$ and the
complementary sets $\big{\\{}G^{k}_{c}\big{\\}}_{k\in K_{u}}$. The global
objective of federated unlearning is to obtain a global embedding minimizing
the average local loss with unlearning:

(4)

As shown in Figure 2, FedLU serves as a general federated KG embedding
learning and unlearning framework for various KG embedding models. In the
learning module of FedLU, we transfer knowledge by mutual knowledge
distillation instead of model replacement. In the unlearning module, we design
a two-step method combining retroactive interference and passive decay, which
ensures exact forgetting and performance maintenance.

###  4.1. Learning in FedLU

For FL algorithms such as FedAvg, clients accept the global model as the
initial states of local models for each round of local training, and upload
the updated model directly for global aggregation. The global model is
expected to aggregate the knowledge on each client and obtain a balanced
performance. However, FedNTD (Lee et al., 2022) observes that the global
convergence and local optimization in FL may interfere with each other, which
we call _drift_. The global model may easily lose optimization details of
local training after aggregation. Furthermore, the local model tends to forget
external knowledge contained in the initial states during training.

Existing work (Hanzely and Richtárik, 2020; Liang et al., 2019) suggests that
there should be a trade-off and separation between global and local models,
endowing the FL framework the compatibility of local optimization and global
generalization. Inspired by this, in FedLU we maintain local and global
embeddings in parallel that mutually reinforce each other but are not
identical. Besides, identical global and local embeddings may be used to infer
knowledge in a private client (Zhang et al., 2022), resulting in data leakage.
This problem is avoided by separation and communication through mutual
distillation in FedLU.

Algorithm 1 shows the federated KG embedding learning via knowledge
distillation of FedLU. In Line 1, the server first initializes the global
embedding model, and then the communication rounds of federated KG embedding
learning start. During each round $t$ (Lines 2–9), a subset of clients
$K_{t}\subseteq K$ are sampled. The server calculates and distributes
corresponding part of the global embedding to each client $k\in K_{t}$ in Line
5. Each client refines its local embedding with the global embedding and
improves the global embedding with its local embedding through mutual
knowledge distillation in parallel in Lines 6–7. In Line 9, the server
aggregates global embeddings without forcing changes to local embeddings,
which maintains the coherence of local training and avoids the drift of local
optimization.

Input: communication rounds $T$, server, client set $K$, mapping matrix
$\mathbf{P}$, existence vector $\mathbf{v}$

Output: global embedding $\mathbf{E}_{T}$, local embeddings
$\\{\mathbf{E}_{T}^{k}\\}_{k\in K}$

1 Server initializes $\mathbf{E}_{0}$;

2 for  _$t=0,\dots,T-1$_ do

3 Sample a client subset $K_{t}\subseteq K$;

4 forall  _$k\in K_{t}$_ do // run in parallel

5 Server sends $\mathbf{E}^{k}_{t}=\mathbf{P}^{k}\mathbf{E}_{t}$ to client
$k$;

6
$\mathbf{E}^{k,\text{local}}_{t}=\operatorname*{arg\,min}_{\mathbf{E}^{k}}\mathcal{L}^{\text{local}}(\mathbf{E}^{k};\mathbf{E}^{k}_{t},G^{k})$;

7
$\mathbf{E}^{k,\text{global}}_{t}=\operatorname*{arg\,min}_{\mathbf{E}^{k}}\mathcal{L}^{\text{global}}(\mathbf{E}^{k};\mathbf{E}^{k,\text{local}}_{t},G^{k})$;

8 Client $k$ sends $\mathbf{E}^{k,\text{global}}_{t}$ to server;

9

10
$\mathbf{E}_{t+1}=\big{(}\mathbb{1}\oslash\sum_{k=1}^{K_{t}}\mathbf{v}^{k}\big{)}\otimes\sum_{k\in
K_{t}}{\mathbf{P}^{k}}^{\top}\mathbf{E}^{k,\text{global}}_{t}$;

11

Algorithm 1 Federated learning via knowledge distillation

Let us first dive into how to refine local embeddings with the global
embedding by knowledge distillation in FedLU. Given a triplet $(h,r,t)$, we
compute its local score and global score by Eqs. (5) and (6), respectively:

(5) $\displaystyle\mathcal{S}^{\text{local}}_{(h,r,t)}$
$\displaystyle=\mathcal{S}(h,r,t;\mathbf{E}^{\text{local}},\mathbf{R}^{\text{local}}),$
(6) $\displaystyle\mathcal{S}^{\text{global}}_{(h,r,t)}$
$\displaystyle=\mathcal{S}(h,r,t;\mathbf{E}^{\text{global}},\mathbf{R}^{\text{local}}),$

where $\mathcal{S}(\cdot)$ is the scoring function referred in Section 2.
$\mathbf{E}^{\text{local}}$ and $\mathbf{E}^{\text{global}}$ are entity
embeddings in the local and global models, respectively, and
$\mathbf{R}^{\text{local}}$ is the relation embedding in the local model. To
train each triplet $(h_{i},r_{i},t_{i})\in G^{k}$, we generate its negative
sample set $N(h_{i},r_{i},t_{i})=\\{(h_{i},r_{i},t_{i,j})\,|\,j=1,\dots,n\\}$
with size $n$, s.t. $N(h_{i},r_{i},t_{i})\cap G^{k}=\emptyset$. We calculate
the contrastive prediction loss of $(h_{i},r_{i},t_{i})$ as follows:

(7)

where $\sigma(\cdot)$ is the sigmoid activation function.

To avoid the inconsistency in the optimization direction of local and global
embeddings, knowledge distillation is conducted along with sample prediction.
The score of a KG embedding model on a triplet characterizes the probability
of being predicted as positive. So, we transfer knowledge by distilling the
distribution of local and global scores on samples and their negative sets.
For a triplet $(h_{i},r_{i},t_{i})$, we compute its distillation loss for the
local embedding:

(8)
$\displaystyle\mathcal{L}^{\text{distill}}_{(h_{i},r_{i},t_{i})}=\text{KL}\Big{(}\mathcal{P}^{\text{local}}_{(h_{i},r_{i},\cdot)},\mathcal{P}^{\text{global}}_{(h_{i},r_{i},\cdot)}\Big{)},$

where $\text{KL}(\cdot)$ is the Kullback-Leiber distillation function.
$\mathcal{P}^{\text{local}}_{(h_{i},r_{i},\cdot)}$ is the local score
distribution of sample $(h_{i},r_{i},t_{i})$ generated by combining
$\mathcal{P}^{\text{local}}_{(h_{i},r_{i},t_{i})}$ and
$\mathcal{P}^{\text{local}}_{(h_{i},r_{i},t_{i,j})}$, which are computed as
follows:

(9)
$\displaystyle\mathcal{P}^{\text{local}}_{(h_{i},r_{i},t_{i})}=\frac{\exp\big{(}s^{\text{local}}_{(h_{i},r_{i},t_{i})}\big{)}}{\sum_{(h,r,t)\in
N(h_{i},r_{i},t_{i})\cup\\{(h_{i},r_{i},t_{i})\\}}\exp\big{(}s^{\text{local}}_{(h,r,t)}\big{)}},$
(10)
$\displaystyle\mathcal{P}^{\text{local}}_{(h_{i},r_{i},t_{i,j})}=\frac{\exp\big{(}s^{\text{local}}_{(h_{i},r_{i},t_{i,j})}\big{)}}{\sum_{(h,r,t)\in
N(h_{i},r_{i},t_{i})\cup\\{(h_{i},r_{i},t_{i})\\}}\exp\big{(}s^{\text{local}}_{(h,r,t)}\big{)}},$

and $\mathcal{P}^{\text{global}}_{(h_{i},r_{i},\cdot)}$ is the global score
distribution of $(h_{i},r_{i},t_{i})$ generated by combining
$\mathcal{P}^{\text{global}}_{(h_{i},r_{i},t_{i})}$ and
$\mathcal{P}^{\text{global}}_{(h_{i},r_{i},t_{i,j})}$, which can be calculated
in a similar way.

Finally, the local model of client $k$ is equipped with the two jointly
optimized losses as follows:

(11) $\displaystyle\mathcal{L}^{\text{local}}=\sum_{(h_{i},r_{i},t_{i})\in
G^{k}}\Big{(}\mathcal{L}^{\text{predict}}_{(h_{i},r_{i},t_{i})}+\mu_{\text{distill}}\,\mathcal{L}^{\text{distill}}_{(h_{i},r_{i},t_{i})}\Big{)},$

where $\mu_{\text{distill}}$ is the parameter to adjust the degree of
distillation.

The joint loss $\mathcal{L}^{\text{global}}$ to optimize global embedding
$\mathbf{E}^{\text{global}}$ can be computed similarly.

Complexity analysis. Given total communication round $T$, client number $K$,
average entity number $N^{\prime}$, total entity number $N$, total relation
number $M$, triple number $P$ and hidden dimension $H$, FedLU’s parameter
complexity is $(KN^{\prime}+N+M)H$, computation complexity is
$\mathcal{O}(PHT)$, and total communication cost is $2KN^{\prime}HT$.

###  4.2. Unlearning in FedLU

To solve the difficulty in federated KG embedding unlearning, we resort to the
forgetting theories in cognitive neuroscience. There are two major theories
explaining for forgetting of cognition, namely interference and decay. The
interference theory (Wixted, 2021) posits that forgetting occurs when memories
compete and interfere with others. The decay theory (Hardt et al., 2013)
believes that memory traces fade and disappear, and eventually lost if not
retrieved and rehearsed. We propose a two-step unlearning method for federated
KG embedding. Inspired by the interference theory, FedLU first conducts a
retroactive interference step with hard and soft confusions. Then, according
to the decay theory, FedLU performs a passive decay step, which can recover
the performance loss caused by interference while suppressing the activation
of the forgotten knowledge.

For client $k$ to perform unlearning with its local KG $G^{k}$, $G^{k}$ is
split into the forgetting set $G^{k}_{u}$ and the retaining set $G^{k}_{c}$.
We first introduce the retroactive interference step conducted to the local
embedding. To unlearn each triplet $(h_{i},r_{i},t_{i})\in G^{k}_{u}$, we have
its negative sample set
$N(h_{i},r_{i},t_{i})=\\{(h_{i},r_{i},t_{i,j})\,|\,j=1,\dots,n\\}$ with size
$n$, s.t. $N(h_{i},r_{i},t_{i})\cap G^{k}=\emptyset$. We first compute the
hard confusion loss to optimize the local embedding by treating
$(h_{i},r_{i},t_{i})$ as negative:

(12)

Unfortunately, if we blindly optimize the forgetting sets as negative, the
embeddings are likely to be polluted. In fact, unlearning may leave trace of
the forgetting set and thus results in privacy risks such as membership
inference attacks (Chen et al., 2021a). So, we design soft confusion, which
reflects the distance between scores of the triplet in the forgetting set and
its negative samples. By minimizing the soft confusion, the scores of the
triplet and negatives are forced closer, which can help not only forgetting
the triplet, but also preventing the overfitting of unlearning. The soft
confusion loss for the triplet $(h_{i},r_{i},t_{i})$ is calculated as follows:

(13)
$\displaystyle\mathcal{L}^{\text{soft}}_{(h_{i},r_{i},t_{i})}=\sum_{(h,r,t)\in
N(h_{i},r_{i},t_{i})}\frac{1}{n}\,\Big{|}\Big{|}\,\mathcal{S}^{\text{local}}_{(h,r,t)}-\mathcal{S}^{\text{local}}_{(h_{i},r_{i},t_{i})}\,\Big{|}\Big{|}_{L2}.$

To perform the retroactive interference while keeping the relevance between
local and global embeddings, we calculate the total interference loss
combining the KL divergence loss in Eq. (8) as

(14)

The interference loss of the global embedding is calculated similarly, by
changing the local scores to the global scores and reversing the distillation.

After the retroactive interference step, memories of the global and local
embeddings on the forgetting set are erased. However, a significant decrease
in model performance can happen. On one hand, the model optimization in the
retroactive interference is limited to specific triplets to forget, which
slightly destroys the generalization of the embedding model. On the other
hand, the unlearning of a specific triplet would affect its associated
triplets. So, we perform a passive decay step afterwards by mutual knowledge
distillation with $G^{k}_{c}$ as input. $\mathbf{E}^{k,global}$ and
$\mathbf{E}^{k,local}$ are optimized alternately in batches as the teacher
model to each other. Learning on the retaining set can recover the
generalization of the model. Mutual distillation suppresses the activation of
the forgetting triplets.

##  5\. Experiments and Results

We implemented our framework, FedLU, on a server with four Intel Xeon Gold
6326 CPUs, 512GB memory and four NVIDIA RTX A6000 GPUs. In this section, we
first introduce our newly-constructed datasets for federated KG embedding.
Then, we carry out experiments to evaluate FedLU on federated KG embedding
learning and unlearning. The datasets and source code are
online.222https://doi.org/10.5281/zenodo.7601676

###  5.1. Clustering-based Dataset Construction

To evaluate the effectiveness of FedLU, we select the benchmark KG embedding
dataset FB15k-237 as the original dataset. Following the experiment setting of
FedE (Chen et al., 2021b), we averagely partition relations and distribute
triplets into three, five or ten clients accordingly, forming three datasets
called FB15k-237-R3, R5 and R10. These datasets satisfy the non-IID condition
with no overlapping relations. However, they do not conform to the entity
distribution and graph structure in real-world federation, because relations
and entities on each client may be unrelated.

In this paper, we propose a new dataset construction algorithm, which first
partitions relations by clustering and then distributes triplets into clients.
This generates more realistic datasets for federated KG embedding. Due to the
space limitation, we present the algorithm in Appendix A. In line with random
partitioning, we name the new heterogeneous datasets FB15k-237-C3, C5 and C10.

Figure 3. Comparison of degree distributions and clustering coefficients
between FB15k-237-C3 and FB15k-237-R3.

We compare the two types of datasets constructed with random partition and
clustering-based partition. Figure 3 shows the comparison results of
FB15k-237-C3 and FB15k-237-R3, and those between FB15k-237-C5/C10 and
FB15k-237-R5/R10 are supplemented in Appendix B. We can see that FB15k-237-C3
exhibits more differences in the relation, entity and triplet numbers. The
average degrees and clustering coefficients of local datasets in FB15k-237-C3
are larger and more varying than those in FB15k-237-R3. Furthermore, the
numbers of overlapping entities of FB15k-237-C3 and R3 are 1,447 and 11,067,
respectively. This shows two key properties of our clustering-based datasets:
(i) the local data distribution of each client is smooth, and the
agglomeration is strong; and (ii) the data among clients are highly
heterogeneous.

###  5.2. Experiments on Federated Learning

Table 1. Average link prediction results on FB15k-237-C3/C5/C10 Methods | FB15k-237-C3 | FB15k-237-C5 | FB15k-237-C10
---|---|---|---
Hits@1 | Hits@3 | Hits@10 | MRR | Hits@1 | Hits@3 | Hits@10 | MRR | Hits@1 | Hits@3 | Hits@10 | MRR
TransE | Independent | 19.48 | 37.57 | 53.91 | 31.44 | 19.77 | 39.77 | 56.28 | 32.60 | 18.68 | 38.56 | 55.66 | 31.52
Centralized | 20.40 | 38.79 | 56.14 | 32.65 | 20.53 | 38.98 | 56.53 | 32.86 | 20.17 | 38.57 | 56.29 | 32.49
FedE | 20.25 | 39.19 | 56.18 | 32.66 | 20.66 | 39.78 | 57.12 | 33.23 | 19.86 | 38.15 | 55.82 | 32.10
FedProx | 20.20 | 38.76 | 55.91 | 32.50 | 21.02 | 39.99 | 57.36 | 33.57 | 20.04 | 38.62 | 56.17 | 32.43
FedEC | 20.65 | 39.36 | 56.44 | 32.99 | 21.11 | 39.90 | 57.42 | 33.54 | 20.05 | 38.67 | 56.27 | 32.42
FedLU (local) | 21.27 | 40.21 | 57.53 | 33.71 | 21.89 | 40.58 | 58.19 | 34.32 | 21.05 | 39.66 | 57.44 | 33.44
FedLU (global) | 20.94 | 39.71 | 56.89 | 33.30 | 21.38 | 40.58 | 57.96 | 33.98 | 20.53 | 39.21 | 56.82 | 32.95
ComplEx | Independent | 23.85 | 39.10 | 54.40 | 34.21 | 22.90 | 37.47 | 52.21 | 32.87 | 23.52 | 39.20 | 54.46 | 34.05
Centralized | 23.95 | 40.51 | 56.45 | 35.02 | 24.47 | 40.96 | 57.22 | 35.57 | 24.73 | 40.70 | 56.69 | 35.52
FedE | 20.88 | 36.22 | 52.31 | 31.45 | 19.82 | 35.32 | 51.65 | 30.49 | 19.52 | 34.79 | 50.61 | 30.02
FedProx | 22.67 | 41.04 | 57.82 | 34.71 | 22.75 | 38.54 | 54.88 | 33.57 | 20.73 | 38.72 | 55.70 | 32.66
FedEC | 22.44 | 40.97 | 57.91 | 34.58 | 19.63 | 37.06 | 54.09 | 31.30 | 20.59 | 38.36 | 55.65 | 32.53
FedLU (local) | 25.38 | 43.37 | 59.46 | 37.10 | 24.05 | 41.74 | 58.11 | 35.66 | 25.14 | 42.01 | 57.92 | 36.33
FedLU (global) | 23.58 | 41.50 | 57.94 | 35.37 | 22.33 | 39.95 | 56.81 | 34.07 | 22.12 | 38.92 | 55.40 | 33.45
RotatE | Independent | 24.31 | 43.13 | 59.55 | 36.47 | 26.43 | 43.36 | 59.45 | 37.64 | 23.94 | 41.80 | 57.95 | 35.67
Centralized | 25.68 | 44.55 | 61.55 | 37.94 | 26.23 | 45.05 | 62.05 | 38.48 | 25.29 | 44.39 | 61.64 | 37.76
FedE | 21.23 | 39.81 | 56.71 | 33.46 | 21.94 | 40.70 | 57.62 | 34.24 | 20.54 | 38.96 | 56.41 | 32.82
FedProx | 26.07 | 45.01 | 61.71 | 38.33 | 26.92 | 45.75 | 62.49 | 39.14 | 25.75 | 44.52 | 61.53 | 37.99
FedEC | 26.13 | 45.20 | 61.76 | 38.38 | 26.50 | 45.12 | 61.82 | 38.67 | 25.53 | 44.49 | 61.33 | 37.86
FedLU (local) | 26.80 | 45.50 | 62.13 | 38.92 | 27.52 | 45.56 | 62.21 | 39.34 | 26.01 | 44.83 | 61.63 | 38.22
FedLU (global) | 26.81 | 45.56 | 61.93 | 38.90 | 27.08 | 45.57 | 62.24 | 39.13 | 25.71 | 44.83 | 61.32 | 38.00
The best and second best scores are marked in bold and with underline,
respectively.
Table 2. Average unlearning results on different sets of FB15K-237-C3 with the local and global models Hits@1 | Raw local | Re-trained local | Unlearned local | Raw global | Re-trained global | Unlearned global
---|---|---|---|---|---|---
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 38.86 | 21.27 | 21.10 | 20.86 | 13.23 | 21.04 | 36.83 | 20.88 | 20.22 | 19.94 | 15.02 | 20.95
ComplEx | 59.16 | 25.38 | 17.60 | 16.70 |  6.26 | 23.49 | 54.05 | 24.13 | 25.63 | 23.98 |  5.72 | 23.03
RotatE | 64.54 | 26.80 | 25.17 | 25.87 | 19.65 | 26.66 | 62.99 | 26.86 | 26.46 | 25.78 | 22.73 | 26.24
MRR | Raw local | Re-trained local | Unlearned local | Raw global | Re-trained global | Unlearned global
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 52.54 | 33.71 | 33.23 | 33.03 | 24.56 | 33.43 | 50.71 | 33.32 | 32.33 | 32.18 | 27.09 | 33.33
ComplEx | 70.44 | 37.10 | 27.32 | 26.53 | 13.83 | 35.14 | 65.57 | 35.67 | 37.48 | 36.13 | 12.70 | 34.76
RotatE | 74.87 | 38.92 | 37.57 | 37.82 | 32.47 | 38.73 | 73.71 | 38.98 | 38.42 | 37.79 | 36.40 | 38.36

Baselines. To validate the effectiveness of learning in FedLU, we compare
FedLU with various federated KG embedding methods, including FedE (Chen et
al., 2021b), FedProx (Li et al., 2020b)333Our implementation of FedProx is
FedE with a regularization term, which keeps local embeddings close to global
embeddings by minimizing their distance
$||\mathbf{E}^{k}-\mathbf{E}^{k}_{t}||_{L2}$., FedEC (Chen et al., 2022), and
two baseline settings, namely independent and centralized. The independent
setting means training separate embeddings for each client with its local
dataset, and the centralized setting means training a global embedding by
aggregating the local datasets from all clients. All these methods and
settings are realized with three representative KG embedding models, i.e.,
TransE (Bordes et al., 2013), ComplEx (Trouillon et al., 2016) and RotatE (Sun
et al., 2019).

Evaluation setup. Following the convention, we use average Hits@$N$
($N=1,3,10$) and mean reciprocal rank (MRR) of all clients under the filtered
setting to evaluate the entity link prediction performance of each method. The
local triplets in each client are randomly divided with the ratio 8:1:1 for
training, validation and test. We report the results of local and global
embeddings of FedLU.

Implementation details. We employ the Adam (Kingma and Ba, 2015) optimizer
with a learning rate of 1e-4. For the independent and centralized settings, we
evaluate the validation set every 5 epochs. We further use early stop based on
MRR on the validation sets with a patience of 3. For FedLU and other
competitors, we train the local model for 3 epochs in each communication
round. We also evaluate the validation sets every 5 communication rounds.
Moreover, we set the patience to 3 for early stop based on the average MRR of
all clients. The sampling fraction to select involved clients in each round of
federated KG embedding learning is set to 100% following FedE and FedEC. Note
that FedLU has the ability to deal with varying sampling fractions. For the KG
embedding models, we set the batch size to 1,024, the negative sampling size
to 256, and the dimension of entity and relation embeddings to 256. For
FedProx, we set $\mu$ for the proximal term to 0.1. For FedEC, we set $\tau$
to 0.2 and $\mu_{\text{con}}$ to 0.3. For FedLU, we set $\mu_{\text{distill}}$
to 2.

Results. The results on FB15k-237-C3, C5 and C10 are presented in Table 1, and
those on FB15k-237-R3, R5 and R10 are shown in Appendix C.1. We can find that
(i) our proposed FedLU can generally achieve better performance in link
prediction than others. (ii) For different client numbers, FedLU achieves
consistent performance after convergence. As shown in Figure 4 shortly, the
convergence round becomes larger with the number of clients increases. (iii)
Compared to the independent setting, FedProx, FedEC and FedLU all gain
improvement, while the results of FedE do not significantly increase or even
decline sometimes. This indicates that FedE can hardly handle such
heterogeneous datasets. (iv) We also see that, in several cases, FedLU even
outperforms the centralized setting, suggesting that for the datasets with
strong heterogeneity, smoothly exchanging knowledge through mutual
distillation is more appropriate than directly sharing data. (v) In most
cases, FedLU (global) achieves the second-best performance, which is only
behind FedLU (local). This shows that FedLU obtains a global entity embedding
which is compatible with local embeddings in clients.

###  5.3. Experiments on Federated Unlearning

Baselines. To assess the federated unlearning in FedLU, we compare the
performance of raw, re-trained and unlearned embeddings. The raw embeddings
are derived from federated learning of FedLU. The re-trained embeddings are
re-trained from scratch using the retaining triplets. The unlearned embeddings
are generated from raw embeddings through unlearning in FedLU.

Evaluation setup. We randomly sample a forgetting set from the original
training set of each client with a proportion of 1%. We feed the forgetting
sets into re-trained/unlearned embeddings, and compare the prediction results
with those obtained by the raw embeddings, to measure the ability of FedLU in
forgetting specific knowledge. Smaller Hits@1 and MRR on the forgetting sets
indicate that the model forgets more thoroughly. In addition, we use the
original test sets to quantify how much performance reduction that we have to
pay as the cost of unlearning. We compare the local and global embeddings to
see if the unlearned knowledge can be propagated to the global embedding
smoothly in FedLU. The re-trained local embeddings are obtained with a single
embedding model for each client with their local retaining sets. The re-
trained global embedding is generated by aggregating the retaining sets of all
clients. We report the average Hits@1 and MRR scores on the forgetting and
test sets of all clients.

Implementation details. For the re-trained embeddings, we follow the previous
hyperparameter settings. For the retroactive interference in unlearning, we
set $\mu_{\text{soft}}$ to 0.1. Moreover, we set the training epoch of
unlearning to 10, which is much smaller than re-training.

Results. The unlearning results on the FB15k-237-C3 dataset are shown in Table
2, and other results are given in Appendix C.2. We have three findings: (i)
The Hits@1 and MRR scores of the re-trained models on the forgetting sets are
close to those on the test sets. This indicates that the re-trained models are
still able to predict missing links, i.e., completely forgetting cannot be
achieved through re-training from scratch. (ii) The scores of the unlearned
embeddings drop to a lower level on the forgetting sets than the raw
embeddings and the re-trained embeddings, suggesting that FedLU is able to
erase the knowledge thoroughly and suppress the activation of the memory to
the forgetting sets during unlearning. (iii) The unlearned embeddings achieve
comparable performance on the test sets with the raw models, which is higher
than the re-trained models. This indicates that unlearning in FedLU can
maintain the global knowledge absorbed in FL.

###  5.4. Further Analysis

Ablation study. Regarding the learning in FedLU, if we abrogate the mutual
knowledge distillation between the global and local embeddings, the global
embedding degrades to the entity embedding in FedE and the local embeddings
degrade to the entity embeddings in the independent setting. The performance
of the global and local embeddings in FedLU is much better than FedE and the
independent setting, which validates the smooth knowledge exchange realized by
mutual knowledge distillation.

To evaluate the effectiveness of the hard and soft confusions in the
retroactive interference step of FedLU, we modify two variants in federated
unlearning, namely FedLU without hard confusion and FedLU without soft
confusion. From Table 3, we find that: (i) The Hits@1 scores of FedLU without
hard or soft confusion on the forgetting sets are much lower than those of the
raw models in Table 2, suggesting that both of them are effective. (ii) FedLU
without hard confusion shows higher Hits@1 on the forgetting sets, indicating
that the hard confusion plays a key role in unlearning. (iii) The Hits@1
scores of FedLU without soft confusion is slightly higher than the original
FedLU. This shows that the soft confusion acts as a fine-tuning factor in
retroactive inference.

Table 3. Ablation studies on FB15K-237-C3 Hits@1 | Unlearned local | Unlearned global
---|---|---
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 13.23 | 21.04 | 15.02 | 20.95
w/o hard confusion | 17.32 | 21.18 | 18.06 | 20.99
w/o soft confusion | 15.87 | 20.73 | 15.28 | 20.59
ComplEx |  6.26 | 23.49 |  5.72 | 23.03
w/o hard confusion | 19.94 | 23.31 | 18.36 | 22.82
w/o soft confusion |  7.71 | 23.36 |  6.48 | 23.00
RotatE | 19.65 | 26.66 | 22.73 | 26.24
w/o hard confusion | 34.23 | 26.06 | 32.60 | 25.84
w/o soft confusion | 21.59 | 26.23 | 24.69 | 26.24
Figure 4. Hits@1 results of TransE on the validation sets w.r.t. communication
rounds.

Convergence speed. Figure 4 shows the average Hits@1 of FedLU (TransE) on the
validation sets w.r.t. communication rounds, compared with other competitors.
In addition to the higher average Hits@1, we can also see that the mutual
distillation of the local and global embeddings makes FedLU converge faster,
while other competitors converge slower due to directly using the aggregated
global embedding for initializing local training.

Entity embedding visualization. To find out the reason that FedLU shows
advantage against other federated KG embedding methods, we plot the t-SNE (van
der Maaten and Hinton, 2008) visualization of the entity embeddings on
FB15k-237-C3 for each client using TransE in Figure 5. Appendix C.3 shows the
visualization on FB15k-237-C5. The triplet proportions in the three clients
are approximately 18:5:80. We observe that FedE, FedProx and FedEC exhibit
commonalities in their embeddings: entities on Client 2 (with less triplets)
are isolated, while entities on Client 1 and Client 3 are highly overlapping.
This indicates that, for better performance in KG embedding, FedE, FedProx and
FedEC tend to aggregate knowledge of the clients with more triplets while
ignoring clients with less triplets. However, FedLU shows a quite different
manner. The entity embeddings between each client intersect with each other,
but only have small overlap. Also, the entity embeddings within each client
are more clustered. This indicates that the entity embeddings generated by
FedLU can not only relate and aggregate the knowledge of all clients, but also
give consideration to the local optimization. FedLU achieves better
performance than others as the learned embeddings describe different but
related sides of corresponding entities.

(a) FedE

(b) FedProx

(c) FedEC

(d) FedLU

Figure 5. t-SNE plot of entity embeddings on FB15k-237-C3 from each client
using TransE, where blue, red and green dots are from Clients 1, 2 and 3,
respectively.

##  6\. Conclusion

We propose FedLU, a novel federated KG embedding learning and unlearning
framework. In federated learning, we design mutual knowledge distillation to
smoothly exchange knowledge among clients, achieving global convergence and
local optimization. In federated unlearning, we combine retroactive
interference and passive decay to enable triplet unlearning and propagation.
We conduct extensive experiments on three newly-constructed datasets of
heterogeneity. The experimental results show that FedLU achieves better
accuracy in link prediction. It can also forget specific knowledge without
significantly hurting the overall performance. In future work, we plan to
study the continual learning and unlearning of federated KG embedding along
the life cycle of KGs.

Acknowledgments. This work is supported by National Natural Science Foundation
of China (No. 62272219).

## References

  * (1)
  * Balazevic et al. (2019) Ivana Balazevic, Carl Allen, and Timothy Hospedales. 2019\.  TuckER: Tensor Factorization for Knowledge Graph Completion. In _EMNLP-IJCNLP_. ACL, Hong Kong, China, 5185–5194.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating Embeddings for Modeling Multi-relational Data. In _NIPS_. Curran Associates, Inc., Lake Tahoe, NV, USA, 2787–2795.
  * Bourtoule et al. (2021) Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. 2021.  Machine Unlearning. In _SP_. IEEE, San Francisco, CA, USA, 141–159.
  * Cao and Yang (2015) Yinzhi Cao and Junfeng Yang. 2015.  Towards Making Systems Forget with Machine Unlearning. In _SP_. IEEE, San Jose, CA, USA, 463–480.
  * Chen et al. (2021b) Mingyang Chen, Wen Zhang, Zonggang Yuan, Yantao Jia, and Huajun Chen. 2021b.  FedE: Embedding Knowledge Graphs in Federated Setting. In _IJCKG_. ACM, Virtual, 80–88.
  * Chen et al. (2022) Mingyang Chen, Wen Zhang, Zonggang Yuan, Yantao Jia, and Huajun Chen. 2022.  Federated Knowledge Graph Completion via Embedding-contrastive Learning.  _Knowledge-Based Systems_ 252 (2022), 109459.
  * Chen et al. (2021a) Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. 2021a.  When Machine Unlearning Jeopardizes Privacy. In _SIGSAC_. ACM, Virtual, 896–911.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2D Knowledge Graph Embeddings. In _AAAI_. AAAI Press, New Orleans, LA, USA, 1811–1818.
  * Ginart et al. (2019) Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. 2019\.  Making AI Forget You: Data Deletion in Machine Learning. In _NeurIPS_. Curran Associates, Inc., Vancouver, BC, Canada, 3513–3526.
  * Hanzely and Richtárik (2020) Filip Hanzely and Peter Richtárik. 2020.  Federated Learning of a Mixture of Global and Local Models.  _CoRR_ (2020), abs/2002.05516.
  * Hardt et al. (2013) Oliver Hardt, Karim Nader, and Lynn Nadel. 2013.  Decay happens: the role of active forgetting in memory.  _Trends in Cognitive Sciences_ 17, 3 (2013), 111–120.
  * Ji et al. (2021) Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. 2021.  A Survey on Knowledge Graphs: Representation, Acquisition, and Applications.  _IEEE Transactions on Neural Networks and Learning Systems_ 33, 2 (2021), 494–514.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization. In _ICLR_. OpenReview.net, San Diego, CA, USA, 1–15.
  * Lample et al. (2018) Guillaume Lample, Alexis Conneau, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2018\.  Word Translation without Parallel Data. In _ICLR_. OpenReview.net, Vancouver, Canada, 1–14.
  * Lee et al. (2022) Gihun Lee, Yongjin Shin, Minchan Jeong, and Se-Young Yun. 2022\.  Preservation of the Global Knowledge by Not-True Self Knowledge Distillation in Federated Learning. In _NeurIPS_. OpenReview.net, New Orleans, LA, USA, 14 pages.
  * Li and Wang (2019) Daliang Li and Junpu Wang. 2019.  FedMD: Heterogenous Federated Learning via Model Distillation. In _NeurIPS Workshop on Federated Learning for User Privacy and Data Confidentiality_. CoRR, Vancouver, BC, Canada, 8 pages.
  * Li et al. (2021a) Qinbin Li, Bingsheng He, and Dawn Song. 2021a.  Model-Contrastive Federated Learning. In _CVPR_. IEEE, Virtual, 10713–10722.
  * Li et al. (2021b) Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. 2021b.  A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection.  _IEEE Transactions on Knowledge and Data Engineering_ Early Access (2021), 10.1109/TKDE.2021.3124599.
  * Li et al. (2020b) Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. 2020b.  Federated Optimization in Heterogeneous Networks. In _MLSys_. mlsys.org, Austin, TX, USA, 429–450.
  * Li et al. (2020a) Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. 2020a.  On the Convergence of FedAvg on Non-IID Data. In _ICLR_. OpenReview.net, Addis Ababa, Ethiopia, 1–26.
  * Liang et al. (2019) Paul Pu Liang, Terrance Liu, Ziyin Liu, Ruslan Salakhutdinov, and Louis-Philippe Morency. 2019\.  Think Locally, Act Globally: Federated Learning with Local and Global Representations. In _NeurIPS Workshop on Federated Learning for User Privacy and Data Confidentiality_. CoRR, Vancouver, BC, Canada, 34 pages.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. 2017\.  Communication-Efficient Learning of Deep Networks from Decentralized Data. In _AISTATS_. PMLR, Fort Lauderdale, FL, USA, 1273–1282.
  * Meng et al. (2021) Weiqiao Meng, Shizhan Chen, and Zhiyong Feng. 2021\.  Federated Knowledge Graph Embeddings with Heterogeneous Data. In _CCKS_. Springer, Guangzhou, China, 16–26.
  * Ng et al. (2001) Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. 2001\.  On Spectral Clustering: Analysis and an algorithm. In _NIPS_. MIT Press, Vancouver, British Columbia, Canada, 849–856.
  * Nguyen et al. (2018) Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. 2018.  A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network. In _NAACL-HLT_. ACL, New Orleans, LA, USA, 327–333.
  * Peng et al. (2021) Hao Peng, Haoran Li, Yangqiu Song, Vincent W. Zheng, and Jianxin Li. 2021.  Differentially Private Federated Knowledge Graphs Embedding. In _CIKM_. ACM, Queensland, Australia, 1416–1425.
  * Scannapieco et al. (2007) Monica Scannapieco, Ilya Figotin, Elisa Bertino, and Ahmed K. Elmagarmid. 2007.  Privacy Preserving Schema and Data Matching. In _SIGMOD_. ACM, Beijing, China, 653–664.
  * Schlichtkrull et al. (2018) Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018.  Modeling Relational Data with Graph Convolutional Networks. In _ESWC_. Springer, Heraklion, Crete, Greece, 593–607.
  * Seo et al. (2022) Hyowoon Seo, Jihong Park, Seungeun Oh, Mehdi Bennis, and Seong-Lyun Kim. 2022.  _Federated Knowledge Distillation_.  Cambridge University Press, Cambridge, UK, Chapter Machine Learning and Wireless Communications, 457–485.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019\.  RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In _ICLR_. OpenReview.net, New Orleans, LA, USA, 1–18.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex Embeddings for Simple Link Prediction. In _ICML_. PMLR, New York, NY, USA, 2071–2080.
  * van der Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing Data using t-SNE.  _Journal of Machine Learning Research_ 9, 11 (2008), 2579–2605.
  * Vashishth et al. (2020) Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. 2020.  Composition-based Multi-Relational Graph Convolutional Networks. In _ICLR_. OpenReview.net, Addis Ababa, Ethiopia, 1–15.
  * Wang et al. (2017) Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017\.  Knowledge Graph Embedding: A Survey of Approaches and Applications.  _IEEE Transactions on Knowledge and Data Engineering_ 29, 12 (2017), 2724–2743.
  * Wixted (2021) John T Wixted. 2021\.  _The role of retroactive interference and consolidation in everyday forgetting_.  Routledge, London, UK, Chapter Current Issues in Memory, 117–143.
  * Wu et al. (2022) Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Yongfeng Huang, and Xing Xie. 2022.  Communication-efficient Federated Learning via Knowledge Distillation.  _Nature Communications_ 13 (2022), 8 pages.
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In _ICLR_. OpenReview.net, San Diego, CA, USA, 1–12.
  * Yang et al. (2019) Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. 2019\.  Federated Machine Learning: Concept and Applications.  _ACM Transactions on Intelligent Systems and Technology_ 10, 2 (2019), 12:1–12:19.
  * Zhang et al. (2022) Kai Zhang, Yu Wang, Hongyi Wang, Lifu Huang, Carl Yang, and Lichao Sun. 2022\.  Efficient Federated Learning on Knowledge Graphs via Privacy-preserving Relation Embedding Aggregation. In _ACL Workshop on FL4NLP_. OpenReview.net, Dublin, Ireland, 8 pages.
  * Zhang et al. (2020) Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. 2020\.  Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction. In _AAAI_. AAAI Press, New York, USA, 3065–3072.

##  Appendix A Dataset Construction Algorithm

Algorithm 2 presents the pseudo-code. In Lines 3-5, we record the set of
relations linked by each entity as $E2R$. In Lines 6-10, we calculate the co-
occurrence matrix $M$ of relations based on $E2R$. In Line 11, we select a
spectral clustering algorithm (Ng et al., 2001) to partition relations.
Specifically, the Laplacian matrix $L$ of $M$ is first computed. Then, the
first $|K|$ eigenvalues and corresponding eigenvectors of $L$ are solved and
formed into matrix $S\in\mathbb{R}_{|R|\times|K|}$, each row of which denotes
the feature of a relation in a $|K|$-dimensional space. Next, the k-means
clustering algorithm is conducted on $S$ to divide $R$ into $|K|$ clusters.
Finally, the triplets are distributed in Line 12.

Input: original KG $G=\\{(h,r,t)\\}$, client number $|K|$

Output: dataset $D=\\{G^{k}\\}_{k=1}^{|K|}$, s.t. $G^{k}\subset
G,\bigcup_{k=1}^{|K|}G^{k}=G$

1 $E=\\{h\,|\,(h,r,t)\in G\\}\cup\\{t\,|\,(h,r,t)\in G\\}$;

2 $R=\\{r\,|\,(h,r,t)\in G\\}$;

$E2R\leftarrow\mathop{Dict}()$ ;

// init mappings from ent. to rel.

3 foreach  _$e\in E$_ do $E2R[e]\leftarrow\mathop{Set}()$;

4 foreach  _$(h,r,t)\in G$_ do $E2R[h].\mathop{add}(r)$;
$E2R[t].\mathop{add}(r)$;

$M\leftarrow[0]_{|R|\times|R|}$ ;

// init co-occurrence matrix

5 foreach  _$e\in E$_ do

6 $R^{\prime}\leftarrow E2R[e]$;

7 foreach  _$r_{1},r_{2}\in R^{\prime},r_{1}\neq r_{2}$_ do

8 $M[r_{1},r_{2}]\leftarrow M[r_{1},r_{2}]+1$;

9

10

11$\\{R^{1},R^{2},\dots,R^{|K|}\\}\leftarrow\mathop{SpectralClustering}(R,M,K)$;

12 foreach  _$k=1,\dots,|K|$_ do $G^{k}\leftarrow\\{(h,r,t)\in G\,|\,r\in
R^{k}\\}$;

Algorithm 2 Clustering-based dataset construction

##  Appendix B Dataset Comparison

Figure 6 shows the comparison results of the degree distributions between
FB15k-237-C5 and FB15k-237-R5, and between FB15k-237-C10 and FB15k-237-R10. We
can find that the degree distributions on FB15k-237-C5/C10 vary more
significantly. Such situations are similar to those on FB15k-237-C3 and
FB15k-237-R3.

Figure 6. Comparison of degree distributions between FB15k-237-C5/C10 and
FB15k-237-R5/R10

##  Appendix C More Experimental Results

(a) FedE

(b) FedProx

(c) FedEC

(d) FedLU

Figure 7. t-SNE plot of entity embeddings on FB15k-237-C5 from each client
using TransE, where blue, red, green, cyan and magenta dots are from Clients
1, 2, 3, 4 and 5, respectively.

###  C.1. Learning Results on FB15k-237-R3/R5/R10

We also conduct link prediction on FB15k-237-R3, R5 and R10. Table 4 presents
the experimental results. We can observe that both FedLU and existing
federated KG embedding methods generally achieve an improvement compared with
the independent setting. FedLU outperforms other competitors stably on all the
three datasets, and even beats the centralized setting sometimes.

Compared with the results in Table 1, we also find two interesting
differences. First, the gap between the independent setting and the
centralized setting is more significant. This is because FB15k-237-R3/R5/R10
are less heterogeneous, which are easier to obtain noticeable increases with
more data. Second, FedLU (local) generally underperforms FedLU (global) in
Table 4, while it performs better in Table 1. The global embedding stored in
FedLU represents the characteristics of the entire data. They cannot capture
the local heterogeneous data on each client well. FB15k-237-R3/R5/R10 do not
encounter such an issue as they are nearly homogeneous.

###  C.2. Unlearning Results on FB15k-237-C5/C10

We also conduct federated unlearning on FB15k-237-C5 and FB15k-237-C10. Tables
5 and 6 show the average results. The conclusion is similar to that from Table
2. Compared with the raw results, the results on the forgetting sets decrease
rapidly with our unlearning method, while there are only slight declines on
the test sets. We also notice that the re-trained results on the forgetting
sets are much higher than our unlearning results. This not only indicates that
simply re-training on the retaining sets cannot achieve unlearning, but also
validates that our proposed unlearning method is effective.

###  C.3. Entity Embedding Visualization on FB15k-237-C5

Figure 7 visualizes the entity embeddings for each client on FB15k-237-C5 with
TransE. We also find that the entity embeddings of FedLU on each client are
better clustered than other competitors, which demonstrates the superiority of
FedLU.

Table 4. Average link prediction results on FB15k-237-R3/R5/R10 Methods | FB15k-237-R3 | FB15k-237-R5 | FB15k-237-R10
---|---|---|---
Hits@1 | Hits@3 | Hits@10 | MRR | Hits@1 | Hits@3 | Hits@10 | MRR | Hits@1 | Hits@3 | Hits@10 | MRR
TransE | Independent | 19.86 | 38.15 | 55.12 | 31.96 | 19.02 | 37.29 | 53.65 | 30.98 | 17.02 | 36.40 | 53.50 | 29.61
Centralized | 20.17 | 38.56 | 56.01 | 32.44 | 20.34 | 38.90 | 56.60 | 32.74 | 19.48 | 38.43 | 56.86 | 32.21
FedE | 20.21 | 38.77 | 56.33 | 32.52 | 20.11 | 38.70 | 56.24 | 32.45 | 19.35 | 38.57 | 56.51 | 32.10
FedProx | 20.02 | 38.71 | 55.98 | 32.38 | 19.97 | 38.54 | 55.42 | 32.25 | 18.57 | 37.89 | 55.02 | 31.24
FedEC | 19.96 | 38.72 | 56.30 | 32.40 | 20.27 | 39.03 | 56.32 | 32.66 | 19.19 | 38.82 | 56.93 | 32.13
FedLU (local) | 20.88 | 39.42 | 56.63 | 33.12 | 20.49 | 39.68 | 56.88 | 33.05 | 19.99 | 39.33 | 56.79 | 32.69
FedLU (global) | 22.06 | 41.62 | 58.74 | 34.75 | 21.35 | 41.52 | 59.06 | 34.38 | 21.53 | 41.98 | 59.78 | 34.77
ComplEx | Independent | 21.51 | 34.06 | 47.51 | 30.31 | 21.43 | 33.71 | 46.67 | 30.04 | 20.68 | 33.61 | 47.08 | 29.64
Centralized | 23.42 | 39.89 | 56.23 | 34.54 | 24.42 | 41.03 | 57.29 | 35.53 | 24.71 | 41.00 | 57.83 | 35.83
FedE | 20.29 | 36.31 | 52.69 | 31.22 | 18.57 | 35.18 | 51.78 | 29.83 | 17.64 | 34.25 | 51.45 | 29.06
FedProx | 22.18 | 39.65 | 56.09 | 33.78 | 17.02 | 29.55 | 43.42 | 25.89 | 16.78 | 28.72 | 42.74 | 25.47
FedEC | 18.07 | 31.08 | 45.15 | 27.19 | 17.51 | 30.51 | 44.53 | 26.62 | 17.54 | 31.78 | 47.95 | 27.75
FedLU (local) | 22.79 | 39.83 | 56.22 | 34.15 | 21.91 | 38.41 | 54.14 | 32.94 | 22.02 | 35.88 | 49.78 | 31.52
FedLU (global) | 22.64 | 40.28 | 56.70 | 34.28 | 21.25 | 38.73 | 55.77 | 32.99 | 18.92 | 33.70 | 50.00 | 29.44
RotatE | Independent | 23.10 | 39.01 | 54.65 | 33.84 | 21.97 | 38.19 | 53.80 | 32.83 | 21.10 | 37.06 | 52.91 | 31.90
Centralized | 25.07 | 44.17 | 61.36 | 37.47 | 25.28 | 44.63 | 62.08 | 37.89 | 24.24 | 44.66 | 62.44 | 37.39
FedE | 20.82 | 38.99 | 56.23 | 32.94 | 24.65 | 44.04 | 61.40 | 37.28 | 23.39 | 43.69 | 61.28 | 36.44
FedProx | 25.42 | 43.91 | 61.05 | 37.59 | 24.95 | 44.05 | 60.87 | 37.28 | 22.87 | 42.33 | 59.50 | 35.46
FedEC | 25.63 | 44.42 | 61.36 | 37.90 | 25.08 | 44.27 | 61.05 | 37.51 | 23.81 | 43.73 | 61.32 | 36.72
FedLU (local) | 25.82 | 45.35 | 61.98 | 38.36 | 25.20 | 44.54 | 61.14 | 37.82 | 24.27 | 44.99 | 62.45 | 37.52
FedLU (global) | 25.29 | 43.33 | 59.93 | 37.15 | 24.23 | 44.56 | 61.18 | 37.24 | 24.29 | 44.82 | 62.42 | 37.47
The best and second best scores are marked in bold and with underline,
respectively.
Table 5. Average unlearning results on different sets of FB15k-237-C5 with the local and global models Hits@1 | Raw local | Re-trained local | Unlearned local | Raw global | Re-trained global | Unlearned global
---|---|---|---|---|---|---
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 43.24 | 21.89 | 19.83 | 21.08 | 12.72 | 21.03 | 37.92 | 21.73 | 19.32 | 20.03 | 13.08 | 21.12
ComplEx | 60.37 | 24.05 | 17.87 | 19.01 |  3.60 | 21.85 | 54.37 | 22.03 | 23.01 | 21.93 |  2.70 | 21.15
RotatE | 69.65 | 27.38 | 25.10 | 26.82 | 17.61 | 26.86 | 64.27 | 27.07 | 25.66 | 25.83 | 17.57 | 26.68
MRR | Raw local | Re-trained local | Unlearned local | Raw global | Re-trained global | Unlearned global
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 56.58 | 34.32 | 32.21 | 33.34 | 22.71 | 33.40 | 51.98 | 34.30 | 31.53 | 32.26 | 23.54 | 33.58
ComplEx | 71.14 | 35.66 | 28.64 | 29.72 |  9.35 | 33.47 | 65.68 | 34.07 | 35.44 | 34.33 |  8.21 | 32.85
RotatE | 78.69 | 38.93 | 36.77 | 38.39 | 29.80 | 38.55 | 74.41 | 39.11 | 37.61 | 38.04 | 29.73 | 38.52
Table 6. Average unlearning results on different sets of FB15k-237-C10 with the local and global models Hits@1 | Raw local | Re-trained local | Unlearned local | Raw global | Re-trained global | Unlearned global
---|---|---|---|---|---|---
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 39.81 | 21.05 | 18.76 | 18.59 | 13.61 | 20.33 | 35.65 | 20.58 | 20.65 | 20.94 | 14.42 | 20.12
ComplEx | 57.54 | 25.14 | 15.84 | 16.62 | 10.29 | 24.12 | 49.12 | 22.07 | 23.28 | 23.66 |  6.65 | 21.65
RotatE | 64.82 | 26.01 | 24.95 | 24.47 | 16.37 | 25.18 | 60.62 | 25.71 | 24.17 | 24.12 | 18.28 | 25.14
MRR | Raw local | Re-trained local | Unlearned local | Raw global | Re-trained global | Unlearned global
Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$ |  Forget$\downarrow$ |  Test$\uparrow$
TransE | 53.90 | 33.44 | 30.69 | 30.78 | 24.29 | 32.68 | 49.60 | 32.95 | 33.85 | 34.18 | 25.33 | 32.58
ComplEx | 67.76 | 36.33 | 27.02 | 27.77 | 18.71 | 35.22 | 59.91 | 33.45 | 35.57 | 36.03 | 13.29 | 32.66
RotatE | 75.16 | 38.22 | 36.87 | 37.36 | 28.20 | 37.37 | 71.27 | 38.00 | 35.50 | 35.50 | 30.69 | 37.36