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

近年來，神經(jīng)網(wǎng)絡(luò)解決了應(yīng)用和基礎(chǔ)科學(xué)方面的諸多難題，其中就包括離散組合優(yōu)化問題，這也是我們理解計(jì)算極限的基礎(chǔ)。

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

論文地址：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 等人的研究提出了質(zhì)疑，認(rèn)為 Martin JA Schuetz 等人提出的 GNN 優(yōu)化器是「用大錘敲堅(jiān)果（ Cracking nuts with a sledgehammer ），類似于迫擊炮打蚊子」，既浪費(fèi)資源，效果也不好。

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

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

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

?

然而，當(dāng)將所提 GNN 與其他可用算法進(jìn)行性能比較時(shí)，該研究僅與 Boppana-Halldorsson（BH）近似算法 [8] 做了比較，該算法在 n≤ 500 時(shí)，運(yùn)行時(shí)間 t～n^2.9。?

實(shí)際上還有許多其他計(jì)算 IS 的算法比 BH 快得多，該研究應(yīng)該將所提 GNN 優(yōu)化器與這些算法進(jìn)行比較。其中，最簡單的算法就是貪心算法（GA）[9]。基于度的貪心算法（DGA）經(jīng)過優(yōu)化后，運(yùn)行時(shí)間幾乎與節(jié)點(diǎn)數(shù)目 n 呈線性關(guān)系。?

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

該研究認(rèn)為 Martin JA Schuetz 等人的主張「基于圖神經(jīng)網(wǎng)絡(luò)的優(yōu)化器的性能與現(xiàn)有的求解器相當(dāng)或優(yōu)于現(xiàn)有的求解器，具有超越當(dāng)前 SOTA 模型的能力，能夠擴(kuò)展到具有數(shù)百萬個(gè)變量的問題」，經(jīng)不起推敲，與實(shí)際實(shí)驗(yàn)結(jié)果不一致，Martin JA Schuetz 等人應(yīng)對論文予以修改。?

該研究詳細(xì)闡明了 DGA 的性能，并認(rèn)為這種簡單的貪心算法應(yīng)該被視為一個(gè)最低基準(zhǔn)，任何新算法的性能必須至少比 DGA 好才能被采用。

當(dāng)然，DGA 只是一種極為簡單的算法，還有許多其他標(biāo)準(zhǔn)算法優(yōu)于 DGA。Maria Chiara 等人 2019 年的論文《Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs》對多個(gè)解決 MIS 問題的算法性能進(jìn)行了深入的研究。?

基于此，該研究提出一個(gè)問題：「評估一個(gè)新的優(yōu)化算法時(shí)，應(yīng)該用什么真正困難的問題作為測試算法性能的基準(zhǔn)？」

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

顯然，一個(gè)好的優(yōu)化算法應(yīng)該在 n 的多項(xiàng)式時(shí)間內(nèi)完成，如果呈線性關(guān)系就更好了，找到的解的質(zhì)量應(yīng)優(yōu)于簡單的現(xiàn)有算法，并且不應(yīng)隨著 n 的增加而質(zhì)量有所下滑。

該研究總結(jié)道：目前，基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化器（如 Martin JA Schuetz 等人提出的優(yōu)化器）不滿足上述要求，并且無法與簡單的標(biāo)準(zhǔn)算法競爭以解決困難的優(yōu)化問題。探究神經(jīng)網(wǎng)絡(luò)是否可以滿足這一要求，或者它們的失敗是否有更深層次的原因，這一點(diǎn)至關(guān)重要。