# data_poisoning_attack_against_knowledge_graph_embedding__2994aa1d.pdf

Data Poisoning Attack against Knowledge Graph Embedding

Hengtong Zhang1, Tianhang Zheng1, Jing Gao1, Chenglin Miao1, Lu Su1, Yaliang Li2, Kui Ren3

1SUNY at Buffalo, Buffalo, NY USA 2Alibaba Group, Bellevue, WA USA 3Zhejiang University, Zhejiang, China {hengtong, tzheng4, jing, cmiao, lusu}@buffalo.edu, yaliang.li@alibaba-inc.com, kuiren@zju.edu.cn

Knowledge graph embedding (KGE) is a technique for learning continuous embeddings for entities and relations in the knowledge graph. Due to its beneﬁt to a variety of downstream tasks such as knowledge graph completion, question answering and recommendation, KGE has gained signiﬁcant attention recently. Despite its effectiveness in a benign environment, KGE s robustness to adversarial attacks is not well-studied. Existing attack methods on graph data cannot be directly applied to attack the embeddings of knowledge graph due to its heterogeneity. To ﬁll this gap, we propose a collection of data poisoning attack strategies, which can effectively manipulate the plausibility of arbitrary targeted facts in a knowledge graph by adding or deleting facts on the graph. The effectiveness and efﬁciency of the proposed attack strategies are veriﬁed by extensive evaluations on two widely-used benchmarks.

1 Introduction

Knowledge graphs have become a critical resource for a large collection of real world applications, such as information extraction [Mintz et al., 2009], question answering [Yih et al., 2015] and recommendation system [Zhang et al., 2016]. Due to its wide application domains, both academia and industry have spent considerable efforts on constructing large-scale knowledge graphs, such as YAGO [Hoffart et al., 2013], Freebase [Bollacker et al., 2008], and Google Knowledge Graph1. In knowledge graphs, knowledge facts are usually stored as (head entity, relation, tail entity) triples. For instance, the fact triple (Albert Einstein, Profession, Scientist) means that Albert Einstein s profession is a scientist. Although such triples can effectively record abundant knowledge, their underlying symbolic nature makes them difﬁcult to be directly fed to many machine learning models. Hence, knowledge graph embedding (KGE), which projects the symbolic entities and relations into continuous vector space, has quickly gained signiﬁcant attention [Nickel et al., 2011; Lin et al., 2015; Bordes et al., 2013; Yang et al., 2014b;

1https://developers.google.com/knowledge-graph/

Trouillon et al., 2016]. These compact embeddings can preserve the inherent characteristics of entities and relations while enabling the use of these knowledge facts for a large variety of downstream tasks such as link prediction, question answering, and recommendation. Despite the increasing success and popularity of Knowledge graph embeddings, their robustness has not been fully analyzed. In fact, many knowledge graphs are built upon unreliable or even public data sources. For instance, the well known Freebase harvests its data from various sources including individual, user-submitted wiki contributions2. The openness of such data unfortunately would make KGE vulnerable to malicious attacks. When being attacked, substantial unreliable or even biased knowledge graph embeddings would be generated, leading to serious impairment and ﬁnancial loss of many downstream applications. For instance, a variety of recommendation algorithms (e.g., [Zhang et al., 2016; Wang et al., 2018]) utilize KGEs of products as external references. If KGEs are manipulated, the recommendation results will be biased. This phenomenon can largely hurt user experiences. Therefore, there is a strong need for the analysis of the vulnerability of knowledge graph embeddings. In this paper, for the ﬁrst time, we systemically investigate the vulnerability of KGE, through designing efﬁcient adversarial attack strategies. Due to the unique characteristics of knowledge graph and its embedding models, existing adversarial attack methods on graph data [Z ugner et al., 2018; Sun et al., 2018; Bojcheski and G unnemann, 2018] cannot be directly applied to attack KGE methods. First, they are all designed for homogeneous graphs, in which there is only a single type of nodes or links. However, in a knowledge graph, both the entities (nodes) and the relations (links) between entities are of different types. Second, existing attack methods for homogeneous graphs usually have strict requirements on the formulation of the targeted methods. For instance, the attack strategies proposed in [Sun et al., 2018; Bojcheski and G unnemann, 2018] can only work for the embedding methods that can be transformed into matrix factorization. However, the KGE methods are diverse and may not be able to be transformed into matrix factorization problems. In this paper, we introduce the ﬁrst study on the vulnerabil-

2https://www.nytimes.com/2007/03/09/technology/09data.html

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

ity of KGE and propose a family of effective data poisoning attack strategies against KGE methods. Our proposed attack strategies can guide the adversary to manipulate the training set of KGE by adding and/or deleting some speciﬁc facts to promote or degrade the plausibility of speciﬁc targeted facts, which can potentially inﬂuence a large variety of applications that utilize the knowledge graph. The proposed strategies include both direct scheme which directly manipulates the embeddings of entities involved in the targeted facts and indirect scheme which utilizes other entities as proxies to achieve the attack goal. Empirically, we perform poisoning attack experiments against three most representative KGE methods on two common KGE datasets (FB15K, WN18), and verify the effectiveness of the proposed adversarial attack. Results show that the proposed strategies can dramatically worsen the link prediction results of targeted facts with only a small amount of changes to the graph needed.

2 Related Work Knowledge Graph Embeddings. KGE as an emerging research topic has attracted tremendous interest. A large number of KGE models have been proposed to represent entities and relations in a knowledge graph with vectors or matrices. RESCAL [Nickel et al., 2011], which is based on bi-linear matrix factorization, is one of the earliest KGE models. Then [Bordes et al., 2013] introduces the ﬁrst translation-based KGE method Trans E. Given a fact (h, r, t), composed of a relation (r) and two entities (h and t) in the knowledge graph, Trans E learns vector representations of h, t, and r (i.e., h, t and r) by compelling h + r t. Later, a large collection of variants, such as Trans H [Wang et al., 2014], Trans R [Lin et al., 2015], Trans D [Ji et al., 2015] and Trans A [Xiao et al., 2015], extend Trans E by projecting the embedding vector into various spaces. On the other hand, Dist Mult [Yang et al., 2014a] simpliﬁes RESCAL by only using a diagonal matrix, and Com Plex [Trouillon et al., 2016] extends Dist Mult into the complex number ﬁeld. [Wang et al., 2017] provides a comprehensive survey on these models. The attack strategy proposed in this paper can be used to attack most of the existing KGE models. Data Poisoning Attack v.s. Evasion Attack. Data poisoning attacks, such as those in [Biggio et al., 2012; Steinhardt et al., 2017] are a family of adversarial attacks on machine learning methods. In these works, the attacker can access the training data of the learning algorithm, and has the power to manipulate a fraction of the training data in order to make the trained model meet certain desired objectives. Evasion attacks such a those in [Goodfellow et al., 2014; Kurakin et al., 2016] are another prevalent type of attack that may be encountered in adversarial settings. In the evasion setting, malicious samples are generated at test time to evade detection. In this paper, the proposed adversarial attack strategies against KGE methods can be categorized into the data poisoning attack setting. Adversarial Attacks on Graphs. There are limited existing works on adversarial attacks for graph learning tasks: node classiﬁcation [Z ugner et al., 2018; Dai et al., 2018], graph classiﬁcation [Dai et al., 2018], link prediction [Chen

et al., 2018] and node embedding [Sun et al., 2018; Bojcheski and G unnemann, 2018]. The ﬁrst work, introduced by [Z ugner et al., 2018] linearizes the graph convolutional network (GCN) [Kipf and Welling, 2016] to derive the closedform expression for the change in class probabilities for a given edge/feature perturbation and greedily pick the top perturbations that change the class probabilities. [Dai et al., 2018] proposes a reinforcement learning based approach where the attack agent interacts with the targeted graph/node classiﬁer to learn the policy of selecting the edge perturbations that fool the classiﬁer. [Chen et al., 2018] adopts the fast gradient sign scheme to perform evasion attack against the link prediction task with GCN. [Sun et al., 2018] and [Bojcheski and G unnemann, 2018] propose data poisoning attack against factorization-based embedding methods on homogeneous graphs. They both formulate the poisoning attack as bilevel optimization problems. The former exploits the eigenvalue perturbation theory [Stewart, 1990], while the latter directly adopts iterative gradient method [Carlini and Wagner, 2017] to solve the problem. To the best of our knowledge, there is no existing investigation on adversarial attack for heterogeneous graphs, in which the links and/or nodes are of different types, like knowledge graphs. This paper sheds ﬁrst light on this important problem that has not been studied yet.

3 Data Poisoning Attack against Knowledge Graph Embedding (KGE) Methods Let us consider a knowledge graph KG, with a training set denoted as {(eh n, rn, et n)}N n=1 and a targeted fact triple (eh,target x , rtarget x , et,target x ) that does not exist in the training set. The goal of the attacker is to manipulate the learned embeddings, which would degrade (or promote) the plausibility of (eh,target x , rtarget x , et,target x ) measured by a speciﬁc fact plausibility scoring function f. Without loss of generality, we focus on degrading the targeted fact. We also assume that the attacker has a limited attacking budget. In this paper, the attacking budget is the number of perturbations per target. Formally, the attack task is deﬁned as follows: Deﬁnition 1 (Problem Deﬁnition). Consider a targeted fact triple (eh,target x , rtarget x , et,target x ) that does not exist in the training set, we use eh,target x to denote the embedding of the head entity eh,target x , et,target x to denote the embedding of the tail entity et,target x and rtarget x to denote the embedding of the relation rtarget x from the original training set. Our task is to minimize the plausibility of (eh,target x , rtarget x , et,target x ), i.e., f(eh,target x , rtarget x , et,target x ), by making perturbations (i.e., adding/deleting facts) on the training set. We assume the attacker has a given, ﬁxed budget and is only capable of making M perturbations. Due to the discrete and combinatorial nature of the knowledge graph, solving this problem is highly challenging. Intuitively, in order to manipulate the plausibility of a speciﬁc targeted fact, we need to shift either the embedding vectors related to its entities or the embedding vectors/matrices related to its relations. However, in a knowledge graph, the number of facts that a relation type involves is much larger than the number of facts that an entity type involves. For instance, in the well-known knowledge graph Freebase, the number of

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

entities is over 30 million, while the number of relation types is only 1345. This leads to the fact that the innate characteristics of each relation type is far more stable than that of entities and is difﬁcult to be manipulated via a small number of modiﬁcations. Hence, in this paper, we focus on manipulating the plausibility of targeted facts from the perspective of entities. To achieve the attack goal, in the rest of this section, we propose a collection of effective yet efﬁcient attack strategies.

3.1 Direct Attack Given the uncontaminated knowledge graph, the goal of direct attack is to determine a collection of perturbations (i.e., fact adding/deleting actions) to shift the embeddings of the entities involved in the targeted fact to minimize the plausibility of the targeted fact. First, we determine the optimal shifting direction that the entity s embedding should move towards. Then we rank the possible perturbation actions by analyzing the training process of KGE models and designing scoring functions, which estimate the beneﬁt of a perturbation, i.e., how much shifting can be achieved by this perturbation along the desired direction. We name the score as perturbation beneﬁt score and calculate such score for every possible perturbation. Finally, we conduct the Top-M perturbations with highest perturbation beneﬁt scores, where M is the attack budget. Suppose we want to degrade the plausibility of the fact (eh,target x , rtarget x , et,target x ). For simplicity, let s focus on shifting the embedding of one of the entities in (eh,target x , rtarget x , et,target x ), say head entity eh,target x , from eh,target x to eh,target x + ϵ x, without loss of generality. Here, ϵ x denotes the embedding shifting vector. The fastest direction of decreasing f(eh,target x , rtarget x , et,target x ) is opposite to its partial derivative with respect to eh,target x . Let ϵh be the perturbation step size, the optimal embedding shifting vector is:

ϵ x = ϵh f(eh,target x , rtarget x , et,target x )

eh,target x . (1)

As mentioned in the problem deﬁnition, in order to shift eh,target x by ϵ x, the adversary is allowed to add perturbation facts to the knowledge graph or delete facts from the knowledge graph. Given the optimal embedding shifting vector ϵ x, we then ﬁnd a ranking of the all the perturbation (add or delete) candidates. We discuss the two schemes in detail as follows.

Direct Deleting Attack. Consider the uncontaminated training set, under the direct adversarial attack scheme, in order to shift the embedding of eh,target x to eh,target x + ϵ x, we need to select and delete one or more facts that directly involve entity eh,target x . Intuitively, the fact to delete should have a great inﬂuence on the embedding of eh,target x , while at the same time not hinder the process of shifting the embedding of eh,target x to eh,target x + ϵ x. To design a scoring criterion that captures these intuitions, let us look into the training process of KGE model. Consider the speciﬁc deletion candidate (eh,target x , ri, et i) that involves eh,target x . During training, the sum of the fact plausibility scores of the observed training samples is maximized. On one hand, the more plausi-

ble the fact (eh,target x , ri, et i) is, the more it contributes to the ﬁnal embedding of eh,target x . Hence, the perturbation beneﬁt score of deleting (eh,target x , ri, et i) should be proportional to f(eh,target x , ri, et i). On the other hand, if the plausibility of fact (eh,target x , ri, et i) is large after eh,target x is shifted to eh,target x +ϵ x (i.e., f(eh,target x +ϵ x, ri, et i) is large), it means that the fact (eh,target x , ri, et i) has a great positive impact on the embedding shifting and should not be deleted. Hence, the perturbation beneﬁt score of deleting (eh,target x , ri, et i) should be inversely proportional to f(eh,target x + ϵ x, ri, et i). Formally, let the set of all the delete candidates be: DD = {(eh i , ri, et i) | eh i = eh,target x and (eh i , ri, et i) KG}, which intuitively denote the set of facts that involve eh,target x as the head entity in the training set. The perturbation beneﬁt score of deleting a speciﬁc perturbation fact (eh,target x , ri, et i) can be estimated as:

η (eh,target x , ri, et i) =f(eh,target x , ri, et i)

λ1f(eh,target x + ϵ x, ri, et i), (2)

where eh,target x , ri, and et i denote the embeddings of eh,target x , ri and et i on the uncontaminated training set. Direct Adding Attack. Now we discuss how to conduct direct adding perturbation. To shift the embedding of exh,target by ϵ , we just need to add new facts that involve eh,target x to make f(eh,target x , rj, et j) less plausible. The set of all the possible adding candidates can be denoted as DA = {eh,target x } {(rj, et j) | rj KG and et j KG}, where {(rj, et j) | rj KG and et j KG} denotes all the possible relation-tail entity combinations in the knowledge graph and stands for Cartesian product. In practice, for better efﬁciency, we can downsample a subset from all the possible relation-tail entity combinations. Formally, the perturbation beneﬁt score of a speciﬁc candidate to add (i.e., (eh,target x , rj, et j)) can be estimated as:

η+(eh,target x , rj, et j) =λ2f(eh,target x + ϵ x, rj, et j)

λ3f(eh,target x , rj, et j), (3)

where eh,target x , rj, and et i denote the embeddings on the uncontaminated training set.

3.2 Indirect Attack Although the direct attack strategy is intuitive and effective, it is possible to be detected by data sanity check. In this section, we move on to introduce a more complicated yet more stealthy adversarial attack scheme, i.e., indirect attack. Suppose a KGE user want to query the plausibility of a potential fact (h, r, t). Due to the huge scales of real-world knowledge graphs, even in the most optimistic situation, we may merely carry data sanity test on the facts related to h and t. However, for indirect attack, instead of adding or deleting the facts that involve the entities in the targeted fact, we propose to perturb the facts that involve other entities in the knowledge graph and let the perturbation effect propagate to the targeted fact. Thus, detecting these perturbations requires data sanity tests on facts that involves every entity that are hops away from h and t. When the number of hops increases linearly, the data

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

sanity cost will have a exponential growth. Even though there is an Oracle that can ﬁnd these anomalous facts effectively, defenders cannot determine the targeted fact(s) of these perturbations. For a better description, we provide the following toy example, which is used throughout this section.

Example 1. Suppose we want to degrade the plausibility of the targeted fact (eh,target x , rtarget x , et,target x ) via shifting the embedding of the targeted entity eh,target x by ϵ x, without loss of generality. Under indirect attack scheme, we perturb the facts that involve the K-hop neighbors of eh,target x . These Khop neighbors are called proxy entities. Then the entities between the K-hop neighbors (proxy entities) and eh,target x are intermediate entities to propagate the inﬂuence of the perturbations to eh,target x . The propagation path can be illustrated as follows:

eh,target x rx,1 ex,1 rx,2 ex,2 rx,K ex,K

where we use rx, to denote the directional relation and use notation ex, to denote the entities on the path. A speciﬁc ex, can work as both the head entity and the tail entity. The notations in the path above are adopted in the rest of this section.

When the perturbations on the proxy entity cause an embedding shift on itself, the embeddings of its neighboring entities will also be inﬂuenced. The inﬂuence will propagate back to the embedding of the targeted entity ultimately. However, ﬁnding the effective perturbations on the proxy entities, which are K-hop away from the targeted entity, is indeed a challenging task. The task involves two key problems: (1) Given a speciﬁc propagation path, how can we determine the desired embedding shifting vectors on its intermediate entities and its proxy entity, in order to accomplish the embedding shifting goal on the targeted entity? (2) How do we select the propagation paths to propagate the inﬂuence of perturbation to the targeted entity? In the rest of this section, we discuss strategies to solve these key problems and propose a criterion to evaluate the beneﬁt of an indirect perturbation (i.e., the perturbation beneﬁt score). For the ﬁrst problem, given a speciﬁc path, in order to conduct a perturbation that makes the embedding of eh,target x shift towards the desired direction (i.e., the direction of ϵ x), we decide the shifting goal for each entity on the path in a recurrent way. Suppose we want to shift eh,target x by ϵ x via the intermediate entities along the path speciﬁed in Example 1. The entity that directly inﬂuences eh,target x is its neighbor ex,1 and what we need to do is to determine the ideal embedding shifting vector ϵ x,1 on ex,1, so that the desired embedding shift on eh,target x (i.e., ϵ x) is approached to the greatest extent. Formally, ϵ x,1 should satisfy:

ϵ x,1 = arg max ϵ f(eh,target x + ϵ x, rx,1, ex,1 + ϵ)

f(eh,target x , rx,1, ex,1 + ϵ) s.t. ||ϵ||2 = ϵh,

where ϵh is the perturbation step size, ex,1 denotes the embedding of ex,1, and rx,1 denotes the embedding of rx,1. As

Algorithm 1 Indirect Attack

Require: Targeted fact (eh,target x , rtarget x , et,target x ), Neighbor hop K, Targeted entity eh,target x . 1: Exhaust all the K-hop paths originating from eh,target x 2: Exhaust all the possible perturbation candidates on the proxy entities of these K-hop paths. 3: Calculate ϵ x for eh,target x according to Eq. (1). 4: for each path k do 5: for each intermediate entity / proxy entity ex,i in path x do 6: Calculate ϵ x,i according to Eq. (4). 7: end for 8: Calculate the score ψ for each perturbation on the current proxy entity according to Eq. (2), Eq. (3) and (5). 9: end for 10: Select M perturbations with highest scores (i.e., ψ) and conduct the attack.

a result, the embedding of eh,target x will have a larger tendency to move towards eh,target x + ϵ x than towards eh,target x , during the training process on the contaminated training data. When ϵ x,1 is determined, we can further get the embedding shifting vector for ex,2, , ex,K, which are denoted as ϵ x,2, , ϵ x,K, respectively. This process is similar as above.

With the embedding shifting vectors on the proxy entities of each path determined, we calculate the scores η and η+, deﬁned in Eq. (2) and (3) for all the possible add/delete perturbations. These scores are later used to calculate the perturbation beneﬁt score under indirect attack schemes.

For the second problem, we look into the training objective function. Suppose we want to shift the embedding of ex,k 1 via its neighbor ex,k, when the embedding shift on ex,k is ϵ x,k. To estimate the inﬂuence of such embedding shift on ex,k 1, we isolate all the facts that involve ex,k 1 in the training objective function, force a embedding shift ϵx,k on ex,k and ignore the negative sampling terms. Formally, the objective function becomes: mineex,k 1 P

(eh i ,ri,et i) D \ex,k ex,k 1 L(eh i , ri, et i) +

L(ex,k 1, rx,k, ex,k + ϵx,k), where D\ex,k ex,k 1 stands for the set of all the observed facts, which involve ex,k 1 except the fact (ex,k 1, rx,k, ex,k), in the training set. L denotes the loss function for a single fact. ex,k + ϵx,k in L(ex,k 1, rx,k, ex,k + ϵx,k) indicates that the embedding of ex,k is already shifted. Clearly, if we ﬁx the embeddings of all the relations and entities except ex,k 1, the impact of shifting ex,k to ex,k + ϵx,k is highly correlated with the number of facts that involves ex,k 1, i.e., |Dex,k 1|. That is to say, the more neighbors an entity has, the less it will be inﬂuenced by a speciﬁc perturbation on one of its neighbors.

Based on above discussions, we propose an empirical scoring function to evaluate the perturbation beneﬁt score of every possible perturbation. We still consider the scenario speciﬁed in Example 1. Suppose we conduct an add/delete perturbation (ex,K, rx,K, ex,K+1) on the proxy entity ex,K. The perturbation beneﬁt score of this indirect perturbation is deﬁned as:

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

ψ(ex,K, rx,K, ex,K+1)

= η(ex,K, rx,K, ex,K+1) λ log 1

k=1 |Dex,k 1|

+ max({|Dex,k 1|}K 1 k=1 ) ,

where max({|Dex,k 1|}K 1 k=1 ) stands for the maximum number of facts that involves each entity k on the path. η is the same as η+ under add perturbation scheme and is the same as η under delete perturbation scheme. λ is a trade-off parameter. The ﬁrst term estimates the direct perturbation beneﬁt of the perturbation in terms of shifting the proxy entity as desired. The second term evaluates the capability of the intermediate entities on the path in terms of propagating the inﬂuence to the targeted entity. As the inﬂuence may be diluted by the facts that involve each entity ex,k on the path. A smaller averaged number of facts that involves each entity ex,k on the path indicates a larger capability of the path in terms of propagating the inﬂuence. Moreover, we also consider the maximum number of facts that involves each entity ex,k on the path. This is to avoid the case when some intermediate entities, whose embedding is difﬁcult to shift, block the propagation path. In practices, we can ﬁrst utilize the second term to determine the best P paths in terms of propagating the inﬂuence from proxy entities to the targeted entity and then choose what facts to add or delete upon these proxy entities in the best P paths. 3 The overall workﬂow of indirect attack is illustrated in Algorithm 1.

4 Experiments 4.1 Datasets and Settings Datasets. In this paper, we use two common KGE benchmark datasets for our experiment: FB15k and WN18. FB15k is a subset of Freebase, which is a large collaborative knowledge base consisting of a large number of real-world facts. WN18 is a subset of Wordnet 4, which is a large lexical knowledge graph. Both FB15k and WN18 are ﬁrst introduced by [Bordes et al., 2013]. The training set and the test set of these two datasets are already ﬁxed. We randomly sample 100 samples in the test set as the targeted facts for the proposed attack strategies.

Baseline & Targeted Models. Since there are no existing methods that can work under the setting of this paper, we compare the proposed attack schemes with several naive baseline strategies. Speciﬁcally, we design random-dd (random direct deleting), random-da (random direct adding), random-id (random indirect deleting), random-ia (random indirect adding) as comparison baselines for our proposed direct deleting attack, direct adding attack, indirect deleting attack, indirect adding attack, respectively. The difference between the baseline and its corresponding proposed methods is that the perturbation facts to add/delete are randomly selected. For the targeted KGE models, we choose three most

3This strategy is used in the experiments of this paper. 4https://wordnet.princeton.edu/

Clean random-da Direct Add MRR H@10 MRR H@10 MRR H@10 Trans E 0.26 0.49 0.24 0.46 0.24 0.42 FB15K Trans R 0.24 0.52 0.23 0.42 0.21 0.41 RESCAL 0.19 0.42 0.20 0.40 0.17 0.39 Trans E 0.39 0.70 0.30 0.68 0.21 0.53 WN18 Trans R 0.44 0.73 0.41 0.71 0.22 0.51 RESCAL 0.41 0.72 0.44 0.69 0.30 0.57

Table 1: Overall Results of Direct Adding Attack

Clean random-dd Direct Delete MRR H@10 MRR H@10 MRR H@10 Trans E 0.26 0.49 0.26 0.54 0.19 0.37 FB15K Trans R 0.24 0.52 0.25 0.49 0.18 0.41 RESCAL 0.19 0.42 0.19 0.38 0.13 0.30 Trans E 0.39 0.70 0.36 0.71 0.11 0.26 WN18 Trans R 0.44 0.73 0.43 0.68 0.11 0.24 RESCAL 0.41 0.72 0.40 0.67 0.02 0.05

Table 2: Overall Results of Direct Deleting Attack

representative Trans E [Bordes et al., 2013], Trans R [Lin et al., 2015] and RESCAL [Nickel et al., 2011] as attack targets.

Metrics. In order to evaluate the effectiveness of the proposed attack strategies. We compare the plausibility change of the targeted fact before and after the adversarial attack. Speciﬁcally, we follow the evaluation protocol of KGE models described in the previous works like [Bordes et al., 2013]. Given a targeted fact (eh, r, et), we remove the head or tail entity and then replace it with all the possible entities. We ﬁrst compute plausibility scores of those corrupted facts and then rank them by descending order; the rank of the correct entity is stored. After that, we use MRR (Mean Reciprocal Rank of all the ground truth triples) and H@10 (the proportion of correct entities ranked in top 10, for all the ground truth entities.) as our evaluation metrics. The smaller MRR and H@10 are on the contaminated dataset, the better the attack performance is.

Experiment Settings. For the targeted KGE models, we use the standard implementation provided by THUNLPOpen KE 5 [Han et al., 2018]. The embedding dimension d is ﬁxed to 50. Other parameters of baseline methods are set according to their authors suggestions. For the proposed attack strategies, the parameter K for indirect attack is ﬁxed to 1. During the experiment all the perturbations are injected into the dataset at the same time. The attack models in this paper are all implemented via Numpy and Python 3.7. The attack models are run on a laptop with 4 GB RAM, 2.7 GHz Intel Core i5 CPU.

4.2 Results and Analysis In this section, we report and analyze the attack results of the proposed attack strategies under different settings. To avoid confusion, the performance of direct adding attack, direct deleting attack, indirect adding attack, and indirect deleting attack are reported separately in Table 1, 2, 3 and 4.

Overall Attack Performance. Let us ﬁrst discuss the performances of the direct attack schemes on two datasets. For

5https://github.com/thunlp/Open KE

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Clean random-ia Indirect Add MRR H@10 MRR H@10 MRR H@10 Trans E 0.26 0.49 0.25 0.50 0.23 0.47 FB15K Trans R 0.24 0.52 0.25 0.51 0.22 0.49 RESCAL 0.19 0.42 0.19 0.40 0.17 0.36 Trans E 0.39 0.70 0.42 0.71 0.32 0.67 WN18 Trans R 0.44 0.73 0.40 0.73 0.34 0.69 RESCAL 0.41 0.72 0.41 0.69 0.39 0.63

Table 3: Overall Results of Indirect Adding Attack

Clean random-id Indirect Delete MRR H@10 MRR H@10 MRR H@10 Trans E 0.26 0.49 0.27 0.50 0.22 0.44 FB15K Trans R 0.24 0.52 0.25 0.53 0.21 0.48 RESCAL 0.19 0.42 0.20 0.36 0.16 0.34 Trans E 0.39 0.70 0.44 0.74 0.35 0.68 WN18 Trans R 0.44 0.73 0.45 0.74 0.41 0.71 RESCAL 0.41 0.72 0.42 0.70 0.38 0.64

Table 4: Overall Results of Indirect Deleting Attack

the direct deleting attack scheme, we set the attack budget for each targeted fact to 4 and 1 on FB15K and WN18 dataset, respectively. For the direct attacking attack scheme, the attack budgets for each targeted fact are 8 and 6 for FB15K and WN18 dataset, respectively. These budgets are low enough to make the whole attack process unnoticeable. From the results, we can clearly see that the plausibilities of these targeted facts signiﬁcantly degrade as desired. We can conclude that these KGE models are quite vulnerable to even a small number of perturbations generated by well-designed attack strategies. For comparison, we have also tested the baseline methods random-da and random-dd, which cannot achieve satisfactory attack performances. This demonstrates the effectiveness of the proposed strategies. Moreover, we observe that the effectiveness of the proposed strategies is more signiﬁcant on WN18 dataset than on FB15K dataset. This is because the average number of facts that each entity involves in WN18 dataset is signiﬁcantly smaller than that in FB15K dataset. Hence, the graph structure of FB15K is more stable and robust. Then, let us move on to the discussion of indirect attack schemes. For the indirect adding attack, we set the attack budget for each targeted fact to 60 and 20 for FB15K and WN18 dataset, respectively. For the indirect deleting attack, the attack budgets for each targeted fact are set to 20 and 5 for FB15K and WN18 dataset, respectively. The reason why indirect attacks need more attack budgets to get comparable results is that only a small portion of the inﬂuence caused by the perturbations on proxy entities is propagated to the targeted entity. In contrast, nearly all of the inﬂuence of the perturbation is exerted on the targeted entity under direct attack schemes. Like direct attack schemes, these indirect attack schemes also demonstrate their effectiveness. For instance, under the indirect deleting attack scheme, the H@10 and MRR metrics of the targeted facts decrease by approximate 0.03 on FB15K dataset. Thus, the indirect deleting attack schemes can also be used in practices to make the attack process more stealthy.

Analysis of the Number of Perturbations. When conducting the data poisoning attack, one of the most important fac-

0 2 4 6 8 Number of Perturbations.

(a) Direct Adding Attack on WN18 Dataset against Trans E

0 1 2 3 4 Number of Perturbations.

(b) Direct Deleting Attack on WN18 Dataset against Trans E

Figure 1: Analysis of the Number of Perturbations

tors is the number of perturbations (i.e. attack budget). Due to space limit, we merely plot performances of direct attack schemes against Trans E w.r.t. the number of perturbations (i.e., attack budgets) on WN18 dataset in Figure 1. From Figure. 1, we can clearly see that the proposed attack strategies consistently degrade the plausibility of the targeted facts under both setting. When the number of perturbations keeps increase, the growth of attack performance becomes slower. This is because when the number of perturbations is small, the selected perturbations are usually of high value in terms of manipulating the plausibility of the targeted facts. When the number of perturbations keeps increase, the high-value perturbations are used up. Hence, the performances become stable.

Efﬁciency Analysis. Finally, let us discuss the efﬁciency of the proposed attack strategies. Here we report the time consumption for the proposed attack strategies to generate the perturbations for a single targeted fact on average. The time consumption of Direct Adding, Direct Deleting, Indirect Adding and Indirect Deleting scheme are 3.36s, 0.13s, 14.04s, and 1.22s, respectively. 6 As one can see, the proposed model takes less than 15 seconds on average to generate the perturbations for a single targeted fact. For the direct deleting attack scheme, the time cost is less than 1 second on average. These results show that the proposed attack strategies are quite efﬁcient.

5 Conclusions

We present the ﬁrst study on the vulnerability of existing KGE methods and propose a collection of data poisoning attack strategies for different attack scenarios. These attack strategies can be efﬁciently computed. Experiment results on two benchmark dataset demonstrate that the proposed strategies can effectively manipulate the plausibility of arbitrary facts in the knowledge graph with limited perturbations.

Acknowledgments

We thank our anonymous reviewers for their insightful comments and suggestions on this paper. This work was supported in part by the US National Science Foundation under grants CNS-1742847, IIS-1747614 and CNS-1652503.

6Note: Candidate downsampling, which is described in Section 3.1 is used.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Biggio et al., 2012] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. ar Xiv preprint ar Xiv:1206.6389, 2012. [Bojcheski and G unnemann, 2018] Aleksandar Bojcheski and Stephan G unnemann. Adversarial attacks on node embeddings. ar Xiv preprint ar Xiv:1809.01093, 2018. [Bollacker et al., 2008] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In Proc. of SIGMOD, 2008. [Bordes et al., 2013] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in NIPS, 2013. [Carlini and Wagner, 2017] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Proc. of IEEE S&P, 2017. [Chen et al., 2018] Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. Fast gradient attack on network embedding. ar Xiv preprint ar Xiv:1809.02797, 2018. [Dai et al., 2018] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. ar Xiv preprint ar Xiv:1806.02371, 2018. [Goodfellow et al., 2014] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ar Xiv preprint ar Xiv:1412.6572, 2014. [Han et al., 2018] Xu Han, Shulin Cao, Xin Lv, Yankai Lin, Zhiyuan Liu, Maosong Sun, and Juanzi Li. Openke: An open toolkit for knowledge embedding. In Proc. of EMNLP Demo, 2018. [Hoffart et al., 2013] Johannes Hoffart, Fabian M Suchanek, Klaus Berberich, and Gerhard Weikum. Yago2: A spatially and temporally enhanced knowledge base from wikipedia. Artiﬁcial Intelligence, 194:28 61, 2013. [Ji et al., 2015] Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. Knowledge graph embedding via dynamic mapping matrix. In Proc. of ACL-IJCNLP, 2015. [Kipf and Welling, 2016] Thomas N Kipf and Max Welling. Semi-supervised classiﬁcation with graph convolutional networks. ar Xiv preprint ar Xiv:1609.02907, 2016. [Kurakin et al., 2016] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. ar Xiv preprint ar Xiv:1607.02533, 2016. [Lin et al., 2015] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In Proc. of AAAI, 2015. [Mintz et al., 2009] Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. Distant supervision for relation extraction without labeled data. In Proc. of ACL-IJCNLP, 2009.

[Nickel et al., 2011] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In Proc. of ICML, 2011. [Steinhardt et al., 2017] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certiﬁed defenses for data poisoning attacks. In Advances in NIPS, 2017. [Stewart, 1990] Gilbert W Stewart. Matrix perturbation theory. 1990. [Sun et al., 2018] Mingjie Sun, Jian Tang, Huichen Li, Bo Li, Chaowei Xiao, Yao Chen, and Dawn Song. Data poisoning attack against unsupervised node embedding methods. ar Xiv preprint ar Xiv:1810.12881, 2018. [Trouillon et al., 2016] Th eo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In Proc. of ICML, 2016. [Wang et al., 2014] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In Proc. of AAAI, 2014. [Wang et al., 2017] Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE TKDE, (12):2724 2743, 2017. [Wang et al., 2018] Hongwei Wang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Dkn: Deep knowledge-aware network for news recommendation. In Proc. of WWW, pages 1835 1844, 2018. [Xiao et al., 2015] Han Xiao, Minlie Huang, Yu Hao, and Xiaoyan Zhu. Transa: An adaptive approach for knowledge graph embedding. ar Xiv preprint ar Xiv:1509.05490, 2015. [Yang et al., 2014a] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. ar Xiv preprint ar Xiv:1412.6575, 2014. [Yang et al., 2014b] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Learning multi-relational semantics using neural-embedding models. ar Xiv preprint ar Xiv:1411.4072, 2014. [Yih et al., 2015] Wen-tau Yih, Ming-Wei Chang, Xiaodong He, and Jianfeng Gao. Semantic parsing via staged query graph generation: Question answering with knowledge base. In Proc. of ACL-IJCNLP, 2015. [Zhang et al., 2016] Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei-Ying Ma. Collaborative knowledge base embedding for recommender systems. In Proc. of SIGKDD, 2016. [Z ugner et al., 2018] Daniel Z ugner, Amir Akbarnejad, and Stephan G unnemann. Adversarial attacks on classiﬁcation models for graphs. ar Xiv preprint ar Xiv:1805.07984, 2018.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)