  In this paper we offer a solution to a long-standing problem in the study of
networks. Message passing is a fundamental technique for calculations on
networks and graphs. The first versions of the method appeared in the 1930s and
over the decades it has been applied to a wide range of foundational problems
in mathematics, physics, computer science, statistics, and machine learning,
including Bayesian inference, spin models, coloring, satisfiability, graph
partitioning, network epidemiology, and the calculation of matrix eigenvalues.
Despite its wide use, however, it has long been recognized that the method has
a fundamental flaw: it only works on networks that are free of short loops.
Loops introduce correlations that cause the method to give inaccurate answers
at best, and to fail completely in the worst cases. Unfortunately, almost all
real-world networks contain many short loops, which limits the usefulness of
the message passing approach. In this paper we demonstrate how to rectify this
shortcoming and create message passing methods that work on any network. We
give two example applications, one to the percolation properties of networks
and the other to the calculation of the spectra of sparse matrices.
