The family of explicit belief propagation algorithms for arbitrary networks with loops

Kurzfassung

Although belief propagation (BP) is a useful inference tool in several network-based contexts given its speed, its precision deteriorates when encountering loops. Generalized belief propagation (GBP) was introduced around two decades ago to mitigate this issue. However, it did not become widely used since it did not provide an explicit algorithm applicable to any network. This only changed recently, with the introduction of the first explicit and general version of GBP for networks, the CN-method, which remained until now the only algorithm with such properties. Here, we provide a family of algorithms with these characteristics. We begin by considering the case where the network only has short loops. In this scenario, we improve on the CN-method by developing a algorithm with optimal time complexity, the NIB-method. We then consider networks that also have long loops. In this context, we show that the NIB-method provides advantages compared to the CN-method: it is faster for the networks where the CN-method is expected to work well, and it is applicable to more networks, i.e. highly dense networks. In general, both the CN-method and the family algorithms introduced here become non-equivalent approximations, and they can provide different levels of accuracy when applied to the same network, as we show numerically using two artificial networks. This discrepancy can have important practical implications, as we discuss in the context of decoding and error correction.