With the profusion of data across new and complicated domains, the compactness and expressivity of PGMs have made them a cornerstone of modern, data-driven technologies. Unfortunately, PGMs suffer one substantial drawback; inference is known to be intractable. Many inference tasks in real-world problems are beyond the reach of existing technology. This dissertation focuses on the message-passing framework, a family of iterative algorithms for performing exact and approximate inference in probabilistic graphical models (PGMs). The message-passing approach is to (1) divide the global inference problem into tractable local problems that can be computed exactly, and (2) iteratively pass messages between local problems until agreement on a global solution is reached. The facility and flexibility of the message-passing framework has made it a popular choice for both exact and approximate inference in PGMs. However, message-passing algorithms suffer from some drawbacks. Exact local inference can be expensive, messages are not guaranteed to converge, and even if they do converge, there are no guarantees on the accuracy of the approximation. In this dissertation, we propose several advances to the message-passing framework that can take advantage of structural properties of a PGM in order to make message-passing based inference faster and more accurate. This document contains the following contributions. First, we propose an alternate representation of the junction-tree algorithm that can take advantage of highly-clustered graph structures in order to perform exact inference more efficiently. Second we investigate the behavior of the loopy belief propagation algorithm in PGMs containing hard constraints; we show that the accuracy of the approximation can be dramatically improved via a preprocessing step that rewrites the PGM in a format more amenable to message-passing. Third, we present a novel message-passing algorithm that allows evaluation of complex queries based on the order statistics of a graphical model. Fourth, we propose a representation for applying the AND/OR search framework to statistical relational graphical models; our representation allows yields tight bounds on the cost of inference in these models. Finally, we outline a method for utilizing the lifted AND/OR framework as the exact inference step in a region-based belief propagation algorithm for statistical relational models.