Cluster variation method example

Cluster variation methods for search work by approximating the distribution over satisfying instances, and then using marginals of that distribution to guide the search.

For instance, when trying to find largest independent set, you would specify probability distribution where probability of independent set k is proportional to lambda^size(k). As lambda goes to infinity, probability mass gets concentrated on nodes that are contained in the largest independent set

Here's an animation of occupation probability marginals with lambda going from 0 to 3. You can see the mass gets concentrated on nodes that are part of the largest independent set in the graph, at which point you can use greedy search


Notebook+packages