*This website uses Javascript to render markdown documents in your browser,
apply syntax highlighting to code fragments and render $\LaTeX$ formulas.
Below is the markdown source code of this page. You can either read that or
enable Javascript to have it rendered to HTML.*

# Self-adhesivity in lattices of abstract conditional independence models This page contains the source code and explanations related to the computational results presented in the paper: > Tobias Boege, Janneke H. Bolt, Milan Studený: *Self-adhesivity in lattices of abstract conditional independence models*. - arXiv preprint: [`math.CO/2402.14053`](https://arxiv.org/abs/2402.14053) - Files directory: [`selfadhe-lattices`](./?dir) with container sources: [`selfadhe-lattices/container`](container?dir) - Container image: [`selfadhe-lattices.tar.zst`](/images/cinet-selfadhe-v1.0.0-20240215.tar.zst) <small style="line-break: anywhere">(SHA256: <code>5392aa406934092400c66fd06ceb8cf35bf8174e246ecf95b201fd1aa061c302</code>)</small> - Repository: <code>git clone <https://git.cinet.link/selfadhe-lattices></code> Notation and terminology follows the paper. All computations are performed in the provided container. Download the container image and `podman load` it or create it yourself (see the [installation instructions](/install) for details on containers). Then login via ``` console $ podman run -w /selfadhe -it cinet/selfadhe bash -l ``` The summary table of numerical data for all computations is available (on which the table in Appendix C is based) in the [`summary.txt`](summary.txt) file. Timings for all computations performed in the above container on the author's laptop (single-thread performance, Thinkpad T14 with Intel i7-1365U) can be found in [`timing.log`](timing.log). $\newcommand{\sg}{\mathfrak{sg}}$ $\newcommand{\gr}{\mathfrak{gr}}$ $\newcommand{\cgr}{\mathfrak{cgr}}$ $\newcommand{\st}{\mathfrak{st}}$ $\newcommand{\pr}{\mathfrak{pr}}$ $\newcommand{\dual}{\star}$ $\newcommand{\sa}{\diamond}$ ## Generating lattice data The core technology of our computations is SAT solving. Every family of CI models we consider is a lattice and can therefore be axiomatized using Horn clauses. The frames of semigraphoids $\sg$, graphoids $\gr$ and compositional graphoids $\cgr$ are known to have a finite axiomatization. The structural semigraphoids $\st$ are known not to have a finite axiomatization as a whole frame [[Mat97]](#Mat97); nevertheless each family in this frame can be axiomatized by a boolean formula. For $\st(4)$ the axioms have been derived in early work by Studený [[Stu94]](#Stu94) and we will derive them from scratch below using only an exhaustive list of the members and the lattice structure of the family. The first program to discuss is [`gen.pl`](gen.pl) which enumerates various families of CI models. By default it enumerates semigraphoids over a given ground set: ``` console $ perl gen.pl 4 >sg4/all $ wc -l sg4/all # count semigraphoids 26424 sg4/all $ perl mod.pl 4 sg4/all | wc -l # count permutational types 1512 ``` The resulting file contains one CI model per line encoded in binary. The encoding follows earlier conventions and is explained on <https://gaussoids.de>. Combining the options `--composition` and `--intersection`, one can enumerate graphoids, compositional semigraphoids or compositional graphoids. The option `--structural` allows to enumerate structural semigraphoids. Finally, the option `--selfadhesive` can be combined with any of the previous options to produce the selfadhesion of the indicated family. Note that `--selfadhesive` *cannot* be used multiple times to compute iterated selfadhesion. There is also a subdirectory [`pr4`](pr4?dir) which contains the probabilistically representable CI models on a 4-element ground set. The file [`pr4/all`](pr4/all) was generated using [`simecek-tools`](https://github.com/taboege/simecek-tools) from files originally produced by Petr Šimeček [[Šim06]](#Šim06). This website disappeared but the data is still available from the [Internet Archive](http://web.archive.org/web/20190516145904/http://atrey.karlin.mff.cuni.cz/~simecek/skola/models/). We have also implemented a function in `Mathematica` to independently test selfadhesivity of semigraphoids over a 4-element ground set at a 2-element subset. Refer to [`doc-N4-xy.nb`](mathematica/doc-N4-xy.nb) and its embedded documentation. ### Pseudo-closed models and axioms The program [`axioms.pl`](axioms.pl) takes a list of models in a CI family as input, assuming that they form a lattice, and executes the algorithm described in Appendix A to compute a canonical implicational basis. It converts this into a boolean formula in conjunctive normal form (CNF). It does this once in human-readable form on stderr and in machine-readable form on stdout. ``` console $ perl axioms.pl 4 sg4/all >sg4/cnf 12| & 13|2 => 12|3 & 13| 12|3 & 14|23 => 12|34 & 14|3 ``` The output file is a boolean formula axiomatizing the input family in the standard DIMACS CNF format which is understood by all varieties of SAT solvers. The pseudo-closed models of the lattice which give rise to these axioms can also be printed: ``` console $ perl axioms.pl --pseudo-closed 4 sg4/all | perl mod.pl 4 | perl write-struct.pl 4 { ab|c, ad|bc } { ab|, ac|b } ``` ### Coatoms and irreducibles Given the axioms of a family of CI models in CNF, it is easy to enumerate the coatoms and irreducible models using their definitions: - A CI model $\mathcal{M}$ is a *coatom* in $\mathfrak{f}(N)$ if the only strict superset in $\mathfrak{f}(N)$ is the full CI model $\mathcal{K}(N)$. By adding the following clauses to the axioms of $\mathfrak{f}(N)$, $$ \bigwedge_{a \in \mathcal{M}} a \wedge \bigvee_{b \in \mathcal{K}(N) \setminus \mathcal{M}} b \wedge \bigvee_{b \in \mathcal{K}(N) \setminus \mathcal{M}} \neg b, $$ we obtain a formula which describes all strict supersets of $\mathcal{M}$ in the family which are not the full CI model. Hence it is satisfiable if and only if $\mathcal{M}$ is *not* a coatom. This is a single SAT solver invocation and usually very fast. - A CI model $\mathcal{M}$ is *irreducible* in its family $\mathfrak{f}(N)$ if it is not equal to the intersection of all its strict supersets in the family. But the intersection of all strict supersets is a superset of $\mathcal{M}$ and hence the only way in which this intersection is not equal to $\mathcal{M}$ is if there exists some $b^* \not\in \mathcal{M}$ such that the $\mathfrak{f}$-closure of every set $\mathcal{M} \cup b$, for any $b \in \mathcal{K}(N) \setminus \mathcal{M}$, contains $b^*$. This can be tested as well using multiple SAT solver invocations, one for each candidate $b^*$. The two programs [`coatoms.pl`](coatoms.pl) and [`irred.pl`](irred.pl) implement these algorithms. ``` console $ perl coatoms.pl 4 sg4/cnf >sg4/coatoms $ perl mod.pl 4 sg4/coatoms | wc -l 10 $ perl irred.pl 4 sg4/cnf >sg4/irred $ perl mod.pl 4 sg4/irred | wc -l 20 ``` ### About duals The script [`check-duals.pl`](check-duals.pl) takes a list of CI models and outputs one representative for each permutational type inside the family whose dual is outside the family. The 48 types of selfadhesive semigraphoids whose dual is not a selfadhesive semigraphoid can be determined as follows (after `sg4sa/all` has been computed using `gen.pl`): ``` console $ perl check-duals.pl 4 sg4sa/all ``` ## The coatoms of structural 5-semigraphoids which are also selfadhesive 5-semigraphoids The second thread of computations concerns the containment of coatoms of $\st(5)$ in the family $\sg^{\sa}(5)$. The coatoms of $\st(5)$ are known: they correspond to the extreme rays of normalized supermodular functions. We include a description of this polyhedral cone in the source file [`nsupmod.in`](st5/nsupmod.in) and use [`normaliz`](https://www.normaliz.uni-osnabrueck.de) to enumerate extreme rays which we then convert to structural semigraphoids: ``` console $ cd st5 $ normaliz nsupmod $ perl extreme-rays.pl nsupmod.out | perl to-relation.pl 5 >coatoms ``` The script [`test.pl`](test.pl) is very similar to `gen.pl` except that it does not enumerate a family but tests if input CI models belong to the family. The coatoms computed in the previous step can thus be checked for containment in $\sg^\sa(5)$: ``` console $ cd .. $ perl mod.pl 5 <st5/coatoms | perl test.pl 5 --selfadhesive | perl unmod.pl 5 >st5/coatoms-sg5sa $ perl mod.pl 5 st5/coatoms | wc -l 1319 $ perl mod.pl 5 st5/coatoms-sg5sa | wc -l 154 ``` This shows that out of all 1319 permutational types of extreme normalized supermodular functions, at most 154 can be entropic due to conditional independence obstructions. A similar computation using `perl test.pl 5 --structural --selfadhesive` instead shows that the coatoms of $\st(5)$ which are in $\sg^\sa(5)$ coincide with those in $\st^\sa(5)$. This computation has been independently verified in `Mathematica` using [`doc-N5-xy.nb`](mathematica/doc-N5-xy.nb) and [`doc-N5-xyz.nb`](mathematica/doc-N5-xyz.nb). A list of permutational types of extreme rays of the polymatroid cone for $|N|=5$ is also available in [`doc-vectors-all.nb`](mathematica/doc-vectors-all.nb). The numbering of the extreme rays follows the ordering on the [Electronic catalogue of representatives of extreme supermodular set functions over five variables](http://www.utia.cas.cz/user_data/studeny/fivevar.htm). ## Further reduction of possible entropic entreme rays of 5-polymatroids In Section 6 we mention that even more permutational types of extreme normalized supermodular functions on $|N|=5$ (or, equivalently, tight 5-polymatroids) can be excluded from being entropic by using probabilistically valid CI implications derived from known conditional Ingleton inequalities on $|N|=4$. This computation is performed using `Mathematica` and documented in its source file [`doc-sec-6-remark-2.nb`](mathematica/doc-sec-6-remark-2.nb). ## Computing the second-order selfadhesive semigraphoids The last major computation in the paper is the determination of $\sg^{\sa\sa}(4)$. This is accomplished by a dedicated script [`sasa.pl`](sg4sasa/sasa.pl). The implementation differs from the algorithm presented in Appendix B of the paper in technical details which are intended to reduce computation time. Still, with almost 8 hours of computation time, this is by far the longest-running task. First note that since $\sg^{\sa\sa}(4)$ is a superset of $\pr(4)$, we only need to test second-order selfadhesivity for elements in the difference set $\sg^{\sa}(4) \setminus \pr(4)$: ``` console $ perl mod.pl 4 sg4sa/all | while read G > do grep -q "$G" pr4/all || echo "$G" > done >sg4sasa/sg4sa-minus-pr4 ``` This results in 254 models to be tested, all of which pass all the tests of second-order selfadhesivity: ``` console $ perl sasa.pl sg4sa-minus-pr4 >/dev/null The sg4sa/all file name is not as expected. at sg4sasa/sasa.pl line 51. Reducing selfadhesive semigraphoids modulo symmetry... 254 [Thu Feb 15 19:44:11 2024] 000011111111111111110001 [AB: 1] [AC: 2] [AD: 2] [BC: 2] [BD: 2] [CD: 2] [ABC: 1] [ABD: 0] [ACD: 2] [BCD: 2] PASS [Thu Feb 15 19:46:17 2024] 000011111111111111110010 [AB: 2] [AC: 2] [AD: 2] [BC: 2] [BD: 2] [CD: 2] [ABC: 2] [ABD: 0] [ACD: 2] [BCD: 2] PASS … [Fri Feb 16 03:40:25 2024] 101111011111111111011110 [AB: 2] [AC: 2] [AD: 2] [BC: 2] [BD: 2] [CD: 2] [ABC: 2] [ABD: 2] [ACD: 1] [BCD: 1] PASS Finished! 254 models passed. ``` The program is long and uses a number of tricks, so some remarks are in order: - The computation is organized into a sequence of "tests" for the model $\mathcal{M} \in \sg^\sa(4)$ under consideration. There is one test for each $L \subseteq N = \\{1,2,3,4\\}$ of size $|L| \in \\{2,3\\}$. The test consists of computing $\sg^{\sa\sa}(\mathcal{M}|L)$ and making sure that it is not a strict superset of $\mathcal{M}$. All of these tests must pass before we can conclude $\mathcal{M} \in \sg^{\sa\sa}(4)$. - Instead of performing tests at a given set $L$ verbatim, we compute an involution $\sigma_L$ (i.e., a self-inverse permutation) of $N$ which transfers $L$ to an initial segment $A = \\{1, \dots, |L|\\}$ of $N$. Using $\sigma_L$, we can then perform the test of $\mathcal{M}$ at $L$ by equivalently testing $\sigma_L(\mathcal{M})$ at $A$. This has two advantages: (1) We can detect permutational symmetries of $\mathcal{M}$ and skip redundant computations; and (2) the boolean formulas for adhesive extensions given initial segments can be cached and reused instead of being computed for every $L$. In general, we cache and reuse as much as possible. This saves time **and** memory compared to the naïve implementation. - The computation of $\sg^{\sa\sa}(\mathcal{M}|L)$ is performed using a *closure loop*, in which multiple $\sg(M)$-closures for ground sets $M$ of size up to 10 have to be computed. On a 10-element ground set, there are $\binom{10}{2} 2^8 = 11\,520$ CI statements which makes closure computations quite expensive. In addition, only a restriction of these closures to 5- or 6-element sub-ground sets are needed. The SAT solver-based closure algorithm can be modified to test only for implications on the relevant sub-ground sets. This gives another considerable speed-up. ## References <dl class="references"> <dt><a name="Mat97">[Mat97]</a></dt> <dd> F. Matúš: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997). </dd> <dt><a name="Stu94">[Stu94]</a></dt> <dd> M. Studený: Structural semigraphoids. Int. J. Gen. Syst. 22(2) (1994). </dd> <dt><a name="Šim06">[Šim06]</a></dt> <dd> P. Šimeček: A short note on discrete representability of independence models. PGM workshop, Prague (2006). </dd> </dl> # Colophon - This document describes version `v1.0.0` of the data. - Author: Tobias Boege `post@taboege.de`. - Last modified: 12 February 2024. - License: <a href="http://creativecommons.org/licenses/by/4.0/?ref=chooser-v1" target="_blank" rel="license noopener noreferrer" style="display:inline-block;">CC BY 4.0<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;" src="https://mirrors.creativecommons.org/presskit/icons/cc.svg?ref=chooser-v1"><img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;" src="https://mirrors.creativecommons.org/presskit/icons/by.svg?ref=chooser-v1"></a>