From Chain to Tree: Refining Chain-like Rules into Tree-like Rules on Knowledge Graphs (2025)

Abstract: With good explainability and controllability, rule-based methods play an important role in the task of Knowledge Graph Completion (KGC). However, existing studies primarily focused on learning chain-like rules, whose chain-like structure limits their expressive power. Consequently, chain-like rules often exhibit lower Standard Confidence, and are prone to the incorrect grounding values during reasoning, thus producing erroneous reasoning results. In this paper, we propose the concept of tree-like rules on knowledge graphs to expand the scope of the application and improve the reasoning ability of rule-based methods. To achieve this, we formalize the problem of tree-like rule refinement and propose an effective framework for refining chain-like rules into tree-like rules. Experimental evaluations on four public datasets demonstrate that the proposed framework can seamlessly adapt to various chain-like rule induction methods and the refined tree-like rules consistently exhibit higher Standard Confidence and achieve better performances than the original chain-like rules on link prediction tasks. Furthermore, we illustrate that the improvements brought by tree-like rules are positively correlated with the density of the knowledge graphs. The data and code of this paper can be available at https://github.com/forangel2014/tree-rule.

## introduction knowledge graph completion (kgc) @xcite @xcite is a fundamental and important task in natural language processing. for kgc, rule-based methods play a pivotal role, which focus on first learning symbolic and interpretable rules, and then leverage them for effective reasoning within knowledge graphs (kgs). in these rule-based methods, the development of comprehensive and high-quality * corresponding author figure 1 : an example of an inaccurate chain-like rule and the refined tree-like rule. although the chain-like rule (bottom-left) can predict most cases correctly, due to its chain structure, it has limited expressive power. the refined tree-like rule (bottom-right) leverages the information in the kg that originally ignored to improve the chain-like rule. to this end, previous works have proposed various types of methods to induce rules from the kgs, like symbol-based @xcite @xcite , differentiable-ilpbased @xcite , and rl-based @xcite . however, these existing rule induction methods only consider the chain-like rules in kgs @xcite @xcite @xcite . chain-like rules are a special case of the horn clauses @xcite , which is equivalent to a multi-hop reasoning process @xcite . for example, in the left-bottom subfigure in figure 1 , live(x, y ) ∧ lang(y, z) ⇒ speak(x, z) is a typical chain-like rule. since there is only one path leading the query variable x to the target variable z, there are limited constraints for the semantics in the reasoning path of the chain-like rules. consequently, chain-like rules are often prone to the incorrect grounding values during reasoning, thus producing erroneous reasoning results. for example, in figure 1 , this rule may reason erroneous facts when x is just a traveler, or y is a country with more than one official language and x just speaks one of them. therefore, this paper introduces the concept of tree-like rules, which is a more general form of rules. apart from a direct path from the query variable x to the target variable z, the tree-like rule body also contains some branch atoms to constrain the grounding values of the rule. these branch atoms can be seen as "hanging" triplets on the path, which further shape and narrow down the possible grounding values of the rule. the path and the branch atoms stretched together into a tree structure in the kg. for example, in the right-bottom subfigure in figure 1 , the tree-like rule may look like live(x, the added atoms bornin(x, y ) and is(y, italy) yield new constraints for the grounding values of variable y . with these added constraints, tree-like rules are expected to possess higher quality (standard confidence) and avoid the wrong predictions that x speaks z in the cases mentioned before. as a result, tree-like rules possess higher standard confidence than chain-like rules and will exhibit better reasoning performance on the task of kgc. to refine chain-like rules into tree-like rules, the key challenge is to tackle the large combinatorial space of the rule body, i.e. searching and selecting the probable branch atoms. the branch atoms are supposed to exclude the incorrect groundings while still including the correct groundings of the rule. to refine chain-like rules into tree-like rules by adding branch atoms, our proposed framework first transforms the optimization problem of the standard confidence of the entire rule to that of the best branch atom selection in a specific variable in the rule body. for the best branch atom selection problem, our framework proposes a threestep pipeline: forward reasoning, backward reasoning, and candidate atom selections. through this pipeline, our framework effectively refines the original chain-like rules into high-quality tree-like rules. to verify the effectiveness of tree-like rules refined by our framework, we conduct experiments on four widely used benchmark kgs with three dif-ferent sources of chain-like rules. the experimental results show that tree-like rules continuously exhibit higher standard confidence, and outperform chain-like rules on the link prediction tasks for different sources of chain-like rules on different kgs. with further analysis, we also find that the improvements brought by tree-like rules are positively correlated with the density of the knowledge graphs, showing that tree-like rules have greater advantages in kgs with complex topological structures. in summary, the contributions of this paper are as follows: ## problem formulation in the scope of first-order logic (fol), the rule (or horn clause) is formalized as σ ⇒ φ. here, the left part σ is called "rule body", which serves as the premise, when it is satisfied by some groundings, then the right part, "rule head" φ, will be grounded as the conclusion. for the evaluation of the quality of such a rule, as we are adding constraints to refine it to be more precise, we adopt the widely-used metric, standard confidence (sc). it can be defined as: based on the definition and objective above, our task can be stated as follows. a given chain-like figure 2 : the framework of our proposed method. in the forward reasoning stage, the query variable x is first grounded with b randomly sampled entities and by forward reasoning, we obtain the grounding values of y and z. in the backward reasoning stage, we then abductively obtain the positive groundings and negative groundings of each variable in the rule body. finally in the candidate atoms selection stage, three types of candidate branch atoms are then selected according to their inner product scores with the variable representation. rule r of length n can be represented as: to obtain tree-like rules from it, we aim to find branch atoms b(x i ) for the variable x i while being aware of the objective in eq 1. finally, a refined tree-like rule has the following format: please note that when we represent branch atoms as b(x i ), we omit other variables and constants that may appear within the predicate, to emphasize that this branch is a constraint on the variable x i . ## method given the chain-like rule, this paper propose to first grounded the rules with entities in the kg, and then find the top branch atoms that could eliminate the undesirable groundings, to make the groundings satisfying rule body be as close as to those satisfying rule head. given a kg @xmath0, r, t ), where e, r, t stands for the entity set, relation set, and triplet set, respectively, to reason with the rule on this kg, this paper adopts the matrix representation of entities and relations for reasoning rules. for an entity @xmath1, let v @xmath2, 1} 1×|e| be the one-hot encoding of entity e, i.e. only the ith element is 1 if e is the ith entity in e. based on the encoding of single entity, for a variable x in the rule, if the set c x denote the entities that can be ground to x, then the variable grounding of x, for an relation @xmath3, let m @xmath4, 1} |e|×|e| be the binary adjacency matrix of relation r, i.e. m r [i, j] = 1 iff (e i , r, e j ) ∈ t . with the definition above, a reasoning hop (h, r, t?) can be modeled by the following matrix multiplication: to obtain r * from r, we need to find a branch atom b(x i ) (correspond to a constraint vector b x i ) for the ground value of variable x i , to best match the reasoning results between rule body and rule head, based on eq 1, we have: however, it is hard to directly find branch atoms by maximizing eq 3. thus we approximately transform it into the best branch atom selection problem: to find the best branch atoms to maximize eq 4, as shown in figure 2 , we propose a three-step framework: • §3.1 forward reasoning: we first sample a batch of b entities to ground the query variable x 0 (i.e. x in figure 2 ). then a forward reasoning process transfers the groundings of x 0 to the target variable x n (i.e. z in figure 2 ) through both the rule body and rule head. at target variable x n , the positive groundings (p xn , the entities correctly predicted by rule body) and negative groundings (n xn , the entities incorrectly predicted by the rule body) are obtained. ## experiments in this section, we conduct a series of experiments to evaluate and compare the refined tree-like rules with original chain-like rules in the following two aspects: • standard confidence ( §4.5). we adopt the standard confidence as the direct metric to evaluate if the refined tree-like rules have better "quality" than the original chain-like rules. ## related work rule induction over knowledge graphs is a classical yet challenging task. inductive logic programming (ilp) seeks to induce the symbolic pattern behind the knowledge graphs. it faces the combinatorial space of searching predicates and binding variables. traditional ilp methods including amie @xcite , amie+ @xcite and rlvlr @xcite used search-based methods to induce chain-like rules. recently, many works have studied the way of inducing chain-like rules in a differentiable approach, named differentiable ilp, like neurallp @xcite , nlm @xcite , dlm @xcite , nlil @xcite . however, only a few works considered the defect of expressive power chain-like rules. nlil @xcite induced conjunctions of chain-like rules like car(x) ⇐ w heel(y 1 ) ∧ of (y 1 , x) ∧ w indow(y 2 ) ∧ of (y 2 , x), but they are only tree-like rules with branches at the target variable x. tyrule @xcite proposed to learn typed rules with type predicate type n (x i ) adding to each variable, but it needs extra type information of the knowledge graphs. in this paper, we propose the concept of tree-like rules and an effective framework for refining chain-like rules into tree-like rules to reach better reasoning ability. ## conclusion this paper introduces the concept of tree-like rules and presents an effective framework for refining chain-like rules into tree-like rules. to verify the effectiveness of the tree-like rules refined by our framework, this paper carried out experiments to show that the refined tree-like rules consistently exhibit higher standard confidence and outperform the original chain-like rules on kg reasoning tasks. further analysis illustrates that the improvements brought by the tree-like rules are positively correlated with the the density of the kgs.