大規模符號網絡劃分的學習驅動型擴展變鄰域搜索算法

摘 要：給定一個無向圖，符號網絡劃分問題（signed graph partitioning problem，SGPP）是將節點集合劃分為K（K≥2）個互不相交的非空分組，旨在最小化所有位于分組內的負符號邊權重之和加上位于分組之間的正符號邊權重之和，使網絡劃分結構盡量趨于平衡。SGPP是NP難問題，在計算機視覺、社交網絡分析、生物信息學等實際領域中具有重要應用。但大數據時代的到來給求解大規模SGPP帶來一定的挑戰。因此，設計新穎且高效的學習驅動型擴展變鄰域搜索算法（learning driven extended variable neighborhood search，LDEVNS）來求解SGPP。具體來說，該算法設計全新的快速增量更新策略以及高效的擴展變鄰域搜索，同時結合強化學習機制來調整算法搜索過程中的前進方向，進一步探索更有希望的解空間區域來找到更高質量的求解方案。實驗部分使用15組大規模社交網絡圖來評估LDEVNS的高性能，實驗結果顯示，LDEVNS在求解質量和計算時間方面相較于當前表現最佳的算法具有顯著優勢，同時也驗證了強化學習在LDEVNS中的有效性。

關鍵詞：符號網絡劃分；啟發式；變鄰域搜索；強化學習

中圖分類號：TP181"" 文獻標志碼：A"" 文章編號：1001-3695（2025）03-017-0770-07

doi：10.19734/j.issn.1001-3695.2024.07.0309

Learning-driven extended variable neighborhood search forsigned graph partitioning

Tao Zijun，Lu Zhi，Meng Bingjin

（Business School，University of Shanghai for Science amp; Technology，Shanghai 200093，China）

Abstract：Given an undirected signed graph，the SGPP divides the set of nodes into K（K≥2）pairwise disjoint nonempty subsets to minimize the number of positive edges between the subsets and the number of negative edges within the subsets.The SGPP is an NP-hard problem with significant applications in real-world fields such as computer vision，social network analysis，bioinformatics，etc.However，the SGPP has become more challenging to address in the big data era.This paper proposed a learning driven extended variable neighborhood search（LDEVNS）to tackle the SGPP.Specifically，it designed a new fast incremental update strategy and an efficient extended variable neighborhood search.To explore the search space more efficiently，it combined a reinforcement learning mechanism to guide the search direction.The experiment utilized 15 large-scale social networks to assess the performance of the LDEVNS algorithm.Experimental results show that the LDEVNS outperforms the best-performing algorithms in terms of solution quality and computing time.Additionally，it verifies the effectiveness of the reinforcement learning mechanism in the LDEVNS.

Key words：signed network partitioning;heuristics;variable neighborhood search;reinforcement learning

0 引言

符號網絡起源于Heider［1］，是指邊具有正負符號屬性的網絡。其中，正符號邊表示友好關系，如朋友、信任、喜歡、支持等，通常使用正號“+”進行標識；負符號邊表示對立關系，例如敵人、不信任、討厭、反對等，通常使用負號“-”進行標識［2］。在社會、生物和信息等領域，許多復雜系統都明確包含著對立關系，例如，人際關系中的朋友與敵人［1］、國際關系中的合作與敵對［2］、生物領域中神經元之間的促進和抑制［3］以及信息領域中用戶在社交網站上表達信任或不信任態度［4］等。

結構平衡理論作為符號網絡研究的理論基礎，刻畫了符號網絡的主要結構和特征。Harary［5］將Heider［1］提出的結構平衡理論概念形式化，為描述社會關系正式引入了符號網絡的概念，為確定符號網絡整體結構奠定了基礎。Harary［5］最初考慮將符號網絡劃分為兩個互不相交的分組，并證明如果使得正符號邊在分組內，負符號邊在分組間，這個符號網絡就是平衡的。Davis［6］將分組擴展到任意數量，并證明當且僅當一個圖中所有環都是正符號環時該圖才是平衡的。然而，在大多數實際的社會符號網絡中，完美的平衡結構并不存在，通過對這些網絡劃分來研究其結構是十分必要的。

Davis［6］進一步闡述了當符號網絡的節點被劃分為K個分組時的K平衡屬性，并稱每個分組為一個聚類。隨后，研究者們開始從不同角度刻畫該聚類問題的數學模型。Doreian等人［7］將該問題形式化為符號網絡的廣義結構平衡劃分（gene-ralized structural balance partitioning），也稱為K劃分（K-balance partitioning）。為了描述一致，本文將它們統稱為符號網絡劃分問題（signed graph partitioning problem，SGPP）。Bansal等人［8］又將該問題表述為相關聚類（correlation clustering，CC）。具體來說，SGPP是將節點集合劃分為K（K≥2）個互不相交的非空分組，目標是使得所有正符號邊位于分組內，負符號邊位于分組間。SGPP被證明是NP難問題［7］，在大規模符號網絡中，上述完美的平衡結構劃分難以找到。因此，文獻中一般使用最小化劃分的不平衡程度（又稱誤差函數）來評估劃分網絡對平衡的接近程度，并已經出現了一些不同的目標函數，例如總體不一致性［7］、加權不一致性［7］、正（負）符號邊不一致性［7］、哈密頓［9］以及拉普拉斯［10］等。本文主要研究最具有代表性的基于總體不一致性［7］目標函數的SGPP，即通過最小化不同分組間的正符號邊權重之和，加上同一分組內的負符號邊權重之和，來找到符號網絡的一種結構最為平衡的劃分方案。

SGPP在一些實際領域中擁有廣泛應用，例如計算機視覺、社交網絡分析、生物信息學等。在計算機視覺領域，SGPP旨在將具有符號信息的圖像劃分為具有獨立語義的區域，這對于處理擁有復雜結構的圖像、符號或文本數據具有重要意義［11］。在社交網絡分析中，SGPP用于識別社交網絡中的不同社群，幫助人們更好地理解社交網絡中的社群結構、信息傳播等特性［12］。在生物信息學領域，蛋白質相互作用網絡被構建為符號網絡，通過劃分該網絡可以揭示蛋白質之間的功能和相互作用［13］。

對于SGPP求解方法的研究，早期主要集中在精確算法。Brusco等人［14］提出了分支定界算法，但僅能求解小于30個節點的符號網絡。Figueiredo等人［15］提出了更加通用的混合整數規劃。Aref等人［16］提出了整數線性規劃，并已成為求解SGPP使用最為廣泛的技術之一。盡管精確算法的研究取得了一定進展，但隨著社交網絡規模的逐漸增大，一些研究者們開始轉向更為高效的啟發式算法，力求在有限的時間范圍內快速找到問題的高質量求解方案，例如基于不同目標函數的重定位啟發式（relocation heuristic，RH）［7］、模因算法（memetic algorithm，MA）［17］、GRASP（greedy randomized adaptive search procedure）［18］、迭代局部搜索（iterated local search，ILS）［19～22］、貪心算法［23］等。Brusco等人［24］提出了兩階段搜索策略來求解基于總體不一致性的SGPP，第一階段使用RH獲得穩定初始解，第二階段使用禁忌搜索（tabu search，TS）或變鄰域搜索（variable neighborhood search，VNS）來進一步提升解的質量。

通過文獻可知，雖然現有方法在一定程度上解決了SGPP，但仍然存在一些明顯不足。SGPP求解方法的早期研究主要集中在針對中小規模問題的精確算法。近些年來，由于大規模問題數據量和復雜性的急劇增加，算法的時間復雜度成倍上升，精確算法因為計算復雜度的限制而變得不可行［21］。而啟發式算法在可接受的時間范圍內能夠找到足夠好的問題求解方案，是目前求解大規模問題的高效方法。文獻［19］指出，啟發式算法是求解大規模CC和SGPP的主要方法。因此，開發高效的啟發式算法是求解SGPP的最重要方向之一。通過文獻分析可知，基于總體不一致性目標函數的SGPP研究還較少，盡管已有一些嘗試，但針對該問題的啟發式算法研究仍然較為有限。Brusco等人［24］提出的VNS是目前最新且性能最好的啟發式算法，其通過在多種鄰域中進行搜索，避免算法陷入局部最優，但仍然存在一些不足。首先，該算法在求解質量和算法效率之間無法取得平衡，難以保證劃分結果的準確性和高效性。其次，處理大規模符號網絡通常需要存儲和處理大量信息，該方法計算復雜度較高，限制了在實際應用中的可能性。因此，新方法需要在保證準確性的同時，提升算法的效率。強化學習（reinforcement learning，RL）［25，26］是通過與環境交互，基于反饋獎勵來逐步改進策略的前沿方法。RL具有自適應性，通過在不斷地試探和反饋過程中優化決策，其與啟發式算法相結合，能夠學習到高質量的解，進一步提高算法的性能。結合目前高效的VNS搜索策略與強大的RL學習能力，可以實現更加高效的優化框架，尤其適合解決大規模問題。因此，本文以符號網絡劃分的總體不一致性為優化目標，擬設計全新且高效的學習驅動型擴展變鄰域搜索算法（learning driven extended variable neighborhood search，LDEVNS）。該算法設計了全新的快速增量更新策略以及高效的擴展變鄰域搜索，并首次將VNS框架與強化學習相結合，利用分組信息指導算法的搜索方向來獲得高質量的求解方案。本文的實驗使用15組代表性的大規模社交網絡圖來評估LDEVNS的高性能，并與現有實驗結果最好的啟發式算法RH、TS和VNS［24］進行對比。實驗結果顯示，隨著分組數量K的逐漸增大，LDEVNS能夠快速獲得更高質量的求解方案，強化學習的加入也進一步提升了算法性能。

2.5 算法復雜度分析

LDEVNS算法主要由三部分組成：RH生成初始解、EVNS和強化學習機制。開始階段，算法生成初始解的時間復雜度為O（N·K）。然后算法進入while循環，首先EVNS由局部搜索和擾動兩部分組成。在局部搜索部分，鄰居解的評估和移動使用的是快速增量更新策略，時間復雜度為O（N·K）。在擾動部分，包括對Freq數組進行排序和選擇部分節點進行擾動兩部分，時間復雜度分別為O（N logN）和O（N）。因此，整個EVNS的時間復雜度為O（N logN+N·K）。然后是強化學習機制，其中分組選擇策略、學習概率更新技術和學習概率平滑技術的時間復雜度均為O（N·K）。因此，LDEVNS算法整體時間復雜度為O（N logN+N·K）。

3 實驗測試與分析

為了驗證本文所設計的LDEVNS算法的高性能，首先將LDEVNS與目前最好的參照算法RH、TS、VNS［24］進行實驗對比，然后分析強化學習機制的有效性，最后總結實驗結果。

3.1 測試算例

本文使用15組大規模社交網絡圖來評估所有算法的性能，它們均來自于公共數據集SNAP［28］（https：//snap.stanford.edu/data/）和KONECT［29］（http：//konect.cc/）。在進行實驗前，本文首先對數據集進行預處理，將其統一轉換為無向圖，并且確保圖中不包含平行邊和自環邊，具體方法為：首先移除圖中所有自環邊，然后將所有平行和相反方向的弧合并為一條無向邊，其權重為原有弧權重的總和［16］。預處理后的15組數據集如表1所示。這些圖的節點范圍為［3 783，138 592］，符號邊范圍為［14 081，1 461 058］，涵蓋了不同結構的大規模社交網絡圖，為算法的評估提供了全面且準確的數據基礎。

3.2 實驗平臺配置

為了公平地驗證所有算法的性能，本文采用相同的實驗運行環境測試提出的LDEVNS算法以及參照算法RH、TS和VNS。在硬件方面，處理器為Intel Xeon E5-2670 v4 processor（2.5 GHz，12 GB RAM），操作系統為Linux操作系統。在軟件方面，使用Python 3.8實現LDEVNS、RH、TS和VNS算法。需要注意的是，本文使用PyPy解釋器進行編譯，其是標準CPython解釋器的另一個版本，在處理長時間運行的純Python腳本時表現出色，特別適用于本文的計算密集型任務。本文的15組測試算例運行時間為［900，3 600］ s，每個算例都在不同的隨機數種子下運行10次，并記錄K∈［2，512］的結果，如表2所示。

3.3 參數設置

LDEVNS一共有2個參數：最大重啟次數L和擾動節點百分比Percent，如表3所示。為了分析參數對LDEVNS性能的影響，本文進行了參數敏感性分析實驗［30］。具體來說，本文首先根據前期實驗測試，經驗性地確定了每個參數的合理取值范圍，參數L的取值為［4 000，…，12 000］，參數Percent的取值為［0.05，…，0.25］。在此基礎上，通過改變一個參數并固定其他參數來在算例上進行測試，以結果判斷參數的取值。本文選取大小和難度較合適的數據集slashdot-undirected-size10000-part1進行調參，實驗運行配置與前述一致。

圖3和4是實驗結果的箱線圖，其中x軸表示參數取值，y軸表示10次測試結果的累積最好目標函數值的統計平均值Z（P）。同時，本文還采用了置信水平為95%的Friedman秩和檢驗來評估不同參數值樣本是否存在統計性差異。從圖3可以看出，參數L的變化對LDEVNS性能影響不明顯，其統計檢測結果也沒有表現出顯著性差異（p-value=0.07）。而從圖4可以看出，參數Percent的變化對LDEVNS性能有明顯影響，其在Percent=0.1處取得最好值，且其統計檢測結果在性能上存在顯著性差異（p-value=0.03）。因此，本文選取L=6 000，Percent=0.1作為參數的最終取值。

3.4 實驗結果

3.4.1 實驗結果比較與分析

表4～7為參照算法RH、TS、VNS和LDEVNS在15個大規模社交網絡圖上統計最好值Zbest、平均值Zavg、統計最差值Zworst以及達到最好值的統計平均時間t（s）的結果比較（詳細結果可參見https：//github.com/hellozhilu/LDEVNS/）。觀察表4～6的三個指標可以發現，在分區K=2和K=4時，LDEVNS的結果略差于VNS，但差距微小。而隨著K的逐漸增大，在8≤K≤512，LDEVNS性能明顯優于參照算法RH、TS、VNS。在運行時間方面，從表7可以看出，LDEVNS運行時間比RH、TS、VNS明顯更短。例如，當K=8時，LDEVNS在平均時間1 173.5 s可以達到統計平均最好值44 631.5，而VNS要在2 312.2 s才能達到最好值44 712.8。圖5～8的折線圖也進一步說明，LDEVNS雖然在K較小時結果略差于參照算法，但隨著K的逐漸變大和算法時間復雜度增大，LDEVNS明顯優于參照算法。綜上所述，LDEVNS在15組測試數據集上展現出了非常優異的性能，雖然在K較小時算法性能略低于參照算法，但當K逐漸變大時，在統計最好、平均、最差結果上，LDEVNS均優于參照算法，且其優勢在K越大時變得越明顯。在計算時間方面LDEVNS也更少，說明LDEVNS在解決大規模網絡時具有較好的求解性能、求解效率以及穩定性。

3.4.2 強化學習機制的有效性驗證

為了驗證強化學習在LDEVNS中的性能，本文對LDEVNS與未加入強化學習的REVNS進行對比實驗。其中，REVNS是將LDEVNS中的強化學習替換成了隨機重啟機制。本部分實驗運行配置與前述一致。表8為REVNS和LDEVNS在測試數據集soc-sign-bitcoinotc上的結果比較，包括每個算法在不同K值下的最好值Zbest、平均值Zavg、最差值Zworst、達到最好值的次數hit和達到最好值的平均時間t（s）。從表8可以看出，在K較小時（如K=2），LDEVNS的最好值和平均值和REVNS持平，但在K較大時（如4≤K≤512），LDEVNS的最好值明顯優于REVNS，平均值略好于REVNS。綜上所述，LDEVNS和REVNS在K較小時表現趨于一致，而當K逐漸變大時，LDEVNS整體效果更優。該現象說明強化學習對算法性能有著非常積極的影響，尤其當問題規模較大且對計算時間要求較高時，結合強化學習機制的LDEVNS性能越好。

4 結束語

符號網絡劃分問題（SGPP）是將節點集合劃分為K（K≥2）個互不相交的非空分組，旨在最小化所有位于分組內的負符號邊權重之和加上位于分組之間的正符號邊權重之和，使劃分網絡結構盡量趨向于平衡。SGPP是NP難問題，在計算機視覺、社交網絡分析、生物信息學等實際領域中具有重要應用。本文首次提出了新穎且高效的學習驅動型擴展變鄰域搜索算法（LDEVNS）來求解SGPP。具體來說，該算法設計了全新的快速增量更新策略以及高效的擴展變鄰域搜索，并結合強化學習機制來調整算法搜索過程中的前進方向，進一步探索更有希望的解空間區域并找到更高質量的求解方案。實驗部分使用了15組大規模社交網絡圖對算法性能進行評估和測試，并與目前文獻中最好的算法RH、TS、VNS進行對比。實驗結果顯示，LDEVNS明顯優于參照算法，特別當分區K越大時，LDEVNS在求解質量和時間方面均占據顯著優勢。本文還驗證了強化學習在LDEVNS中的有效性，結果表明當問題規模越大且計算時間要求越高時，LDEVNS的性能越好。在未來研究中，還可以進一步探索更高效的啟發式算法來求解更大規模的SGPP，考慮將算法應用到一些實際的工程問題中。

參考文獻：

［1］Heider F.Attitudes and cognitive organization［J］.The Journal of Psychology，1946，21：107-112.

［2］劉苗苗，扈慶翠，郭景峰，等.融合局部與全局緊密度的符號網絡鏈接預測算法［J］.計算機應用研究，2021，38（7）：2003-2008，2017.（Liu Miaomiao，Hu Qingcui，Guo Jingfeng，et al.Link prediction in signed networks based on local and global tightness［J］.Application Research of Computers，2021，38（7）：2003-2008，2017.）

［3］Parisien C，Anderson C H，Eliasmith C.Solving the problem of negative synaptic weights in cortical models［J］.Neural Computation，2008，20（6）：1473-1494.

［4］顏仕雄，朱焱，李春平.基于多頭注意力機制的社交網絡符號預測［J］.計算機應用研究，2021，38（5）：1360-1364.（Yan Shixiong，Zhu Yan，Li Chunping.Social network sign prediction based on multi-head attention mechanism［J］.Application Research of Compu-ters，2021，38（5）：1360-1364.）

［5］Harary F.On the notion of balance of a signed graph［J］.Michigan Mathematical Journal，1953，2（2）：143-146.

［6］Davis J A.Clustering and structural balance in graphs［J］.Human Relations，1967，20（2）：181-187.

［7］Doreian P，Mrvar A.A partitioning approach to structural balance［J］.Social Networks，1996，18（2）：149-168.

［8］Bansal N，Blum A，Chawla S.Correlation clustering［J］.Machine Learning，2004，56（1）：89-113.

［9］Xia Chengyi，Luo Yongping，Wang Li，et al.A fast community detection algorithm based on reconstructing signed networks［J］.IEEE Systems Journal，2022，16（1）：614-625.

［10］Ko T，Choi Y，Kim C K.A spectral graph convolution for signed directed graphs via magnetic Laplacian［J］.Neural Networks，2023，164：562-574.

［11］Kim S，Nowozin S，Kohli P，et al.Higher-order correlation clustering for image segmentation［C］//Proc of the 24th International Confe-rence on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2011：1530-1538.

［12］Altafini C.Dynamics of opinion forming in structurally balanced social networks［J］.PLoS One，2012，7（6）：e38135.

［13］DasGupta B，Enciso G A，Sontag E，et al.Algorithmic and complexity results for decompositions of biological networks into monotone subsystems［J］.Biosystems，2007，90（1）：161-178.

［14］Brusco M，Steinley D.K-balance partitioning：an exact method with applications to generalized structural balance and other psychological contexts［J］.Psychological Methods，2010，15（2）：145-157.

［15］Figueiredo R，Moura G.Mixed integer programming formulations for clustering problems related to structural balance［J］.Social Networks，2013，35（4）：639-651.

［16］Aref S，Mason A J，Wilson M C.An exact method for computing the frustration index in signed networks using binary programming［EB/OL］.（2016-11-28）.https：//arxiv.org/abs/1611.09030v1.

［17］Hausberger F，Fonseca M，Schulz C，et al.A distributed multilevel memetic algorithm for signed graph clustering［C］//Proc of Compa-nion Conference on Genetic and Evolutionary Computation.New York：ACM Press，2023：207-210.

［18］Wahid D F，Hassini E.A literature review on correlation clustering：cross-disciplinary taxonomy with bibliometric analysis［J］.Operations Research Forum，2022，3（3）：47.

［19］Levorato M，Figueiredo R，Frota Y，et al.Evaluating balancing on social networks through the efficient solution of correlation clustering problems［J］.EURO Journal on Computational Optimization，2017，5（4）：467-498.

［20］Queiroga E，Subramanian A，Figueiredo R，et al.Integer programming formulations and efficient local search for relaxed correlation clustering［J］.Journal of Global Optimization，2021，81（4）：919-966.

［21］伍康，夏維，王子源.一種基于圖神經網絡的改進鄰域搜索算法［J］.計算機應用研究，2024，41（5）：1402-1408.（Wu Kang，Xia Wei，Wang Ziyuan.Improved neighborhood search algorithm based on graph neural network［J］.Application Research of Computers，2024，41（5）：1402-1408.）

［22］Cordner N，Kollios G.An efficient local search algorithm for correlation clustering on large graphs［C］//Proc of International Conference on Combinatorial Optimization and Applications.Cham：Springer，2023：3-15.

［23］Soldatenko A，Semenova D，Ibragimova E.On heuristic algorithm with greedy strategy for the correlation clustering problem solution［C］//Proc of International Conference on Distributed Computer and Communication Networks：Control，Computation，Communications.Cham：Springer，2024：462-477.

［24］Brusco M J，Doreian P.Partitioning signed networks using relocation heuristics，tabu search，and variable neighborhood search［J］.Social Networks，2019，56：70-80.

［25］Zhou Yangming，Hao Jinkao，Duval B.Reinforcement learning based local search for grouping problems：a case study on graph coloring［J］.Expert Systems with Applications，2016，64：412-422.

［26］劉全，翟建偉，章宗長，等.深度強化學習綜述［J］.計算機學報，2018，41（1）：1-27.（Liu Quan，Zhai Jianwei，Zhang Zongchang，et al.A survey on deep reinforcement learning［J］.Chinese Journal of Computers，2018，41（1）：1-27.）

［27］Brimberg J，Salhi S，Todosijevic＇ R，et al.Variable neighborhood search：the power of change and simplicity［J］.Computers amp; Ope-rations Research，2023，155：106221.

［28］Jure L.SNAP datasets：Stanford large network dataset collection［EB/OL］.［2024］.http：//snap.stanford.edu/data 2014.

［29］Kunegis J.KONECT：the Koblenz network collection［C］//Proc of the 22nd International Conference on World Wide Web.New York：ACM Press，2013：1343-1350.

［30］Hamby D M.A review of techniques for parameter sensitivity analysis of environmental models［J］.Environmental Monitoring and Assessment，1994，32（2）：135-154.