今天小編分享的科學經驗：圖結構轉文本序列，大模型直接讀懂！圖推理性能大漲，歡迎閲讀。
大語言模型直接理解復雜圖結構的新方法來了：
将圖（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
