大語(yǔ)言模型直接理解復(fù)雜圖結(jié)構(gòu)的新方法來(lái)了：

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

belike：

圖片

這種最新圖線性化方法，反映了自然語(yǔ)言中局部依賴性和全局對(duì)齊性兩個(gè)關(guān)鍵屬性，即：

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

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

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

機(jī)器學(xué)習(xí)工程師Rohan Paul發(fā)帖推薦論文并做了個(gè)總結(jié)。

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

圖片

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

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

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

圖片

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

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

圖片

研究團(tuán)隊(duì)提出了幾種基于圖論的圖線性化方法。

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

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

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

另一種是基于圖退化性（Graph degeneracy）的方法，即通過(guò)圖的核編號(hào)（Core Number）來(lái)排序節(jié)點(diǎn)。

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

圖片

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

他們將每個(gè)圖轉(zhuǎn)換為其對(duì)應(yīng)的線圖（Linegraph），將原圖的每條邊轉(zhuǎn)換為線圖中的節(jié)點(diǎn)，如果原圖中兩條邊相鄰，則在線圖中對(duì)應(yīng)節(jié)點(diǎn)相連。然后，應(yīng)用與核編號(hào)相同的過(guò)程來(lái)對(duì)Linegraph中的節(jié)點(diǎn)進(jìn)行排序。

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

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

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

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

首先構(gòu)造基礎(chǔ)圖（循環(huán)或鏈?zhǔn)浇Y(jié)構(gòu)），然后附加預(yù)定義形狀的圖案（motifs）。

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

圖片

實(shí)驗(yàn)中設(shè)計(jì)了三個(gè)評(píng)估任務(wù)：

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

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

包括zero-shot和one-shot兩種設(shè)置，并與兩個(gè)基線方法比較：MotifAware基線，保持圖生成過(guò)程中的默認(rèn)邊序；Random基線，完全隨機(jī)的邊列表排序和節(jié)點(diǎn)標(biāo)簽。

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

首先，在節(jié)點(diǎn)計(jì)數(shù)任務(wù)中，所有方法都顯示較低的平均誤差，但準(zhǔn)確率表現(xiàn)各異?；诙戎行男院蚉ageRank的方法表現(xiàn)最好，超過(guò)了基線方法。

圖片

在最大度計(jì)算任務(wù)中，由于需要更復(fù)雜的計(jì)算過(guò)程，整體性能低于節(jié)點(diǎn)計(jì)數(shù)任務(wù)。使用默認(rèn)節(jié)點(diǎn)標(biāo)簽時(shí)，度中心性和PageRank方法在one-shot設(shè)置下取得最佳效果。

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

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

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

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