# Privacy-Preserving XGBoost Inference

Xianrui Meng Joan Feigenbaum
AWS Cryptography Algorithm
{xianru<EMAIL_ADDRESS>
Amazon Scholar and Grace Hopper Prof. of Computer Science at Yale University

###### Abstract

Although machine learning (ML) is widely used for predictive tasks, there are
important scenarios in which ML cannot be used or at least cannot achieve its
full potential. A major barrier to adoption is the sensitive nature of
predictive queries. Individual users may lack sufficiently rich datasets to
train accurate models locally but also be unwilling to send sensitive queries
to commercial services that vend such models. One central goal of privacy-
preserving machine learning (PPML) is to enable users to submit encrypted
queries to a remote ML service, receive encrypted results, and decrypt them
locally. We aim at developing practical solutions for real-world privacy-
preserving ML inference problems. In this paper, we propose a privacy-
preserving ${\mathsf{XGBoost}}$ prediction algorithm, which we have
implemented and evaluated empirically on AWS SageMaker. Experimental results
indicate that our algorithm is efficient enough to be used in real ML
production environments.

##  1 Introduction

Machine Learning (ML) plays an important role in daily life. Pervasive use of
digital devices and networks produces massive amounts of data that are
analyzed to reveal patterns and correlations that, in turn, are used to draw
conclusions or make predictions. Diverse applications that make successful use
of ML include market forecasting, service personalization, voice and facial
recognition, autonomous driving, health diagnostics, education, and security
analytics.

Clearly in tension with the utility of ML is the desire of individuals and
organizations for data privacy. Both the input and the output of an ML
prediction may be highly personal, confidential information and may be
constrained by regulations. For example, students’ confidential educational
records are governed by FERPA – the Family Educational Rights and Privacy Act.
Organizations that produce valuable models may wish to sell access to them on
a pay-per-prediction basis and must protect them as one would any valuable
form of digital intellectual property. The need to maintain the privacy of
data subjects, to protect intellectual property, and to keep commercially
valuable instances and predictions confidential motivate the study of privacy-
preserving machine learning (PPML).

Gentry has shown that one can perform arbitrary computations on encrypted data
using fully homomorphic-encryption (FHE) (16). In principle, FHE could fully
resolve the tension between utility of ML and data-privacy requirements, but
there are application scenarios in which it is prohibitively computationally
expensive by orders of magnitude. In these scenarios, it is natural to seek
specialized homomorphic-encryption (SHE) schemes that are more efficient. We
provide one such scheme in this paper.

Extreme Gradient Boosting (${\mathsf{XGBoost}}$) (9) is an optimized,
distributed, gradient-boosting ML framework designed to be highly efficient,
flexible, and portable. It performs parallel tree boosting that solves many
classification and regression problems quickly and accurately. For example, 17
of the 29 challenge-winning solutions published on Kaggle’s blog in 2015 used
${\mathsf{XGBoost}}$ (33), Facebook uses it to predict click through on
advertisements (19), and it is very popular on Amazon’s managed-cloud ML
platform SageMaker.111https://aws.amazon.com/sagemaker/

We present ${\mathsf{PPXGBoost}}$, a privacy-preserving
${\mathsf{XGBoost}}$-prediction algorithm, in Section 2. In Section 3, we
explain the security definition and the privacy properties that our algorithm
achieves. Experimental results are given in Section 4. Finally, we present
open problems in Section 5.

##  2 Privacy-preserving XGBoost

###  2.1 Preliminaries

#### XGBoost

Upon receiving a training dataset, the ${\mathsf{XGBoost}}$ training algorithm
produces an ML model in the form of a set $\\{T_{i}\\}_{i=1}^{M}$ of
classification and regression trees (CARTs). A CART is a generalization of a
decision tree; while the latter produces a binary output, thus classifying
each input query as a “yes” or “no” instance of the phenomenon under study, a
CART assigns to each input query a (real) numerical score. Interpretation of
scores is application-dependent.222This is one of the roles of the hyper-
parameter $\alpha$ referred to in Subsection 2.2 We use boldface lowercase
letters, such as $\mathbf{v}$, to denote a vector of real numbers. If
$\mathbf{v}$ is an input query, and $\\{y_{i}\leftarrow
T_{i}(\mathbf{v})\\}_{i=1}^{M}$ is the set of scores produced by the CARTs,
then the final prediction (i.e., the overall score assigned to $\mathbf{v}$ by
${\mathsf{XGBoost}}$) is typically $y=\sum_{i=1}^{M}y_{i}$. Depending on the
application, a $softmax$ function may be applied to the $y_{i}$ to obtain the
final prediction, but we restrict attention to summation in this paper. A full
explanation of ${\mathsf{XGBoost}}$ training and inference can be found in the
original paper of Chen and Guestrin (9).

#### Homomorphic encryption

Homomorphic encryption is a form of encryption that can perform arbitrary
computation on plaintext values while manipulating only ciphertexts. In this
work, we use an additive SHE scheme. Specifically, let ${\sf
SHE}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be a public-key SHE that
consists of three polynomial-time algorithms. ${\mathsf{Gen}}$ is a
probabilistic algorithm that takes a security parameter $k$ as input and
returns a private and public key pair $(\sf pk,\sf sk)$. ${\mathsf{Enc}}$ is a
probabilistic encryption algorithm that takes as input a public key $\sf pk$
and a message $m$ and outputs a ciphertext. ${\mathsf{Dec}}$ is an algorithm
that takes as input a private key $\sf sk$ and a ciphertext and returns the
corresponding plaintext. In addition, ${\sf SHE}$ has an evaluation algorithm
${\mathsf{Eval}}$ that supports any number of additions over the plaintexts:
${\mathsf{Enc}}(\sf
pk,(m_{1}+\cdots+m_{n}))={\mathsf{Eval}}\big{(}+,{\mathsf{Enc}}(\sf
pk,m_{1}),\ldots,{\mathsf{Enc}}(\sf pk,m_{n})\big{)}$.

#### Order-preserving encryption

For $A,B\subseteq N$ with $|A|\leq|B|$, a function $f:A\to B$ is order-
preserving if, for all $i,j\in A$, $f(i)>f(j)$ if and only if $i>j$. We say
that a symmetric encryption scheme
$({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ with plaintext and ciphertext
spaces $\mathcal{D}$ and $\mathcal{R}$ is an order-preserving encryption
(${\mathsf{OPE}}$) scheme if ${\mathsf{Enc}}(\K,\cdot)$ is an order-preserving
function from $\mathcal{D}$ to $\mathcal{R}$, for all $K$ output by
${\mathsf{Gen}}(1^{k})$. To make sense of the $>$ relation in this context,
elements of $\mathcal{D}$ and $\mathcal{R}$ are encoded as binary strings,
which are then interpreted as numbers.

Throughout this paper, “polynomial” means “polynomial in the security
parameter $k$.” Formal definitions of these cryptographic concepts, including
the Pseudorandom Function (PRF) family and semantic security can be found in
(23).

${\mathsf{Setup}}$ Phase:
Input: Plaintext model $\Omega$; Security parameter $k$; Model hyper-parameter
$\alpha$. Proxy computes: -
$K_{1}\leftarrow{\mathsf{OPE}}.{\mathsf{Gen}}(1^{k})$; - $(\sf pk,\sf
sk)\leftarrow{\sf SHE}.{\mathsf{Gen}}(1^{k})$; - Choose $f$ uniformly at
random from ${\mathcal{F}}_{k}$ in the PRF family; - Choose $K_{2}$ uniformly
at random from $\\{0,1\\}^{k}$; - For each CART $T_{i}\in\Omega$, construct
$T_{i}^{\prime}$ in ${\mathsf{EncML}}$ as follows: – $T_{i}^{\prime}$ is
structurally isomorphic to $T_{i}$. Let $\phi:T_{i}\rightarrow T_{i}^{\prime}$
be an isomorphism; – For each internal node $x$ with value $\mathbf{v}$ in
$T_{i}$, assign the value ${\mathsf{OPE}}.{\mathsf{Enc}}(K_{1},\mathbf{v})$ to
$\phi(x)$; – For each leaf $z$ with value $y_{i}$ in $T_{i}$, assign the value
${\sf SHE}.{\mathsf{Enc}}(\sf pk,$ $y_{i})$ to $\phi(z)$; – For each feature
name $\ell$ used in $T_{i}$, create the corresponding feature pseudonym
$\ell^{\prime}\leftarrow f(K_{2},\ell)$; Proxy sends to ML Module:
${\mathsf{EncML}}$; Proxy sends to client: $\alpha$, $K_{1}$, $K_{2}$, $f$,
$\sf sk$; ${\mathsf{Query}}$ Phase:
Input (to client): Query $\mathbf{q}$. - Client computes: – For each feature
name $l$ in $\mathbf{q}$, compute the corresponding feature pseudonym
$l^{\prime}\leftarrow f(K_{2},l)$; – Encrypt the plaintext value:
$\mathbf{q^{\prime}}\leftarrow{\mathsf{OPE}}.{\mathsf{Enc}}(K_{1},\mathbf{q})$;
- Client sends to ML Module: $\mathbf{q^{\prime}}$ - ML Module computes: – For
each $T_{i}^{\prime}\in{\mathsf{EncML}}$, evaluate $T_{i}^{\prime}$ on
$\mathbf{q^{\prime}}$ to obtain value $y_{i}^{\prime}$; – Homomorphically sum
the values: $y^{\prime}\leftarrow{\sf
SHE}.{\mathsf{Eval}}(+,y_{1}^{\prime},\ldots,y_{n}^{\prime})$, where $n$ is
the number of CARTs in ${\mathsf{EncML}}$ (note: this step is slightly
different for computing softmax objective) ; - ML Module sends to client:
$y^{\prime}$; - Client decrypts the result: $y\leftarrow{\sf
SHE}.{\mathsf{Dec}}(\sf sk,$ $y^{\prime}$); - Client interprets the result
using the model hyper-parameter $\alpha$;

Figure 1:  ${\mathsf{PPXGBoost}}$: A privacy-preserving ${\mathsf{XGBoost}}$
inference algorithm

###  2.2 ${\mathsf{PPXGBoost}}$ inference algorithm

The ${\mathsf{PPXGBoost}}$ algorithm is given in Figure 1. On the client side,
there is an app with which a user encrypts queries and decrypts results. On
the server side, there is a module called ${\mathsf{Proxy}}$ that runs in a
trusted environment and is responsible for set up (i.e., creating, for each
authorized user, an encrypted model and a set of cryptographic keys) and an ML
module that evaluates the encrypted queries.

The inputs to the ${\mathsf{Setup}}$ phase are an ${\mathsf{XGBoost}}$ model
$\Omega$, a model hyper-parameter $\alpha$, and a security parameter $k$.
During this phase, ${\mathsf{Proxy}}$ generates, for each authorized user, the
keys $K_{1}$ and $(\sf pk,\sf sk)$. $K_{1}$ is the user’s key for the
(symmetric-key) OPE scheme. $(\sf pk,\sf sk)$ is the user’s key pair for the
(public-key) SHE scheme. ${\mathsf{Proxy}}$ then encrypts the node values in
each CART $T_{i}$ in $\Omega$ to create an encrypted CART $T_{i}^{\prime}$ in
this user’s encrypted model ${\mathsf{EncML}}$. For each internal node in
$T_{i}$ with value $\mathbf{x}$, the value of the corresponding node in
$T_{i}^{\prime}$ is ${\mathsf{OPE}}.{\mathsf{Enc}}(K_{1},\mathbf{x})$.
(Vectors of values are encrypted and decrypted component-wise.) For each leaf
in $T_{i}$ with value $y$, the value of the corresponding leaf in
$T_{i}^{\prime}$ is ${\sf SHE}.{\mathsf{Enc}}(\sf pk,$ $y)$. Finally, the
proxy sends $K_{1}$, $K_{2}$, $f$ and $\sf sk$ to the user’s client and sends
${\mathsf{EncML}}$ to the ML module.

In the ${\mathsf{Query}}$ phase, the client first encrypts its plaintext query
$\mathbf{q}$ with OPE, i.e., it computes
$\mathbf{q^{\prime}}\leftarrow{\mathsf{OPE}}.{\mathsf{Enc}}(K_{1},\mathbf{q})$.
It sends $\mathbf{q^{\prime}}$ to the ML module, which evaluates each
$T_{i}^{\prime}$ in ${\mathsf{EncML}}$ on input $\mathbf{q^{\prime}}$ to
obtain a value $y_{i}$. The module computes $y^{\prime}\leftarrow{\sf
SHE}.{\mathsf{Eval}}(+,y_{1}^{\prime},\dots,y_{n}^{\prime})$, where $n$ is the
number of CARTs, and sends it to the client, which decrypts to obtain the
final result $y\leftarrow{\sf SHE}.{\mathsf{Dec}}(\sf sk,$ ${y^{\prime}})$.

The correctness of this scheme follows directly from the properties of OPE and
SHE. Because $a>b$ if and only if
${\mathsf{OPE}}.{\mathsf{Enc}}(K_{1},a)>{\mathsf{OPE}}.{\mathsf{Enc}}(K_{1},b)$,
for all $a$, $b$, and $K_{1}$, and the same $K_{1}$ is used to encrypt both
queries and internal-node values in $\Omega$, an encrypted query will travel
precisely the same path through each encrypted CART $T_{i}^{\prime}$ that the
corresponding plaintext query would have traveled through the corresponding
plaintext CART $T_{i}$. Because the leaf values $y_{i}$ in $\Omega$ have been
encrypted using the additively homomorphic encryption operation ${\sf
SHE}.{\mathsf{Enc}}(\sf pk,$ $y_{i})$, and $\sf sk$ is the decryption key that
corresponds to $\sf pk$, the plaintext $y$ corresponding to the ciphertext sum
$y^{\prime}$ is the sum of the individual plaintext values $y_{i}$ in leaves
of $T_{i}$.

The proxy also chooses, for each authorized user, a function $f$ uniformly at
random from ${\mathcal{F}}_{k}$ in the PRF family and a a key $K_{2}$
uniformly at random from $\\{0,1\\}^{k}$ for use with $f$. This function is
used to generate pseudorandom “feature names” for vectors of queries and node
values. We defer discussion of this aspect of the algorithm until the full
paper.

Note that the plaintext $(\Omega,\alpha,k)$ can be used by a very large user
population, but a unique, personalized encrypted model must be created for
each individual user.

##  3 Privacy properties

Ideally, we would like a privacy-preserving inference algorithm to hide all
information about the model, the queries, and the results from all adaptive
probabilistic polynomial-time (PPT) adversaries.

For the ${\mathsf{Setup}}$ phase, this means that the adversary should be able
to choose a sequence $M_{1}$, $M_{2}$, $\ldots$, $M_{n}$ of plaintext models,
submit them to an oracle, and receive the corresponding sequence
$M_{1}^{\prime}$, $M_{2}^{\prime}$, $\ldots$, $M_{n}^{\prime}$ of encrypted
models; it may choose the sequence adaptively in the sense that its choice of
$M_{i}$ may depend upon the oracle’s answers $M_{1}^{\prime}$, $\ldots$,
$M_{i-1}^{\prime}$. After this adaptive, chosen-plaintext, oracle-query phase,
the adversary is presented with an encrypted model that it has not seen
before, and it cannot infer anything about the corresponding plaintext model.

For the ${\mathsf{Query}}$ phase, this means that, for a fixed encrypted model
$M^{\prime}$, the adversary should be able to choose a sequence $q_{1}$,
$q_{2}$, $\ldots$, $q_{n}$ of plaintext queries, submit them to an oracle, and
receive the corresponding sequence $\sigma=(q_{1}^{\prime},r_{1}^{\prime})$,
$(q_{2}^{\prime},r_{2}^{\prime})$, $\ldots$, $(q_{n}^{\prime},r_{n}^{\prime})$
of encrypted queries and encrypted results; once again, it may choose $q_{i}$
based on $\sigma_{i-1}=(q_{1}^{\prime},r_{1}^{\prime})$, $\ldots$,
$(q_{i-1}^{\prime},r_{i-1}^{\prime})$. After this adaptive query phase, it
cannot infer anything about the encrypted model; furthermore, when
subsequently presented with additional pairs
$(q_{n+1}^{\prime},r_{n+1}^{\prime})$, …,
$(q_{n+j}^{\prime},r_{n+j}^{\prime})$, it cannot infer anything about the
corresponding plaintext queries or answers.

Known algorithms that achieve these ideal privacy properties are not efficient
enough for practical use. As initiated in the work of Curtmola et al. (10) and
Chase and Kamara (8), one can instead define acceptable leakage functions and
devise efficient algorithms that provably leak only the values of these
functions. In ${\mathsf{PPXGBoost}}$, this information may be leaked to the ML
module and any party that observes the inner workings of the ML module, the
communication between ${\mathsf{Proxy}}$ and the ML module, or the
communication between the client and the ML module.

Because of space limitations we give the main ideas of our formal security
definitions, ${\mathsf{PPXGBoost}}$’s privacy properties, and our security
proof in Appendix B.

##  4 AWS SageMaker experiments

| time | Model size
---|---|---
Dataset | ${\mathsf{XGBoost}}$ | ${\mathsf{PPXGBoost}}$ | ${\mathsf{XGBoost}}$ | ${\mathsf{PPXGBoost}}$
Amazon Synthetic Data | $1ms$ | $0.43s$ | 506KB | 4.2MB
Titanic | $<1ms$ | $0.32s$ | 3KB | 12KB
US Census | $1ms$ | $0.49s$ | 210KB | 2.5MB
Table 1: ${\mathsf{PPXGBoost}}$ Performance

For our experiments on ${\mathsf{PPXGBoost}}$, we implemented the
cryptographic protocols in python3. We instantiated the PRF using
${\mathsf{HMAC}}$, and we used Paillier encryption (31) for our additive SHE
and Boldyreva et al.’s scheme (3) for our OPE.

An overview of our system architecture can be found in Appendix A. All of our
experiments were run on AWS. The ${\mathsf{Setup}}$ phase is deployed in AWS
Virtual Private Cloud 333https://aws.amazon.com/vpc/ environment. The
inference procedure is run on SageMaker using an $\mathsf{ml.t2.large}$
instance and the Amazon Elastic Container Service
444https://aws.amazon.com/ecs/. Our experimental results are summarized in
Table 1. We ran ${\mathsf{PPXGBoost}}$ on three different models derived from
three different datasets. One data is synthetically generated based on
Amazon’s dataset. The other two datasets are public datasets. On average,
${\mathsf{PPXGBoost}}$ inference is approximately $10^{3}$ times slower than
the plaintext version of ${\mathsf{XGBoost}}$. The size of encrypted models is
between four and nine times larger than that of the plaintext models. The
inference time includes the network traffic time. This performance is
sufficient for many inference tasks currently done on smart phones that must
query a remote server.

##  5 Open problems

Our initial version of ${\mathsf{PPXGBoost}}$ is still quite limited.
Currently, we can support binary classifications and multiclass classification
using the softmax objective. Future work includes support for more learning
parameters in the privacy-preserving version. Moreover, in our algorithm, we
leverage the order-preserving encryption scheme to support comparisons.
Comparison on semantically encrypted data is computationally expensive, but we
plan to investigate the use of secure multiparty computation for this purpose.
In particular, we will explore the use of two non-colluding servers that
execute secure comparison for each internal node in an encrypted CART.

## References

  * (1) Yoshinori Aono, Takuya Hayashi, Le Trieu Phong, and Lihua Wang.  Scalable and secure logistic regression via homomorphic encryption.  In 6th ACM Conference on Data and Application Security and Privacy, pages 142–144, 2016.
  * (2) Mauro Barni, Pierluigi Failla, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider.  Privacy-preserving ECG classification with branching programs and neural networks.  IEEE Trans. Information Forensics and Security, 6(2):452–468, 2011.
  * (3) Alexandra Boldyreva, Nathan Chenette, and Adam O’Neill.  Order-preserving encryption revisited: improved security analysis and alternative solutions.  In 31st CRYPTO, volume 6841 of Lecture Notes in Computer Science, pages 578–595. Springer, 2011.
  * (4) Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth.  Practical secure aggregation for privacy-preserving machine learning.  In 24th ACM Conference on Computer and Communications Security, pages 1175–1191, 2017.
  * (5) Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser.  Machine learning classification over encrypted data.  In 22nd Annual Network and Distributed System Security Symposium. The Internet Society, 2015.
  * (6) Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel, and Emmanuel Prouff.  Privacy-preserving classification on deep neural network.  Cryptology ePrint Archive, Report 2017/035, 2017.  https://eprint.iacr.org/2017/035.
  * (7) Nishanth Chandran, Divya Gupta, Aseem Rastogi, Rahul Sharma, and Shardul Tripathi.  Ezpc: Programmable, efficient, and scalable secure two-party computation.  Cryptology ePrint Archive, Report 2017/1109, 2017.  https://eprint.iacr.org/2017/1109.
  * (8) Melissa Chase and Seny Kamara.  Structured encryption and controlled disclosure.  In 16th ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 577–594. Springer, 2010.
  * (9) Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794, 2016.
  * (10) Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky.  Searchable symmetric encryption: Improved definitions and efficient constructions.  In 13th ACM Conference on Computer and Communications Security, pages 79–88, 2006.
  * (11) Wenliang Du and Mikhail J. Atallah.  Privacy-preserving cooperative scientific computations.  In 14th IEEE Computer Security Foundations Workshop, pages 273–294, 2001.
  * (12) Wenliang Du, Yunghsiang S. Han, and Shigang Chen.  Privacy-preserving multivariate statistical analysis: Linear regression and classification.  In 4th SIAM International Conference on Data Mining, pages 222–233, 2004.
  * (13) Stephen E. Fienberg, William J. Fulp, Aleksandra B. Slavkovic, and Tracey A. Wrobel.  “Secure” log-linear and logistic regression analysis of distributed databases.  In Privacy in Statistical Databases, volume 4302 of Lecture Notes in Computer Science, pages 277–290. Springer, 2006.
  * (14) Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In 22nd ACM Conference on Computer and Communications Security, pages 1322–1333, 2015.
  * (15) Adrià Gascón, Phillipp Schoppmann, Borja Balle, Mariana Raykova, Jack Doerner, Samee Zahur, and David Evans.  Privacy-preserving distributed linear regression on high-dimensional data.  Proceedings on Privacy-Enhancing Technologies, 2017(4):345–364, 2017.
  * (16) Craig Gentry.  Fully homomorphic encryption using ideal lattices.  In 41st ACM Symposium on Theory of Computing, pages 169–178, 2009\.
  * (17) Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing.  Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy.  In 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 201–210, 2016.
  * (18) Ran Gilad-Bachrach, Kim Laine, Kristin E. Lauter, Peter Rindal, and Mike Rosulek.  Secure data exchange: A marketplace in the cloud.  In 10th ACM Conference on Cloud Computing Security Workshop, pages 117–128, 2019.
  * (19) Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers, and Joaquin Quiñonero Candela.  Practical lessons from predicting clicks on ads at Facebook.  In 8th ACM International Workshop on Data Mining for Online Advertising, pages 1–9, 2014.
  * (20) Ehsan Hesamifard, Hassan Takabi, and Mehdi Ghasemi.  Cryptodl: Deep neural networks over encrypted data.  Computing Research Repository, abs/1711.05189, 2017.
  * (21) Briland Hitaj, Giuseppe Ateniese, and Fernando Pérez-Cruz.  Deep models under the GAN: information leakage from collaborative deep learning.  In 24th ACM Conference on Computer and Communications Security, pages 603–618, 2017.
  * (22) Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan.  Gazelle: A low latency framework for secure neural network inference.  Computing Research Repository, abs/1801.05507, 2018.
  * (23) Johnathan Katz and Yehuda Lindell.  Introduction to Modern Cryptography.  Chapman & Hall/CRC, 2008.
  * (24) Yi Li, Yitao Duan, and Wei Xu.  Privpy: Enabling scalable and general privacy-preserving computation.  Computing Research Repository, abs/1801.10117, 2018.
  * (25) Yehuda Lindell and Benny Pinkas.  Privacy-preserving data mining.  In 20th CRYPTO, volume 1880 of Lecture Notes in Computer Science, pages 36–54. Springer, 2000.
  * (26) Jian Liu, Mika Juuti, Yao Lu, and N. Asokan.  Oblivious neural network predictions via minionn transformations.  In 24th ACM Conference on Computer and Communications Security, pages 619–631, 2017.
  * (27) Yang Liu, Zhuo Ma, Ximeng Liu, Siqi Ma, Surya Nepal, and Robert H. Deng.  Boosting privately: Privacy-preserving federated extreme boosting for mobile crowdsensing.  Computing Research Repository, abs/1907.10218, 2019.
  * (28) Payman Mohassel and Yupeng Zhang.  SecureML: A system for scalable privacy-preserving machine learning.  In 38th IEEE Symposium on Security and Privacy, pages 19–38, 2017\.
  * (29) Valeria Nikolaenko, Udi Weinsberg, Stratis Ioannidis, Marc Joye, Dan Boneh, and Nina Taft.  Privacy-preserving ridge regression on hundreds of millions of records.  In 34th IEEE Symposium on Security and Privacy, pages 334–348, 2013\.
  * (30) Claudio Orlandi, Alessandro Piva, and Mauro Barni.  Oblivious neural network computing via homomorphic encryption.  EURASIP Journal on Information Security, 2007:Article ID 37343\.
  * (31) Pascal Paillier.  Public-key cryptosystems based on composite degree residuosity classes.  In 7th EUROCRYPT, volume 1592 of Lecture Notes in Computer Science, pages 223–238. Springer, 1999.
  * (32) Manoj Prabhakaran and Amit Sahai, editors.  Secure Multi-Party Computation, volume 10 of Cryptology and Information Security Series. IOS Press, 2013.
  * (33) Kaggle Competition Ranking.  https://www.kaggle.com/c/otto-group-product-classification-challenge/discussion/14335.
  * (34) M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, and Farinaz Koushanfar.  Chameleon: A hybrid secure computation framework for machine learning applications.  Computing Research Repository, abs/1801.03239, 2018.
  * (35) Bita Darvish Rouhani, M. Sadegh Riazi, and Farinaz Koushanfar.  Deepsecure: Scalable provably-secure deep learning.  Computing Research Repository, abs/1705.08963, 2017.
  * (36) Ahmad-Reza Sadeghi and Thomas Schneider.  Generalized universal circuits for secure evaluation of private functions with application to data classification.  In 11th International Conference on Information Security and Cryptology, pages 336–353, 2008.
  * (37) Ashish P. Sanil, Alan F. Karr, Xiaodong Lin, and Jerome P. Reiter.  Privacy preserving regression modelling via distributed computation.  In 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 677–682, 2004.
  * (38) Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In 38th IEEE Symposium on Security and Privacy, pages 3–18, 2017\.
  * (39) Jaideep Vaidya, Hwanjo Yu, and Xiaoqian Jiang.  Privacy-preserving SVM classification.  Knowledge and Information Systems, 14(2):161–178, 2008.

##  Appendix A System Architecture

As mentioned in the paper, we deploy ${\mathsf{PPXGBoost}}$ using AWS
infrastructure. We set up an Amazon VPC environment for deploying the
inference prototype. Amazon VPC environment allows the model provider to have
a logically isolated section of the AWS Cloud, therefore; the
${\mathsf{PPXGBoost}}$ provider can have complete control over the virtual
networking environment. The ${\mathsf{Proxy}}$ service is deployed in a
trusted environment, similarly to Amazon’s Key Management Services (KMS). The
ML module is run on the Amazon SageMaker platform, a fully managed machine
learning service. The security of SageMaker its own relies on the traditional
AWS’s security model 555see
https://docs.aws.amazon.com/sagemaker/latest/dg/data-protection.html,
including AWS Identity and Access Management (IAM), Amazon Macie, etc.

Figure 2: System architecture

Amazon SageMaker makes extensive use of Docker containers for build and
runtime tasks. After the ${\mathsf{Proxy}}$ produces an encrypted model
${\mathsf{EncML}}$, we store ${\mathsf{EncML}}$ to an S3 bucket (with proper
permission configuration). We package our inference algorithm using Amazon’s
container service, Amazon ECS. When deploying the ML inference module, we
upload the inference package in Amazon’s Elastic Container Repository and
specify the encrypted model location in S3. We create an endpoint for this
SageMaker instance to handle the encrypted queries. After the client receives
a private key, the client can send an encrypted query by querying a SageMaker
endpoint. The ML module computes the encrypted query and returns an encrypted
result to the client.

##  Appendix B Privacy Definitions and Proof

At a high level, the security guarantee we require from privacy-preserving
inference scheme is that: $(1)$ given an encrypted ML model, no adversary can
learn any information about the model; and $(2)$ given the view of a
polynomial number of ${\mathsf{Query}}$ executions for an adaptively generated
sequence of queries $\mathbf{q}=(q_{1},\ldots,q_{n})$, no adversary can learn
any partial information about either the model or $\mathbf{q}$.

Such a security notion can be difficult to achieve efficiently, so often one
allows for some form of leakage. Following [10, 8], this is usually formalized
by parameterizing the security definition with leakage functions for each
operation of the scheme which in this case include the ${\mathsf{Setup}}$
algorithm and ${\mathsf{Query}}$ protocol.

###  B.1 Security definition

In our description of what it means for
${\mathsf{PPXGBoost}}=({\mathsf{Setup}},{\mathsf{Query}})$ to be secure,
$\mathcal{A}$ is a semi-honest adversary, $\mathcal{S}$ is a simulator,
$\mathcal{L}_{\mathsf{Setup}}$ and $\mathcal{L}_{\mathsf{Query}}$ are the
leakage functions, and $\sigma$ and $\sigma_{i-1}$ are as defined above. The
terms Ideal and Real are used as they are in the literature on searchable
encryption [10].

Let $\Omega$ and $\alpha$ be an ${\mathsf{XGBoost}}$ model and hyper-parameter
chosen by $\mathcal{A}$. Let $v$ be a polynomially bounded function of $k$. We
consider the following two randomized experiments.

$\mathbf{Real}(\Omega,1^{k},\alpha)$:

  * •

Run the ${\mathsf{Setup}}$ protocol: $(\sf
K,{\mathsf{EncML}})\leftarrow{\mathsf{Setup}}(Omega,1^{k},\alpha)$

  * •

Execute the ${\mathsf{Query}}$ protocol $m=v(k)$ times. In these executions,
Client (adaptively) chooses queries as well as performing its role in Figure
1; it chooses $q_{1}$ uniformly at random.

  * •

Output the sequence $\sigma=(q_{1}^{\prime},r_{1}^{\prime})$,
$(q_{2}^{\prime},r_{2}^{\prime})$, $\ldots$, $(q_{m}^{\prime},r_{m}^{\prime})$
of encrypted queries and results.

$\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\mathcal{L}_{\mathsf{Setup}}(\Omega),1^{k},\alpha)$:

  * •

Given $\mathcal{L}_{\mathsf{Setup}}(\Omega)$, $1^{k}$, and $\alpha$,
$\mathcal{S}$ generates an encrypted model ${\mathsf{EncML}}$ and sends it to
$\mathcal{A}$.

  * •

$\mathcal{A}$ and $\mathcal{S}$ conduct $m=v(k)$ executions of the
${\mathsf{Query}}$ protocol, in which $\mathcal{S}$ plays the role of Client
by (adaptively) constructing a sequence $(q_{1},\ldots,q_{m})$ of queries, and
$\mathcal{A}$ plays the role of the ML module. $\mathcal{S}$ generates $q_{1}$
uniformly at random and uses
$\mathcal{L}_{\mathsf{Query}}(\Omega,\sigma_{i-1})$ to generate $q_{i}$,
$2\leq i\leq m$.

  * •

Output the sequence $\sigma=(q_{1}^{\prime},r_{1}^{\prime})$,
$(q_{2}^{\prime},r_{2}^{\prime})$, $\ldots$, $(q_{m}^{\prime},r_{m}^{\prime})$
of encrypted queries and results.

The gist of our security definition is that a PPT observer cannot distinguish
between outputs of the $\mathbf{Real}$ experiment, which runs the protocol in
Figure 1, and the $\mathbf{Ideal}$ experiment, in which a simulator that knows
the values of the leakage functions plays the role of the client and the
adversary plays the role of the ML module. A distinguisher $\mathcal{D}$ is an
algorithm that plays a refereed game with the adversary. In each round of the
game, the referee obtains $\Omega$ and $\alpha$ from $\mathcal{A}$, runs
either $\mathbf{Real}(\Omega,1^{k},\alpha)$ or
$\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\mathcal{L}_{\mathsf{Setup}}(\Omega),1^{k},\alpha)$,
and shows the output of whichever experiment is run to the distinguisher.

Let $w$ be a polynomially bounded function of $k$. The entire distinguishing
game proceeds as follows. Fix a security parameter $k$. For $w(k)$ rounds,
$\mathcal{D}$ may ask the referee to run either
$\mathbf{Real}(\Omega,1^{k},\alpha)$ or
$\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\mathcal{L}_{\mathsf{Setup}}(\Omega),1^{k},\alpha)$
and show him the output. The referee then chooses $b\in\\{0,1\\}$ uniformly at
random; if $b=0$, it runs $\mathbf{Real}(\Omega,1^{k},\alpha)$, and, if $b=1$,
it runs
$\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\mathcal{L}_{\mathsf{Setup}}(\Omega),1^{k},\alpha)$.
It shows the output to $\mathcal{D}$, and $\mathcal{D}$ outputs its best guess
$b^{\prime}$ of the value of $b$. The distinguisher’s advantage in this game,
which is a function of the security parameter $k$, is
$|\Pr\left[b=b^{\prime}\right]-\frac{1}{2}|$.

######  Definition B.1.

We say that ${\mathsf{PPXGBoost}}$ is adaptively
$(\mathcal{L}_{\mathsf{Setup}},\mathcal{L}_{\mathsf{Query}})$-semantically
secure if, for every PPT adversary $\mathcal{A}$, there exists a PPT simulator
$\mathcal{S}$ for which every PPT distinguisher’s advantage is negligible in
$k$.

###  B.2 Leakage profile

We now describe the leakage functions that specify, in the sense of [10, 8],
the information that ${\mathsf{PPXGBoost}}$ is willing to leak for the sake of
efficiency.

Setup leakage. Recall that the ${\mathsf{Setup}}$ phase of
${\mathsf{PPXGBoost}}$ takes as one of its inputs a plaintext model $\Omega$
and gives as one of the outputs an encrypted model. The plaintext model
consists of a set of CARTs. Setup leakage in ${\mathsf{PPXGBoost}}$ is a
function $\mathcal{L}_{\mathsf{Setup}}(\Omega)$ of the plaintext model; it
consists of the number of CARTs in $\Omega$, the depth of each CART, and, for
each internal node $w$ in each CART, which of $w$’s two children has the
smaller value. Note that the numerical values of the nodes are not leaked;
this is true of both internal nodes and leaves. In the high-level descriptions
of ${\mathsf{Setup}}$ given in Section 2 and Figure 1, the entire structure of
each CART is leaked, but, in practice, it is straightforward to pad each CART
out to a complete binary tree of the appropriate depth without changing the
results of the computation.

Query leakage. During the ${\mathsf{Query}}$ phase of ${\mathsf{PPXGBoost}}$,
the client and ML module exchange a sequence
$\sigma=(q_{1}^{\prime},r_{1}^{\prime})$, $(q_{2}^{\prime},r_{2}^{\prime})$,
$\ldots$, $(q_{n}^{\prime},r_{n}^{\prime})$ of encrypted queries and encrypted
results. Query leakage in ${\mathsf{PPXGBoost}}$ is a function
$\mathcal{L}_{\mathsf{Query}}(\Omega,\sigma)$ of the plaintext model and this
sequence. It consists of a query pattern and the set of paths that are
traversed during the execution of the encrypted queries. For every encrypted
query $q^{\prime}$ in $\sigma$, this phase of ${\mathsf{PPXGBoost}}$ leaks the
number of times it appears in $\sigma$ and where it appears; that is, for
every $q^{\prime}$, the query phase reveals the set of $i$, $1\leq i\leq n$,
such that $q_{i}^{\prime}=q^{\prime}$. In addition, for each $q_{i}^{\prime}$
and each encrypted CART, the path from the root to a leaf in that CART that is
traversed during the evaluation of $q_{i}^{\prime}$ is leaked to the ML module
and to any party that can observe the inner workings of this module while
queries are executed. Note that the query pattern and set of paths is well
defined for each prefix $\sigma_{i}$ of $\sigma$. Crucially, the decryptions
of the queries and results are not leaked.

###  B.3 Main idea and interpretation of the security proof

To prove that the only information leaked by ${\mathsf{PPXGBoost}}$ is
$\mathcal{L}_{\mathsf{Setup}}$ and $\mathcal{L}_{\mathsf{Query}}$, we present
a PPT algorithm that is given $1^{k}$, $\alpha$,
$\mathcal{L}_{\mathsf{Setup}}(\Omega)$, and
$\mathcal{L}_{\mathsf{Query}}(\Omega,\sigma)$ as input and simulates the
behavior of ${\mathsf{PPXGBoost}}$’s ${\mathsf{Setup}}$ and ${\mathsf{Query}}$
phases. We provide the main idea of the security proof here and defer the full
proof to an expanded version of this paper.

Given $\mathcal{L}_{\mathsf{Setup}}(\Omega)$, a simulator $\mathcal{S}$ can
construct a set $\\{\mathbf{T}_{i}\\}$ of CARTs with the required ordering of
internal nodes by sampling random values from the co-domain of OPE. For the
leaves, $\mathcal{S}$ assigns values chosen at random from the co-domain of
SHE. Given $\mathcal{L}_{\mathsf{Query}}(\Omega,\sigma)$, $\mathcal{S}$
follows, for each encrypted query, the appropriate paths in each $T_{i}$ that
it constructed and returns the leaf value. The security properties of the OPE
and SHE schemes ensure that the final predications are not revealed.

##  Appendix C Related work

Practical attacks on supervised learning systems that result in leakage of
sensitive information about training datasets, models, or hyper-parameters can
be found in, e.g. [14, 21, 38]. Among proposals to mitigate those attacks, the
majority focus on classification models, including decision trees [25], SVM
classification [39], linear regression [11, 12, 37], logistic regression [13],
and neural networks [30, 2, 36]. Recently, a fast-growing number of works
(e.g., [5, 29, 15, 18, 1, 6, 34, 35, 26, 7, 20, 17, 28, 24, 22]) have achieved
strong security guarantees in this setting by providing concrete security
definitions and provably secure protocols that use multiple cryptographic-
computation techniques [32]. Another research thread has focused on privacy-
preserving federated learning (see, e.g., [4]), in which multiple mobile users
update a global model by sharing aggregated updates to model parameters using
a privacy-preserving, client-server protocol. Recently, Liu et al. [27]
proposed a privacy-preserving boosting method for training
${\mathsf{XGBoost}}$ models in the federated-learning setting.


11institutetext: University of Mannheim, Germany
Data and Web Science Group
11email: ahmad.altaweel<EMAIL_ADDRESS>
# Towards Exploiting Implicit Human Feedback for Improving RDF2vec
Embeddings††thanks: Copyright © 2020 for this paper by its authors. Use
permitted under Creative Commons License Attribution 4.0 International (CC BY
4.0).

Ahmad Al Taweel  Heiko Paulheim

###### Abstract

RDF2vec is a technique for creating vector space embeddings from an RDF
knowledge graph, i.e., representing each entity in the graph as a vector. It
first creates sequences of nodes by performing random walks on the graph. In a
second step, those sequences are processed by the word2vec algorithm for
creating the actual embeddings. In this paper, we explore the use of external
edge weights for guiding the random walks. As edge weights, transition
probabilities between pages in Wikipedia are used as a proxy for the human
feedback for the importance of an edge. We show that in some scenarios,
RDF2vec utilizing those transition probabilities can outperform both RDF2vec
based on random walks as well as the usage of graph internal edge weights.

###### Keywords:

RDFvec Random Walks Edge Weights Knowledge Graph Embedding Human Feedback

##  1 Introduction

RDFvec [18] was originally conceived for exploiting Semantic Web knowledge
graphs in data mining. Since most popular data mining tools require a feature
vector representation of records, various techniques have been proposed for
creating vector space representations from subgraphs, including
straightforward techniques like adding features for datatype properties or
binary dimensions for types, [17], as well as techniques based on graph
kernels [9, 21].

Given the increasing popularity of the word2vec family of word embedding
techniques [11], which learns feature vectors for words based on the context
in which they appear, this approach has been proposed to be transferred to
graphs as well. Since word2vec operates on (word) sequences, several
approaches have been proposed which first turn a graph into sequences by
performing random walks, and then applying the idea of word2vec to those
sequences. Such approaches include node2vec [5], DeepWalk [14], Wembedder
[12], and the aforementioned RDF2vec.

While random walks are a straightforward technique for transforming a graph
into sequences, they lack a notion of importance of edges, and assign each
edge in the graph – be it important or not – the same weight. This observation
has lead to the inspection of various biases in the walk generation, e.g.,
preferring edges to nodes with a high or low PageRank [4]. However, the
results using those graph-internal biases were not very conclusive so far.

In this paper, we present an initial set of experiments which, instead of
generating a bias signal from data which is _internal_ to the graph (e.g., by
utilizing PageRank), uses _external_ data for assigning weights to edges. More
specifically, we utilize transition probabilities between Wikipedia pages,
created from user logs in Wikipedia, as a proxy for the importance of an edge
in a knowledge graph derived from Wikipedia, i.e., DBpedia.

The rest of this paper is structured as follows. In section 2, we discuss some
relevant related work. In section 3, we introduce the approach and data used.
We present some initial experimental findings in section 4. In section 5, we
discuss the results and their possible impact on applications, as well as how
they can be generalized to other datasets and embedding methods.

##  2 Related Work

The generation of knowledge graph embeddings is a highly active and vibrant
field, with many new approaches being proposed at a very high pace [22].
Despite the high number of approaches that have been proposed, little light
has been shed on assigning a weight or importance measure to edges when
constructing the embedding space.

One such approach is the extension of RDF2vec already discussed [4] above,
which replaces _random_ by _biased_ walks, where the bias comes from property
frequencies or PageRank of target nodes.

In [10], an information theoretic approach is taken to assign weights to
edges. The authors argue that the importance of an edge in the graph can be
determined by the likelihood that it can be reconstructed by inference. The
more easily it gets reconstructed, the more redundant it is. Consequently, the
authors propose an extension of translational embeddings which focus more on
the less redundant edges.

Both approaches use _graph-internal_ sources to generate the weights, i.e.,
the weights are derived directly from the graph without any additional use of
external data. In contrast, we propose an approach for using external data for
deriving such weights, thereby adding a truly fresh signal to the embedding
approach.

##  3 Approach

Our approach is a direct extension of RDF2vec. As discussed above, RDF2vec
uses random walks to generate sequences of nodes and edges, and then applies
word2vec on top of those sequences for generating feature vectors. Both
variants of word2vec – CBOW and SkipGram111CBOW (Context Bag of Words) tries
to predict a token in a sequence given its surrounding tokens, while SkipGram
tries the opposite, i.e., predicting the surroundings of a token in a sequence
given that token. – have been implemented for RDF2vec, with the latter often
showing superior results [19].

In [4], edge weights have been introduced as an extension to RDF2vec. The
adaptation of the RDF2vec is shown in Algorithm 1. When generating weighted
random walks, the next edge to follow is selected in the function _selectEdge_
(line 11) using a probability distribution computed from the edge weights of
all connecting edges of a node, i.e., the probability of each edge $e_{ij}$
from node _i_ to node _j_ being followed is the weight of that edge, divided
by the sum of the weights of all outgoing edges of _i_ :

$Pr\left[e_{ij}\right]=\frac{weight(e_{ij})}{\sum_{e_{ik}}weight(e_{ik})}$ (1)

Note that the classic RDF2vec implementation of RDF2vec is equivalent to using
uniform weights, i.e., all weights being set to 1.

Data: $G=(V,E)$: RDF Graph, $d$: walk depth, $n$: number of walks

Result: $P_{G}$: Set of sequences

1 $P_{G}$ := $\emptyset$

2 foreach  _vertex $v\in V$_ do

3 $n_{v}$ = n

4 while  _$n_{v}$ $>$ 0_ do

5 $w$ = initialize walk

6 add $v$ to $w$

7 $currentVertex$ = $v$

8 $d_{v}$ = $d$

9 while  _$d_{v}$ $>$ 0_ do

10 $E_{c}$ = $currentVertex.outEdges()$

11 $e$ = selectEdge($E_{c}$)

12 $d_{v}$ = $d_{v}$ \- 1

13 add $e$ to $w$

14 if  _$d_{v}$ $>$ 0_ then

15 $v_{e}$ = $e.endVertex()$

16 add $v_{e}$ to $w$

17 $currentVertex$ = $v_{e}$

18 $d_{v}$ = $d_{v}$ \- 1

19

20 end if

21

22 end while

23 add $w$ to $P_{G}$

24 $n_{v}$ = $n_{v}$ \- 1

25

26 end while

27

28 end foreach

Algorithm 1 Algorithm for generating weighted RDF graph walks [19]

In this paper, we generate RDF2vec embeddings for DBpedia [2], a knowledge
graph extracted from Wikipedia. In DBpedia, each entity corresponds to a
Wikipedia page. Hence, we can utilize information generated for Wikipedia also
for computations on DBpedia.

For assigning weights to edges, we collect implicit human feedback. To that
end, we utilize transition likelihoods in user navigation, generated from
Wikipedia’s usage
logs222https://meta.wikimedia.org/wiki/Research:Wikipedia_clickstream. Those
represent the number of link transitions (i.e., clicks) from a Wikipedia page
to another one. This transitional probability is used as implicit user
feedback, serving as a proxy for a human rating for the importance of an edge
in the knowledge graph.

Figure 1: Clickstream data example, showing the top 10 click sources and
targets for the Wikipedia page for London. Source:
https://meta.wikimedia.org/wiki/Research:Wikipedia_clickstream

Figure 1 shows an example excerpt of the clickstream data for the Wikipedia
page London. On the left hand side, the top pages from which a user gets to
the Wikipedia page for London are depicted: the top five are Google and Bing,
as well as other Web pages, the most likely Wikipedia pages are United
Kingdom, main Page, Europe, England, and City of London. On the right hand
side, the top 10 pages to which a user navigates from the London pages are
depicted. Each transition has a probability, indicated by the strength of the
connecting line.

Note that not every link in Wikipedia corresponds to a statement in DBpedia;
numbers not referring to Wikipedia pages (e.g., links from/to non-Wikipedia
pages) are ignored in the formula above generating the random walks. This
means that the transition probabilities are normalized so that the sum of
probabilities of a transition from one Wikipedia page to all Wikipedia pages
linked from this page is $1$. Fig. 2 shows an excerpt of DBpedia, with weights
extracted from the Wikipedia Clickstream dataset. In this case, the sequence

    Pretty_Hate_Machine artist Nine_Inch_Nails bandMember Trent_Reznor

would have a much higher probability to be generated than the sequence

    Bad_Witch artist Nine_Inch_Nails genre Industrial_Rock

Figure 2: Excerpt from DBpedia, using transition likelihoods from the
Clickstream dataset

##  4 Experiments

For evaluating the impact of weights in the RDF2vec embeddings, we conduct two
series of experiments. First, we follow the setup in [13], solving a couple of
entity classification and regression tasks based on a set of benchmarks for
machine learning on the semantic web [16]. For those datasets, three sets of
entities – cities, movies, and albums – have been augmented with an external
variable to be predicted, i.e., the quality of living index for cities, and
the metacritic score for movies and albums.

Second, we perform a set of experiments with a content-based recommender
system based on RDF2vec embeddings [19]. Here, we use a variant of the
MovieLens dataset, which collects user ratings for movies, which has been
linked to DBpedia.

In both sets of experiments, we compare the results achieved using our
weighted RDF2vec embeddings generated on DBpedia against the standard
implementation of RDF2vec, as well as the three best performing variants using
graph internal weighting schemes, as reported in [4], i.e.,

Predicate Frequency

uses the global frequency of a predicate as an edge weight. Consequently,
edges with frequent properties are followed more frequently than edges with
infrequent properties.

PageRank

uses the PageRank of the target node of an edge as the edge weight. Hence,
nodes which are more central in the graph are more likely to be part of walks.

Inverse PageRank

does the opposite, as it uses the inverse of the PageRank of an object as the
edge weight. Here, walks are more likely to contain nodes which are less
central in the graph.

In particular, the latter two strategies are very different: PageRank creates
walks which mainly contain central nodes, i.e., it creates a very uneven
distribution reflecting the popularity of nodes, whereas inverse PageRank
tries to favor less central nodes and create a more even distribution in which
central nodes are not treated with preference, i.e., long tail entities are
covered better.

The code used for the experiments, including all the variants that were
considered for comparison, is available
online.333https://github.com/ataweel55/RDF2VEC

Table 1: Classification results (accuracy) Strategy/Dataset | Cities | Metacritic Movies | Metacritic Albums
---|---|---|---
NB | KNN | SVM | C4.5 | NB | KNN | SVM | C4.5 | NB | KNN | SVM | C4.5
Uniform SG 200w 200v 4d | 73.25 | 72.90 | 76.32 | 50.26 | 72.29 | 75.81 | 75.94 | 67.28 | 71.46 | 72.87 | 68.66 | 63.45
Uniform SG 500w 200v 4d | 59.25 | 67.51 | 73.01 | 61.27 | 65.25 | 79.62 | 81.19 | 74.52 | 69.25 | 72.85 | 75.80 | 64.92
Uniform SG 500w 200v 8d | 71.65 | 75.52 | 72.82 | 59.48 | 76.41 | 72.35 | 83.51 | 76.83 | 76.36 | 75.96 | 81.72 | 67.25
Uniform SG 500w 500v 8d | 87.63 | 70.15 | 82.70 | 68.72 | 81.35 | 76.24 | 83.35 | 71.52 | 75.64 | 75.92 | 78.63 | 67.18
Predicate frequency weight SG 200w 200v 4d | 72.15 | 70.77 | 73.37 | 51.25 | 74.60 | 75.21 | 76.13 | 72.42 | 69.82 | 71.90 | 73.53 | 62.22
Page-Rank weight SG 200w 200v 4d | 74.16 | 72.73 | 67.21 | 62.83 | 71.32 | 69.19 | 79.70 | 74.43 | 69.61 | 71.98 | 74.47 | 68.11
Inverse Page-Rank Weight SG 200w 200v 4d | 73.98 | 69.37 | 74.60 | 57.38 | 68.68 | 71.25 | 72.71 | 64.93 | 67.39 | 73.57 | 64.27 | 58.66
Click-Stream weight CBOW 200w 200v 4d | 60.25 | 64.90 | 74.32 | 65.26 | 67.29 | 75.81 | 77.94 | 69.20 | 71.15 | 72.38 | 74.47 | 63.48
Click-Stream weight SG 200w 200v 4d | 74.68 | 71.20 | 77.94 | 53.45 | 71.11 | 77.31 | 79.52 | 67.78 | 70.46 | 72.20 | 67.18 | 62.88
Click-Stream weight SG 500w 200v 4d | 61.22 | 73.90 | 78.39 | 62.45 | 65.14 | 80.49 | 81.44 | 79.65 | 71.19 | 69.78 | 74.15 | 69.37
Click-Stream weight SG 500w 500v 8d | 88.63 | 69.70 | 81.62 | 71.93 | 82.44 | 74.69 | 82.27 | 69.12 | 77.63 | 72.84 | 79.48 | 66.81
Table 2: Regression results (Root Mean Squared Error) Strategy/Dataset | Cities | Metacritic Movies | Metacritic Albums
---|---|---|---
LR | KNN | M5 | LR | KNN | M5 | LR | KNN | M5
Uniform SG 200w 200v 4d | 16.64 | 15.92 | 16.87 | 17.16 | 19.33 | 17.79 | 12.38 | 14.42 | 12.97
Uniform SG 500w 200v 4d | 14.74 | 12.78 | 14.52 | 16.95 | 18.62 | 17.28 | 13.56 | 14.33 | 13.65
Uniform SG 500w 200v 8d | 13.68 | 14.93 | 13.45 | 16.79 | 18.40 | 16.97 | 13.17 | 14.36 | 13.22
Uniform SG 500w 500v 8d | 12.23 | 13.81 | 10.86 | 16.42 | 18.03 | 16.68 | 12.48 | 13.63 | 11.96
Predicate frequency weight SG 200w 200v 4d | 16.54 | 17.83 | 17.56 | 18.28 | 20.90 | 19.72 | 14.31 | 16.88 | 13.44
Page-Rank weight SG 200w 200v 4d | 14.74 | 14.57 | 16.14 | 17.63 | 20.81 | 16.86 | 12.57 | 15.72 | 12.56
Inverse Page-Rank weight SG 200w 200v 4d | 14.87 | 16.59 | 14.93 | 16.10 | 18.44 | 16.16 | 11.56 | 12.93 | 11.51
Click-Stream weight CBOW 200w 200v 4d | 15.13 | 13.64 | 16.13 | 19.76 | 20.91 | 19.48 | 13.52 | 14.29 | 13.58
Click-Stream weight SG 200w 200v 4d | 15.48 | 16.16 | 15.24 | 17.31 | 19.27 | 16.78 | 12.28 | 13.75 | 12.21
Click-Stream weight SG 500w 200v 4d | 13.96 | 16.53 | 14.82 | 15.66 | 16.15 | 15.86 | 11.70 | 12.50 | 11.77
Click-Stream weight SG 500w 500v 8d | 12.25 | 12.57 | 10.11 | 15.72 | 16.89 | 15.80 | 10.79 | 11.67 | 11.14

###  4.1 Results on Machine Learning Benchmark Datasets

In the three benchmark datasets used, the goal is to predict the quality of
living in cities, and the metacritic score of movies and albums. For
classification, those are discretized (into high and low), for regression, the
goal is to predict the actual number. In those experiments, we follow the
setup in the original RDF2vec paper [18], utilizing four standard out of the
box classification algorithms (Naive Bayes, nearest neighbors, Support Vector
Machines, and C4.5 decision trees) and three regression algorithms (linear
regression, nearest neighbors, and M5 regression trees).444We are aware that
there might be better performing state of the art algorithms, e.g., deep
neural networks or XGboost. However, for our goal of comparing different
RDF2vec variants, we tried to follow the original evaluation protocol of
RDF2vec as closely as possible.

Tables 1 and 2 depict the results for the classification and regression tasks.
It can be observed that for the classification tasks, the embeddings
incorporating clickstream data outperform the default RDF2vec embeddings in
one out of three tasks, while for the regression, they outperform those in all
three cases. Moreover, we can observe that the embeddings utilizing the
external signal for the weighting schemes are superior to all three techniques
utilizing graph internal signals.

###  4.2 Results on Recommendation Datasets

In this experiment, we use the RDF2vec graph embedding method in the framework
of content-based recommender systems for feature generation and rely on a
comparatively easy suggestion algorithm, i.e., the items are recommended using
the K-Nearest Neighbors technique with cosine similarity in the RDF2vec
embedding space. Formally, this technique evaluates the proximity of objects
by means of cosine similarity between the respective RDF2vec vectors and then
selects a subset of those – the neighbors – for each object, which will be
used to predict the user u a rating for a fresh item I as follows:

$r^{*}\left(u,i\right)=\frac{\sum_{j\in
ratedItems\left(u\right)}cosineSim(j,i).r_{u,j})}{\sum_{j\in
ratedItems\left(u\right)}|cosineSim(j,i)|}$ (2)

Where $ratedItems(u)$ is a collection of products already assessed by the user
$u,r_{u,j}$ suggests the user $u$ use $j$ rating and $cosineSim(j,i)$ shows
the cosine similarity score between $j$ and $i$ products. The size of the
considered neighborhood is restricted to 5 in our experiments.

Table 3: Results of the ItemKNN approach on Movielens dataset  Strategy | Precision | Recall | F1
---|---|---|---
Uniform SG 200w 200v 4d | 0.05128 | 0.02466 | 0.03330
Uniform SG 500w 200v 4d | 0.04852 | 0.03024 | 0.03725
Uniform SG 500w 200v 8d | 0.04279 | 0.02612 | 0.03243
Uniform SG 500w 500v 8d | 0.02692 | 0.01624 | 0.02025
Predicate frequency weight SG 200w 200v 4d | 0.01946 | 0.0960 | 0.03236
Page-Rank weight SG 200w 200v 4d | 0.03251 | 0.01828 | 0.02340
Inverse Page-Rank weight SG 200w 200v 4d | 0.03924 | 0.02369 | 0.02954
Click-Stream weight CBOW 200w 200v 4d | 0.03162 | 0.01348 | 0.01890
Click-Stream weight SG 200w 200v 4d | 0.05261 | 0.03625 | 0.04292
Click-Stream weight SG 500w 200v 4d | 0.04622 | 0.02573 | 0.03305
Click-Stream weight SG 500w 500v 8d | 0.02489 | 0.01925 | 0.02170

Table 3 depicts the results of the recommender system experiments. It can be
observed that the results incorporating human feedback outperform both the
default RDF2vec approach as well as the three variants using graph-internal
weights.

##  5 Conclusion and Outlook

In this paper, we have introduced an approach for incorporating an external
signal – in our case: page transition probabilities in Wikipedia – for
creating knowledge graph embeddings. We have shown that the performance of
RDF2vec models can be increased by exploiting such a signal for edge weights.

So far, we have carried out experiments on DBpedia, and used edge weights
derived from Wikipedia. The same technique would be applicable for knowledge
graphs based on Wikipedia, such as YAGO [20] and CaLiGraph [6], as well as
knowledge graphs based on other Wikis [7] for which log files are available.
For other knowlede graphs and datasets, other methods of obtaining edge
weights need to be investigated. Moreover, for Wikipedia-based knowledge
graphs, other measures of weights than interaction histories might be feasible
(e.g., assessing the importance of a link based on the text of a Wikipedia
page, or analyzing the edit history of a page to find out how early the link
to the other page was added).

RDF2vec is not the only knowledge graph embedding technique in which edge
weights can be exploited. In [10], the authors argue that translational
embedding techniques such as TransE [3] and its descendants can also be
adapted in a way that they use edge weights. So far, this has only done by
using graph internal weights. Hence, given our observations that external
weights work better for RDF2vec than graph internal weights, we want to
investigate the usage of graph external weights in such embedding techniques
as well.

Since RDF2vec has been used in quite a few downstream applications, we want to
investigate the effect of graph external edge weights in such application as
well. Besides recommender systems, possible fields are the use of RDF2vec for
ontology alignment [15], for analyzing changes in ontologies [8], or
reconciling information extracted from different texts [1]. Moreover, given a
specific task, it would be interesting to investigate to which extent task-
specific weighting schemes might be utilized.

## References

  * [1] Alam, M., Recupero, D.R., Mongiovi, M., Gangemi, A., Ristoski, P.: Reconciling event-based knowledge through rdf2vec. In: HybridSemStats@ ISWC (2017)
  * [2] Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., Ives, Z.: Dbpedia: A nucleus for a web of open data. In: The semantic web, pp. 722–735. Springer (2007)
  * [3] Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., Yakhnenko, O.: Translating embeddings for modeling multi-relational data. In: Advances in neural information processing systems. pp. 2787–2795 (2013)
  * [4] Cochez, M., Ristoski, P., Ponzetto, S.P., Paulheim, H.: Biased graph walks for rdf graph embeddings. In: Proceedings of the 7th International Conference on Web Intelligence, Mining and Semantics. pp. 1–12 (2017)
  * [5] Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 855–864 (2016)
  * [6] Heist, N., Paulheim, H.: Uncovering the semantics of wikipedia categories. In: International semantic web conference. pp. 219–236. Springer (2019)
  * [7] Hertling, S., Paulheim, H.: Dbkwik: A consolidated knowledge graph from thousands of wikis. In: 2018 IEEE International Conference on Big Knowledge (ICBK). pp. 17–24. IEEE (2018)
  * [8] Jurisch, M., Igler, B.: Rdf2vec-based classification of ontology alignment changes. arXiv preprint arXiv:1805.09145 (2018)
  * [9] Lösch, U., Bloehdorn, S., Rettinger, A.: Graph kernels for rdf data. In: Extended Semantic Web Conference. pp. 134–148. Springer (2012)
  * [10] Mai, G., Janowicz, K., Yan, B.: Support and centrality: Learning weights for knowledge graph embedding models. In: European Knowledge Acquisition Workshop. pp. 212–227. Springer (2018)
  * [11] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013)
  * [12] Nielsen, F.Å.: Wembedder: Wikidata entity embedding web service. arXiv preprint arXiv:1710.04099 (2017)
  * [13] Pellegrino, M.A., Cochez, M., Garofalo, M., Ristoski, P.: A configurable evaluation framework for node embedding techniques. In: European Semantic Web Conference. pp. 156–160. Springer (2019)
  * [14] Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 701–710 (2014)
  * [15] Portisch, J., Paulheim, H.: Alod2vec matcher. OM@ ISWC 2288, 132–137 (2018)
  * [16] Ristoski, P., De Vries, G.K.D., Paulheim, H.: A collection of benchmark datasets for systematic evaluations of machine learning on the semantic web. In: International Semantic Web Conference. pp. 186–194. Springer (2016)
  * [17] Ristoski, P., Paulheim, H.: A comparison of propositionalization strategies for creating features from linked open data. Linked Data for Knowledge Discovery 6 (2014)
  * [18] Ristoski, P., Paulheim, H.: Rdf2vec: Rdf graph embeddings for data mining. In: International Semantic Web Conference. pp. 498–514. Springer (2016)
  * [19] Ristoski, P., Rosati, J., Di Noia, T., De Leone, R., Paulheim, H.: Rdf2vec: Rdf graph embeddings and their applications. Semantic Web 10(4), 721–752 (2019)
  * [20] Suchanek, F.M., Kasneci, G., Weikum, G.: Yago: A large ontology from wikipedia and wordnet. Journal of Web Semantics 6(3), 203–217 (2008)
  * [21] de Vries, G.K.: A fast approximation of the weisfeiler-lehman graph kernel for rdf data. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pp. 606–621. Springer (2013)
  * [22] Wang, Q., Mao, Z., Wang, B., Guo, L.: Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering 29(12), 2724–2743 (2017)