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

GNN 是近年來非常火的一個領域。最近，一篇 Nature 子刊論文提出了一種用 GNN 解決組合優化問題的方法，并聲稱該 GNN 優化器的性能與現有的求解器相當，甚至超過了現有的求解器。不過，這篇論文引來了一些質疑：有人指出，這個 GNN 的性能其實還不如經典的貪心算法，而且速度還比貪心算法慢得多（對于有一百萬個變量的問題，貪心算法比 GNN 快 104 倍）。所以質疑者表示，「我們看不出有什么好的理由用這些 GNN 來解決該問題，就像用大錘砸堅果一樣。」他們希望這些論文作者能夠在宣稱方法優越性之前，先和困難問題的基準比較一下。

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

論文地址：https://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 ），類似于迫擊炮打蚊子」，既浪費資源，效果也不好。

論文地址：https://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 等人提出的優化器）不滿足上述要求，并且無法與簡單的標準算法競爭以解決困難的優化問題。探究神經網絡是否可以滿足這一要求，或者它們的失敗是否有更深層次的原因，這一點至關重要。