We study the problem of generating data poisoning attacks against Knowledge Graph Embedding (KGE) models for the task of link prediction in knowledge graphs. To poison KGE models, we propose to exploit their inductive abilities which are captured through the relationship patterns like symmetry, inversion and composition in the knowledge graph. Specifi-cally, to degrade the model's prediction confidence on target facts, we propose to improve the model's prediction confidence on a set of decoy facts. Thus, we craft adversarial additions that can improve the model's prediction confidence on decoy facts through different inference patterns. Our experiments demonstrate that the proposed poisoning attacks outperform state-of-art baselines on four KGE models for two publicly available datasets. We also find that the symmetry pattern based attacks generalize across all model-dataset combinations which indicates the sensitivity of KGE models to this pattern. Knowledge graph embeddings (KGE) are increasingly deployed in domains with high stake decision making like healthcare and finance (Noy et al., 2019), where it is critical to identify the potential security vulnerabilities that might cause failure. But the research on adversarial vulnerabilities of KGE models has received little attention. We study the adversarial vulnerabilities of KGE models through data poisoning attacks. These attacks craft input perturbations at training time that aim to subvert the learned model's predictions at test time. Poisoning attacks have been proposed for models that learn from other graph modalities (Xu et al., 2020) but they cannot be applied directly to KGE models. This is because they rely on gradients of  Equal contribution by last authors. Figure 1 : Composition based adversarial attack on fraud detection. The knowledge graph consists of two types of entities Person and BankAccount. The target triple to predict is ( Karl, affiliated with , Joe the mobster ) . Original KGE model predicts this triple as True. But a malicious attacker adds adversarial triples (in purple) that connect Karl with a non-suspicious person Bob through composition pattern. Now, the KGE model predicts the target triple as False. all possible entries in a dense adjacency matrix and thus, do not scale to large knowledge graphs with multiple relations. The main challenge in designing poisoning attacks for KGE models is the large combinatorial search space of candidate perturbations which is of the order of millions for benchmark knowledge graphs with thousands of nodes. Two recent studies (Zhang et al., 2019a; Pezeshkpour et al., 2019) attempt to address this problem through random sampling of candidate perturbations (Zhang et al., 2019a) or through a vanilla auto-encoder that reconstructs discrete entities and relations from latent space (Pezeshkpour et al., 2019). However, random sampling depends on the number of candidates being sampled and the auto-encoder proposed in Pezeshkpour et al. (2019) is only applicable to multiplicative KGE models. In this work, we propose to exploit the inductive abilities of KGE models to craft poisoned examples against the model. The inductive abilities of KGE models are expressed through different connectivity patterns like symmetry, inversion and composition between relations in the knowledge graph. We refer to these as inference patterns . We focus on the task of link prediction using KGE models and consider the adversarial goal of degrading the predicted rank of target missing facts. To degrade the ranks of target facts, we propose to carefully select a set of decoy facts and exploit the inference patterns to improve performance on this decoy set. Figure 1 shows an example of the use of composition pattern to degrade KGE model's performance. We explore a collection of heuristic approaches to select the decoy triples and craft adversarial perturbations that use different inference patterns to improve the model's predictive performance on these decoy triples. Our solution addresses the challenge of large candidate space by breaking down the search space into smaller steps - (i) determining adversarial relations; (ii) determining the decoy entities that most likely violate an inference pattern; and (iii) determining remaining adversarial entities in the inference pattern that are most likely to improve the rank of decoy triples. We evaluate the proposed attacks on four state-of-art KGE models with varied inductive abilities DistMult, ComplEx, ConvE and TransE. We use two publicly available benchmark datasets for link prediction WN18RR and FB15k-237. Comparison against the state-of-art poisoning attacks for KGE models shows that our proposed attacks outperform them in all cases. We find that the attacks based on symmetry pattern perform the best and generalize across all model-dataset combinations. Thus, the main contribution of our research is an effective method to generate data poisoning attacks, which is based on inference patterns captured by KGE models. Through a novel reformulation of the problem of poisoning KGE models, we overcome the existing challenge in the scalability of poisoning attacks for KGE models. Furthermore, the extent of effectiveness of the attack relying on an inference pattern indicates the KGE model's sensitivity to that pattern. Thus, our proposed poisoning attacks help in understanding the KGE models. For a set of entities E and a set of relations R , a knowledge graph is a collection of triples represented as KG = { ( s, r , o ) | s, o  E and r  R} , where s, r , o represent the subject, relation and object in a triple. A Knowledge Graph Em-Model Scoring Function DistMult (cid:104) e s , e r , e o (cid:105) ComplEx (cid:60) ( (cid:104) e s , e r , e o (cid:105) ) ConvE (cid:104)  (vec(  ([ e r , e s ]   )) W ) , e o (cid:105) TransE  (cid:107) e s + e r  e o (cid:107) Table 1: Scoring functions f sro of the KGE models used in this research. To do so, it uses a scoring function f : E  R  E  R which depends on the entity and relation embeddings to assign a score to each triple f sro = f ( e s , e r , e o ) . Table 1 shows the scoring functions of state-of-art KGE models studied in this research. The embeddings are learned such that the scores for true (existing) triples in the knowledge graph are higher than the scores for false (non-existing) triples in the knowledge graph. Multiplicative vs Additive Interactions: The scoring functions of KGE models exhibit multiplicative or additive interactions (Chandrahas et al., 2018). The multiplicative models score triples through multiplicative interactions of subject, relation and object embeddings. The scoring function for these models can be expressed as f sro = e (cid:62) r F ( e s , e o ) where the function F measures the compatibility between the subject and object embeddings and varies across different models within this family. DistMult, ComplEx and ConvE have such interactions. On the other hand, additive models score triples through additive interactions of subject, relation and object embeddings. The scoring function for such models can be expressed as f sro =  (cid:13)(cid:13) M 1 r ( e s ) + e r  M 2 r ( e o ) (cid:13)(cid:13) where e s , e o  R k E , e r  R k R and M r  R k E  k R is the projection matrix from entity space R k E to relation space R k R . TransE has additive interactions. Inductive Capacity of KGE models: The general intuition behind the design of the scoring functions of KGE models is to capture logical properties between relations from the observed facts in the knowledge graph. These logical properties or inference patterns can then be used to make downstream inferences about entities and relations. For example, the relation is owned by is inverse of the relation owns , and when the fact ( Account 42 , is owned by , Karl ) is true, then the fact ( Karl, owns , Account 42) is also true and vice versa. A model that can capture inversion pattern can thus predict missing facts about owns based on observed facts about is owned by . The most studied inference patterns in the current literature are symmetry, inversion and composition since they occur very frequently in real-world knowledge graphs. In this work, we use these patterns to investigate the adversarial vulnerability of KGE models. Link Prediction: Since most of the existing knowledge graphs are incomplete, a standard use case of KGE models is to predict missing triples in the KG . This task is evaluated by an entity ranking procedure. Given a test triple ( s, r , o ) , the subject entity is replaced by each entity from E in turn. These replacements are referred to as synthetic negatives . The KGE model's scoring function is used to predict scores of these negative triples. The scores are then sorted in descending order and the rank of the correct entity is determined. These steps are repeated for the object entity of the triple. The state-of-art evaluation metrics for this task are (i) MR which is the mean of the predicted ranks, (ii) MRR which is the mean of the reciprocals of predicted ranks and (iii) Hits@n which count the proportion of correct entities ranked in top-n. In the filtered setting (Bordes et al., 2013), negative triples that already exist in the training, validation or test set are filtered out. That is, their scores are ignored while computing the ranks. Depending on the domain of use, either subject or object or both ranks of the test triple are used to determine the model's confidence 1 in predicting a missing link. Poisoning Attacks on KGE models: We study poisoning attacks for the task of link prediction using KGE models. We focus on targeted attacks where the attacker targets a specific set of missing triples instead of the overall model performance. We use the notation ( s, r , o ) for the target triple ; in this case, s, o are the target entities and r is the target relation . The goal of an adversarial attacker is to degrade the ranks of missing triples which are predicted highly plausible by the model. The rank of a highly plausible target triple can be degraded by improving the rank of less plausible decoy triples . For a target triple ( s, r , o ) , the decoy triple for degrading the rank on object side would be ( s, r , o (cid:48) ) and the decoy triple for degrading the 1 KGE models do not provide model uncertainty estimates. rank on subject side would be ( s (cid:48) , r , o ) . Thus, the aim of the adversarial attacker is to select decoy triples from the set of valid synthetic negatives and craft adversarial edits to improve their ranks. The attacker does not add the decoy triple itself as an adversarial edit, rather chooses the adversarial edits that would improve the rank of a missing decoy triple through an inference pattern. Threat Model: To ensure reliable vulnerability analysis, we use a white-box attack setting where the attacker has full knowledge of the target KGE model (Joseph et al., 2019). They cannot manipulate the model architecture or learned embeddings directly; but only through addition of triples to the training data. We focus on adversarial additions which are more challenging to design than adversarial deletions for sparse knowledge graphs 2 . As in prior studies (Pezeshkpour et al., 2019; Zhang et al., 2019a), the attacker is restricted to making edits only in the neighbourhood of target entities. They are also restricted to 1 decoy triple for each entity of the target triple. Furthermore, because of the use of filtered settings for KGE evaluation, the attacker cannot add the decoy triple itself to the training data (which intuitively would be a way to improve the decoy triple's rank). Since the inference patterns on the knowledge graph specify a logic property between the relations, they can be expressed as Horn Clauses which is a subset of FOL formulae. For example, a property represented in the form  x, y : ( x, owns , y )  ( y, is owned by , x ) means that two entities linked by relation owns are also likely to be linked by the inverse relation is owned by . In this expression, the right hand side of the implication  is referred to as the head and the left hand side as the body of the clause. Using such expressions, we define the three inference patterns used in our research. 2 For every target triple, the possible number of adversarial additions in the neighbourhood of each entity are E  R . For the benchmark dataset FB15k-237, this is of the order of millions; whereas the maximum number of candidates for adversarial deletion are of the order of thousands. Definition 3.2. The inversion pattern P i is expressed as  x, y : ( x, r i , y )  ( y, r , x ) . Here, the relations r i and r are inverse of each other. Definition 3.3. The composition pattern P c is expressed as  x, y, z : ( x, r 1 , z )  ( z, r 2 , y )  ( x, r , y ) . Here, the relation r is a composition of r 1 and r 2 ; and the  is the conjunction operator from relational logic. The mapping G : V  E of variables V in the above expressions to entities E is called a grounding. For example, we can map the logic expression  x, y : ( x, owns , y )  ( y, is owned by , x ) to the grounding ( Karl, owns , Account 42)  ( Account 42 , is owned by , Karl ) . Thus, a KGE model that captures the inversion pattern will assign a high prediction confidence to the head atom when the body of the clause exists in the graph. In the above expressions, the decoy triple becomes the head atom and adversarial edits are the triples in the body of the expression. Since the decoy triple is an object or subject side negative of the target triple, the attacker already knows the relation in the head atom. They now want to determine (i) the adversarial relations in the body of the expression; (ii) the decoy entities which will most likely violate the inference pattern for the chosen relations and; (iii) the remaining entities in the body of the expression which will improve the prediction on the chosen decoy triple. Notice that the attacker needs all three steps for composition pattern only; for inversion pattern, only the first two steps are needed; and for symmetry pattern, only the second step is needed. Below we describe each step in detail. A computational complexity analysis of all the steps is available in Appendix A. 3.1 Step1: Determine Adversarial Relations Expressing the relation patterns as logic expressions is based on relational logic and assumes that the relations are constants. Thus, we use an algebraic approach to determine the relations in the head and body of a clause. Given the target relation r , we determine the adversarial relations using an algebraic model of inference (Yang et al., 2015). Inversion: If an atom ( x, r , y ) holds true, then for the learned embeddings in multiplicative models, we can assume e x  e r  e y ; where  denotes the Hadamard (element-wise) product. If the atom ( y, r i , x ) holds true as well, then we can also assume e y  e r i  e x . Thus, e r  e r i  1 for inverse relations r and r i when embeddings are learned from multiplicative models. We obtain a similar expression e r + e r i  0 when embeddings are learned from additive models. Thus, to determine adversarial relations for inversion pattern, we use the pre-trained embeddings to select r i that minimizes | e r i e T r  1 | for multiplicative models; and r i that minimizes | e r i + e r | for additive models. Composition : If two atoms ( x, r 1 , y ) and ( y, r 2 , z ) hold true, then for multiplicative models, e x  e r 1  e y and e y  e r 2  e z . Therefore, e x  ( e r 1  e r 2 )  e z . Hence, relation r is a composition of r 1 and r 2 if e r 1  e r 2  e r . Similarly, for embeddings from additive models, we can model composition as e r 1 + e r 2  e r . Thus, to determine adversarial relations for composition pattern, we use pre-trained embeddings to obtain all possible compositions of ( r 1 , r 2 ). For multiplicative models, we use e r 1  e r 2 and for additive models we use e r 1 + e r 2 . From these, we choose the relation pair for which the Euclidean distance between the composed relation embeddings and the target relation embedding e r is minimum. We consider three different heuristic approaches to select the decoy entity soft truth score, ranks predicted by the KGE model and cosine distance. Soft Logical Modelling of Inference Patterns Once the adversarial relations are determined, we can express the grounding for symmetry, inversion and composition patterns for the decoy triples. We discuss only object side decoy triple for brevity G s : ( o (cid:48) , r , s )  ( s, r , o (cid:48) ) G i : ( o (cid:48) , r i , s )  ( s, r , o (cid:48) ) G c : ( s, r 1 , o (cid:48)(cid:48) )  ( o (cid:48)(cid:48) , r 2 , o (cid:48) )  ( s, r , o (cid:48) ) If the model captures P s , P i or P c to assign high rank to the target triple, then the head atom ( s, r , o (cid:48) ) of a grounding that violates this pattern is a suitable decoy triple. Adding the body of this grounding to the knowledge graph would improve the model performance on decoy triple through P s , P i or P c . To determine the decoy triple this way, we need a measure of the degree to which a grounding satisfies an inference pattern. We call this measure the soft truth score  : G  [0 , 1] it provides the truth value of a logic expression indicating the degree to which the expression is true. We model the soft truth score of grounded patterns using t-norm based fuzzy logics (Hajek, 1998). The score f sro of an individual atom (i.e. triple) is computed using the KGE model's scoring function. We use the sigmoid function  ( x ) = 1 / (1 + exp(  x )) to map this score to a continuous truth value in the range (0 , 1) . Hence, the soft truth score for an individual atom is  ( s, r , o ) =  ( f sro ) . The soft truth score for the grounding of a pattern can then be expressed through logical composition (e.g.  and  ) of the scores of individual atoms in the grounding. We follow (Guo et al., 2016, 2018) and define the following compositions for logical conjunction (  ), disjunction (  ), and negation (  ):  ( a  b ) =  ( a )   ( b ) ,  ( a  b ) =  ( a ) +  ( b )   ( a )   ( b ) ,  (  a ) = 1   ( a ) . Here, a and b are two logical expressions, which can either be single triples or be constructed by combining triples with logical connectives. If a is a single triple ( s, r , o ) , we have  ( a ) =  ( s, r , o ) . Given these compositions, the truth value of any logical expression can be calculated recursively (Guo et al., 2016, 2018). Thus, we obtain the following soft truth scores for the groundings of symmetry, inversion and composition patterns G s , G i and G c  ( G s ) =  ( o (cid:48) , r , s )   ( s, r , o (cid:48) )   ( o (cid:48) , r , s ) + 1  ( G i ) =  ( o (cid:48) , r i , s )   ( s, r , o (cid:48) )   ( o (cid:48) , r i , s ) + 1 . ( G c ) =  ( s, r 1 , o (cid:48)(cid:48) )   ( o (cid:48)(cid:48) , r 2 , o (cid:48) )   ( s, r , o (cid:48) )   ( s, r 1 , o (cid:48)(cid:48) )   ( o (cid:48)(cid:48) , r 2 , o (cid:48) ) + 1 To select the decoy triple ( s, r , o (cid:48) ) for symmetry and inversion, we score all possible groundings using  ( G s ) and  ( G i ) . The head atom of grounding with minimum score is chosen as decoy triple. For composition pattern, the soft truth score  ( G c ) for candidate decoy triples ( s, r , o (cid:48) ) contains two entities ( o (cid:48) , o (cid:48)(cid:48) ) to be identified. Thus, we use a greedy approach to select the decoy entity o (cid:48) . We use the pre-trained embeddings to group the entities o (cid:48)(cid:48) into k clusters using K-means clustering and determine a decoy entity with minimum soft truth score for each cluster. We then select the decoy entity o (cid:48) with minimum score across the k clusters. KGE Ranks: We use the ranking protocol from KGE evaluation to rank the target triple against valid subject and object side negatives ( s (cid:48) , r , o ) and ( s, r , o (cid:48) ) . For each side, we select the negative triple that is ranked just below the target triple (that Adversarial Attack Step Sym Inv Com Determine Adversarial Relations n/a Alg Alg Determine Decoy Entities Sft Sft Sft Rnk Rnk Rnk Cos Cos Cos Determine Adversarial Entities n/a n/a Sft Table 2: A summary of heuristic approaches used for different steps of the adversarial attack with symmetry (Sym), inversion (Inv) and composition (Com) pattern. is, negative rank = target rank + 1 ). These are suitable as decoy because their predicted scores are likely not very different from the target triple's score. Thus, the model's prediction confidence for these triples might be effectively manipulated through adversarial additions. This is in contrast to very low ranked triples as decoy; where the model has likely learnt a low score with high confidence. Cosine Distance: A high rank for the target triple ( s, r , o ) against queries ( s, r , ?) and (? , r , o ) indicates that e s , e o are similar to the embeddings of other subjects and objects related by r in the training data. Thus, a suitable heuristic for selecting decoy entities s (cid:48) and o (cid:48) is to choose ones whose embeddings are dissimilar to e s , e o . Since these entities are not likely to occur in the neighbourhood of o and s , they will act adversarially to reduce the rank of target triple. Thus, we select decoy entities s (cid:48) and o (cid:48) that have maximum cosine distance from target entities s and o respectively. This step is only needed for the composition pattern because the body for this pattern has two adversarial triples. Given the decoy triple in the head of the composition expression, we select the body of the expression that would maximize the rank of the decoy triple. We use the soft-logical model defined in Step 2 for selecting decoy triples. The soft truth score for composition grounding of decoy triple is given by  ( G t ) =  ( s, r 1 , o (cid:48)(cid:48) )   ( o (cid:48)(cid:48) , r 2 , o (cid:48) )   ( s, r , o (cid:48) )   ( s, r 1 , o (cid:48)(cid:48) )   ( o (cid:48)(cid:48) , r 2 , o (cid:48) ) + 1 . We select the entity o (cid:48)(cid:48) with maximum score because this entity satisfies the composition pattern for the decoy triple and is thus likely to improve the decoy triple's ranks on addition to the knowledge graph. The aim of our evaluation is to assess the effectiveness of proposed attacks in degrading the predictive performance of KGE models on missing triples that are predicted true. We use the state-of-art evaluation protocol for data poisoning attacks (Xu et al., 2020). We train a clean model on the original data; then generate the adversarial edits and add them to the dataset; and finally retrain a new model on this poisoned data. All hyperparameters for training on original and poisoned data remain the same. We evaluate four models with varying inductive abilities DistMult, ComplEx, ConvE and TransE; on two publicly available benchmark datasets for link prediction 3 WN18RR and FB15k-237. We filter out triples from the validation and test set that contain unseen entities. To assess the attack effectiveness in degrading performance on triples predicted as true, we need a set of triples that are predicted as true by the model. Thus, we select as target triples , a subset of the original test set where each triple is ranked  10 by the original model. Table 3 provides an overview of dataset statistics and the number of target triples selected. Baselines: We compare the proposed methods against the following baselines Random n : Random edits in the neighbourhood of each entity of the target triple. Random g1 : Global random edits in the knowledge graph which are not restricted to the neighbourhood of entities in the target triple and have 1 edit per decoy triple (like symmetry and inversion). Random g2 : Global random edits in the knowledge graph which are not restricted to the neigh-3 https://github.com/TimDettmers/ConvE bourhood of entities in the target triple and have 2 edits per decoy triple (like composition). Zhang et al. : Poisoning attack from (Zhang et al., 2019a) for edits in the neighbourhood of subject of the target triple. We extend it for both subject and object to match our evaluation protocol. Further implementation details available in Appendix B.2. CRIAGE : Poisoning attack from (Pezeshkpour et al., 2019). We use the publicly available implementation and the default attack settings 4 . The method was proposed for edits in the neighbourhood of object of the target triple. We extend it for both entities to match our evaluation protocol and to ensure fair evaluation. Implementation: For every attack, we filter out adversarial edit candidates that already exist in the graph.We also remove duplicate adversarial edits for different targets before adding them to the original dataset. For Step 2 of the composition attack with ground truth, we use the elbow method to determine the number of clusters for each model-data combination. Further details on KGE model training, computing resources and number of clusters are available in Appendix B. The source code to reproduce our experiments is available on GitHub 5 . Table 4 and 5 show the reduction in MRR and Hits@1 due to different attacks on the WN18RR and FB15k-237 datasets. We observe that the proposed adversarial attacks outperform the random baselines and the state-of-art poisoning attacks for all KGE models on both datasets. We see that the attacks based on symmetry inference pattern perform the best across all model-dataset combinations. This indicates the sensitivity of KGE models to symmetry pattern. For DistMult, ComplEx and ConvE, this sensitivity can be explained by the symmetric nature of the scoring functions of these models. That is, the models assign either equal or similar scores to triples that are symmetric opposite of each other. In the case of TransE, the model's sensitivity to symmetry pattern is explained by the translation operation in scoring function. The score of target ( s, r , o ) is a translation from subject to object embedding through the relation embedding. Symmetry attack adds the adversarial triple ( o (cid:48) , r , s ) where the relation is same 4 https://github.com/pouyapez/criage 5 https://github.com/PeruBhardwaj/ InferenceAttack DistMult ComplEx ConvE TransE MRR Hits@1 MRR Hits@1 MRR Hits@1 MRR Hits@1 Original 0.90 0.85 0.89 0.84 0.92 0.89 0.36 0.03 BaselineAttacks Random n 0.86 (-4%) 0.83 0.84 (-6%) 0.80 0.90 (-2%) 0.88 0.28 (-20%) 0.01 Random g1 0.88 0.83 0.88 0.83 0.92 0.89 0.35 0.02 Random g2 0.88 0.83 0.88 0.83 0.91 0.89 0.34 0.02 Zhang et al. 0.82 (-8%) 0.81 0.76 (-14%) 0.74 0.90 (-2%) 0.87 0.24 (-33%) 0.01 CRIAGE 0.87 0.84 -0.90 0.88 -Proposed Attacks Sym truth 0.66 0.40 0.56 (-33%) 0.24 0.61 (-34%) 0.28 0.57 0.36 Sym rank 0.61 0.32 0.56 (-33%) 0.24 0.62 0.31 0.25 0.02 Sym cos 0.57 (-36%) 0.32 0.62 0.43 0.67 0.44 0.24 (-33%) 0.01 Inv truth 0.87 0.83 0.86 0.80 0.90 0.87 0.34 0.03 Inv rank 0.86 0.83 0.85 0.80 0.89 (-4%) 0.85 0.25 0.02 Inv cos 0.83 (-8%) 0.82 0.80 (-10%) 0.79 0.90 0.88 0.25 (-30%) 0.01 Com truth 0.86 0.83 0.86 0.81 0.89 0.86 0.53 (+49%) 0.27 Com rank 0.85 (-5%) 0.80 0.83 0.77 0.89 0.84 0.57 0.32 Com cos 0.86 0.77 0.82 (-8%) 0.70 0.88(-4%) 0.83 0.53 (+49%) 0.27 Table 4: Reduction in MRR and Hits@1 due to different attacks on the target split of WN18RR. as the target relation, but target subject is the object of adversarial triple. Now, the model learns the embedding of s as a translation from o (cid:48) through relation r . This adversarially modifies the embedding of s and in turn, the score of ( s, r , o ) . We see that inversion and composition attacks also perform better than baselines in most cases, but not as good as symmetry. This is particularly true for FB15k-237 where the performance for these patterns is similar to random baselines. For the composition pattern, it is likely that the model has stronger bias for shorter and simpler patterns like symmetry and inversion than for composition. This makes it harder to deceive the model through composition than through symmetry or inverse. Furthermore, FB15k-237 has high connectivity (Dettmers et al., 2018) which means that a KGE model relies on a high number of triples to learn target triples' ranks. Thus, poisoning KGE models for FB15k-237 will likely require more adversarial triples per target triple than that considered in this research. The inversion pattern is likely ineffective on the benchmark datasets because these datasets do not have any inverse relations (Dettmers et al., 2018; Toutanova and Chen, 2015). This implies that our attacks cannot identify the inverse of the target triple's relation in Step 1. We investigate this hypothesis further in Appendix D, and evaluate the attacks on WN18 dataset where the inverse relations have not been filtered out. This means that the KGE model can learn the inversion pattern and the inversion attacks can identify the inverse of the target relation. In this setting, we find that the inversion attacks outperform other attacks against ComplEx on WN18, indicating the sensitivity of ComplEx to the inversion pattern when the dataset contains inverse relations. An exception in the results is the composition pattern on TransE where the model performance improves instead of degrading on the target triples. This is likely due to the model's sensitivity to composition pattern such that adding this pattern improves the performance on all triples, including target triples. To verify this, we checked the change in ranks of decoy triples and found that composition attacks on TransE improve these ranks too. Results for this experiment are available in Appendix C. This behaviour of composition also indicates that the selection of adversarial entities in Step 3 of the composition attacks can be improved. It also explains why the increase is more significant for WN18RR than FB15k-237 WN18RR does not have any composition relations but FB15k-237 does; so adding these to WN18RR shows significant improvement in performance. We aim to investigate these and more hypotheses about the proposed attacks in future work. KGE models can be categorized into tensor factorization models like DistMult (Yang et al., 2015) and ComplEx (Trouillon et al., 2016), neural archi-DistMult tectures like ConvE (Dettmers et al., 2018) and translational models like TransE (Bordes et al., 2013). We refer the reader to (Cai et al., 2018) for a comprehensive survey. Due to the black-box nature of KGE models, there is an emerging literature on understanding these models. (Pezeshkpour et al., 2019) and (Zhang et al., 2019a) are most closely related to our work as they propose other data poisoning attacks for KGE models. Minervini et al. (2017) and Cai and Wang (2018) use adversarial regularization in latent space and adversarial training to improve predictive performance on link prediction. But these adversarial samples are not in the input domain and aim to improve instead of degrade model performance. Poisoning attacks have also been proposed for models for undirected and single relational graph data like Graph Neural Networks (Zugner et al., 2018; Dai et al., 2018) and Network Embedding models (Bojchevski and Gunnemann, 2019). A survey of poisoning attacks for graph data is available in (Xu et al., 2020). But the attacks for these models cannot be applied directly to KGE models because they require gradients of a dense adjacency matrix. In the literature besides adversarial attacks, Lawrence et al. (2020), Nandwani et al. (2020) and Zhang et al. (2019b) generate post-hoc explanations to understand KGE model predictions. Trouillon et al. (2019) study the inductive abilities of KGE models as binary relation properties for controlled inference tasks with synthetic datasets. Allen et al. (2021) interpret the structure of knowledge graph embeddings by comparison with word embeddings. On the theoretical side, Wang et al. (2018) study the expressiveness of various bilinear KGE models and Gutierrez-Basulto and Schockaert (2018) study the ability of KGE models to learn hard rules expressed as ontological knowledge. The soft-logical model of inference patterns in this work is inspired by the literature on injecting logical rules into KGE models. Guo et al. (2016) and Guo et al. (2018) enforce soft logical rules by modelling the triples and rules in a unified framework and jointly learning embeddings from them. Additionally, our algebraic model of inference patterns, which is used to select adversarial relations, is related to approaches for graph traversal in latent vector space discussed in Yang et al. (2015); Guu et al. (2015); Arakelyan et al. (2021). We propose data poisoning attacks against KGE models based on inference patterns like symmetry, inversion and composition. Our experiments show that the proposed attacks outperform the state-of-art attacks. Since the attacks rely on relation inference patterns, they can also be used to understand the KGE models. This is because if a KGE model is sensitive to a relation inference pattern, then that pattern should be an effective adversarial attack. We observe that the attacks based on symmetry pattern generalize across all KGE models which indicates their sensitivity to this pattern. In the future, we aim to investigate hypotheses about the effect of input graph connectivity and existence of specific inference patterns in datasets. We note that such investigation of inference pattern attacks will likely be influenced by the choice of datasets. In this paper, we have used benchmark datasets for link prediction. While there are intuitive assumptions about the inference patterns on these datasets, there is no study that formally measures and characterizes the existence of these patterns. This makes it challenging to verify the claims made about the inductive abilities of KGE models, not only by our proposed attacks but also by new KGE models proposed in the literature. Thus, a promising step in understanding knowledge graph embeddings is to propose datasets and evaluation tasks that test varying degrees of specific inductive abilities. These will help evaluate new models and serve as a testbed for poisoning attacks. Furthermore, specifications of model performance on datasets with different inference patterns will improve the usability of KGE models in high-stake domains like healthcare and finance. In addition to understanding model behaviour, the sensitivity of state-of-art KGE models to simple inference patterns indicates that these models can introduce security vulnerabilities in pipelines that use knowledge graph embeddings. Thus, another promising direction for future work is towards mitigating the security vulnerabilities of KGE models. Some preliminary ideas for this research can look into adversarial training; or training an ensemble of different KGE scoring functions; or training an ensemble from subsets of the training dataset. Since our experiments show that state-of-art KGE models are sensitive to symmetry pattern, we call for future research to investigate neural architectures that generalize beyond symmetry even though their predictive performance for link prediction on benchmark datasets might not be the best. This research was conducted with the financial support of Accenture Labs and Science Foundation Ireland (SFI) at the ADAPT SFI Research Centre at Trinity College Dublin. The ADAPT SFI Centre for Digital Content Technology is funded by Science Foundation Ireland through the SFI Research Centres Programme and is co-funded under the European Regional Development Fund (ERDF) through Grant No. 13/RC/2106 P2. We study the problem of generating data poisoning attacks on KGE models. Data poisoning attacks identify the vulnerabilities in learning algorithms that could be exploited by an adversary to manipulate the model's behaviour (Joseph et al., 2019; Biggio and Roli, 2018). Such manipulation can lead to unintended model behaviour and failure. Identifying these vulnerabilities for KGE models is critical because of their increasing use in domains that need high stakes decision making like heathcare (Bendtsen and Petrovski, 2019) and finance (Hogan et al., 2020; Noy et al., 2019). In this way, our research is directed towards minimizing the negative consequences of deploying state-of-art KGE models in our society. This honours the ACM code of Ethics of contributing to societal well-being and acknowledging that all people are stakeholders in computing. At the same time, we aim to safeguard the KGE models against potential harm from adversaries and thus honour the ACM code of avoiding harm due to computing systems. Arguably, because we study vulnerabilities by attacking the KGE models, the proposed attacks can be used by an actual adversary to manipulate the model behaviour of deployed systems. This paradox of an arms race is universal across security research (Biggio and Roli, 2018). For our research, we have followed the principle of proactive security as recommended by Joseph et al. (2019) and Biggio and Roli (2018). As opposed to reactive security measures where learning system designers develop countermeasures after the system is attacked, a proactive approach anticipates such attacks, simulates them and designs countermeasures before the systems are deployed. Thus, by revealing the vulnerabilities of KGE models, our research provides an opportunity to fix them. Besides the use case of security, our research can be used in understanding the inductive abilities of KGE models, which are black-box and hard to interpret. We design attacks that rely on the inductive assumptions of a model to be able to deceive that model. Thus, theoretically, the effectiveness of attacks based on one inference pattern over another indicates the model's reliance on one inference pattern over another. However, as we discussed in our paper, realistically, it is challenging to make such claims about the inductive abilities of KGE models because the inference patterns in benchmark datasets are not well defined. Thus, we would encourage further work to evaluate our proposed attacks by designing benchmark tasks and datasets that measure specific inductive abilities of models. This will not only be useful for evaluating the proposed attacks here, but also for understanding the inductive abilities of existing KGE models. This in turn, can guide the community to design better models. In this direction, we encourage researchers proposing new KGE models to evaluate not only the predictive performance on benchmark datasets, but also the claims made on inductive abilities of these models and their robustness to violations of these implicit assumptions.
method objective objective result objective result abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective abstain abstain objective objective abstain objective abstain abstain abstain abstain objective method objective result objective objective abstain objective abstain other abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method method abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method method method abstain abstain method abstain abstain abstain abstain abstain method method method abstain other abstain abstain method method abstain method abstain abstain method abstain abstain abstain other method abstain abstain method method abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method other abstain abstain method abstain abstain method method method abstain abstain abstain abstain other abstain abstain abstain abstain abstain method abstain abstain method method method abstain abstain result abstain abstain abstain abstain abstain other abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain result abstain abstain abstain other other abstain other abstain other other other other other other other other other abstain other method objective objective abstain abstain result objective abstain method abstain objective abstain abstain abstain abstain abstain abstain objective other other method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method method abstain method abstain abstain abstain abstain