Authors: Aniruddh Nath and Pedro Domingos (AAAI-10)
Abstract
Probabilistic inference in large graphical models is computationally expensive, particularly in scenarios requiring repeated inference for utility maximization. We present Expanding Frontier Belief Propagation (EFBP), an algorithm that significantly reduces redundant computation by reusing previous messages and limiting updates to a localized "frontier" of affected nodes. Evaluated on viral marketing and combinatorial auction tasks, EFBP achieves orders-of-magnitude speedups over standard Belief Propagation, enabling deeper search and substantially higher utility within fixed time constraints.
Introduction
Probabilistic graphical models, such as Bayesian and Markov networks, are fundamental tools for reasoning under uncertainty. However, the computational cost of inference—calculating variable probabilities given evidence—remains a significant bottleneck. This challenge is amplified in decision-making tasks like utility maximization, where an agent must evaluate thousands of potential actions (e.g., marketing strategies or auction bids).
Standard algorithms like Loopy Belief Propagation (BP) typically restart from scratch for every new piece of evidence. In large, sparse networks, a small change in evidence usually only affects its immediate neighborhood. Recalculating the entire network for every minor variation is massively redundant. This paper introduces Expanding Frontier Belief Propagation (EFBP) to exploit this locality of influence.
The EFBP Algorithm
EFBP is designed to handle repeated inference efficiently by focusing computation only where it is needed. The algorithm is built on four core principles:
- State Reuse: Instead of resetting messages to a neutral state, EFBP initializes with the messages from the previous inference run.
- The Frontier ($\Delta$): The algorithm maintains a set of "active" nodes, initially containing only the variables where evidence has changed.
- Selective Propagation: In each iteration, only nodes within the frontier send messages.
- Expansion: If a node receives a message that differs from its previous state by more than a user-defined threshold ($\gamma$), it is added to the frontier to propagate the change further.
By stopping propagation once changes fall below the threshold, EFBP effectively "ripples" outward from the change and stops when the influence becomes negligible. The authors also introduced EFBP*, a variant that uses theoretical bounds to ensure decisions remain identical to standard BP while maintaining speed gains.
Experimental Evaluation
The authors evaluated EFBP across two complex, high-dimensional domains:
- Viral Marketing: Using the Epinions "web of trust" dataset (75,888 users, >500,000 edges), the task was to select an optimal set of users to target to maximize a chain reaction of purchases.
- Probabilistic Combinatorial Auctions: A synthetic dataset of 1,000 products and 1,000 bids, where product failures create dependencies and uncertainty in auction success.
Key Results and Discussion
In both domains, EFBP demonstrated a transformative impact on computational efficiency. As shown in the viral marketing experiments, EFBP was consistently orders of magnitude faster than standard BP.
This speedup is not merely a matter of efficiency; it directly translates to better decision quality. When limited to a 24-hour window for the viral marketing task, EFBP achieved 40% to 80% higher utility than BP. Because EFBP could evaluate many more potential strategies in the same timeframe, the search algorithm could explore the state space much more deeply.
Furthermore, the accuracy of EFBP remained high. Despite being an approximation, the quality of the solutions was nearly identical to full BP when both were allowed to run to convergence. The primary trade-off involves the threshold $\gamma$: a higher threshold increases speed but may reduce approximation quality, while a lower threshold approaches the behavior of standard BP.
Conclusion
Expanding Frontier Belief Propagation provides a powerful framework for scaling probabilistic reasoning to massive, dynamic decision problems. By recognizing the locality of influence in large networks, EFBP avoids the redundant calculations that plague standard inference methods. This efficiency allows for deeper search and higher-quality outcomes in real-world applications ranging from social network marketing to complex resource allocation.
Summary updated