[1910.11142] Tractable Minor-free Generalization of Planar Zero-field Ising Models
(That is we keep the algorithm of Globerson and Jaakkola (2007), but substitute planar graphs with a family of spanning decomposition-based graphs that are tractable.) This improvement of Globerson and Jaakkola (2007) results in a tighter upper bound on the true partition function and a more precise approximation of marginal probabilities

Abstract: We present a new family of zero-field Ising models over $N$ binary
variables/spins obtained by consecutive "gluing" of planar and $O(1)$-sized
components and subsets of at most three vertices into a tree. The
polynomial-time algorithm of the dynamic programming type for solving exact
inference (computing partition function) and exact sampling (generating i.i.d.
samples) consists in a sequential application of an efficient (for planar) or
brute-force (for $O(1)$-sized) inference and sampling to the components as a
black box. To illustrate the utility of the new family of tractable graphical
models, we first build a polynomial algorithm for inference and sampling of
zero-field Ising models over $K_{3,3}$-minor-free topologies and over
$K_{5}$-minor-free topologies -- both are extensions of the planar zero-field
Ising models -- which are neither genus - nor treewidth-bounded. Second, we
demonstrate empirically an improvement in the approximation quality of the
NP-hard problem of inference over the square-grid Ising model in a
node-dependent non-zero "magnetic" field.

‹Figure 3: (a) A fragment of G’s embedding after triangulation (black), expanded dual graph G∗ (red). (b) Possible X configurations and corresponding M(X) (wavy lines) on a single face of G. Rotation symmetric and reverse sign configurations are omitted. (Perfect Matching (PM) Model)Figure 4: a) An exemplary graph G and its 8-nice decomposition T , where t ∈ {1, · · · , 7} labels nodes of the decomposition tree T and node 4 is chosen as the root (r = 4). Identical vertices of G in its subgraphs Gt are shown connected by dashed lines. Navels of size 1, 2, and 3 are highlighted. Component G5 is nonplanar, and G4 becomes nonplanar when all attachment edges are added (according to the fourth item of the definition of the c-nice decomposition). G≤3 and G3 are shown with dotted lines. Note that the decomposition is non-unique for the graph. For instance, edges that belong to the attachment set can go to either of the two subgraphs containing this set or even repeat in both. b) Minors K5 and K33 are forbidden in the planar graphs. Möbius ladder and its subgraphs are the only nonplanar graphs allowed in the 8-nice decomposition of a K5-free graph. c) The left panel is an example of conditioning on three vertices/spins in the center of a graph. The right panel shows a modified graph where the three vertices (from the left panel) are reduced to one vertex, then leading to a modification of the pairwise interactions within the associated zero-field Ising model over the reduced graph. d) Example of a graph that contains K5 as a minor: by contracting the highlighted groups of vertices and deleting the remaining vertices, one arrives at the K5 graph. (Decomposition tree and the key result (of the manuscript))Figure 5: a) Example of inference at node t with children c1, c2, c3, c4. Navels K1 = {u1, q1, h1}, K2 = {u2, q2, h2}, K3 = {u2, q2}, K4 = {u4}, and K = {u, q, h} are highlighted. Fragments of I≤ci are shown with dotted lines. Here, I(0) = ∅, I(1) = {4}, I(2) = {3}, and I(3) = {1, 2}, indicating that one child is glued over one node, one child is glued over two nodes, and two children are glued over three nodes. b) “Aggregated” Ising model It and its pairwise interactions are shown. Both c) and d) illustrate sampling over It. One sample spins in It conditioned on S(t) and then repeats the procedure at the child nodes. (Inference algorithm)Figure 6: (a) KL-divergence of the model probability distribution compared with the empirical probability distribution. N, m are the model’s size and the number of samples, respectively. (b) Execution time of inference (red dots) and sampling (blue dots) depending on N, shown on a logarithmic scale. Black line corresponds to O(N 3 2 ). (K33-free Zero-field Ising Models: Implementation and Tests)Figure 7: Construction of graphs used for approximate inference on a rectangular lattice. For better visualization, vertices connected to an apex are colored white. a) G0 graph. b) One of planar G(r) graphs used in Globerson and Jaakkola (2007). Such “separator” pattern is repeated for each column and row, resulting in 2(H − 1) graphs in {G(r)}. In addition, Globerson and Jaakkola (2007) adds an independent variables graph where only apex edges are drawn. c) A modified “separator” pattern we propose. Again, the pattern is repeated horizontally and vertically resulting in 2(H − 2) graphs + independent variables graph. This pattern covers more magnetic fields and connects separated parts. Dashed edges indicate the structure of 10-nice decomposition used for inference. (Nonplanar node of size 10 is illustrated on the right.) (Conclusion)Figure 8: Comparison of tree-reweighted approximation (TRW), planar spanning graph (PSG), and decomposition-based spanning graph (DSG) approaches. The first plot is for normalized log-partition error, the second is for error in pairwise marginals, and the third is for error in singleton central marginal. Standard errors over 100 trials are shown as error bars. An asterisk “*” indicates the statistically significant improvement of DSG over PSG, with a p-value smaller than 0.01 according to the Wilcoxon test with the Bonferroni correction (Wilcoxon, 1945). (Conclusion)

Z__star = sum(prod(c_e__star == frac12 Z exp(sum(J_e))))

Figure 9: (I) An example biconnected graph G. (II) A separation pair {a, b} of G and separation classes E1, E2, E3 associated with {a, b}. (III) Result of split operation with E0 = E1 ∪E2, E00 = E3. Dashed lines indicate virtual edges and dotted lines connect equivalent virtual edges in split graphs. (IV) Split components of G (non-unique). (V) Triconnected components of G. (VI) Triconnected component tree T of G; spacial alignment of V is preserved. “G,” “B,” and “C” are examples of the “triconnected graph,” “multiple bond,” and “cycle,” respectively. (Theorem ?? Proof)Figure 10: Steps of planar graph generation. I-V refers to random tree construction on a plane, VI is a triangulation of a tree, VII is a result after multiple edges removal. (Random Graph Generation)Figure 11: Generation of K33-free graph G and its partially merged decomposition T0. Starting with K5 (I), new components are generated and attached to random free edges (II-V). VI is a result graph G obtained by merging all components in T0. (Random Graph Generation)