基于K維結構熵的調查傳播算法收斂性分析

摘 要： 信息傳播算法在可滿足性（SAT）問題上性能表現優越，其收斂性卻依賴于因子圖的結構復雜程度，至今缺少系統的理論解釋。調查傳播算法（SP）是解決SAT問題效果最好的信息傳播算法。為有效分析SP算法的收斂性，借助因子圖轉換技術和魯汶算法劃分因子圖社區，基于K維結構熵理論，提出了SAT實例的K維結構熵度量模型，得出了隨機SAT實例的K維結構熵。分析了SP算法收斂性與K維結構熵之間的關系，給出了SP算法收斂性的K維結構熵閾值。實驗證明該方法有效。

關鍵詞： 可滿足性問題； K維結構熵； 調查傳播算法； 收斂性

中圖分類號： TP301.6"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-024-1432-05

doi：10.19734/j.issn.1001-3695.2021.10.0474

Convergence analysis of survey propagation algorithm based on K-dimensional structure entropy

Liang Chena， Wang Xiaofenga，b， Liu Zilina， Lu Leia， Niu Pengfeia

（a.School of Computer Science amp; Engineering， b.Key Laboratory of Images amp; Graphics Intelligent Processing of State Ethnic Affairs Commission， North Minzu University， Yinchuan 750021， China）

Abstract： Survey propagation（SP） algorithm is the most effective information propagation algorithm.However，the algorithm does not often converge when it encounters factor graphs of complex structures.In order to explain this phenomenon theoretically，based on the theory of K-dimension structure entropy，and with the help of factor graph transformation technology and Leuven algorithm to divide factor graph community，this paper proposed the K-dimension structure entropy measurement model of propositional formula，and obtained the K-dimension structure entropy of random satisfiability instance.This paper analyzed the relation between the convergence of SP algorithm and K-dimension structure entropy，and gave the threshold of K-dimension structure entropy for SP algorithm convergence.The experimental results show that the method is effective.

Key words： satisfiability problem； K-dimensional structural entropy； survey propagation algorithm； convergence

0 引言

現實中的許多問題都被看做是約束可滿足問題（constraint satisfiability problem，CSP），是人工智能研究領域的一個重要分支［1，2］。可滿足性判定問題（satisfiability，SAT）屬于CSP的子問題，該問題研究是否存在并且找到使合取范式（conjunctive normal form，CNF）所有合取子句都滿足的賦值，是計算機科學中的一個核心問題并且應用廣泛，在現實中如加密、調度等問題，都可以直接或間接地編碼為SAT問題。因此，求解SAT問題的算法研究一直是學界關注的熱點。

Pearl［3］于1982年提出信息傳播算法，是計算貝葉斯網絡和馬爾可夫隨機場邊際分布的一種消息傳遞算法。Braunstein等人［4］基于因子圖的信息傳遞提出了警示傳播算法（warning propagation，WP）、置信傳播算法（belief propagation，BP）和調查傳播算法（survey propagation，SP）三種信息傳播算法。目前，調查傳播算法在處理3-SAT實例上，有效性和收斂性表現最好［5～7］。然而，對于具有復雜結構的SAT實例，SP算法的信息傳遞常在因子圖中循環傳播，無法有效找到可滿足性指派，表現為不收斂［8］。因此，研究SP算法的收斂性可以為研究其他信息傳播算法的收斂性提供重要參考。近年來，對信息傳播算法的收斂性研究已經取得了一些成果。文獻［9］基于高斯模型分析了信息傳播算法的收斂情況，表明在該模型下算法能夠收斂。文獻［10］通過邊緣分布的有效近似，證明在含有單個環路結構的特殊因子圖上，信息傳播算法可以收斂。文獻［11～14］給出了高斯空間中信息傳播算法的收斂條件，但是這些研究存在不足：文獻［11］需要利用半正定規劃驗證算法是否收斂，驗證困難且低效；文獻［12］基于均值的收斂條件要求計算無限維的譜半徑，在實際計算中可行性不高；文獻［13，14］只適用于具有標量變量的xi節點，實際應用中場景有限。文獻［15］分析了信息傳播算法與Bethe函數之間的關系，利用統計物理自由能函數最小值的唯一性得出，信息傳播算法能夠收斂至固定點，但未作出信息傳播算法能否收斂的分析；文獻［16］針對信息傳播算法的SP算法，通過將傳遞信息ηa→i擴展至無窮大，利用壓縮映射原理給出了SP算法收斂的一個充分條件，但要求矩陣譜半徑ρ嚴格小于1，收斂條件困難。上述研究不難看出，現有對于信息傳播算法收斂性的研究都是基于特定模型，或有一些條件限制，或驗證過程困難，并且只針對SP算法收斂性的研究較少。因此，現有對于SP算法收斂的研究仍然不夠充分，缺乏在廣義因子圖模型上算法收斂的探討。

SP算法收斂取決于因子圖的結構。近年來研究發現，隨著實例集的增大，因子圖的結構也變得復雜，呈現出復雜的多維社區結構［17］。文獻［18］提出了圖的K維結構熵，可以度量圖的結構信息，Zhang等人［19］基于結構熵理論得出工業SAT實例的二維結構熵較大，隱含大量不確定性。圖的K維結構熵被定義為節點代碼所需的最小總位數，該節點可以通過隨機游走來訪問。不同于香農熵和馮諾依曼熵測度，K維結構熵根據圖本身的結構，而不是給定圖的集合而確定。因此，K維結構熵同時提供了結構信息的量化和圖的動態復雜性，可以完全或最大限度地度量由圖的規則、順序組成的K維結構，支持對SP算法在因子圖上隨機游走的動態復雜性、不確定性等因素的研究。

不確定信息最小化是結構熵度量過程中始終遵循的原則，關系著結構熵度量的準確性，為保證不確定信息最小化，需要精確劃分SAT實例的社區結構。文獻［20，21］的結果表明，將因子圖轉換為變元交互圖［22］（variable incidence graph，VIG），使用魯汶算法［23］劃分社區有較高的模塊度（modularity）［23］。

綜上所述，本文針對SP算法的收斂性進行研究。基于K維結構熵理論，在不同長度的隨機SAT實例集上，利用魯汶算法劃分實例社區，提出了SAT實例的K維結構熵模型，根據該模型得出了SAT實例的結構信息并計算了K維結構熵。對比SP算法在SAT實例的收斂情況，分析了SP算法關于K維結構熵的收斂情況，給出了SP算法收斂性的K維結構熵閾值。

3 SP算法收斂性分析

使用G（n，3，m）模型生成3-SAT實例。隨機3-SAT實例含有n個變元，m個子句，子句長度為3。對于一個隨機3-SAT實例，約束密度α=m/n對SP算法的收斂時間和收斂困難程度有重要的影響，而因子圖結構的復雜程度決定SP算法的收斂性。本章使用G（n，3，m）模型生成SAT實例，設置兩組變元規模（n=20，n=40），控制α的值由0遞增到5，遞增梯度為0.1。為消解極少數異常SAT實例的影響，隨機生成100組實例形成實例組，實驗產生的所有K維結構熵均為100組實例的均值。隨機實例隨結構熵變化如圖5～8所示。

在不同規模的實例中，隨著約束密度α的增大，K維結構熵逐漸增大，熵增量ΔH逐漸減小。0lt;αlt;3.9時，由于因子圖結構不穩定，社區內部信息傳遞不夠緊密，魯汶算法劃分的社區模塊度較小［20］，增量ΔH較大。3.9lt;αlt;5.0時，K維結構熵的增量ΔH趨近于0，此時因子圖趨于穩定，最終規模為20、40的SAT實例的K維結構熵分別逼近3.527 1和3.996 8。以上K維結構熵的變化表明，在固定規模的實例集中，隨著約束密度α的逐漸增大，因子圖的動態復雜性在0lt;αlt;3.9內迅速上升，呈現出復雜的多維結構，當αgt;3.9時，動態復雜性的增速趨于平緩。

統計SP算法在100組實例上收斂的個數，除以實例組總數即得到了SP算法收斂概率。圖6展示了SP算法隨K維結構熵增大的收斂概率，當K維結構熵超過當前實例規模的閾值時，算法收斂概率急速下降至不收斂。變元規模n=20，因子圖的K維結構熵在［1.76，3.53］分布密集，當Hk≤3.130時，SP算法在隨機實例上能夠完全收斂，當3.130lt;Hk≤3.445，算法收斂概率迅速下降至0。變元規模n=40，Hk在［1.87，4.02］分布密集，Hk未超過3.535時，算法在所有實例上可以收斂。圖5、6說明SP算法能在大多數隨機實例上收斂，但是一旦超過某一閾值，SP算法幾乎不收斂。由于給定變元規模的情況下，隨著α的增大，因子圖開始呈現復雜的多維結構，圖中含有環路連通分支數目和環路節點數目的增多、圖直徑的增大，都對圖結構信息影響較大，體現在K維結構熵中即增量ΔH較大，此時SP算法依然能在絕大多數實例上收斂，表現了良好的性能。當α接近SP算法可滿足性相變點時，SP算法的收斂概率急劇下降至0。此時，因子圖的結構信息趨于穩定，環路數量、圖直徑、環路節點數的變化對圖的動態復雜性影響顯著減小，Hk趨于穩定。此外，本文對比了SP算法收斂時間與SAT實例K維結構熵之間的關系，如圖7、8所示。

圖7、8分別展示了SP算法收斂時間隨約束密度α、K維結構熵變化的情況，表明了SP算法的收斂時間幾乎不受變元規模的影響，算法的收斂時間取決于約束密度α和K維結構熵的大小。總體來說，兩種參數對SP算法收斂難度的影響相似，但又有一些差異。圖7表明約束密度α∈［0，3.1］時，算法性能優異，能在幾乎所有實例上以極快的速度收斂，對比圖5可知，此時因子圖的K維結構熵增長較快，圖的動態復雜性迅速增加。α∈［3.1，3.9］時，收斂時間急劇增長；α∈［3.9，5.0］時，算法收斂時間進一步增長，增幅變緩，而圖5表明，此時因子圖的多維結構復雜性和動態復雜性已趨近于最高，Hk的增幅趨近于0；事實上，α∈［3.921，4.27］已經是隨機SAT實例的難解區域，此區域內大部分算法已經失效，因此，此區域的實例常被用于國際賽事以測試算法性能。

圖8從因子圖多維結構的復雜程度和動態復雜性的角度，表現了SP算法收斂時間隨K維結構熵變化的情況。以n=20為例，當Hklt;3.245時，算法收斂速度較快，由圖6可知，Hk≤3.130時可以完全收斂，在3.32附近SP算法開始不完全收斂，此時因子圖動態復雜性接近最高值，實例開始難解。當Hkgt;3.245時，算法收斂時間呈指數上升，對比圖6發現，此時SP算法收斂概率已開始迅速下降，因子圖出現的環路結構、直徑大小已強烈影響SP算法的收斂性。SP算法在其他規模實例中的K維結構熵收斂性閾值也可通過以上方法求得。

4 結束語

本文利用魯汶算法劃分SAT實例社區，并基于K維結構熵提出了SAT實例的K維結構熵獲取方法，通過實驗得到了不同規模的SAT實例中K維結構熵的變化情況，通過分析SP算法在不同規模SAT實例中的收斂情況，給出了SP算法收斂的一個充分條件。后續工作中，將利用因子圖的結構信息對信息傳播算法作出理論分析，用結構熵模型探索信息傳播算法在SAT問題中的相變情況，從結構信息的角度解釋信息傳播算法收斂性相變本質。

參考文獻：

［1］Dyer M，Frieze A，Molloy M.A probabilistic analysis of randomly generated binary constraint satisfaction problems［J］.Theoretical Computer Science，2003，290（3）：1815-1828.

［2］Creignou N，Daudé H.The SAT-UNSAT transition for random constraint satisfaction problems［J］.Discrete Mathematics，2009，309（8）：2085-2099.

［3］Pearl J.Probabilistic reasoning in intelligent systems［M］.San Francisco，CA：Morgan Kaufmann Publishers，1988：552.

［4］Braunstein A，Mézard M，Zecchina R.Survey propagation：an algorithm for satisfiability［J］.Random Structures amp; Algorithms，2005，27（2）：201-226.

［5］Maneva E，Mossel E，Wainwright M J.A new look at survey propagation and its generalizations［J］.Journal of the ACM，2007，54（4）：17-es.

［6］Yedidia J S，Freeman W T，Weiss Y.Understanding belief propagation and its generalizations［J］.Exploring Artificial Intelligence in the New Millennium，2003，8：236-239.

［7］Braunstein A，Zecchina R.Survey and belief propagation on random k-SAT［M］//Giunchiglia E，Tacchella A.Theory and Applications of Satisfiability Testing.Berlin：Springer，2003：519-528.

［8］Meng Xiangyu，Chen Tongwen.Event based agreement protocols for multi-agent networks［J］.Automatica，2013，49（7）：2125-2132.

［9］Weiss Y，Freeman W T.Correctness of belief propagation in Gaussian graphical models of arbitrary topology［J］.Neural Computation，2001，13（10）：2173-2200.

［10］Fan Yuan，Feng Gang，Wang Yong，et al.Distributed event-triggered control of multi-agent systems with combinational measurements［J］.Automatica，2013，49（2）：671-675.

［11］Su Qinliang，Wu Y C.Convergence analysis of the variance in Gaussian belief propagation［J］.IEEE Trans on Signal Processing，2014，62（19）：5119-5131.

［12］Su Qinliang，Wu Y C.On convergence conditions of Gaussian belief propagation［J］.IEEE Trans on Signal Processing，2015，63（5）：1144-1155.

［13］Malioutov D M，Johnson J K，Willsky A S.Walk-sums and belief propagation in Gaussian graphical models［J］.The Journal of Machine Learning Research，2006，7：2031-2064.

［14］Moallemi C C，Van Roy B.Convergence of min-sum message-passing for convex optimization［J］.IEEE Trans on Information Theory，2010，56（4）：2041-2050.

［15］Heskes T.On the uniqueness of loopy belief propagation fixed points［J］.Neural Computation，2004，16（11）：2379-2413.

［16］王曉峰，許道云，姜久雷，等.調查傳播算法收斂的一個充分條件［J］.中國科學：信息科學，2017，47（12）：1646-1661. （Wang Xiaofeng，Xu Daoyun，Jiang Jiulei，et al.Sufficient conditions for convergence of the survey propagation algorithm［J］.Science in China：Information Sciences，2017，47（12）：1646-1661.）

［17］Biere A，Sinz C.Decomposing SAT problems into connected components［J］.Journal on Satisfiability，Boolean Modeling and Computation，2006，2（1-4）：201-208.

［18］Li Angsheng，Pan Yicheng.Structural information and dynamical complexity of networks［J］.IEEE Trans on Information Theory，2016，62（6）：3290-3339.

［19］Zhang Zaijun，Xu Daoyun，Zhou Jincheng.A structural entropy mea-surement principle of propositional formulas in conjunctive normal form［J］.Entropy，2021，23（3）：article No.303.

［20］Newsham Z，Ganesh V，Fischmeister S，et al.Impact of community structure on sat solver performance［C］//Proc of International Confe-rence on Theory and Applications of Satisfiability Testing.Berlin：Springer，2014：252-268.

［21］Ansótegui C，Bonet M L，Giráldez-Cru J，et al.Community structure in industrial SAT instances［J］.Journal of Artificial Intelligence Research，2019，66：443-472.

［22］Sinz C.Visualizing the internal structure of SAT instances（preliminary report）［C］//Proc of the 7th International Conference on Theory and Applications of Satisfiability Testing.2004：345-350.

［23］Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks［J］.Journal of Statistical Mechanics：Theory and Experiment，2008，2008（10）：P10008.

［24］Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：026113.