引言

Graph Transformer已成為ML的重要架構(gòu)，它將基于序列的Transformer應(yīng)用于圖結(jié)構(gòu)數(shù)據(jù)。然而當(dāng)面對(duì)大型圖數(shù)據(jù)集時(shí)，使用Graph Transformer會(huì)存在擴(kuò)展性限制。為此，「Google提出了一個(gè)稀疏注意力框架Exphormer，它使用擴(kuò)展圖來(lái)提高圖Transformer的可擴(kuò)展性，并在長(zhǎng)期依賴關(guān)系表現(xiàn)出了強(qiáng)大的性能」。

論文：https://arxiv.org/pdf/2303.06147.pdf

背景介紹

圖在計(jì)算和機(jī)器學(xué)習(xí) (ML) 中無(wú)處不在，其中對(duì)象及其關(guān)系可以用圖中的節(jié)點(diǎn)和節(jié)點(diǎn)之間的邊來(lái)表示。社交網(wǎng)絡(luò)、道路網(wǎng)絡(luò)以及分子結(jié)構(gòu)之間的相互作用都都具有類似圖結(jié)構(gòu)。通過(guò)機(jī)器學(xué)習(xí)可學(xué)習(xí)圖的節(jié)點(diǎn)、邊亦或者整個(gè)圖的屬性。

圖學(xué)習(xí)的一種常見(jiàn)方法是圖神經(jīng)網(wǎng)絡(luò)（GNN），它通過(guò)對(duì)節(jié)點(diǎn)、邊和全局屬性信息進(jìn)行相應(yīng)的轉(zhuǎn)換來(lái)實(shí)現(xiàn)對(duì)圖數(shù)據(jù)的操作。典型的圖神經(jīng)網(wǎng)絡(luò)（GNN）是通過(guò)消息傳遞框架進(jìn)行數(shù)據(jù)操作，其中每一層都將節(jié)點(diǎn)的表示與其直接相鄰的表示聚合在一起。

最近，圖Transformer已成為了消息傳遞架構(gòu)的替代方案。這些模型建立在Transformer成功的基礎(chǔ)之上，使其可以適應(yīng)圖結(jié)構(gòu)數(shù)據(jù)。圖Transformer中的注意力機(jī)制可以通過(guò)交互圖來(lái)建模，其中邊代表相互關(guān)聯(lián)的節(jié)點(diǎn)對(duì)。與消息傳遞架構(gòu)不同，圖Transformer具有與輸入圖分離的交互圖。

典型的交互圖是一個(gè)完整的圖，它表示一個(gè)完整的注意力機(jī)制，可以對(duì)所有節(jié)點(diǎn)對(duì)之間的交互進(jìn)行建模。然而，這會(huì)產(chǎn)生二次計(jì)算和內(nèi)存瓶頸，限制了圖Transformer在具有數(shù)千個(gè)節(jié)點(diǎn)的小圖上的適用性。使圖Transformer具備可擴(kuò)展性，已被認(rèn)為是該領(lǐng)域最重要的研究方向之一。

面對(duì)二次計(jì)算和內(nèi)存瓶頸，一種方法是使用邊數(shù)較少的稀疏交互圖。當(dāng)前已經(jīng)提出了許多稀疏且高效的Transformer來(lái)消除序列的二次瓶頸，但是，它們通常不會(huì)將其擴(kuò)展應(yīng)用到圖神經(jīng)網(wǎng)絡(luò)。

基于以上背景，在ICML2023上，Google提出了“Exphormer: Sparse Transformers for Graphs”中，通過(guò)引入專為圖數(shù)據(jù)設(shè)計(jì)的Transformers 的稀疏注意力框架來(lái)解決可擴(kuò)展性問(wèn)題，Exphormer框架在各種數(shù)據(jù)集上獲得優(yōu)異的結(jié)果。

Exphormer

「Exphormer核心思想是使用擴(kuò)展圖」，它們是稀疏但連接良好的圖，如下圖所示。

并且具有以下屬性：

• 1）圖的矩陣表示具有與完整圖類似的線性代數(shù)屬性；

• 2 ）它們表現(xiàn)出快速混合的隨機(jī)游走，即從任何起始節(jié)點(diǎn)開(kāi)始的隨機(jī)游總走中的少量步驟足以確保收斂至圖節(jié)點(diǎn)上的“穩(wěn)定”分布。

當(dāng)前 Exphormer 已應(yīng)用于不同領(lǐng)域，例如算法、偽隨機(jī)性、復(fù)雜理論和代碼糾錯(cuò)。

一類常見(jiàn)的擴(kuò)展圖是擴(kuò)展圖，其中每個(gè)節(jié)點(diǎn)都有d條邊（即每個(gè)節(jié)點(diǎn)的度數(shù)為d）。擴(kuò)展圖的好壞通過(guò)譜間隙來(lái)衡量的，譜間隙是其相鄰矩陣的代數(shù)屬性。那些最大化譜間隙的圖被稱為Ramanujan圖——它們實(shí)現(xiàn)了的間隙，這本質(zhì)上是正則圖中最好的。多年來(lái)，針對(duì)不同的??值，提出了一系列的Ramanujan圖構(gòu)造。本文使用Friedman隨機(jī)擴(kuò)展結(jié)構(gòu)，它可以近似產(chǎn)生Ramanujan圖。

構(gòu)建稀疏交互圖

Exphormer 將擴(kuò)輸入圖的擴(kuò)展器邊緣和虛擬節(jié)點(diǎn)結(jié)合起來(lái)。具體來(lái)說(shuō)，Exphormer 的稀疏注意力機(jī)制構(gòu)建了一個(gè)由三種類型的邊組成的交互圖，如下圖所示：

• 輸入圖的邊（局部注意力）

• constant-degree擴(kuò)展圖的邊（擴(kuò)展注意力）

• 從每個(gè)節(jié)點(diǎn)到一小組虛擬節(jié)點(diǎn)的邊（全局注意力）

其中，每個(gè)組件都有特定的用途：輸入圖的邊保留輸入圖結(jié)構(gòu)的歸納偏差；擴(kuò)展邊允許良好的全局連接性和隨機(jī)游走混合特性；虛擬節(jié)點(diǎn)充當(dāng)全局“內(nèi)存接收器”，可以直接與每個(gè)節(jié)點(diǎn)通信。雖然這會(huì)導(dǎo)致每個(gè)虛擬節(jié)點(diǎn)的附加邊等于輸入圖中的節(jié)點(diǎn)數(shù)，但生成的圖仍然是稀疏的。擴(kuò)展圖的degree和虛擬節(jié)點(diǎn)的數(shù)量是用于調(diào)整以提高質(zhì)量指標(biāo)的超參數(shù)。

此外，由于使用constant-degree擴(kuò)展圖和少量恒定數(shù)量的虛擬節(jié)點(diǎn)來(lái)進(jìn)行全局注意力，因此所得的稀疏注意力機(jī)制與原始輸入圖的大小呈線性關(guān)系，即它模擬了許多直接交互節(jié)點(diǎn)和邊總數(shù)的順序。

此外，Exphormer 與密集Transformer一樣具有表現(xiàn)力，并且遵循常用的近似屬性。特別是，當(dāng) Exphormer 的稀疏注意力圖通過(guò)自環(huán)（將節(jié)點(diǎn)連接到自身的邊）進(jìn)行增強(qiáng)時(shí)，它可以普遍逼近連續(xù)函數(shù)。

與稀疏Transformer的關(guān)系

將 Exphormer 與稀疏注意力方法進(jìn)行比較是很有趣的。也許在概念上與我們的方法最相似的架構(gòu)是 BigBird，它通過(guò)組合不同的組件來(lái)構(gòu)建交互圖。BigBird 也使用虛擬節(jié)點(diǎn)，但與 Exphormer 不同的是，它對(duì)其余組件使用來(lái)自 Erd?s-Rényi 隨機(jī)圖模型的窗口注意力和隨機(jī)注意力。

BigBird 中的窗口注意力著眼于序列中標(biāo)記周圍的標(biāo)記，而Exphormer 中的局部鄰域注意力可以被視為窗口注意力對(duì)圖的概括。

n 個(gè)節(jié)點(diǎn)的 Erd?s-Rényi 圖 G(n, p) ，以概率 p 連接每對(duì)節(jié)點(diǎn)，也可用作高度為p的擴(kuò)展圖。然而，需要超線性邊數(shù)來(lái)確保 Erd?s-Rényi 圖是連通的，更不用說(shuō)良好的擴(kuò)展器了。另一方面，Exphormer 中使用的擴(kuò)展器僅具有線性數(shù)量的邊。

實(shí)驗(yàn)結(jié)果

為了評(píng)估 Exphormer 的性能，本文以GraphGPS 框架為基礎(chǔ)，該框架結(jié)合了消息傳遞和圖Transformer，并在許多數(shù)據(jù)集上實(shí)現(xiàn)了最先進(jìn)的性能。實(shí)驗(yàn)結(jié)果如下圖所示：

可以發(fā)現(xiàn)，用 Exphormer替代GraphGPS 框架中的密集注意力可以實(shí)現(xiàn)具有可比或更好性能，并且具有更少的訓(xùn)練參數(shù)。

此外，Exphormer 能夠讓圖Transformer架構(gòu)的擴(kuò)展超出常規(guī)大小限制。Exphormer 可以擴(kuò)展到包含 10,000 多個(gè)節(jié)點(diǎn)圖的數(shù)據(jù)集，例如 Coauthor 數(shù)據(jù)集，甚至可以擴(kuò)展到更大的圖，如下圖所示。

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-824660.html

到了這里，關(guān)于Google 提出稀疏注意力框架Exphormer，提升圖Transformer的擴(kuò)展性！的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！