Poisoning Knowledge Graph Embeddings via Relation Inference Patterns (2021)

Abstract: 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. Specifically, 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.

## introduction knowledge graph embeddings (kge) are increasingly deployed in domains with high stake decision making like healthcare and finance @xcite , 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 @xcite but they cannot be applied directly to kge models. this is because they rely on gradients of * equal contribution by last authors. 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 @xcite attempt to address this problem through random sampling of candidate perturbations @xcite or through a vanilla auto-encoder that reconstructs discrete entities and relations from latent space @xcite . however, random sampling depends on the number of candidates being sampled and the auto-encoder proposed in @xcite 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 connectiv-ity 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 stateof-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. ## problem formulation for a set of entities e and a set of relations r, a knowledge graph is a collection of triples represented as @xmath0, r, o) | s, @xmath1, where s, r, o represent the subject, relation and object in a triple. a knowledge graph em- ## poisoning knowledge graph embeddings through relation inference patterns 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. definition 3.1. the symmetry pattern p s is expressed as ∀x, y : (x, r, y) ⇒ (y, r, x). here, the relation r is symmetric relation. 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 : @xmath2. for example, we can map the logic expression ∀x, y : (x, owns, y) ⇒ (y, is owned by, x) to the grounding (karl, owns, account42) ⇒ (account42, 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. ## evaluation 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 @xcite . 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 @xmath3. 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 @xcite 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 @xcite . we use the publicly available implementation and the default attack settings foot_1 . 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 foot_2 . ## conclusion 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-ofart 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.