一句话：提出利用局部结构编码因子加速环状信念传播，并用于程序分析。
在程序分析中，基于概率图模型的推理方法日益常见，但环状信念传播（loopy belief propagation）的效率受大因子影响。本文观察到概率约束常具有局部结构，可用 if-then 规则编码因子，从而设计一种高效的环状信念传播算法。文章还讨论了推理算法复杂度，并证明了方法的若干适用条件。作者在两个已有的基于概率图模型的程序分析工作上评估该方法。结果表明，相比原始环状信念传播算法，平均分别加速 5.11 倍和 2.31 倍。
In program analysis, there is an emerging trend to apply probabilistic reasoning. In general, these approaches build their models based on probabilistic graphical models because they can express local correlations through factors in a compositional manner, which is suitable for program analysis. These models commonly use the loopy belief propagation algorithm to infer the marginal probability distribution for efficiency. However, the efficiency of loopy belief propagation is still affected by large factors. To address this challenge, our insight is that we can exploit the local structure of probabilistic constraints to speed up the inference. To realize this idea, we use if-then rules to encode the factors with local structures and propose an efficient loopy belief propagation algorithm based on it. We also discuss the inference algorithm complexity and prove some applicable conditions of our approach. Our approach is evaluated on two existing program analysis works based on probabilistic graphical models. The results show that our approach can be 5.11 and 2.31 times faster than the original loopy belief propagation algorithm on average, respectively.
DOI 原文 ·
@inproceedings{paperbot9523,
title = {Belief Propagation with Local Structure and Its Applications in Program Analysis},
author = {Yiqian Wu and Yifan Chen and Yingfei Xiong and Xin Zhang},
booktitle = {ASE},
year = {2025},
doi = {10.1109/ase63991.2025.00132}
}