TL;DR
This paper introduces a novel method for poisoning Knowledge Graph Embedding (KGE) models by exploiting their inherent "inference patterns" (like symmetry and inversion). These attacks effectively degrade KGE model performance on link prediction tasks, outperforming existing methods and highlighting the sensitivity of KGE models to these logical structures.
What Problem Does This Paper Address?
Knowledge Graph Embeddings (KGEs) are increasingly used in critical decision-making domains like healthcare and finance. However, their vulnerability to adversarial attacks, specifically data poisoning, has been underexplored. Data poisoning attacks aim to subtly alter training data to degrade model performance at test time. Existing poisoning methods for graph data often don't scale to the large, sparse nature of knowledge graphs or are limited to specific KGE model types. This paper tackles the challenge of developing effective and scalable poisoning attacks for KGE models by leveraging their inductive capabilities, which are often captured through relational inference patterns.
Methods
The core of this work lies in exploiting three key relation inference patterns: symmetry, inversion, and composition. The authors propose a three-step process to craft adversarial additions:
- Determine Adversarial Relations: Using algebraic models based on pre-trained KGE embeddings, they identify relations that exhibit symmetry, inversion, or composition with the target relation.
- Determine Decoy Entities: They employ heuristic approaches (soft truth scores, KGE ranks, and cosine distance) to select "decoy" entities that, when linked with the target relation, are likely to be manipulated by adversarial edits.
- Determine Adversarial Entities: For composition attacks, this step involves finding specific entities to form the adversarial triples that best exploit the inference pattern to degrade the decoy triple's score.
The novelty lies in framing poisoning as a way to improve the model's confidence on carefully chosen decoy facts, thereby degrading performance on target facts, and in leveraging specific inference patterns to guide this process.
Datasets
The authors evaluate their proposed attacks on two widely-used benchmark datasets for link prediction:
- WN18RR: A subset of WordNet, filtered to remove reciprocal relations.
- FB15k-237: A subset of Freebase, also filtered to remove reciprocal relations.
They also conduct an additional evaluation on the WN18 dataset to specifically analyze the impact of inversion attacks when inverse relations are present.
Key Insights and Ideas
- Inference Patterns as Attack Vectors: KGE models learn logical relationships between entities and relations. These learned patterns (symmetry, inversion, composition) can be exploited to craft targeted attacks.
- Decoy Facts for Degradation: Instead of directly attacking target facts, the strategy is to improve the model's prediction confidence on carefully selected "decoy" facts, which indirectly degrades performance on the target facts.
- Symmetry is King (for Attacks): The symmetry pattern-based attacks proved to be the most effective and generalized across all tested KGE models and datasets, highlighting a significant vulnerability.
- Model Sensitivity: The effectiveness of different attack patterns reveals the inductive biases and sensitivities of various KGE models. For instance, ComplEx is particularly sensitive to inversion attacks when inverse relations are present.
- Dataset Influence: The presence or absence of specific relation types (like inverse relations) in the dataset significantly impacts the effectiveness of certain attack patterns.
Key Results
The proposed poisoning attacks consistently outperformed existing state-of-the-art baselines and random attacks across four KGE models (DistMult, ComplEx, ConvE, TransE) on both WN18RR and FB15k-237 datasets.
- MRR Reduction: For example, on WN18RR, the symmetry-rank attack achieved a reduction in MRR of up to 36% for DistMult, and on FB15k-237, it achieved up to 33% reduction for DistMult.
- Generalization: Symmetry-based attacks showed strong generalization, indicating a fundamental sensitivity of KGE models to this pattern.
- Inversion Effectiveness: On the WN18 dataset (which includes inverse relations), inversion attacks were highly effective, especially for ComplEx, demonstrating its sensitivity to this pattern.
- Runtime Efficiency: The proposed attacks were found to be more efficient than some baseline methods (e.g., Zhang et al.) and comparable to others (e.g., CRIAGE).
Limitations and Future Work
- Dataset Definition: The authors note that the inference patterns in benchmark datasets are not always well-defined, making it challenging to definitively claim a model's inductive abilities solely based on attack effectiveness. Future work could involve designing datasets and evaluation tasks that specifically test varying degrees of inductive abilities.
- Composition Attack Anomaly: For the TransE model, composition attacks sometimes improved performance, suggesting that the model might not have learned composition patterns, and adding them actually boosted its overall performance. This indicates room for improvement in selecting adversarial entities for composition attacks.
- Mitigation Strategies: The paper highlights that KGE models' sensitivity to inference patterns can introduce security vulnerabilities. Future research directions include exploring adversarial training, ensemble methods, and investigating neural architectures that generalize beyond simple symmetry.
- Input Graph Properties: The authors suggest investigating the effect of input graph connectivity and the existence of specific inference patterns in datasets on attack effectiveness.
Summary updated