Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets

arXiv:2508.06706 · cs.AI, cs.LO · Submitted 2026-08-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets".

Jane: The paper was written by Jaikrishna Manojkumar Patil, Nathaniel Lee, Al Mehdi Saadat Chowdhury, YooJung Choi and Paulo Shakarian from Syracuse University and Arizona State University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title and Authors: Tom: Welcome back to the show, everyone! Today we're diving into a paper that's got me genuinely fired up: "Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets." Jane, you've been looking at this one too—what's the big deal?

Jane: Oh, Tom, this is one of those papers where the title sounds dense but the idea is actually super intuitive. The team—Jaikrishna Patil, Nathaniel Lee, Al Mehdi Saadat Chowdhury, YooJung Choi, and Paulo Shakarian from Syracuse and ASU—they're tackling a problem that's been bugging the explainable AI community for years.

Tom: And what problem is that, exactly?

Jane: So, knowledge graphs are these giant webs of facts, like "Einstein was born in Germany" or "penicillin treats infections." The task is to fill in missing links. There are two main ways to do it: black-box neural networks that are accurate but you can't see why they make a prediction, and rule-based systems that give you logical chains like "if X is a parent of Y, and Y is a parent of Z, then X is a grandparent of Z."

Tom: And the rule-based ones are explainable, right? That's the whole selling point.

Jane: In theory, yes. But here's the catch—to get competitive performance, these systems like AnyBURL need tens of thousands of rules. On the UMLS dataset, they use twenty thousand rules just to get decent accuracy, and almost seven thousand of those rules never even fire during inference. They're just sitting there, taking up space.

Tom: So you've got a system that's supposed to be transparent, but it's drowning in rules nobody uses.

Jane: Exactly. And that's what this paper fixes. They use something called probabilistic circuits—which is basically a fancy way of learning a probability distribution over which rules actually work together—to cut that rule count by seventy to ninety-six percent.

Tom: That's a massive reduction. And they still keep most of the performance?

Jane: They preserve about ninety-one percent of the baseline's peak performance, and with the same number of rules as the baseline, they outperform it by up to thirty-one times. That's not a small improvement, Tom.

Tom: Okay, I need to understand the probabilistic circuit part a bit better. What makes it better than just picking the rules with the highest confidence scores?

Jane: Think of it like this. The old way treats each rule as if it works independently. But rules don't work in isolation—they fire together, they depend on each other. A probabilistic circuit learns those dependencies. It's like knowing that in a recipe, the baking powder and the flour work together, but the baking powder and the salt might not. The circuit figures out which combinations actually produce results.

Tom: So it's not just about which rules are good—it's about which rules are good together.

Jane: You got it. And that's why they can get away with so few rules. They're not picking the top thousand individually good rules; they're picking the rules that form a coherent, working set.

Tom: Alright, I'm hooked. But I want to know more about how they actually build this circuit and what the formal math looks like. That's coming up next.

Jane: And trust me, the formal results are worth hearing about. They prove their approach is grounded in real probabilistic logic, not just heuristic guesswork.

Paper Summary: Tom: So we're back with "Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets." Jane, you mentioned the formal side of things—let's dig into what they actually did.

Jane: Right. So the core idea is they take each training triple—that's a fact from the knowledge graph—and they figure out which rules could have predicted it. They build what's called an association matrix. Each row is a rule, each column is a training sample, and the entry is marked if that rule could have produced that sample.

Tom: And then they feed that matrix into the probabilistic circuit?

Jane: Exactly. But here's the clever part—the matrix has missing entries. If a rule doesn't apply to a particular sample, they don't just mark it as false. They leave it unknown. And the circuit learning algorithm, which uses expectation maximization, treats those unknowns as latent variables.

Tom: So it's not assuming a rule is inactive just because it didn't fire for one sample. It's learning the pattern of when rules actually do fire.

Jane: Precisely. And this matters because rules are correlated. If one rule fires, another might be more likely to fire. The circuit captures those correlations without assuming independence.

Tom: Now, I read that they have these formal propositions. Can you walk me through what those mean in plain language?

Jane: Sure. The first one is a lower bound—they show that the probability of a set of rules is at least the sum of the probabilities of the samples that contain all those rules. That gives them a way to compute a conservative estimate.

Tom: And the second one?

Jane: That one's about computing the exact probability of a query. They show that the probability of a query being true is one minus the probability that none of the samples that entail the query are active. It's a neat trick because it lets them compute exact probabilities without enumerating all possible worlds.

Tom: And then they have those upper and lower bound propositions for when you don't want to compute everything exactly.

Jane: Right. Those are useful when you have a huge number of samples—like one hundred thousand training triples—and you don't want to check every single one. You can pick a few rule sets and bound the answer.

Tom: And the big theorem—they prove their framework is equivalent to Nilsson's probabilistic logic. What does that mean for people who care about formal semantics?

Jane: It means their approach isn't just a heuristic that happens to work. It's grounded in a well-established logical framework. They construct a logic program where each rule gets probability one, each sample gets its learned probability, and then they show that any interpretation satisfying that structure gives you exactly the probabilities you'd expect.

Tom: So it's not just engineering—it's principled.

Jane: Exactly. And that's important because it means the approach can be extended and trusted. It's not a black box that happens to work on these eight datasets.

Tom: Speaking of datasets—they tested on eight benchmarks. What did they find?

Jane: The results are striking. On UMLS, the baseline needs twenty-five thousand rules to hit its peak Hits@ten of zero point nine six four four. The PC approach gets there with just one thousand rules. That's a twenty-five-fold reduction. On CODEX-S, they use one thousand rules to achieve ninety-nine point nine five percent of the baseline's best performance, which needed twenty thousand rules.

Tom: So the pattern holds across different domains—biomedical, general knowledge, family relations.

Jane: It does. And the improvement isn't just about rule count. It's about utilization. The baseline has tons of inactive rules—rules that never fire. The PC approach has far fewer wasted rules, which means the system is actually understandable.

Tom: Okay, so we've got the theory and the results. But I want to know how they actually implement this. What's the inference procedure look like? That's next.

Improvements and Inference: Tom: We're back with "Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets." Jane, we've covered the theory and the results. Now I want to get into the practical side—how do they actually run inference with these reduced rule sets?

Jane: Great question. They introduce three inference variants. The first is called SingletonLB. Here, they sort all the rules by their marginal probability under the learned circuit, then take the top rules one at a time. Each rule forms its own singleton set, and they use the lower bound from Proposition three to estimate the query probability.

Tom: So it's basically "pick the best single rule and see what it predicts"?

Jane: Sort of, but the key is that the marginal probability isn't just the rule's confidence score. It's the probability that the rule is active given all the correlations the circuit learned. So a rule that looks good in isolation but conflicts with other rules might get a lower marginal.

Tom: And the second variant?

Jane: SingletonExact. Same idea—singleton rule sets—but instead of the lower bound, they compute the exact probability using Proposition two. That's the one where they compute one minus the probability that no supporting sample is active.

Tom: And that gives them better accuracy?

Jane: It does. On most datasets, SingletonExact outperforms SingletonLB. For example, on UMLS, SingletonExact hits zero point nine six four four Hits@ten with one thousand rules, while SingletonLB gets there a bit later. But both are dramatically better than the baseline at the same rule count.

Tom: And the third variant?

Jane: That's GreedyLB. Instead of singleton rules, they do a greedy walk. They start with the highest-marginal rule, then keep adding the rule that most increases the joint probability of the set, until the probability drops below a threshold. Then they start a new walk with the remaining rules.

Tom: So it's building sets of rules that work together.

Jane: Right. And it does beat the baseline—on Nations, GreedyLB gets twice the Hits@ten and MRR of the baseline with five hundred rules. But here's the interesting part: it doesn't beat the singleton approaches. SingletonLB gets thirteen percent higher Hits@ten and eleven percent higher MRR on the same dataset.

Tom: So the extra computational complexity of greedy walks didn't pay off?

Jane: Exactly. The paper is honest about that. The greedy walks add complexity without improving results. The singletons are simpler and better. That's a useful finding for anyone building on this work.

Tom: And what about runtime? Does the circuit learning slow things down?

Jane: They show that everything scales linearly with the number of rules. Generating rule samples has an R-squared of zero point nine zero, learning the circuit has zero point nine nine, and both inference variants have above zero point nine five. So the approach is practical, even for larger datasets.

Tom: But the circuit learning itself takes a while, right?

Jane: It does. On the Family dataset, learning the circuit took between one thousand and nine thousand five hundred seconds depending on the rule count. That's the most expensive step. But it's a one-time training cost, and once you have the circuit, inference is fast.

Tom: So the trade-off is training time for explainability and efficiency at inference time.

Jane: That's the deal. And given that the baseline needs tens of thousands of rules, the training cost is worth it.

Tom: Alright, so we've got the methods and the results. But what does this mean for the broader world? Who should care about this? That's our final segment.

Conclusion: Tom: We're wrapping up our discussion of "Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets." Jane, let's pull it all together. Who should actually care about this work?

Jane: Honestly, anyone building explainable AI systems. The problem this paper solves isn't specific to knowledge graphs—it's the problem of rule explosion in symbolic reasoning. Any system that learns logical rules, whether for medical diagnosis, legal reasoning, or question answering, faces the same issue: too many rules, most of them useless.

Tom: And this paper shows a principled way to cut through that noise.

Jane: Exactly. By learning a joint distribution over rule activations, they can identify the small set of rules that actually work together. That's a huge win for transparency. If you're a doctor using an AI system to recommend treatments, you want to see three rules that explain a decision, not three thousand.

Tom: And there's the memory angle too. Storing tens of thousands of rules is expensive. The paper mentions this is especially acute when you want to feed rules into a large language model with limited context.

Jane: Right. If you're using an LLM to reason over rules, you can't fit twenty thousand rules in the context window. But one thousand rules? That's doable. So this framework could enable new kinds of neuro-symbolic systems where the LLM reasons over a compact, high-quality rule set.

Tom: And the authors mention future work—applying this to other symbolic AI domains like theorem proving.

Jane: Yes. The framework is agnostic to the rule source. It works with AnyBURL, but it could work with any rule learner. That's a big deal because it means the approach is general.

Tom: Let me bring in Lu, our senior researcher, to get a bigger picture take.

Lu: Thanks, Tom. I think the most exciting implication is that this could change how we think about rule-based systems entirely. For years, the community assumed you needed massive rule sets to compete with embeddings. This paper shows that's not true—you just need the right rules. That reframes the research question from "how do we learn more rules" to "how do we learn better rules."

Tom: And Meng, from the engineering side, what do you think?

Meng: I'm impressed by the linear scalability. That means I can actually deploy this without worrying about exponential blow-up. The training time is a cost, but it's a one-time cost. And the fact that SingletonExact is both simpler and better than GreedyLB means I don't need complex machinery to get the benefit.

Tom: And Lalam, what's the cultural or societal angle here?

Lalam: I think the biggest impact is on trust. When AI systems can explain their reasoning with a handful of rules, people can actually audit them. That's essential for domains like healthcare and finance where decisions have real consequences. This paper is a step toward AI that doesn't just perform well but can justify itself.

Jane: That's a beautiful way to put it. So, to summarize: "Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets" gives us a principled, practical way to shrink rule sets by up to ninety-six percent while keeping ninety-one percent of the performance. It's grounded in formal logic, it scales linearly, and it opens the door to more transparent AI systems.

Tom: And with that, we're saying goodbye to this paper. Thanks for joining us, everyone. Next up, we've got a paper on neuro-symbolic reasoning that I think you're all going to love.

Jane: See you then!

Jaikrishna Manojkumar Patil, Nathaniel Lee, Al Mehdi Saadat Chowdhury, YooJung Choi, Paulo Shakarian

Syracuse University · Arizona State University

cs.AI, cs.LO

Submitted: 2026-08-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 69/100

Key concepts

Knowledge Graph Completion
This is a task involving filling in missing links within a massive web of facts. The goal is to predict the relationship between entities, such as determining if a specific person was born in a certain country, based on existing data points.
Probabilistic Circuits
These are designed to capture how logical rules interact. Instead of treating each rule in isolation, the circuit learns which combinations or sets of rules fire together, allowing for a massive reduction in the total number of necessary rules.
Rule Explosion
This refers to the massive number of logical rules required for complex reasoning systems. The paper addresses this by identifying and eliminating the unused majority of these rules, achieving a reduction of up to 96% while maintaining high accuracy.

Terminology

Summary

Summary

This paper addresses the challenge of rule explosion in rule-based knowledge graph (KG) completion methods. While rule-based approaches like AnyBURL provide explainable predictions, they require tens of thousands of rules to achieve competitive performance, which undermines their core advantage of explainability. The paper states: To reach peak performance on standard benchmarks, AnyBURL requires tens of thousands of rules. This creates three interconnected problems: (1) a substantial fraction of learned rules are never active during inference (e.g., on UMLS, AnyBURL requires 20,000 rules to achieve Hits@10 = 0.9644, but only 12,938 rules (64.69%) are actually used, leaving 7,062 wasted rules); (2) storing and managing tens of thousands of rules creates significant memory overhead; (3) reasoning tasks beyond simple prediction—such as consistency checking and abduction—become computationally intractable as the search space grows.

The proposed framework uses probabilistic circuits (PCs) to learn a distribution over sets of rules that work together from training data, without independence assumptions between rules. The paper notes: "By learning this distribution without independence assumptions between rules, we can identify smaller, high-utilization rule sets that achieve competitive performance while dramatically improving system-level explainability." The framework is agnostic to the underlying rule sources and is not limited to AnyBURL.

Methodology: For each rule r in a program Π, the authors introduce a zero-arity indicator atom µr representing whether r is active, rewriting each rule as hr(X,Y) ← br(X,Y) ∧ µr. For each training sample s (a ground atom p(c1,c2)), they introduce a zero-arity helper atom νs. The rule-sample associations are stored in a matrix M where Mr,s = 1 if µr ← νs is included and is missing otherwise. The associations are computed via PyClause. Given the association matrix, the authors treat each sample as one observation of an underlying joint distribution over rule indicators and use maximum-likelihood learning to fit the PC Pθ over these indicators, using Hidden Chow-Liu Tree for structure learning and expectation maximization (EM) for parameter learning via the Juice library. The paper emphasizes: "To see why a general joint distribution matters, consider a fully factorized distribution over rule indicators... Here, each rule indicator is treated as independent of every other. This is the implicit model behind traditional confidence-based rule scoring... However, rule indicators are typically not independent and usually show correlations in their activations. The PC instead learns a general (non-factorized) joint distribution over rule indicators."

Formal Results: The paper provides a suite of formal results. Proposition 1 shows a lower bound on the marginal: Pθ(R) ≥ Σ s s.t. R⊆Πs Pθ(s). Proposition 2 shows that when q is intensional, Pθ(q) = 1 − Pθ(∧ s s.t. Πs=q ¬νs). Proposition 3 shows Pθ(q) ≥ sup Pθ(Rj)Rj = q, and Proposition 4 shows Pθ(q) ≤ sup 1 − Pθ(Rj)Rj ̸= q. The paper also proves Theorem 1, showing the framework is equivalent to Nilsson's probabilistic logic, grounding it in classical logic programming semantics. The proof of Lemma 1 establishes that any satisfying interpretation assigning a world w a non-zero probability must satisfy exactly one νs atom, and that w = q if and only if for some s where Πs = q, w = νs.

Inference Procedures: The paper introduces three PC-guided inference methods: SingletonLB (approximates query probability with the lower bound of Proposition 3 using singleton rule sets), SingletonExact (exactly computes query probability using Proposition 2), and GreedyLB (approximates query probability with the lower bound of Proposition 3 using rule sets created from a greedy walk). Algorithm 2 describes the complete inference procedure: rules are sorted by marginal probability, candidate rule sets are constructed, AnyBURL inference is run restricted to each selected rule set, and each predicted triple is assigned a probability based on the rules active for it.

Experiments: The framework was evaluated on 8 standard benchmark datasets: FB15K-237, WN18RR, WN18, Family, Nations, UMLS, CODEX-S, and Kinship. AnyBURL rule learner was used with 10 seconds learning time and minimum support threshold ≥ 10. Confidence thresholds for input non-ground rules varied by dataset (50% for CODEX-S/Kinship/UMLS, 60% for FB15K-237, 70% for Nations, 0% for WN18, WN18RR, Family). The number of EM iterations were 100 (Family/WN18/WN18RR), 50 (Kinship), 10 (Others). Standard metrics Hits@1, Hits@3, Hits@10, and MRR were used, all filtered.

Results: The framework reduced the required size of rule sets between 70-96% (average 12-fold reduction in rules) across the 8 datasets. With this reduced rule count, the framework outperformed the baseline by approximately 31×. The approach preserved an average of around 91% of the highest baseline performance. For Hits@10, SingletonExact inference showed substantial improvements over the baseline with minimal equivalent number of rules: 214-fold (UMLS), 17-fold (Kinship), 6.4-fold (FB15K-237), 6.2-fold (CODEX-S), 4-fold (Family), 2.8-fold (Nations), 1.4-fold (WN18RR), and significant improvement in WN18 where baseline achieved zero performance for 500 rules. In CODEX-S, SingletonExact achieved Hits@10 of 0.4259 using only 1000 rules, achieving 99.95% of the baseline's highest Hits@10 (0.4261) that required 20000 rules. In UMLS, SingletonExact achieved baseline's peak Hits@10 of 0.9644 using only 1000 rules compared to baseline requiring 25000 rules—a 25-fold reduction. For MRR, consistent superior performance was observed: 151-fold (UMLS), 11-fold (Kinship), 4.5-fold (FB15K-237), 5-fold (CODEX-S), 4-fold (Family), 2.4-fold (Nations), 1.2-fold (WN18RR). In UMLS and Nations, SingletonExact outperformed the highest baseline by 1.78% and 4.7% respectively while using 96% and 70% fewer rules. GreedyLB also outperformed the baseline with at least 2× better Hits@10 and MRR using 500 rules on Nations, but SingletonLB and SingletonExact were superior to GreedyLB. Runtime analysis showed the framework scales linearly with the number of input rules (R2 ≥ 0.90 for all components).

The paper concludes: "Our framework reduced the rule requirement by 70-96%, and with these smaller rule sets, we got 31-fold performance (Hits@10, MRR) improvement over baseline with same number of baseline rules. We also preserve an average of 91% performance with a reduced rule set compared to the full rule set of the baseline." Future work includes applying the framework to other symbolic AI domains struggling with rule explosion, integrating with other rule learning systems, and improving neuro-symbolic systems.

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to AI systems and what the improved systems can do:

What I improve: I add a probabilistic circuit (PC) layer that learns a joint distribution over rule activations from training data, replacing the confidence-based rule selection used by systems like AnyBURL.

What the improved system can do:

  • Reduce the number of rules needed to reach peak performance by 70–96% (average 12-fold reduction) across 8 benchmark knowledge graphs (FB15K-237, WN18RR, CODEX-S, UMLS, Kinship, Nations, Family, WN18).

  • With an equivalent minimal number of rules, outperform the confidence-based baseline by up to 31× on Hits@10 and MRR.

  • Preserve an average of 91% of the baseline’s peak performance while using dramatically fewer rules.

  • Eliminate inactive rules: e.g., on UMLS, the baseline requires 20,000 rules with 7,062 inactive; my system achieves the same Hits@10 (0.9644) with only 1,000 rules and 868 active.

The improved AI system:

  • Compresses rule sets by 70–96% while maintaining 91% of peak baseline performance.

  • Outperforms baseline by up to 31× with equivalent minimal rules.

  • Provides exact and bounded probabilistic inference grounded in formal logic semantics.

  • Scales linearly with rule count, enabling deployment on large KGs and resource-limited hardware.

  • Integrates with any rule learner and any symbolic reasoning domain, not just KG completion.

This makes the system ideal for explainable AI applications where transparency, tractability, and performance are critical—such as healthcare reasoning, legal compliance checking, and LLM-guided decision support.

Abstract

Rule-based methods for knowledge graph completion provide explainable results, but often require tens of thousands of rules to achieve competitive performance. Although individual predictions may use only a few rules, reasoning over an entire dataset requires these massive rule sets, hampering system-level understanding. We address this by learning a probability distribution over sets of rules that work together using probabilistic circuits. Our approach achieves a 70-96% reduction in the number of rules needed to reach peak baseline performance. Using an equivalent minimal number of rules, we outperform the baseline by up to 31 times. When comparing our minimal rule sets against baseline's full rule sets, we preserve 91% of peak baseline performance. Empirical validation on 8 benchmark datasets shows that our reduced rule sets exhibit higher utilization---fewer rules are wasted, and each prediction requires fewer rules. We show that our framework is grounded in well-known semantics of Nilsson's probabilistic logic and does not require independence assumptions. We provide exact probabilistic inference as well as an efficient lower bound and evaluate both.

Sources

Related papers