# GLIDR: Graph-Like Inductive Logic Programming with Differentiable Reasoning
**Authors**:
- Blair Johnson (Georgia Institute of Technology)
- Clayton Kerce (Georgia Institute of Technology)
- Faramarz Fekri (Georgia Institute of Technology)
## Abstract
Differentiable inductive logic programming (ILP) techniques have proven effective at finding approximate rule-based solutions to link prediction and node classification problems on knowledge graphs; however, the common assumption of chain-like rule structure can hamper the performance and interpretability of existing approaches. We introduce GLIDR, a differentiable rule learning method that models the inference of logic rules with more expressive syntax than previous methods. GLIDR uses a differentiable message passing inference algorithm that generalizes previous chain-like rule learning methods to allow rules with features like branches and cycles. GLIDR has a simple and expressive rule search space which is parameterized by a limit on the maximum number of free variables that may be included in a rule. Explicit logic rules can be extracted from the weights of a GLIDR model for use with symbolic solvers. We demonstrate that GLIDR can significantly outperform existing rule learning methods on knowledge graph completion tasks and even compete with embedding methods despite the inherent disadvantage of being a structure-only prediction method. We show that rules extracted from GLIDR retain significant predictive performance, and that GLIDR is highly robust to training data noise. Finally, we demonstrate that GLIDR can be chained with deep neural networks and optimized end-to-end for rule learning on arbitrary data modalities.
## 1 Introduction
This paper presents GLIDR (Graph-like Logical Induction with Differentiable Reasoning), a differentiable inductive logic programming (ILP) method that learns expressive graph-structured logical rules for knowledge graph reasoning. Unlike existing differentiable ILP approaches that are limited to chain-like rule structures, GLIDR supports an expressive syntax that can represent rules with branches, cycles, and complex variable interactions. The method consists of two key components: (1) a graph-like rule representational structure, and (2) a differentiable message passing algorithm for deriving the entailment of rules encoded in this representational structure. Experiments on knowledge graph completion benchmarks demonstrate GLIDR’s expanded expressiveness enables it to significantly outperform existing rule learning methods while maintaining the noise robustness and scalability advantages of differentiable approaches. Furthermore, as a differentiable method, GLIDR can be integrated end-to-end with deep neural networks, enabling rule learning on mixed symbolic and continuous data modalities.
### 1.1 Inductive Logic Programming
Inductive Logic Programming (ILP) is a machine learning technique that learns from examples of facts to construct logical rules. ILP benefits from a strong modeling bias that allows it to learn from small amounts of data, and the logical nature of the models it produces is explicitly interpretable. Learned rules explicitly describe the conditions under which a model makes a given prediction. In doing this, learned rules often reveal explicit knowledge about the patterns present in the data used for training.
The logical rules learned by ILP systems are typically first-order logic rules comprised of predicates, variables, constants, and logical operators. A predicate $P$ can represent conceptual relationships or properties. Constants represent specific entities, and predicates can be combined with constants to represent facts. For instance, $\text{dog}(\text{Rufus})$ , uses the ”dog” predicate to record the fact that a specific entity, ”Rufus”, is a dog. Sometimes, we need to express facts that are true for many entities without enumerating them. Logic variables allow first-order logic to express abstract facts in this manner. The fact $\forall X,Y(\text{parent}(X)\leftarrow\text{has\_child}(X,Y))$ states that for all possible pairs of entities, represented by variables $X,Y$ , if the entity represented by $Y$ is the child of the entity represented by $X$ , then $X$ must necessarily be a parent. We call abstract facts of this nature rules because they describe patterns of other facts. The first term of the rule, $\text{parent}(X)$ , is referred to as the head literal and is implied to be true whenever the fact described by the body literal, $\text{has\_child}(X,Y)$ , is true. Logical operators like conjunction ( $\wedge$ ) and disjunction ( $\vee$ ) allow first order logic to express more complex facts. The conjunction operator represents the logical AND of facts, and it is frequently used to combine multiple literals in a rule body to express simultaneously necessary conditions. For example, the rule $\forall X,Y,Z($ grandparent $(X,Y)\leftarrow$ parent $(X,Z)\wedge$ parent $(Z,Y))$ represents the fact that an entity $X$ is always the grandparent of an entity $Y$ if $X$ is the parent of an entity $Z$ and that entity $Z$ is the parent of $Y$ . The disjunction operator implements the logical OR of facts, meaning that at least one of the facts it connects must be true. ILP systems typically favor conjunctive rule bodies because they are computationally efficient to evaluate and describe clear, human-understandable sets of truth conditions. Using these simple primitives, rules learned by ILP can represent highly expressive statements about the world.
### 1.2 Knowledge Graphs
As ILP deals heavily with relational facts, ILP problems are closely related to knowledge graph reasoning problems. Knowledge graphs are useful and convenient data structures for encoding information about entities, their properties, and the relationships between them. The generality of knowledge graphs as a mechanism for storing and retrieving relational information has resulted in widespread adoption across many domains such as biomedicine nicholson2020constructing ; ernst2015knowlife , cybersecurity piplai2020cyber ; qi2023attack , financial crime suzumura2019towards , and public health park2021discovering ; bettencourt2020exploring . By representing knowledge in a structured and machine-readable format, knowledge graphs have enabled a wide range of applications, including question answering, recommendation systems Fensel2020 , and decision support systems nickel2015review . All of these applications rely on the core tasks of predicting edges and classifying nodes using the background knowledge contained in the knowledge graph. These tasks can also be represented as ILP problems, and ILP methods are frequently evaluated on knowledge graph completion benchmarks.
While embedding methods represent the most popular and performant approaches for knowledge graph reasoning tasks, they have several important limitations. The most significant limitation of embedding methods is that they typically operate in the transductive setting, and must be trained on a set of entities that overlaps those seen at test-time teru2020inductive . They often perform poorly on rare entities with few training examples zhang2019iteratively . They have limited interpretability GeseseBS19 ; HamiltonYL17 , and they struggle to model patterns that can be naturally compressed into rules qu2020rnnlogic . These limitations motivate the development of graph reasoning algorithms that can generate predictions from structure alone, enabling interpretability and generalization unseen data.
### 1.3 Previous Work
Previous ILP techniques such as Progol muggleton1995progol , Aelph srinivasan_aleph , and Metagol muggleton_meta-interpretive_2015 have relied heavily on symbolic solvers, often implemented in Prolog, to search for rules that entailed the positive examples provided to the algorithm and reject the negative examples. These solvers used hypothesis generation algorithms, inverse entailment, heuristic search, and meta-templating strategies to construct rules explaining observed data. Recent advancements such as Popper cropper_learning_2021 have re-framed ILP problems as special cases of answer set programming (ASP) or Boolean satisfiability (SAT) problems. These approaches leverage high-performance SAT and ASP solvers to improve the performance and efficiency of the ILP process while enjoying the passive benefit of advancements in SAT and ASP solving. While symbolic ILP techniques like Metagol and Popper initially lacked noise tolerance, extensions to these methods have eased this limitation muggleton2018meta ; noisypopper ; hocquette_learning_2023 .
Today’s symbolic ILP methods are very capable but have properties that make them unsuitable for some problems. First, the computational efficiency of these systems is often extremely dependent on the choice of language bias supplied to the solver, and choosing such a bias can be a difficult process requiring both ILP and problem domain knowledge cropper2022inductive . Second, symbolic ILP methods often struggle when very large amounts of noisy background knowledge is supplied during rule learning. Finally, symbolic ILP methods do not interface with continuous data well, as they typically operate entirely on explicit symbolic representations of data cropper2022inductive . Some recent works, such as prob_popper have begun to address this limitation for probabilistic data.
Recent work on differentiable ILP solvers has attempted to address some of these issues by employing gradient-based optimization methods to search for rules in a numerically parameterized search space cohen2016tensorlog ; yang2017differentiable ; evans2018learning ; sadeghian2019drum ; payani2019inductive ; yang2020learn . These differentiable methods are noise robust, and some can scale to datasets with very large numbers of facts and predicate types. The numerical nature of these methods has also allowed some to interface with continuous valued data or even other machine learning models for end-to-end learning on mixed symbolic and non-symbolic domains evans2018learning .
While these are valuable properties, most differentiable ILP methods cannot represent or learn the full scope of language features supported by some symbolic methods such as N-ary predicates, lists, number systems, and recursive rule evaluation. These methods also vary significantly in their scalability and expressiveness. Methods such as $\delta$ ILP (evans2018learning, ) and dNL-ILP (payani2019inductive, ) can represent complex rules supporting more traditional language features, but this comes at a significant memory cost that seriously restricts the size of problems that they can be applied to. Other, more memory efficient ILP methods such as Neural-LP yang2017differentiable , DRUM sadeghian2019drum , and NLIL yang2020learn can scale to much larger datasets, but they adopt restrictive rule syntax and support very few language features. GLIDR improves on the inference algorithm used by these methods to enable differentiable learning of rules that have more general syntax. In doing so, GLIDR can learn relationships that are impossible to represent for previous memory-efficient differentiable ILP methods. In this paper we demonstrate that:
1. The added expressiveness of our method translates into performance improvements on knowledge graph completion tasks.
1. Our method retains performance when subject to noisy training data.
1. Hard rules extracted from our method retain significant performance.
1. Our method can be effectively co-trained with other deep learning models using end-to-end optimization.
### 1.4 Chain-Like Rule Syntax
Most differentiable ILP methods can learn rules that conform to a schema that we describe as ”chain-like”.
**Definition 1.1**
*Any $n$ -variable logic rule that can be equivalently expressed in the standard form described by Equation 1 is chain-like.
$$
\forall\{Z_{i}\}_{i=1}^{n}\left(P_{h}(Z_{1},Z_{n})\leftarrow\bigwedge_{i=1}^{n-1}P_{i}(Z_{i},Z_{i+1})\right) \tag{1}
$$*
In this schema, there are $n$ logic variables with $n-1$ binary (2-ary) body literals that form a ”chain” between the head variables. In practice, the restriction that argument order must follow the $P({Z_{i},Z_{i+1}})$ pattern is typically relaxed by introducing ”inverse” predicates such that $P_{inv}(X,Y)\Leftrightarrow P(Y,X).$ This means that both $P_{head}(X,Y)\leftarrow P_{A}(X,Z_{1}),P_{B}(Z_{1},Z_{2}),P_{C}(Z_{2},Y)$ and $P_{head}(X,Y)\leftarrow P_{A}(X,Z_{1}),P_{B}(Z_{2},Z_{1}),P_{C}(Y,Z_{2})$ can be made into valid chain-like rules.
Chain-like rules are favored by most differentiable ILP methods because rule inference is computationally convenient. Chain-like rules are also very natural for answering queries that commonly appear in information retrieval problems. For instance, the query ”Who is the brother of the director of the most recent Star Wars movie?” can be easily modeled as a chain of relations:
$$
?-\text{brother}(X,Z_{1}),\text{directedMovie}(Z_{1},Z_{2}),\text{mostRecentEntry}(Z_{2},Z_{3}),\text{StarWarsFranchise}(Z_{3}). \tag{2}
$$
GLIDR extends previous differentiable rule learning methods with a more complex rule inference algorithm based on message passing. This updated algorithm enables GLIDR to perform inference on non-chain-like, or what we call ”graph-like” rules. We will show that any rule conforming to the chain-like schema can also be expressed using our graph-like schema, demonstrating that the latter is strictly more general.
## 2 Methodology
GLIDR consists of (1) a graph-like rule representational structure, and (2) a differentiable message passing algorithm for deriving the entailment of rules encoded in this representational structure. These two features allow GLIDR to be optimized using gradient-based optimization to learn rules that conform to its representational structure and predict training data.
### 2.1 Overview of GLIDR’s Operational Modes
GLIDR’s differentiable design gives rise to two distinct operational modes primarily distinguished by how predicate selections are represented in the model weights.
- Soft Setting: In the soft setting, the contributions of predicates to the modeled logic rule are modulated by confidence values from discrete probability distributions formed from the model’s weights. During learning, candidate predicates are represented as linear superpositions of all possible predicates, and the learning process collapses these to predicate instances that are most consistent with the data. Consequentially, GLIDR’s inference results in this setting are a ”soft” approximation, blending influences from multiple logical paths and generally not guaranteed to match those of any particular rule. While not necessarily obeying strictly logical inference, this mode can still offer a degree of interpretability, as the learned confidence values may highlight dominant predicate choices and emergent rule-like structures.
- Hard Setting: In the hard setting, GLIDR uses strictly binary valued weights encoding a specific logic rule. In this setting, GLIDR’s inference can exactly model logical rule inference for certain classes of rules and approximately model inference for others. Section 2.6.3 discusses the distinction. The ability to differentiably approximate inference on specific ”hard” rules can be useful in special applications where a differentiable rule inference algorithm is required. When differentiability is not required, symbolic solvers offer more efficient and exact rule inference.
GLIDR can be used to identify logical rules by applying a rule extraction algorithm to the model weights learned in the soft setting. Rules extracted from GLIDR’s weights are strictly logical, offering direct human interpretability. Generally, there is some task performance lost when extracting a logical rule from GLIDR, however this depends on the degree of convergence in the model weights. It is possible for GLIDR to converge to weight configurations in the soft setting that correspond closely to discrete logic rules, enabling high-fidelity rule extraction.
### 2.2 GLIDR’s Graph-Like Rule Syntax
The key innovation that allows GLIDR to outperform other differentiable rule learning methods is support for a more general class of logic rules. GLIDR can learn rules which conform to a more expressive schema than chain-like rules. We describe rules that conform to this schema as ”graph-like”.
**Definition 2.1**
*Any $n_{v}$ -variable logic rule that can be equivalently expressed in the standard form described by Equation 3 (with $n\geq n_{v}$ variables) is a graph-like rule.
$$
\forall\{Z_{i}\}_{i=1}^{n}\left(P_{h}(Z_{1},Z_{n})\leftarrow\bigwedge_{i=1}^{n-1}\bigwedge_{j=i+1}^{n}P_{i,j}(Z_{i},Z_{j})\right) \tag{3}
$$*
Equation 3 defines the graph-like rule schema involving $n$ distinct variables, $Z_{1},\ldots,Z_{n}$ . The head of the rule, $P_{h}\left(Z_{1},Z_{n}\right)$ , uses the first and last variables of this indexed set. The body is a conjunction of $n(n-1)/2$ binary literals, $P_{i,j}\left(Z_{i},Z_{j}\right)$ , one for each distinct pair of variables $\left(Z_{i},Z_{j}\right)$ where $i<j$ . This schema defines a maximal set of potential directed interactions between variables. Figure 1 illustrates this maximal, directed acyclic graph (DAG) of literals for $n=4$ variables. $Z_{1}$ $Z_{2}$ $Z_{3}$ $Z_{4}$ $P_{1,2}$ $P_{1,3}$ $P_{1,4}$ $P_{2,3}$ $P_{2,4}$ $P_{3,4}$
Figure 1: Graphical illustration of the variables and predicates in the graph-like rule schema for $n=4$ . The graph-like schema invokes a directed acyclic graph (DAG) representation.
### 2.3 Equivalently Expressing Graph-Like Rules
The implicit assertion in Definition 2.1 that a wide range of $n_{v}$ -variable rules can be ”equivalently expressed” by the graph-like schema hinges on the flexibility afforded by freely selecting predicates for each $P_{i,j}$ ”slot”. When provided with a set of background predicates, $\mathcal{P}_{bg}$ , with which to build a rule, GLIDR automatically constructs an extended set of background predicates, $\mathcal{P}^{*}_{bg}$ , which includes:
- Standard Domain Predicates: The set of available domain predicates from $\mathcal{P}_{bg}$ . These comprise the union of all predicates represented in the background knowledge.
- A ”Null” Predicate ( $P_{true}$ ): This predicate is universally true (e.g., $P_{true}(A,B)$ holds for any $A,B$ ). When a schema slot $P_{i,j}$ is instantiated with $P_{true}$ , the literal $P_{true}(Z_{i},Z_{j})$ becomes logically redundant within the body’s conjunction. This effectively ”masks” or removes that specific $P_{i,j}(Z_{i},Z_{j})$ literal from the rule body. This predicate allows the maximal schema to represent rules with sparser graphical structures.
- Inverse Predicates ( $P_{inv}$ ): For every predicate $P(X,Y)$ from the domain $\mathcal{P}_{bg}$ , the inverse predicate $P_{inv}(X,Y)\Leftrightarrow P(Y,X)$ is included in $\mathcal{P}^{*}_{bg}$ . As in the case of chain-like rules, this provides flexibility in constructing literals with argument orderings that disobey the schema’s fixed $Z_{i}\to Z_{j}$ slot structure.
The use of these additional background predicates allows GLIDR to represent an expansive and diverse set of logic rules. To illustrate this, consider the logic rule depicted in Figure 2, $P_{h}(X,Y)\leftarrow R_{1}(X,B)\land R_{2}(X,C)\land R_{3}(B,C)\land R_{4}(B,Y)\land R_{5}(Y,C)$ . This rule is distinctly non-chain-like because the intermediate variables $B,C$ each appear in more than 2 literals, meaning that they must ”branch” and violate the multi-hop structure of chain-like rules. $X$ $B$ $C$ $Y$ $R_{1}$ $R_{2}$ $R_{3}$ $R_{4}$ $R_{5}$
Figure 2: Conceptual graph of the example rule $P_{h}(X,Y)\leftarrow R_{1}(X,B)\land R_{2}(X,C)\land R_{3}(B,C)\land R_{4}(B,Y)\land R_{5}(Y,C)$ .
Figure 3 illustrates how this 4-variable conceptual rule is equivalently expressed using GLIDR’s graph-like schema, instantiated here with $n=5$ schematic variables ( $Z_{1},\dots,Z_{5}$ ). This representation is achieved by first mapping the conceptual rule’s four variables $(X,B,C,Y)$ to a subset of the five schema variables $(Z_{1},\dots,Z_{5})$ . This leaves one schema variable $(Z_{4})$ effectively unused in this particular rule. Then, the appropriate $P_{i,j}$ predicates in the schema are instantiated with the conceptual rule’s predicates ( $R_{1},\dots,R_{5}$ ), utilizing an inverse predicate ( $R_{5,inv}$ ) to make $P_{3,5}$ represent $R_{5}(Y,C)$ . Finally, the $P_{true}$ predicate is assigned to all remaining $P_{i,j}$ in the maximal rule (illustrated by dotted lines in the diagram). This example highlights how an appropriate selection of each $P_{i,j}$ from $\mathcal{P}^{*}_{bg}$ allows GLIDR to precisely represent diverse graph-like rules. $Z_{1}$ $Z_{2}$ $Z_{3}$ $Z_{4}$ $Z_{5}$ $R_{1}$ $R_{2}$ $R_{3}$ $R_{4}$ $R_{5,inv}$
Figure 3: Example rule from Figure 2 equivalently represented within GLIDR’s graph-like schema for $n=5$ variables ( $Z_{1}\equiv X,Z_{2}\equiv B,Z_{3}\equiv C,Z_{5}\equiv Y$ ; $Z_{4}$ is unused). Solid lines are active predicates from the rule (e.g., $P_{1,2}\equiv R_{1}$ , $P_{3,5}\equiv R_{5,inv}$ ); dotted lines represent schema slots occupied by $P_{true}$ .
### 2.4 Rule Inference Characteristics
GLIDR can learn rules that are syntactically recursive, meaning that the predicate in the rule head also appears in the rule body. GLIDR does not support recursive execution or unfolding of rules; all body literals are exclusively resolved by direct lookup against the ground facts in a background knowledge base. This means that rules learned by GLIDR can capture recursive patterns but evaluation of such rules is limited to single-step deductive lookup. Similarly, GLIDR can not use logic rules as background knowledge without first deriving their consequences as ground facts. All background knowledge used by GLIDR must be expressed as ground facts.
GLIDR’s inference algorithm performs ground query evaluation and does not generally support open queries (queries with ungrounded head variables). To evaluate queries of this form, GLIDR uses a generate and test approach, where all possible groundings of an ungrounded head variable are instantiated and tested. This limitation is a consequence the more complex rule inference algorithm required to support graph-like rules, and it is a notable departure from previous works like Neural-LP, DRUM, and NLIL. The requirement of exhaustive constant enumeration means that rule inference with GLIDR does not scale well when addressing open queries on large knowledge bases. For example, GLIDR took around 40 hours to generate all tail predictions for the knowledge graph completion benchmark on the Freebase15k-237 dataset using 4 NVIDIA A100 GPUs.
Unlike previous methods such as Neural-LP, DRUM, and NLIL, the rule parameterization in GLIDR is fixed rather than generated from a neural network. This means that rules learned by GLIDR must be individually instantiated and trained for different target predicates. This is not a fundamental limitation of the method, and future work could generate GLIDR’s weights with a neural network for added training efficiency.
### 2.5 Differentiable Rule Inference via Iterative Consistency Propagation
The core inference mechanism in GLIDR, while implemented with differentiable linear algebra for end-to-end learning, conceptually mirrors the iterative enforcement of local constraints employed by arc consistency algorithms (e.g., AC-3 mackworth_ac3 ) in constraint satisfaction problems (CSPs). During inference, GLIDR maintains a ”soft” domain of potential entity groundings for each logic variable. Predicates in each body literal act as differentiable constraints acting on these variables. The inference algorithm iteratively refines the soft domains for each variable via message passing until a fixed point is reached or unsatisfiability is detected.
#### 2.5.1 GLIDR Initialization and Data Inputs
During inference and training, GLIDR operates on a background knowledge graph, denoted $\mathcal{G}_{bg}$ , which contains all of the ground facts from which GLIDR will reason. Each ground fact is a triple ( $(e_{i},r_{k},e_{j})\equiv r_{k}(e_{i},e_{j}).$ ) describing a relationship $r_{k}$ (the predicate with index $k$ ) between two entities $e_{i},e_{j}$ . GLIDR treats these relationships as directional, meaning that generally $(e_{i},r_{k},e_{j})\neq(e_{j},r_{k},e_{i})$ .
**Definition 2.2**
*A knowledge graph $\mathcal{G}$ contains all triples from a set of facts $\mathcal{F}$ . Each triple contains an ordered pair of entities from the set of graph entities, $e_{i},e_{j}\in\mathcal{E}$ , and a relation $r\in\mathcal{P}$ from the set of graph predicates. A unique index is defined on the sets of entities and relations such that $(e_{i}=e_{j})\Leftrightarrow(i=j)$ and $(r_{k}=r_{l})\Leftrightarrow(k=l)$ .
$$
\mathcal{G}=\{(e_{i},r_{k},e_{j})_{l}\}_{l=1}^{|\mathcal{F}|} \tag{4}
$$*
GLIDR encodes the background graph $\mathcal{G}_{bg}$ into a numerical representation for inference. First, the set of background predicates is augmented with the inclusion of inverse predicates and $P_{true}$ to create the extended background predicate set $\mathcal{P}_{bg}^{*}$ as described in Section 2.3. Next, $\mathcal{F}_{bg}$ is augmented with the addition of ground facts for each inverse predicate, such that:
$$
\mathcal{F}_{bg}^{*}=\mathcal{F}_{bg}\cup\{(e_{j},r_{k,inv},e_{i}):\forall(e_{i},r_{k},e_{j})\in\mathcal{F}_{bg}\} \tag{5}
$$
Finally, we construct a sparse binary adjacency tensor $\mathbf{B}\in\{0,1\}^{|\mathcal{E}_{bg}|\times|\mathcal{E}_{bg}|\times|\mathcal{P}^{*}_{bg}|}$ . Each element of this adjacency tensor encodes a triple from $\mathcal{F}^{*}_{bg}$ such that $((e_{i},r_{k},e_{j})\in\mathcal{F}^{*}_{bg})\Leftrightarrow(\mathbf{B}_{j,i,k}=1)$ . The adjacency matrix for $P_{true}$ is ill-defined and non-sparse, so this relationship is handled algorithmically and its corresponding slice of $\mathbf{B}$ is all zeros. During inference, a GLIDR model is presented with a batch of triples $\{(e_{i},r_{k},e_{j})\}_{l}$ , with each $(e_{i},e_{j})$ encoded as one-hot vectors $x_{i},x_{j}\in\{0,1\}^{|\mathcal{E}_{bg}|}:x_{i,i}=1,x_{j,j}=1$ , and the background graph $\mathcal{G}_{bg}$ in the form of $\mathbf{B}$ . For each triple, GLIDR produces a score $\hat{y}\in(0,1)$ indicating the likelihood of that fact being implied by the modeled rule for $r_{k}$ given $\mathcal{G}_{bg}$ .
While the adjacency tensor $\mathbf{B}$ provides a fixed numerical encoding of the background knowledge, the specific rule structure that GLIDR models is determined by a set of learnable parameters, or weights. A GLIDR model is configured to represent any graph-like rule with $n_{v}\leq N$ distinct logic variables. It accomplishes this by initializing a numerical encoding of a graph-like rule with $n=N$ schematic variables following Equation 3. For each of the $N(N-1)/2$ body literals in the schematic rule, GLIDR stores a learnable logit that encodes which predicate from the extended background set $\mathcal{P}_{bg}^{*}$ should occupy that slot in the rule body.
**Definition 2.3**
*For each predicate slot $(i,j):1\leq i<j\leq N$ in the $N$ -variable graph-like schema defined in Equation 3, GLIDR maintains a vector of learnable logit parameters:
$$
\theta_{i,j}\in\mathbb{R}^{|\mathcal{P}_{bg}^{*}|} \tag{6}
$$
When the softargmax function $\sigma(\cdot)$ is applied to a vector of logits, the result is a discrete probability distribution over the set of predicates in $\mathcal{P}_{bg}^{*}$ . The resulting probability weights $w_{i,j,k}$ encode the strength of predicate $r_{k}$ ’s contribution to the modeled body literal $P(Z_{i},Z_{j})$ :
$$
w_{i,j}\in\mathbb{R}^{|\mathcal{P}_{bg}^{*}|}=\sigma(\theta_{i,j})=\frac{e^{\theta_{i,j}}}{\sum_{k=1}^{|\mathcal{P}_{bg}^{*}|}e^{\theta_{i,j,k}}} \tag{7}
$$*
#### 2.5.2 Numerical Representation of Variables and Predicates
During inference, each logic variable (instantiated from the graph-like schema in Equation 3 with $N$ nodes) $\{Z_{i}\}_{i=1}^{N}$ is associated with a state vector $\phi_{i}\in\mathbb{R}^{|\mathcal{E}_{bg}|}$ . Each element in a state vector $\phi_{i,l}\in[0,1]$ represents the current belief that the entity $e_{l}\in\mathcal{E}_{bg}$ satisfies all adjacent constraints imposed on the grounding of $Z_{i}$ by the body literals it is involved in. This is analogous to the domain $D(Z_{i})$ tracked during an arc-consistency algorithm like AC-3 mackworth_ac3 . If at any time, $\max(\phi_{i})=0$ , then a domain wipeout has occurred, meaning that there are no possible groundings of $Z_{i}$ that satisfy the constraints placed upon it, and the rule must be false. At time step $t=0$ of inference, the first and last state vectors are initialized to equal the one-hot encodings of the input head entities $(e_{i},e_{j})$ , and all other state vectors are initialized to $1$ , indicating an unconstrained initial domain:
$$
\phi_{k}^{(0)}=\begin{cases}x_{i}&\text{if }k=1\\
x_{j}&\text{if }k=N\\
\mathbf{1}^{|\mathcal{E}_{bg}|}&\text{else}\end{cases} \tag{0}
$$
Each predicate slot in the modeled rule schema $P_{i,j}(Z_{i},Z_{j})$ is modeled by a soft adjacency matrix $\mathbf{M}_{i,j}\in\mathbb{R}^{|\mathcal{E}_{bg}|\times|\mathcal{E}_{bg}|}$ that acts as a learnable, differentiable constraint on the states $\phi_{i},\phi_{j}$ of variables $Z_{i},Z_{j}$ . Candidate predicates are represented as linear superpositions of all possible predicates (Equation 9), and the learning process collapses this superposition to predicate instances that are most consistent with the data.
**Definition 2.4**
*The soft adjacency matrix $\mathbf{M}_{i,j}\in\mathbb{R}^{|\mathcal{E}_{bg}|\times|\mathcal{E}_{bg}|}$ for graph-like rule schema slot $P_{i,j}(Z_{i},Z_{j})$ is the stochastic weighted sum of each adjacency matrix from $\mathcal{P}^{*}_{bg}$ according to the probability mass vector $w_{i,j}$ , defined in Equation 7.
$$
\mathbf{M}_{i,j}=\sum_{k=1}^{|\mathcal{P}^{*}_{bg}|}w_{i,j,k}\mathbf{B}_{:,:,k} \tag{9}
$$*
#### 2.5.3 Iterative Message Passing and State Refinement
GLIDR employs an iterative message-passing procedure to propagate local constraints and refine the soft domains tracked by each variable’s state vector $\phi_{i}$ . Message passing is organized into $R$ rounds that alternate between forward and backward passes through the rule. In each round, there are $N$ time-steps $t$ , corresponding to the $N$ variables in the graph-like schema. After each round, the variables in a rule are implicitly re-indexed in reverse-topological order and the adjacency tensor $B$ is transposed such that $B_{i,j,k}=B_{j,i,k}$ . Messages in the next round are then effectively sent ”backward” in the reverse order of those sent during the previous round. This scheduling process ensures that messages are always computed using the most up-to-date information about each variable. As a result, messages cascade from $(Z_{1}\rightarrow Z_{N})$ , $(Z_{N}\rightarrow Z_{1})$ , $(Z_{1}\rightarrow Z_{N})$ etc. in alternating ”forward” and ”backward” passes as depicted in Figure 4. The remainder of this section will assume the indexing scheme of the forward pass. Round 1: Forward Pass (Processing Order: $Z_{1}\to Z_{2}\to Z_{3}\to Z_{4}$ ) $Z_{1}$ $Z_{2}$ $Z_{3}$ $Z_{4}$ $\psi_{1\rightarrow 2}^{(t_{1})}$ $\psi_{1\rightarrow 3}^{(t_{1})}$ $\psi_{1\rightarrow 4}^{(t_{1})}$ $\psi_{2\rightarrow 3}^{(t_{2})}$ $\psi_{2\rightarrow 4}^{(t_{2})}$ $\psi_{3\rightarrow 4}^{(t_{3})}$ $t_{1}:\phi_{1}^{(1)}\equiv\phi_{1}^{(0)}$ $t_{2}:\phi_{2}^{(0)}\rightarrow\phi_{2}^{(1)}$ $t_{3}:\phi_{3}^{(0)}\rightarrow\phi_{3}^{(1)}$ $t_{4}:\phi_{4}^{(0)}\rightarrow\phi_{4}^{(1)}$ Round 2: Backward Pass (Processing Order: $Z_{4}\to Z_{3}\to Z_{2}\to Z_{1}$ ) (using transposed/inverse relations) $Z_{1}$ $Z_{2}$ $Z_{3}$ $Z_{4}$ $\psi_{4\rightarrow 3}^{(t^{\prime}_{1})}$ $\psi_{4\rightarrow 2}^{(t^{\prime}_{1})}$ $\psi_{4\rightarrow 1}^{(t^{\prime}_{1})}$ $\psi_{3\rightarrow 2}^{(t^{\prime}_{2})}$ $\psi_{3\rightarrow 1}^{(t^{\prime}_{2})}$ $\psi_{2\rightarrow 1}^{(t^{\prime}_{3})}$ $t^{\prime}_{1}:\phi_{4}^{(2)}\equiv\phi_{4}^{(1)}$ $t^{\prime}_{2}:\phi_{3}^{(1)}\rightarrow\phi_{3}^{(2)}$ $t^{\prime}_{3}:\phi_{2}^{(1)}\rightarrow\phi_{2}^{(2)}$ $t^{\prime}_{4}:\phi_{1}^{(1)}\rightarrow\phi_{1}^{(2)}$
Figure 4: Illustration of GLIDR’s iterative message passing over two rounds for a 4-node graph-like rule schema ( $Z_{1},Z_{2},Z_{3},Z_{4}$ ). (Top) Round 1: Forward pass, processing variables in order $Z_{1}\to Z_{4}$ . Messages $\psi_{i\rightarrow j}^{(t)}$ flow from $Z_{i}$ to $Z_{j}$ (where $i<j$ ). (Bottom) Round 2: Backward pass, processing variables in order $Z_{4}\to Z_{1}$ . Messages $\psi_{j\rightarrow i}^{(t^{\prime})}$ flow from $Z_{j}$ to $Z_{i}$ (where $i<j$ ). Messages are computed using using transposed/inverse relations. Each $t_{k}$ or $t^{\prime}_{k}$ indicates a sequential update and message emission step within its respective round.
At each time-step within a round $R$ , the value of a state vector $\phi_{j}^{(R-1)}$ is updated using the set of incoming messages from variables $Z_{i<j}$ , and then its new value $\phi_{j}^{(R)}$ is used to compute new messages to all variables $Z_{k>j}$ . Messages are computed and communicated along the ”arcs” (predicate slots representing body literals) of the schematic rule structure. Each message $\psi_{i\rightarrow j}\in\mathbb{R}^{|\mathcal{E}_{bg}|}$ encodes a soft belief about which groundings in the domain of $Z_{j}$ are compatible with the current domain of $Z_{i}$ according too the predicate modeled by $\mathbf{M}_{i,j}$ .
**Definition 2.5**
*A message at time-step $t$ in round $R$ , $\psi_{i\rightarrow j}^{(t)}\in\mathbb{R}^{|\mathcal{E}_{bg}|}$ , sent from $Z_{i}\rightarrow Z_{j}$ is the matrix-vector product of the current state vector for $Z_{i}$ , $\phi_{i}^{(R)}$ , and the soft adjacency matrix $\mathbf{M}_{i,j}$ associated with the $i,j$ slot in the graph-like rule schema. The scalar value $w_{i,j,(-1)}$ holds the probability mass associated with the $P_{true}$ predicate’s involvement in the $i,j$ arc.
$$
\psi_{i\rightarrow j}^{(t)}=\mathbf{M}_{i,j}\phi_{i}^{(R)}+\mathbf{1}\cdot w_{i,j,(-1)} \tag{10}
$$*
If the soft adjacency matrix $\mathbf{M}_{i,j}$ approximates the adjacency matrix of a specific predicate from $\mathcal{P}_{bg}^{*}$ , then the message $\psi_{i\rightarrow j}$ holds the set of all destination entities in $\mathcal{G}$ of edges originating at the entities encoded in $\phi_{i}$ by the modeled relationship. Conceptually, this message encodes a soft representation of a set of entities where values crossing some threshold $\epsilon$ are considered present in the set:
$$
\psi_{i\rightarrow j}\approx\{e_{j}:(e_{i},r_{\mathbf{M}_{i,j}},e_{j})\in\mathcal{F}_{bg}^{*},\forall e_{j}\text{ s.t. }(\phi_{i})_{i}>\epsilon\} \tag{11}
$$
The addition of the weight associated with $P_{true}$ ensures that the message becomes $\mathbf{1}$ when all probability mass is placed on $P_{true}$ , effectively imposing no constraint on the destination variable’s domain. As in a constraint satisfaction problem, a logic variable in a rule body must have a valid grounding that simultaneously satisfies the constraints imposed by all adjacent body literals for a rule to be true. Determining simultaneous satisfaction involves computing set intersections on the soft set-like state variables $\phi_{i}$ . We compute approximate set intersection using the element-wise minimum operation. Before a variable $Z_{i}$ can emit a message to its neighboring variables $Z_{j>i}$ , it must first update its state to reflect any new messages that it received in previous time steps.
**Definition 2.6**
*A state update, $\phi_{i}^{(R-1)}\rightarrow\phi_{i}^{(R)}$ , for variable $Z_{i}$ in round $R$ , is the element-wise minimum between all incoming messages from variables $Z_{j<i}$ from previous time steps in the round, $\{\psi_{k\rightarrow i}^{(k)}\}_{k=1}^{i-1}$ , and the state vector $\phi_{i}^{(R-1)}$ .
$$
\phi_{i}^{(R)}=\min(\phi_{i}^{(R-1)},\psi_{1\rightarrow i}^{(1)},\ldots,\psi_{(i-1)\rightarrow i}^{(i-1)}) \tag{1}
$$*
During a forward pass, $Z_{1}$ has no incoming messages, and Definition 2.6 reduces to $\phi_{1}^{(R)}=\phi_{1}^{(R-1)}$ . The same is true for $Z_{N}$ during a backward pass.
### 2.6 Convergence and Rule Evaluation
GLIDR’s differentiable inference, as described, proceeds through iterative rounds of message passing and variable state refinement. This section details how this iterative process terminates, how the final variable states are used to evaluate a rule’s entailment for a given query, and the theoretical underpinnings of these outcomes with respect to Constraint Satisfaction Problem (CSP) theory.
#### 2.6.1 Terminating Inference
In a ”pure” implementation of GLIDR, message passing rounds would continue until one of the following termination conditions was met:
- Convergence to a Fixed Point: The iteration is complete if the state vectors $\phi_{i}$ for all variables $Z_{i}$ show negligible change between successive rounds. That is, for a round $R$ , if $||\phi_{i}^{(R)}-\phi_{i}^{(R-1)}||<\epsilon$ for all $i$ and some tolerance $\epsilon$ . This indicates that the system has settled into a stable belief about the feasible domains of each variable.
- Domain Wipeout: The iteration terminates immediately if the state vector $\phi_{i}^{(R)}$ for any variable $Z_{i}$ effectively becomes a zero vector (e.g., $\max(\phi_{i}^{(R)})\approx 0$ ). This signifies that no consistent grounding can be found for that variable under the propagated constraints.
In practice, we typically set a fixed maximum number of message passing rounds $R_{max}$ to constrain inference complexity.
#### 2.6.2 Determining Rule Entailment
After the final round of message passing, GLIDR produces a score, $\hat{y}$ , indicating the confidence that the initial grounding query (e.g., $P_{h}(e_{i},e_{j})$ ) is true according to the modeled rule.
**Definition 2.7**
*A GLIDR model’s confidence score, $\hat{y}\in(0,1)$ , derived from the variable states $\{\phi_{i}^{(R_{max})}\}_{i=1}^{N}$ after message passing, represents the model’s predicted confidence that the query grounding $P_{h}(e_{h},e_{t})$ satisfies the modeled rule for $P_{h}$ .
$$
\hat{y}=\min_{1\leq i\leq N}(\max_{k}(\phi_{i,k}^{(R_{max})})) \tag{13}
$$*
The min-of-maxes form in Definition 2.7 ensures that the final predictions produced by GLIDR reflect any domain wipeout that may have occurred during message passing. If any state variable is close to the zero vector, then the overall score will be close to zero. If all state vectors contain entries close to $1$ , then the overall score will be close to $1$ .
#### 2.6.3 Connections to Constraint Satisfaction Theory
The message passing inference algorithm that GLIDR uses to determine rule satisfiability can be interpreted as a form of iterated local consistency enforcement. Iterative local consistency is the same core inference mechanism used by backtrack-free algorithms like AC-3 mackworth_ac3 to solve constraint satisfaction problems. Local consistency algorithms are characterized by applying constraints locally between variables and iterating until convergence. The constraints imposed on variable groundings by body literals in GLIDR are analogous to arc consistency enforcement mackworth_ac3 . CSP theory offers several theoretical results that can applied to GLIDR’s inference in the hard setting. In the soft setting, GLIDR’s inference is already fully approximate.
- Domain Wipeout Implies Falsity: The occurrence of a domain-wipeout during local consistency propagation guarantees unsatisfiability of the constraint network russel_ai_modern_approach . The converse is not generally true.
- Fixed-Point Proves Satisfiability for Tree-Like Networks: If a constraint network is structured like a tree, then arrival at a fixed point (without domain collapse) during arc consistency propagation is sufficient to prove satisfiability Kumar_1992 ; freuder_suff_cond . This implies that GLIDR’s inference can be exact for cycle free rules such as chain-like and tree-like rules.
- Fixed-Point in Loopy Network Does Not Prove Satisfiability: In a loopy network, it is possible to arrive at a fixed point solution that is locally consistent, but still globally unsatisfiable. Proving satisfiability in such a case requires backtracking, and GLIDR’s inference will be incorrect. Figure 5 illustrates such an example. $e_{0}$ $e_{1}$ $e_{2}$ $e_{3}$ $e_{4}$ $e_{5}$ $e_{j}$ $e_{i}$ $Z_{1}$ $Z_{2}$ $Z_{4}$ $Z_{3}$ $Z_{5}$
Figure 5: A simple counterexample illustrating variable domains that are locally consistent but not globally satisfiable. Each stack of entities is the domain $D(Z_{i})$ for a logic variable in the rule $P_{h}(Z_{1},Z_{5})\leftarrow P_{1,2}(Z_{1},Z_{2})\wedge P_{2,4}(Z_{2},Z_{4})\wedge P_{4,3}(Z_{4},Z_{3})\wedge P_{3,2}(Z_{3},Z_{2})\wedge P_{4,5}(Z_{4},Z_{5})$ . The arrows represent background facts satisfying the constraints imposed by each body literal. The domains are an entirely arc consistent fixed point, but the modeled query is not true.
### 2.7 Optimization
GLIDR models are essentially binary classifiers that accept a background graph and a pair of entity indices to make predictions. This means that, unlike Neural-LP and DRUM yang2017differentiable ; sadeghian2019drum , GLIDR requires negative examples during training. We sample positive examples of entities that share the target relationship to form mini-batches. We employ the closed-world hypothesis during negative example selection, sampling entity pairings that, to the best knowledge in the training data, do not share the target relationship. The sampling rates of positive and negative examples are weighted to ensure an average 1:1 ratio of positives and negatives in a mini-batch during training. GLIDR is optimized to maximize its confidence score when applied to a positive example and minimize its confidence score when applied to a negative example. We adopt the pairwise logistic loss burges2005ranking when training GLIDR for ranking problems because it promotes high relative score difference between positive and negative examples in a batch, even when a modeled rule is unsatisfiable and producing low confidence scores.
**Definition 2.8**
*The pairwise logistic loss burges2005ranking for a batch of predictions $\hat{\mathbf{y}}$ and score labels $\mathbf{y}$ is defined by Equation 14. $\mathbb{I}[y_{i}>y_{j}]$ is the indicator function and takes a value of 1 when $\mathbf{y_{i}}>\mathbf{y_{j}}$ and 0 otherwise.
$$
l(\hat{\mathbf{y}},\mathbf{y})=\sum_{i}\sum_{j}\mathbb{I}[\mathbf{y_{i}}>\mathbf{y_{j}}]\log(1+\exp(-(\hat{\mathbf{y}}_{i}-\hat{\mathbf{y}}_{j}))) \tag{14}
$$*
The pairwise logistic loss is constructed for problems with continuous labels, but we can apply it to problems like ours with discrete labels $y\in\{0,1\}$ .
We typically learn multiple rule definitions for each target relationship when training GLIDR on a dataset. A set of weights is randomly initialized for each rule definition at the beginning of training, and each rule produces predictions during training. For a given training batch, the pairwise logistic loss is applied to each rule’s predictions and the resulting loss values are averaged together. We use the AdamW optimizer adamw2017 to train GLIDR, and we find that the method converges best with high learning rates in the vicinity of $0.1$ . We also find that GLIDR benefits from a high weight decay, also in the vicinity of $0.1$ .
### 2.8 Rule Extraction
The approximate rules learned by GLIDR in the soft setting must be extracted before they can be used by a symbolic solver. The process of rule-extraction is crucial to the interpretability of differentiable rule learning methods, and many differentiable rule learning methods approximate rules that are difficult to explicitly extract faithfulre .
Chain-like differentiable ILP techniques like Neural-LP and DRUM yang2017differentiable ; sadeghian2019drum derive rule satisfiability by counting paths on the background graph and mix different sequential reasoning pathways to produce a confidence score. This can make the extraction of rules that correctly reflect the behavior of the soft models difficult faithfulre . GLIDR mitigates some of these issues by maintaining separate and explicit pathways for interaction between variables. GLIDR’s inference process is also more closely related to traditional logical inference, seeking a mutually consistent state across the soft domains that it tracks. The constraint that these soft domains are bounded on $[0,1]$ prevents GLIDR from ”counting” the frequency of entities in a domain (at least in the hard setting).
A key consideration in extracting symbolic rules from GLIDR arises when the learned probability distribution $w_{i,j}$ for predicate slot $(i,j)$ does not sharply concentrate on a single predicate. This indicates model uncertainty, or that multiple predicate types contributed to the learned behavior for that slot. GLIDR’s construction of the soft adjacency matrix for a slot, Equation 9, is inherently additive. This means that when multiple predicates $P_{k}$ have substantial weights $w_{i,j,k}$ , the inference step involving $\mathbf{M}_{i,j}$ effectively aggregates the outcomes as if each of these highly weighted predicates is ”active” simultaneously. Consequentially, the behavior of such a slot can be interpreted as a soft logical disjunction of the highly weighted predicates $\bigvee_{k}P_{k}$ . While the primary goal of GLIDR is to learn Horn clauses without disjunction among body literals, sometimes extracted rules can be more faithfully represented by introducing disjunctions.
One heuristic that we explore for rule extraction is a ”top $p$ ” sampling of each predicate distribution. All predicates with weights in the top $p$ cumulative probability mass are extracted and added to a disjunctive body term. If $P_{true}$ falls within the top $p$ probability mass, then $P_{true}$ is sampled for that slot instead of any other predicates. This heuristic has the desirable property that a highly converged soft model will often produce the same hard rule with top $p$ as with an argmax strategy (where the highest scoring predicate is assigned to each slot). This means that in highly converged models, the resulting rule is purely conjunctive. When a model shows lower convergence, a limited number of disjunctive body literals are introduced based on the parameter $p$ . If $p$ is low, then a limited number of disjunctive body literals are added to a rule. If $p$ is high, then a large number of disjunctive body literals can be added to a rule. The inclusion of many disjunctive body literals can hurt rule interpretability by introducing many possible truth conditions. In testing different rule extraction heuristics, we observed that no single heuristic worked best across all rules. This indicates that there is likely significant performance to be gained by applying a search-based approach to rule extraction.
During evaluation, we performed a top $p=0.25$ rule extraction on GLIDR models trained on multiple datasets. We observed that the disjunctions introduced were sometimes informative and reflected disjunctive patterns in the background data. For example, this rule for niece was extracted from the family dataset:
$$
\text{niece}(X,Y)\leftarrow\text{niece}(X,Z_{1})\wedge(\text{aunt}(Y,X)\vee\text{uncle}(Y,X))\wedge\text{brother}(Y,Z_{1}).
$$
While this rule isn’t perfect, mishandling the scenario where $Y$ is an aunt of $X$ , it does give us a glimpse into the internal tension within the model. The ”aunt or uncle” disjunction will explain every instance of niece, but it will also explain every instance of nephew. To control the gender of $X$ , the model has included the niece and brother terms, however they constrain $Y$ to be an uncle, hurting the generality of the rule. The model seems to be splitting the difference between a rule that fully commits to classifying an uncle-niece relationship, and a rule that classifies an aunt-niece relationship. In theory, a dangling niece $(X,Z_{2})$ term with no corresponding brother would be sufficient to make this an acceptable hard rule, however the split probability mass between the aunt and uncle predicates limits the maximum score of such a rule. This may indicate that more explicit handling of disjunctive terms could benefit future methods.
### 2.9 Complexity
When run until convergence, GLIDR’s worst-case inference compute complexity is $\mathcal{O}(N^{3}D^{3})$ . Where $N$ is the number of schematic variables, and $D=|\mathcal{E}_{bg}|$ is the maximum domain size (background entity count). Computing each message involves a matrix-vector product which is $\mathcal{O}(D^{2})$ . There are $\mathcal{O}(N^{2})$ messages passed in each round of message passing. If any round of message passing concludes without introducing a change in a variable domain, then a fixed-point has been reached and inference is converged. There are $\mathcal{O}(ND)$ total possible entities represented in all variable domains. In the worst-case, where only a single entry in a single domain is eliminated per round of message passing, it would take $\mathcal{O}(ND)$ rounds of message passing to reach a domain wipeout. This yields the overall worst-case complexity $\mathcal{O}(N^{3}D^{3})$ . The high-degree of sparsity in graph datasets (e.g. $\mathbf{B}$ is highly sparse) means that most messages are also highly sparse, leading to rapid domain convergence. The use of sparse linear algebra primitives also constrains the typical complexity of the matrix-vector product required for each message. GLIDR inference is typically only performed for a fixed $R_{max}$ rounds, so the typical inference compute complexity per-query $P_{h}(e_{i},e_{j})$ is $\mathcal{O}(N^{2}D^{2})$ . In the case of open queries like $P_{h}(e_{i},Y)$ , $D$ inferences must be made for the $D$ possible tail entities. This can be quite expensive as $|\mathcal{E}_{bg}|$ grows large.
## 3 Experiments
To assess the graph learning capabilities of GLIDR, we evaluate its performance on several knowledge graph completion benchmarks and subject it to mislabeling noise. Following the approach used by Neural-LP yang2017differentiable , each dataset is partitioned into four splits: train, validation, test, and facts. During training, the facts split is used to construct the background knowledge graph, $\mathcal{G}_{bg}$ , for rule inference. During validation and testing, both the facts and train splits are combined to form the background knowledge graph used for reasoning. The facts and train splits were formed by partitioning the train split commonly used by embedding methods yang2017differentiable . GLIDR fits rule definitions during the training stage and evaluates them during the validation and testing stages; therefore, we require that the sets of predicates in each split overlap. The rule definitions fit by GLIDR only involve lifted predicates and logic variables, so in contrast with many embedding methods, we do not require that the entities in any split overlap. In this sense, the rules learned by GLIDR are entirely inductive, and can be applied to any dataset with the appropriate predicates.
We implement GLIDR in JAX jax2018github using the experimental sparse module to perform sparse tensor operations. Our implementation also makes use of sharding and parallelism primitives provided by JAX to enable multi-gpu training with many rule bodies using model parallelism. We use the implementations of the pairwise logistic loss burges2005ranking and ranking utilities provided by Rax jagerman2022rax . Our experiments use the Optax deepmind2020jax implementation of the AdamW optimizer adamw2017 .
### 3.1 Knowledge Graph Completion
We evaluate GLIDR on the knowledge graph completion problem described by bordes2013translating . In this problem, a relational query of the form relation(head,?) is posed, and a system must find tail entities that complete the query by ranking all entities in the background graph by the likelihood that the fact relation(head,tail) exists in the knowledge base. To evaluate knowledge graph reasoning systems in this manner, a held-out set of facts from a knowledge base is used to generate queries, and systems must rank the entities that complete these held-out facts as highly as possible.
Bordes et al. establish several conventions for evaluating methods on this task. Queries are constructed to retrieve both head entities relation(?,tail) and tail entities relation(head,?) for each fact in the evaluation set. Retrieval metrics such as hits@ $k$ , which count the fraction of target entities that are ranked within the top $k$ results for each query are used to report performance. We adopt the filtered setting described by Bordes et al. in which true positive completions do not affect the rank of entities ranked below them. This setting modifies the interpretation of hits@ $k$ to be the proportion of target entities that are ranked below fewer than $k$ false positives. A further issue with ranking metrics arises when rankings have the potential for ties as is common with methods that assign numerical scores. Optimistic or pessimistic tie-breaking can have significant impacts on ranking evaluation as noted by sun2020evaluation , so we follow the recommendation of applying random tie-breaking.
For each dataset, we learn a collection of 8 rule definitions for each predicate. We initialize GLIDR with $N=4$ schematic variables, implying that the maximum depth of any learned rule is 3. This length restriction is consistent with the other methods we evaluate against. Following other rule learning methods yang2017differentiable ; qu2020rnnlogic ; cheng2023neural we allow GLIDR to learn recursive rule definitions during benchmarking. To avoid the possibility of recursive rules exploiting the facts that they are meant to predict, we ensure that we only train on positives from the train split, while negatives can be sampled from either the train or facts splits. This ensures that a positive training example never exists in the background data.
To facilitate better rankings, we create a weight for each rule definition based on that rule’s performance on the validation set. Each definition is assigned a weight equal to the ratio of the minimum average validation loss across definitions to its own average validation loss $w_{i}=\frac{\bar{l}_{\text{min}}}{\bar{l}_{i}}$ . The best performing definitions get a weight of $1.0$ and worse performing definitions get down-weighted. The final ranking score generated by GLIDR is the weighted sum of the confidence scores produced by each rule definition.
### 3.2 Datasets
We train and evaluate GLIDR on the knowledge graph completion task for the Family yang2017differentiable , Alyawarra Kinships denham1973 ; denham2016 , UMLS mccray2003umls ; bodenreider2004umls , and Freebase15k-237 toutanova2015observed datasets. For each of these datasets, we use the splits provided by Neural-LP yang2017differentiable . Family is a noisy dataset with 3007 entities related by 12 western kinship terms following the small Kinship dataset hinton1990kinship . The Unified Medical Language System (UMLS) is a dataset of 135 biomedical entities and 46 relational terms. The Alyawarra Kinships dataset (henceforth referred to as Kinships), is a dataset derived from ethanographic data collected by Denham in 1973. This dataset was constructed by first photographing 104 Alyawarra-speaking Aboriginal people of the central Australian outback. Participants were then shown pictures of the other 103 persons photographed and asked to name a kinship relation for each relative to themself. The resulting graph is fully connected and contains 25 different Alyawarra kinship terms. Freebase15k-237 is a subset of the Freebase knowledge graph containing 14541 entities and 237 relation types that primarily describe sports, media, and geographical concepts.
### 3.3 Existing Methods
We compare GLIDR to a selection of rule learning and embedding methods. Among embedding methods, we choose to compare against ConvE dettmers2018conve , an algorithm based on graph convolutions, and RotatE sun2019rotate an algorithm that makes use of complex vector space embedding transformations and an improved adversarial negative sampling technique. We also compare against RNNLogic qu2020rnnlogic , a hybrid rule-based and embedding method that learns chain-like rules. The first reported setting for RNNLogic makes use of both logical rules and learned entity embeddings. The second setting, denoted by w/o emb. is only rule-based and does not make use of embeddings. In addition to RNNLogic, we compare against NeuralLP yang2017differentiable , a differentiable chain-like rule learning method. DRUM sadeghian2019drum improves on NeuralLP by modifying the mechanism for variable-length rule learning. We also include NCRL cheng2023neural , another rule based method that learns compositional chain-like logic rules and scales well to large datasets.
| Model ConvE | Family MRR - | Kinships Hits@1 - | UMLS Hits@10 - | FB15k-237 MRR 0.83 | Hits@1 73.0 | Hits@10 98.0 | MRR 0.94 | Hits@1 92.0 | Hits@10 99.0 | MRR 0.32 | Hits@1 24.0 | Hits@10 49.0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| RotatE | 0.86 † | 78.7 † | 93.3 † | 0.65 | 50.4 | 93.2 | 0.74 | 63.6 | 93.9 | 0.34 | 24.1 | 53.3 |
| RNNLogic | - | - | - | 0.72 | 59.8 | 94.9 | 0.84 | 77.2 | 96.5 | 0.34 | 25.2 | 53.0 |
| w/o emb. | 0.86 † | 79.2 † | 95.7 † | 0.64 | 49.5 | 92.4 | 0.75 | 63.0 | 92.4 | 0.29 | 20.8 | 44.5 |
| Neural-LP | 0.88 † | 80.1 † | 98.5 † | 0.30 ‡ | 16.7 ‡ | 90.1 | 0.48 ‡ | 33.2 ‡ | 93.2 | 0.24 | 17.3 ‡ | 36.2 |
| DRUM (L=3) | 0.95 | 91.0 | 99.0 | 0.61 | 46.0 | 91.0 | 0.80 | 66.0 | 97.0 | 0.34 | 25.5 | 51.6 |
| NCRL | 0.91 | 85.2 | 99.3 | 0.64 | 49.0 | 92.9 | 0.78 | 65.9 | 95.1 | 0.30 | 20.9 | 47.3 |
| Soft ( $\mu$ ) | 0.90 | 93.2 | 95.6 | 0.72 | 73.5 | 93.1 | 0.81 | 87.8 | 95.2 | 0.20 | 18.6 | 35.6 |
| Soft ( $\sigma$ ) | 0.01 | 0.67 | 0.72 | 0.01 | 1.09 | 0.92 | 0.01 | 0.63 | 0.37 | - | - | - |
| Top $p=0.25$ ( $\mu$ ) | 0.66 | 68.4 | 72.4 | 0.61 | 61.7 | 78.3 | 0.67 | 71.2 | 87.0 | - | - | - |
| Top $p=0.25$ ( $\sigma$ ) | 0.04 | 4.75 | 5.42 | 0.01 | 1.53 | 1.77 | 0.02 | 2.82 | 2.20 | - | - | - |
Table 1: Performance of embedding and rule-based methods on several knowledge graph completion benchmarks. Embedding methods are reported above the first dashed line and rule-based methods below. The best result for each metric is reported independently in bold for embedding methods and rule-based methods. We report mean ( $\mu$ ) and standard deviation ( $\sigma$ ) scores for GLIDR in both the hard (”Top $p$ ”) and soft (”Soft”) settings across 10 runs for Family, Kinships, and UMLS. All scores for other differentiable rule learning systems are reported for the soft setting. Hits@ $k$ is reported in %. $[\dagger]$ indicates a result taken from the NCRL paper cheng2023neural . $[\ddagger]$ indicates a result from the RNNLogic paper qu2020rnnlogic . All other results are from the original papers.
### 3.4 Results
We compare mean reciprocal rank (MRR), Hits@1, and Hits@10 for GLIDR and the other selected algorithms in Table 1. For Family, Kinships, and UMLS, we train and evaluate GLIDR 10 times with different random seeds and report the mean and standard deviation for each metric. Generating tail rankings for all test queries on FB15k-237 is very expensive given GLIDR’s ground-and-check inference algorithm, and we only report the result from a single run. Compute resources and hyperparameters for each experiment are reported in the appendix A.
We observe that GLIDR performs very competitively with other rule learning methods. On Kinships, UMLS, and Family, GLIDR has the top performing Hits@1 among rule learning methods, and its scores are often competitive with embedding methods. GLIDR does not significantly improve on Neural-LP’s performance on FB15k-237. We hypothesize that the structure of the dataset may not benefit significantly from the added expressivity that GLIDR’s rules offer. FB15k-237 is also significantly larger than the other datasets studied, and it is possible that this difference necessitates special treatment with modified training hyperparameters.
Generally, we observe that our method performs better in Hits@1 than MRR or Hits@10. We believe that the highly-constrained nature of GLIDR’s rules produces sharper drops in confidence scores when entity pairings do not perfectly satisfy a rule. This allows learned rules to be highly selective in their decision criteria at the cost of covering fewer cases.
It is important to note, as previous authors have sadeghian2019drum , that rule based methods cannot be fairly compared with embedding methods, since embedding methods can store per-entity information at training time and utilize it at test time. Previous authors have shown that the performance of embedding methods suffers significantly in the purely inductive setting where no entities are shared between training and test time, while rule-based methods can retain much of their performance yang2017differentiable ; sadeghian2019drum .
We tested hard rules extracted from GLIDR’s soft weights using the top $p=0.25$ rule extraction heuristic on Kinships, UMLS, and Family. Inference was performed using GLIDR in the hard setting, with binary probability weights $w_{i,j}$ . We used the same weighted averaging based on validation loss as in the soft setting. We found that rules extracted from GLIDR retained a large proportion of the performance of the original soft models. In Kinships and UMLS, the soft rules still outperformed the next best rule learning method in Hits@1.
In keeping with the expressive nature of its rule parameterization, we observe that GLIDR learns collections of both chain-like and graph-like rules for each dataset. One example of a graph-like rule extracted from GLIDR during an experiment with the original Kinships data is visualized in Figure 6. This recursive rule for Agngiya was discovered from a schematic rule with $N=6$ . We found that this extracted rule achieved an F1 score of 0.803 when used to predict the existence of Agngiya relationships in the graph. This was a transductive setting, where all background data was available at training and test time. $X$ $Z_{1}$ $Z_{2}$ $Z_{3}$ $Y$ agngiya umbaidya aleriya adardiya adardiya aleriya male male
Figure 6: Illustration of the learned rule graph for a recursive rule discovered for Agngiya in the original Kinships dataset.
### 3.5 Performance Subject to Noise
To investigate the performance impact that noisy data has on GLIDR, we conduct an experiment where we purposefully introduce mislabeled edges into the training dataset. With some probability $p$ , we change the predicate type of each edge in the train and facts splits to a different predicate type during training. Although some edges may still match a fact from the unperturbed data after mislabeling, the widespread random relabeling of edges should introduce significant noise into the training graph. We evaluate GLIDR on Kinships, Family, and UMLS while varying the probability of mislabeling from $p=0$ to $p=1$ . We report Hits@1 for each of these trials in Figure 7. We find that our method shows significant robustness to mislabeling across all three datasets. In each case, GLIDR only incurs minor performance degradation at mislabeling rates below 50%. We also observe a steady decline in performance as mislabeling increases to 100% rather than a sudden drop, indicating that the method is consistently robust to noise even at high rates.
<details>
<summary>figs/mislabel_rate_figure_large.png Details</summary>
### Visual Description
\n
## Line Chart: Performance vs. Mislabeled Edge Probability
### Overview
This is a line chart illustrating the relationship between "Mislabeled Edge Probability" (x-axis) and a performance metric called "Hits@1" (y-axis). It compares the performance degradation of three distinct datasets or models—UMLS, Family, and Kinships—as the probability of incorrect labels in the data increases.
### Components/Axes
* **Chart Type:** Line chart with three data series.
* **X-Axis:**
* **Label:** "Mislabeled Edge Probability"
* **Scale:** Linear, ranging from 0.0 to 1.0.
* **Major Ticks:** 0.0, 0.2, 0.4, 0.6, 0.8, 1.0.
* **Y-Axis:**
* **Label:** "Hits@1"
* **Scale:** Linear, ranging from 0.0 to 1.0.
* **Major Ticks:** 0.0, 0.2, 0.4, 0.6, 0.8, 1.0.
* **Legend:** Located in the top-right corner of the plot area.
* **UMLS:** Represented by a dotted line (`...`).
* **Family:** Represented by a dash-dot line (`-.-`).
* **Kinships:** Represented by a solid line (`-`).
* **Grid:** Dashed horizontal and vertical grid lines are present at each major tick mark.
### Detailed Analysis
The chart plots the Hits@1 score against increasing levels of label noise. Below are the approximate trends and data points for each series, verified by matching line style to legend.
**1. UMLS (Dotted Line)**
* **Trend:** Starts highest, shows a general downward trend with some fluctuation, and maintains the highest performance until very high noise levels.
* **Approximate Data Points:**
* At x=0.0, y ≈ 0.90
* At x=0.2, y ≈ 0.86
* At x=0.3, y ≈ 0.77 (local dip)
* At x=0.4, y ≈ 0.81
* At x=0.5, y ≈ 0.82
* At x=0.6, y ≈ 0.73
* At x=0.7, y ≈ 0.62
* At x=0.8, y ≈ 0.58
* At x=0.9, y ≈ 0.40
* At x=1.0, y ≈ 0.19
**2. Family (Dash-Dot Line)**
* **Trend:** Starts high, dips, recovers to a peak, then begins a steady decline, crossing below the UMLS line around x=0.65.
* **Approximate Data Points:**
* At x=0.0, y ≈ 0.90
* At x=0.1, y ≈ 0.84
* At x=0.2, y ≈ 0.81
* At x=0.3, y ≈ 0.87 (peak)
* At x=0.4, y ≈ 0.81
* At x=0.5, y ≈ 0.67
* At x=0.6, y ≈ 0.66
* At x=0.7, y ≈ 0.64
* At x=0.8, y ≈ 0.40
* At x=0.9, y ≈ 0.12
* At x=1.0, y ≈ 0.03
**3. Kinships (Solid Line)**
* **Trend:** Starts significantly lower than the other two, shows a slight initial increase to a peak, then declines, with a very sharp drop-off after x=0.7.
* **Approximate Data Points:**
* At x=0.0, y ≈ 0.63
* At x=0.1, y ≈ 0.64
* At x=0.2, y ≈ 0.60
* At x=0.3, y ≈ 0.62
* At x=0.4, y ≈ 0.67 (peak)
* At x=0.5, y ≈ 0.59
* At x=0.6, y ≈ 0.53
* At x=0.7, y ≈ 0.46
* At x=0.8, y ≈ 0.17
* At x=0.9, y ≈ 0.12
* At x=1.0, y ≈ 0.00
### Key Observations
1. **Universal Degradation:** All three datasets show a clear negative correlation between Hits@1 and Mislabeled Edge Probability. Performance decreases as label noise increases.
2. **Performance Hierarchy:** At low noise (x < 0.6), UMLS and Family perform similarly and significantly better than Kinships. UMLS generally maintains the lead.
3. **Differential Robustness:** The datasets exhibit different robustness profiles. UMLS degrades most gradually. Family has a mid-range collapse. Kinships is the least robust, suffering a catastrophic drop in performance between x=0.7 and x=0.8.
4. **Convergence at High Noise:** At extreme noise levels (x > 0.9), the performance of all three models converges toward zero, with Kinships reaching it first.
### Interpretation
This chart likely evaluates the robustness of knowledge graph embedding models or link prediction algorithms on different datasets when subjected to increasing levels of incorrect training data (mislabeled edges).
* **What the data suggests:** The "Kinships" dataset appears to be the most sensitive to label noise, suggesting its underlying structure or the model's reliance on it is more fragile. The "UMLS" dataset (a medical ontology) shows the most graceful degradation, indicating either more redundant information or a model that generalizes better despite noise. The "Family" dataset shows an interesting non-monotonic response, where a small amount of noise (x=0.3) might even slightly improve performance before causing decline.
* **Relationship between elements:** The x-axis represents the independent variable (noise level), and the y-axis represents the dependent variable (model accuracy). The diverging lines highlight how the same noise level impacts different data domains unequally.
* **Notable anomaly:** The peak for "Family" at x=0.3 and for "Kinships" at x=0.4 are anomalies. In a controlled experiment, this could indicate that a very small amount of noise acts as a regularizer, preventing overfitting and slightly improving generalization before the detrimental effects of corruption dominate.
* **Practical implication:** The results argue for the importance of data cleaning and noise-robust training methods, especially for domains like kinship relation modeling which appear highly vulnerable. The choice of evaluation dataset significantly impacts conclusions about a model's robustness.
</details>
Figure 7: Hits@1 on the Kinships, Family, and UMLS datasets as the probability of edge mislabeling $p$ increases.
### 3.6 Choosing the Number of Schematic Variables
In theory, GLIDR parameterized with $N$ schematic variables should be able to learn any rule that can be expressed with $n^{\prime}<N$ variables. To investigate whether this happens in practice, we again trained GLIDR on Kinships, Family, and UMLS. For each dataset, we varied the number of schematic variables from $N=2$ to $N=9$ and recorded the results. Figure 8 plots the Hits@1 on each dataset as the number of variables was changed. We observe that there is a performance benefit to increasing the rule graph size up to a certain point, after which the performance plateaus. This can be explained by the existence rules of a certain length which are sufficient to predict the relationships in a dataset. As the rule graph grows past that size, the system continues to learn the optimal rules as smaller and smaller subsets of the larger schematic rule. This is a very good property, as it implies that a user can set the rule graph as large as their computer and patience allows without fear of hurting model performance.
<details>
<summary>figs/rule_graph_nodes_figure_large.png Details</summary>
### Visual Description
## Line Graph: Performance vs. Rule Graph Complexity
### Overview
The image is a line graph comparing the performance of three different datasets or models (UMLS, Family, Kinships) as a function of increasing rule graph complexity. The performance metric is "Hits@1," and the complexity is measured by the "Number of Rule Graph Nodes."
### Components/Axes
* **X-Axis:** Labeled "Number of Rule Graph Nodes." It has discrete integer markers from 2 to 9.
* **Y-Axis:** Labeled "Hits@1." It is a continuous scale from 0.0 to 1.0, with major gridlines at intervals of 0.2.
* **Legend:** Located in the bottom-right corner of the plot area. It defines three line styles:
* `......` (dotted line): **UMLS**
* `-.-.` (dash-dot line): **Family**
* `______` (solid line): **Kinships**
* **Grid:** A light gray, dashed grid is present for both major x and y ticks.
### Detailed Analysis
**Trend Verification & Data Points (Approximate):**
1. **UMLS (Dotted Line):**
* **Trend:** Starts very low, exhibits a steep, near-linear increase from 2 to 3 nodes, then continues to rise more gradually to a peak at 4 nodes. After the peak, it shows a very slight, gradual decline and then a plateau.
* **Approximate Values:**
* Node 2: ~0.36
* Node 3: ~0.82
* Node 4: ~0.89 (Peak)
* Node 5: ~0.88
* Node 6: ~0.84
* Node 7: ~0.86
* Node 8: ~0.87
* Node 9: ~0.88
2. **Family (Dash-Dot Line):**
* **Trend:** Starts at a moderate level, increases steadily to a peak at 4 nodes, then experiences a slight dip at 6 nodes before recovering and stabilizing at a high level.
* **Approximate Values:**
* Node 2: ~0.65
* Node 3: ~0.85
* Node 4: ~0.91 (Peak)
* Node 5: ~0.88
* Node 6: ~0.85
* Node 7: ~0.88
* Node 8: ~0.90
* Node 9: ~0.90
3. **Kinships (Solid Line):**
* **Trend:** Starts at the lowest point among the three. Shows a steady, moderate increase from 2 to 4 nodes, then plateaus with minor fluctuations, remaining consistently below the other two series.
* **Approximate Values:**
* Node 2: ~0.47
* Node 3: ~0.62
* Node 4: ~0.66
* Node 5: ~0.63
* Node 6: ~0.65
* Node 7: ~0.64
* Node 8: ~0.62
* Node 9: ~0.63
### Key Observations
1. **Performance Hierarchy:** The "Family" dataset consistently achieves the highest Hits@1 scores across all node counts, followed closely by "UMLS" after 3 nodes. "Kinships" performs significantly worse than the other two.
2. **Diminishing Returns:** All three series show a clear pattern of diminishing returns. The most significant performance gains occur when increasing the number of nodes from 2 to 4. After 4 nodes, performance gains are minimal or non-existent, with lines plateauing or showing slight fluctuations.
3. **Convergence:** The performance of "UMLS" and "Family" converges after 3 nodes, with their lines running nearly parallel and within ~0.05 Hits@1 of each other from node 4 onward.
4. **Peak Performance:** Both "UMLS" and "Family" appear to reach their peak performance at 4 rule graph nodes. "Kinships" peaks at 4 nodes as well but at a much lower absolute value.
### Interpretation
This graph demonstrates the relationship between the structural complexity of a rule-based system (represented by graph node count) and its predictive accuracy (Hits@1) on three distinct knowledge domains or tasks.
* **Core Insight:** Increasing rule graph complexity is highly beneficial up to a point (around 4 nodes in this experiment), after which the accuracy benefits plateau. This suggests an optimal complexity threshold exists; adding more nodes beyond this yields little to no improvement and may increase computational cost without benefit.
* **Domain Difficulty:** The stark performance gap between "Kinships" and the other two datasets indicates that the kinship relation prediction task is fundamentally more challenging for the model or rule system being tested. The relationships may be more complex, noisier, or less explicitly captured by the rule graph structure compared to the domains covered by "UMLS" (likely medical terminology) and "Family."
* **Model Behavior:** The similar trajectories of "UMLS" and "Family" suggest the model handles these domains with comparable efficiency once a minimal complexity threshold (3-4 nodes) is met. The initial steep rise for UMLS implies it benefits most dramatically from the introduction of basic relational rules.
</details>
Figure 8: Hits@1 on the Kinships, Family, and UMLS datasets as the number of nodes in the schematic rule, $N$ , grows.
### 3.7 End-to-End Co-Training with Deep Learning Models
To demonstrate the feasibility of using GLIDR in a larger deep learning system, we co-train GLIDR with an image encoder to classify MNIST lecun2010mnist digits. We choose to use MNIST as a test-case to simplify the analysis of predicates learned during the co-training process. In this experiment, images are divided into a 7x7 grid of 4x4 pixel image patches. Each image patch is independently vectorized and mapped into a latent representation using a four layer MLP. We model each image as a 49 node multi-graph, where each node corresponds to a patch in the original image. We choose a number of binary and unary predicates to generate for inclusion in this background graph. Each binary relationship and unary property is generated using the embedded representations of the image patches. To create unary facts, a linear projection and sigmoid activation function are applied to each image patch embedding. To create relational facts, each image patch embedding is projected into query and key embeddings and these are combined with an attention mechanism vaswani2017attention . Rather than using a softargmax in the attention mechanism, we use a sigmoid function to produce a soft adjacency matrix for each predicate type. We manually zero the diagonals of these matrices and clip any values below 0.5 to zero. Clipping small activations to zero promotes sparsity in the adjacency matrices, and we find that this is a key modification required to achieve convergence during training. With a trainable mapping from images to graph adjacency arrays and node property arrays, we can model the digit classification problem as a graph classification problem with GLIDR. We initialize GLIDR with 10 body rules, one for each digit type. We take the scores produced by each body rule and apply a softargmax, so that the ”most satisfied” rule is the classification decision made by the ensemble. We then train the GLIDR model as usual, taking batches of images, mapping them into graphs, and then passing those graphs into GLIDR.
We observe that the high learning rates favored by GLIDR are unsuited for training the image encoder. To address this, we use two AdamW optimizers with different hyperparameters. Gradients are backpropagated end-to-end through the system, and a high learning rate AdamW is used to update GLIDR’s parameters while a low learning rate AdamW is used to update the parameters of the image encoder. With this setup, we observe rapid convergence of the combined models. With an $N=4$ GLIDR backbone, 8 binary predicates, 8 unary predicates, and a 4-layer MLP, we achieve an F1 Score of 0.79 on the MNIST test set. We find that the performance of the system improves as the number of available predicates increases, with 32 binary predicates and 32 unary predicates achieving an F1 score of 0.88.
Notably, no information about the spatial layout of the image patches is retained in this system, and we expect some inherent limitation on the performance of this system due to the constrained nature of viewing images as a bag of patches. Despite this, we observe that many of the learned predicates attempt to recover elements of the original image structure. For example, one learned predicate (heavily featured in the rule for 1) consistently maps left edges of vertical lines to similar looking right edges of vertical lines. In doing so, this predicate measures the prevalence of vertical edges in the image. Indeed, we observe that the learned definition of ”1” makes exclusive use of predicate 6 for its binary relationships. Similarly, we observe that another predicate maps tops and bottoms of horizontal edges together to recover information about the existence of horizontal lines.
For the smaller experiment with 8 predicates, we observe a high degree of predicate re-use between the rules for different digits. As the domain grew to 32 predicates, few were re-used across rules. This indicates that successful discovery of general purpose predicates might require a learning schedule or another mechanism to promote predicate reuse.
The rules learned by this system are not directly interpretable due to their use of learned neural predicates, however they do offer a straightforward mechanism for understanding the behavior and role of learned predicates. The ability to co-train GLIDR with other deep learning models also opens up a large design space in problems characterized by a mixture of symbolic and numerical data. Learned predicates could be combined with known ground truth predicates and learned rules can be combined with hard-coded known rules. In this way GLIDR and other differentiable rule learning systems can serve as a bridge between symbolic and numerical modalities.
## 4 Strengths and Limitations
GLIDR learns expressive, graph-like rules that can’t be represented by previous chain-like differentiable ILP techniques. This expressivity allows it to outperform other methods on knowledge graph completion tasks. The message passing inference algorithm required to support these expressive rules imposes the limitation that GLIDR does not efficiently support open queries. This is in contrast with many embedding methods and chain-like rule methods such as Neural-LP yang2017differentiable which can generate 1:N scores, emitting a confidence score for every tail entity given a head entity for the rule. While GLIDR is still fast to train, the 1:1 limitation means that generating scores for knowledge graph completion requires $\mathcal{O}(|\mathcal{E}_{bg}|^{2})$ inferences. Generating rankings for FB15k-237 took approximately 40 hours on 4 NVIDIA A100 80GB GPUs using the settings described.
## 5 Conclusion
In this paper we introduce GLIDR and show that its construction allows it to learn logical rules that cannot be represented by previous chain-like differentiable ILP methods. We evaluate the algorithm on several knowledge graph completion benchmarks and show that it achieves state of the art performance compared to other rule-based methods. We also perform experiments demonstrating that GLIDR retains the characteristic noise robustness that differentiable ILP methods are known for and that hard rules extracted from GLIDR perform well. We also demonstrate the GLIDR can be co-trained with other deep learning models to incorporate rule-based learning in domains that are not inherently symbolic.
## References
- [1] Joao H Bettencourt-Silva, Natasha Mulligan, Charles Jochim, Nagesh Yadav, Walter Sedlazek, Vanessa Lopez, and Martin Gleize. Exploring the social drivers of health during a pandemic: Leveraging knowledge graphs and population trends in covid-19. In Integrated Citizen Centered Digital Health and Social Care, pages 6–11. IOS Press, 2020.
- [2] O. Bodenreider. The Unified Medical Language System (UMLS): integrating biomedical terminology. Nucleic Acids Research, 32(90001):267D–270, January 2004.
- [3] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pages 2787–2795, 2013.
- [4] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018.
- [5] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd International Conference on Machine Learning, ICML ’05, page 89–96, New York, NY, USA, 2005. Association for Computing Machinery.
- [6] Kewei Cheng, Nesreen Ahmed, and Yizhou Sun. Neural compositional rule learning for knowledge graph reasoning. In The Eleventh International Conference on Learning Representations, 2023.
- [7] William W. Cohen, Fan Yang, and Kathryn Rivard Mazaitis. Tensorlog: A probabilistic database implemented using deep-learning infrastructure. Journal of Artificial Intelligence Research, 67, 2020.
- [8] Andrew Cropper and Sebastijan Dumančić. Inductive logic programming at 30: a new introduction. Journal of Artificial Intelligence Research, 74:765–850, 2022.
- [9] Andrew Cropper and Rolf Morel. Learning programs by learning from failures. Machine Learning, 110:801–856, April 2021.
- [10] DeepMind, Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedieu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Laurent Sartran, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Miloš Stanojević, Wojciech Stokowiec, Luyu Wang, Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020.
- [11] Woodrow Denham. The detection of patterns in Alyawarra nonverbal behavior. PhD thesis, Department of Anthropology, University of Washington, Seattle, WA, 1973.
- [12] Woodrow W. Denham. Alyawarra 1971 au01 dataset, 2016.
- [13] Tim Dettmers, Minervini Pasquale, Stenetorp Pontus, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the 32th AAAI Conference on Artificial Intelligence, pages 1811–1818, February 2018.
- [14] Patrick Ernst, Amy Siu, and Gerhard Weikum. KnowLife: a versatile approach for constructing a large knowledge graph for biomedical sciences. BMC Bioinformatics, 16(1):157, December 2015.
- [15] Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1–64, 2018.
- [16] Dieter Fensel, Umutcan Şimşek, Kevin Angele, Elwin Huaman, Elias Kärle, Oleksandra Panasiuk, Ioan Toma, Jürgen Umbrich, and Alexander Wahler. Introduction: What Is a Knowledge Graph?, pages 1–10. Springer International Publishing, Cham, 2020.
- [17] Eugene C. Freuder. A sufficient condition for backtrack-free search. J. ACM, 29(1):24–32, January 1982.
- [18] Genet Asefa Gesese, Russa Biswas, and Harald Sack. A comprehensive survey of knowledge graph embeddings with literals: Techniques and applications. In Mehwish Alam, Davide Buscaldi, Michael Cochez, Francesco Osborne, Diego Reforgiato Recupero, and Harald Sack, editors, Proceedings of the Workshop on Deep Learning for Knowledge Graphs (DL4KG2019) Co-located with the 16th Extended Semantic Web Conference 2019 (ESWC 2019), Portoroz, Slovenia, June 2, 2019, volume 2377 of CEUR Workshop Proceedings, pages 31–40. CEUR-WS.org, 2019.
- [19] William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52–74, 2017.
- [20] FIEKE HILLERSTRÖM and GERTJAN BURGHOUTS. Towards probabilistic inductive logic programming with neurosymbolic inference and relaxation. Theory and Practice of Logic Programming, 24(4):628–643, 2024.
- [21] Geoff Hinton. Kinship. UCI Machine Learning Repository, 1990. DOI: https://doi.org/10.24432/C5WS4D.
- [22] Céline Hocquette, Andreas Niskanen, Matti Järvisalo, and Andrew Cropper. Learning MDL logic programs from noisy data, August 2023. arXiv:2308.09393 [cs].
- [23] Rolf Jagerman, Xuanhui Wang, Honglei Zhuang, Zhen Qin, Michael Bendersky, and Marc Najork. Rax: Composable learning-to-rank using jax. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, page 3051–3060, New York, NY, USA, 2022. Association for Computing Machinery.
- [24] Vipin Kumar. Algorithms for constraint-satisfaction problems: A survey. AI Magazine, 13(1):32, Mar. 1992.
- [25] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, 2, 2010.
- [26] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2017.
- [27] Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118, 1977.
- [28] Alexa T. McCray. An upper‐level ontology for the biomedical domain. Comparative and Functional Genomics, 4(1):80–84, February 2003.
- [29] Stephen Muggleton. Inverse entailment and progol. New Generation Computing, 13, 1995.
- [30] Stephen Muggleton, Wang-Zhou Dai, Claude Sammut, Alireza Tamaddoni-Nezhad, Jing Wen, and Zhi-Hua Zhou. Meta-interpretive learning from noisy images. Machine Learning, 107:1097–1118, 2018.
- [31] Stephen H. Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited. Machine Learning, 100(1):49–73, July 2015.
- [32] David N. Nicholson and Casey S. Greene. Constructing knowledge graphs and their biomedical applications. Computational and Structural Biotechnology Journal, 18:1414–1428, 2020.
- [33] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11–33, 2015.
- [34] Yoonyoung Park, Natasha Mulligan, Martin Gleize, Morten Kristiansen, and Joao H Bettencourt-Silva. Discovering associations between social determinants and health outcomes: merging knowledge graphs from literature and electronic health data. In AMIA Annual Symposium Proceedings, volume 2021, page 940. American Medical Informatics Association, 2021.
- [35] Ali Payani and Faramarz Fekri. Inductive logic programming via differentiable deep neural logic networks. CoRR, abs/1906.03523, 2019.
- [36] Aritran Piplai, Sudip Mittal, Anupam Joshi, Tim Finin, James Holt, and Richard Zak. Creating cybersecurity knowledge graphs from malware after action reports. IEEE Access, 8:211691–211703, 2020.
- [37] Yulu Qi, Zhaoquan Gu, Aiping Li, Xiaojuan Zhang, Muhammad Shafiq, Yangyang Mei, and Kaihan Lin. Cybersecurity knowledge graph enabled attack chain detection for cyber-physical systems. Computers and Electrical Engineering, 108:108660, 2023.
- [38] Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogic: Learning logic rules for reasoning on knowledge graphs. In International Conference on Learning Representations, 2021.
- [39] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall Press, USA, 3rd edition, 2009.
- [40] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. Advances in Neural Information Processing Systems, 32, 2019.
- [41] Ashwin Shrinivasan. The aleph manual. Machine Learning at the Computing Laboratory, 2001. Oxford University.
- [42] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10197, 2019.
- [43] Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 5516–5522, Online, July 2020. Association for Computational Linguistics.
- [44] Toyotaro Suzumura, Yi Zhou, Natahalie Baracaldo, Guangnan Ye, Keith Houck, Ryo Kawahara, Ali Anwar, Lucia Larise Stavarache, Yuji Watanabe, Pablo Loyola, et al. Towards federated graph learning for collaborative financial crimes detection. arXiv preprint arXiv:1909.12946, 2019.
- [45] Komal Teru, Etienne Denis, and William Hamilton. Inductive relation prediction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9448–9457. PMLR, 2020.
- [46] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pages 57–66, 2015.
- [47] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998–6008, 2017.
- [48] John Wahlig. Learning logic programs from noisy failures. Master’s thesis, University of Oxford, 2021.
- [49] Xiaxia Wang, David J. Tena Cucala, Bernardo Cuenca Grau, and Ian Horrocks. Faithful rule extraction for differentiable rule learning models. In The 12th International Conference on Learning Representations, 2024.
- [50] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. Advances in neural information processing systems, 30, 2017.
- [51] Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In International Conference on Learning Representations, 2020.
- [52] Wen Zhang, Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhao, Wei Zhang, Huajun Wen, and Jiajun Chen. Iteratively learning embeddings and rules for knowledge graph reasoning. In The World Wide Web Conference, WWW ’19, pages 2366–2377. Association for Computing Machinery, 2019.
## Appendix A Experimental Details
### A.1 Experiment Hyperparameters
Table 2: Hyperparameter settings used during Family, Kinships, and UMLS benchmarking.
| Hyperparameter | Value |
| --- | --- |
| Training Steps | 2048 |
| Batch Size | 64 |
| Learning Rate | 0.15 |
| Weight Decay | 0.1 |
| Schematic Variables $N$ | 4 |
| Rule Bodies | 8 |
| Message Passing Rounds $R_{\text{max}}$ | 3 |
We use the same hyperparameters across the Kinships, Family, and UMLS datasets, reported in Table 2. The learning rate and weight decay were chosen because we consistently observed these settings to contribute to stable convergence throughout GLIDR’s development. The batch size was chosen because it offered acceptable training times across different GPUs. All sources of randomness including model weights and data-loaders were seeded with a different seeds across each of the 10 runs used to produce the statistics in Table 1. During GLIDR’s development, we validated its performance extensively with the Hinton kinship dataset [21], which has no noise. GLIDR classifies this dataset perfectly.
Table 3: Hyperparameter settings used during FB15k-237 benchmarking.
| Hyperparameter | Value |
| --- | --- |
| Training Steps | 512 |
| Batch Size | 64 |
| Learning Rate | 0.15 |
| Weight Decay | 0.1 |
| Schematic Variables $N$ | 4 |
| Rule Bodies | 8 |
| Training $R_{\text{max}}$ | 3 |
| Testing $R_{\text{max}}$ | 2 |
Table 3 records the hyperparameters used during benchmarking on the FB15k-237 dataset. A smaller number of training steps was chosen to reduce runtime, as was a reduced number of message passing steps at test-time.
### A.2 Hardware
The experimental results reported in Table 1 were generated on a heterogeneous compute cluster, and so several different models of GPU and CPU were used throughout evaluation. Each of the benchmarking jobs had access to 8 CPU cores, 16GB of system memory, and one of the GPUs from the following list: NVIDIA RTX A6000-48GB, NVIDIA Tesla V100-32GB, NVIDIA Tesla V100S-32GB, NVIDIA A100-80GB. Training on YAGO3-10 [13], a dataset significantly larger than any of those studied here, was validated on a NVIDIA RTX 3090-24GB GPU. Although training and evaluation would be impractically slow due to the large number of entities in this dataset (123,182), it demonstrates that memory complexity is not a significant concern for GLIDR given its use of sparse matrix algebra. Each benchmarking run on the Kinships, Family, and UMLS datasets took approximately 2 hours. The FB15k-237 benchmarking run used 4 NVIDIA A100-80GB GPUs, and the full run took approximately 72 hours, with approximately 48 hours of that time devoted to generating rankings.
## Appendix B Examples of Learned Rules
Table 4: A sample of learned rules for each studied dataset. Rules frequently contain terms resulting in non-chain-like branching or cyclic structure. All rules were fit with a maximum of $N=4$ schematic variables.
| UMLS | $\texttt{result\_of}(X,Y):-$ $\texttt{manifestation\_of}(X,Y):-$ | $\texttt{result\_of}(X,Z_{1})\wedge\texttt{co-occurs\_with}(Z_{1},Z_{2})\wedge$ $\texttt{result\_of}(Z_{1},Y)\wedge\texttt{result\_of}(Z_{2},Y).$ $\texttt{exhibits}(Z_{1},X)\wedge\texttt{disrupts}(Z_{2},Z_{1})\wedge\texttt{result\_of}(Z_{1},Y)\wedge$ |
| --- | --- | --- |
| $\texttt{complicates}(Z_{2},Y).$ | | |
| $\texttt{affects}(X,Y):-$ | $\texttt{affects}(X,Z_{1})\wedge\texttt{interacts\_with}(X,Z_{2})\wedge\texttt{affects}(Z_{2},Z_{1})\wedge$ | |
| $\texttt{interacts\_with}(Z_{1},Y)\wedge\texttt{affects}(Z_{2},Y).$ | | |
| FB15k-237 | $\texttt{countries\_within}(X,Y):-$ | $\texttt{contains}(X,Z_{1})\wedge\texttt{countries\_within}(X,Z_{2})\wedge$ |
| $\texttt{adjoins}(Y,Z_{2})\wedge\texttt{countries\_within}(Z_{1},Y).$ | | |
| $\texttt{place\_of\_burial}(X,Y):-$ | $\texttt{place\_of\_burial}(X,Z_{1})\wedge\texttt{celebrity\_friendship}(X,Z_{2})\wedge$ | |
| $\texttt{place\_of\_burial}(Z_{2},Z_{1})\wedge$ | | |
| $\texttt{distributed\_films\_in\_region}(Z_{2},Y).$ | | |
| $\texttt{art\_direction\_by}(X,Y):-$ | $\texttt{set\_design\_for}(Z_{1},X)\wedge\texttt{art\_direction\_by}(X,Z_{2})\wedge$ | |
| $\texttt{award\_nomination\_for}(Y,Z_{1})\wedge\texttt{award\_received\_for}(Y,Z_{2}).$ | | |
| Kinships | $\texttt{adardiya}(X,Y):-$ | $\texttt{anguriya}(Z_{1},X)\wedge\texttt{adardiya}(X,Z_{2})\wedge\texttt{adardiya}(Z_{1},Y)\wedge$ |
| $\texttt{anyainya}(Y,Z_{2}).$ | | |
| $\texttt{agngiya}(X,Y):-$ | $\texttt{agngiya}(X,Z_{1})\wedge\texttt{anguriya}(X,Z_{2})\wedge\texttt{andungiya}(Z_{2},Z_{1})\wedge$ | |
| $\texttt{awaadya}(Z_{1},Y)\wedge\texttt{agngiya}(Z_{2},Y).$ | | |
| $\texttt{aleriya}(X,Y):-$ | $\texttt{adniadya}(Z_{1},X)\wedge\texttt{aweniya}(Y,X)\wedge\texttt{umbaidya}(Y,Z_{1}).$ | |
| Family | $\texttt{nephew}(X,Y):-$ | $\texttt{son}(X,Z_{1})\wedge\texttt{daughter}(Z_{2},Z_{1})\wedge\texttt{uncle}(Y,Z_{2}).$ |
| $\texttt{aunt}(X,Y):-$ | $\texttt{sister}(X,Z_{1})\wedge\texttt{sister}(X,Z_{2})\wedge\texttt{brother}(Z_{2},Z_{1})\wedge$ | |
| $\texttt{nephew}(Y,Z_{1}).$ | | |
| $\texttt{father}(X,Y):-$ | $\texttt{husband}(X,Z_{2})\wedge\texttt{mother}(Z_{2},Y).$ | |
Table 4 reports three example rules learned for each dataset during benchmarking. Each reported rule performed well on the validation set compared to the other 7 competing rule definitions. Each of these rules was chosen because it illustrates interesting structure or describes a predicate for which the model performed particularly well. The predicates in the Kinships dataset are encoded as $\texttt{term1},\texttt{term2},$ etc., and have been translated to their corresponding Alyawarra kinship terms using the key provided by [12].