Neuro-symbolic Entity Alignment via Variational Inference

We sincerely thank the reviewer for these detailed comments that enable use to improve the quality of the work. Below we present the responses to the concerns.

[w1] Why leveraging the EM algorithm and its connection to the given problem

We aim to introduce a principled framework to combine neural and symbolic methods. At the very begining, we model the label distribution of each pair $(e, e')$ as $p_w(v_{(e, e')}|\mathcal{G}, \mathcal{G}')$. And the learning objective is to optimize maximize the log-likelihood of the observed labels: $\log p_w(v_O)$. Directly optimizing this objective is intractable because it requires computing an integral over all the hidden variables. Therefore, we resort to optimizing the evidence lower bound of $\log p_w(v_O)$:

The insight of employing EM algorithm here is that, the ELBO contains hidden variables $v_H$. In machine learning and statistics, EM algorithm is an efficient and scalable method to find the maximum likelihood where the model depends on unobserved hidden variables. Thank you for this kind suggestion, we have included this insight in the lines 143-152 in the revised manuscripts, highlighted in blue.

[w2] Clarification of the dataset used

Allow us to clarify any confusion.

1. Full version of DBP15K contains long-tail entities. As we mentioned in the experimental setting (line269-273) and the dataset statistics (Table 4 & Table 5 at Appendix B.1), we respectifully point out that the original full version of DBP15K dataset does contain a significant number of long-tail entities, while the later condensed version of DBP15K only contains popular entities, which is the popularly-adopted version you mentioned. We included both versions in the main experiment (Table 1).

2. Results on OpenEA. OpenEA, also has two versions of dataset: the normal version (V1) and the condensed version (V2). We include the results on both versions below. Results show that our model still outperforms the strong baselines on these datasets.

• Results on OpenEA V1

• Results on OpenEA V2

[w3] Performance of PARIS

The low performance of PARIS comes from two reasons: low recall of symbolic models and Graph heterougeity

• Low recall of confidently inferred pairs. As a symbolic model, PARIS focuses on generating confident pairs and evaluates their precision and recall, unlike neural models that assess metrics like hit@k and mean reciprocal rank. We unify the metric and treat the recall of PARIS as hit@1, following the practice in EMEA[1], as stated in lines 280-281 in the manuscript. However, as a rule-based model, PARIS achieves high precision but generally suffers from low recall. For example, the precision and recall of PARIS on $DBP15K_{fr_en}$ and $OpenEA_{EN_FR}$ are:

As results show, the recall of PARIS on both datasets are low, although they have a high precision. Note that NeuSymEA can also generate confidence pairs with symbolic reasoning, we present the results of NeuSymEA below. Under this evaluation metric, NeuSymEA still outperforms PARIS on both datasets.

• Graph Heterougeity. OpenEA contains two mono-lingual datasets, D-W-15K and D-Y-15K. These mono-lingual datasets usually share more structural and semantic similarities compared to cross-lingual datasets in DBP15K, thus is easier to be aligned. For instance, the source and target KGs of D-Y-15K are respectively constructed from Dbpedia and YAGO, both partially use Wikipedia, leading to overlapping structures and relations.

Dear Reviewer,

We sincerely appreciate the time and effort you have invested in assessing our work. As the deadline is approaching, we would like to kindly inquire if you have had a chance to review our rebuttal. Should there be any remaining concerns, we would be glad to provide additional clarification.

We would greatly appreciate your reconsideration of our paper in light of the revisions we have made.

Bests,

The Authors

Dear Reviewer ggkd,

We sincerely appreciate the time and effort you have invested in reviewing our paper. We understand you may have a tight schedule, so we’d like to provide a brief summary of our responses to facilitate your review:

• Insights of employing the EM Algorithm: We clarified its role in optimizing the evidence lower bound for efficient reasoning with hidden variables. Revisions are highlighted in the manuscript (Lines 143–152).
• Dataset: We clarified the DBP15K dataset statistics (full and condensed versions) and presented new results demonstrating NeuSymEA’s consistent superiority on DBP15K and newer datasets (OpenEA). Additionally, we analyzed dataset properties to contextualize the performance.
• PARIS Performance: We explained its lower recall due to its symbolic nature and graph heterogeneity in DBP15K.
• ASGEA Comparison: NeuSymEA is compared with ASGEA in terms of model design considerations and empirical results. NeuSymEA demonstrates stronger performance under the same setting.

We hope this summary aids your review and welcome any further questions.

Best regards, The Authors

We sincerely appreciate your detailed and expertized comments. Below, we outline our responses to the concerns.

[w1] Unclear definition of rules.

Thank you for this detailed and constructive comment, we will provide a clear definition for the rules in the draft revision.

[w2] Complexity of EM algorithm

The EM algorithm is an iterative method for finding maximum likelihood estimates of parameters, with each iteration consisting of an E-step and an M-step. In this work, the overall run-time complexity of the EM algorithm is expressed as:

$n\times(C_E+C_M)$

Here, $C_E$ and $C_M$ represent the complexities of the E-step and M-step, respectively, and $n$ is the number of EM iterations. In this work, we set $n=5$ as the default, which we demonstrate to be sufficient for convergence in Figure 2 of the manuscript.

For the per-iteration complexity:

• E-step ($C_E$) involves parameter learning for the neural model. The complexity depends on the neural model used and can be very fast and scalable with GPU acceleration.
• M-step ($C_M$) encompasses the symbolic model's reasoning process, which has been designed to be both scalable and efficient. Detailed explanations for the symbolic reasoning process can be found in Appendix A.2 of the updated manuscript. There, we outline how reasoning is accelerated using parallel computing and made parameter-efficient via lazy inference.

We attach the runtime of neusymEA, and its memory consumption during symbolic reasoning below.

[w2, Q1] Rule mining and complexity.

We clarify that, rule mining are performed during both the variational EM process and the interpretation generation process but conducted differently. Below, we provide analyses for each case:

1.Rule-Based Reasoning During the Variational EM Process

In this case, long rules are not mined explicitly, we instead approximate the long rule reasoning with iterative reasoning using unit-length rules. The parameter complexity is $O(\max\left(|\mathcal{E}|+|\mathcal{E}'|)\right)$. The run time complexity is $O\left(L \cdot \frac{|\mathcal{E}||\mathcal{E}^{\prime}|}{n}\right)$, where $n$ denotes the number of CPU cores available for parallel computing. The detailed analysis is presented in Appendix A.2 in the updated manuscripts, highlighted in blue.

2.Rule Mining During the Interpretation Generation Process

In this case, rules are mined explictly using the algorithm described in the pseudo-code in Appendix A.3 in the updated manuscripts. The computation is dominated by the breadth-first search algoithm during searching reachable anchor pairs within max depth $L$, where the run time complexity and parameter complexity are both $O(d^L+d'^L)$, with $d$ and $d'$ denoting the average degree of the source and target knowledge graphs. Note that the upper bound of the run time and parameter complexity is $O(|\mathcal{E}|+|\mathcal{T}|+|\mathcal{E}'|+|\mathcal{T}'|)$ and $O(|\mathcal{E}|+|\mathcal{E}'|)$ respectively, which happpen when $L$ is large enough to potentially cover the entire graph.

[w3] related work

Thank you for suggesting the related work (ExEA), which will help enhance the comprehensiveness of our discussion. Below, we discuss the similarities and differences between NeuSymEA and ExEA:

The suggested work is also designed to generate interpretations for the entity alignment results. However, there are differences between our work and theirs.

• Types of interpretations: NeuSymEA generate a set of rules (path pairs), while ExEA identifies a subgraph as a holistic interpretation for entity alignment results.
• Sources of interpretations: NeuSymEA derives rules through reasoning results from the symbolic model, whereas ExEA extracts subgraphs through semantic matching with a pretrained neural model.

Thank you for suggesting this work that boost the comprehensiveness of the discussion of related work. We have incorporated it into the revised manuscript (line469-471).

We appreciate your insightful comments and hope our response satisfactorily addresses your concerns.

Thank you for your helpful feedback that helps us improve the draft. We answer concerns and address the three weaknesses in the following.

[w1] Trade-offs of the EM framework.

The variational EM framework is an efficient and principled approach for integrating two models, enhancing alignment effectiveness by leveraging their complementary strengths. The trade-off is that this framework requires more training time.

Specifically, our framework is iteratively optimized using an EM algorithm, where each iteration consists of an E-step and an M-step. The overall run-time is $n*(T_E+T_M)$, where $T_E$ and $T_M$ denote the per-iteration run-time of the E-step and M-step, respectively, and $n$ is the number of EM iterations. In this work, the default number of iterations is $n=5$, which we demonstrate to be sufficient for convergence, as shown in Figure 2 of the manuscript.

[w2] Efficiency of symbolic reasoning

We respectfully point out that, as we have described in Page 4, section 4.1 in the manuscripts. We have enable efficient optimization of the symbolic reasoning process. For further details, we have included a complexity analysis of symbolic reasoning in Appendix A.2 of the updated manuscript, highlighted in blue.

[w3] Neural models’ performance on sparse data.

We respectfully point out that the statement “the neural model tends to rely heavily on sparse data” is not correct. In this work, the sparsity challenge refers to scenarios where some entities lack aligned neighbors, which typically occurs when knowledge graphs contain many low-degree entities.

Our neuro-symbolic framework addresses this issues for the incorporated neural model by augmenting it with precisely inferred new alignments from the symbolic model (as demonstrated in Figure 2). These inferred alignments serve as additional anchor pairs, effectively supporting low-degree entities.

[Q1] Will NeuSymEA's performance improve further with an increase in data volume? Is this improvement significantly different from existing baseline models?

The performance of all methods, including ours, is expected to improve with an increase in data volume. Below, we present the original results for the ja_en dataset (as shown in Figure 4):

Hit@1 on ja_en, with x% denoting the ratio of data used for training.

These results demonstrate that performance consistently improves as training data increases. However, as the data volume grows, the performance gap among models tends to narrow, since Hit@1 values for all models eventually approach 1.0 with sufficient training data. Yet, NeuSymEA consistently outperforms strong baselines with high training data volumn.

We appreciate your comments that help us improve the quality of our work, and we hope our response can satisfactorily address your concerns.

I appreciate the author's good response, as it has resolved my question，thanks.I will maintain my score.

Thank you for the detailed comments, we answer the concerns below.

[w1] Paper presentation.

Thank you for your kind suggestions, we will include more diagrams to illustrate the framework and simplify the explanations.

[w2] Efficiency analysis

Overall complexity

Our framwork is iteratively optimzed under a EM algorithm, each iteration consists of an E-step and an M-step. The overall complexity is thus $n*(C_E+C_M)$, where $C_E$ and $C_M$ is the complexity of the E-step and M-step, respetively, and $n$ is the number of EM iterations. In this work, the default number of EM-iterations is 5, and we show that this is enough for convergence in Figure 2 in the manuscripts.

For the per-iteration complexity. $C_E$ involves the parameter learning of the neural model, which depends on the neural model used, can be very fast and scalable with GPUs. $C_M$ comes from the reasoning process of the symbolic model, which we have made scalable and efficient. The detailed analysis of the symbolic reasoning is below.

Complexity of symbolic reasoning

For the symbolic reasoning during the variational EM, we approximate the long rule reasoning with iterative reasoning using unit-length rules. This efficient approach eliminates the need to search long rules in exponential space, enabling the parameter complexity to $O(\max\left(|\mathcal{E}|+|\mathcal{E}'|)\right)$, which scales linearly with dataset size. And the run time complexity is $O\left(L \cdot \frac{|\mathcal{E}||\mathcal{E}^{\prime}|}{n}\right)$, where $n$ denotes the number of CPU cores available for parallel computing. A detailed indepth analysis is included in Appendix A.2 in the updated manuscripts, highlighted in blue.

[w3] Performance of NeuSymEA in challenging scenarios.

Thank you for your detailed comments. We address the questions in two parts:

1. NeuSymEA’s capability in handling sparse and heterogeneous KGs.

NeuSymEA demonstrates strong performance on the "full version" of DBP15K, as noted in lines 269–273. This dataset contains a substantial number of long-tail entities, introducing sparsity challenges, and its cross-lingual nature results in structural heterogeneity between the KG pairs. These characteristics highlight NeuSymEA's robustness in tackling such scenarios.

2. Limitation of NeuSymEA.

NeuSymEA currently focuses on structural information and does not natively support multi-modal inputs (e.g., images or text). Extending it to multi-modal EA tasks would require incorporating representations of such modalities as entity features, enabling the neural model to train or compute feature-based matching scores with tailored components. We leave this for future work.

[w4] Sensitivity to hyperparameters.

We respectfully highlight that the performance is robust to the threshold $\delta$, as illustrated in Figure 6 in the appendix. Below are results for ja-en with varied hyperparameters. The results demonstrate that NeuSymEA is robust to $\delta$, generally improving in early iterations and converging within approximately five iterations.

[w5] Practicability of rule-based explanations.

Thanks for acknowledging the significance of the interpretability. To facilatate the usability of the generated intepretations (supporting rules), we quantify their confidences based on reasoning results. These confidences help prioritize the most important rules, ensuring more precise and actionable interpretations.

Table 2 presents three examples of interpretations alongside their associated confidences. Such rules are in the human-readable format and easy to understand. While further exploration through user studies could provide additional insights, this is beyond the scope of our current research and is left as future work.

We appreciate your comments that help us improve the quality of our work, and we hope our response can satisfactorily address your concerns.

Dear Reviewer 1SAx,

We deeply value the effort and time you have devoted to reviewing our submission. As the deadline nears, we wanted to follow up to check if you’ve had the opportunity to review our rebuttal. If there are any additional confusions or concerns, we would be more than happy to address them.

We truly hope the improvements and clarifications we provided in our response help in reevaluating our work.

Best regards, The Authors

Thank you for your response. Your answer has partially resolved my doubts, but there are still many aspects of this article that require discussion, which you clarified will be addressed in future work. I maintain my current score.

Dear reviewer 1SAx,

Thank you for your thoughtful engagement with our paper and for your detailed comments. We greatly appreciate the time and effort you’ve dedicated to reviewing our rebuttal.

Regarding your feedback on the aspects of our work outlined as future work, we would like to clarify any potential misunderstandings and address the remaining concerns.

1. On Extending NeuSymEA to Multi-Modal Inputs

We initially discussed the limitation of NeuSymEA in response to the original concern that “The paper does not provide an in-depth exploration of scenarios where NeuSymEA might underperform” (weakness 3). Specifically, we noted that the current model does not inherently support multi-modal information and only focuses on structural information. For completeness, we expand on the multi-modal scenario below:

• Discussion of potential multi-modal extensions: While our current framework focuses on structural reasoning within knowledge graphs, we acknowledge the growing importance of integrating multi-modal information—such as text and images—into entity alignment tasks. Incorporating such modalities requires specialized representations and tailored components for feature-based matching. Although developing these components lies beyond the scope of our current research, we outline potential approaches to address this limitation in future work:
  • Multi-modal anchor alignment: Pretrained models (e.g., BERT for text or CNNs for images) could be used to encode features from text and images. Similarities calculated from these features could identify anchor pairs, which would augment the training data and enhance the learning process.
  • Multi-modal fine-tuning: Text/image representations encoded by pretrained models could serve as features for entities and be input into neural architectures like GNNs. Existing seed alignments could further refine these representations to improve performance in multi-modal contexts.

2. On User Studies for Rule-Based Explanations

• Qualitative and quantitative analysis of rule-based explanations: The reviewer suggested that user studies or qualitative assessments would provide valuable insights into the practical utility of rule-based explanations. While a full-scale user study is beyond the scope of this work, we currently quantify rule confidences to prioritize actionable interpretations. This aligns with the reviewer’s suggestion to make Neuro-Symbolic EA frameworks more practical for real-world applications, such as knowledge fusion. We provide an example below.
• Example application of rule-based explanations: In cross-domain knowledge graph question answering (KG-QA), entity alignment plays a foundational role in fusing knowledge from different domain-specific KGs. This alignment is essential when integrating multi-hop relations spanning multiple graphs, as aligned entities act as crucial intermediate anchors that bridge these relations. To ensure the reliability of such alignments, our framework generates explanations in the form of path pairs, ranks them based on confidence scores, and selects the most reliable ones. Each selected explanation, represented as a pair of relational paths in their respective knowledge domains, provides a clear and interpretable description of the aligned entity. By offering transparent and trustworthy justifications for entity alignments, these explanations contribute to improving the accuracy and effectiveness of cross-domain question answering.