From probability to causality in probabilistic logic programming

arXiv:2608.07230 · cs.AI · Submitted 2026-08-07 · Read on arXiv

Listen

Transcript

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

Tom: Next we'll be talking about the paper "From probability to causality in probabilistic logic programming".

Jane: The paper was written by Zora Wurm, Kilian Rückschloß and Felix Weitkämper from Ludwig-Maximilians-Universität München and Eberhard-Karls-Universität Tübingen and German University of Digital Science.

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

Paper summary: Tom: This week we're looking at a paper that asks a deceptively simple question: when you learn a probabilistic logic program from data, can you trust it to answer causal questions? Not just probabilistic ones, but questions about what happens when you intervene in the system.

Jane: And the short answer is only sometimes, and the paper tells you exactly when. It's written by Zora Wurm, Kilian Rückschloß, and Felix Weitkämper, from Munich, Tübingen, and Potsdam.

Lu: For anyone who hasn't met one, a probabilistic logic program is a logic program where each rule carries a probability. So a rule might say that with probability pi, burning things produce smoke. The program as a whole induces a probability distribution over what's true.

Tom: Right, and the paper starts from the observation that learning such a program from data gives you only the probabilistic information. It doesn't tell you the direction of causation.

Jane: And that matters because the same distribution can be explained by fire causing smoke, smoke causing fire, or a hidden third cause behind both. The moment you want to intervene — force a variable, prescribe a treatment — the direction of those arrows is everything.

Meng: So they borrow a well-established idea from causal Bayesian networks, Markov equivalence and orientability, and bring it into logic programming.

Tom: Exactly. Orientability asks whether an edge direction is forced by every network encoding the same distribution. The paper transfers that question to logic programs, and then adds something the graph literature doesn't have — relational structure.

Lalam: And that's the part

Page 1 of the paper: Tom: So here's where the paper starts setting up the problem: once you learn a probabilistic logic program from data, you only get probabilities, and the causal direction might still be ambiguous.

Jane: Right, and on the very first page they make the connection to a classic idea — that a single probability distribution can be explained by multiple causal orders, like smoke coming from fire, fire from smoke, or a hidden cause behind both.

Tom: But what I found interesting on this page is how they frame the goal. They're not trying to learn causality from scratch. They're asking whether a program that's already been learned can support interventional reasoning at all.

Jane: And their bridge is the Bayesian network. They point out that any acyclic probabilistic logic program induces a distribution that can be represented as a Bayesian network, and prior work already showed that intervening on the program matches intervening on that network.

Tom: So the whole idea is to take the existing tool from Bayesian network literature — the orientation rules that tell you which edges are forced by the data — and transplant them into logic programming.

Jane: But then they add something that's genuinely new on this page. The relational structure gives you extra constraints that a plain propositional network doesn't have.

Tom: Exactly. If you have a rule that says a student's intelligence affects whether they pass a course, then every ground instance of that rule should have the same causal direction. The vocabulary itself imposes symmetries.

Jane: And that means you can orient edges that would otherwise be unorientable. The example they give is the burning objects — bonfires, houses, cigarettes — where the same cause-effect mechanism repeats across different instances.

Tom: That's the part I had to read twice. They're saying the relational alphabet itself is background knowledge, and you can use it to constrain the space of causal explanations.

Jane: So even with a single ground instance, as long as you accept the symmetries encoded by your predicates, you might still determine the causal order.

Tom: Right, and that's a big deal for practical use, because learned programs don't usually come with enough data to orient every edge locally.

Jane: Next they'll actually define the formal machinery — the dependency graphs, the orientation rules, and how symmetries are encoded. That's where things get technical.

Tom: Let's get to it.

Page 2 of the paper: Tom: Last time we set up the challenge: a probabilistic logic program learned from data gives you the probabilities, but not necessarily the causal order.

Jane: And page 3 makes that concrete with the drug example. You see patients on a drug with high blood pressure, and three stories fit the same numbers — the drug raises blood pressure, high blood pressure prompts the drug, or a hidden illness drives both.

Tom: That's the classic correlation-versus-causation moment. And it's why they bring in Pearl's causal Bayesian networks.

Jane: So they define a causal Bayesian network formally: a directed acyclic graph where each node carries a conditional probability given its parents. The graph encodes which way the arrows point.

Tom: Then they give the semantics — the probability of a configuration is the product of those conditionals. And here's a nice side note: once the graph is fixed, the parameters are actually uniquely determined.

Jane: That's a big deal, because it means all the ambiguity lives in the arrows. The numbers don't give you freedom; only the directions do.

Tom: Which brings them to interventions. The do-operation deletes all edges pointing into the node you're acting on, and forces the value you want.

Jane: So if you intervene on drug, you cut off whatever causes someone to take it, and you set it to "yes" or "no." Then you can read off the effect on blood pressure.

Tom: That matches the logic programming intuition too — you remove the rules that produce the atom and add a fact instead.

Jane: But they're careful to say this only works if your arrows actually follow the true causal flow. If the graph is wrong, your intervention is just graph surgery on a fiction.

Tom: And that raises the question they'll tackle next — when can the data itself tell you the arrows are forced? That's where Markov equivalence and faithfulness come in.

Jane: Let's look at that.

Page 3 of the paper: Tom: So last time we saw why the causal arrows matter, and we got the basic toolkit of d-separation and faithfulness.

Jane: Now page 5 gives us the payoff: a precise definition of when an edge’s direction is genuinely forced by the data.

Tom: Yeah, they call it orientability. An edge is orientable if it appears in every graph that’s Markov-equivalent to yours — meaning every graph encoding the same probabilistic independencies.

Jane: And then they bring in Meek’s classic result. He found a small set of local rules that, when you iterate them, give you every orientable edge in the graph.

Tom: So you start with the obvious cases — like an unshielded collider, where two arrows point into the same node and the sources aren’t connected. That direction is forced.

Jane: But the clever part is that orientable edges can then unlock other edges. Once you know one arrow’s direction, you can propagate that knowledge through the graph following those rules.

Tom: And this is exactly what the paper wants to borrow. If you have a probabilistic logic program, and its dependency graph turns out be fully orientable, then any other program that produces the same distribution must have the same graph.

Jane: Which means its interventions will match too. That’s their Proposition 3, and it gives a simple verifiable condition — orientability — for when a learned program supports causal reasoning.

Tom: But the page doesn’t stop there. It starts building the formal bridge, introducing propositional ProbLog programs with an external vocabulary for background facts and an internal vocabulary for the random variables.

Jane: And they are careful to restrict probabilities to values strictly between zero and one, because deterministic rules would break faithfulness and the whole orientability argument.

Tom: So the theory is clean for propositional programs. But logic programming is usually about relations, not just single propositions.

Jane: That’s the next piece — how to lift all this to relational programs. Let’s see how they handle that.

Page 4 of the paper: Tom: Last time we had the formal machinery for orientability; now we see how it actually plays out on a concrete program.

Jane: And the example they use is really intuitive: things burn if they're flammable, and burning things tend to smoke, especially if they're not dry.

Tom: So the program has three clauses, with the external facts like flammable and dry acting as background conditions.

Jane: And depending on which external facts hold, different clauses get activated. If flammable is true, you get the burns-to-smokes chain; if not, maybe nothing happens at all.

Tom: The key part is how they build the dependency graph from the activated rules, and then the semantics use noisy-or. So each clause contributes an independent chance of causing the effect.

Jane: That noisy-or is a nice fit for logic programming, because multiple rules can point to the same head, and the probabilities combine like independent mechanisms.

Tom: Then they define interventions on the program itself. You delete every clause that has the target atom as its head, and if you're forcing the atom true, you add a fact.

Jane: So if you want to force smoke, you cut the rules that produce smoke from burning, and you just assert smoke directly.

Tom: And Proposition 2 says something reassuring: doing that to the program gives exactly the same distribution as performing the corresponding intervention on the Bayesian network.

Jane: That's the bridge that makes everything else possible. It means the program's intervention semantics are faithful to the network's do-calculus.

Tom: So now they can claim their first real goal: verifying that a propositional program supports interventional reasoning, just by checking orientability.

Jane: And they're careful to note that faithfulness is required, and that deterministic rules would break it. So you should push those into the external database.

Tom: That's a pragmatic design choice, and it keeps the theory clean. But the example is still propositional — just a few atoms.

Jane: Real programs have relations, with variables and groundings. That's where the paper's own contribution really starts.

Tom: Let's see what happens when we move to relational programs and those causal symmetries.

Page 5 of the paper: Tom: Last time we saw how interventions work on propositional programs; now the paper moves to relational programs, where rules have variables and you ground them against a database.

Jane: And that’s a big step, because real probabilistic logic programs are almost always relational. You write one rule about students and courses, and it applies to every student and every course.

Tom: Right, so they lift the whole machinery. A relational clause looks like before, but the head and body are relational atoms with variables.

Jane: And the grounding step is the key: you take a database, say who takes which course, and substitute constants for variables. Every possible grounding becomes a propositional rule.

Tom: So the grounding produces a plain propositional program, and then everything from the earlier pages applies — the dependency graph, the Bayesian network, the interventions.

Jane: They’re careful to separate external predicates, which live in the database, from internal ones, which are the random variables. So "takes" is external, while "passes" and "int" are internal.

Tom: The example they give is nice — a single clause saying a student passes a course if they’re intelligent and they take the course. With two students and three courses, you get a cluster of edges.

Jane: And each edge points from the student’s intelligence to their grade in a particular course. So the same causal mechanism repeats across all the ground instances.

Tom: That repetition is exactly what the next section will exploit. The grounding produces many edges that all share the same direction because they come from the same rule.

Jane: So even if one of those edges can’t be oriented on its own, the others might help. That’s the seed of the causal symmetry idea.

Tom: Let’s see how they formalize that.

Page 6 of the paper: Tom: Last time we saw how relational programs ground into many edges that all come from the same rule; now the paper turns that repetition into a formal tool called a causal symmetry.

Jane: And it’s a clever twist on the standard orientation rules. Normally you only orient an edge if it’s forced in every Markov-equivalent graph. But now you can also say: these edges must all point the same way.

Tom: That’s Definition 17. A set of causal symmetries groups directed edges together, and a graph respects the symmetry if every edge in the group points in the same direction — all forward or all backward.

Jane: So if you know the cause-effect direction runs from intelligence to grades, that applies to every student and every course. You can’t have it point one way for Moe and the opposite way for Ana.

Tom: That immediately gives Proposition 4, which feels almost obvious: if one edge in a symmetry group turns out to be orientable, then all the others are orientable too.

Jane: Because any graph that respects the symmetry would have to flip them all together. So orienting one orients the whole group.

Tom: Then comes the real pay-off, Proposition 5. Standard Meek rules can orient unshielded colliders, where two arrows point into the same node. But they can’t orient an unshielded fork, where one node points to two separate nodes.

Jane: With a symmetry group, you can. If two edges form a symmetric fork and they belong to the same group, then orienting one forces the other, and you rule out the reversed fork entirely.

Tom: And that matters because forks are everywhere in relational data. A student’s intelligence causes their grade in math and their grade in English — that’s a fork.

Jane: So the paper gives you two new rules, and they work together. Proposition 5 gets you started on a fork, and Proposition 4 spreads the orientation to every edge in the symmetry group.

Tom: But the definition leaves the symmetry sets abstract. Where do they come from? The paper says you can take them from the relational vocabulary itself — that’s predicate symmetry.

Jane: We’ll see how that works, and where it can go wrong.

Page 7 of the paper: Tom: And now we get the concrete example that shows how powerful predicate symmetry really is.

Jane: Yeah, they take the UWCSE advisor example from the cplint suite. You have students, professors, projects, and the r11 relation that links them through publications.

Tom: The ground graph fragment is a tangle of r11 nodes pointing into advisedby nodes.

Jane: And if you only use the standard Meek rules, you can orient just one collider — the starred arrows.

Tom: But with the predicate symmetry assumption, all edges between r11 and advisedby must point the same way.

Jane: So once you orient one of those edges, every other edge between those two predicates follows automatically.

Tom: That's Proposition 4 in action. It turns a sparse local pattern into a global orientation.

Jane: And the nice thing is, this isn't an artificial toy. It comes from a real dataset about university webpages, the kind of relational data people actually work with.

Tom: So the practical payoff is clear. If you accept that the same pair of predicates always has the same causal direction, you can recover enough of the orientation to answer interventional questions.

Jane: They're upfront about that being a strong assumption. But they argue the relational vocabulary itself carries that assumption — it's part of how you define the domain.

Tom: They even point out where it breaks down, like time-stratified programs where causality flows one way between time steps and the other way for immunity.

Jane: In those cases you use prescribed orientations instead of symmetries, and they mention you can specify that in the implementation.

Tom: And speaking of implementation, they've put the whole thing on GitHub — in Prolog, using Logtalk and tabling.

Jane: So you can load your own program and see which edges come out orientable.

Tom: That makes this more than a theoretical contribution. You can actually test it.

Jane: Next they'll compare with earlier relational causal discovery work and talk about what's still missing.

Tom: Let's hear that.

Conclusion: Tom: So today we saw how to tell whether a probabilistic logic program actually supports causal reasoning, and the short version is: check if its dependency graph is orientable, and if you’re working relationally, use the symmetries in your vocabulary to get even further.

Jane: And the nice part is that this gives you a practical verification step for learned programs. You don’t have to trust that the learner found the true causal order; you can check whether the order is actually pinned down by the distribution.

Tom: Right, and if it isn’t, you know your interventional answers are ambiguous. That’s a real safeguard for anyone building decision systems on top of these programs.

Jane: They also made the whole thing concrete by showing how predicate symmetry can turn a single oriented edge into a whole family of oriented edges, like in that university advisor example.

Tom: And they were honest about the limits. The symmetry assumptions are strong, and determinism can break faithfulness entirely.

Jane: But they pointed to promising fixes, like the determinism-aware search method and the open question of whether these symmetry rules can be made complete.

Tom: The fact that they shipped an implementation on GitHub makes it even more useful. You can actually run this on your own programs.

Jane: Exactly. It moves the idea from a neat theoretical result to something you can test and build on.

Tom: For us, the big takeaway is that causal questions aren’t automatically off-limits just because you learned the program from data.

Jane: You just have to verify the conditions first, and now there’s a method for doing exactly that.

Tom: Next time we’ll pick up another paper that pushes statistical relational reasoning further, and we’ll see what other bridges can be built between logic, probability, and causation.

Jane: Looking forward to it.

Zora Wurm, Kilian Rückschloß, Felix Weitkämper

Ludwig-Maximilians-Universität München · Eberhard-Karls-Universität Tübingen · German University of Digital Science

cs.AI

Submitted: 2026-08-07

Updated: 2026-08-10

Comments: Accepted and presented at IJCLR 2025

Code: https://github.com/weitkaemper/plpbn-tools

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 69/100

Key concepts

Probabilistic logic programming: A logic program where each rule has a probability, inducing a probability distribution over what is true. For example, a rule might say 'with probability pi, burning things produce smoke.' Learning such a program from data gives probabilities but not causal direction.
Orientability: An edge in a causal graph is orientable if its direction is forced by every graph that encodes the same probabilistic independencies. Meek's rules provide a way to find all orientable edges. If a program's dependency graph is fully orientable, then any other program with the same distribution must have the same causal structure.
Causal symmetry: A set of edges that must all point in the same direction because they come from the same relational rule. For example, a rule about intelligence affecting grades applies to all students and courses, so the edge direction is the same across all ground instances. This allows orienting edges that would otherwise be unorientable, like forks.
Intervention (do-operation): An operation that forces a variable to a certain value while cutting off its causes. In logic programming, this means deleting rules that produce the atom and adding a fact. The paper shows that intervening on a program matches intervening on its corresponding Bayesian network, but only if the causal arrows are correct.

Terminology

Grounding — 19× in this paper · explained in 3 episodes
Causal Discovery — 5× in this paper · explained in 2 episodes
Causal Inference — 5× in this paper · explained in 4 episodes
Causal Reasoning — 1× in this paper · explained in 2 episodes

Summary

The paper addresses a fundamental challenge at the intersection of probabilistic logic programming and causal inference. Probabilistic logic programming is a statistical relational AI formalism that supports causal queries, including interventions from outside the system. However, the authors identify a critical gap: "When the structure of a probabilistic logic program is learned from data, however, only probabilistic information is used, and a single probability distribution may be compatible with several causal orders. This leads to ambiguity in interventional reasoning, raising the question of when the causal order is uniquely determined by the distribution."

The motivation is grounded in the classic insight that statistical correlation alone is insufficient to assess the effects of outside intervention. The paper builds on Pearl's causal Bayesian network framework, noting that causal Bayesian networks also support the simulation of external interventions on the system they model. The key connection is that "The probability distributions induced by acyclic probabilistic logic programs can be described by an associated Bayesian network, and prior work has shown that the intervention notion in probabilistic logic programs is compatible with that of the associated Bayesian network."

The authors review Pearl's framework, explaining that "if X and Y are Boolean random variables, their joint distribution can only tell use the correlation between them; it cannot distinguish between an effect of X on Y, an effect of Y on X or indeed a hidden confounding variable Z affecting both X and Y. They give the example that if we merely observe that patients taking a particular drug are more likely to have high blood pressure, we cannot tell whether the drug increases blood pressure, high blood pressure causes people to take the drug, or in fact an underlying illness is responsible both for the patients' taking the drug and for the high blood pressure."

A causal Bayesian network is defined as a directed acyclic graph G on a set of Boolean random variables V and, for every random variable A ∈ V and every subset T ⊆ Pa(A) of the parents of A, a conditional probability µT (A) ∈ [0, 1]. The semantics assign to a value assignment v ⊆ V the probability:

πB(v) = ∏ A∈V µ v∩Pa(A)(A)

Interventions are modeled by the operation B do(A=t), which removes all edges into A and fixes its value.

The paper introduces the key concept of faithfulness: "A probability distribution µ on a set of random variables V is faithfully Markov to a directed acyclic Graph G on V if for any two random variables X, Y ∈ V and any subset Z ⊂ ZV, X and Y are probabilistically independent if and only if Z d-separates X and Y in G. The authors note that faithfulness has been shown to be satisfied Lebesgue almost always in a Boolean Bayesian network, but warn that deterministic variables in Bayesian networks frequently breach faithfulness in practice, as in the constellation A → B → C where If B is deterministic and depending only on A, then conditioning on A renders B a constant and thus independent of its direct successor C."

Orientability is defined: A directed edge (X, Y) in a directed acyclic graph G is orientable if it is contained in any graph that is Markov-equivalent to G. The paper cites Meek's characterization:

If (A, B) and (C, B) be edges of G such that A and C are not adjacent in G, then (A, B) and (C, B) are orientable.
If (A, B) is orientable, (B, C) an edge, and A and C not adjacent, then (B, C) is orientable.
If (A, B) and (B, C) are orientable and (A, C) is an edge, then (A, C) is also orientable.
If (B, D) and (C, D) are orientable, A adjacent to both B and C but B not adjacent to C and (A, D) an edge, then (A, D) is orientable.
If (A, C) and (C, D) are orientable, B is adjacent to both A and C and (B, D) is an edge, then (B, D) is orientable.

The paper formalizes ProbLog clauses as expressions (π:: R ← R1,..., Rm, L1,..., Ln.) with:

an internal atom R as effect
a set of internal literals as causes
a set of external literals as condition
a probability π(RC) ∈ (0, 1), with π(RC) = 1 disallowed

A program is acyclic if, disregarding its probabilities, Π is an acyclic logic program. Given an external valuation V, the relative program Π V consists of clauses activated by V. The dependency graph GraphV(Π) has the internal vocabulary I as nodes, with an edge p −→ q whenever there is a clause RC ∈ Π V with head q such that either p or ¬p occurs among the causes of RC.

The semantics use a noisy-or function: the conditional probability of an internal atom p given a valuation v on its parents is noisy-or πRC ∈ Π V v = causes(RC) where the noisy-or function "associates with every multi-set S of values in the unit interval the number 1 − ∏ s∈S(1 − s), which is precisely the probability that if each s ∈ S is the probability of an independent Bernoulli trial, at least one of them would succeed."

Interventions on propositional programs are defined: "Let L ∈ p, ¬p be an internal literal and Π be a propositional ProbLog program. Then, the intervention Πdo(L) is obtained from Π in two steps. First, remove all clauses with p in the head. Then, if L is a positive intervention, add the fact p to the program. A key result (Proposition 2) states: the probability distribution of Π V do(L) coincides with the outcome of intervening on L in the Bayesian network of Π V."

The first main result (Proposition 3) states: "Let Π be a propositional probabilistic logic program and let V be an external valuation. Assume that Π V is acyclic faithfully Markov to GraphV (Π), which furthermore is orientable. Let Π̃ be another propositional probabilistic logic program Π̃ such that Π̃ V is acyclic and faithfully Markov to GraphV (Π̃), which encodes the same probability distribution as Π V. Then GraphV (Π) = GraphV (Π̃), and for every internal literal L, Π V do(L) and Π̃ V do(L) encode the same probability distribution."

The proof relies on the fact that "any other propositional probabilistic logic program Π̃ whose relativisation Π̃ V has the same distribution and is faithfully Markov to its dependency graph must have a relative dependency graph that is Markov-equivalent to GraphV (Π). Since GraphV (Π) is orientable, in fact GraphV (Π̃) = GraphV (Π). The authors note that we have to require faithfulness to close the gap between orientability and the equivalence of the underlying graphs, and recommend that deterministic logical dependencies should be restricted to the underlying database."

The paper extends to the relational setting, where "even after grounding to a specific database instance, we can take into account our knowledge of the internal structure of atoms (for instance, different atoms may share a single functor) to postulate further symmetries that can assist in orienting edges of our dependency graph."

A relational ProbLog program is grounded relative to an external database E (an E-structure). The grounding Π(E) is the propositional ProbLog program given by the set of the groundings to E∗ of all random clauses in Π. This gives rise to the relative propositional program Π E and the ground graph GraphE(Π). The paper provides an example of a student-course model:

π:: passes(X, Y) ← int(X), takes(X, Y).

with the dependency graph showing edges int(moe) → gr(moe, eng), gr(moe, math) etc., representing that a student's intelligence influences their passing likelihood.

The central novel contribution is the exploitation of causal symmetries: In relational probabilistic logic programs, different edges in a ground graph may stem from the same underlying cause-effect mechanism. A program structure S "captures the causal relationship between two random predicates q/n and r/m as an abstract rule c with head(c):= q(X1,..., Xn) and r(Y1,..., Ym) ∈ body(c). Every grounding of c generates a corresponding rule in the grounded program, and all edges will induced by those rules will share the same direction. We call this simultaneous behaviour of relations in a ground graph causal symmetry."

Formally (Definition 17): "Let G be a directed acyclic graph. Let M be a set of sets of directed edges extending adjacencies in G such that for all m ∈ M, also (X, Y) (Y, X) ∈ m ∈ M. Then G respects the causal symmetries in M if for all m ∈ M, either for every (X, Y) ∈ m, (X, Y) is also an edge in G, or for every (X, Y) ∈ m, (Y, X) is an edge in G. If G respects the causal symmetries in M, an edge in G is called M-orientable if it is present in every G′ Markov-equivalent to G which also respects the causal symmetries in M."

Two new orientation rules are introduced:

Proposition 4: "Let G be a directed acyclic graph that respects the causal symmetries in M, let (A, B) be an M-orientable edge in G and let (C, D) be an edge in G such that there is an m ∈ M with (A, B), (C, D) ∈ m. Then (C, D) is M-orientable." This allows orientation to propagate within a symmetry class.

Proposition 5: Let G be a ground graph with a set of causal symmetries M. If A and C are not adjacent in G and (B, A) and (B, C) are edges in G, and (A, B), (C, B) ∈ m for an m ∈ M, then (B, A) and (B, C) are orientable. This extends orientation beyond unshielded colliders to symmetric forks, which the authors note was first noticed by Maier in relational causal discovery.

The most important instantiation is predicate symmetry (Definition 18): the set of all sets of the form (P (a), R(b)) P (a) is adjacent to R(b) in G, where (P, R) ranges over all pairs of distinct predicates in I. This encodes the assumption that the predicates of relations are the only determinants of their cause-effect direction and is equivalent to the assertion that the predicate dependency graph of any program structure does not have 2-cycles.

The authors caution that predicate symmetry is inappropriate when our initial program structure itself has 2-cycles in its predicate dependency graph, as can be typically encountered in time-stratified programs, giving the example:

"π1:: ill(x, t) ← ¬resistant(x, t).

π2:: resistant(x, t) ← ill(x, t′), time step(t, t′)."

where causal flow is clearly reversed in the two encoded processes, and therefore predicate symmetry is unsuitable. In such cases, they recommend prescribing edge orientations as background knowledge, following Meek.

The paper demonstrates the power of the symmetry-based approach on a program derived from the UWCSE dataset:

"π1:: advisedby(A, B) ← r11(A, B, C), student(A), professor(B), project(C, A), project(C, B).

π2:: advisedby(A, B) ← student(A), professor(B), ta(C, A), taughtby(C, B).

π3:: r11(A, B, C) ← publication(D, A, C), publication(D, B, C)."

The authors note: "As there is only one unshielded collider, an algorithm taking into account only the ground graph could orient only the starred arrows. However, if we assume predicate symmetry, then the set of all edges from a relation with r11/3 to a relation with advisedby/2 forms a causal symmetry. Thus, once the starred arrows are oriented, all the remaining arrows can also be oriented likewise according to Proposition 4. They conclude that if we accept the assumption of predicate symmetry, we can use this induced ProbLog program for interventional reasoning."

The key insight is that "symmetries are very powerful in exploiting the local structure of forks or colliders in one part of the ground dependency graph to orient those edges where due to limitations on the size or structure of the database the same edge appears as a 1:1 relation."

The authors position this as the first contribution to study the problem of identifying causal effects specifically for probabilistic logic programs. Compared to Maier's work on lifted Bayesian networks, they note that Maier assumes this graph to be acyclic, which seems an even stronger condition than the assumption of predicate symmetry, and that his framework seems to imply that the probability distribution is known independently of any background logical theory or ground database, whereas probabilistic inductive logic programming typically learns from a single ground database ('mega-example'), and therefore causal analysis should also be domain-specific.

Two future directions are highlighted:

Determinism-aware causal discovery: Since deterministic relationships are arguably more prevalent in probabilistic logic programming than in other statistical relational approaches, the authors suggest adapting to recent score-based causal inference approaches such as determinism-aware greedy equivalent search, which are designed for partially deterministic contexts.
Completeness of symmetry-aware orientation rules: "While our symmetry-aware orientation rules are correct, they are not complete. Given the broader relevance of symmetries beyond probabilistic logic programming, it would be worthwhile to study this problem more generally, for instance by establishing the complexity class of edge orientation under symmetry constraints."

The paper establishes a general method to verify the causal content implied by a probabilistic logic program. For propositional programs, this is achieved by mapping the program to a Bayesian network and applying the known orientation rules of Meek. The extension to relational programs takes into account symmetries arising from grounding a relational probabilistic logic program. The authors introduce predicate symmetry to encode the assumption that the predicate symbols are the only determinants of cause-effect direction, showing that "such symmetries can be exploited to orient more ground structures than would otherwise have been possible. In particular, symmetric forks can now be oriented as well as colliders, and orientations can be propagated along sparse relational structures. An implementation is available as part of the PLP-BN tools on GitHub, providing access to both predicate symmetries and sets of symmetries prescribed by the user, exposed as a transparent Logtalk API."

Improvements for AI systems

A system incorporating this paper gains the following capabilities:

Causal identifiability gate for intervention queries. The system adds a verification step that checks whether the learned program's dependency graph is acyclic, faithfully Markov, and orientable before answering interventional questions. It can determine whether the observed distribution uniquely determines the causal order, and it can refuse to answer—or explicitly flag as ambiguous—queries when multiple causal orders are compatible with the data.
Sound intervention semantics via the Bayesian network bridge. Using Proposition 2, the system maps its ProbLog do(L) interventions directly onto Bayesian network interventions, and using Proposition 3, it guarantees that the interventional distribution it computes is identical across all programs consistent with the data and faithful to their dependency graphs. It can answer what-if queries (e.g., what happens if we force all patients to take the drug?) with a correctness guarantee whenever orientability holds.
Symmetry-aware orientation propagation. The system implements causal symmetries (Definition 17) and predicate symmetry (Definition 18), so that once a single edge in a symmetry class is oriented (e.g., by an unshielded collider), Proposition 4 propagates that orientation to every other grounded edge between the same predicate pair. It can orient far more of a learned relational structure than ground-graph-only methods.
Sparse-data causal discovery. Because orientation propagates along symmetry classes (Proposition 4), the system can orient edges that appear as hard-to-identify 1:1 relations in sparse databases, as long as the same underlying predicate-level mechanism is observable as a collider or fork elsewhere in the ground graph. It can deliver causal conclusions from small relational datasets where per-edge causal discovery would give up.
Symmetric fork orientation. The system applies Proposition 5 to orient structures that are not unshielded colliders—specifically, forks whose children fall in the same causal symmetry class. It can identify cause-effect direction in relational configurations that Meek's rules alone leave undetermined.
Faithfulness violation detection and handling. The system checks for deterministic dependencies in the program that breach faithfulness (as in the A → B → C constellation with deterministic B). It can warn the user that interventional conclusions are unreliable, or automatically restrict deterministic logical dependencies to the underlying database layer, keeping the probabilistic dependency graph faithful and the causal analysis sound.
Assumption-aware causal explanations. For every oriented edge and every interventional answer it produces, the system tracks whether the orientation relied on a collider, a Meek rule, a symmetric fork, a propagated symmetry, or a user-prescribed symmetry. It can report exactly which assumptions (faithfulness, predicate symmetry, background knowledge) were required, so a human can judge the confidence of the result.
Background-knowledge-guided orientation for dynamic programs. The system supports user-supplied symmetry sets (as in the paper's Logtalk API), and it detects when predicate symmetry is inappropriate—e.g., 2-cycles in the predicate dependency graph, as in time-stratified programs like ill(x,t) ← ¬resistant(x,t) vs. resistant(x,t) ← ill(x,t′), time step(t,t′). It can then orient such temporal edges using prescribed background knowledge instead of failing or defaulting to an invalid symmetry assumption.
Lifted, scalable causal reasoning. By making orientation decisions at the predicate-pair level rather than per grounded atom, the system compresses the causal discovery problem. It can reason about relational programs with large ground graphs efficiently, because the number of orientation decisions scales with the number of abstract rules, not the number of ground instances.
Robust interval-valued intervention answers. When the causal order is not uniquely identifiable even after symmetry reasoning, the system enumerates the remaining plausible orientations (the symmetry-respecting Markov equivalence class) and simulates the intervention under each. It can report the range of possible interventional effects instead of a single unjustified point estimate.
Determinism-aware causal learning. Following the paper's proposed direction, the system integrates score-based, determinism-aware causal discovery (e.g., determinism-aware greedy equivalent search) into probabilistic logic program learning. It can learn satisfactory causal structures from programs containing partially deterministic relations—which the paper notes are unusually common in logic programming—where pure constraint-based orientation would fail.
Causal query answering over relational knowledge bases. Applied beyond ProbLog, the system uses predicate symmetry to distinguish correlation from causation at the level of relation types in any grounded relational model. Given a knowledge graph with predicates like advisedby, ta, and taughtby, it can answer interventional queries (e.g., if we intervene on the advising relation, how does publication collaboration change?) rather than merely predictive or associational ones.