Erdős goes neural： unsupervised learning of combinatorial algorithms with neural networks

https：//

arxiv。org/pdf/2006。1064

3。pdf

部落格：Erdős goes neural： unsupervised learning of combinatorial algorithms with neural networks

程式碼：Stalence/erdos_neu

重點：無監督、GNN、橋接離散和連續最佳化的loss engineering和smart encoding

監督學習for COP(組合最佳化問題)的陷阱：

得到的output離整數有一段距離（比如和0。5比較近）；如果直接離散化可能不滿足約束或者長時間梯度為0（連續值一直在變但離散化後的值有好一段時間不變，所以如果loss和離散化後的輸出有關則可能長時間不變。如果loss只和連續值輸出有關，則不能代表我們對離散解要求的約束。總之，在設計loss的過程中，一直有梯度和鼓勵約束滿足可能很難完美兼得）……

所以，我們需要進行loss engineering（比如在loss上增加一個熵正則化項以鼓勵遠離0。5的解，這可能有助於緩解僵局但還是不能保證約束滿足）和smart encoding（用一些非學習的演算法如啟發式演算法充當後處理機制，不過這可能還是遠不能保證找到最優解）。

《Erdős goes neural： unsupervised learning of combinatorial algorithms with neural networks》nips2020則

打算用Erdős提出的機率方法來彌補離散世界和連續世界的鴻溝，由GNN學習機率分佈，並想辦法將約束納入上述學習正規化中。

（emmm，看上到涉及機率的方法，我馬上想起CEM交叉熵（一種進化演算法）以及belief propagation或者說message passing，如果考慮約束則還要加入一些tricks，如果大規模，則可以考慮並行化。我做實驗的時候感覺它們在大規模問題和像二次分配問題這種比較困難的COP的表現不是很...如果客官自己做實驗覺得效果不錯，歡迎和本“工程小學生”交流）

1。 Erdos probabilistic method for deep learning

我們專注於加權圖G =（V，E，w）上的約束組合最佳化問題（eg：最大團和最小頂點覆蓋問題）：

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

1.1 The “Erdos Goes Neural” pipeline

與其直接最佳化不可微問題（1），我們打算訓練GNN來識別具有provably advantageous properties的解的分佈，用Erdős提出的機率方法來彌補離散世界和連續世界的鴻溝。

如圖1所示，新方法包括三步：

1。構造一個GNN gθ以輸出集合上的分佈D =gθ（G）；

2。訓練gθ以最佳化“存在較小成本f（S ∗； G）的可行S ∗〜D”的機率；

3。透過條件期望的方法確定性地從D中恢復S ∗。

There are several possibilities in instantiating D。 我們選擇最簡單的方法，並假設vi是否屬於S由以pi為期望的伯努利隨機變數xi決定。 網路可透過為每個節點vi計算pi來瑣碎地對D引數化。 保持分佈簡單將有助於我們稍後輕鬆控制相關的機率估計。

接下來，我們討論如何訓練gθ以及如何從D中恢復S ∗：

1.2 機率損失函式的匯出

新方法的主要挑戰在於靈活+可微分地訓練gθ。

1.2.1機率損失

先考慮無約束的情況來熱熱身。

為訓練網路，我們先構造一個滿足以下條件的損失函式l（D； G）

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

l的構造取決於f的結構，我們可以使用Any number of tail inequalities來例項化這種損失l。

如果僅假設f非負，則由馬爾可夫不等式，可設

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

如果不能以封閉形式計算期望，則用任何上限作為loss function也足夠。

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

1.2.2 機率懲罰損失

在1。2。1基礎上加入一個針對約束的懲罰項，

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

當f非負時可證明

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

1.2.3 線性box constraints的特殊情況

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

其中ai、bl、bh是非負標量。

我們用兩步法解決問題（4）。

用D0表示由gnn預測的集合的分佈，

p_{1}^{0}, \ldots, p_{n}^{0}

是引數化D0的機率。 現在rescale這些機率以（in expectation）滿足約束：

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

儘管上式非線性，我們可透過D。2節中的簡單迭代方案來執行上述rescale，然後按1。2。1中的方法利用機率損失函式來保證存在良好的unconstrained solution。我們證明了

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

1.3 Retrieving integral solutions

從學習的分佈D中檢索低成本 integral solution S ∗的簡單方法是蒙特卡洛抽樣。 如果S *〜D的機率為t，則我們可在前k個樣本中以至少1-（1- t）^k的機率找到效能等於或優於 S ∗的解。 下面我們用條件期望方法確定性地獲得S ∗。

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

如果考慮約束，還是按照上圖的方法，只不過f變成了1。2。2中的f_p！

2。 Case studies

2。1最大團問題

一個clique是每兩兩不同的節點都相鄰的節點集。 最大團問題需要確定the clique of a given graph with the largest possible number of nodes：

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

Ωclique是G中的clique families，

w(S)=\sum_{v_{i}, v_{j} \in S} w_{i j}

是S的權重。

現在藉助1。2。2來匯出機率懲罰損失：

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

解碼clique

：訓練完gnn後，根據1。3順序解碼可行解。 或者透過用適當的upper bound替換one for each node的條件期望評估來加快計算速度。

2。2 Graph partitioning

find set P S ⊂ V such that cut（S） =

\sum_{v_{i} \in S, v_{j} \notin S} w_{i j}

is minimized，並且滿足約束

\operatorname{vol}(S)=\sum_{v_{i} \in S} d_{i} \in\left[v_{l}, v_{h}\right]

。

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

解碼cluster：

可透過取樣或1。3中的方法來獲取符合推論2的解。如果用1。3中的方法，linear box constraint can be practically enforced by terminating

before

the volume constraint gets violated~

3。 圖神經網路框架

圖同構網路（GIN）［81］+圖注意（GAT）［73］層。

此外，每個卷積層都配備了skip connections，批處理歸一化和圖大小歸一化［21］。

除了graph外，

Erdős goes neural：用圖神經網路無監督求解組合最佳化問題（

4。 Baselines

4。1最大團問題

三個神經網路方法：RUN-CSP（SotA無監督網路，包含對獨立集合的簡化和對貪婪啟發式演算法的無效解的後處理機制），Bomze GNN和MS GNN（後兩者儘管在構造上與鄂爾多斯GNN相同，但都是基於最大團問題的標準平滑鬆弛和平坦的0。5閾值離散化進行訓練的）。

三個離散最佳化演算法；

兩種整數規劃求解器。

4。2區域性割問題

略