[發明專利]一種基于圖深度學習的最小覆蓋集問題求解方法

在審

• 申請號: 202110553854.2
• 申請日: 2021-05-20
• 公開（公告）號: CN113361684A
• 公開（公告）日: 2021-09-07
• 發明（設計）人: 杜海舟;嚴宗
• 申請（專利權）人: 上海電力大學
• 主分類號: G06N3/04
• 分類號: G06N3/04;G06N3/08
• 代理公司: 南京禹為知識產權代理事務所(特殊普通合伙) 32272
• 代理人: 王曉東

本發明公開了一種基于圖深度學習的最小覆蓋集問題求解方法，包括：采用python中的networkx模塊生成輸入圖，結合頂點的狀態和入度出度信息初始化所述輸入圖的頂點特征；根據所述輸入圖生成規則，對所述輸入圖中的每個頂點的鄰居頂點進行采樣，來嵌入圖的結構信息；經過鄰居頂點采樣后，將鄰居頂點的特征傳播到當前的節點，對頂點向量采用拼接的操作，并對所述拼接操作后的頂點向量進行L2正則化處理；設置強化學習參數，基于正則化處理結果進行強化學習優化，求解最小覆蓋集。本發明的模型具有很好的擴展性，可用于大規模的現實場景。

技術領域

本發明涉及最小覆蓋集(Minimum Vertex Cover，MVC)，圖深度學習的技術 領域，尤其涉及一種基于圖深度學習的最小覆蓋集問題求解方法。

背景技術

MVC問題可以歸類為圖上的組合優化問題，在應用數學和理論計算機領域 中，圖組合優化是指在具有某些特性的有限集合中，按某種目標找出一個最優子 集的一類數學規劃方法。MVC可以定義為給定一個無向圖G(V，E)，找到頂點S∈ V的最小子集，使得圖中每一條邊都會入射到集合S里的至少一個頂點上。這是 一個經典的NP-Hard問題，理論上不存在多項式時間內的最優解，通常的求解 方法是設計一個啟發式的算法，需要根據特定的實例和領域內的知識，且算法的 誤差在較為大規模的圖上難以得到保證。近些年來由于圖神經網絡的發展，圖神 經網絡可以很好的利用圖結構特征，在一些頂點分類的實驗上取得比傳統方法 更好的結果，加上強化學習的崛起，使得結合圖神經網絡和強化學習來解決MVC這一NP-hard圖組合優化問題成為可能。

發明內容

本部分的目的在于概述本發明的實施例的一些方面以及簡要介紹一些較佳 實施例。在本部分以及本申請的說明書摘要和發明名稱中可能會做些簡化或省 略以避免使本部分、說明書摘要和發明名稱的目的模糊，而這種簡化或省略不能 用于限制本發明的范圍。

鑒于上述現有存在的問題，提出了本發明。

因此，本發明解決的技術問題是：傳統啟發式算法的誤差在較為大規模的圖 上難以得到保證。

為解決上述技術問題，本發明提供如下技術方案：采用python中的networkx 模塊生成輸入圖，結合頂點的狀態和入度出度信息初始化所述輸入圖的頂點特 征；根據所述輸入圖生成規則，對所述輸入圖中的每個頂點的鄰居頂點進行采樣， 來嵌入圖的結構信息；經過鄰居頂點采樣后，將鄰居頂點的特征傳播到當前的節 點，對頂點向量采用拼接的操作，并對所述拼接操作后的頂點向量進行L2正則 化處理；設置強化學習參數，基于正則化處理結果進行強化學習優化，求解最小 覆蓋集。

作為本發明所述的基于圖深度學習的最小覆蓋集問題求解方法的一種優選 方案，其中：所述結合頂點的狀態和入度出度信息初始化所述輸入圖的頂點特征 包括，

其中，x_v表示頂點的狀態，初始化都為O，d_i表示頂點的入度，d_o表示頂點 的出度。

作為本發明所述的基于圖深度學習的最小覆蓋集問題求解方法的一種優選 方案，其中：對所述輸入圖中的每個頂點的鄰居頂點進行采樣，來嵌入圖的結構 信息包括，

其中，t表示網絡的層數，也表示每個頂點所能捕捉的最遠跳數，取t＝2，AGGREGATE為聚合函數，這里取平均值

作為本發明所述的基于圖深度學習的最小覆蓋集問題求解方法的一種優選 方案，其中：所述對頂點向量采用拼接的操作包括，

其中，N(v)表示頂點v鄰居節點的集合，CONCAT表示頂點向量的拼接操 作，W^t表示第t層網絡的參數矩陣，σ表示非線性映射。