大模型執(zhí)行圖推理任務(wù)，我們是希望大模型僅僅給出結(jié)果，還是在給出準(zhǔn)確答案的同時(shí)，輸出詳細(xì)的推理過程？

先來(lái)看GPT-4的表現(xiàn)：

給出了一個(gè)非常簡(jiǎn)短且錯(cuò)誤的答案（判斷該圖中沒有環(huán)），這可能是由于模型在處理長(zhǎng)輸入時(shí)的局限性，或者是對(duì)圖的復(fù)雜結(jié)構(gòu)理解錯(cuò)誤所致。這顯示了大型模型在適應(yīng)圖論問題時(shí)面臨的挑戰(zhàn)。

相比之下，港科大團(tuán)隊(duì)開發(fā)的GraphWiz不僅給出了正確的答案，還提供了一條清晰且詳細(xì)的推理路徑。

圖片

GraphWiz 的設(shè)計(jì)目的是提升目前開源的大型模型在解決各種圖推理任務(wù)時(shí)的能力：

通過對(duì)大型模型進(jìn)行針對(duì)性的微調(diào)，處理不同復(fù)雜度的圖推理任務(wù)，并同時(shí)輸出明確而連貫的推理路徑。

對(duì)于人類來(lái)說，要在這樣規(guī)模的圖中檢測(cè)環(huán)是極具挑戰(zhàn)性的。通常，人類需要借助外部工具或花費(fèi)大量時(shí)間來(lái)完成這一任務(wù)，因?yàn)閮H僅依靠腦力計(jì)算是不切實(shí)際的。

這突顯了GraphWiz在空間推理和記憶保持方面的能力。它表明，該模型已經(jīng)有效地吸收了圖論的基本原理，并能夠自主地在大規(guī)模且復(fù)雜的圖結(jié)構(gòu)中進(jìn)行導(dǎo)航和推理。GraphWiz在處理復(fù)雜圖問題方面的能力，證明了其在實(shí)際應(yīng)用中的巨大潛力。

總的來(lái)說，本篇文章的主要貢獻(xiàn)如下：

• 創(chuàng)建了GraphInstruct，一個(gè)大規(guī)模的數(shù)據(jù)集，用于訓(xùn)練語(yǔ)言模型處理圖任務(wù)，并提供清晰推理路徑，提高可解釋性。
• 推出了GraphWiz，一個(gè)開源的大型語(yǔ)言模型，擅長(zhǎng)通過明確推理解決各種圖問題，性能優(yōu)于GPT-4。
• 研究了訓(xùn)練數(shù)據(jù)量和DPO框架下采樣策略等對(duì)模型性能的影響，并探索了GraphWiz跨任務(wù)遷移的能力，為后續(xù)模型優(yōu)化和性能提升提供指導(dǎo)。

圖推理任務(wù)介紹

在本研究中，團(tuán)隊(duì)精心挑選了九種不同計(jì)算復(fù)雜度層次的圖問題，涵蓋了研究的廣度和深度，包括：

• 四個(gè)線性復(fù)雜度任務(wù)：連通性和環(huán)檢測(cè)、二分圖檢驗(yàn)、拓?fù)渑判颍?/li>
• 三個(gè)多項(xiàng)式復(fù)雜度任務(wù)：最短路徑、最大三角形和、最大流；
• 以及兩個(gè)NP完全任務(wù)：哈密爾頓路徑和子圖匹配。

圖片

通過選擇這九個(gè)圖問題，團(tuán)隊(duì)的工作從簡(jiǎn)單到復(fù)雜、可解到難解的問題上進(jìn)行了全面的圖論探索。這種多樣化的選擇不僅有助于團(tuán)隊(duì)理論上理解圖算法，而且還能解決廣泛的實(shí)際應(yīng)用問題。

GraphInstruct數(shù)據(jù)集構(gòu)建

圖片

GraphInstruct的構(gòu)建包括以下幾個(gè)關(guān)鍵步驟：

圖問題生成。為了打造一個(gè)多樣而具挑戰(zhàn)性的圖問題庫(kù)以供模型訓(xùn)練與測(cè)試之用，團(tuán)隊(duì)通過編程輔助的方法，為每一種預(yù)設(shè)的任務(wù)生成隨機(jī)圖問題。團(tuán)隊(duì)為每一個(gè)任務(wù)設(shè)計(jì)了獨(dú)特的模板，以捕捉圖的特有屬性，例如圖是有向還是無(wú)向，邊是否有權(quán)重等。隨機(jī)圖的生成團(tuán)隊(duì)采用了Erd?s-Rényi（ER）模型。

顯式推理路徑生成。GraphInstruct為每一個(gè)圖問題對(duì)都配備了一條顯式推理路徑?？紤]到手動(dòng)標(biāo)注這些圖任務(wù)的推理路徑既復(fù)雜又耗時(shí)，團(tuán)隊(duì)選擇利用GPT-4來(lái)生成初步的推理路徑。

數(shù)據(jù)增強(qiáng)與拒絕采樣。由于觀察到GPT-4在許多圖任務(wù)上的表現(xiàn)欠佳，比如在初始數(shù)據(jù)集中的最大流任務(wù)上自由不足100個(gè)樣本是正確的，團(tuán)隊(duì)采用了拒絕采樣策略來(lái)增廣數(shù)據(jù)集，以包含更多樣的推理路徑。

挑選多樣化的推理路徑。這個(gè)步驟需要在準(zhǔn)確度和多樣性之間找到平衡。為此，團(tuán)隊(duì)采用了一系列精細(xì)化策略，這些策略分為基于字符串和基于語(yǔ)義的方法，用以篩選出不同的生成推理路徑。

GraphWiz訓(xùn)練

圖片

基于GraphInstruct，團(tuán)隊(duì)訓(xùn)練了GraphWiz，旨在優(yōu)化當(dāng)前大模型解決圖問題并給出顯式推理路徑的能力。GraphWiz的訓(xùn)練方法是一個(gè)創(chuàng)新的兩階段過程：

混合任務(wù)指令調(diào)優(yōu)（Mixed-Task Instruction Tuning）：在第一階段，團(tuán)隊(duì)專注于提升模型解釋和解決各種圖問題的能力。通過這種方法，GraphWiz學(xué)習(xí)處理包括理解問題、識(shí)別圖的屬性、應(yīng)用圖算法等在內(nèi)的多個(gè)子任務(wù)。

直接偏好優(yōu)化對(duì)齊（Direct Preference Optimization Alignment ）：第二階段，團(tuán)隊(duì)通過訓(xùn)練模型區(qū)分更有效與不太有效的問題解決路徑來(lái)進(jìn)一步銳化模型的推理能力。DPO對(duì)齊使模型能夠識(shí)別和生成更理想的推理路徑，從而提高解決問題的效率和準(zhǔn)確性。

GraphWiz性能評(píng)測(cè)

團(tuán)隊(duì)對(duì)GraphWiz進(jìn)行評(píng)估，旨在回答以下關(guān)鍵問題：

• Q1: GraphWiz在不同復(fù)雜度的圖問題上的表現(xiàn)如何，特別是與目前最強(qiáng)大的閉源模型GPT-4相比如何？
• Q2: 訓(xùn)練數(shù)據(jù)量的變化對(duì)GraphWiz的性能有什么影響？
• Q3: GraphWiz 對(duì)不同圖問題的遷移能力如何？
• Q4: 圖中節(jié)點(diǎn)數(shù)量的變化會(huì)如何影響GraphWiz的性能？此外，它能有效處理的最復(fù)雜的圖是多大的？
• Q5: 超參數(shù)?如何影響模型性能？

圖片

從上表中可以看出，團(tuán)隊(duì)的模型在各種開源模型上展示出了卓越的結(jié)果，顯著超過了GPT-4的性能。這一點(diǎn)在從簡(jiǎn)單到困難類別的各種任務(wù)中都保持一致。DPO進(jìn)一步提高了模型平均性能。然而，DPO可能對(duì)特定任務(wù)有不利影響。這表明，雖然DPO通常有助于改善模型推理，但可能需要進(jìn)一步調(diào)整，以避免對(duì)某些問題類型產(chǎn)生負(fù)面影響。

圖片

根據(jù)上表，團(tuán)隊(duì)觀察到隨著訓(xùn)練語(yǔ)料庫(kù)的增加，兩個(gè)模型都有效果的提升，比如GraphWiz (Mistral-7B)的平均準(zhǔn)確率從1:1比率的46.56％上升到1:5比率的53.75％。這表明更多的多樣化推理路徑通常有利于模型解決圖推理問題的整體性能。

團(tuán)隊(duì)可以注意到在某些任務(wù)上，如三角形和漢密爾頓路徑問題，準(zhǔn)確性并沒有顯著提高，甚至隨著數(shù)據(jù)量的增加而略有下降。例如，GraphWiz (Mistral-7B) 在三角和問題上在1:1比率下的準(zhǔn)確性為47.00％，然后在1:5比率下降至38.75％。這可能表明了過擬合現(xiàn)象，即模型開始記住訓(xùn)練數(shù)據(jù)中的模式，這些模式并不適用于未見過的數(shù)據(jù)。

總之，雖然增加數(shù)據(jù)量和推理路徑的多樣性通?？梢詫?dǎo)致更好的模型性能，但在某些復(fù)雜任務(wù)中存在潛在的過擬合跡象，這強(qiáng)調(diào)了需要仔細(xì)設(shè)計(jì)模型訓(xùn)練，并對(duì)不同的圖問題任務(wù)進(jìn)行驗(yàn)證，以確保廣泛的泛化能力。

圖片

為了探索GraphWiz在不同圖任務(wù)中的遷移能力，團(tuán)隊(duì)建立了一個(gè)額外的模型變體：GraphWiz-High。這個(gè)模型僅在兩個(gè)高復(fù)雜度（NP-完全）圖任務(wù)上進(jìn)行訓(xùn)練：漢密爾頓路徑和子圖匹配。為了研究其遷移能力，團(tuán)隊(duì)進(jìn)行了兩個(gè)比較實(shí)驗(yàn)：

高復(fù)雜度任務(wù)比較。團(tuán)隊(duì)首先將GraphWiz-High與常規(guī)的GraphWiz在高復(fù)雜度任務(wù)上進(jìn)行比較。上圖(a)表明GraphWiz的表現(xiàn)更好，驗(yàn)證了混合任務(wù)訓(xùn)練的有效性。這個(gè)結(jié)果也表明模型能夠?qū)钠渌蝿?wù)學(xué)到的知識(shí)轉(zhuǎn)移到特定的高復(fù)雜度任務(wù)上。

零樣本遷移能力。團(tuán)隊(duì)進(jìn)一步測(cè)試GraphWiz-High在從未訓(xùn)練過的低和中復(fù)雜度任務(wù)上的零樣本遷移能力。如上圖 (b) 所示，GraphWiz-High與Mistral-Base相比有顯著的性能提升。即使與ChatGPT相比，團(tuán)隊(duì)的模型也能保持相當(dāng)?shù)男阅堋？紤]到ChatGPT和GraphWiz-High之間在參數(shù)數(shù)量上的巨大差異，這表明團(tuán)隊(duì)的模型具有值得稱贊的跨任務(wù)泛化能力，展示了實(shí)際應(yīng)用的重大潛力。

圖片

為了解答關(guān)于模型性能如何隨著不同圖大小變化的問題，以及確定模型能夠有效解決的最大圖大小，團(tuán)隊(duì)在上圖展示了GraphWiz在表現(xiàn)最佳任務(wù)（a）環(huán)檢測(cè)和最差任務(wù)（b）最短路徑上的性能。

從圖中，團(tuán)隊(duì)得出以下結(jié)論：

GraphWiz和GPT-4在圖的大小增加時(shí)都表現(xiàn)出性能的下降。然而，團(tuán)隊(duì)的模型在大多數(shù)時(shí)候當(dāng)圖大小上一致時(shí)優(yōu)于GPT-4，這表明了對(duì)圖結(jié)構(gòu)更強(qiáng)大的理解和處理能力。

團(tuán)隊(duì)觀察到在最短路徑上，隨著節(jié)點(diǎn)數(shù)的增加，性能顯著下降。這種下降很可能可以歸因于兩個(gè)主要因素：該任務(wù)要求高推理和記憶能力，因?yàn)楦邥r(shí)間復(fù)雜性，以及強(qiáng)大的計(jì)算技巧，這可能對(duì)模型的容量構(gòu)成額外挑戰(zhàn)。實(shí)際上，團(tuán)隊(duì)發(fā)現(xiàn)兩種模型主要依賴枚舉來(lái)得出解決方案。因此，隨著圖大小的增加，所需的枚舉推理呈指數(shù)級(jí)增長(zhǎng)，導(dǎo)致當(dāng)節(jié)點(diǎn)數(shù)超過60后，準(zhǔn)確率顯著下降，之后幾乎不再有準(zhǔn)確性。

這些觀察表明，盡管GraphWiz在處理與圖相關(guān)的任務(wù)方面明顯優(yōu)于GPT-4，但存在一個(gè)復(fù)雜度的閾值——特別是在需要超出簡(jiǎn)單推理的計(jì)算的任務(wù)中——即使是最先進(jìn)的模型的性能也開始顯著下降。

圖片

最后，團(tuán)隊(duì)還探究了參數(shù)?對(duì)模型效果的影響。團(tuán)隊(duì)觀察到，較高的 ?似乎在一定程度上有利于困難任務(wù)的性能，但這并非嚴(yán)格的線性關(guān)系，并且在不同的模型大小之間也不一致。這表明，仔細(xì)調(diào)整 ? 對(duì)于在不同難度任務(wù)之間取得最佳平衡，提高模型的整體準(zhǔn)確性是必要的。

更多樣例

團(tuán)隊(duì)還展示了更多不同任務(wù)上GraphWiz的推理樣例。

連通性任務(wù)：

圖片

漢密爾頓路徑任務(wù)：

圖片

最短路徑任務(wù)：

圖片

子圖匹配任務(wù)：

圖片

論文鏈接：https://arxiv.org/abs/2402.16029項(xiàng)目主頁(yè)：https://graph-wiz.github.io/