Recursive sum–product algorithm for generalized outer-planar graphs

Inference on cyclic graphs is one of the most important problems in the applications of graphical models. While exact inference is NP-hard on general cyclic graphs, it has been found that exact inference can be achieved with a computational complexity as low as O(Nm3)O(Nm3) on the outer-planar graph, which is a special kind of cyclic graph. In this paper, we introduce a new kind of cyclic graph, the generalized outer-planar (GOP) graph, which is more general than the outer-planar graph and show that the exact inference on the GOP graphs can be achieved in O(Nm3)O(Nm3) by a recursive sum–product (RSP) algorithm. RSP exploits the property of GOP graphs that the faces are reducible, and brings a “face elimination” procedure to compute the marginals exactly. Furthermore, RSP can be implemented on general cyclic graphs to obtain approximate marginals. Experimental results show the effectiveness of approximate RSP on various graphical models.

► We extract two essential operations for exact inference on outer-planar graphs.
► A new kind of cyclic graphs, generalized outer-planar graphs (GOP), is introduced.
► We propose recursive sum–product algorithm (RSP) for exact inference on GOPs.
► RSP is extended to general cyclic graphs to obtain approximate results.