Probabilistic Circuits for Knowledge Graph Completion with Reduced Rule Sets

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!