
Rapid Mixing SwendsenWang Sampler for Stochastic Partitioned Attractive Models
The Gibbs sampler is a particularly popular Markov chain used for learning and inference problems in Graphical Models (GMs). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the SwendsenWang dynamics which is a more sophisticated Markov chain designed to overcome bottlenecks that impede the Gibbs sampler. We prove O( n) mixing time for attractive binary pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned graphs having n vertices, under some mild conditions, including low temperature regions where the Gibbs sampler provably mixes exponentially slow. Our experiments also confirm that the SwendsenWang sampler significantly outperforms the Gibbs sampler when they are used for learning parameters of attractive GMs.
04/06/2017 ∙ by Sejun Park, et al. ∙ 0 ∙ shareread it

On The Projection Operator to A Threeview Cardinality Constrained Set
The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NPhard in general when there exist multiple overlapped cardinality constraints. In this paper, we consider the scenario where the overlapped cardinality constraints satisfy a Threeview Cardinality Structure (TVCS), which reflects the natural restriction in many applications, such as identification of gene regulatory networks and taskworker assignment problem. We cast the projection into a linear programming, and show that for TVCS, the vertex solution of this linear programming is the solution for the original projection problem. We further prove that such solution can be found with the complexity proportional to the number of variables and constraints. We finally use synthetic experiments and two interesting applications in bioinformatics and crowdsourcing to validate the proposed TVCS model and method.
03/21/2017 ∙ by Haichuan Yang, et al. ∙ 0 ∙ shareread it

Subset Selection for Gaussian Markov Random Fields
Given a Gaussian Markov random field, we consider the problem of selecting a subset of variables to observe which minimizes the total expected squared prediction error of the unobserved variables. We first show that finding an exact solution is NPhard even for a restricted class of Gaussian Markov random fields, called Gaussian free fields, which arise in semisupervised learning and computer vision. We then give a simple greedy approximation algorithm for Gaussian free fields on arbitrary graphs. Finally, we give a message passing algorithm for general Gaussian Markov random fields on bounded treewidth graphs.
09/26/2012 ∙ by Satyaki Mahalanabis, et al. ∙ 0 ∙ shareread it

Structure Learning of Hcolorings
We study the structure learning problem for graph homomorphisms, commonly referred to as Hcolorings, including the weighted case which corresponds to spin systems with hard constraints. The learning problem is as follows: for a fixed (and known) constraint graph H with q colors and an unknown graph G=(V,E) with n vertices, given uniformly random Hcolorings of G, how many samples are required to learn the edges of the unknown graph G? We give a characterization of H for which the problem is identifiable for every G, i.e., we can learn G with an infinite number of samples. We focus particular attention on the case of proper vertex qcolorings of graphs of maximum degree d where intriguing connections to statistical physics phase transitions appear. We prove that when q>d the problem is identifiable and we can learn G in poly(d,q)× O(n^2n) time. In contrast for softconstraint systems, such as the Ising model, the best possible running time is exponential in d. When q≤ d we prove that the problem is not identifiable, and we cannot hope to learn G. When q<d√(d) + Θ(1) we prove that even learning an equivalent graph (any graph with the same set of Hcolorings) is computationally hardsample complexity is exponential in n in the worstcase. For the qcolorings problem, the threshold for efficient learning seems to be connected to the uniqueness/nonuniqueness phase transition at q=d. We explore this connection for general Hcolorings and prove that under a wellknown condition in statistical physics, known as Dobrushin uniqueness condition, we can learn G in poly(d,q)× O(n^2n) time.
08/17/2017 ∙ by Antonio Blanca, et al. ∙ 0 ∙ shareread it

Inapproximability of the independent set polynomial in the complex plane
We study the complexity of approximating the independent set polynomial Z_G(λ) of a graph G with maximum degree Δ when the activity λ is a complex number. This problem is already well understood when λ is real using connections to the Δregular tree T. The key concept in that case is the "occupation ratio" of the tree T. This ratio is the contribution to Z_T(λ) from independent sets containing the root of the tree, divided by Z_T(λ) itself. If λ is such that the occupation ratio converges to a limit, as the height of T grows, then there is an FPTAS for approximating Z_G(λ) on a graph G with maximum degree Δ. Otherwise, the approximation problem is NPhard. Unsurprisingly, the case where λ is complex is more challenging. Peters and Regts identified the values of λ for which the occupation ratio of the Δregular tree converges. These values carve a cardioidshaped region Λ_Δ in the complex plane. Motivated by the picture in the real case, they asked whether Λ_Δ marks the true approximability threshold for general complex values λ. Our main result shows that for every λ outside of Λ_Δ, the problem of approximating Z_G(λ) on graphs G with maximum degree at most Δ is indeed NPhard. In fact, when λ is outside of Λ_Δ and is not a positive real number, we give the stronger result that approximating Z_G(λ) is actually #Phard. If λ is a negative real number outside of Λ_Δ, we show that it is #Phard to even decide whether Z_G(λ)>0, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis  specifically the study of iterative multivariate rational maps.
11/01/2017 ∙ by Ivona Bezakova, et al. ∙ 0 ∙ shareread it

On Counting Perfect Matchings in General Graphs
Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #Pcomplete to compute exactly by Valiant (1979), and a fully polynomial randomized approximation scheme (FPRAS) was presented by Jerrum, Sinclair, and Vigoda (2004) using a Markov chain Monte Carlo (MCMC) approach. However, it has remained an open question whether there exists an FPRAS for counting perfect matchings in general graphs. In fact, it was unresolved whether the same Markov chain defined by JSV is rapidly mixing in general. In this paper, we show that it is not. We prove torpid mixing for any weighting scheme on hole patterns in the JSV chain. As a first step toward overcoming this obstacle, we introduce a new algorithm for counting matchings based on the GallaiEdmonds decomposition of a graph, and give an FPRAS for counting matchings in graphs that are sufficiently close to bipartite. In particular, we obtain a fixedparameter tractable algorithm for counting matchings in general graphs, parameterized by the greatest "order" of a factorcritical subgraph.
12/20/2017 ∙ by Daniel Stefankovic, et al. ∙ 0 ∙ shareread it

Sampling in Uniqueness from the Potts and RandomCluster Models on Random Regular Graphs
We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers q≥ 3 and Δ≥ 3, we develop algorithms that produce samples within error o(1) from the qstate Potts model on random Δregular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes may induce linearsized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of q and Δ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we simplify the algorithm significantly by utilising the randomcluster representation of the model. In particular, we show that a percolationtype algorithm succeeds in sampling from the randomcluster model with parameters p,q on random Δregular graphs for all values of q≥ 1 and p<p_c(q,Δ), where p_c(q,Δ) corresponds to a uniqueness threshold for the model on the Δregular tree. When restricted to integer values of q, this yields a simplified algorithm for the ferromagnetic Potts model on random Δregular graphs.
04/22/2018 ∙ by Antonio Blanca, et al. ∙ 0 ∙ shareread it

The complexity of approximating the matching polynomial in the complex plane
We study the problem of approximating the value of the matching polynomial on graphs with edge parameter γ, where γ takes arbitrary values in the complex plane. When γ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of γ, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree Δ as long as γ is not a negative real number less than or equal to 1/(4(Δ1)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all Δ≥ 3 and all real γ less than 1/(4(Δ1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Δ with edge parameter γ is #Phard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real γ it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #Phard on graphs with bounded connective constant for a dense set of γ values on the negative real axis. Nevertheless, we show that the result does extend for any complex value γ that does not lie on the negative real axis. Our analysis accounts for complex values of γ using geodesic distances in the complex plane in the metric defined by an appropriate density function.
07/13/2018 ∙ by Ivona Bezakova, et al. ∙ 0 ∙ shareread it

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution μ_M̂ of an unknown model M̂, can we efficiently determine if the two models M and M̂ are the same? We consider identity testing for both softconstraint and hardconstraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a superpolynomial number of samples. In particular, for nvertex graphs of maximum degree d, we prove that if β d = ω(n) (where β is the inverse temperature parameter), then there is no polynomial running time identity testing algorithm unless RP=NP. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. Our proofs utilize insights into the design of gadgets using random graphs in recent works concerning the hardness of approximate counting by Sly (2010). In the hardconstraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing is hard in the same range of parameters where structure learning is known to be hard.
01/22/2019 ∙ by Ivona Bezakova, et al. ∙ 0 ∙ shareread it
Daniel Stefankovic
is this you? claim profile