Representing entities and relations in an embedding space is a well-studied approach for machine learning on relational data. Existing approaches, however, primarily focus on improving accuracy and overlook other aspects such as robustness and interpretability. In this paper, we propose adversarial modifications for link prediction models: identifying the fact to add into or remove from the knowledge graph that changes the prediction for a target fact after the model is retrained. Using these single modifications of the graph, we identify the most influential fact for a predicted link and evaluate the sensitivity of the model to the addition of fake facts. We introduce an efficient approach to estimate the effect of such modifications by approximating the change in the embeddings when the knowledge graph changes. To avoid the combinatorial search over all possible facts, we train a network to decode embeddings to their corresponding graph components, allowing the use of gradient-based optimization to identify the adversarial modification. We use these techniques to evaluate the robustness of link prediction models (by measuring sensitivity to additional facts), study interpretability through the facts most responsible for predictions (by identifying the most influential neighbors), and detect incorrect facts in the knowledge base. Knowledge graphs (KG) play a critical role in many real-world applications such as search, structured data management, recommendations, and question answering. Since KGs often suffer from incompleteness and noise in their facts (links), a number of recent techniques have proposed models that embed each entity and relation into a vector space, and use these embeddings to predict facts. These dense representation models for link prediction include tensor factorization [Nickel et al., 2011, Socher et al., 2013, Yang et al., 2015], algebraic operations [Bordes et al., 2011, 2013b, Dasgupta et al., 2018], multiple embeddings [Wang et al., 2014, Lin et al., 2015, Ji et al., 2015, Zhang et al., 2018], and complex neural models [Dettmers et al., 2018, Nguyen et al., 2018]. However, there are only a few studies [Kadlec et al., 2017, Sharma et al., 2018] that investigate the quality of the different KG models. There is a need to go beyond just the accuracy on link prediction, and instead focus on whether these representations are robust and stable, and what facts they make use of for their predictions. In this paper, our goal is to design approaches that minimally change the graph structure such that the prediction of a target fact changes the most after the embeddings are relearned , which we collectively call Completion Robustness and Interpretability via Adversarial Graph Edits (CRIAGE). First, we consider perturbations that remove a neighboring link for the target fact, thus identifying the most influential related fact, providing an explanation for the model's prediction. As an example, consider the excerpt from a KG in Figure 1a with two observed facts, and a target predicted fact that Princes Henriette is the parent of Violante Bavaria . Our proposed graph perturbation, shown in Figure 1b, identifies the existing fact that Fer-dinal Maria is the father of Violante Bavaria as the one when removed and model retrained, will change the prediction of Princes Henriette 's child. We also study attacks that add a new, fake fact into the KG to evaluate the robustness and sensitivity of link prediction models to small additions to the graph. An example attack for the original graph in Figure 1a, is depicted in Figure 1c. Such perturbations to the the training data are from a family of adversarial modifications that have been applied to other machine learning tasks, known as poisoning [Biggio et al., 2012, Corona et al., 2013, Biggio FerdinandMaria PrincessHenriette ViolanteBavaria isMarried h a s C h il d h a s C h il d target prediction (cid:104) s,r,o (cid:105) Since the setting is quite different from traditional adversarial attacks, search for link prediction adversaries brings up unique challenges. To find these minimal changes for a target link, we need to identify the fact that, when added into or removed from the graph, will have the biggest impact on the predicted score of the target fact. Unfortunately, computing this change in the score is expensive since it involves retraining the model to recompute the embeddings. We propose an efficient estimate of this score change by approximating the change in the embeddings using Taylor expansion. The other challenge in identifying adversarial modifications for link prediction, especially when considering addition of fake facts, is the combinatorial search space over possible facts, which is intractable to enumerate. We introduce an inverter of the original embedding model, to decode the embeddings to their corresponding graph components, making the search of facts tractable by performing efficient gradient-based continuous optimization. We evaluate our proposed methods through following experiments. First, on relatively small KGs, we show that our approximations are accurate compared to the true change in the score. Second, we show that our additive attacks can effectively reduce the performance of state of the art models [Yang et al., 2015, Dettmers et al., 2018] up to 27 . 3% and 50 . 7% in Hits@1 for two large KGs: WN18 and YAGO3-10. We also explore the utility of adversarial modifications in explaining the model predictions by presenting rule-like descriptions of the most influential neighbors. Finally, we use adversaries to detect errors in the KG, obtaining up to 55% accuracy in detecting errors. In this section, we briefly introduce some notations, and existing relational embedding approaches that model knowledge graph completion using dense vectors. In KGs, facts are represented using triples of subject, relation, and object, (cid:104) s, r, o (cid:105) , where s, o   , the set of entities, and r  R , the set of relations. To model the KG, a scoring function  :   R    R is learned to evaluate whether any given fact is true. In this work, we focus on multiplicative models of link prediction 1 , specifi-cally DistMult [Yang et al., 2015] because of its simplicity and popularity, and ConvE [Dettmers et al., 2018] because of its high accuracy. We can represent the scoring function of such methods as  ( s, r, o ) = f ( e s , e r )  e o , where e s , e r , e o  R d are embeddings of the subject, relation, and object respectively. In DistMult, f ( e s , e r ) = e s (cid:12) e r , where (cid:12) is element-wise multiplication operator. Similarly, in ConvE, f ( e s , e r ) is computed by a convolution on the concatenation of e s and e r . We use the same setup as Dettmers et al. [2018] for training, i.e., incorporate binary cross-entropy loss over the triple scores. In particular, for subject-relation pairs ( s, r ) in the training data G , we use binary y s,ro to represent negative and positive facts. Using the model's probability of truth as  (  ( s, r, o )) for (cid:104) s, r, o (cid:105) , the loss is defined as: L ( G ) = (cid:88) ( s,r ) (cid:88) o y s,ro log(  (  ( s, r, o ))) + (1  y s,ro ) log(1   (  ( s, r, o ))) . (1) Gradient descent is used to learn the embeddings e s , e r , e o , and the parameters of f , if any. For adversarial modifications on KGs, we first define the space of possible modifications. For a target triple (cid:104) s, r, o (cid:105) , we constrain the possible triples that we can remove (or inject) to be in the form of (cid:104) s (cid:48) , r (cid:48) , o (cid:105) i.e s (cid:48) and r (cid:48) may be different from the target, but the object is not. We analyze other forms of modifications such as (cid:104) s, r (cid:48) , o (cid:48) (cid:105) and (cid:104) s, r (cid:48) , o (cid:105) in appendices A.1 and A.2, and leave empirical evaluation of these modifications for future work. For explaining a target prediction, we are interested in identifying the observed fact that has the most influence (according to the model) on the prediction. We define influence of an observed fact on the prediction as the change in the prediction score if the observed fact was not present when the embeddings were learned. Previous work have used this concept of influence similarly for several different tasks [Kononenko et al., 2010, Koh and Liang, 2017]. Formally, for the target triple (cid:104) s, r, o (cid:105) and observed graph G , we want to identify a neighboring triple (cid:104) s (cid:48) , r (cid:48) , o (cid:105)  G such that the score  ( s, r, o ) when trained on G and the score  ( s, r, o ) when trained on G {(cid:104) s (cid:48) , r (cid:48) , o (cid:105)} are maximally different, i.e. argmax ( s (cid:48) ,r (cid:48) )  Nei ( o )  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) (2) where  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) =  ( s, r, o )   ( s, r, o ) , and Nei ( o ) = { ( s (cid:48) , r (cid:48) ) |(cid:104) s (cid:48) , r (cid:48) , o (cid:105)  G } . We are also interested in investigating the robustness of models, i.e., how sensitive are the predictions to small additions to the knowledge graph. Specifically, for a target prediction (cid:104) s, r, o (cid:105) , we are interested in identifying a single fake fact (cid:104) s (cid:48) , r (cid:48) , o (cid:105) that, when added to the knowledge graph G , changes the prediction score  ( s, r, o ) the most. Using  ( s, r, o ) as the score after training on G  {(cid:104) s (cid:48) , r (cid:48) , o (cid:105)} , we define the adversary as: argmax ( s (cid:48) ,r (cid:48) )  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) (3) where  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) =  ( s, r, o )   ( s, r, o ) . The search here is over any possible s (cid:48)   , which is often in the millions for most real-world KGs, and r (cid:48)  R . We also identify adversaries that increase the prediction score for specific false triple, i.e., for a target fake fact (cid:104) s, r, o (cid:105) , the adversary is argmax ( s (cid:48) ,r (cid:48) )   ( s (cid:48) ,r (cid:48) ) ( s, r, o ) , where  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) is defined as before. There are a number of crucial challenges when conducting such adversarial attack on KGs. First, evaluating the effect of changing the KG on the score of the target fact (  ( s, r, o ) ) is expensive since we need to update the embeddings by retraining the model on the new graph; a very time-consuming process that is at least linear in the size of G . Second, since there are many candidate facts that can be added to the knowledge graph, identifying the most promising adversary through search-based methods is also expensive. Specifically, the search size for unobserved facts is |  ||R| , which, for example in YAGO3-10 KG, can be as many as 4 . 5 M possible facts for a single target prediction. In this section, we propose algorithms to address mentioned challenges by (1) approximating the effect of changing the graph on a target prediction, and (2) using continuous optimization for the discrete search over potential modifications. We first study the addition of a fact to the graph, and then extend it to cover removal as well. To capture the effect of an adversarial modification on the score of a target triple, we need to study the effect of the change on the vector representations of the target triple. We use e s , e r , and e o to denote the embeddings of s, r, o at the solution of argmin L ( G ) , and when considering the adversarial triple (cid:104) s (cid:48) , r (cid:48) , o (cid:105) , we use e s , e r , and e o for the new embeddings of s, r, o , respectively. Thus e s , e r , e o is a solution to argmin L ( G  {(cid:104) s (cid:48) , r (cid:48) , o (cid:105)} ) , which can also be written as argmin L ( G ) + L ( (cid:104) s (cid:48) , r (cid:48) , o (cid:105) ) . Similarly, f ( e s , e r ) changes to f ( e s , e r ) after retraining. Since we only consider adversaries in the form of (cid:104) s (cid:48) , r (cid:48) , o (cid:105) , we only consider the effect of the attack on e o and neglect its effect on e s and e r . This assumption is reasonable since the adversary is connected with o and directly affects its embedding when added, but it will only have a secondary, negligible effect on e s and e r , in comparison to its effect on e o . Further, calculating the effect of the attack on e s and e r requires a third order derivative of the loss, which is not practical ( O ( n 3 ) in the number of parameters). In other words, we assume that e s (cid:39) e s and e r (cid:39) e r . As a result, to calculate the effect of the attack,  ( s, r, o )   ( s, r, o ) , we need to compute e o  e o , followed by:  ( s, r, o )   ( s, r, o ) = z s,r ( e o  e o ) (4) where z s,r = f ( e s , e r ) . We now derive an efficient computation for e o  e o . First, the derivative of the loss L ( G ) = L ( G ) + L ( (cid:104) s (cid:48) , r (cid:48) , o (cid:105) ) over e o is:  e o L ( G ) =  e o L ( G )  (1   ) z s (cid:48) ,r (cid:48) (5) where z s (cid:48) ,r (cid:48) = f ( e (cid:48) s , e (cid:48) r ) , and  =  (  ( s (cid:48) , r (cid:48) , o )) . We perform first order Taylor approximation of  e o L ( G ) to get: 0 (cid:39)  (1   ) z (cid:124) s (cid:48) ,r (cid:48) + ( H o +  (1   ) z (cid:124) s (cid:48) ,r (cid:48) z s (cid:48) ,r (cid:48) )( e o  e o ) (6) where H o is the d  d Hessian matrix for o , i.e., second order derivative of the loss w.r.t. e o , computed sparsely. Solving for e o  e o gives us, e o  e o = : (1   )( H o +  (1   ) z (cid:124) s (cid:48) ,r (cid:48) z s (cid:48) ,r (cid:48) )  1 z (cid:124) s (cid:48) ,r (cid:48) . Then, we compute the score change as:  ( s, r, o )   ( s, r, o ) = z s,r ( e o  e o ) (7) = z s,r ((1   )( H o +  (1   ) z (cid:124) s (cid:48) ,r (cid:48) z s (cid:48) ,r (cid:48) )  1 z (cid:124) s (cid:48) ,r (cid:48) ) . Similarly, we estimate the score change of (cid:104) s, r, o (cid:105) after removing (cid:104) s (cid:48) , r (cid:48) , o (cid:105) as:  z s,r ((1   )( H o +  (1   ) z (cid:124) s (cid:48) ,r (cid:48) z s (cid:48) ,r (cid:48) )  1 z (cid:124) s (cid:48) ,r (cid:48) ) . At convergence, after retraining, we expect  e o L ( G ) = 0 . In practice, H o is positive definite, making H o +  (1   ) z (cid:124) s (cid:48) ,r (cid:48) z s (cid:48) ,r (cid:48) positive definite as well, and invertible. Calculating this expression is efficient since H o is a d  d matrix ( d is the embedding dimension), and z s,r , z s (cid:48) ,r (cid:48)  R d . Using the approximations provided in the previous section, Eq. (7) and (4.1), we can use brute force enumeration to find the adversary (cid:104) s (cid:48) , r (cid:48) , o (cid:105) . This approach is feasible when removing an observed triple since the search space of such modifications is usually small; it is the number of observed facts that share the object with the target. On the other hand, finding the most influential unobserved fact s e s r e r f ( e s , e r ) (Fixed) z s , r Inverter Network s e s r e r Figure 2: Inverter Network The architecture of our inverter function that translate z s,r to its respective ( s,  r ) . to add requires search over a much larger space of all possible unobserved facts (that share the object). Instead, we identify the most influential unobserved fact (cid:104) s (cid:48) , r (cid:48) , o (cid:105) by using a gradient-based algorithm on vector z s (cid:48) ,r (cid:48) in the embedding space (reminder, z s (cid:48) ,r (cid:48) = f ( e (cid:48) s , e (cid:48) r ) ), solving the following continuous optimization problem in R d : argmax z s (cid:48) ,r (cid:48)  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) . After identifying the optimal z s (cid:48) ,r (cid:48) , we still need to generate the pair ( s (cid:48) , r (cid:48) ) . We design a network, shown in Figure 2, that maps the vector z s (cid:48) ,r (cid:48) to the entity-relation space, i.e., translating it into ( s (cid:48) , r (cid:48) ) . In particular, we train an auto-encoder where the encoder is fixed to receive the s and r as one-hot inputs, and calculates z s,r in the same way as the DistMult and ConvE encoders respectively (using trained embeddings). The decoder is trained to take z s,r as input and produce s and r , essentially inverting f and the embedding layers. As our decoder, for DistMult, we pass z s,r through a linear layer and then use two other linear layers for the subject and the relation separately, providing one-hot vectors as  s and  r . For ConvE, we pass z s,r through a decon-volutional layer, and then use the same architecture as the DistMult decoder. Although we could use maximum inner-product search [Shrivastava and Li, 2014] for DistMult instead of our defined inverter function, we are looking for a general approach that works across multiple models. We evaluate the performance of our inverter networks (one for each model/dataset) on correctly recovering the pairs of subject and relation from the test set of our benchmarks, given the z s,r . The accuracy of recovered pairs (and of each argument) WordNet YAGO DistMult ConvE DistMult ConvE Recover s 93.4 96.1 97.2 98.1 Recover r 91.3 95.3 99.0 99.6 Recover { s,r } 89.5 94.2 96.4 98.0 Table 1: Inverter Functions Accuracy , we calculate the accuracy of our inverter networks in correctly recovering the pairs of subject and relation from the test set of our benchmarks. is given in Table 1. As shown, our networks achieve a very high accuracy, demonstrating their ability to invert vectors z s,r to { s, r } pairs. Datasets To evaluate our method, we conduct several experiments on four widely used KGs. To validate the accuracy of the approximations, we use smaller sized Kinship and Nations KGs for which we can make comparisons against more expensive but less approximate approaches. For the remaining experiments, we use YAGO3-10 and WN18 KGs, which are closer to real-world KGs in their size and characteristics (see Table 2). Models We implement all methods using the same loss and optimization for training, i.e., Ada-Grad and the binary cross-entropy loss. We use validation data to tune the hyperparameters and use a grid search to find the best hyperparameters, such as regularization parameter, and learning rate of the gradient-based method. To capture the effect of our method on link prediction task, we study the change in commonly-used metrics for evaluation in this task: mean reciprocal rank (MRR) and Hits@K. Further, we use the same hyperparameters as in Dettmers et al. [2018] for training link prediction models for these knowledge graphs. Influence Function We also compare our method with influence function (IF) [Koh and Liang, 2017]. The influence function approximates the effect of upweighting a training sample on the loss for a specific test point. We use IF to approximate the 20 40 60 80 100 Number of entities 0 200 400 600 800 1000 1200 1400 1600 T i m e ( s ) IF (d=5) IF (d=10) CRIAGE (d=5) CRIAGE (d=10) Figure 3: Influence function vs CRIAGE . change in the loss after removing a triple as: I up,loss ( (cid:104) s (cid:48) , r (cid:48) , o (cid:105) , (cid:104) s, r, o (cid:105) ) =   L ( (cid:104) s, r, o (cid:105) ,   ) (cid:124) H  1     L ( (cid:104) s (cid:48) , r (cid:48) , o (cid:105) ,   ) (9) where (cid:104) s (cid:48) , r (cid:48) , o (cid:105) and (cid:104) s, r, o (cid:105) are training and test samples respectively,   represents the optimum parameters and L ( (cid:104) s, r, o (cid:105) ,   ) represents the loss function for the test sample (cid:104) s, r, o (cid:105) . Influence function does not scale well, so we only compare our method with IF on the smaller size KGs. We evaluate CRIAGE by (6.1) comparing CRIAGE estimate with the actual effect of the attacks, (6.2) studying the effect of adversarial attacks on evaluation metrics, (6.3) exploring its application to the interpretability of KG representations, and (6.4) detecting incorrect triples. To evaluate the quality of our approximations and compare with influence function (IF), we conduct leave one out experiments. In this setup, we take all the neighbors of a random target triple as candidate modifications, remove them one at a time, retrain the model each time, and compute the exact change in the score of the target triple. We can use the magnitude of this change in score to rank the candidate triples, and compare this exact ranking with ranking as predicted by: CRIAGE-Remove, influence function with and without Hessian matrix, and the original model score (with the intuition that facts that the model is most confident of will have Methods Nations Kinship Adding Removing Adding Removing         Ranking Based on Score 0.03 0.02 -0.01 -0.01 -0.09 -0.06 0.01 0.01 Influence Function without Hessian 0.15 0.12 0.12 0.1 0.77 0.71 0.77 0.71 CRIAGE (Brute Force) 0.95 0.84 0.94 0.85 0.99 0.97 0.99 0.95 Influence Function 0.99 0.95 0.99 0.96 0.99 0.98 0.99 0.98 Table 3: Ranking modifications by their impact on the target . the largest impact when removed). Similarly, we evaluate CRIAGE-Add by considering 200 random triples that share the object entity with the target sample as candidates, and rank them as above. The average results of Spearman's  and Kendall's  rank correlation coefficients over 10 random target samples is provided in Table 3. CRIAGE performs comparably to the influence function, confirming that our approximation is accurate. Influence function is slightly more accurate because they use the complete Hessian matrix over all the parameters, while we only approximate the change by calculating the Hessian over e o . The effect of this difference on scalability is dramatic, constraining IF to very small graphs and small embedding dimensionality ( d  10 ) before we run out of memory. In Figure 3, we show the time to compute a single adversary by IF compared to CRIAGE, as we steadily grow the number of entities (randomly chosen subgraphs), averaged over 10 random triples. As it shows, CRIAGE is mostly unaffected by the number of entities while IF increases quadratically. Considering that real-world KGs have tens of thousands of times more entities, making IF unfeasible for them. Now we evaluate the effectiveness of CRIAGE to successfully attack link prediction by adding false facts. The goal here is to identify the attacks for triples in the test data, and measuring their effect on MRR and Hits@ metrics (ranking evaluations) after conducting the attack and retraining the model. Since this is the first work on adversarial attacks for link prediction, we introduce several baselines to compare against our method. For finding the adversarial fact to add for the target triple (cid:104) s, r, o (cid:105) , we consider two baselines: 1) choosing a random fake fact (cid:104) s (cid:48) , r (cid:48) , o (cid:105) ( Random Attack ); 2) finding ( s (cid:48) , r (cid:48) ) by first calculating f ( e s , e r ) and then feeding  f ( e s , e r ) to the decoder of the inverter function ( Opposite Attack ). In addition to CRIAGE-Add, we introduce two other alternatives of our method: (1) CRIAGE-FT , that uses CRIAGE to increase the score of fake fact over a test triple, i.e., we find the fake fact the model ranks second after the test triple, and identify the adversary for them, and (2) CRIAGE-Best that selects between CRIAGE-Add and CRIAGE-FT attacks based on which has a higher estimated change in score. All-Test The result of the attack on all test facts as targets is provided in the Table 4. CRIAGE-Add outperforms the baselines, demonstrating its ability to effectively attack the KG representations. It seems DistMult is more robust against random attacks, while ConvE is more robust against designed attacks. CRIAGE-FT is more effective than CRIAGE-Add since changing the score of a fake fact is easier than of actual facts; there is no existing evidence to support fake facts. We also see that YAGO3-10 models are more robust than those for WN18. Looking at sample attacks (provided in Appendix A.4), CRIAGE mostly tries to change the type of the target object by associating it with a subject and a relation for a different entity type. Uncertain-Test To better understand the effect of attacks, we consider a subset of test triples that 1) the model predicts correctly, 2) difference between their scores and the negative sample with the highest score is minimum. This Uncertain-Test subset contains 100 triples from each of the original Models YAGO3-10 WN18 All-Test Uncertain-Test All-Test Uncertain-Test MRR Hits@1 MRR Hits@1 MRR Hits@1 MRR Hits@1 D i s t M u l t DistMult 0.458 37 (0) 1.0 100 (0) 0.938 93.1 (0) 1.0 100 (0) + Adding Random Attack 0.442 34.9 (-2.1) 0.91 87.6 (-12.4) 0.926 91.1 (-2) 0.929 90.4 (-9.6) + Adding Opposite Attack 0.427 33.2 (-3.8) 0.884 84.1 (-15.9) 0.906 87.3 (-5.8) 0.921 91 (-9) + CRIAGE-Add 0.379 29.1 (-7.9) 0.71 58 (-42) 0.89 86.4 (-6.7) 0.844 81.2 (-18.8) + CRIAGE-FT 0.387 27.7 (-9.3) 0.673 50.5 (-49.5) 0.86 79.2 (-13.9) 0.83 74.5 (-25.5) + CRIAGE-Best 0.372 26.9 (-10.1) 0.658 49.3 (-50.7) 0.838 77.9 (-15.2) 0.814 72.7 (-27.3) C o n v E ConvE 0.497 41.2 (0) 1.0 100 (0) 0.94 93.3 (0) 1.0 100 (0) + Adding Random Attack 0.474 38.4 (-2.8) 0.889 83 (-17) 0.921 90.1 (-3.2) 0.923 89.7 (-10.3) + Adding Opposite Attack 0.469 38 (-3.2) 0.874 81.9 (-18.1) 0.915 88.9 (-4.4) 0.908 88.1 (-11.9) + CRIAGE-Add 0.454 36.9 (-4.3) 0.738 61.5 (-38.5) 0.897 87.8 (-5.5) 0.895 87.6 (-12.4) + CRIAGE-FT 0.441 33.2 (-8) 0.703 57.4 (-42.6) 0.865 80 (-13.3) 0.874 79.5 (-20.5) + CRIAGE-Best 0.423 31.9 (-9.3) 0.677 54.8 (-45.2) 0.849 79.1 (-14.2) 0.858 78.4 (-21.6) Table 4: Robustness of Representation Models , the effect of adversarial attack on link prediction task. test sets, and we provide results of attacks on this data in Table 4. The attacks are much more effective in this scenario, causing a considerable drop in the metrics. Further, in addition to CRIAGE signifi-cantly outperforming other baselines, they indicate that ConvE's confidence is much more robust. Relation Breakdown We perform additional analysis on the YAGO3-10 dataset to gain a deeper understanding of the performance of our model. As shown in Figure 4, both DistMult and ConvE provide a more robust representation for isAli-atedTo and isConnectedTo relations, demonstrating the confidence of models in identifying them. Moreover, the CRIAGE affects DistMult more in playsFor and isMarriedTo relations while affecting ConvE more in isConnectedTo relations. To be able to understand and interpret why a link is predicted using the opaque, dense embeddings, we need to find out which part of the graph was most influential on the prediction. To provide such explanations for each predictions, we identify the most influential fact using CRIAGE-Remove. Instead of focusing on individual predictions, we aggregate the explanations over the whole dataset for each relation using a simple rule extraction technique: we Methods (cid:104) s (cid:48) , r (cid:48) , o (cid:105) Noise (cid:104) s (cid:48) , r, o (cid:105) Noise Hits@1 Hits@2 Hits@1 Hits@2 Random 19.7 39.4 19.7 39.4 Lowest 16 37 26 47 CRIAGE 42 62 55 76 Table 6: Error Detection Accuracy in the neighborhood of 100 chosen samples. find simple patterns on subgraphs that surround the target triple and the removed fact from CRIAGE-Remove, and appear more than 90% of the time. We only focus on extracting length2 horn rules, i.e., R 1 ( a, c )  R 2 ( c, b )  R ( a, b ) , where R ( a, b ) is the target and R 2 ( c, b ) is the removed fact. Table 5 shows extracted YAGO3-10 rules that are common to both models, and ones that are not. The rules show several interesting inferences, such that hasChild is often inferred via married parents, and isLocatedIn via transitivity. There are several differences in how the models reason as well; DistMult often uses the hasCapital as an intermediate step for isLocatedIn , while ConvE incorrectly uses isNeighbor . We also compare against rules extracted by Yang et al. [2015] for YAGO3-10 that utilizes the structure of DistMult: they require do-main knowledge on types and cannot be applied to ConvE. Interestingly, the extracted rules contain all the rules provided by CRIAGE, demonstrating that CRIAGE can be used to accurately interpret models, including ones that are not interpretable, such as ConvE. These are preliminary steps toward interpretability of link prediction models, and we leave more analysis of interpretability to future work. Here, we demonstrate another potential use of adversarial modifications: finding erroneous triples in the knowledge graph. Intuitively, if there is an error in the graph, the triple is likely to be inconsistent with its neighborhood, and thus the model should put least trust on this triple. In other words, the error triple should have the least influence on the model's prediction of the training data. Formally, to find the incorrect triple (cid:104) s (cid:48) , r (cid:48) , o (cid:105) in the neighborhood of the train triple (cid:104) s, r, o (cid:105) , we need to find the triple (cid:104) s (cid:48) , r (cid:48) , o (cid:105) that results in the least change  ( s (cid:48) ,r (cid:48) ) ( s, r, o ) when removed from the graph. triples into the graph, and measure the ability of CRIAGE to detect the errors using our optimization. We consider two types of incorrect triples: 1) incorrect triples in the form of (cid:104) s (cid:48) , r, o (cid:105) where s (cid:48) is chosen randomly from all of the entities, and 2) incorrect triples in the form of (cid:104) s (cid:48) , r (cid:48) , o (cid:105) where s (cid:48) and r (cid:48) are chosen randomly. We choose 100 random triples from the observed graph, and for each of them, add an incorrect triple (in each of the two scenarios) to its neighborhood. Then, after retraining DistMult on this noisy training data, we identify error triples through a search over the neighbors of the 100 facts. The result of choosing the neighbor with the least influence on the target is provided in the Table 6. When compared with baselines that randomly choose one of the neighbors, or assume that the fact with the lowest score is incorrect, we see that CRIAGE outperforms both of these with a considerable gap, obtaining an accuracy of 42% and 55% in detecting errors. Learning relational knowledge representations has been a focus of active research in the past few years, but to the best of our knowledge, this is the first work on conducting adversarial modifications on the link prediction task. Knowledge graph embedding There is a rich literature on representing knowledge graphs in vector spaces that differ in their scoring functions [Wang et al., 2017, Goyal and Ferrara, 2018, Fooshee et al., 2018]. Although CRIAGE is primarily applicable to multiplicative scoring functions [Nickel et al., 2011, Socher et al., 2013, Yang et al., 2015, Trouil-lon et al., 2016], these ideas apply to additive scoring functions [Bordes et al., 2013a, Wang et al., 2014, Lin et al., 2015, Nguyen et al., 2016] as well, as we show in Appendix A.3. Furthermore, there is a growing body of literature that incorporates an extra types of evidence for more informed embeddings such as numerical values [Garcia-Duran and Niepert, 2017], images [Ooro-Rubio et al., 2017], text [Toutanova et al., 2015, 2016, Tu et al., 2017], and their combinations [Pezeshkpour et al., 2018]. Using CRIAGE, we can gain a deeper understanding of these methods, especially those that build their embeddings wit hmultiplicative scoring functions. Interpretability and Adversarial Modification There has been a significant recent interest in conducting an adversarial attacks on different machine learning models [Biggio et al., 2014, Papernot et al., 2016, Dong et al., 2017, Zhao et al., 2018a,b, Brunet et al., 2018] to attain the interpretability, and further, evaluate the robustness of those models. Koh and Liang [2017] uses influence function to provide an approach to understanding black-box models by studying the changes in the loss occurring as a result of changes in the training data. In addition to incorporating their established method on KGs, we derive a novel approach that differs from their procedure in two ways: (1) instead of changes in the loss, we consider the changes in the scoring function, which is more appropriate for KG representations, and (2) in addition to searching for an attack, we introduce a gradient-based method that is much faster, especially for adding an attack triple (the size of search space make the influence function method infeasible). Previous work has also considered adversaries for KGs, but as part of training to improve their representation of the graph [Minervini et al., 2017, Cai and Wang, 2018]. Adversarial Attack on KG Although this is the first work on adversarial attacks for link prediction, there are two approaches [Dai et al., 2018, Zgner et al., 2018] that consider the task of adversarial attack on graphs. There are a few fundamental differences from our work: (1) they build their method on top of a path-based representations while we focus on embeddings, (2) they consider node classifi-cation as the target of their attacks while we attack link prediction, and (3) they conduct the attack on small graphs due to restricted scalability, while the complexity of our method does not depend on the size of the graph, but only the neighborhood, allowing us to attack real-world graphs. Motivated by the need to analyze the robustness and interpretability of link prediction models, we present a novel approach for conducting adversarial modifications to knowledge graphs. We introduce CRIAGE, completion robustness and interpretability via adversarial graph edits: identifying the fact to add into or remove from the KG that changes the prediction for a target fact. CRIAGE uses (1) an estimate of the score change for any target triple after adding or removing another fact, and (2) a gradient-based algorithm for identifying the most influential modification. We show that CRIAGE can effectively reduce ranking metrics on link prediction models upon applying the attack triples. Further, we incorporate the CRIAGE to study the interpretability of KG representations by summarizing the most influential facts for each relation. Finally, using CRIAGE, we introduce a novel automated error detection method for knowledge graphs. We have release the open-source implementation of our models at: https://pouyapez.github.io/criage . We would like to thank Matt Gardner, Marco Tulio Ribeiro, Zhengli Zhao, Robert L. Logan IV, Dheeru Dua and the anonymous reviewers for their detailed feedback and suggestions. This work is supported in part by Allen Institute for Artificial Intelligence (AI2) and in part by NSF awards #IIS-1817183 and #IIS-1756023. The views expressed are those of the authors and do not reflect the official policy or position of the funding agencies.
abstain abstain objective method method method method abstain abstain other abstain abstain objective objective abstain objective objective abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain method other other method abstain other other method other method other other objective method method method method abstain method abstain method method abstain method abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain abstain method other abstain other other abstain method method abstain abstain abstain abstain abstain abstain abstain abstain other method abstain method abstain method method method method abstain abstain abstain method method method method method method method abstain method abstain method other method abstain abstain abstain other abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain other result abstain abstain abstain abstain result abstain abstain other result abstain abstain abstain abstain abstain result abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain other abstain abstain abstain result objective other other other method other other other other other method objective method abstain result objective objective other other other other