Efficiently Learning Probabilistic Logical Models by Cheaply Ranking Mined Rules

This paper aims at rule mining in the neuro-symbolic (NS) domain. Rule mining is critical in NS methods which typically requires domain-specific rules. To address this, the paper defines several criteria to measure the utility of various rules and develop an algorithm for fast rule mining. They investigate the performance in various datasets: for MLN datasets, the method successfully mined most rules; for graph completion datasets, the method effectively outperforms RNNLogic and NCRL, two typical NS methods.

This paper discussed a method to evaluate the quality of a symbolic first-order rule. In addition, the paper also proposed a new method for mining rules from data. The measurement is cheap, the rule learning is in linear-time complexity, and the finding best utility algorithm is in quadratic-time complexity. The experiment results indicate that the model can be used in the ILP domain for learning rules and the model can perform knowledge graph completion for larger knowledge graphs such as the FB15K-237 dataset.

This paper introduces a framework called SPECTRUM, which focuses on efficiently learning probabilistic logical models to address scalability challenges in neurosymbolic AI. SPECTRUM incorporates a low-cost utility measure for assessing the predictive performance of logical models. Additionally, it employs a linear-time pattern mining algorithm to identify common structures within data and uses a fast sorting algorithm to optimize rule selection. Experimental results demonstrate that SPECTRUM can quickly construct efficient logical models across various tasks, significantly reducing computation time while surpassing existing methods in terms of interpretability and accuracy.

This paper deals with the task of efficiently learning logical rules from large relational databases. This can be seen as structure learning for probabilistic (and neural) logical models and hence efficient rule learning is also an important problem in statistical relational and neuro symbolic AI. The authors approach this problem by proposing the SPECTRUM, an efficient rule learning algorithm based on a 2-phase process. The first phase is pattern mining; it involves finding frequent relational patterns from the database. The second phase is pattern optimization; it involves (greedily) finds the top-M rules according to an efficiently computable rule utility score. The authors prove completeness and approximate optimality of the pattern mining phase and derive a principled yet efficiently computable utility function to score theories. Once the rules are learned, they can be used to instantiate a statistical relational or neurosymbolic model. The authors consider the former case and specifically instantiate probabilistic soft logic (PSL) models. They compare SPECTRUM against NCRL (Cheng et al., 2023) and RNNlogic (Qu et al., 2021) on 5 knowledge graph completion databases. The results show that SPECTRUM outperforms the baselines especially on larger databases. The authors also compare SPECTRUM against MLN learning methods including LSM (Kok & Domingos, 2010), BOOSTR (Khot et al., 2015), and PRISM (Feldstein et al., 2023) on IMDB and WebKB databases, showing that SPECTRUM outperforms the baselines.

We would like to summarise the review discussions for the benefit of the AC. We also like to thank the reviewers again for their comments and suggestions as we believe these reviews helped improve the paper from the original submission.

Reviewer GgSo: The only remark reviewer GgSo made was on missing citations and baselines to prove SPECTRUM's scalability. We summarize our analysis of the baselines they asked us to compare against:

• Natarajan, S (2012) RDNs: We ran RDN's rule learning algorithm on Family, UMLS, WN-18RR (see Table 2) using the codebase at https://github.com/hayesall/rfgb. The RDN's rule learning algorithm needs $>$15 minutes to learn rules for a single predicate, while SPECTRUM takes at most 36 seconds to learn rules and their weights for all predicates in these benchmarks, see Table 2.

• B-RLR (Ramanan et al., 2021 and Felix Weitkämper, 2024). The B-RLR implementation at https://github.com/nandhiniramanan5/RLR_Boost cannot be executed successfully, as also reported in Section 5 by (Felix Weitkämper, 2024). Similarly, the B-RLR implementation at https://github.com/srlearn/srlearn throws exceptions as reported in our earlier replies. Regarding the B-RLR implementation at (Felix Weitkämper,2024) we contacted the authors, who replied that B-RLR does not find meaningful rules for the link prediction datasets from Table 2.

• $\alpha$ILP (Shindo et al., 2023): $\alpha$ILP is a rule learning technique for a specific visual task, applied to scenarios including $\sim1000$ facts. In contrast, SPECTRUM runs on benchmarks of millions of facts (see benchmarks in Section 7.1). Further, the inputs to $\alpha$ILP are images, and the code base is implemented for specific visual tasks/datasets, making it unclear how to use it for the benchmarks in Section 7 and Appendix D. We asked reviewer GgSo for their suggestions, but they did not provide any.

As we pointed out in our rebuttal, the techniques suggested by reviewer GgSo (i) were originally tested by their authors on smaller datasets than the ones in our paper and (ii) are even significantly slower than the baselines in Section 7.2. Based on the above, if reviewer GgSo believes that a comparison against his suggestions is needed to prove scalability, then this has been shown beyond any doubt. Hence, it is unclear why in this case the grade remains a 3/10.

Reviewer jm86: The reviewer found two weaknesses:

1. Unclear definitions: We have cleaned up the definitions mentioned by the reviewer (seemingly to the reviewer's satisfaction).

2. Missing experiments: The experiments the reviewer claimed were missing were already in Section 7.2 and we have pointed this out in the rebuttal.

Based on (i) having cleaned the definitions, (ii) the experiments being present in the paper, it is unclear why the grade has not changed from the initial 6/10, since no additional weaknesses were added.

Reviewer Zbym: The reviewer found two weaknesses:

1. They claimed that our work does not learn probabilistic models: We provided a list of arguments explaining why this statement is false (seemingly to the reviewer's satisfaction).

2. Missing comparison (Glanois 2022): We performed a detailed analysis (theoretical and experimental) and found that the work by (Glanois 2022) does not scale even to the smallest datasets we tested, making a comparison impossible.

Since (i) the above issues seem to be answered, (ii) no further weaknesses have been mentioned, and (iii) the individual grading is very positive (Soundness: 4 excellent, Presentation: 3 good, Contribution: 3 good), it is unclear to us why the grading has not improved from the 6/10.

Reviewer gjdo: The reviewer identified three weaknesses:

1. SPECTRUM is limited to Horn clauses: As we pointed out, this assumption is made by the vast majority of structure learning techniques, and, in particular, by the latest state-of-the-art frameworks we compare against. In addition, we presented a solution to engineer around this limitation.

2. A comparison to AMIE3 is missing: We provided an in-depth (theoretical and experimental) analysis of AMIE3.

3. Confusion about how inference was performed in experiments: We pointed the reviewer to the paragraph in the original submission explaining this.

The reviewer increased their score from a 5/10 to a 6/10 for comparing against AMIE3 but provided no comments on the other points. It is unclear to us what weaknesses remain from their perspective. Seemingly, there are issues in soundness (scored with a 2) but the reviewer offered no explanations. We believe our six pages with proofs to be correct and despite us requesting further clarification, scoring soundness with 2 is unanswered.

This paper introduces a framework called SPECTRUM, a method to learn probabilistic logical model from large relational databases. In terms of the proposed method itself, more than half of the reviewers share the appreciation of its technical contribution. Furthermore, the method first proposes a metric to evaluate the performance and then employs a linear-time pattern mining algorithm to identify common structures and uses a sorting algorithm to do the selection. The linear-time complexity has theoretical guarantee, which is a plus. However, firstly, this paper is not well contextualized; a few important references are not well discussed. Second, the experiment results are not enough to convince readers. I would encourage the paper to, instead of spending more time on running experiments, put more efforts to carefully discuss about its baselines, and build a stronger case about its evaluation protocol. After that, to re-evaluate what experiments remain and what need to be added or ru-run.

Reject