# Efficient and Effective Unsupervised Entity Alignment in Large Knowledge Graphs
## 4 Methodology
### Pruning-hop2 Token  
Inspired by the hop2 Token method introduced by [15], we adapt hop2 Token into a Pruning-hop2 Token tailored to the specific requirements of the EA task, enabling more effective extraction of multi-hop neighborhood features for entities within KGs.  
Hop2 Token employs a propagation process akin to that of GCNs to derive \(K\)-hop neighborhood features. Utilizing the normalized adjacency matrix \(\bar{A}\) (also known as the transition matrix) and the node feature \(\mathbf{E}^{nc}\) from the given KG, the direct neighborhood information is aggregated through multiplication of \(\bar{A}\) and \(\mathbf{E}^{nc}\). This multiplication is iteratively applied to achieve feature aggregation across \(k\)-hop neighborhoods. Specifically, \(\bar{A}(\bar{A}\mathbf{E}^{nc})\) represents the 2-hop neighborhood information for all entities in KGs. Therefore, the \(k\)-hop neighborhood feature can be expressed as  
\[\mathbf{E}_{k}=\bar{A}^{k}\mathbf{E}^{nc}. \tag{3}\]  
However, within the \(k\)-hop neighborhood, the similarity of aligned entities between two KGs is often low. This phenomenon arises because the neighbors of aligned entities may not exhibit high similarity, and such noise is geometrically amplified along the \(k\)-hop paths. Consequently, directly applying hop2 Token to the alignment task in KGs may yield suboptimal results.  
To address this issue, we develop a novel method, Pruning-hop2 Token, inspired by search pruning algorithms. We leverage the multi-hop path acquisition technique proposed by [8], and employ similarity relations to filter out neighbors exhibiting lower noise levels. Specifically, we first derive a relation matching set \(R_{align}\) based on the relation names and the relation matching algorithm (following our previous work [49]), which represents reliable alignment relations between two KGs. Subsequently, we filter out neighbors beyond the first hop using \(R_{align}\). For instance, \((\bar{A}^{\prime}\cdot\bar{A})\) denotes the filtered 2-hop adjacency matrix, where \(\bar{A}^{\prime}\) is the neighborhood matrix obtained after filtering out noisy neighbors based on \(R_{align}\),  
\[\bar{A}^{\prime}=\{(e_{i},e_{j})|(e_{i},r_{t},e_{j})\in T,r_{t}\in R_{align}\}. \tag{4}\]Thereafter, Pruning-hop2 Token transforms the \(k\)-hop neighborhood into a neighborhood embedding,  
\[\mathbf{E}^{\prime}_{k}=(\tilde{A}^{\prime})^{k-1}(\tilde{A}\mathbf{E}^{nc}). \tag{5}\]  
Ultimately, Pruning-hop2 Token produces a neighborhood matrix \(\mathbf{E}\) with a sequence length of \(K+1\) (including the entities themselves),  
\[\mathbf{E}=(\mathbf{E}^{\prime}_{0};\mathbf{E}^{\prime}_{1};\dots;\mathbf{E}^ {\prime}_{K}), \tag{6}\]  
where \(\mathbf{E}^{\prime}_{0}=\mathbf{E}^{nc}\) represents the 0-hop neighborhood of the entities.  
Pruning-hop2 Token retains two key advantages from hop2 Token. First, it is a non-parametric method that can be executed offline prior to model training. Second, it facilitates small-batch training for subsequent models. The output of Pruning-hop2 Token is a three-dimensional matrix \(\mathbf{E}\in\mathbb{R}^{|E|\times(K+1)\times d}\). It simply requires splitting the first dimension of \(\mathbf{E}\) into several smaller matrices, denoted as \(\mathbf{E}_{B}\in\mathbb{R}^{|B|\times(K+1)\times d}\), where \(B\) denotes the size of each batch. Furthermore, compared to hop2 Token, our optimized Pruning-hop2 Token not only captures hop-wise semantic correlations but also effectively filters out most multi-hop superposition noise.