Clusters and Par77ons in LP Relaxa7ons 
David Sontag, Amir Globerson, and Tommi Jaakkola 
(MIT, Hebrew University) 

MAP problem: 

max
x

i

ij (xi , xj )
j E

ij(xi, xj)

xj 
jk(xj, xk)

T55 
xk 

x i

· Generalized BP uses larger clusters to improve approxima7on of MAP  · Problem: Algorithms scale exponen7ally with cluster size!  · Our solu-on  1  Par77on variables' values: 

xi
Edge  marginal 
x xk
k

1  2 

3  4 

zi zz k
k

1 

2 

z zk
x xi
i

k

2          Use clusters on  coarsened variables 

z zi
i

zi z

i

zj

zj

3  Enforce consistency on par$$oned state space  · We obtain a messagepassing algorithm that finds the exact MAP on protein  design problems at reduced computa7onal cost