大模型執行圖推理任務，我們是希望大模型僅僅給出結果，還是在給出準確答案的同時，輸出詳細的推理過程？
先來看GPT-4的表現：
給出了一個非常簡短且錯誤的答案（判斷該圖中沒有環），這可能是由於模型在處理長輸入時的侷限性，或者是對圖的複雜結構理解錯誤所致。這顯示了大型模型在適應圖論問題時面臨的挑戰。
相比之下，港科大團隊開發的GraphWiz不僅給出了正確的答案，還提供了一條清晰且詳細的推理路徑。
GraphWiz 的設計目的是提升目前開源的大型模型在解決各種圖推理任務時的能力：
通過對大型模型進行針對性的微調，處理不同複雜度的圖推理任務，並同時輸出明確而連貫的推理路徑。
對於人類來說，要在這樣規模的圖中檢測環是極具挑戰性的。通常，人類需要藉助外部工具或花費大量時間來完成這一任務，因為僅僅依靠腦力計算是不切實際的。
這突顯了GraphWiz在空間推理和記憶保持方面的能力。它表明，該模型已經有效地吸收了圖論的基本原理，並能夠自主地在大規模且複雜的圖結構中進行導航和推理。GraphWiz在處理複雜圖問題方面的能力，證明了其在實際應用中的巨大潛力。
總的來說，本篇文章的主要貢獻如下：
創建了GraphInstruct，一個大規模的數據集，用於訓練語言模型處理圖任務，並提供清晰推理路徑，提高可解釋性。
推出了GraphWiz，一個開源的大型語言模型，擅長通過明確推理解決各種圖問題，性能優於GPT-4。
研究了訓練數據量和DPO框架下采樣策略等對模型性能的影響，並探索了GraphWiz跨任務遷移的能力，為後續模型優化和性能提升提供指導。
圖推理任務介紹
在本研究中，團隊精心挑選了九種不同計算複雜度層次的圖問題，涵蓋了研究的廣度和深度，包括：
四個線性複雜度任務：連通性和環檢測、二分圖檢驗、拓撲排序；
三個多項式複雜度任務：最短路徑、最大三角形和、最大流；
以及兩個NP完全任務：哈密爾頓路徑和子圖匹配。
通過選擇這九個圖問題，團隊的工作從簡單到複雜、可解到難解的問題上進行了全面的圖論探索。這種多樣化的選擇不僅有助於團隊理論上理解圖算法，而且還能解決廣泛的實際應用問題。
GraphInstruct數據集構建
GraphInstruct的構建包括以下幾個關鍵步驟：
圖問題生成。為了打造一個多樣而具挑戰性的圖問題庫以供模型訓練與測試之用，團隊通過編程輔助的方法，為每一種預設的任務生成隨機圖問題。團隊為每一個任務設計了獨特的模板，以捕捉圖的特有屬性，例如圖是有向還是無向，邊是否有權重等。隨機圖的生成團隊採用了Erdős-Rényi（ER）模型。
顯式推理路徑生成。GraphInstruct為每一個圖問題對都配備了一條顯式推理路徑。考慮到手動標註這些圖任務的推理路徑既複雜又耗時，團隊選擇利用GPT-4來生成初步的推理路徑。
數據增強與拒絕採樣。由於觀察到GPT-4在許多圖任務上的表現欠佳，比如在初始數據集中的最大流任務上自由不足100個樣本是正確的，團隊採用了拒絕採樣策略來增廣數據集，以包含更多樣的推理路徑。
挑選多樣化的推理路徑。這個步驟需要在準確度和多樣性之間找到平衡。為此，團隊採用了一系列精細化策略，這些策略分為基於字符串和基於語義的方法，用以篩選出不同的生成推理路徑。
GraphWiz訓練
基於GraphInstruct，團隊訓練了GraphWiz，旨在優化當前大模型解決圖問題並給出顯式推理路徑的能力。GraphWiz的訓練方法是一個創新的兩階段過程：
混合任務指令調優（Mixed-Task Instruction Tuning）：在第一階段，團隊專注於提升模型解釋和解決各種圖問題的能力。通過這種方法，GraphWiz學習處理包括理解問題、識別圖的屬性、應用圖算法等在內的多個子任務。
直接偏好優化對齊（Direct Preference Optimization Alignment ）：第二階段，團隊通過訓練模型區分更有效與不太有效的問題解決路徑來進一步銳化模型的推理能力。DPO對齊使模型能夠識別和生成更理想的推理路徑，從而提高解決問題的效率和準確性。
GraphWiz性能評測
團隊對GraphWiz進行評估，旨在回答以下關鍵問題：
Q1: GraphWiz在不同複雜度的圖問題上的表現如何，特別是與目前最強大的閉源模型GPT-4相比如何？
Q2: 訓練數據量的變化對GraphWiz的性能有什麼影響？
Q3: GraphWiz 對不同圖問題的遷移能力如何？
Q4: 圖中節點數量的變化會如何影響GraphWiz的性能？此外，它能有效處理的最複雜的圖是多大的？
Q5: 超參數ß如何影響模型性能？
從上表中可以看出，團隊的模型在各種開源模型上展示出了卓越的結果，顯著超過了GPT-4的性能。這一點在從簡單到困難類別的各種任務中都保持一致。DPO進一步提高了模型平均性能。然而，DPO可能對特定任務有不利影響。這表明，雖然DPO通常有助於改善模型推理，但可能需要進一步調整，以避免對某些問題類型產生負面影響。
根據上表，團隊觀察到隨著訓練語料庫的增加，兩個模型都有效果的提升，比如GraphWiz (Mistral-7B)的平均準確率從1:1比率的46.56％上升到1:5比率的53.75％。這表明更多的多樣化推理路徑通常有利於模型解決圖推理問題的整體性能。
團隊可以注意到在某些任務上，如三角形和漢密爾頓路徑問題，準確性並沒有顯著提高，甚至隨著數據量的增加而略有下降。例如，GraphWiz (Mistral-7B) 在三角和問題上在1:1比率下的準確性為47.00％，然後在1:5比率下降至38.75％。這可能表明了過擬合現象，即模型開始記住訓練數據中的模式，這些模式並不適用於未見過的數據。
總之，雖然增加數據量和推理路徑的多樣性通常可以導致更好的模型性能，但在某些複雜任務中存在潛在的過擬合跡象，這強調了需要仔細設計模型訓練，並對不同的圖問題任務進行驗證，以確保廣泛的泛化能力。
為了探索GraphWiz在不同圖任務中的遷移能力，團隊建立了一個額外的模型變體：GraphWiz-High。這個模型僅在兩個高複雜度（NP-完全）圖任務上進行訓練：漢密爾頓路徑和子圖匹配。為了研究其遷移能力，團隊進行了兩個比較實驗：
高複雜度任務比較。團隊首先將GraphWiz-High與常規的GraphWiz在高複雜度任務上進行比較。上圖(a)表明GraphWiz的表現更好，驗證了混合任務訓練的有效性。這個結果也表明模型能夠將從其他任務學到的知識轉移到特定的高複雜度任務上。
零樣本遷移能力。團隊進一步測試GraphWiz-High在從未訓練過的低和中複雜度任務上的零樣本遷移能力。如上圖 (b) 所示，GraphWiz-High與Mistral-Base相比有顯著的性能提升。即使與ChatGPT相比，團隊的模型也能保持相當的性能。考慮到ChatGPT和GraphWiz-High之間在參數數量上的巨大差異，這表明團隊的模型具有值得稱讚的跨任務泛化能力，展示了實際應用的重大潛力。
為了解答關於模型性能如何隨著不同圖大小變化的問題，以及確定模型能夠有效解決的最大圖大小，團隊在上圖展示了GraphWiz在表現最佳任務（a）環檢測和最差任務（b）最短路徑上的性能。
從圖中，團隊得出以下結論：
GraphWiz和GPT-4在圖的大小增加時都表現出性能的下降。然而，團隊的模型在大多數時候當圖大小上一致時優於GPT-4，這表明了對圖結構更強大的理解和處理能力。
團隊觀察到在最短路徑上，隨著節點數的增加，性能顯著下降。這種下降很可能可以歸因於兩個主要因素：該任務要求高推理和記憶能力，因為更高時間複雜性，以及強大的計算技巧，這可能對模型的容量構成額外挑戰。實際上，團隊發現兩種模型主要依賴枚舉來得出解決方案。因此，隨著圖大小的增加，所需的枚舉推理呈指數級增長，導致當節點數超過60後，準確率顯著下降，之後幾乎不再有準確性。
這些觀察表明，儘管GraphWiz在處理與圖相關的任務方面明顯優於GPT-4，但存在一個複雜度的閾值——特別是在需要超出簡單推理的計算的任務中——即使是最先進的模型的性能也開始顯著下降。
最後，團隊還探究了參數ß對模型效果的影響。團隊觀察到，較高的 ß似乎在一定程度上有利於困難任務的性能，但這並非嚴格的線性關係，並且在不同的模型大小之間也不一致。這表明，仔細調整 ß 對於在不同難度任務之間取得最佳平衡，提高模型的整體準確性是必要的。
更多樣例
團隊還展示了更多不同任務上GraphWiz的推理樣例。
連通性任務：
漢密爾頓路徑任務：
最短路徑任務：
子圖匹配任務：
論文鏈接：https://arxiv.org/abs/2402.16029項目主頁：https://graph-wiz.github.io/
本文來自微信公眾號“量子位”（ID:QbitAI），作者：香港科技大學 陳諾，36氪經授權發佈。
