Adversarial Attacks on Knowledge Graph Embeddings via Instance Attribution Methods (2021)

Abstract: Despite the widespread use of Knowledge Graph Embeddings (KGE), little is known about the security vulnerabilities that might disrupt their intended behaviour. We study data poisoning attacks against KGE models for link prediction. These attacks craft adversarial additions or deletions at training time to cause model failure at test time. To select adversarial deletions, we propose to use the model-agnostic instance attribution methods from Interpretable Machine Learning, which identify the training instances that are most influential to a neural model’s predictions on test instances. We use these influential triples as adversarial deletions. We further propose a heuristic method to replace one of the two entities in each influential triple to generate adversarial additions. Our experiments show that the proposed strategies outperform the state-of-art data poisoning attacks on KGE models and improve the MRR degradation due to the attacks by up to 62% over the baselines.

## introduction knowledge graph embeddings (kge) are the stateof-art models for relational learning on large scale knowledge graphs (kg). they drive enterprise products ranging from search engines to social networks to e-commerce @xcite . however, the analysis of their security vulnerabilities has received little attention. identifying these vulnerabilities is especially important for high-stake domains like healthcare and finance that employ kge models to make critical decisions @xcite . we study the security vulnerabilities of kge models through data poisoning attacks @xcite that aim to degrade the predictive performance of learned kge models by adding or removing triples to the input training graph. in this work, we propose to use the modelagnostic instance attribution methods from interpretable machine learning @xcite to select adversarial deletions and additions against kge models. instance attribution methods identify the training instances that are influential to model predictions, that is, deleting the instances from the training data would considerably change the model parameters or predictions. these methods are widely used to generate post-hoc examplebased explanations for deep neural networks on images @xcite @xcite ) and text @xcite @xcite . since the kge models have relatively shallow neural architectures and the instance attribution metrics are independent of the black-box models and the input domain, they are a promising approach to estimate the influence of training triples on the kge model predictions. yet, despite their promise, they have not been used on kge models so far. we use the instance attribution methods to address the challenge of measuring the impact of a candidate adversarial deletion on the model predictions. we focus on the adversarial goal of degrading the kge model prediction on a given target triple. to achieve this goal, we use three types of instance attribution methods -instance similarity that compares the feature representations of target and training triples @xcite ; gradient similarity that compares the gradients of model's loss function due to target and training triples @xcite ; and influence function (koh and liang, 2017) which is a principled approach from the robust statistics to estimate the effect of removing a training triple on the kge model's predictions. using these metrics, we select the most influential training triple for adversarial deletion. using the influential triple, we further select adversarial addition by replacing one of the two entities of the influential triple with the most dissimilar entity in the embedding space. the intuition behind this step is to add a triple that would reduce the influence of the influential triple. this solution also overcomes the scalability challenge for adversarial additions by comparing only the entity embeddings to select the replacement. figure 1 shows an example of the proposed adversarial deletions and additions against kge models for fraud detection. we evaluate the proposed attacks for four kge models -distmult, complex, conve and transe on two benchmark datasets -wn18rr and fb15k-237. our results show that instance attribution metrics achieve significantly better performance than all state-of-art attacks for both adversarial additions and deletions on three out of four models; and better or equivalent performance on one model. we find that even simple metrics based on instance similarity outperform the state-of-the-art poisoning attacks and are as effective as the computationally expensive influence function. thus, the main contribution of our research is a collection of effective adversarial deletion and addition strategies based on instance attribution methods against kge models. ## knowledge graph embeddings a knowledge graph (kg), is a set of triples t ⊆ e × r × e where each triple encodes the relationship r as a typed link between the subject entity s and the object entity o, i.e. t := {t := (s, r, o) | s, @xmath0. here, e is the set of entities and r is the set of relations in the knowledge graph. large scale kgs are often curated automatically from the user content or from the web and thus are incomplete in practice. to predict the missing links in a kg, the state-of-art method is to learn low dimensional feature vectors for entities and relations in the graph and use them to score the links. these feature vectors are called knowledge graph embeddings (kge) and denoted as θ := {e, r} where @xmath1, @xmath2. scoring functions: kge models differ from each other by their scoring functions f : @xmath3, relation and object embeddings to assign a score to the triple, i.e. f t := f (e s , e r , e o ) where e s , e @xmath4. these scoring functions are used to categorize the models as additive or multiplicative @xcite . additive models apply relation-specific translation from the subject embedding to the object embedding. the scoring function for such models is expressed as training: since the kgs only contain positive triples; to train the kge model, synthetic negative samples @xmath5. that is, for each positive triple t := (s, r, o), the set of negative samples is t := {(s , r, o) ∪ (s, r, o )}. the training objective is to learn the embeddings that score positive triples existing in the kg higher than the negative triples generated synthetically. to achieve this, a triple-wise loss function l(t, θ) := ℓ(t, θ) + @xmath6, θ) is minimized. thus, the optimal parameters θ learned by the model are defined by θ := arg min θ @xmath7, θ). further details on kge loss functions and negative sampling strategies are available in @xcite . ## poisoning knowledge graph embeddings via instance attribution we consider an adversarial attacker that aims to degrade the kge model's predictive performance on a set of missing triples that have been ranked highly plausible by the model. we denote these target triples as z := {z := (z s , z r , z o )}. since the predicted ranks are based on the predicted scores; to reduce the predicted rank of a target triple, we craft perturbations to the training data that aim to reduce the predicted score of the target triple. threat model: we use the same threat model as the state-of-art poisoning attacks on kge models @xcite . we focus on the white-box attack setting where the attacker has full knowledge of the victim model architecture and access to the learned embeddings. however, they cannot perturb the architecture or the embeddings directly; but only through perturbations in the training data. we study both adversarial additions and adversarial deletions. in both settings, the attacker is restricted to making only one edit in the neighbourhood of the target triple. the neighbourhood of the target triple z := (z s , z r , z o ) is the set of triples that have the same subject or the same object as the target triple, i.e. x := {x := (x s , x r , x o ) | x @xmath8, z o } ∨ x @xmath9, z o }}. ## evaluation we evaluate the effectiveness of the proposed attack strategies in degrading the kge model's predictions on target triples at test time. we follow the state-of-art protocol to evaluate poisoning attacks @xcite ) -we train a victim kge model on the original dataset; generate adversarial deletions or additions using one of the attacks; perturb the original dataset; and train a new kge model on the perturbed dataset. the hyperparameters for victim and poisoned kge models are same. we evaluate our attacks on four state-of-art kge models -distmult, complex, conve and transe on two publicly available 1 benchmark datasets -1 https://github.com/timdettmers/conve wn18rr and fb15k-237. to be able to evaluate the effectiveness of attacks in degrading the predictive performance, we select a subset of the benchmark test triples that has been ranked highest (@xmath10. from this subset, we randomly sample 100 triples as the target triples. this is to avoid the expensive hessian inverse estimation in the if metric for a large number of target triples (for each target triple, this estimation requires one training epoch). the source code implementation of our experiments is available at https://github.com/ perubhardwaj/attributionattack . baselines: we evaluate our attacks against baseline methods based on random edits and the stateof-art poisoning attacks. random_n adds or removes a random triple from the neighbourhood of the target triple. random_g adds or removes a random triple globally and is not restricted to the target's neighbourhood. direct-del and direct-add are the adversarial deletion and addition attacks proposed in @xcite . criage is the poisoning attack from @xcite and is a baseline for both deletions and additions. gr (gradient rollback) @xcite uses influence estimation to provide post-hoc explanations for kge models and can also be used to generate adversarial deletions. thus, we include this method as a baseline for adversarial deletions. the attack evaluations in @xcite ; @xcite ; @xcite differ with respect to the definition of their neighbourhood. thus, to ensure fair evaluation, we implement all methods with the same neighbourhoodtriples that are linked to the subject or object of the target triple (section 3). we use the publicly available implementations for criage foot_0 and gradient rollback foot_1 and implement direct-del and direct-add ourselves. further details on datasets, implementation of kge models, baselines and computing resources is available in appendix a and b. results: for wn18rr and fb15k-237 respectively, tables 2 and 3 show the degradation in mrr and hits@1 due to adversarial deletions; and tables 4 and 5 due to adversarial additions for stateof-art kge models. below we discuss different patterns in these results. we also discuss runtime efficiency of the attack methods in appendix c.1. ## conclusion we propose data poisoning attacks against kge models using instance attribution methods and demonstrate that the proposed attacks outperform the state-of-art attacks. we observe that the attacks are particularly effective when the kge model relies on few training instances to make predictions, i.e. when the input graph is sparse. we also observe that shallow neural architectures like distmult, complex and transe are vulnerable to naive attacks based on instance similarity. these models have shown competitive predictive performance by proper hyperparameter tuning @xcite , making them promising candidates for use in production pipelines. but our research shows that these performance gains can be brittle. this calls for improved kge model evaluation that accounts for adversarial robustness in addition to predictive performance. additionally, as in bhardwaj (2020); bhardwaj et al. (2021), we call for future proposals to defend against the security vulnerabilities of kge models. some promising directions might be to use adversarial training techniques or train ensembles of models over subsets of training data to prevent the model predictions being influenced by a few triples only. specification of the model failure modes through adversarial robustness certificates will also improve the usability of kge models in high-stake domains like healthcare and finance.