  GBP and EP are two successful algorithms for approximate probabilistic
inference, which are based on different approximation strategies. An open
problem in both algorithms has been how to choose an appropriate approximation
structure. We introduce 'structured region graphs', a formalism which marries
these two strategies, reveals a deep connection between them, and suggests how
to choose good approximation structures. In this formalism, each region has an
internal structure which defines an exponential family, whose sufficient
statistics must be matched by the parent region. Reduction operators on these
structures allow conversion between EP and GBP free energies. Thus it is
revealed that all EP approximations on discrete variables are special cases of
GBP, and conversely that some wellknown GBP approximations, such as overlapping
squares, are special cases of EP. Furthermore, region graphs derived from EP
have a number of good structural properties, including maxent-normality and
overall counting number of one. The result is a convenient framework for
producing high-quality approximations with a user-adjustable level of
complexity
