Data Poisoning Attack against Knowledge Graph Embedding

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 Graph 1 . 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 difficult 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 significant attention [Nickel et al., 2011; Lin et al., 2015; Bordes et al., 2013; Yang et al., 2014b;

1 https://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 contributions 2 . 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 financial 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 first time, we systemically investigate the vulnerability of KGE, through designing efficient 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 first study on the vulnerability 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 specific facts to promote or degrade the plausibility of specific targeted facts, which can potentially influence 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 https://www.nytimes.com/2007/03/09/technology/09data.html

2 RelatedWork

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 first translation-based KGE method TransE. Given a fact (h, r, t), composed of a relation (r) and two entities (h and t) in the knowledge graph, TransE 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 TransH [Wang et al., 2014], TransR [Lin et al., 2015], TransD [Ji et al., 2015] and TransA [Xiao et al., 2015], extend TransE by projecting the embedding vector into various spaces. On the other hand, DistMult [Yang et al., 2014a] simplifies RESCAL by only using a diagonal matrix, and ComPlex [Trouillon et al., 2016] extends DistMult into the complex number field. [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 classification [Z¨ugner et al., 2018; Dai et al., 2018], graph classification [Dai et al., 2018], link prediction [Chen et al., 2018] and node embedding [Sun et al., 2018; Bojcheski and G¨unnemann, 2018]. The first 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 classifier to learn the policy of selecting the edge perturbations that fool the classifier. [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 first 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 {(ehn , rn, etn )}Nn=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 specific 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 defined as follows:

Definition 1 (Problem Definition). 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, fixed 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 specific 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 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 difficult to be manipulated via a small number of modifications. 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 efficient 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 benefit of a perturbation, i.e., how much shifting can be achieved by this perturbation along the desired direction. We name the score as perturbation benefit score and calculate such score for every possible perturbation. Finally, we conduct the Top-M perturbations with highest perturbation benefit 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:

As mentioned in the problem definition, 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 find 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 influence 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 specific deletion candidate (eh,target x , ri, eti ) 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 plausible the fact (eh,target x , ri, eti ) is, the more it contributes to the final embedding of eh,target x . Hence, the perturbation benefit score of deleting (eh,target x , ri, eti ) should be proportional to f(eh,target x , ri, eti ). On the other hand, if the plausibility of fact (eh,target x , ri, eti ) is large after eh,target x is shifted to eh,target x +ϵ∗x (i.e., f(eh,target x +ϵ∗x , ri, eti ) is large), it means that the fact (eh,target x , ri, eti ) has a great positive impact on the embedding shifting and should not be deleted. Hence, the perturbation benefit score of deleting (eh,target x , ri, eti ) should be inversely proportional to f(eh,target x + ϵ∗x , ri, eti ). Formally, let the set of all the delete candidates be: DD = {(ehi , ri, eti ) | ehi = eh,target x and (ehi , ri, eti ) ∈ KG}, which intuitively denote the set of facts that involve eh,target x as the head entity in the training set. The perturbation benefit score of deleting a specific perturbation fact (eh,target x , ri, eti ) can be estimated as:

where eh,target x , ri, and eti denote the embeddings of eh,target x , ri and eti on the uncontaminated training set.

Direct Adding Attack. Nowwe 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, etj ) less plausible. The set of all the possible adding candidates can be denoted as DA = {eh,target x } × {(rj, etj ) | ∀rj ∈ KG and etj ∈ KG}, where {(rj, etj ) | ∀rj ∈ KG and etj ∈ KG} denotes all the possible "relation-tail entity" combinations in the knowledge graph and × stands for Cartesian product. In practice, for better efficiency, we can downsample a subset from all the possible "relation-tail entity" combinations. Formally, the perturbation benefit score of a specific candidate to add (i.e., (eh,target x , rj , etj )) can be estimated as:

where eh,target x , rj, and eti 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 sanity cost will have a exponential growth. Even though there is an Oracle that can find 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 influence of the perturbations to eh,target x . The propagation path can be illustrated as follows:

where we use rx,· ←-→ to denote the directional relation and use notation ex,· to denote the entities on the path. A specific 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 influenced. The influence will propagate back to the embedding of the targeted entity ultimately.

However, finding 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 specific 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 influence 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 benefit of an indirect perturbation (i.e., the perturbation benefit score).

For the first problem, given a specific 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 specified in Example 1. The entity that directly influences 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:

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 η+, defined in Eq. (2) and (3) for all the possible add/delete perturbations. These scores are later used to calculate the perturbation benefit 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 influence 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 ∑(ehi ,ri,eti )∈D\ex,k ex,k-1 L(ehi , ri, eti ) +

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 fix 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 influenced by a specific perturbation on one of its neighbors.

Based on above discussions, we propose an empirical scoring function to evaluate the perturbation benefit score of every possible perturbation. We still consider the scenario specified 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 benefit score of this indirect perturbation is defined as:

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 first term estimates the direct perturbation benefit 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 influence to the targeted entity. As the influence 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 influence. 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 difficult to shift, "block" the propagation path. In practices, we can first utilize the second term to determine the best P paths in terms of propagating the influence 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 workflow 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 first introduced by [Bordes et al., 2013]. The training set and the test set of these two datasets are already fixed. 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. Specifically, 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 representative TransE [Bordes et al., 2013], TransR [Lin et al., 2015] and RESCAL [Nickel et al., 2011] as attack targets.

3 This strategy is used in the experiments of this paper.

4 https://wordnet.princeton.edu/

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. Specifically, 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 first 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 THUNLPOpenKE 5 [Han et al., 2018]. The embedding dimension d is fixed 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 fixed 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 first discuss the performances of the direct attack schemes on two datasets. For 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 significantly 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 significant on WN18 dataset than on FB15K dataset. This is because the average number of facts that each entity involves in WN18 dataset is significantly 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 influence caused by the perturbations on proxy entities is propagated to the targeted entity. In contrast, nearly all of the influence 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.

5 https://github.com/thunlp/OpenKE

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

• (a) Direct Adding Attack on WN18 Dataset against TransE
• (b) Direct Deleting Attack on WN18 Dataset against TransE

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 TransE 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.

Efficiency Analysis. Finally, let us discuss the efficiency 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 efficient.

5 Conclusions

We present the first 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 efficiently 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.

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