圖神經網絡發Nature子刊，卻被爆比普通算法慢104倍，質疑者：灌水新高度？

近年來，神經網絡解決了應用和基礎科學方面的諸多難題，其中就包括離散組合優化問題，這也是我們理解計算極限的基礎。

Martin JA Schuetz 等人 2022 年的研究《Combinatorial optimization with physics-inspired graph neural networks》[4]提出使用受物理啟發的無監督圖神經網絡（GNN）來解決圖上的組合優化問題，這種方法似乎很有前途，並發表在具有高影響力的期刊（《自然 · 機器智能》）上。該研究測試了 GNN 在兩個標準優化問題上的性能：最大切割和最大獨立集（MIS）。這種新提出的 GNN優化器有一個非常好的特性：它可以擴展到許多更大的實例問題上。

論文地址：http://arxiv.org/pdf/2107.01188.pdf

不過，最近一篇新論文《Cracking nuts with a sledgehammer: when modern graph neural networks do worse than classical greedy algorithms》對 Martin JA Schuetz 等人的研究提出了質疑，認為 Martin JA Schuetz 等人提出的 GNN優化器是「用大錘敲堅果（ Cracking nuts with a sledgehammer ），類似於迫擊炮打蚊子」，既浪費資源，效果也不好。

論文地址：http://arxiv.org/abs/2206.13211

MIS 問題的定義如下：給定一個具有 n 個節點、度固定為 d 的無向隨機正則圖（d-RRG），獨立集（IS）是指不包含任何最近鄰對的頂點子集；MIS 問題需要找到最大的 IS，其大小稱為α。MIS 是一個 NP-hard 問題，但人們希望找到一種算法，以在多項式時間內找到一個大小盡可能接近最大值的 IS。此外，一個好算法不應因為 n 值較大而性能降低。

Martin JA Schuetz 等人提出的新型 GNN 可以為非常大的圖（n≤ 10^6）找到 IS：算法運行時間與問題大小成比例：t∼ n^1.7，並且算法性能隨着 n 的增加保持穩定，如下圖 1 所示。

然而，當將所提 GNN 與其他可用算法進行性能比較時，該研究僅與 Boppana-Halldorsson（BH）近似算法 [8] 做了比較，該算法在 n≤ 500 時，運行時間 t∼n^2.9。

實際上還有許多其他計算 IS 的算法比 BH 快得多，該研究應該將所提 GNN優化器與這些算法進行比較。其中，最簡單的算法就是貪心算法（GA）[9]。基於度的貪心算法（DGA）經過優化後，運行時間幾乎與節點數目 n 呈線性關係。

該研究比較了 Martin JA Schuetz 等人提出的 GNN優化器（空心）和 DGA（實心）在 d=3 和 d=5 的 d-RRG 上查找 MIS 的性能。 如圖 1（右）所示，從運行時間與問題大小（節點數）的關係上看，DGA 比 GNN 好得多，前者的運行時間幾乎與節點數 n 呈線性關係（指數是 1.15 可能是由於預漸近效應），而 GNN 的運行時間與節點數 n 幾乎呈二次關係。

該研究認為 Martin JA Schuetz 等人的主張「基於圖神經網絡的優化器的性能與現有的求解器相當或優於現有的求解器，具有超越當前 SOTA 模型的能力，能夠擴展到具有數百萬個變量的問題」，經不起推敲，與實際實驗結果不一致，Martin JA Schuetz 等人應對論文予以修改。

該研究詳細闡明瞭 DGA 的性能，並認為這種簡單的貪心算法應該被視為一個最低基準，任何新算法的性能必須至少比 DGA 好才能被採用。

當然，DGA 只是一種極為簡單的算法，還有許多其他標準算法優於 DGA。Maria Chiara 等人 2019 年的論文《Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs》對多個解決 MIS 問題的算法性能進行了深入的研究。

基於此，該研究提出一個問題：「評估一個新的優化算法時，應該用什麼真正困難的問題作為測試算法性能的基準？」

例如，該研究認為，在 d<16 的 d-RRG 中找出 MIS 可能只是一個容易的問題；對於較大的 d，優化的要求可能會更高，因為較大 IS 的聚類可能會給搜索 MIS 的算法帶來障礙。因此，如果要選擇作為基準的困難問題，一個可能的答案是研究 d>16 的 d-RRG 上的 MIS。這裏可以將 d=20 和 d=100 的結果與 2019 年論文《Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs》中給出的結果進行比較。

顯然，一個好的優化算法應該在 n 的多項式時間內完成，如果呈線性關係就更好了，找到的解的質量應優於簡單的現有算法，並且不應隨着 n 的增加而質量有所下滑。

該研究總結道：目前，基於神經網絡的優化器（如 Martin JA Schuetz 等人提出的優化器）不滿足上述要求，並且無法與簡單的標準算法競爭以解決困難的優化問題。探究神經網絡是否可以滿足這一要求，或者它們的失敗是否有更深層次的原因，這一點至關重要。