Adversarial Attack against Cross-lingual Knowledge Graph Alignment (2021)

Abstract: Recent literatures have shown that knowledge graph (KG) learning models are highly vulnerable to adversarial attacks. However, there is still a paucity of vulnerability analyses of cross-lingual entity alignment under adversarial attacks. This paper proposes an adversarial attack model with two novel attack techniques to perturb the KG structure and degrade the quality of deep cross-lingual entity alignment. First, an entity density maximization method is employed to hide the attacked entities in dense regions in two KGs, such that the derived perturbations are unnoticeable. Second, an attack signal amplification method is developed to reduce the gradient vanishing issues in the process of adversarial attacks for further improving the attack effectiveness.

## introduction today, multilingual knowledge graphs (kgs), such as wordnet @xcite , dbpedia @xcite , yago @xcite , and concept-net @xcite , are becoming essential sources of knowledge for various ai-related applications, e.g., personal assistants, medical diagnosis, and online question answering. cross-lingual entity alignment between multilingual kgs is a powerful tool that align the same entities in different monolingual kgs together, automatically synchronize different language-specific kgs and revolutionize the understanding of these ubiquitous multilingual kgs in a transformative manner @xcite @xcite . unfortunately, real-world kgs are typically noisy due to two main reasons: (1) massive fake information injected by malicious parties and users on online encyclopedia websites (e.g., wikipedia (wik) and answers.com (ans)), social networks (e.g., twitter and facebook), online communities (e.g., reddit and yahoo answers), news websites, and search engines that usually serve as data sources of the kgs; and (2) direct adversarial attacks on the kgs. google knowledge graph has been criticized for providing answers without source attribution or citation, and thus undermines people's ability to verify information and to develop well-informed opinions @xcite . recent studies have shown that kg learning models remain highly sensitive to adversarial attacks, i.e., carefully designed small perturbations in kgs can cause the models to produce wrong prediction results, including knowledge graph embedding @xcite @xcite @xcite and knowledge graph-based dialogue generation @xcite . however, existing techniques focus on the adversarial attacks on single kg learning tasks. these techniques cannot be directly utilized to attack the cross-lingual entity alignment models, as they have to analyze relations within and across kgs. two critical questions still keep unsolved: (1) can small perturbations on kgs defeat cross-lingual entity alignment models? (2) how to design effective and unnoticeable perturbations against cross-lingual entity alignment? the majority of cross-lingual entity alignment techniques aim to train the model by minimizing the distance between pre-aligned entity pairs in training data, such that the corresponding entity embeddings across kgs are close to each other, and the entity pairs with the smallest distance in test data are output as alignment results @xcite @xcite @xcite @xcite . in terms of the distribution of entities in a kg, one idea of perturbing an entity unobtrusively is to move the entity to a dense region in the kg with many similar entities by adding/deleting relations to/from it is able to move it to a dense region in the kg with many similar entities, such that it is non-trivial to recognize the modified entity in the dense region with many similar entities. existing gradient-based adversarial attack methods @xcite search for the weakest input features to attack by calculating the loss gradient. however, the vanishing gradient problem is often encountered when training neural networks with poor backward signal propagation and thus leads to the attack failures @xcite . can we enhance the attack signal propagation for improving the attack effectiveness? in this work, an entity density estimation and maximization method is employed to first estimate the distribution of entities in kgs. based on the estimated kg distributions, the entities to be attacked are then moved to dense regions in two kgs by maximizing their densities. the attacked entities are hidden in dense regions in two kgs, such that they are surrounded by many neighbors in dense regions as well as indistinguishable from these neighbors. in addition, the surrounding of many neighbors makes it difficult to identify the correctly aligned entity pairs among many similar candidate entities. we comprehensively study how poor signal propagation on neural networks leads to vanishing gradients in adversarial attacks over cross-lingual entity alignment. an attack signal amplification method is developed to secure informative attack signals with both well-conditioned jacobian and competent signal propagation from the alignment loss. this reduces the gradient vanishing issues in the process of adversarial attacks for further improving the attack effectiveness. extensive experiments over real-world kg datasets validate the superior attack performance of the eaa model against several state-of-the-art cross-lingual entity alignment models. to our best knowledge, this work is the first to study adversarial attacks on cross-lingual entity alignment. ## unnoticeable adversarial attacks existing gcn-based entity alignment methods often initialize entity features with random initialization or pre-trained word embeddings of entity names and utilize adjacency matrix of kgs to learn the entity embeddings @xcite @xcite . thus, the embedding of an entity mainly depends on the embeddings of its neighbor entities. in order to modify the embedding of a target entity for the purpose of adversarial attacks, we need to remove some positive (i.e., existing) relations and add some negative (i.e., non-existing) relations between the target entity and its neighbors in adjacency matrix, and thus degrade the accuracy of entity embedding and alignment. we use the i th row of adjacency matrix a k (i.e., a k i ) to represent structure features of each entity e k as shown in figure 1 , assuming that e 1 i and e 2 j are pre-aligned entity embeddings, if we hide an entity e 1 i in a dense region with many similar e 1 k s by modifying its associated relations, then the surrounding of many e 1 k s makes it difficult to differentiate e 1 i from many similar e 1 k s and identify the correctly aligned entity pairs e 1 the vector form f (x k ) can be rewritten as an element form, where x k j denotes the j th dimension in we make use of a greedy search method to determine bandwidths in the kernel density estimation method. for a non-trivial/trivial dimension j, updating the bandwidth b j will have a strong/weak influence over f (x k ). we greedily reduce b j with a sequence b 0 , b 0 s, b 0 s 2 , • • • for a parameter 0 < @xmath0, until b j is smaller than a certain threshold τ j , to validate whether a small update in b j is able to lead to a large update in f (x k ). according to the estimated bandwidth b by algorithm 1, we can calculate density f (x k ) of x k in eq.( 3 ). the perturbation process is to maximize the following attack loss l a for producing unnoticeable perturbations, in terms of the estimations f (x 1 ) and f (x 2 ) in two kgs g 1 and g 2 . we leverage the projected gradient descent (pgd) technique @xcite to produce perturbed adjacency matrices â1 and â2 of two kgs g 1 and g 2 . t+1) and (a 2 j ) (t+1) denotes the perturbations of a 1 i and a 2 j derived at step t. specifies the budget of allowed perturbed relations for each attacked entity. it is obvious that the gradient is determined with both the signal and the jacobian together. the situation that either the signal has saturating gradient or the jacobian is insignificant is able to result in vanishing gradients in all singular values of a neural network's inputoutput jacobian matrix concentrate near 1 is a property known as dynamical isometry @xcite . ensuring the mean squared singular value of a network's input-output jacobian is o(1) is essential for avoiding the exponential vanishing or explosion of gradients. we leverage the dynamical isometry theory for improving the effectiveness of the pgd adversarial attacks. concretely, a neural network is dynamical isometry if all singular values λ ir of the jacobian j i are close to 1, i.e., 1 -λ @xmath1, @xmath2, • • • , min{n 1 , n 2 }} and a small positive number ξ ≈ 0. in our problem, when the jacobian matrix j i is dynamical isometry, the signal φ (e 1 i ) t , e 2 j backpropagates isometrically over the neural network and maintains the norm and all angles between vectors. intuitively, if we select a good attack signal amplification factor α to amplify e 1 in addition, a good α should guarantee the relative order of the network's output logits invariant, to ensure the decision boundary of entity alignment unchanged. we rewrite the gradients with α as follows. when α is close to ∞, the alignment signal φ (ẽ 1 i ) t , ẽ2 j approaches zero and thus the vanishing gradient problem is encountered in adversarial attacks. in addition, all singular values of αj i are equal to zeros if α = 0. therefore, a desired α for avoiding the exponential vanishing of gradients should stand in between 0 and ∞, in order to guarantee the signal φ (ẽ 1 i ) t , ẽ2 j large enough, i.e., φ (ẽ 1 i ) t , ẽ2 j 2 > η for a positive threshold η, as well as make all singular values of αj i close to 1, such that the signal φ (ẽ 1 i ) t , ẽ2 j can be well backpropagated from the output layer to the input layer. in order to make the mean of singular values of αj i close to 1, the first option of α is the inverse of the mean of singular values of j i . for the purpose of ensuring φ (ẽ 1 i ) t , ẽ2 j 2 > η, the second option of α should be satisfied with the feasible α can be obtained through the following theorem. theorem 1. let entity embedding vectors ẽ2 k and ẽ2 l be the most similar and least similar to (ẽ 1 i ) t (1 ≤ k, @xmath3, i.e., ẽ2 @xmath4, and @xmath5. also, suppose that d is the minimal norm of entity embedding vectors in g 2 , i.e., @xmath6. for a given 0 < η < d/2, if α < algorithm 2 effective adversarial attacks input: kg g @xmath7, r k , t k ), set of pre-aligned entity pairs @xmath8, e 2 j )|e 1 i ↔e 2 j }, trained entity embedding model h, noise budget , and signal threshold η. output: perturbed adjacency matrices { â1 i , â2 j |(e 1 i , e 2 j ) ∈ d}. 1: for each pair (e 1 i , e 2 j ) in d 2: proof. please see appendix a for proof. algorithm 2 combines the above two kinds of α to produce effective adversarial attacks with attack signal amplification. the perturbed entity embeddings ê1 ## experimental evaluation they consist of three different cross-lingual datasets which are dbp 15k zh-en , dbp 15k ja-en , and dbp 15k f r-en . each cross-lingual dataset contains two monolingual kgs in different languages and 15,000 pre-aligned entity pairs between two kgs. in the experiment, 30% pre-aligned entity we compare the eaa model with seven state-ofthe-art attack models. sememe-based word substitution (sws) incorporates the sememe-based word substitution and swarm optimization-based search to conduct word-level attacks @xcite . inflection word swap (iws) perturb the inflectional morphology of words to craft plausible and semantically similar adversarial examples @xcite . we utilize the above two word-level attack models to replace associated entities of a relation based on semantics. gf-attack attacks graph embedding methods by devising new loss and approximating the spectrum @xcite . lowblow is a general low-rank adversarial attack model which is able to affect the performance of various graph learning tasks @xcite . we use the above two graph attack models to directly add/remove relations in terms of graph topology. criage aims to add/remove the facts to/from the kg that degrades the performance of link prediction @xcite . dpa contains a collection of data poisoning attack strategies against knowledge graph embedding @xcite . rl-rr uses reinforcement learning policy to produce deceptively perturbed kgs while keeping the downstream quality of the original kg @xcite . to our best knowledge, this work is the first to study adversarial attacks on cross-lingual entity alignment. we evaluate four versions of eaa to show the strengths of different components. eaa-p uses the basic pgd @xcite to produce adversarial attacks. eaa-d only utilizes the kde and density maximization to generate effective and unnoticeable attacks. eaa-a employs only our attack signal amplification strategy to improve the performance of the basic pgd attack. eaa operates with the full support of both kde and signal amplification components. we validate the effectiveness of the above attack models with three representative cross-lingual entity alignment algorithms. we use two popular metrics in entity alignment to verify the attack effectiveness: hits@k (i.e., the ratio of correctly aligned entities ranked in the top k candidates) and m rr (i.e., mean reciprocal rank). a smaller hits@k or m rr indicates a worse entity alignment but a better attack. k is fixed to 1 in all tests. attack performance on various datasets with different entity alignment algorithms. attack performance with varying perturbed relations. figure 4 presents the performance of entity alignment under nine attack models by varying the ratios of perturbed edges from 5% to 30%. it is obvious that the attacking performance improves for each attacker with an increase in the number of perturbed edges. this phenomenon indicates that current gcn-based entity alignment methods are very sensitive to adversarial attacks. eaa achieves especially, when the perturbation ratio is large than 10%, the hits@1 values drop quickly. impact of perturbation budget . figure 5 (a ) measures the performance effect of in the eaa model for the entity alignment by varying from 1 to 6. it is observed that when increasing , both hits@1 and mrr scores of the eaa model decreases substantially. this demonstrates it is difficult to train a robust entity alignment model under large constraint. however, a large can be easily detected by humans or by defender programs. notice that the average number of associated relations of each entity in three datasets is between 2.3 and 2.9. thus we suggest generating both effective and unnoticeable attacks for the entity alignment task under between 2 and 3, such that is smaller than the average number of associated relations. impact of signal threshold η. figure 5 (b ) shows the impact of η in our eaa model over three groups of datasets. the performance curves initially drop when η increases. intuitively, this can help alleviate the vanishing gradient issue in the pgd adversarial attacks. later on, the performance curves keep relatively stable or even increasing when η continuously increases. a reasonable explanation is that the too large η makes the upper bound of α too small. this results in poor-conditioned jacobian and thus leads to the vanishing gradient issue again. thus, it is important to determine the optimal η for the eaa model. ## conclusions we have studied the problem of adversarial attacks against cross-lingual entity alignment. first, we proposed to utilize kernel density estimation technique to estimate and maximize the densities of attacked entities and generate effective and unnoticeable perturbations, by pushing attacked entities to dense regions in two kgs. second, we analyze how gradient vanishing causes failures of gradientbased adversarial attacks. we design an attack signal amplification method to ensure informative signal propagation. the eaa model achieves superior performance against representative attack models.