Simple Augmentations of Logical Rules for Neuro-Symbolic Knowledge Graph Completion (2023)

Abstract: High-quality and high-coverage rule sets are imperative to the success of Neuro-Symbolic Knowledge Graph Completion (NS-KGC) models, because they form the basis of all symbolic inferences. Recent literature builds neural models for generating rule sets, however, preliminary experiments show that they struggle with maintaining high coverage. In this work, we suggest three simple augmentations to existing rule sets: (1) transforming rules to their abductive forms, (2) generating equivalent rules that use inverse forms of constituent relations and (3) random walks that propose new rules. Finally, we prune potentially low quality rules. Experiments over four datasets and five ruleset-baseline settings suggest that these simple augmentations consistently improve results, and obtain up to 7.1 pt MRR and 8.5 pt Hits@1 gains over using rules without augmentations.

## introduction knowledge graphs (kgs) comprise important world knowledge facts, but are typically incomplete, due to their ever-increasing size. kg embeddings @xcite has been the dominant methodology for knowledge graph completion (kgc). a kg embedding approach represents entities and relations as learnable dense vectors and computes a score for an unseen fact as a function over them. these generally have state-of-the-art performance, especially for large kgs. recently, neuro-symbolic (ns-kgc) approaches for the task have been proposed, where kg embeddings are enhanced by inferences over an explicit first-order logic rule set @xcite . the resulting models bring together best of both worlds -generalizability and interpretability of explicit logical rules, and the scalability and representation power of embeddings. unfortunately, a key roadblock for success of ns-kgc is the availability of a high-coverage rule set. early ns-kgc methods, such as neu-rallp @xcite and drum @xcite , learn rules as part of a single model, but do not have performance competitive with embedding models such as rotate @xcite . a recent ns-kgc model, @xcite , matches empirical performance with embedding approaches. it has a separate neural component that outputs a set of rules, which is then used to train inference parameters, in an em-based approach. preliminary experiments on rnnlogic suggest that its ruleset has limited coverage, due to which symbolic inferences do not fire for many queries, and the model gets limited to using its embedding part only. the goal of this work is to strengthen the symbolic inferences in ns-kgc models for better overall performance. in this work, we propose simple augmentations that take an existing ruleset (such as one output by rnnlogic) and proposes additional (related) rules to improve coverage and quality. we propose three augmentations. first, we convert each deductive rule into its abductive counterparts. second, we supplement each rule via an equivalent rule that uses inverses for all constituent relations. third, we generate additional high-quality rules independently by local random walks and subsequent pca filtering @xcite . these increase size of ruleset drastically; we balance runtimes by additionally pruning rules from existing set using our filtering approach. overall, this results in a comparable number of high-quality and high-coverage rules, for use in ns-kgc. on four kgc datasets, over three ns-kgc models, we find that our augmentations consistently improve kgc performance, outperforming no augmentation baselines by up to 7.1 mrr and 8.5 hits@1 pts. we believe our augmentations should become standard practice over any ruleset for ns-kgc. we release our code foot_0 and rulesets. ## background and related work we are given an incomplete kg @xmath0, r, t ) consisting of entities e, relation set r and set @xmath1, r, t)} of triples. our goal is to predict the validity of any triple not present in t . related work: existing work on ns-kgc can roughly be characterized into four types. one approach is to use attention over relations to learn end-to-end differentiable models @xcite . a second approach, which includes minerva @xcite and deep-path @xcite , uses rl to train an agent to find reasoning paths for kg completion. these approaches are not yet competitive to kg embedding models for large datasets. thirdly, models like expressgnn @xcite and rnn-logic use variational inference to assess plausibility of a given triple. we experiment with both these models in this paper. the final type includes uniker @xcite and ruge @xcite , which integrate embeddings alongside traditional rules learnt via ilp models. we believe that our augmented rules can benefit these works too. since our experiments are based on rnn-logic, expressgnn and we utilize pca scores for filtering, we describe these in some detail next. rnnlogic+: as a pre-processing step, for every @xmath2, rnnlogic adds a relation r -1 to r, and corresponding facts using inverse relations to t . rnnlogic first produces a set of first order rules (l) using an lstm which are used by the rnn-logic+ predictor to compute the score of a given triple. given a query (h, r, ?), the candidate answer o is scored by rnnlogic+ as: the authors designed another scoring function that incorporates rotate @xcite into the scoring function, scor(o), in equation ( 1 ) where the goal is to exploit the knowledge encoded in the kg embeddings. the resulting scoring function is: expressgnn: it is a novel model that integrates markov logic networks (mln) @xcite and graph neural networks (gnn) @xcite to exploit their complementary strengths. an open-world paradigm is adopted in which a fact that is unknown in kg is assumed to be hidden (not false). the joint distribution of the observed and hidden triples of the kg in the mln is optimized by employing a variational em framework where the variational posterior distribution of the hidden variables is encoded as a gnn. please refer to @xcite for further details about the model. pca score: it is a symbolic rule confidence metric proposed in amie (2013) -see appendix m for details. broadly, it is the number of positive examples satisfied by a rule, divided by the total number of tails reached by the rule from heads occurring in the training dataset. its performance in the context of amie was not as good due to its purely symbolic approach, and we are likely the first to show its utility in the context of ns-kgc. ## rule augmentation in ns-kgc models with the aim of maximal utilization of a given rule @xmath3, we first propose two rule augmentation techniques: abduction and rule inversion. the other two techniques prune low-quality rules from l, and independently add new rules to increase coverage. all augmentations are generic and can be integrated with any existing ruleset, and ns-kgc model. abduction: the goal of abductive reasoning (or abduction) is to find the best explanation from a given set of observations @xcite . it has seen limited use in the context of kbs @xcite . in our approach, for every rule in l, we introduce several abductive rules with one of the antecedants, appearing as a consequent. as an example, consider the rule: our augmentation will generate abductive rules, one for each relation in the body, as: as an example, let's say a learned rule is bornin(x, u) ∧ placeincountry(u, y) ⇒natio nality(x, y). if in the kg, we know that oprah has nationality u.s., and that she is born in mississippi, then abduction allows the model to hypothesize that mississippi might be in u.s. of course, not all abductions are accurate, for instance, just because alabama is known to be in u.s., does not mean that oprah was born in alabama. abductive rules increase rule coverage at the cost of precision. we expect the predictor scorer to automatically handle which (abductive) rules can and cannot be trusted. rule inversion: our second rule augmentation takes an existing rule and rewrites it by referring to inverses of all relations. as an example, if a rule uses the path oprah bornin -----→ mississippi placeincountry ----------→ us, then it could also use the equivalent path formally, for every original rule: rule filtering: augmentations increase the size of the ruleset. in order to reduce the number of parameters and the training/test times of the ns-kgc model, we prune seemingly low-quality rules from the augmented rulebase. for this, we compute the pca score for each original and augmented rule and prune all the rules that have score less than a threshold (set at 0.01 in experiments) and have less than 10 groundings. so, all low-coverage rules with seemingly low quality are pruned out. as experiments show, this results in up to 70% reduction in the number of rules, while preserving kgc performance. random walk augmentation: motivated by the empirical success of pca scores for finding good rules in the previous step, we further augment our ruleset with new, high scoring rules generated independently via local random walks. starting at each entity in the kg, we perform a number of random walks of fixed length. each such random walk constitutes the body of the rule and the relation connecting the end entities in the kg form the head of the discovered rule. we score these rules by the pca score and retain all such rules that have pca score above the threshold (of 0.1). baselines: we first experiment with two base models: rnnlogic+ ([rnn] in tables), and rnnlogic+ with rotate ([rnn+rote]) (eqn 2). we have reproduced the numbers published by the original authors for these models (details in appendix d). we run these models with two rulesets: (1) orig, rules generated by rnnlogic (around 300 rules per relation for wn18rr and fb15k-237, and 1000 rules per relation for kinship and umls), and (2) rw, only the rules discovered by our random walks. this second setting can only evaluate the value of abduction, inversion, and pruning since random walks are anyways used in generating rules. more details in appendix c, f and g. in order to assess the generality of our augmentations, we also experiment with expressgnn @xcite . we choose top five rules for each relation from rnnlogic's orig ruleset according to pca confidence and provide them as input ruleset to @xcite in tables). expressgnn does not scale up to the augmented ruleset for fb15k-237, hence we test it for the other three datasets. refer to appendix e for more details. we use aug to denote the performance of rule augmentations for all baselines. we also tried rulesets from neurallp (2017), but they are too small to be useful with rnn-logic+. the only other ns-kgc model that has reported performance similar to rnnlogic+ is rlogic (2022). unfortunately, their code is not publicly available. 2 results: we report the results in next, we present the results of our proposed augmentations with expressgnn 3 as baseline in ## analysis of augmented rules we perform five further analyses to answer the following questions. q1. are the rules created by abduction and rule inversion of high quality? q2. what is the individual effect of each type of augmentation on the performance? q3. how do the rule augmentations affect the training time of a model? q4. can we get the same performance as augmentation by generating more rules from the lstm in rnnlogic? q5. are the augmented rules interpretable by a human? quality of new rules: to answer q1, we employ two metrics to assess quality of rules, (pca-metric and foil-metric) before and after abduction and rule inversion. the rules obtained from random walks have high scores by construction since they are filtered based on pca score. therefore, they are of high quality as per our definition. (details in appendix m and n) ablation: to answer q2, we perform an ablation in general, abduction (row 3) gives larger improvements than rule inversion (row 2) because as we noticed in the previous section, abduction adds a larger number of high-quality rules to the rule set. we also find that adding the pca-based random walk rules results in performance improvement, even with only 5% new rules being added (as in kinship) as compared to original rule set. finally, we find that filtering based on the pca metric results in marginal performance improvement, along with lower running times (see below). performance vs training time trade-off: to answer q3, we report training time per epoch (in minutes), size of ruleset and performance metrics after augmentation through abd, inv and rw (denoted as aug) and filtering (aug + fil) with [rnn + rote] as the baseline model in our proposed augmentations (inv, abd and rw) result in substantial performance gains, at the cost of 5-6 times increase in the training time. after filtering (fil), there is no decrease in performance, and the training time goes down by 2-3× compared to aug. therefore, we obtain substantial performance gains through our augmentations, at the cost of only 2-3 times increase in training time. rule generation vs rule augmentation: our augmentations result in 100-200% increase in the number of rules across datasets after filtering. as a we observe that rule augmentations lead to large improvement over rule generation in all cases, even when rule generation creates more rules. thus, we find that rule augmentation is more beneficial than simply using more rules from the rule generator. augmentations exploit a small number of highquality rules to their full potential. ## conclusion and future work we present simple rule augmentation techniques in the context of neuro-symbolic knowledge graph models and obtain substantial increase in performance over strong base models. we believe our augmentations can become standard for all subsequent ns-kgc models. we release code and rulesets for further research. future work includes using our augmentation technique during the iterative learning of rules in algorithms such as rnnlogic, potentially further improving their performance.