Graphoid

<h2 id="history">History</h2>
<a href="/facts/Judea_Pearl/J2JUSAfe">Judea Pearl</a> and Azaria Paz<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> coined the term "graphoids" after discovering that a set of axioms that govern <a href="/facts/Conditional_independence/udUXFaMw">conditional independence</a> in <a href="/facts/Probability_theory/mFBn51rE">probability theory</a> is shared by <a href="/facts/Undirected_graph/kw3eIBUe">undirected graphs</a>. Variables are represented as nodes in a graph in such a way that variable sets X and Y are independent conditioned on Z in the distribution whenever node set Z separates X from Y in the graph. Axioms for conditional independence in probability were derived earlier by <a href="/facts/A._Philip_Dawid/6oKuNnW1">A. Philip Dawid</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> and <a href="/facts/Wolfgang_Spohn/nLGpQssG">Wolfgang Spohn</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
The correspondence between dependence and graphs was later extended to <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graphs</a> (DAGs)<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and to other models of dependency.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="definition">Definition</h2>
A dependency model M is a subset of triplets (X,Z,Y) for which the predicate I(X,Z,Y): X is independent of Y given Z, is true. A graphoid is defined as a dependency model that is closed under the following five axioms:

<ol><li>Symmetry: 
 
 
 
 I
 (
 X
 ,
 Z
 ,
 Y
 )
 ⇔
 I
 (
 Y
 ,
 Z
 ,
 X
 )
 
 
 {\displaystyle I(X,Z,Y)\Leftrightarrow I(Y,Z,X)}
 
</li>
<li>Decomposition: 
 
 
 
 I
 (
 X
 ,
 Z
 ,
 Y
 ∪
 W
 )
 ⇒
 I
 (
 X
 ,
 Z
 ,
 Y
 )
  
 &
  
 I
 (
 X
 ,
 Z
 ,
 W
 )
 
 
 {\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)}
 
</li>
<li>Weak Union: 
 
 
 
 I
 (
 X
 ,
 Z
 ,
 Y
 ∪
 W
 )
 ⇒
 I
 (
 X
 ,
 Z
 ∪
 W
 ,
 Y
 )
  
 &
  
 I
 (
 X
 ,
 Z
 ∪
 Y
 ,
 W
 )
 
 
 {\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)}
 
</li>
<li>Contraction: 
 
 
 
 I
 (
 X
 ,
 Z
 ,
 Y
 )
  
 &
  
 I
 (
 X
 ,
 Z
 ∪
 Y
 ,
 W
 )
 ⇒
 I
 (
 X
 ,
 Z
 ,
 Y
 ∪
 W
 )
 
 
 {\displaystyle I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}
 
</li>
<li>Intersection: 
 
 
 
 I
 (
 X
 ,
 Z
 ∪
 W
 ,
 Y
 )
  
 &
  
 I
 (
 X
 ,
 Z
 ∪
 Y
 ,
 W
 )
 ⇒
 I
 (
 X
 ,
 Z
 ,
 Y
 ∪
 W
 )
 
 
 {\displaystyle I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}
 
</li></ol>
A semi-graphoid is a dependency model closed under 1–4. These five axioms together are known as the graphoid axioms.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Intuitively, the weak union and contraction properties mean that irrelevant information should not alter the relevance status of other propositions in the system; what was relevant remains relevant and what was irrelevant remains irrelevant.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="types-of-graphoids">Types of graphoids</h2>
<h3>Probabilistic graphoids</h3>
Conditional independence, defined as

I
        (
        X
        ,
        Z
        ,
        Y
        )
        ⇔
        P
        (
        X
        ∣
        Y
        ,
        Z
        )
        =
        P
        (
        X
        ∣
        Z
        )
      
    
    {\displaystyle I(X,Z,Y)\Leftrightarrow P(X\mid Y,Z)=P(X\mid Z)}

is a semi-graphoid which becomes a full graphoid when P is strictly positive.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h3>Correlational graphoids</h3>
A dependency model is a correlational graphoid if in some probability function we have,

I
          
            c
          
        
        (
        X
        ,
        Y
        ,
        Z
        )
        ⇔
        
          ρ
          
            x
            y
            .
            z
          
        
        =
        0
        
           for every 
        
        x
        ∈
        X
        
           and 
        
        y
        ∈
        Y
      
    
    {\displaystyle I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0{\text{ for every }}x\in X{\text{ and }}y\in Y}

where 
 
 
 
 
 ρ
 
 x
 y
 .
 z
 
 
 
 
 {\displaystyle \rho _{xy.z}}
 
 is the <a href="/facts/Partial_correlation/q9jC1m48">partial correlation</a> between x and y given set Z.
In other words, the linear estimation error of the variables in X using measurements on Z would not be reduced by adding measurements of the variables in Y, thus making Y irrelevant to the estimation of X. Correlational and probabilistic dependency models coincide for normal distributions.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h3>Relational graphoids</h3>
A dependency model is a relational graphoid if it satisfies

P
        (
        X
        ,
        Z
        )
        >
        0
         
        &
         
        P
        (
        Y
        ,
        Z
        )
        >
        0
        
        ⟹
        
        P
        (
        X
        ,
        Y
        ,
        Z
        )
        >
        0.
      
    
    {\displaystyle P(X,Z)>0~\&~P(Y,Z)>0\implies P(X,Y,Z)>0.}

In words, the range of values permitted for X is not restricted by the choice of Y, once Z is fixed. Independence statements belonging to this model are similar to <a href="/facts/Multivalued_dependency/a9b3na1u">embedded multi-valued dependencies (EMVDs)</a> in databases.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h3>Graph-induced graphoids</h3>
If there exists an undirected graph G such that,

I
        (
        X
        ,
        Z
        ,
        Y
        )
        ⇔
        ⟨
        X
        ,
        Z
        ,
        Y
        
          ⟩
          
            G
          
        
        ,
      
    
    {\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{G},}

then the graphoid is called graph-induced. 
In other words, there exists an undirected graph G such that every independence statement in M is reflected as a vertex separation in G and vice versa. A necessary and sufficient condition for a dependency model to be a graph-induced graphoid is that it satisfies the following axioms: symmetry, decomposition, intersection, strong union and transitivity.
Strong union states that

I
        (
        X
        ,
        Z
        ,
        Y
        )
        
        ⟹
        
        I
        (
        X
        ,
        Z
        ∪
        W
        ,
        Y
        )
      
    
    {\displaystyle I(X,Z,Y)\implies I(X,Z\cup W,Y)}

Transitivity states that

I
        (
        X
        ,
        Z
        ,
        Y
        )
        
        ⟹
        
        
          (
          
            ∀
             
            γ
            ∉
            X
            ∪
            Y
            ∪
            Z
            ,
             
             
            I
            (
            X
            ,
            Z
            ,
            γ
            )
            
               or 
            
            I
            (
            γ
            ,
            Z
            ,
            Y
            )
          
          )
        
      
    
    {\displaystyle I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\cup Y\cup Z,~~I(X,Z,\gamma ){\text{ or }}I(\gamma ,Z,Y)\right)}

The axioms symmetry, decomposition, intersection, strong union and transitivity constitute a complete characterization of
undirected graphs.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h3>DAG-induced graphoids</h3>
A graphoid is termed DAG-induced if there exists a directed acyclic graph D such that 
 
 
 
 I
 (
 X
 ,
 Z
 ,
 Y
 )
 ⇔
 ⟨
 X
 ,
 Z
 ,
 Y
 
 ⟩
 
 D
 
 
 
 
 {\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}}
 
 where 
 
 
 
 ⟨
 X
 ,
 Z
 ,
 Y
 
 ⟩
 
 D
 
 
 
 
 {\displaystyle \langle X,Z,Y\rangle _{D}}
 
 stands for <a href="/facts/Bayesian_network/Ry31vq6T">d-separation</a> in D. d-separation (d-connotes "directional") extends the notion of vertex separation from undirected graphs to directed acyclic graphs. It permits the reading of conditional independencies from the structure of <a href="/facts/Bayesian_network/Ry31vq6T">Bayesian networks</a>. However, conditional independencies in a DAG cannot be completely characterized by a finite set of axioms.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

<h2 id="inclusion-and-construction">Inclusion and construction</h2>
Graph-induced and DAG-induced graphoids are
both contained in probabilistic graphoids.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> This means that for every graph G there exists a probability distribution P such that every conditional independence in P is represented in G, and vice versa. The same is true for DAGs.
However, there are probabilistic distributions that are not graphoids and, moreover, there is no finite axiomatization for probabilistic conditional dependencies.
<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>
Thomas Verma showed that every semi-graphoid has a recursive way of constructing a DAG in which every d-separation is valid.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
The construction is similar to that used in <a href="/facts/Bayes_networks/Ry31vq6T">Bayes networks</a> and goes as follows:

<ol><li>Arrange the variables in some arbitrary order 1, 2,...,i,...,N and, starting with i = 1,</li>
<li>choose for each node i a set of nodes PAi such that i is independent on all its predecessors, 1, 2,...,i − 1, conditioned on PAi.</li>
<li>Draw arrows from PAi to i and continue.</li></ol>
The DAG created by this construction will represent all the conditional independencies that
follow from those used in the construction. Furthermore, every d-separation shown in the DAG will be a valid conditional independence in the graphoid used in the construction.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Pearl, Judea; Paz, Azaria (1985). "Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations" (PDF). <a href="http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf" target="_blank">http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Dawid, A. Philip (1979). "Conditional independence in statistical theory". Journal of the Royal Statistical Society, Series B: 1–31. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Spohn, Wolfgang (1980). "Stochastic independence, causal independence, and shieldability". Journal of Philosophical Logic. 9: 73–99. doi:10.1007/bf00258078. <a href="http://nbn-resolving.de/urn:nbn:de:bsz:352-136744" target="_blank">http://nbn-resolving.de/urn:nbn:de:bsz:352-136744</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Pearl, Judea (1986). "Fusion, propagation and structuring in belief networks". Artificial Intelligence. 29 (3): 241–288. doi:10.1016/0004-3702(86)90072-x. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Verma, Thomas; Pearl, Judea (1988). "Causal networks: Semantics and expressiveness". Proceedings of the 4th Workshop on Uncertainty in Artificial Intelligence: 352–359. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Lauritzen, S.L. (1996). Graphical Models. Oxford: Clarendon Press. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Pearl, Judea; Paz, Azaria (1985). "Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations" (PDF). <a href="http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf" target="_blank">http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Geiger, Dan (1990). "Graphoids: A Qualitative Framework for Probabilistic Inference" (PhD Dissertation, Technical Report R-142, Computer Science Department, University of California, Los Angeles). <a href="https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf" target="_blank">https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Pearl, Judea (1988). Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann. <a href="https://archive.org/details/probabilisticrea00pear" target="_blank">https://archive.org/details/probabilisticrea00pear</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Pearl, Judea (1988). Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann. <a href="https://archive.org/details/probabilisticrea00pear" target="_blank">https://archive.org/details/probabilisticrea00pear</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Pearl, Judea; Paz, Azaria (1985). "Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations" (PDF). <a href="http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf" target="_blank">http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Geiger, Dan (1990). "Graphoids: A Qualitative Framework for Probabilistic Inference" (PhD Dissertation, Technical Report R-142, Computer Science Department, University of California, Los Angeles). <a href="https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf" target="_blank">https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Pearl, Judea; Paz, Azaria (1985). "Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations" (PDF). <a href="http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf" target="_blank">http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Geiger, Dan (1990). "Graphoids: A Qualitative Framework for Probabilistic Inference" (PhD Dissertation, Technical Report R-142, Computer Science Department, University of California, Los Angeles). <a href="https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf" target="_blank">https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Pearl, Judea; Paz, Azaria (1985). "Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations" (PDF). <a href="http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf" target="_blank">http://ftp.cs.ucla.edu/pub/stat_ser/r53-L.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Geiger, Dan (1990). "Graphoids: A Qualitative Framework for Probabilistic Inference" (PhD Dissertation, Technical Report R-142, Computer Science Department, University of California, Los Angeles). <a href="https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf" target="_blank">https://ftp.cs.ucla.edu/pub/stat_ser/r142-geiger-phd.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">A. Paz, J. Pearl, and S. Ur, "A New Characterization of Graphs Based on Interception Relations" Journal of Graph Theory, Vol. 22, No. 2, 125-136, 1996. <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Geiger, D. (1987). "The non-axiomatizability of dependencies in directed acyclic graphs" (PDF). UCLA Computer Science Tech Report R-83. <a href="http://ftp.cs.ucla.edu/tech-report/198_-reports/870048.pdf" target="_blank">http://ftp.cs.ucla.edu/tech-report/198_-reports/870048.pdf</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Geiger, D.; Pearl, J. (1993). "Logical and algorithmic properties of conditional independence and graphical models". The Annals of Statistics. 21 (4): 2001–2021. CiteSeerX 10.1.1.295.2043. doi:10.1214/aos/1176349407. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Studeny, M. (1992). Kubik, S.; Visek, J.A. (eds.). "Conditional independence relations have no finite complete characterization". Information Theory, Statistical Decision Functions and Random Processes. Transactions of the 11th Prague Conference. B. Dordrecht: Kluwer: 377–396. <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Verma, T.; Pearl, J. (1990). Shachter, R.; Levitt, T.S.; Kanal, L.N. (eds.). "Causal Networks: Semantics and Expressiveness". Uncertainty in AI 4. Elsevier Science Publishers: 69–76. <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
</ol>

Graphoid open-in-new

Graphoid