Sampling From Graph-Structured Binary Data

Given a positive semi definite matrix, it is easy to generate a Gaussian vector with covariance equal to this matrix. It turns out that the problem is much harder for binary data: in fact finding general necessary and sufficient conditions on the matrix such that the simulation is possible is still an open problem. I want to focus on particular set of matrices (graph laplacians), discuss some possible simulation algorithms, and hear your suggestions about the theoretical conditions or practical implementations. 
For both Genomics and Counting Visitors.