大語言模型直接理解復雜圖結構的新方法來了：

將圖（Graph）轉(zhuǎn)換為適合Transformer架構的線性token序列。

belike：

圖片

這種最新圖線性化方法，反映了自然語言中局部依賴性和全局對齊性兩個關鍵屬性，即：

不僅需要保留基于前文上下文預測下一個token的能力（局部依賴性），而且不同圖的token序列應該從具有相似特征的token開始或結束（全局對齊性），就像自然語言文本經(jīng)常以特定詞語開頭或結尾。

如此一來，在海量文本數(shù)據(jù)上訓練的LLM也能更好地理解圖結構中的關系和屬性，如節(jié)點計數(shù)、最大度數(shù)計算和圖式形狀分類等圖推理任務都能完成。

具體如何實現(xiàn)？

機器學習工程師Rohan Paul發(fā)帖推薦論文并做了個總結。

• 用多種技術開發(fā)了圖線性化方法：圖中心性（PageRank和度）、圖退化（k-core分解）、節(jié)點重標記方案
• 基于節(jié)點重要性創(chuàng)建了邊排序策略
• 應用節(jié)點重標記以保持全局對齊

圖片

作者使用GraphWave合成數(shù)據(jù)集進行評估，結果表明他們提出的線性化方法相比基線方法取得了更好的性能，特別是基于度中心性和PageRank的方法在多個任務中表現(xiàn)突出。

有網(wǎng)友已經(jīng)迫不及待集成到RAG中了：

我一直在尋找這方面的論文。

圖片

多種基于圖論的線性化方法

在具體方法上，圖線性化涉及將圖的節(jié)點和邊轉(zhuǎn)換為線性token序列。

圖片

研究團隊提出了幾種基于圖論的圖線性化方法。

一種是根據(jù)圖中心性（Graph centrality）對節(jié)點進行排序。

這里的中心性可以是節(jié)點的度（Degree centrality），即與節(jié)點直接相連的邊的數(shù)量；也可以是更為復雜的PageRank值，它不僅考慮節(jié)點的連接數(shù)，還考慮連接到它的節(jié)點的重要性。

研究人員根據(jù)排序結果選擇與重要性最高的節(jié)點相連的邊，并隨機排列這些邊，然后對下一個重要性節(jié)點重復此過程。如果多個節(jié)點具有相同的中心性值，則隨機選擇它們的順序。

另一種是基于圖退化性（Graph degeneracy）的方法，即通過圖的核編號（Core Number）來排序節(jié)點。

利用k-core分解,將圖分解為一系列嵌套的子圖。核編號是指節(jié)點在圖中最高核的編號。通過這種方式，能夠捕捉到圖中最核心的部分，并將這些信息線性化。

圖片

除了基于節(jié)點屬性的排序，作者們還考慮了直接對邊進行排序的方法。

他們將每個圖轉(zhuǎn)換為其對應的線圖（Linegraph），將原圖的每條邊轉(zhuǎn)換為線圖中的節(jié)點，如果原圖中兩條邊相鄰，則在線圖中對應節(jié)點相連。然后，應用與核編號相同的過程來對Linegraph中的節(jié)點進行排序。

為了實現(xiàn)全局對齊性，作者還提出了節(jié)點重命名策略。

在這個策略中，不同圖中具有最高核編號的節(jié)點被重新標記為索引0，以此類推。這樣做的目的是讓LLM能夠?qū)⒐?jié)點索引與其重要性屬性之間建立一致的聯(lián)系。

中心性方法總體優(yōu)于退化性方法

為了測試上述方法的有效性，作者使用GraphWave生成器構建了合成數(shù)據(jù)集。

首先構造基礎圖（循環(huán)或鏈式結構），然后附加預定義形狀的圖案（motifs）。

研究人員選擇了五種基本形狀（團、星形、扇形、菱形和樹），并包含了這些形狀的組合，總共生成了3000個圖，平均每個圖包含32.33個節(jié)點和43.72條邊。

圖片

實驗中設計了三個評估任務：

• 節(jié)點計數(shù)：要求模型從邊列表推斷節(jié)點數(shù)量
• 最大度計算：確定圖中最大節(jié)點度數(shù)
• 圖案形狀分類：給定詳細的圖案定義，識別圖中存在的圖案

實驗采用了Llama 3 Instruct 8B模型，使用4bit量化版本。為確保輸出的確定性和一致性，temperature參數(shù)設為1e-3，sampling參數(shù)設為1e-1。

包括zero-shot和one-shot兩種設置，并與兩個基線方法比較：MotifAware基線，保持圖生成過程中的默認邊序；Random基線，完全隨機的邊列表排序和節(jié)點標簽。

結果顯示了以下幾個重要發(fā)現(xiàn)。

首先，在節(jié)點計數(shù)任務中，所有方法都顯示較低的平均誤差，但準確率表現(xiàn)各異。基于度中心性和PageRank的方法表現(xiàn)最好，超過了基線方法。

圖片

在最大度計算任務中，由于需要更復雜的計算過程，整體性能低于節(jié)點計數(shù)任務。使用默認節(jié)點標簽時，度中心性和PageRank方法在one-shot設置下取得最佳效果。

節(jié)點重標記策略的效果因任務而異，在節(jié)點計數(shù)中，除了zero-shot的度中心性方法外，大多導致準確率下降，但在平均誤差上通常有改善。

one-shot設置的性能普遍低于zero-shot，這表明示例可能并不總是有助于提高性能。

基于中心性的方法（度中心性和PageRank）總體上優(yōu)于基于退化性的方法。

參考鏈接：https://x.com/rohanpaul_ai/status/1863014451827655118
論文鏈接：https://arxiv.org/pdf/2410.19494