Join-Graph Propagation Algorithms

Area of Science:

• Artificial Intelligence
• Computer Science
• Statistical Physics

Background:

• Pearl's belief propagation (BP) is a foundational algorithm for approximate inference.
• Bounded inference and mini-clustering are established techniques in message-passing algorithms.
• Generalized Belief Propagation (GBP) offers a framework connecting AI and statistical physics.

Purpose of the Study:

• To develop and evaluate novel parameterized approximate message-passing schemes.
• To introduce Iterative Join-Graph Propagation (IJGP) as an advancement over existing methods.
• To analyze the accuracy of iterative belief propagation and IJGP.

Main Methods:

• Investigated parameterized approximate message-passing schemes based on bounded inference.
• Developed the Iterative Join-Graph Propagation (IJGP) algorithm, combining iteration and bounded inference.
• Compared IJGP against mini-clustering, belief propagation, and other state-of-the-art algorithms.

Main Results:

• IJGP empirically surpasses the performance of mini-clustering and belief propagation.
• IJGP demonstrates superior results compared to several other state-of-the-art network algorithms.
• The study provides insights into the accuracy of iterative BP and IJGP through constraint propagation schemes.

Conclusions:

• Iterative Join-Graph Propagation (IJGP) represents a significant improvement in approximate message-passing algorithms.
• IJGP offers enhanced accuracy and performance for various network analysis tasks.
• The research bridges concepts from artificial intelligence and statistical physics in approximate inference.