Graphical models provide an elegant formalism for probabilistic computation that unifies much of the literature on stochastic modeling. For sparse networks (e.g., networks in the form of chains or trees, such as hidden Markov models, Kalman filters, and probabilistic decision trees), graphical model algorithms are exact, efficient and practical. For dense networks, however, the exact algorithms are often (hopelessly) inefficient, and this fact has hindered the application of this richer class of models to large-scale problems. I discuss variational methodology, which provides a general framework for approximate graphical model inference. The variational methods I present are efficient; moreover, they tend to be more accurate for dense networks than for sparse networks. They can readily be combined with exact techniques to yield a class of algorithms that perform well for a variety of network architectures. I will discuss applications of these ideas to a variety of architectures, including layered belief networks with logistic nodes, coupled hidden Markov models, factorial hidden Markov models, hidden Markov decision trees, and hidden Markov models with long-range dependencies.