Qualitative Mechanism Independence
Authors: Oliver Ethan Richardson
Spencer J Peters
Joseph Halpern
Venue: NeurIPS 2024 poster (2024)
Keywords: causality
information theory
directed hypergraphs
qualitative structures
Primary area: causal_inference
TL;DR: a definition of compatibility between a distribution and a directed hypergraph, with implications for causality and information theory

Abstract: We define what it means for a joint probability distribution to be compatible with aset of independent causal mechanisms, at a qualitative level—or, more precisely with a directed hypergraph $\mathcal A$, which is the qualitative structure of a probabilistic dependency graph (PDG). When A represents a qualitative Bayesian network, QIM-compatibility with $\mathcal A$ reduces to satisfying the appropriate conditional independencies. But giving semantics to hypergraphs using QIM-compatibility lets us do much more. For one thing, we can capture functional dependencies. For another, we can capture important aspects of causality using compatibility: we can use compatibility to understand cyclic causal graphs, and to demonstrate structural compatibility, we must essentially produce a causal model. Finally, compatibility has deep connections to information theory. Applying compatibility to cyclic structures helps to clarify a longstanding conceptual issue in information theory.

Qualitative Mechanism Independence
Oliver E. Richardson Dept of Computer Science Cornell University
Spencer Peters Dept of Computer Science
Joseph Y. Halpern
Dept of Computer Science
Cornell University Ithaca NY 14853 spetersecs. cornel1 edu
Cornell University Ithaca NY 14853
Ithaca NY 14853
oli@cs, cornell. edu
halpern@cs cornell.....ooo edu
Abstract
We define what it means for joint probability distribution to be (QIM-jcompatible with a set of independent causal mechanisms, at a qualitative level-ane or, more precisely, with directed hypergraph A, which is the qualitative structure of a prob- abilistic dependency graph (PDG). When A represents a qualitative Bayesian net- work, QIM-compatibility with A reduces to satisfying the appropriate conditional independencies. But giving semantics to hypergraphs using QIM-compaibbility lets do much more. For one thing, we can capture functional dependencies. For another, QIM-compatibility captures important aspects of causality: we can use compatibility to understand cyclic causal graphs, and demonstrate compatibility is essentially to produce a causal model. Finally, compatibility has deep connec- tions information theory. Applying compatibility to cyclic structures helps clarify a longstanding conceptual issue in information theory.
1 Introduction
The structure of (standard) probabilistic graphical model (like a Bayesian Network or Markov Random Field) encodes set of conditional independencies among variables. This is useful because enables a compact description of probability distributions that have those independencies; also lets graphs visual language for describing important qualitative properties of probabilistic world. Yet these kinds of independencies are not the only important qualitative aspects a probability measure. In this paper, study natural generalization of standard graphical model structures that can describe far more than conditional independence.
For example, another qualitative aspect of probability distribution is that of functional dependence, which also exploited across computer science to enable compact representations and simplify probabilistic analysis. Acyclic causal models, for instance, specify distribution via probability over contexts (the values variables whose causes are viewed as outside the model), and collection of equations (i.e., functional dependencies) [18]. And in deep learning, popular class of models called normalizing flows [25, 12] specify a distribution by composing a fixed distribution over some latent space, say standard normal distribution, with function (i.e., functional dependence) fit to observational data. Functional dependence and independence are deeply related and interacting notions. For instance, if B is function of A (written
B) and independent of C' (written A JL C), then B and C are also independent (B 11. C). Moreover, dependence can be written in terms of independence: Y is a function of X if and only if Y is conditionally independent of itself given X (i.e., X + Y iff Y IL Y X). Traditional graph-based languages such as Bayesian Networks (BNs) and Markov Random Fields (MRFs) cannot capture these relationships. Indeed, the graphoid axioms (which describe BNs and MRFs) [21] and axioms for conditional independence [17], do not even consider statements like L. A be syntactically valid. Yet such statements
'Thi well-known fact (Lemma 10) is formalized and proved in Appendix A, where all proofs can be found.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

are perfectly meaningful, and reflect a deep relationship between independence, dependence, and generalizations of both notions (grounded information theory, a point we will soon revisit).
This paper provides a simple yet expressive graphical language for describing qualitative structure such dependence and independence in probability distributions. The idea is specify the inputs and outputs of a set of independent mechanisms: processes by which some target variables I are determined as a (possibly randomized) function of some source variables S. This idea generalizes intuition going back to Pearl [18] by allowing, for example, two mechanisms to share a target variable. So at qualitative level, the modeler specifies not a (directed) graph, but a (directed) hypergraph.
If we were interested in a concrete probabilistic model, we would also need to annotate this hypergraph with quantitative information describing the mechanisms. For directed acyclic graphs, there two standard approaches: supply conditional probability distributions (cpds) to get a BN, or supply equations get a causal model. Correspondingly, there based on hypergraphs. The analogue of the first approach supplying a probability P(T)S) for each mechanism-leaads to the notion of a probabilistic dependency graph (PDG) [23, 22, 24]. The analogue of the second ppproach--upplyyine independent random noise-leads to novel generalization of a causal model (Definition 4). Models of either kind are of interest to us only insofar as they explain how hypergraphs encode qualitative aspects of probability. Qualitative information in a PDG was characterized by Richardson and Halper [23] using a scoring function that, despite having some attractive properties, lacks justification and has not been fully understood. In particular, the PDG formalism does not appear to answer a basic question: what does it mean for distribution to be compatible with a directed hypergraph structure?
approaches to probabilistic modeling
an equation describing ' as a function of S and
We develop precisely such a notion (Definition 2) of compatibility between a distribution μ and directed hypergraph qualitatively representing a collection of independent mechanisms- or, for short, simply MoM---cooaatibillty.. This definition allows us use directed hypergraphs as a language for specifying structure in probability distributions, of which the semantics of qualitative BNs are special case (Theorem 1). Yet QIM-compatibility can do far more than represent conditional independencies in acyelic networks. For one thing, it can encode arbitrary functional dependencies (Theorem 2); for another, it gives meaningful semantics to cyclic models. Indeed, compatibility lets us go well beyond capturing dependence and independence. The fact that Pearl [18] views causal models as representing independent mechanisms suggests that there might be connection to causality. In fact, there is. A wifness that distribution μ is compatible with hypergraph AA is an extended distribution j that is nearly equivalent to (and guarantees the existence of) a causal model that explains f with dependency structure A (Propositions 3 to 5). As we shall see, thinking in terms of witnesses and compatibility allows us to tie together causality, dependence, and independence.
Perhaps surprisingly, compatibility also has deep connections with information theory (Section 4). The conditional independencies of BN can be viewed as a certain kind of information theoretic information-thcoreiiic constraint. Our notion of compatibility with hypergraph A turns out to imply a generalization of this constraint (closely related the qualitative PDG scoring function) that meaningful for all hypergraphs (Theorem 7). Applied to cyclic models, it yields a causally inspired notion of pairwise interaction that clarifies some important misunderstandings in information theory (Examples and 6).
Saying that one approach to qualitative graphical modeling has connections to so many different notions is rather bold claim. We spend the rest of the paper justifying it.
2 Qualitative Independennt-Mechaniis (QIM) Compatibility
In this section, we present the central definition of our paper: a way of making precise Pearl's notion of "independent mechanisms", used to motivate Bayesian Networks from causal perspective. Pearl [19, p.22] states that "each parent-child relationship in a causal Bayesian network represents a stable and autonomous physical mechanism." " But, technically speaking, a parent-child relationship only partially describes the mechanism. Instead, the autonomous mechanism that determines the child is really represented by that child's joint relationship with all its parents. So. the qualitative aspect of a mechanism is best represented as a directed hyperarc [5], that can have multiple sources.
Definition 1. A directed hypergraph (or simply a hypergraph, since all our hypergraphs will be directed) consists of N of nodes and a set A of directed hyperedges, or hyperarcs; each hyperarc a E A associated with a set S. S N of source nodes and set T, C A of target nodes. We write S e A to specify hyperarc A together with its sources S = S, and targets T = Tg. Nodes

---

that are neither a source nor a target of any hyperare will seldom have any effect on our constructions; the other nodes can be recovered from the hyperares (by selecting N := Uae S. U UT))) Thus, we often leave N implicit, referring to the hypergraph simply as A.
M
Following the graphical models literature, we are interested in hypergraphs whose nodes represent variables, so that each X E .N will ultimately be associated with a (for simplicity, finite) set V(X) of possible values. However, one should not think of V as part of the information carried by the hypergraph. It makes perfect sense to say that X and Y are independent without specifying the possible values of X and Y. Of course, when we talk concretely about a distribution μ on a set of variables X = V), those variables must have possible values but the qualitative properties of 14, such as independence, can be expressed purely in terms of N, without reference to V.
Intuitively, we expect a joint distribution (x(x)) to be qualitatively compatible with a set of independent mechanisms (whose structure is given by a hypergraph AA if there is mechanistic explanation of how each target arises as a function of the variable(s) on which it depends and independent random noise. This is made precise by the following definition.
Definition 2 HiM-coompatiiilityy. Let X' and y be (possibly identical) sets of variables, and A (S, be a hypergraph with nodes X. We say distribution s=())) is qualitatively independent- mechanism compatible, or (0IM-)compatible with A (symbolically: / F Q-A) iff there exists an extended distribution pa) U X' U Ma) of μ()²) to A' and to U^ = (Ua)aEA an additional set of "noise" variables (one variable per hyperare) according to which:
(a) the variables y are distributed according to (b) the variables UA are mutually independent (c) the target variable(s) Ta of each hyperare a E A are determined by U, and the source variable(s) S.
(i.e., (A())) = x())))
Gee.pauA = IIoEAF(Ua)) ) and
(i.e., Ya E A. F (S Un) - Ta). We call such a distribution p(( U LYU U MA)= a wimess that f is QIM-compatible with A.
While Definition 2 requires the noise variables {Ua A to be independent of one another, note that they need not be independent of any variables in X. In particular, U₂ may not be independent of S. and the situation can diverge from what one would expect from a randomized algorithm, whose randomness U is assumed to be independent of its input S. Furthermore, the variables in ll may not be independent of one another conditional on the value of some X E
Example 1. pxX, Y) is compatible with AA = (x), (+)})} (depicted in PDG notation as -X K-)) ) iff X and are independent, i.e., ((X, Y) = (Y)) For if U1 and U2 are independent and respectively determine X and Y, then X and Y must also be independent.
A
This is a simple illustration of a more general phenomenon: when A describes the structure of a Bayesian Network (BN), then QIM ciM-coopatibility with A coincides with satisfying the independencies of that BN (which are given, equivalently, by the ordered Markov properties [14], factoring as a product of probability tables, or d-separation [6]). To state the general result (Theorem 1), must first clarify how the graphs of standard graphical and causal models give rise to directed hypergraphs.
Suppose that G = (V. F)) is a graph, whose edges may be directed or undirected. Given vertex u E V. write (w) := {o (v, u) E E} for the set of vertices that can "influence" u. There is a natural way to interpret the graph G as giving rise to set of mechanisms: one for each variable which determines the value of u based the values of the variables on which u can depend. Formally, let Ag = { (a " {u} } Swev be the hypergraph corresponding to the graph G.
Theorem 1. If G is a directed acyelic graph and IGG consists of the independencies of its corre- sponding Bayesian network, then μ - AG if and only if y satisfies I(G).
Theorem I shows, for hypergraphs that correspond to directed acyclic graphs (dags), our definition of compatibility reduces exactly to the well-understood independencies of BNs. This means that QIM- compatibility, a notion based on the independence of causal mechanisms, gives us a very different way of characterizing these independencies one that can be generalized to a much larger class of graphical models that includes, for example, cyclic variants [1]. Moreover, QIM-compatibility can capture properties other than independence. As the next example shows, it can capture determinism.
Example If A = + x2 consists of just two hyperares pointing to a single variable X, then a distribution p ((X) is QIM-compatible with A iff μ places all mass on single value E V(X). A
3

---

Intuitively, if two independent coins always give the same answer (the value of X), then neither coin can be random. This simple example shows that we can capture determinism with multiple hyperares pointing to the same variable. Such hypergraphs do not correspond to graphs; recall that in a BN, two arrows pointing to X (e.g.. Y - X and Z + X) represent a single mechanism by which X is jointly determined (by Y and 2), rather than two distinct mechanisms.
Given a hypergraph A = (W. X, Y S N, and natural number n 2 0, let AU (+n) denote the hypergraph that results from augmenting A with additional (distinet) hyperares from X to Y.
Theorem 2.
(a) / -== X-+Y A QA if and only if Vn 2 O. / F QAU (+a)
X-Y
(b) if = for dag G, then μ F= X- A OA if and only if F QAU
(4)
X-Y
(c) if 3a E A such that S. 0 and X E Ta, then μ F X- A Af F CAU (+2) X-Y-
Based on the intuition given after Example 2, may seem unnecessary ever add more than two parallel hyperares to ensure functional dependence in part (a). However, this intuition implicitly assumes that the randomness U1 and U2 of the two mechanisms independent conditional on X, which may not be the case. See Appendix D for counterexamples.
Finally, as mentioned above, QIM-compatibilit gives meaning cyclic structures, a topic that we will revisit often in Sections 3 and 4. We start with a simple example.
Example 3. Every pxX, Y) is compatible with X マ2 Y because every distribution is compatible
with - x +Y Y and mechanism with no inputs is a special case of one that can depend on Y. A
The logic above is an instance of an important reasoning principle, which we develop in Appendix B. Although the 2-cycle in Example 3 is straightforward, generalizing it even slightly to 3-cycle raises a not-soo-straighfforraad question, whose answer will turn out to have surprisingly broad implications.
Example 4. What (xX, Y, Z) are compatible with the 3-cycle shown, on the right? By the reasoning above, among them must be all distributions consistent with a linear chain -
Thus, any distribution in which two variables are conditionally independent given the third compatible with the 3-cycle. Are there distributions that are nol compatible with this hypergraph? It is not obvious. We return to this in Section 4. A
X
Z
Because OlM-compaiibility applies to cyclic structures, one might wonder if it also captures the independencies of undirected models. Our definition of Ag, as is common, implicitly identifies a undirected edge A-B with the pair (A-B, B B-A} of directed edges; in this way, it naturally converts even an undirected graph G to (directed) hypergraph. Compatibility with Ac. however, does not coincide with any of the standard Markov properties corresponding to G [13]. This may appear to be flaw in Definition 2, but it is unavoidable (see Appendix B) if we wish to also capture causality, as we do the next section.
3 QIM-Compaiibility and Causality
Recall that in the definition of DJM-compatibility, each hyperarc represents independent mecha- nism. Equations in a causal model are also viewed as representing independent mechanisms. This suggests a possible connection between the two formalisms, which we now explore. We will show that QIM-compatibility with A means exactly that a distribution can be generated by a causal model with the corresponding dependency structure (Section 3.1). Moreover, such causal models and QIM- compatibility witnesses are themselves closely related (Section 3.2). In this section, we establish a causal grounding for QIM-compatibility. To do so, must first review some standard definitions.
Definition 3 (Pearl [19]). A structural equations model (SEM) is tuple M = (24, V, V.F). where
W is a set of exogenous variables;
V is a set of endogenous variables (disjoint from U(); F = [/yrrev associates to each endogenous variable Y an equation fY v(UUV-Y) - V(Y)
that determines its value as a function of the other variables.
In SEM M, variable X E y does not depend on Y E Vuulif [x(..., for y. y E V(Y). Let the parents Pa (X) of X the set of variables on which depends. M is acyclic iff Pay (X) V = (Xa(X) for some dag G with vertices V. In acyclic SEM, it is
(x(..,,''... ...)

---

easy to see that a setting of the exogneous variables determines the values of the endogenous variables SEM, together
(symbolically: M += U * V). A probabilisticc SEM (PSEM) M (M, with a probability P over the exogenous variables. When M }= 4 - V. the distribution P(4) extends uniquely to distribution over U() cylic PSEM, however, may induce more than one such distribution, or none at all. In general, a PSEM M induces a (possiby empty) convex set of distributions over V(u U V). This set is defined by two (linear) constraints: the equations F must hold with probability 1, and the marginal probability over U must equal P. Given a PSEM M, let {MB consist of all joint distributions VI, V) that satisfy the two constraints above; this set captures the behavior of M in the absence of interventions. A joint distribution μ²() over X C VUU can arise from a (P)SEM M iff there is some V E {M] whose marginal on X is J..
We now review the syntax of a language for describing causality. A basic causal formula is one of the form (Y-y] (p, where o a Boolean expression over the endogenous variables V. Y C V a subset of them, and y E V(Y). The language then consists of all Boolean combinations of basic formulas. In causal model M and context u E V(U). a Boolean expression yp over V is true iff holds for all (u, x) E V(U, V) consistent with the equations of M. Basic causal formulas are then given semantics by (M, u) + yY iff (My+y, u) = s,, where My--y is the result of changing each fr, for Y E Y. to the constant function + y y|Y], which returns (on all inputs s) the value of Y in the joint setting y. The dual formula (Y+y) == - y|
mip is equivalent to y O in SEMs where each context u induces unique setting of the endogenous variables [7]. A PSEM M (M. P)
assigns probabilities to causal formulas according to PIM(() == P((u E V(U): : (M, u) } +)).
Some authors assume that for each variable X, there is a special "independent noise" exogenous variable Ux on which only the equation fx can depend; we call PSEM (M, P) randomized if it contains such exogenous variables that are mutually independent according to P, and fully randomized all its exogenous variables are of this form. Randomized PSEMs are clearly a special class of PSEMs, but note also that every PSEM can be converted to an equivalent randomized PSEM by extending it with additional dummy variables bxEv that can take only a single value. Thus, we do not lose expressive power by using randomized PSEMs. In fact, qualitatively, randomized PSEMs are more expressive: they can encode independence.
3.1 The Equivalence Between QLM-Compatibillty and Randomized PSEMs
We are now equipped to formally describe the connection between QIM-compatibility and causality. At high level, this connection should be unsurprising: witnesses and causal models both relate dependency structures to distributions, but in "opposite directions".. QIM-compatibility starts with distributions and asks what dependency structures they are compatible with. Causal models, on the other hand, are explicit (quantitative) representations of dependency structures that give rise to sets of distributions. We now show that the existence of a causal model coincides with the existence of a witness. We start by showing this for the hypergraphs generated by graphs (like Bayesian networks, except possibly eyclic), which we show correspond to fully randomized causal models (Proposition 3). We then give natural generalization of a causal model that exactly captures QIM-compatibility with an arbitrary hypergraph (Proposition 4). In both cases, the high-level result is the same: fa } A iff there is causal model that "has dependency structure A²" that gives rise to μl.
More precisely, randomized causal model M has dependency structure A iff there is a 1-1 correspondence between a E A and the equations of M, such that the equation Sa produces a value of Te and depends only on Sa and Ua. The definition above emphasizes the hypergraph; for readers interested in causality, here is an equivalent one that emphasizes the causal model: M is of dependency structure A iff the targets of A are disjoint singletons corresponding to the elements of y (so A = {Sy + HY)rev)) and PaM(Y) C Sy U {Uy} } for all Y = V. We start by presenting the result in the case where A corresponds to a directed graph.
Proposition 3. Given a graph G and a distribution μe, μ == Aa iff there exists a fully randomized PSEM of dependency structure AG from which μ can arise.
In other words, compatibility with hypergraph corresponding to a graph means arising from a fully randomized PSEM of the appropriate dependency structure. In light of this, Theorem I can be viewed as formalizing a phenomenon that seems to be almost universally implicitly understood: every acyelic fully randomized SEM induces distribution with the independencies of the corresponding Bayesian Network. Conversely, every distribution with those independencies arises from such a causal model. Both halves have been recognized before. Druzdzel and Simon [4, Theorem 1] arguably establish
5

---

one direction of the correspondence (turning BN into a causal model). but their statement of the result obscures the possibility of a converse. Pearl's ss causal Markov condition [20, Theorem 1]. on the other hand, is closely related to that converse (as will be made explicit by our Proposition 3). Yet, to the best of our knowledge, the two results have not before been combined and recognized as an equivalent characterization of a BN's conditional independencies.
Like before, QIM-compatibility allows us to go much futher. It easy to extend Proposition 3 the dependency structures of all randomized PSEMs. But what happens if AA contains hyperarcs with overlapping targets? Here the correspondence starts to break down for a simple reason: by definition, there is at most one equation per variable in a (P)SEM; thus, no PSEM can have dependency structure A. Nevertheless, the correspondence between witnesses and causal models persists if we simply drop the (traditional) requirement that F is indexed by V. This leads us to consider natural generalization of a (randomized) PSEM that has an arbitrary set of equations- not just one per variable.
Definition 4.
Let (N. A) be a hypergraph. generalized randomized PSEM M (X (X,U,F,P) P) with structure A consists of sets of variables X' and u = { EEEA, together with a set of functions F= (SS)) x V(U,) + V(Ta))aE.A. and a probability Pa over each independent noise variable U.. The meanings of {M) } and can arise are the same as for a PSEM.
Proposition 4. μ + QA iff there exists a generalized randomized PSEM with structure A from which μ can arise.
Generalized randomized PSEMs can capture functional dependencies, and constraints. For instance, an equality (say X = =) can be encoded in a generalized randomized PSEM with a second equation for X. Indeed, we believe that generalized randomized PSEMs can capture a wide class of constraints, and are closely related to causal models with constraints [2], a discussion we defer to future work.
3.2 Interventions and the Correspondence Between Witnesses and Causal Models
We have seen that QIM-compatibility with A (i.e., the existence of a witness (t) coincides exactly with the existence of a causal model M from which distribution can arise. But which witnesses correspond to which causal models? The answer to this question will be critical to extend the correspondence we have given so that it can deal with interventions. Different causal models may give rise to the same distribution, yet handle interventions differently.
There are two directions of the correspondence. Given a randomized PSEM M. distributions arising from it are compatible with its dependency structure, and the corresponding witnesses are exactly the distributions in {M} (see Appendix E). In particular, if M is acyclic, there is a unique witness. The converse more interesting: how can we turn a witness into a causal model?
Construction 5. Given a witness (x()) to compatibility with a hypergraph A with disjoint targets, construct a PSEM according to the following (non-determiniistic) procedure. Take V := A 4 :4:44 Ua U (V-V), and P(2)) := p(()). For each X E V. there a unique ax E whose targets Tax contain X. Since fı }=
) + Tax (this is just property (c) in Definition 2), X E Tay must also be a function of Sex and Uax ; take fx to be such a function. More precisely, for each E V(Uax) and s E V(Saa) ) for which jú( jú(Uax
Say s) >> O. there is unique / E V(Tax) ) such that ji,,,, s, 1) > In this case, set [x (u, 8, S..... == { j( = u, Soy =s) = 0, fx (u, .....) can be an arbitrary function of u and s. Let PSEMs (n) denote the set of PSEMs that can result.
It's clear from Construction 5 that PSEMSA (ī) is always nonempty, and is a singleton iff juu,, s) > 0 for all (a, u, 8) E L S.). A witness with this property exists when μ is positive (i.e., =xx=x) > 0 for all x E V(X)), in which case the construction gives a unique causal model. Conversely, we have seen that an acylic model M gives rise a unique witness. So, in the simplest cases, models M with structure A and witnesses j to compatibility with A are equivalent. But there are two important caveats.
1. A causal model M can contain more information than a witness f if some events have probability zero. For instance, could be a point mass single joint outcome of all variables that satisfies the equations of M. But M cannot be reconstructed uniquely from jú because there may be many causal models for which is solution.
'Indeed, Druzdzel and Simon [4] state that "a causal structure does not necessarily imply independences", suggesting that they did not realize that their result could be used to characterize BN independencies.

---

2. A witness ji can contain more information than causal model M if M is cyclic. For example, suppose that M consists of two variables. X and X', and equations fx(X)) X' and Jxx(X) X. In this case, f cannot be reconstructed from M, because M does not contain information about the distribution of X.
These two caveats appear to be very different, but they fit together in a surprisingly elegant way. Proposition 5. If ffX. UA) is a witness for QIM compoataatbbl with A and M PSEM with dependency structure A, then ş E {MB if and only if M E PSEMsA
Equivalently, this means that PSEMs (f), the possible outputs of Construction 5, are precisely the randomized PSEMs of dependency structure A that can give rise to j.. This is already substantial evidence that causal models .M ( are closely related to the QIM-compatibility witness j.. But everything we have seen so far describes only the correspondence in the absence of intervention, a setting in which many causal models are indistinguishable, Yet the correspondence goes deeper; extends to interventions. This claim may seem dubious, as the obvous distinction between observing and doing is fundemental principle of causality. What could witness, which purely probabilistic, have to say about intervention? In randomized PSEM M, we can define an event
dx-(X-x) :=
nn (Xx(Ux, - =x(]), XEX sEV(Pa(X))
where x[X] is the value of X in X.
(1)
This is intuitively the event in which the randomness is such that X regardless of the values of the parent variables. As we now show. conditioning on (X=M(xxx) has the effect of intervention- least as long as the noise variables UA ] are independent of the other exogenous variables U \. UA in addition to one another (e.g., when M is fully randomized).
Theorem 6. Suppose that p is QIM witness for A. that M (U,V,F,P) E PSEMsA (p) is corresponding PSEM, and that the noise variables UA- {Ux]xEv are independent of the other exogenous variables U V.A. For all X S V and x E V(X),, if ((dom((=x))) > O, then
(a) p(V| do)ldoxxxxx) can arise from Mx-xi (b) for all events & S V(V), PRM ([X+xlpp) S p and all three are equal when M =
doo(xx))))))) S PIM ((x+x)pp
(such when M is acyclic).
Theorem shows that the relationship between witnesses and causal models extends to interventions. Even when do (X=x) has probability zero, it is always possible to find nearly equivalent setting where the bounds of the theorem apply. Intervention and conditioning are conceptually very different, so it may seem surprising that conditioning can have the effect of intervention (and also that the Pearl's do(.) notation actually corresponds to an event [9]). We emphasize that the conditioning (on d (X=x)) is the randomness {Ux) } xex and not X itself; intervening X-x is indeed fundamentally different from conditioning on X=x.
QIM-Compatibility and Information Theory
The fact that the dependency structure of (causal) Bayesian network describes the independencies of the distribution induces is fundamental to both causality and probability. It makes explicit the distributional consequences of BN structure. Yet, despite substantial interest [1], generalizing the BN case to more complex (e.g., cyclic) dependency structures remains largely an open problem. In Section 4. we generalize the BN case by providing an information-theorriic constraint, capable of capturing conditional independence, functional dependence, and more, on the distributions that can arise from an arbitrary dependency structure. This connection between causality and information theory has implications for both fields. It grounds the eyclic dependency structures found in causality in concrete constraints on the distributions they represent. At the same time, it allows us to resolve longstanding confusion about structure in information theory, clarifying the meaning of the so-called "interaction information". and recasting standard counterexample substantiate the claim it was intended to oppose. In Section 4.2, we strengthen this connection. Using entropy to measure distance to (in)dependence, we develop a scoring function to measure how far a distribution from being QIM- compatible with a given dependency structure. This function turns out to have an intimate relationship
'More precisely, for all E > 0, there exists some M that differs from A on the probabilities of all causal formulas by at most and distribution je that is c-close to μ. such that j' (do (X=x) > 0.
7

---

with the qualitative PDG scoring fuention IDef, which we use to show that our cetemattion-thhoretie constraints degrade gracefully on "near-compatible" distributions.
We now review the critical information theoretic concepts and their relationships (in)dependence (see Appendix C.1 for a full primer). Conditional entropy Hμ (Y ) measures how far is from satisfying the functional dependency X + Y. Conditional mutual information (Y; Z|X) measures how far is from satisfying the conditional in- dependence Y IL X. Linear combinations of these quantities (for Y.Y. Z S X)) can be viewed as the inner product between coefficient vector v and a 2 information profile of ft. For three variables, the components of this vector are illustrated in Figure 1 (right). It is not hard to see that an arbitrary conjunction of (conditional) (in)dependencies can be expressed as a constraint 4 v 2 O, for some appropriate choice of vector V.
H(YIX.Z)
II( 2)
(IZY
AOy.EAA eix)
HIZIX]
I(X-V:Z)
BAX 21 D(XIY
dimensional vector I, that we will call the
X
Z
Figure 1: Ip-
We now formally introduce the qualitative PDG scoring function IDef. which interprets hypergraph structure A as a function of the form IN VA- This information deficiency, given by
(e) I VA == - HA) + Hp Sa),
(2)
is the difference between the number of bits needed to (independently) specify the randomness in along the hyperarcs A, and the number of bits needed to specify a sample of l according to its own structure (l) + X). While IDef has some nice properties*, it can also behave unintuitively in some cases; for instance, it can be negative. Clearly, it does not measure how close μ is to being structurally compatible with A. in general. Nevertheless, there is still a fundamental relationship between IDef and QIM-compatibility, as we now show.
4.1 A Necessary Condition for QIM-Compatibility
What constraints does QIM-compatibility with A place on a distribution μr? When G is a dag, we have seen that if y -= GAG., then μ must satisfy the independencies of the corresponding Bayesian network (Theorem 1); we have also seen that additional hyperares impose functional dependencies (Theorem 2). But these results apply only when A of very special form. More generally, μ F QA implies that µ can arise from some randomized causal model whose equations have dependency structure A (Propositions 3 and 4). Still, unless A has a particularly special form, is not obvious whether or not this says something about μ.. The primary result of this section is an information- theoretic bound (Theorem 7) that generalizes most the concrete consequences of QIM compaiiiatiyility we have seen so far (Theorems and 2). The result is connection between information theory and causality; it yields an informationn-hhoreee test for complex causal dependency structures, and enables causal notions of structure to dispel misconceptions in information theory.
Theorem 7. If p + OA, then IDe S O.
Theorem 7 applies of for proving that μ # Q.A. Indeed, the negative directions of Theorems 1 and 2 are immediate consequences of it. To illustrate some of its subtler implications, we return to the 3-cycle in Example 4.
all hypergraphs. and subsumes every general-purpose technique we know
Example 5. It is easy to see (e.g., by inspecting Figure 1) that DDefs-yyceed (Y|x) + H₂, + (X|Z) - (XY = - (X; Y; 2). Theorem 7 therefore tells that a distribution lr that is QIM-compatible with the 3-cycle cannot have negative interaction information [x, Z). What does this mean? When I(X;Y; 2)- O, conditioning on one variable causes the other two to share more information than they did before. The most extreme instance is Mwoor the distribution in which two variables are independent and the third is their parity (illustrated on the right). seems intuitively clear that Mzor cannot arise from the 3-cycle, a causal model with only pairwise dependencies. This difficult to prove directly, but is an immediate consequence of Theorem 7.
A
For many, there is an intuition that I(X; Y; Z) < 0 should require a fundementally "3-way" interac- tion between the variables, and should not arise through pairwise interactions alone [10]. This has
'It captures BN independencies and the dependencies of Theorem 2, reduces to maximum entropy for the empty hypergraph, and combines with the quantitative PDG scoring function [23] to capture factor graphs.
8

---

been a source of conflict [26, 16, 15, 3]. because traditional ways of making precise "pairwise inter- actions" (e.g,, maximum entropy subject to pairwise marginal constraints and pairwise factorization) Y:
do not ensure that Y( 2) 2 O. But QIM-compatibility does. One can verify by enumeration that the 3-cycle the most expressive causal structure with no joint dependencies, and we have already proven that QIM-compaibbilit with that hypergraph implies non-negative interaction information. QIM-compatibility has another even more noteworthy clarifying effect on information theory.
There is school of thought that contends that all structural information in (((²) is captured by its information profile In. This position has fallen out of favor in some communities due to standard counterexamples: distributions that have intuitively different structures yet share an information profile [11]. However, with "structure" explicated by compatibility, the prototypical counterexample of this kind suddenly supports the very notion it was meant to challenge, suggesting in an unexpected way that the information profile may yet capture the essence of probabilistic structure.
Example 6. Let A, B, and C be variables with V(A), V(B). V(C) = {0, 1}2. Using independent fair coin flips X1, X2, and X3. define two joint distributions, P and Q, over A, B, C' as follows. Define P by selecting A == X2). B = (X2, X3), and C== (X,, X2 @ X3). Structurally, P and Q appear to be very different. According to P. the first components of the three variables (A, B, C) are independent, yet they are identical according to Q. Moreover, P has only simple pairwise interactions between the variables, while Q has Maor (a clear 3-way interaction) embedded within it. Yet P and Q have identical information profiles (see right): in both cases, each of (A, B, C} is determined by the values of the other two, each pair share one bit of information given the third, and ((A; B;C) C) = O.
+
and C = (X3, X1). Define Q by selecting A (X 1, X2), B ==
This example has been used to argue that multivariate Shannon information does not take into account important structural differences between distributions [11]. We are now in a position to give novel and particularly persuasive response, by appealing to QIM-compatibility. Unsurprisingly, P is compatible with the 3-cycle; it is clearly consists of "2-way" interactions, as each pair of variables shares a bit. But, counterintuitieely the distribution Q is also compatible with the 3-cycle! (The reader encouraged to verify that U1 X3 @ X1, U2 X2. and U3 = X3 serves as witness.) To emphasize: this is despite the fact that Q is just Pzor (which is certainly not compatible with the 3-cycle) together with a seemingly irrelevant random bit X1. By the results of Section 3, this means there is a causal model without joint dependence giving rise to Q despite appearances, Q does not require a 3-way interaction. Indeed, P and Q are QiM-coppatible with precisely the same hypergraphs over {A, B, C)2, suggesting that they don't 't have structural difference after all. A
In light of Example 6. one might reasonably conjecture that the converse of Theorem 7 holds. Unfortunately, it does not (see Appendix C.3); the quantity (D) does not completely determine whether or not μ } O.A. We now pursue a new (entropy- -bsed) scoring function that does. This will allow us to generalize Theorem 7 to distributions that are only compailomp with A.
4.2 A Scoring Function for QIM-Compatibility
Here is function that measures how far a distribution ju is from being QIM-compatible with A.
QIMInCA(R) inf x(
HZ) x(x)=x(x)
Σ (Ua) aEA
Σ U.). aeA
(3)
QIMIne is direct translation of Definition 2 (a-c); it measures the (optimal) quality of extended distribution v as a witness. The infimum restricts the search to v satisfying (a), the first two terms measure v's discrepancy of with (b), and the last term measures v/s discrepancy with (c). Therefore: Proposition 8. QIMInCA(1) (p) 2 O, with equality iff F= OAA.
Although they seem to be very different, QIMicc and IDef turn out to be closely related. In fact, modulo the infimum. QIMInc is a special case of IDef-not for the hypergraph A, but rather for transformed one Att that models the noise variables expleitly. To construct AAT from A, add new nodes 21 = (Ua JaEA and replace each hyperarc
U
S₂
Ta
with the pair of hyperares
S
Ta
Q1

---

Finally, add one additional hyperare 4 - X. (Intuitively, this hyperare creates functional depen- dencies in the spirit of Theorem 2.) With these definitions in place, we can state a theorem that bounds QIMIne above and below with information deficiencies (Theorem 9). The lower bound generalizes Theorem by giving an upper limit on TDe even for distributions y that are not QIM-compatible with A. The upper bound is tight in general, and shows that QIMIICA can be cquivalently defined as minimization over ADef
Theorem 9. (a) If (X, A) is hypergraph, p(X) is a distribution, and ((X is an extension of to additional variables U = (UaJaEA indexed by A, then:
IDef & QIMICCA(H) & Ar
(b) For all p and A, there is a choice of v that achieves the upper bound. That is,
VE AVA, v(X) = v(X) }
QIMicca()) min (Delar()):
The semantics of PDGs are based the idea of measuring (and resolving) inconsistency, which is defined as a minimization over IDef (plus a term that captures relevant concrete probabilistic information). Thus, Theorem 9 (b) tells us that QIM-compatibility (with A) can be captured with qualitative PDG (namely, A!). It follows that our notion of QIM-compatibility can be viewed as a special case of the semanties of PDGs-one that, as we have shown, has a causal interpretation.
5 Discussion and Conclusions
We have shown how directed hypergraphs can be used to represent structural aspects of distributions. Moreover, they can do so in a way that generalizes conditional independencies and functional dependencies and has deep connections to causality and information theory. This notion of QIM- compatibility can be captured with PDGs, and also partially explains the qualitative foundations of these models. Still, many questions remain open.
Perhaps the most important open problem is that of computing whether or not given distribution μ is QIM compatible with directed hypergraph A. We have implemented a rudimentary approach (based on solving problem (3) to calculate QIMIne) that works in practice for small examples, but that approach scales poorly, and its correctness has not yet been proved. Even representing distribution μ over n variables requires 12(2") space in general, and a candidate witness j is even bigger: if all variables are binary, |A| = m, and [Sa], [Ta] < k for all a E A, then a direct implementation of (3) is a non-convex optimization problem with most 2*+*mk(2") variables. Even accepting the (substantial) cost of representing extended distributions, we do not have bound on the time needed to solve the optimization problem. There are more compact ways of representing the joint distributions μ used in practice (by assuming (in)dependencies). but we do not know if such independence assumptions make it easier to determine whether μ }= QA for arbitrary A. But computing IDef can be much easier. We suspect that Theorem 7, a nontrivial condition for QIM coM-oomatibillity that requires only computing TDef (p), could play a critical role designing such inference procedure.
Another major open problem is that of more precisely understanding the implications of QIM- compatibility in cyclic models. We do not yet know, for example, whether the same set of distributions are QIM-compatible with the clockwise and counter-clockwise 3-cycles.
As mentioned in Section 3, our notion of QIM-compatibility has led us to a generalization of a standard causal model (Definition 4). A proper investigation of this novel modeling tool (which we have not attempted in this paper) would include concrete motivating examples, a careful account of interventions and counterfactuals in this general setting, and results situating these causal models among other generalizations of causal models in the literature.
We hope to address these questions in future work.
(1) typically dominated by difficulty of calculating the joint entropy H(z). It can be difficult to compute H()) in some cases (e.g.. for undirected models), but in others (e.g.. for Bayesian Networks or clique trees) the same assumptions that enable a compact representation of μ also make it easy to calculate H(p))
"The complexity of calculating (Def(())
10

---

Acknowledgments and Disclosure of Funding
We would like to thank the reviewers for useful discussion and helpful feedback, such the pointer to Druzdzel and Simon [4], and for asking us to expand on the complexity of inference. Thank you to Matt MacDermott for identifying a bug in prior version of Theorem 6, and to Matthias Georg Mayer for catching several low-level issues with the presentation. The work of Halpern and Richardson was supported in part by AFOSR grant FA238621 14029, MURI grant W91 LANF-19-1-020 W91 INF-22 1-0061, and NSF grant MMMtFF-2319185 S.P. is supported in part by the NSF under Grants Nos. CCF-2122230 and CCF-2312296, a Packard Foundation Fellowship, and a generous gift from Google.
ARO grant
References
[1] C. Baier, C. Dubslaff, H. Hermanns, and N. Käfer. On the foundations of cycles in bayesian networks. In Lecture Notes in Computer Science, pages 343-363. Springer Nature Switzer- land, 2022. doi: (0007/978-3-031-223333 17. URL bttpp::/ddi.orr// 2F978-3 001-0001-22220 2011--2237722211
[2] Beckers, Y. Halpem, and C. Hitchcock. Causal models with constraints, 2023.
[3] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, New York, 1991.
[4] M. J. Druzdzel and Simon. Causality in bayesian belief networks. In Conference on Uncertainty in Artificial Intelligence, 1993. URL https: htap::://app //api.pppppp// wemanticscholee.t.......i org/ CorpusID: IrrpusID:4880431. 14801431.
[5] G. Gallo, G. Longo. S. Pallottino, and S. Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2):177-201, 1993. ISSN 0166-218X. doi: https://doi. org/10. (1000100166001666288899999000800 arricll/pps///66621123390044
URL https:: /www:///wwww//////////////// sciencedirect. http:::///...sccccceerrrtttt com/ stsssciencee
[6] D. Geiger, T. Verma, and J. Pearl. Identifying independence in bayesian networks. Ner- works, 20(5):507-534, 1990. doi: hups://doi.or//100 http:////............00000000000 URL https:
//onlinelibrary. wiley com/ hon/doi//ae /a//////1// /00 1002/eteeet....... 3230200504
[7] Y. Halpern. Axiomatizing causal reasoning. Journal of Artificial Intelligence Research, 12:
317-337, 2000.
[8] D. Heckerman, M. Chickering, C. Meek, R. Rounthwaite, and C. Kadie. Dependency networks for inference, collaborative filtering, and data visualization. Journal of Machine Learning Research, 1(Oct):49-77) 2000.
[9] C. Hitchcock. Causal Models. In E. N. Zalta and U. Nodelman, editors, The Stanford Encyclo- pedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2024 edition, 2024.
[10] R. James. (stumbling blocks) on the road understanding multivariate information theory. Dis- crete Information Theory package documentation, 2018. URL https://dit.... readtheeos. io/en/
stumbl ing. html.
[11] R. G. James and J. P. Crutchfield. Multivariate dependence beyond shannon information. Entropy, 19(10), 2017. ISSN 1099-4300. doi: 10.3390/e11100531 URL https://wwwt http://wwwwmmpp...////
[12] Kobyzev, S. Prince,
A. Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions Pattern Analysis and Machine Intelligence, 43 (11):39443997, nov 2021. doi: 10. 10.1109/tpami.2000 29929499... URL https::/ddo.i.. org/10. 10.
1109%2Ftpami. 2020 2992934.
[13) D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT press, 2009.

---

[14] S. L. Lauritzen, A. P. Dawid, B. N. Larsen, and H.-G. Leimer. Independence proper- ties of directed markov fields. Networks, 2065):91-5505 1990. doi: https://doi.or/// 10.
320200e3.3330000533.. URL https://onnimellirrane wwwpaarrr.lllllly...........eeee wiley. com com/doi/abs/ 10. net. 323.203000
/oo//abs/10.1002 1002/
[15] leonbloy information. Mathematics Stack Exchange, 2015. URL https: http///aaatttatteeeeeeeeeseeeeee stackexchange com/q/1219753,
www.::sttcccccccccccccmoo.a 1/leonbloo)///oy conditioning reduces mutual
(version: 2015-04-04).
[16] D. J. C. MacKay, Information Theory, Inference and Learning Algorithms. Cambridge Univer- sity Press, 2003.
[17] Naumov and B. Nicholls. R.e. axiomatization of conditional independence, 2013.
[18] Pearl, Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2000.
[19] J. Pearl. Causality. Cambridge university press, 2009.
[20] J. Pearl. Causal inference in statistics: An overview. Staristics Surveys, (none)):96 146, 2009. doi: 10.1214/09-SS057 URL aattps:///oi.e org/ 1214/09-810055
[21] J. Pearl and A. Paz. Graphoids: A graphbased logic for reasoning about relevance relations. advances in artificial intelligence, vol. ii, 1987.
[22] O. E. Richardson. Loss the inconsistency of probabilistic dependency graph: Choose your model, not your loss function. AISTATS '22, 151, 2022.
[23] O. E. Richardson and J. Y. Halpern. Probabilistic dependency graphs. In Proc. Thirty-Fifth AAAI Conference on Artificial Intellience (AAAI-21), pages 12174-12181, 2021.
[24] O. E. Richardson, J. Halpern, and C. De Sa. Inference for probabilistic dependency graphs. In Uncertainty in Artificial Intelligence, pages 1741-1751. PMLR, 2023.
[25] E. G. Tabak and E. Vanden-Eijnden. Density estimation by dual ascent of the log-likelihood. Communications in Mathematical Sciences, 8(1::217-233, 2010.
[26] P. L. Williams and R. D. Beer. Nonnegative decomposition of multivariate information, 2010.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: All claims are substantiated with precise theorem statements in Sections 2-4, and their implications are carefully discussed.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: For example, we discuss the inherent limitations of our central notion with respect undirected graphical models, and pose several open problems regarding the distributional implications of cyclic dependency structures that we were not able to solve in this work. We also explain that we only partially characterize the distributions compatible with general dependency structures.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: This is theoretical work and as such we take mathematical precision very seriously.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper is theoretical in nature and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper is theoretical nature and there is no associated data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c
ieguiidde///ddduuiisssss wwteemisssssoooliiiiiioooooooe conoolccy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: gwt////i//////e////g
/ //nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is theoretical and does not involve any training or testing of models.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not have experiments, computational or otherwise.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /nerrps......// wwwuuipp.ccppuuee wctppccic//eeeeccccccccc Cetellic/EEiiiaeeee http:/Etthiiiiiiieeeeeeeeeee caGuidelnes"
Answer: [Yes]
Justification: To the best of our understanding, since this paper focuses on purely theoretical questions regarding graphical languages and the structure of probability distributions, there are no substantive ethical concerns to address.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is best viewed as basic theoretical research and is therefore far from direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not have and have not released any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We use no external assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode.hcoe...c. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
18

---

A Proofs
We begin with de-randomization construction, that will be useful for the proofs.
A.1 From CPDs to Distributions over Functions
Compare two objects:
* cpd pY|]X), and
a distribution g(Y*) over functions g VX - VY.
The latter is significantly larger - if both [X] = |VY| = N, then is N dimensional object, while p is only dimension N2, A choice of distribution (V*x) corresponds unique choice cpd p( ).), according to
pY==y X=x) = q(Y (x) y)
Claim 1.
1. The definition above in fact yields a cpd, i.e., E,p(Y==y\==)) 1 for all
I E VX.
2. This definition of (X) the conditional marginal of any joint distribution ((X,Y,XX) satisfying u(Y = and μ(Y = Y -
Both p and 9 give probabilistic information about Y conditioned on X. But q( contains strictly more information. Not only does it specify the distribution over Y given X=x, but it also contains counter- counter-factual information about the distribution of if X were equal to x', conditioned on the fact that, in reality, X=r.
there natural construction that goes in the opposite direction, intuitively making as many independence assumptions as possible? It turns out there is:
q(Y x9)=
II (LY=g(=) FEVX
Think of x as collection of variables {Y*: E J.X describing the value of the function for each input, so that is a joint distribution over them. This construction simply asks that these variables be independent. Specifying distribution with these independences amounts to choice of "marginal" distribution q(Y") for each x E VX, and hence is essentially a funciton of type VX - AVY, the same as p. In addition, we apply the previous construction, recover p. since:
Q (x) -)
Σ
1[(x)) v II p(==g(>') X=r')
VV
x'EVX
Σ
1k((x) = (Y x=x) II m(==((>') (x=')
-VVVVVY
z'z4
p(Y=y X=r)
Σ
1[g(z) v] Il 1y==g((a') Xx=x))
g:VX -VY
=pYY=y X=r)
Σ
II (eEX(a)
p(Y=g(z)) X=r')
VXX
=p(Y=y|X=))
The final equality holds because the remainder of the terms can be viewed as the probability of selecting any function from {ar) to Y, under an analogous measure; thus, equals This will be a useful construction for us in general.
A.2 Results on (In)dependence
n), .,.,. Yn are sets, and for each i E (1,...n), have a function Js : V(X,) - Y.. Then if X1...., X,, are mutually independent (according joint distribution p), then are fi(X))..... fn (Xn).
Lemma 10. Suppose X1,..., Xn are variables, Yi,...,
19

---

Proof. This is an intuitive fact, but we provide a proof for completeness. Explicitly, mu- tual independence of XI...,, X, means that, for all joint settings x (æ).... F.) we have
u(x1=I1,... X,= xn) = I (X)=aa). So, for any joint setting = (.1...., Un
x Yas have
(f
u((x ((x))(xx>> fxxx((xx)) =
E
u(X1=21, ... In=In)
(iuunnneVe (E((X
f (a))))=
E
E
p(X1=11, ..... xx=In))
1iEVX, h=())==
BVEV (a
E
E
II
TI TIEVI f
BREVE =l (an)==Va
Σ
((X=m)))
Σ
( = Ui)
XIEVX, ((
ZNEVX.
(n(x)==y
II (((().) =
Lemma 11 (properties of determination).
}= A > C, v = A (B,C). 1. If J A + B and v/
2. If J A + B and v }= B > C, then A C.
Proof. v V= X * Y. means there exists function f VAA) + (B) such that v(f(Y) = =X) 1, ie., the event f(A) B occurs with probability 1.
1. Let f V(A) + V(B) and g V(A) + V(C) be such that B)
=
(Ag(A) C). Since both events happen with probability 1, so must the event f(A)
Brg(A) A) = C. Thus the event (J(A), I ()) = (B, C)) occurs with probability Therefore, "F A * C).
2. The same ideas, but faster: have f: V(A) V(B) as before, and g: V(B) - V(C), such that the events ((A) B and (BB = C occur with proability 1. By the same logic, follows that their conjunction holds with probability 1, and hence C = f(g(A)) occurs with probability 1. So v = A + C.
Theorem 1. G is a directed acyclic graph and I(G) consists of the independencies of its corresponding Bayesian network, then p. F GA if and only if μ satisfies IG)..
Proof. Label the vertics of G (N, by natural numbers so that they are topological sort of G-that is, without loss of generality, suppose = [n] = 21, n). and < j whenever i i-j E E. By the definition of Ag. the ares Ag {S: 4 = are also indexed by integers. Finally, write X' = (X1.... .x,) for the variables & corresponding to A over which y is defined
(=) ). Suppose y += Q.Ac. This means there is extension of jaX, 2f) of ((X²) to additional independent variables 2/ = (U,.... U.). such that f + (S,, U.) - for all E [n].
First, we claim that if fi is such witness, then j += (UI...., U2) - (X1, (X) for all & E [n], and so in particular, j 21 = X. This follows from QIM-compatibility s condition (c) and the fact that G is acyclic, by induction. In more detail: The base case of f 0 holds vacuously. Suppose that
20

---

A F (XI,..., Xx) for some k < n. Now, conditon (c) of Definition 2 says - (Sk+1. U++1) -
X1-1 1. Because the varaibles are sorted in topoloical order, the parent variables + are subset of Xa). which are determined by LI by the induction hypothesis; at the same time clearly F (UI..... Uk+1) + Uk+1 as well. So, by two instances of Lemma 11, F ....... Uk+1) - X8+1- Combining with our inductive hypothesis, we find that + 1U Uk+1) - (X1-- by induction, a + (U1...., Ux) - (X1...., Xx) for & E [nl. and particular, f - U - X.
XR+1). So,
With this in mind, we now return to proving that l has the required independencies. It suffices to show that (xx) IT= ((X; St). We do so by showing that, for all [m], p(xx...... Xx)
u(X1...... ( St). By QIM-compatibility witness condition (c), we know that f F x for which the event
(Sp. Ux) + Xx. and so there exists a function fi+ V(Sk) V(U+) + V(Xx)
xx occurs with probability 1. Since f - (UI...., -,,,),-11) - (X...... XR-1). 1). and Uk is independent of (k....,Uk-I)) follows from Lemma 10 that j F (X1,..., Xk-1) 11 Uk.
Ux, =xx
Thus
Σ
,
Xx-1)A(UE = u) 1[x = fa(Sk. u)]
=
we vEV(UL)
=M(X (0(1.--... Xk-1)
Σ
plUk= = u) 1[x SkeSSk; u)]-
REV(U.)
Observe that the quantity on the right, including the sum, is a function of X and Se, but no other variables; let oo( (x) denote this quantity. Because ye is a probability distribution, know that ((X,, Sk) must be the conditional probability of X& given Xi...., Xx-1, and it depends only on the variables Sk. Thus u(X), Xx) = X XR-1)U(Xx Ss).
Therefore (xx) = x(x) factors as required by the BN G. meaning that μ has the independencies specified by G. (See Koller & Friedman Thm 3.2, for instance.)
(=). ). Suppose l satiesfies the independencies of G, meaning that each node is conditionally independent of its non-descendents given its parents. We now repeatedly apply the construction Appendix A.I to construct QIM-compatibility witness. Specifically, for l {1, (1.....n)) let Us be variable whose values V(Ux) == V(Xx)V(Ss are functions from values of Xx 's parents, to values of Xx- Let lf denote the joint variable (Ui...., Un), and observe that a setting g (gl,...,,0) Gn) of l uniquely picks out a value of X, by evaluating each function in order. Let's call this function f: V(2) V(X).
To be more precise, now construct f(g) inductively. The first component must produce is X1, but since X1 has no parents, 91 effectively describes a single value of X1, so we define the first component [(g) [x] to be that value. More generally, assuming that we have already defined the components determine the value of X,; formally, this means defining
among which are the variables S₃ on which X, depends, we can
f(g][ = [((
which, by our inductive assumption, is well-defined. Note that, for all g E v(U) and x E V(X), the function f is characterized by the property
f(g) = x
A
= x[X.].
To quickly verify this: if [g) = x, then in particular, for i E [n]. then x x[X,] = [x,] = y, (x(S.) by the definition above. Conversely, if the right hand side of (4) holds, then we can prove f(g) by induction over our construction of f: f()][X,] = x[X,] for all j < i, then f(g) [x,] =
(:(f() (x({.)) =x x[X,).
Next, we define an unconditional probability over each U2 according to
p (U: = = II
n(X; g(s) S =)), SEV(S.)
which, as verified in Appendix A.1, is indeed a conditional probability, and has the property that (s)(((s)) = r) =(X,=x) =s) for all z E V(X,) and s V(S.). By taking an independent
21

---

combination (tensor product) of each of these unconditional distributions, we obtain joint distribution f(4) = = (U,)). Finally, we extend this distribution a full joint distribution ii,,, via the pushforward of fa((1) through the function f defined by induction above. In this distribution, each X; determined by Ug and S,
By construction, the variables U are mutually independent (for Definition 2(b)), and satisfy (Sk, U2) + X for all k E [n] (Definition 2(c)). It remains only verity that the marginal of j on the variables N' is the original distribution (Definition 2(a)). Here is where we rely on the fact that satisfies the independencies of G, which means that we can factor p(X) as p(x) I (xx; S.).
x(X=xx=
E gEV(L)
p(==g) 8f(x
Σ
1xx=(())
II 1=1
((U-99))
( (n)...)))EV(())
Σ
I (x(xi)))) x[xxi] II p(U,=9))
by (4)
(g) (n (V(())
II
Σ
1 [g(([()) = x[Xi]| MiU = g)
1=1
SEV(UL)
a (199 v(Ui) g(s:) =x:])
Ti = x(X:), S; = x(S:
where
II (s:(ss))a:)) 1=1
p(X; = 3z 1 S =
1 = x).
Therefore, when μ satisfies the independencies of a BN G, is QIM-compatible with Ag.
Before we move on to proving the other results in the paper, we first illustrate how this relatively substantial first half of the proof of Theorem 1 can be dramatically simplified by relying on two information theoretic arguments.
Alternate, information-base proof. (=), ). Let G be a dag. If F AA then by Theorem 7, IDef (n) < 0. In the appendix of [23], it shown that IDef (1) 2 0 with equality iff satisfies the BN's independencies. Thus μ must satisfy the appropriate independencies.
Theorem 2.
(a) и F= X-X if and only if Vn 2 0. = Ct
(b) if = AG dag G, then p F= X- OA if and only if F QAU X-Y.
(4))
(+2) (c) Ia E such that S. 0 and X Ta. then μ F X A CAii CAU X-Y"
Proof. (a). The forward direction is straightforward. Suppose that μ F= QA = The former condition gives us witness v(X', U1) in which U = {Ua)aEA are mutually independent variables indexed by A. that determine their respective edges. "Extend" y in the unique way to additional constant variables UI...., .a....,,,, Un. each of which can only take on one value. We claim that this "extended" distribution v', which we conflate with because is not meaningfully different, a witness to f }= CAU (+n)
X Y Since μ }= X - Y must also be that v }=r X + Y, and follows that T (X, U.) + Y for all i E [l,... ., n). demonstrating that the new requirements of
22

---

v' imposed by Definition 2(c) hold. (The remainder of the requirements for condition (c), namely that v' = (S,. U,) Ta for E A, still hold because v' an extension v, which know has this property.) Finally, since U are mutually independent and each U; is constant (and hence independent of everything), the variables U1' := U {U; ) are also mutually independent. Thus (or, more precisely, isomorphic "extension" of it to additional trivial variables) is witness of = QAU (+n)
The reverse direction is difficult to prove directly, yet it is straightforward application of Theorem Suppose that + QAU (+x), for all n 2 0. By Theorem 7, we know that
X IDef tt (1) (D) n HY(())).
Because Def (u) is bounded below (by log ). it cannot be the that H (Y)x) 0: oth- erwise, the inequality above would not hold for large (specifically, for > log (V() (YIx)) By Gibbs inequailty. H [X) is non-negative, and thus it must be the case that HY [X) 0. Thus = + Y. It is also true that + QA by monotonicity (Proposition 13), which is itself direct application of Theorem
(b). Now A = Ag for some graph G. The forward direction the equivalence is strictly weaker (+x) for all n 2 0, and needed will take
than the one we already proved part (a); we have shown jA F= QAU X-Y only show it for significant shorteut by using Theorem Suppose μt = QAU (+1). this case where A Ac.
1. The reverse direction is what's interesting. As before,
was shown by Richardson and Halper [23] that IDef (H) Z Ü. It follows that
(Theorem 7) 2
0
IDef StR) (H) = (D) (YIX) 2 0,
and thus (Y|X) = O. meaning that μ X + Y as promised. As before, we also have μ + QA by monotonicity.
(c). As in part (b), the forward direction special case of the forward direction of part (a), and it remains only to prove the reverse direction. Equipped with the additional information that
(+2) A { {X}}. suppose that μ - OAu x- By monotonicity, this means μ F QAA and also that
-
X
Let A' denote this hypergraph. Once again by appeal to Theorem 7, we have
that
0 IDef (X, + H(X) 2H, H₂ (Y|x) 2: 0.
It follows that H₂ (Y 0, and thus F X + Y. As mentioned above, we also know that μ += OAA, and thus μ = QA X-+Y as promised.
23

---

A.3 Causality Results of Section 3
Proposition 3. Given graph G and a distribution μ., ia F OA iff there exists fully randomized
PSEM of dependency structure Ag from which ja can arise.
Proof. ( (=), ). Suppose F Q.AG. Thus there exists some witness ()( to this fact, satisfying
conditions (a-c) of Definition 2. Because Ag is partitional, the elements of PSEMS (ā) are ordi- nary (i.e., not generalized) randomized PSEMs. We claim that every M = (M, P) E PSEMs (7) that is a randomized PSEM from which μu can arise, and also has the property that Pas (Y) S (Y) [Uy] for all Y E X.
The hyperares of Ag correspond to the vertices of G, which in turn correspond to the variables in X: thus U= = {Ux]x By property (b) of QIM-compaibbility witnesses (Definition 2), these variables {Ux] are mutually independent according to j.. Furthermore, because M (M, P) Ac)M) mutually independent according to P. By construction, in causal models M E PSEMs, (#) the equation fy can depend only on Sy = Pa) S X and Uy. So, in particular, fy does not depend on Ux for X YY.
know that µ(()) P. and thus the variables in U must be
Altogether, we have shown that M contains exogenous variables {Ux Xxxx that are mutually independent according to P, and that fy does not depend on Ux when X # Y. Thus, M is randomized PSEM.
By condition (a) on QIM-compatibility witnesses (Definition 2), we know that ja(x)= = μ.. By Proposition 5(a), we know that μ E {M}. Together, the previous two sentences mean that j can arise from M.
Finally, as mentioned in the first bullet item, the equation fy in M can depend only on Sy = (Y) and on Uy. Thus Pam S PY) [Uy) for all Y e X.
Under the assumption that μ +=r OAc. we have now shown that there exists a randomized causal model M from which j can arise, with the property that PY S Pac(YY U }Uy} for all Y E X.
(=). Conversely, suppose there is a randomized PSEM M = (M (V, P) with the property that Paw(YY PY) U {Uy} for all Y, from which μ can arise The last clause means there exists some v E {M} such that ((t)= = μ. We claim that this / is a witness to μ += QAg. We already know that condition (a) of being QIM-compatibility witness is satisfied, since v(x) = μ. Condition (b) holds because of the assumption that (Ux |xxxx are mutually independent in the distribution P for a randomized PSEM (and the fact that v/21) P. since v E {MM)). Finally, we must show that (c) for each Y E X, v F Pag (Y)) U {Uy} - Y. Since v E {MB. we know that M's equation holds with probability in v, and so must be the case that v |= PaP(aa))) + Y. Note that, in general, if A C B and A + C, then B = C. By assumption, PaM C Pag (Yr) and thus v += (Y) (Uv} + Y.
Thus satisfies all conditions (a-c) for QIM-compatbillity witness, and hence F AAG.
Proposition 4. μ == O.A iff there exists generalized randomized PSEM with structure A from which μ can arise.
Proof. (-)) ). Suppose F= Q.A, meaning there exists a witness v(('2) with property Defi- nition 2(c), meaning that, for all a E A. there is functional dependence (S., Ua) - T.- Thus, there is some set of functions F with these types that holds with probability according to v. Meanwhile, by Definition 2(b), v(l)) are mutually independent, so defining P. P..U.) := v(U.). we have v(()= = lL A Pa (U.). Together, the previous two conditions (non--eterministicalll)) define generalized randomized PSEM M of shape A for which v E {MM. Finally, by Definition 2(a), we know that y can arise from M.
(=) ). Conversely, suppose there is generalized randomized SEM M of shape A from which (Xt') can arise. Thus, there is some v E {M} whose marginal on X' is p. We claim that this / is also
24

---

a witness that μ F= Q.A. The marginal constraint from Definition 2(a) is clearly satisfied. Condition (b) is immediate as well, because v(()) = II. Pa (Ua). Finally, condition (c) is satisfied. because the equations of M hold with probability 1, ensuring the appropriate functional dependencies.
I
If U(X, MA) is a witness for OlM-compatibility with A and M is a PSEM with dependency structure A, then ji E RMB if and only if M E PSEMsa(i).
Proposition 5.
Proof. (a) is straightforward. Suppose M E PSEMs(v). By construction, the equations of M reflect functional dependencies in is and hence hold with probability 1. Furthermore, the distribution P(4) in all M E PSEMs(v) is equal to v(f). These two facts, demonstrate that v satisfies the two constraints required for membership in I {.M.
(b). We do the two directions separately. First, suppose M E PSE We have already shown (in part (a)) that E {.M.. The construction of PSEMs(() depends on the hypergraph A (even if the dependence not explicitly clear from our notation) such a way that fx does not depend on any variables beyond Ua and Sux Thus, (a S Sux U [Uax): J.
Conversely, suppose M = (K, JF) is PSEM satisfying V/ E {MM and (XM S Sax o. We would like to show that M E PSEMs(v). Because v E {MM. we know that the distribution P(4) over the exogenous variables in the PSEM M is equal to v1(4), matching the first part of our construction. What remains is to show that the equations F are consistent with our transformation. Choose any X E X. Because A is subpartitional, there is a unique ax E such that X E Tax Now choose any values s E V(S.x) ) and E V(Uxx), ). If v(s, u) > O, then we know there is a unique value of x E V(X) such that v(s, u, x) > Since M's equation for X, fx. depends only on s and u. and holds with probability 1, we know that /x(s, u) = L, as required. On the other hand, if v(s, u) = 0, then any choice of fx u) is consistent with our procedure. Since this true for all X, and all possible inputs to the equation fx. conclude that the equations FF can arise from the procedure described the main text, and therefore M E PSEMs(v).
Theorem 6. Suppose that jı is a QIM witness for A. that M (U,VFF PSEMSA (p) is corresponding PSEM, and that the noise variables UA {Ux]XEV are independent of the other exogenous variables Ut A.d.. For all X C V and x E V(X), if ((dom((=x)) > 0, then
(a) [x)]dox(xXx)) can arise from Mx-xi
(b) for all events & S V(V), PIM (Xxxxlp) S p1p dom(X=xx) S PIM ((x)x) and all three are equal when M =u * V (such when M is acyclic).
Proof. (part a). Because we have assumed piddo (oo(ddm(xxx))) > 0, the conditional distribution
II 1 [ [Ux. (Ux, = x[X]]] / [((oo(X=x))) XEX
p | do = x),
defined. By assumption, M PSEMs(a) and jú is a witness to the fact that j F= OA. Thus, by Proposition 5, we know that j E {M}. So in particular, all equations of . hold for all joint settings (u, v) E V(U V) in the support of p. But the support of the conditional distribution (X=x) is a subset of the support of so all equations of M also hold in the conditioned distribution. Furthermore, the event do ( (X=x) is the event in which, for all X E X, the variable x[X]. Thus the equations corresponding X
Ux takes value such that fx (..., Ux... also hold with probability in f dX
This shows that all equations of Mx hold with probability 1 in p dX=x). However, the marginal distribution jilld (X=x) over 24 is typically not equal to P(U) all, we have collapsed distribution of the variables Ux == {Ux X E X). Clearly, j dX=x(xxx) g {Mx+x} }. However, as we now show, there exists a different distribution pt E [Mxxx] such that R'(V) v(V) (X=x).
'When the probability of some combination of source variables is zero, there is typically more than one choice of functions that holds with probability 1; the choice of functions is essentially the choice of M E PSEMs(P).
25

---

Uo = Ux. We can define jí' according to
i'V Mo) == jiV (o
The distribution zí' satisfies three critical properties:
1. By construction, the marginal jt' on V ('()) = p(V) do.m(xxx))
2. At the same time, the marginal of ji' on exogenous variables is
(1())= pt (1xx
-
V(C) pl (VV, dv
- plv, do,w(X-x))((x)x
[definition of p
((( dX-(X=x)) =((Ux) dom dX-(X=x))
[because p(()) P(4), since j E {MB
since dx-x(Xxx) depends only on Uxx while Ux and Uz are indepen- dent in z (by the witness condition)..
-P(4))
P((
same reason as above
Finally, pí satisfies all equations of Mx-xx satisfies the equations for the variables X because X = holds with probability 1. At the same time, the equations of Mx-x corresponding to other variables, say fx for E \ X, also hold with probability one. This is because the marginal z z'UZ, V) is shared with the distribution f (X=x), and that distribution satisfies these equations. (It suffices to show that they share this particular marginal because the equations for Z do not depend on mxx.)
Together, properties 2 and 3 show that j E {Mx+x] while property 1 shows that BiV do can arise from Mxex This establishes part (a).
(part b). We will again make use of the distribution ní' defined in part (a), and its three critical properties listed above. Given setting V(U) of the exogenous variables, let
(( (WEVM)
v = fx
Fx-x(u) =
(Y),))
VY E
denote the set of joint settings of endogenous variables that consistent with the equations of Mx+x-
If E V(U) is such that
(M, u) - X
= u) to E Fx) w
Fx-x(u) C ip
then é holds at all points that satisfy the equations Mx.x. So, since şí' is supported only on such points (property 3), it must be that (T) 1. By property 1, p (vp piy dX=x(X
Furthermore, if (sp) > 0, then there must exist some w Fx-x (u) satisfying s, and thus (M, u) + (X+x)yp Putting both of these observations together, and with bit more care to the
26

---

symbolic manipulation, we find that:
Pr M
Pr((++x|p) = P(lu E v(U) : (M, u) + [X+x|pp)
E ((x)1(FFxx r
uEVIL)
Σ P(u) u)
= = iál ddon(x-x)
VEV()))
Σ (x=x uEVR))
= P((u V(u): : (M, u) J (x+x)+))
Pr((X+xxpp)
desired.
Finally, if } U + V. then Fx-x(u) (u) is a singleton for all u, and hence yp holding for all w WE Fxrx and for some E Fxex are equivalent. So, in this case,
(M,u) == X
(M, u) F (X+x)
and thus the probability of both formulas are the same and must also equal ما | dom (X-x) which we have shown lies between them.
A.4 Information Theoretic Results of Section 4
To prove Theorem 7 and Theorem 9(a), we will need the following Lemma.
Lemma 12. Consider a set of variables Y = (Y,...., Yah, and another (set of) variable(s) X. Every joint distribution p(X, Y) over the values of X and Y satisfies
(x;;Y) & IX;;; Y) + Σ H2 - -Y,
Proof. Since there is only joint distribution in scope, omit the subscript μ4, writing I(-) instead of [-(- and H(-) instead of H-)(), in the body of this proof. The following fact will also be very useful:
-),,nn
T(A; B, C) I I(A: I(A;
(the chain rule for mutual information).
(5)
We prove this by induction on n. In the base case (n = 1), we must show that I(X;Y) - I(X;Y)
+
H(Y) H(Y), which is an obvious tautology. Now, suppose inductively that
Σ 1(x; Y.) s 1(X; Y + Σ H(Y)) - H(Y
(IH₂)
i=1
for some h < n, where YIA (Y,,..,,Y, YR). We now prove that the analogue for h: + also holds. Some calculation reveals:
I(X; Yet1)
= I(x; Y1s+1) I(X; Yis (Y41)
by MI chain rule (5)
< 1(X; Y18+1)
since 1(X; YIck (Y41) 2
= =I(X; Yeer Y + +(Y l2: V&+1)
by MI chain rule (5)
= -( - -1-1 -I(XXY
Y1s41) (((4))) + H(Y++1) - H(Y +H(+.))
)
[
left: one more MI chain rule (5); right: defn of mutual information
Observe: adding this inequality to our inductive hypothesis (IHg) yields (lH&+1)) ! So, by induction, the lemma holds for all k.
27

---

Theorem 7. yf + Q.A, then (M) = O.
Proof. Suppose that f F Q.A, meaning that there is witness v(X, that extends μe, and has properties (a-c) of Definition 2. For each hyperarc a, since v -= (S., Ua) + Tos we have (T
Sa, Ua) 0, and
(Ta Sa) HT Ua) + (Ta;Ua S.) (Taa: Sa).
Thus, we compute
Σ 4EA
HT Sa) Σ (Ua:Ta S 1.))
aeA
Σ1 Lu Ta, Sa) - LU Sa)
by MI chain rule (5)
aEA
(Ua;;aa, Sa)
since (, : S.)
aEAA
Σ LU(a;
since X' - (S Ta)
aEAA
(XZU)) Σ (v,( H2,(1)
by Lemma 12
aEA
since UI are independent (per condition (b) of Definition 2)
(xx;))
$ = H
(per condition (a) Definition 2)
Thus, (De) S0.
Proposition 8. QIMIncA(R) 2 0, with equality iff p - OA
Proof. The first term in the definition of QIMinc be written
log m())
HT) + ΣH.(U.)
II. v(U.)
aEA
and is therefore the relative entropy between v(2)) and the independent product distribution ILe P(U,). Thus, it is non-negative. The remaining terms of QIMInc are all conditional entropies, and hence non-negative well. Thus QIMinc(()) 0.
Now, suppose 4 s2-comaptible with A, i.e., there exists some v(M, X) such that (a) v(X)= - (x)). (b) H. (T, U,) = 0, and (d) {Ua} ) are mutually independent. Then clearly satisfies the condition under the infemum, every H, (Ta SS, Ua) is zero. is also immediate that the final term zero well, because it equals D(v(U) II. p(Ua)), and v(U)) II. v(Ua), per the definition of mutual independence. Thus, // witnesses that QIMInC(A.) = 0.
Conversely, suppose QIM/RC(A.A) = 0. Because the feasible set is closed and bounded, as is the function, the infemum achieved by some joint distribution v(X', with marginal (xX'). In this distribution v, we know that every (T, U.) 0 and Dvv(() || II. v(U.) = 0- because any of these terms were positive, then the result would be positive as well. So satisfies (a) and (b) by definition. And, because relative entropy is zero iff its arguments are identical we have v(l) = II. v(Ua), so the Ug 's are mutually independent, and v satisfies (d) as well.
Theorem 9.
(a) (X, A) a hypergraph, p(X) is distribution, and v(X,2) is an extension of to additional variables U = (oa) indexed by A, then:
IDefa(H) QIMInCA(H) S IDef (v).
28

---

(b) For all μ and A, there is choice of v that achieves the upper bound. That is,
E A (V v(X) = v(x) }
a = min IDefar(v):
Proof. Part (a). The left hand side of the theorem (IDef (v) - QIMInc (H)) is a strengthening of the argument used to prove Theorem Specifically, let v² be a minimizer of the optimization problem defining QIM/cc We calculate
QIMInc (Defalu)
Σ (To San Ua) Hv) + Σ (U.)(U))) aeA
) (Ta Sa) H,)
-
-(I
aEA
aEA
Hy- (Ta Sa, Un)
H (Ta So)) + +Hp(2) -Hp- +
Σ Hu-(Uu)
aEA
acA
Σ a
Ly (TaiUs Sa))
+ Hx) H (1) + Σ Hp,(
aEA
The argument given in the first five lines of the proof of Theorem 7, gives us particularly convenient bound for the first group of terms on the left:
Σ L. (Ua: Ta S.) S -.- (Z;2))+ + Σ HU,) - H. (2).
REA
aEA
Substituting this into our previous expression, we have:
(MMIICA(M) (p)
2 - -- (2;;1) +
Σ
H. Hb.(Uu) - H.- (40) + H,((2) - H2) + Σ Ho- (Ua)
aEA
aEA
= -
20.
The final inequality holds because of our assumption that the marginal (x( equals μ(X). Thus, QIMIne 2 (H)) as proimised.
We now turn the right hand inequality, and part (b) of the theorem. Recall that D² is defined to be minimizer of the optimization problem defining QIMhnc. For the right inequality (QTMfic S
At (v)) of part (a), observe that
IDef (v) = (X, + Σ (U.) +
Σ
HT, U.) + (X
aEd
aEA
(y Σ HH,(Uu))
Σ
H (Ta U.)
aEA
aEA
2 H,,
Hy. (4) + Σ H Hu)) + Σ
H, (Ta S. U.)
aEA
aEA
QIMIne(u).
This proves the right hand side of the inequality of part (a). Moreover, because the one inequality holds with equality when n² is minimizer of this quantity (subject having marginal ((X)) we have shown part (b) as well.
B Monotonicity and Undirected Graphical Models
The fact that (quantitative) PDG inconsistency is monotonic is powerful reasoning principle that can he used to prove many important inequalities [22]. In this section, we develop a related principle for QIM-compatibility Here is direct but not very useful analague: if AA C A' and μ += Q'A', conclude µ }== QAA. After all, if μu is consistent with a set of independent causal mechanisms, then surely it is consistent with a causal picture in which only subset of those mechanisms are present and independent. There is sense in which BNs and MRFs are also monotonic, but in the opposite direction: adding edges to a graph results weaker independence statement. We will soon see why.
29

---

Since we use directed hypergraphs, there is actually finer notion of monotonicity play. Inputs and ouputs play opposite roles, and they are naturally monotonic in opposite directions. If there is an obvious way to regard an element of B as an element of B' (abbreviated B - B'), and A' A, then function f A - can be regarded as one of type A' + B'. This is depicted to the right. The same principile applies in our setting. If X and Z are sets of variables and X C ZZ then V(Z)+ (XX), by restriction. It follows, for example, that any mechanism by which X determines (Y, Y") can be viewed mechanism by which (X, X') determines Y. The general phenomenon is captured by the following.
A 1 B J \
A' --> B'
Definition 6. If A = {{S"T] Jas A' (S*TT"" Ja', and there is an injective map A' such that TV C T((a) and S 2 ((()) for all a E A', then A' is a weakening of A (written A~+A'). 0
Proposition 13. If
A' and μ F= QA, then μl = Q.A'.
Proposition 13 is strictly stronger than the simple monotonicity mentioned at the beginning of the section, because a hyperare with no targets is vacuous, so removing all targets of hyperarc is equivalent to deleting it. It also explains why BNs and MRFs are arguably anti-monotonic: adding X ++Y Y to a graph G means adding X the sources the hyperarc whose target is Y, in Ag.
As mentioned in the main body the paper, the far more important consequence this result that helps begin to understand what QIM- compatibility means for cyclic hypergraphs. For the reader's convenience, we now restate the examples in the main text, which are really about monotonicity.
Example 3. Every (x(,, Y) is compatible with X 7 y. This is because this cycle is weaker than hypergraph that can already represent any distribution, i.e., - X
X 7 Y
A.
Example 4. What pf Y, Z) compatible with the 3-cycle shown, on the right? By monotonicity, among them must be all distributions consistent with linear chain -X-Y- Thus, any distribution in which two variables are conditionally indepen- dent given the third is compatible with the 3-cycle. Are there any distributions that are not compatible with this hypergraph? It is not obvious. We return to this in Section 4. A
K
X
Z
Because QIM-compatibility applies to cyclic structures, one might wonder if it also captures the independencies of undirected models. Undirected edges A-B are monly identified with (cylic) pair of directed edges {A-B, A->A. as we have implicitly done in defining Ag. In this way, undirected graphs, too, naturally cor- respond to directed hypergraphs. For example, G = A-B-C corresponds to the hypergraph Ag shown on the left. Compatibility with Ag. however, does not coincide with any of the standard Markov properties corresponding to G [13]. This may appear to be flaw in Definition 2 (QIM-comatiiilltt).. but is unavoidable. While both BNs and MRFs are monotonic, it is impossible to capture both classes with monotonic definition.
Theorem 14. It is possible to define relation _ between distributions μ and directed hypergraphs A satisfying any two, but not all three, of the following.
(monotonicity) If ft = A and A A', then μ - A'.
(positive BN capture) If μ satisfies the independencies I(G) of a dag G, then μ F Ag.
(negative MRF capture) If j Ag for an undirected directed graph G, then j has one of the Markov properties with respect to G.
The proof is a direct and casy-to-visualize application of monotonicity (Proposition 13). Assume montonicity and positive BN capture. Let pmoor (A, B, C)) be the joint distribution in which A and C are independent fair coins, and B A @ C is their parity. We then have:
Mxzor
N = AA-B-C. But Pizor | AALCB A
L
A
C
C
We emphasize that Theorem 14 has implications for the qualitative semantics of any graphical model (even if one were to reject the definition ciM-coopatibllity.. We now look into the implications for some lesser-known graphical models, which may appear not to comply with Theorem 14.
Dependecny Networks To readers familiar with dependency networks (DNs) [8], Theorem 14 may raise some conceptual issues. When G is undirected graph, Ag is the structure of consistent DN.
30

---

The semantics of such a DN, which intuitively describe an independent mechanism on each hyperarc, coincide with the MRFs for G (at least for positive distributions). In more detail, DN semantics are given by the fixed point of a markov chain that repeatedly generates independent samples along the hyperares of Ag for some (typically eyclic) directed graph G. The precise definition requires an order in which to do sampling. Although this choice doesn't 't matter for the "consistent DNs" that represent MRFs, it does in general. With fixed sampling order, the DN monotonic and captures MRFs, but can represent only BNs for which that order is a topological sort.
C Information Theory, PDGs, and QIM-Compatibilit
C.1 More Detailed Primer on Information Theory
We now expand on the fundemental information quantities introduced at the beginning of Section 4. Let ju be a probability distribution, and be X, Y, Z be (sets of) discrete random variables. The entropy of X is the uncertainty in X, when it is distributed according μ., measured by the number of bits of information needed (in expectation) needed to determine it, if the distribution μ is known. is given by
Hx( = E m(X=x) log
1
E-looog(a P
m(X=x)
zEV(X)
and few very important properties; chief among them. H (X) is non-negative, and equal to zero iff X is a constant according to μ. The "joint entropy" H(X, Y) is just the entropy of the combined variable (X, Y) whose values are pairs (z, y) for E V(X), entropy of the variable X UU when and are themselves sets of variables.
V(Y); this is the same as the
The conditional entropy of Y given X measures the uncertainty present in Y if one knows the value of X (think: the information Y but not X), and equivalently defined as any of the following three quantities:
(Y E log 1/(0|]]] (X, (x)
E zvu((X
H (X)
The mutual information Y); and its conditional variant I(X; YI), are given, respectively, by
(x(YY) = E log 1(X, 8) and T(X; 2) = log p(X, Z)n(Z) p(X, 2) pY, Z)
((X) (Y))
The former is non non-negative and equal to zero iff μ ト X Y, and the latter is non-negative and equal to zero iff μ + X IL Y Z. All of these quantities are purely "structural" or "qualitative" in the sense that they are invariant to relabelings of values, and
Just as conditional entropy can be written as a linear combination of unconditional entropies, so too conditional mutual information be written informations: I(X; Z| = T(X; (Y, Z)) - I(X; Z). Thus conditional quantities are easily derived from the unconditional ones. But the same time, the unconditional versions are clearly special cases of the conditional ones; for example, (X, ) is clearly the special case of H(X) Z) when Z constant (e.g., Z 0). Furthermore, entropy and mutual information are also interdefinable and generated by linear combinations of one another. It is easy to verify that I, Y) = (x) - (Y) - H(X, Y) and (X: information is derived from entropy. Yet on the other hand, (Y; = H (Y) and (Y; Y|X) = (Y|X) thus entropy a special case of mutual information.
linear combination of unconditional mutual
(X]Z) + H. ZY H(X, Y|Z), and thus mutual
C.2 Structural Deficiency: More Motivation, and Examples
To build intuition for IDef, which characterizes our bounds in Section 4, we now visualize the vector VA for various example hypergraphs.
Subfigures 2a, 2b, and 2c show how adding hyperarcs makes distriutions more determin- istic. When the empty hypergraph, IDef reduces to negative entropy, and so prefers distributions that are "maximally uncertain" (e.g., Subfigures 2a and 2d). For this empty but all distributions f have negative IDef ((z) S 0. the definition of IDef. each hyperare X + Y is compiled to "cost" H(Y (X) for uncertainty in Y given X. One see this
31

---

X
X
Y
(a)
(b)
X
X
X
Y
(h)
X
X
(c)
(e)
(g)
X
Y
Y
Y
Y
X
X
Z
Z
X
7
kk)
(
(m)
Figure 2: Illustrations of the structural deficiency IDef A underneath drawn underneath their associ- ated hypergraphs {G Each circle represents variable; area in the intersection of circles {C₃} } but outside of circles {D₂} corresponds to information that shared between all Cj 's. but not in any DA. Variation of a candidate distribution in green area makes its qualitative fit better (according to IDef), while variation in a red area makes its qualitative worse; grey neutral. Only the boxed structures in blue, whose IDef can be seen measuring distance to particular set of (conditional) independencies, are expressible as BNs.
visually in Figure 2 as red crescent that's added to the information profile as we move from 2d to 2e 2f.
Some hypergraphs (see Figures 2b and 2h) are indiscriminate, in the sense that every distribution gets the same score (of zero, because a point mass 5 always has SDef ر (8) = 0). Such graph has structure such that any distribution can be precisely encoded by the process in (b). As shown here and also in Richardson and Halper [23], IDef can also indicate independencies and conditional independencies, illustrated respectively in Subfigures 2g and 2i.
For more complex structures, structural information deficiency IDef can represent more than independence and dependence. The cyclic structures in Examples 3 and 4, correspond to the structural deficiencies pictured in Subfigures 2f and 2j. respectively, which are functions that encourage shared information between the three variables.
C.3 Coumter-Examples to the Converse of Theorem
In light of Example 6 and its connections to IDef through Theorem 7, one might hope this criterion is not just bound, but precise characterization of the distributions that are QIM-compatible with the 3-cycle. Unfortunately, it does not, and the converse Theorem false.
Example 7. Suppose μxX, Y, 2) = Unif(X, Z (X and A = {+ x, YJ. where all variables are binary. Then IDef (m) O, but X and Y are independent.
A
Here is another counter-example, of very different kind.
Example Suppose A, B, C are binary variables. can be shown by enumeration (see appendix) that no distribution supported on seven of the eight possible joint settings of of ((A, B, C) can be QIM-compatible with the 3-cycle Aso. Yet it easy to find examples of such distributions ya that have positive interaction information I(A; B; C),, and thus IDef (Aso) < 0 for such distributions. A
32

---

D QIM-Compatibility Constructions and Counterexamples
We now give counterexample simpler previously conjectured strengthening of Theorem in which part (a) is an if-aandonly-iff. This may be surprising. In the unconditional case, it is true that, two ares (+x,, 3 precisely encode that X is a constant, as illustrated by Example 2. The following, slightly more general result, is an immediate correlary of Theorem 2(c).
Proposition 15. (-U 3x} if and only if T QA and μl } X
One can be forgiven for imagining that the conditional case would be analogous- that QIM- compatibility with a hypergraph that has two parallel ares from X to Y would imply that Y is a function of X. But this is not the case. Furthermore, our counterexample also shows that neither of the two properties we consider in the main text (requiring that A is partitional, or that the QIM- compatibility with μ is even) are enough to ensure this. That is, there are partitional graphs A such that J j A but / QA (X-,, J.
Example 9. We will construct a witness of SIM-compatibility for the hypergraph
A
X
Y
in which Y is not a function of X, which for n = will disprove the analogue of Theorem 2 for the partitional context A'' equal to the 2-cycle.
Let = (Uo, UI...., Un) be a vector of n mutually independent random coins, and is one more independent random coin. For notational convenience, define the random vector U == (Uo....: Un) consisting of all variables U, except for Un- Then, define variables X and Y according to:
X (A U1..... A Un. Uo @ U1. Up U2,..., Up + Un)
(A a U, Uo ① U)
y = (A, Uo @ U) = (A, Un @ U1, Up @ U2.... Un @ Un),
where and the operation Z @ V is element-wiss xor (or addition in F3), after implicitly converting the scalar Z to a vector by taking n copies of Call the resulting distribution v(X, Y,U).
It now show that witnesses that its marginal on X, Y is QIM-compatible with A, which is straightforward.
(b) U are mutually independent by assumption;
(c.0) Y (A, B) and Uo determine X according to:
g(A, B, U)) (A @ Ug + B, B)
(A Uo @ Uo U, Uo U) U) =
since Uo U
(A @ U.U @
(c.l-n) for [L, (I....,,)) n). U, and X (V, B) together determine Y according
A(V, B, U.) = (V: @ U, B) (A t @ U. Un @ U) Y.
In addition, this distribution v(U, X, Y) satisfies condition
(d) v(X,Y Y ( [gg Y, Ub) = X - L[),(X, YJ. since, for all joint settings of Ut there are two possible values of X,Y), corresponding to the two values of A, and both happen with probability }
Thus, have constructed distribution that witnessing the fact that p(X, Y) A. A.
Yet, observe that alone does not determine in this distribution, because alone is not enough to determine A (without also knowing some U.).
33

---

For those who are interested, observe that the bound of Theorem 7 tells that we must satisfy
2 (Defa()) = - + H X) + H Y) =x,,(Xx;) + (n H) X)
Indeed, this distribution has information profile
H(X X Y) bit, I(X; Y) = n bits,
H(Y X) = 1 bit,
and so IDef (1) bit. Intuitively, this one missing bit corresponds the value of A that not determined by the structure of A.
A
E From Causal Models to Witnesses
We now return to the "easy" direction of the correspondence between QIM-compatibillty witnesses and causal models, mentioned at the beginning of Section 3.2. Given (generalized) randomized PSEM M, we now show that distributions v E {M}. are QIM-compatibiliy witness showing that the marginals of are QIM-compatible with the hypergraph AM. More formally:
Proposition 16. If = (M-(u, F),, P) is a randomized PSEM, then every E {M} witnesses the QiM-compatbility of its marginal on ils exogenous variables, with the dependency structure of M. That is. for all {M} and y cuUv, v()) } QAM-
The proof straightforward: by definition, if E H.M,, then must satisfy the equations, and automatically fulfills condition (c). Condition (a) is also satisfied trivially, by assumption: the distribution we're considering is defined to be a marginal of v. Finally, (b) also satisfied by construction: assumed that MA (Ua) are independent.
34


Reviews:
[{"review_id": "HptzH1nTIH", "reviewer": "Reviewer_91DJ", "summary": "This paper establishes a notion of \"QIM compatibility\" between the functional dependences and the joint distribution through the directed hypergraph. The functional dependence is a general notion of dependences containing conditional independences.", "questions": "1. My understanding of QIM compatibility from Definition 2 is that the hypergraph $\\mathcal{A}$ is QIM-compatible if $\\mathcal{A}$ satisfies the causal Markov condition with respect to the distribution. Then, there must be a graph capturing this independence information, by a graphoid theory. Then, how the notion of QIM compatibility can be differentiated with the existing graphoid theory? \n\n2. A semi-Markovian causal graph (an acyclic directed mixed graph, ADMG) is known to carry a set of conditional independences and a set  of _functional independence_. For example, consider a graph G = {W -> R -> X -> Y, W<-> X, W<-> Y} (which is known to be a _Napkin graph_ (Book of Why, Pearl)). In this graph, no conditional independences exist. However, it's known that the functional $Q[Y]:= \\frac{\\sum_{w}P(y,x \\mid r,w)P(w)}{\\sum_{w}P(x \\mid r,w)P(w) }$ (which is an identification estimand of $P(y | do(x))$) is known to be independent of the choice of $r$. This type of functional independence is called the _Verma's constrains_. This type of constraints doesn't show up explicitly in the ADMG. Then, do you think this type of constraints (more generally, a set of conditional independence and Verma's constraints) can be shown simultaneously in the directed hypergraph?", "limitations": "1. I think this paper only considered the case where the unmeasured noises are independent. I think this is a strong assumption.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I want to state that my understanding of this paper is partial, given that I have a limited knowledge and understanding on the computational logic theory where this paper might reside in. I am from causal inference field. \n\n---\n1. This paper is technically precise. All mathematical terminologies are carefully chosen, and the degree of ambiguity is minimized. \n2. I think this theory has a lot of potentials in providing a graphical tool for describing functional dependences. Despite the wide usage of the causal graph, it's known that the graph is only suitable for expressing conditional independences. Even if the causal graph also carries functional independences (called \"Verma's constraints\" described exemplified in Question section), such constraints are not explicitly shown in the graph. I think the proposed framework has a potential of explicitly revealing such hidden constraints from the graph.", "weaknesses": "I want to state that my understanding of this paper is partial, given that I have a limited knowledge and understanding on the computational logic theory where this paper might reside in. I am from causal inference field. \n\n---\n\n__Lack of preliminaries__\n\nI felt difficulty in digesting this paper.  Some knowledge on probabilistic dependency graph (PDG) is required to understand this paper, but examples are limited to capture what functional independences are captured from this PDG. Also, a natural question is then the difference between the DAG and the PDG. Such differences need to be highlighted to motivate this work and provide a clear distinction on the notion of PDG. \n\n__Lack of motivations__\n\nI think a real-world example of functional independences that are not captured by the conditional independence terminology is required. Even if there are some examples (such as a non-random coin in line 134) exist to capture the distinction between the causal graph and the PDG, this example is somewhat made-up and can be addressed in the existing framework, since in causal graph, such two non-random coins are considered as one variable. I believe this proposed work is providing a new _paradigm_ compared to existing causal graphical model to capture more general functional dependencies. Then, there should be more examples that readers would feel the incapability of causal graphs. \n\n\n__Weak literature review__\nI wanted to read the history of development of the notion of QIM in the paper but couldn't find. What is the limitation of previous papers, and what are the distinction of this paper compared to them?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n**RESPONSES TO QUESTIONS**\n\n1. While your understanding is not far off at a high level, there is an important wrinkle in your restatement of Definition 2: what exactly do you mean by “the causal Markov condition (for a hypergraph) with respect to a distribution?”  There is no standard answer to this question. In a way, the primary contribution of this paper is to propose a (novel) principled way of making this precise.  Yet to do so, we have had to step beyond the purview of graphoid theory.  As mentioned in the introduction, the standard theory of graphoids cannot even describe functional dependencies, let alone the complex information-theoretic constraints implied by QIM compatibility in general (e.g., Theorem 7). We reiterate that QIM-compatibility is about more than just independence; for a very concrete illustration, see Example 2. \n\n2. This is an interesting idea. To model an ADMG with a directed hypergraph, it seems the appropriate thing to do would be to explicitly include the implied confounding variables.  Our (brief) investigation has not yet turned up anything interesting about these Verma’s constraints, and it is not yet clear to us what relationship they may have to the hypergraph.  But going forwards, we will keep an eye out for these properties. Thanks again for the suggestion!\n\n**ADDRESSING WEAKNESSES AND LIMITATIONS**\n\n**Preliminaries.** QIM compatibility is an original and self-contained concept. Although our concept of QIM compatibility turns out to have subtle connections to existing work on probabilistic dependency graphs (PDGs), as we show in section 4, we maintain that no prior knowledge of PDGs is necessary to understand any part of this paper.  We hope that some careful rewording of the paragraphs in the introduction and in section 4 will clarify this. \n\n**Motivations.** The reviewer makes a good point: many of our examples (such as the non-random coin on example on line 134) can be captured with the existing framework for causal modeling. Recall, however, that our goal is to develop a unified graphical language for just the qualitative aspects of causality (such as independence and dependence). In that regard, Example 2 demonstrates a lack of expressive power of qualitative (causal) Bayesian Networks: they cannot represent determinism. \n\nIndeed, there are two standard ways that one can interpret a graph as specifying the qualitative structure of a causal model. Either (1) each variable $X$ is associated with a function $f_X(\\mathrm{Pa}(X))$ that determines the value of $X$ based on the value of its parent variables, or (2) the function $f_X$ also takes as input an additional independent noise (this is Pearl’s definition; we call it a randomized causal model). Quantitatively, the two are equally expressive, because noise can be modeled explicitly as variables, and, conversely, one can ignore the noise term.  But qualitatively, these two standard models are different, and neither can express both dependence and independence. Graphs with interpretation (1) cannot articulate independencies, while graphs with interpretation (2) cannot describe dependencies or determinism. Our framework can do both, even within a single model. It can also capture subtler qualitative phenomena, as we explore in Section 4. \n\n**Literature Review.** As far as we are aware, the definition of qualitatively independent mechanisms (QIM), in the general form made precise by Definition 2, is entirely new.  Of course, people have long studied the special case of hypergraphs that arise from DAGs (which, by Theorem 1, amounts to Bayesian Network independencies); we have credited Pearl (Causality, 2009) for the intuition for DAGs, on which our more general notion is based.  The other key point of contact with the literature is probabilistic dependency graphs (PDGs).  The key difference between the hypergraphs we work with here and PDGs is in the semantics they give to qualitative information (and the fact that the hypergraphs don’t deal with quantitative information at all, whereas PDGs do).  PDGs give semantics to qualitative information using an information-theoretic scoring function (IDef); we do so using QIM-compatibility (Definition 2).   But, as we show (Theorems 7 and 8), there are deep connections between the two.\n\n**Independence of Noise Variables.** It is indeed a strong assumption to assume that noise variables are independent, but it is one that is commonly made both in theory (see Pearl’s definition of a causal model in Causality (2009)) and in practice.  Moreover, perhaps counter-intuitively, it is still possible to use this framework to express situations in which noise variables are not independent.  In fact, it is often possible to do so in two different ways: one can either (1) combine mechanisms that are not independent into one large mechanism with the union of the sources and targets, or (2) explicitly model the noise as variables on which both mechanisms can depend.  As mentioned in the paper, randomized causal models (which assume independent noise) and ordinary causal models (which do not) are equally expressive.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1vAHs3wavE", "reviewer": "Reviewer_wE8z", "summary": "The paper studies notions of \"compatibility\" between probability distributions and directed hypergraphs with causal mechanisms.  In such a hypergraph, we have (roughly) hyperedges T ---> S annotated by a latent/exogenous variable U where the variables S are functionally determined by the variables T and U.  Bayesian networks can be naturally formulated in such terms (where T is the set of parents and S is a singleton set containing the child, and U is a (local) causal mechanism).  The paper explores notions of \"compatibility\" with a joint distribution (over say endogenous variables) and such a hypergraph with additional causal mechanisms.  \"Compatibility\" here means that there exists an realization of the hypergraph that matches a given distribution.\n\nThe paper shows that this notion of compatibility can:\n1) characterize the conditional independencies of a distribution and a DAG\n2) based on hypergraph structure, can represent some functional dependencies (unlike DAGs)\n3) characterize (probabilistic) structural equation models (SEMs) for a graph\n4) characterize generalized (probabilistic) SEMS for hypergraphs\n5) given a (witness) distribution for a class of hypergraphs, can reconstruct its PSEM (up to a family of PSEMs)\n6) and, from (5), also characterize its interventional distrbution\n7) compatibility implies a negative \"information deficiency\"\n8) be characterized with a QIM incompatibility score based on information theoretic entropy\n9) which, from (8), can also be upper- and lower-bounded\n\n(note: my summary may be over-simplifying).  Correspondingly, notions of independence, causality and information theory are tied together through the notion of compatibility.", "questions": "none", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is ambitious, and seeks to tie together central ideas from independence, causality, and information theory into a notion of distribution compatibility with a hypergraph over causal mechanisms.  In addition, there are some generalizations made from (causal) DAGs and SEMs to hypergraphs.\n\nI appreciate that the authors regularly included examples throughout the paper, which makes things easier to follow, and also helps to motivate the discussion.", "weaknesses": "At times, the claims of the paper seem overstated.  The first half of the results are familiar from (causal) DAGs.  For example, the claim after Proposition 3, mentions a phenomena relating randomized SEMs and BNs as possibly not being formalized previously.  I believe, for one example, that the following paper talks about this connection:\n\n  \"Causality in Bayesian belief networks\"\n  Marek Druzdzel, Herbert Simon\n  in Uncertainty in Artificial Intelligence, 1993.\n\nI also found the paper relatively dense, with many results given.  I believe there is a central theme of compatibility tying together concepts of independence, causality and information theory.  Some of the other results, for example, the characeterization of some functional dependencies through hypergraph edges --- this seems more like an extra result that does not clearly support the main story (in my opinion), or it is otherwise under-explored given the space constraints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the reference to Druzdzel and Simon’s 1993 paper!  You are right to point out a similarity between their Theorem 1 and ours; we both provide causal interpretations of Bayesian Networks. We will certainly discuss this in the full paper! However, upon close examination, we believe that their results are not as strong as ours (i.e., do not fully capture the equivalence between BNs and fully randomized acyclic causal models). Here is why: \n \n- At best, Druzdzel and Simon’s Theorems 1 (and 2) provide one direction of the result: if you have a Bayesian Network (with graphical structure G) then it can be converted to an equivalent structural equations model (also with structure G) with independent error terms.  But the reverse direction is missing: that an arbitrary structural equations model with independent error variables determines a Bayesian Network.  \n- While it is true that Druzdzel and Simon’s construction could be the centerpiece of an alternate proof of one direction of our Theorem 1, this fact is not reflected in the theorem statement, which says nothing about the mechanisms’ noise variables being (jointly) independent.  Thus, technically speaking, the formal statement of their result is weaker than (one direction of) ours. Indeed, strengthening the statement is necessary to get the reverse direction of the equivalence. \n- Perhaps most importantly, the fundamental story is extremely different. Druzdzel and Simon are concerned with interpreting *quantitative* BNs in a causal way (and to that end finish with a third theorem that is unrelated to our work). But they are not concerned with representing independencies in this way. Indeed, they state in the intro  that “a causal structure does not necessarily imply independences”, strongly suggesting that they did not realize that their result could actually form half of a causal characterization of BN independencies. \n\nWe share your intuition that this equivalence between (fully randomized) causal models and Bayesian networks should be present in the literature. Beyond the Druzdzel and Simon reference that you pointed us to, which comes close to capturing one direction of the correspondence, we also recently (re)discovered that Pearl’s “Causal Markov Condition” (Theorem 1 from Causal Inference: an overview, 2009) comes close to showing the other direction.  Yet we still haven’t found anything that puts the two halves together and recognizes it as an equivalent characterization of a Bayesian Network’s conditional independencies. We will make sure to point out these new points of contact with the literature, and will tone down the rhetoric accordingly. We would also be grateful for any other leads you might have!\n\n\nNow, to directly address your concerns:\n\n**Overstatement.** Whether or not we can track down prior discussion of the equivalence discussed above, we are happy to include a discussion of how Pearl's and Druzdel and Simon’s work relates to ours, which will mean toning down the rhetoric that follows Proposition 3.  Please let us know if there are other places in which the results seemed overstated!\n\n**Density and “Extra” Results.** We agree that the paper is denser than would be ideal, but found that this level of density was necessary to capture the full scope of the concept. Theorem 2 is identified as one result that might not directly support the main story.  But, to our minds, Theorem 2 is a key element.  It demonstrates that mechanism independence can capture not only (conditional) independencies but also functional dependencies, even within a single hypergraph. That our definition can capture both dependence and independence is no coincidence—the two are closely related (see lines 28-31) and both are special cases of the information-theoretic constraints that QIM compatibility implies in general (see lines 313-315, or for more detail, lines 333-335, equation (2), and Theorem 7). If the paper is accepted, perhaps with the extra page provided in the proceedings we will be able to make this thread more visible, and otherwise add discussion to reduce the density of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fkX5r8GsWF", "reviewer": "Reviewer_3P8H", "summary": "The paper presents a formalism that is claimed to extend the qualitative structure of probabilistic dependency graphs.", "questions": "What is the problem that this is a solution to? What can this do (or do better) that other proposals cannot do? \n\nYou highlight that this is a hypergraph rather than a DAG in a belief network. What does the hypergraph let us do that a Bayesian network does not? (In a Bayesian network, all of the parents affect the child; your's allows multiple targets.) Can a node be in multiple targets?  If so, what if different mechanisms result in different values? If not, isn't having a mechanism that produces multiple targets trivially equivalent to multiple mechanisms that produce single targets?\n\nFor Example 3 with Boolean variables, the bidirectional arrow (X <-> Y) has 4 parameters, but there are only 3 degrees of freedom. Almost all parameterizations are inconsistent. For one of the inconsistent parameterizations, does it define a distribution? If so, which one?", "limitations": "I don't think it has any societal impacts, positive or negative. \n\nThere are very few limitations to the work done.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "I think it might be original, but it is difficult to tell. It might be potentially significant, but it isn't clear what the significance might be.", "weaknesses": "It is not clear what problem this solves (or does better than other proposals). It claims to be \"do much more\", but it isn't clear what the much more is. The semantics needs to be presented in a much more straightforward way.\n\nIn example 4, you ask \"are there distributions not compatible...? It is not obvious.\" The answer is yes. The parity function X \\equiv (Y \\equiv Z) that is true when an even number of X,Y,Z are true, is not compatible. They are each a function of the other two but are independent of either one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n**QUESTIONS**\n\n1. You start with a very important question: \n> what is the problem that this is a solution to? What can it do (or do better) that other proposals cannot do?”\n    \n    Until now, there has not been a satisfying generalization of qualitative Bayesian networks (which can capture independencies without needing conditional probability tables) that applies more broadly to other (causal/probabilistic) models, such as those with cycles or constraints. At the same time, there has been no definition for what it would mean for a distribution to be compatible with an arbitrary set of causal mechanisms.  The answer we propose in this paper not only solves these problems, but also provides a deep and nontrivial connection between information theory and causality.  For the causality community, it provides an information-theoretic test for whether a probability distribution is compatible with a (possibly cyclic) qualitative graph.  For the information-theory community, it provides a principled notion of “pairwise interaction” that explains and shines light on a long misunderstood quantity (interaction information) and reframes a standard counterexample in new light.\n\n2. Next, for your questions about expressiveness, and the syntax of directed hypergraphs.\n> What does the hypergraph let us do that a BN does not? (In a BN, all parents affect the child; your's allows multiple targets.) Can a node be in multiple targets? If so, what if different mechanisms result in different values? \n\n    (Directed) hypergraphs can express many things that DAGs cannot.  They can encode cyclic graphs.  They can also describe situations in which multiple independent mechanisms generate the same variable, as shown in Example 2  (so a node can indeed be in multiple targets). In such situations, all mechanisms that generate a node are required to generate the same value. This may seem strange, but it is useful, and there are scenarios where it is also quite natural. Suppose that X and Y turn out to be different names for essentially the same concept. Then, in addition to the ordinary mechanism that explains the value of X, we can also add an equation stating that $X = f(Y)$ for some function f, which must also hold simultaneously. In such cases, the question of “which value of X: the one prescribed by the original function, or the one prescribed by Y?” is moot; both equations must hold.\n\n    Finally, you ask if having a single mechanism that produces, say, three targets (call them $X,Y,Z$) is the same as having three (independent) mechanisms that each produce a single target ($X,Y$, and $Z$, respectively).  They are not, because the mechanisms are assumed to be *independent*.  A single randomized function that produces all three of $(X,Y,Z)$ can represent an arbitrary distribution over the three variables, but three independent randomized functions taken together can only represent distributions of the form $P(X,Y,Z) = P(X) P(Y) P(Z)$.\n\n3. We are not sure that we understood your final question, but we will try to answer it to the best of our ability.  \n> For Example 3 with Boolean variables, the bidirectional arrow (X <-> Y) has 4 parameters, but there are only 3 degrees of freedom. Almost all parameterizations are inconsistent. For an inconsistent parameterization, does it define a distribution? If so, which one?\n    By the “bidirectional arrow X <-> Y”,  we assume you mean the pair of two arrows, X->Y and Y->X.  We have not talked in this paper about how to parameterize arrows (we are focused on the qualitative aspects of the graph, not the probabilistic parameterization).  However, the work on probabilistic dependency graphs (PDGs) that we reference does. \n\n    In that setting, parameters for these two arrows amount to giving four distributions:  P(Y|X=0) and P(Y|X=1) for the arrow X -> Y, as well as P(X|Y=0) and P(X|Y=1) for the arrow Y-> X. Each is a distribution over a binary variable, and hence can be specified with a single parameter.  So, if we have understood correctly, this indeed means specifying four independent parameters, when in fact there are only three degrees of freedom in joint distributions over P(X,Y).  As you correctly point out, this means most settings of the parameters will not be consistent with any distribution. The question of which distribution is specified in this case is an interesting one; indeed, that is the focus of Richardson and Halpern’s 2021 paper on PDGs. (Essentially, they do so by finding a distribution that is minimally inconsistent with the specified information, as measured by relative entropy.)  But that resolution of the inconsistency is not directly relevant to our paper.\n\n**WEAKNESSES**\n\nWe admit that the presentation is dense and technical; we have tried to add intuition and examples to mitigate this, and may be able to do more with an extra page. We welcome any suggestions for how to make the presentation more straightforward without making it less precise. \n\nYou provide an answer to the rhetorical question posed in example 4—and indeed, when we return to the example in section 4 (as promised in the forward reference), we give exactly the same answer (example 5).  We agree with the reviewer that this distribution ($\\mu_{\\mathrm{xor}}$ in the paper) intuitively should not be compatible with the 3-cycle. But why not?  Can you prove it without using the tools presented in Section 4 (Theorems 7 or 8)?  We found this exercise very difficult, and were able to do it only by combining a technical argument tailored to binary variables with exhaustive computer search.  We are eager to hear if you have found a simpler proof, especially one that does not use the information-theoretic arguments behind Theorem 7! (See Example 6 for further evidence that questions of QIM-compatibility may not always be as obvious as they may seem.)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xm5BNRLY37", "reviewer": "Reviewer_b6Hm", "summary": "The paper considers the framework of directed hypergraphs and demonstrates how it can be used to represent the structural properties of probability distributions. Inspired by the successes of Bayesian networks (which are essentially DAGs), they generalize the findings from the perspective of directed hypergraphs. The key innovation seems to be that instead of simply understanding conditional dependencies (or more specific context-specific indepdencies), the framework goes beyond to consider functional dependencies and understand thesein greater depth. The idea is to use these probabilisitic dependency graphs  as formulations to define the idea of QIM (qualtiatively independent mechanism) compatibility of a distribution w.r.t a hypergraph. \n\nOnce the QIM compatibility is defined, the paper proceeds to demonstrate its usefulness in two specific settings - causal models and information theory. Specifically, it establishess the equivalence between QIM compatibility and randomzized probabilistic structural equation models (PSEMs). The key result in this direction is presented in Proposition 4 where it presents a natural generalization of causal model that exactly captures QIM compatibilitywith an arbitrary hypergraph.  In addition, the paper considers the correspondence between QIM compatibility and interventions in causal models. Finally, it takes a deeper dive into discussing the relation between information theory and QIM compatibility by defining a qualitative scoring function for probabilisitic dependency graphs. The key idea here is to show how one can measure how far a distribution is QIM compatible with a hypergraph structure.", "questions": "Please see the weaknesses for specific questions about theorems, definitions and the delination between prior and proposed contributions.", "limitations": "Some real examples could be used for motivation.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Over all, this is a well written paper. Albeit quite dense, the paper is indeed worth publishing for the community. It was quite insightful read and the paper clearly layes out the problem and the solutions. Clearly written for a niche community, the paper does convey what it aims to do -- the value of probabilistic hyerpgraphs in deeply understanding the causal models and the connection to information theory. I q2uite like the paper.", "weaknesses": "While the paper is excellent, I do have a few concerns/questions:\n\n* I am not sure I clearly see what the contributions of the current paper are w.r.t the literature. For instance, as the paper mentions., Richardson and Halpern had already defined PDGs but you have redefined it in Definition 1. This is perfectly fine if this section is a background section but the way it is written, it appears that it is part of the contributions.  It would be great to separate out where teh prior work and background ends and where the paper begins. I assumed that it ends around line 94 and the paper's contributions start from Definition 2. Is this correct?\n\n* As the paper itself mentions, I do not see the need for Proposition 3. It kinda directly follows from Theorem 1 and so why have it separately when the value is not clear?\n\n* While I clearly like the information theory part more (since the scoring function is quite intuitive at the end due to the definition of QIM compatibility), I would have liked to see some practical use cases. I would have liked to see a specific discussion on the types of settings/problems where such situations are plausible/common. Specifically, what kind of interventions are possible (may be in specific domains). \n\n* Some analysis on the computational complexity of these scoring functions would be nice as well.\n\nOver all, a good paper but can be made a bit more acecssible with some real examples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\nA few responses to your questions:\n\n1. **The division between hypergraphs (defn 1) and original contributions.** Definition 1 is an old (if not particularly common) idea; we cite Gallo et. al. [4] as a reference, although surely they were not the first to study directed hypergraphs. In any case, Definition 1 is not the definition of a PDG.  It is important to distinguish directed hypergraphs from PDGs for the same reason that it is important to distinguish ordinary directed acyclic graphs (dags) from Bayesian Networks.  We present a definition of a directed hypergraph for two reasons: to make the paper self-contained, and to introduce convenient notation.\n\n    You are essentially correct about where the division between prior work and the contributions are, although arguably the contributions start with the lead-in to Definition 2, on line 86. We will try to add a few words to try to make it clearer where the background ends and our contributions begin.\n\n2. **Distinguishing Proposition 3 from Theorem 1.**\nProposition 3 is in many ways orthogonal to Theorem 1.  Theorem 1 describes an equivalence between the independencies of a dag $G$ and QIM-compatibility with $\\mathcal A_G$, but says nothing about causality.  Meanwhile, Proposition 3 describes an equivalence between arising from a fully randomized causal model with graph $G$ (now an arbitrary graph, not necessarily acyclic), and QIM-compatibility with the graph $G$.  By composing the two results, we get an equivalence between BNs  and (fully randomized) acyclic causal models.  But Proposition 3 does not follow from Theorem 1, because Theorem 1 does not talk about causality (or graphs with cycles, for that matter). \n\n\n3. **Practical use cases.**\nYou are right to point out that our examples are often purely mathematical and uninterpreted. We will think hard about how to enrich our examples to more vividly illustrate the utility of our approach to qualitative modeling. \n\n    We are not entirely sure what is meant by the inquiry as to “what interventions are possible”. This work is focused on qualitative modeling, while interventions typically involve concrete values of the variables, and one is typically interested in the quantitative effects of those interventions. Nevertheless, as we show in Theorem 7, a witness to qualitative compatibility can be used to describe interventions. Although the statement of the theorem describes a limitation as to which interventions are encoded in a witness (a certain event must have positive probability), we believe that those limitations are surmountable (see footnote 2).  We also suspect that a generalized randomized PSEM (definition 4) may be able to handle a far broader class of interventions than the standard one—but investigating that is beyond the scope of this work. \n\n4. **Complexity.** Because there are $2^n$ joint distributions over $n$ variables, even the input to the scoring functions must be exponentially large, unless we restrict to a specialized structure parameterizing a special class of distributions (that have certain (in)dependencies). In any standard representation, the difficulty of calculating IDef is dominated by the difficulty of calculating the entropy of the entire joint distribution.  While difficult in some cases (e.g., certain undirected models), often it is the case (e.g., in Bayesian Networks or clique trees) that the same independence structure that makes for a manageable representation also makes it easy to calculate the entropy of the distribution it represents. \n\n    Calculating QIM-Inc, on the other hand, is significantly more difficult. (In fact, even calculating whether or not a distribution is QIM-compatible with a hypergraph appears to be quite difficult.) It involves solving an optimization problem over extended distributions—objects that are (perhaps even exponentially) larger even than the original distributions.  And even if we ignore the cost of representing extended distributions, how long will it take to solve the optimization problem?  This is an interesting question, and one we do not yet have a good theoretical understanding of.  We do have a rudimentary approach that is able to solve that problem in practice, providing a witness of QIM-compatibility if there is one. But it works only for small graphs, and we have not yet been able to prove its correctness. These problems remain important areas for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you all for your careful reading and useful comments!
 
First and foremost, we want to emphasize that our work has focused purely on qualitative aspects of a model (those properties that can be described with a graphical structure, without needing to know, for instance, the specific values that variables can take on). Indeed, the central definition of the paper (Definition 2) does not discuss how we can use (directed) hypergraphs as the basis of a quantitative modeling tool. Therefore, our framework cannot be used to model specific concrete distribution at all (although it can certainly be used to characterize structural properties of a concrete distribution). To model concrete distributions, one would need to augment directed hypergraphs with additional information, in the same way that one augments a causal graph with equations to get a SEM, or augments a directed acyclic graph with probability tables to get a Bayesian Network.  Correspondingly, we mention two possible avenues for augmenting (directed) hypergraphs with quantitative information: we can annotate hyperarcs with (randomized) functions, to get Generalized Randomized PSEMs (Definition 4), or we can annotate them with (possibly weighted) probability tables, to get a PDG [Richardson and Halpern, 2021].  In Sections 3 and 4, respectively, we describe some relationships between QIM-compatibility and each of these two models. Nevertheless, ultimately our work here is at the qualitative level.  Our goal was to show that our formalism could capture in a useful way qualitative phenomena such as dependence, independence, and more, with QIM compatibility. We believe we have shown that we can. 

Perhaps in part due to our focus on unifying qualitative models, the examples we have chosen are not concrete real-world situations in which a modeler should be using our framework; they were instead selected to be mathematically simple and illustrate key conceptual points about qualitative modeling.  Having said that, we will think hard about how to modify our examples to more forcefully make the case that this level of generality is truly necessary to represent what one would like, at the qualitative level.   We agree that this would give the paper more impact, and appreciate the suggestion.

Several reviewers point out that the material is rather dense. Indeed it is, and if the paper is accepted, we will do what we can with the additional page in the proceedings to expand on and clarify the material that is already there.

Meta-review: The paper studies notions of “Compatibility”  between probability distributions and directed hypergraphs. Its main benefit beyond Bayesian networks is that it can capture functional dependencies.
The majority of f the reviewers agreed that the paper can be accepted even when they were not sure about the contribution beyond earlier work.One reviewer questions the very essence of the work: what does it add to the area. What is the question being solved here. Yet after discussion he also agreed that given  all the points raised in the discussion the paper ca be accepted.
Decision: Accept (poster)