Belief Propagation on Dense Graphs with Few Strong Links

Abstract

Message passing techniques in general and belief propagation in particular are highly useful tools for inference, especially when the problem can be represented by a sparse graph. They have been used to solve a range of computational problems such as decoding, graph colouring, satisfiability problems etc. In this approach, messages containing probabilistic information about nodes in the graph are being passed from node (variable) to node to facilitate the calculation of joint and conditional probabilities of the variables, which are then used for inferring their most likely value. One of the great advantages of message passing techniques on sparse graphs is that they are distributed and scale well with the system size (i.e., the computational effort involved grows linearly with the system size). Extending the problem to densely connected systems where the number of messages is very high has been recently suggested. This approach is based on looking at macroscopic properties of sums of messages and modifying them locally (e.g., they can be represented by a Gaussian distribution of some mean and variance which could be modified locally). The task in the project is to devise an algorithm for carrying out updates in a case where sparse strong links exist in conjunction with dense weak links, using features of both algorithms.