Source-linked AI summary
Boosting the Speed of Entity Alignment 10*: Dual Attention Matching Network with Normalized Hard Sample Mining
Xin Mao, Wenting Wang, Yuanbin Wu, Man Lan
TL;DR
Entity alignment methods often struggle with inefficiency and scalability when integrating multi-source knowledge graphs. Dual-AMN combines a lightweight dual-attention encoder with normalized hard-sample mining, and outperforms existing methods across datasets while substantially reducing runtime.
Problem
Existing entity alignment methods are inefficient and scale poorly, partly because of over-complex graph encoders and inefficient negative sampling strategies.
Method
Dual-AMN models intra-graph and cross-graph relations, while Normalized Hard Sample Mining Loss efficiently selects hard negatives and accelerates convergence.
Results
The method outperforms competitors across all datasets; on DWY100K, the complete process takes 1,100 seconds, and Hits@1 and MRR improvements range from 6% to 13%.
Takeaways & Limitations
The proposed encoder and loss enable entity alignment with high accuracy and substantially improved efficiency across benchmark datasets.
Takeaways & Limitations
The paper acknowledges that its use of literal information is simple and crude, with performance gains mainly coming from structural embeddings.
Abstract
from arXiv · showhide
Seeking the equivalent entities among multi-source Knowledge Graphs (KGs) is the pivotal step to KGs integration, also known as \emph{entity alignment} (EA). However, most existing EA methods are inefficient and poor in scalability. A recent summary points out that some of them even require several days to deal with a dataset containing 200,000 nodes (DWY100K). We believe over-complex graph encoder and inefficient negative sampling strategy are the two main reasons. In this paper, we propose a novel KG encoder -- Dual Attention Matching Network (Dual-AMN), which not only models both intra-graph and cross-graph information smartly, but also greatly reduces computational complexity. Furthermore, we propose the Normalized Hard Sample Mining Loss to smoothly select hard negative samples with reduced loss shift. The experimental results on widely used public datasets indicate that our method achieves both high accuracy and high efficiency. On DWY100K, the whole running process of our method could be finished in 1,100 seconds, at least 10* faster than previous work. The performances of our method also outperform previous works across all datasets, where Hits@1 and MRR have been improved from 6% to 13%.
1 INTRODUCTION
Entity alignment integrates multi-source knowledge graphs, but existing methods face serious efficiency and scalability problems. Dual-AMN addresses these issues with a simpler encoder and normalized hard-sample mining, achieving high accuracy and efficiency.
- Entity alignment identifies equivalent entities across multi-source knowledge graphs as a key step in KG integration.
- Existing EA methods can require several hours or days on DWY100K, hindering application to large-scale knowledge graphs.DWY100K contains 200,000 nodes, while real-world KGs may contain millions or more entities and relations.
- Over-complex graph encoders and inefficient negative sampling are identified as the two main sources of high time complexity.Uniform random negatives are often redundant and low-information, slowing convergence and potentially degrading models.
- Dual-AMN models intra-graph and cross-graph information while reducing computational complexity.Its proposed training strategy uses normalized hard-sample mining to reduce sampling inefficiency.
- 1,100 seconds is sufficient for the complete DWY100K process, while Hits@1 and MRR improve by 6% to 13% across datasets.The reported runtime includes data loading, training, and evaluation.
2 TASK DEFINITION
The paper defines a knowledge graph as a directed graph of entities, relations, and triples, and formulates entity alignment as finding additional equivalent entity pairs from two KGs and known alignments.
- A knowledge graph is a directed graph G = (E, R, T) containing entities, relations, and triples.Triples belong to E × R × E and represent relations between entities.
- Given two knowledge graphs and a pre-aligned entity-pair set, entity alignment seeks additional equivalent entity pairs.The task uses information from both graphs and the known equivalent pairs.
3 RELATED WORK
Related EA work is organized around graph embedding, alignment, and information enhancement components. Existing approaches include translation-based, GNN, hybrid, mapping, corpus-fusion, bootstrapping, and literal-information methods.
- Existing EA frameworks commonly contain graph embedding, entity alignment, and information enhancement modules.
- TransE, GNN, and hybrid methods are described as the three mainstream embedding approaches.TransE models relations as translations, while GNNs provide strong graph-structure modeling.
- Common alignment methods include mapping embeddings into a shared space and corpus fusion using pre-aligned entities.
- Because labeled alignments are limited, methods may reserve a small training subset and use bootstrapping or iterative strategies to generate semi-supervised data.MRAEA is noted for using a bidirectional iterative strategy.
- Literal information can improve accuracy, but structure-only methods are more general because literal data may be unavailable or risky to use.
4 DUAL ATTENTION MATCHING NETWORK
Dual-AMN combines a simplified relational attention layer for within-graph structure with a proxy matching attention layer for cross-graph alignment. Proxy vectors replace expensive node-to-node interactions, reducing the matching complexity for large graphs.
- 4 DUAL ATTENTION MATCHING NETWORK: Dual-AMN consists of a Simplified Relational Attention Layer and a Proxy Matching Attention Layer.
- 4.1 Simplified Relational Attention Layer: The simplified layer captures intra-graph relational information using relation-aware attention and relational projection.Relational projection generates relation-specific entity embeddings without extra parameters.
- 4.1 Simplified Relational Attention Layer: The encoder design favors anisotropic attention while limiting transformation parameters to reduce complexity and avoid overfitting risks.
- 4.2 Proxy Matching Attention Layer: GMN computes cross-graph attention for every entity pair, giving it O(|E1||E2|) computational cost.
- 4.2 Proxy Matching Attention Layer: Proxy matching represents alignment with a limited set of proxy vectors, reducing interaction complexity from O(|E1||E2|) to O(|E1| + |E2|).Equivalent entities are expected to have consistent similarity distributions over the proxies.
5 NORMALIZED HARD SAMPLE MINING
The section replaces costly nearest-neighbor hard sampling with parallelizable LogSumExp-based mining and normalizes losses to reduce hyper-parameter sensitivity. It also specifies the training and testing distance metrics used in the method.
- Smooth Hard Sample Mining: Nearest-neighbor hard sampling improves sample quality but requires expensive candidate ranking each epoch, which is difficult to parallelize on GPUs.This can increase total training time despite faster convergence.
- Smooth Hard Sample Mining: LogSumExp smoothly generates hard negatives and can replace K-nearest sampling with better computational efficiency through GPU parallelization.When λ→∞, it approximates TUNS with K = 1; when λ = 1, it is equivalent to Softmax with Cross-Entropy loss.
- Loss Normalization: The choice of hard-sampling hyper-parameters is difficult: small K slows initial convergence, while large K produces overly easy negatives.LogSumExp likewise depends on selecting an appropriate λ.
- Loss Normalization: Loss normalization fixes the mean and variance of sample losses, reducing dependence on the scale hyper-parameter.The method is inspired by batch normalization and aims to adjust sample weights without changing the gradient direction.
- Implementation: Training uses L2 distance for entity similarity, whereas testing uses CSLS to address hubness in high-dimensional spaces.The normalization statistics are excluded from gradient calculation and backpropagation.
6 EXPERIMENTS
Experiments evaluate Dual-AMN on dense, sparse, cross-lingual, and mono-lingual KG alignment benchmarks, showing strong accuracy, efficiency, interpretability, and sensitivity to graph sparsity. The method consistently outperforms competing approaches while substantially reducing runtime.
- Experimental Settings: Experiments use DBP15K, DWY100K, and SRPRS to assess effectiveness, robustness, and scalability across dense, large-scale, and sparse KGs.DBP15K and DWY100K contain dense graphs, while SRPRS is designed to reflect sparser real-world structure.
- Main Experiments: Dual-AMN consistently achieves the best performance across the evaluated datasets and method categories.It outperforms basic methods by at least 20% on DBP15K and exceeds previous SOTA by more than 15% on DWY100K.
- Main Experiments: On SRPRS, Dual-AMN exceeds RSNs by at least 10% on both Hits@1 and MRR despite the dataset’s sparse structure.Performance declines for all methods on sparse datasets, making SRPRS a test of structural modeling under limited connectivity.
- Limitations: The authors acknowledge that their use of literal information is simple and crude, identifying better integration of literals as future work.They attribute most performance improvement to better structural embeddings rather than their literal-information strategy.
- Ablation Experiment: The Normalized Hard Sample Mining Loss converges faster and achieves better performance than compared losses, while Triplet loss requires thousands of epochs and performs about 4% worse.The proposed loss improves convergence without losing accuracy relative to the alternatives evaluated.
- Relation Interpretability: Relation-importance analysis finds that highly important relations often form meta-paths that sharply reduce candidate entities, whereas broad relations such as President are less discriminative.The model derives relation importance from attention weights associated with neighboring entities.
- Degree Analysis: Performance correlates strongly with entity degree: Dual-AMN reaches only 20% Hits@1 for entities with one neighbor, while literal information helps sparse entities when available.Semi-supervised training has limited effect on entities with extremely sparse local structure, and literal information cannot be used on datasets lacking it.
7 CONCLUSION
The paper proposes Dual-AMN and Normalized Hard Sample Mining Loss to improve entity alignment efficiency while preserving strong performance across datasets and metrics.
- Dual-AMN models intra-graph and cross-graph relations while reducing computational complexity.
- Normalized Hard Sample Mining Loss reduces sampling consumption and accelerates convergence.
- The proposed method outperforms competitors across all datasets and metrics.
- Auxiliary experiments evaluate the effectiveness of each component and the model's interpretability.