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

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

belike：

圖片

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

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

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

具體如何實現？

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

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

圖片

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

有網友已經迫不及待集成到RAG中了：

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

圖片

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

在具體方法上，圖線性化涉及將圖的節點和邊轉換為線性token序列。

圖片

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

一種是根據圖中心性（Graph centrality）對節點進行排序。

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

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

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

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

圖片

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

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

為了實現全局對齊性，作者還提出了節點重命名策略。

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

中心性方法總體優于退化性方法

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

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

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

圖片

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

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

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

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

結果顯示了以下幾個重要發現。

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

圖片

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

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

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

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

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