本文約4500字，建議閱讀10+分鐘

本文率先提出了無(wú)監(jiān)督圖結(jié)構(gòu)學(xué)習(xí)的范式，旨在不依賴(lài)標(biāo)簽信息的條件下，從數(shù)據(jù)本身中學(xué)習(xí)更普適、更高質(zhì)量的圖結(jié)構(gòu)。

作者 | Yuki

研究方向 | 推薦系統(tǒng)，圖神經(jīng)網(wǎng)絡(luò)

論文題目：

Towards Unsupervised Deep Graph Structure Learning

論文鏈接：

https://arxiv.org/pdf/2201.06367.pdf

代碼鏈接：

https://github.com/GRAND-Lab/SUBLIME

參考鏈接：

https://mp.weixin.qq.com/s/k66maMGcufw4svmIRC13zA

一、前言

近年來(lái)，圖神經(jīng)網(wǎng)絡(luò)（graph neural networks，GNNs）被廣泛應(yīng)用于各種圖數(shù)據(jù)相關(guān)的任務(wù)當(dāng)中。然而，圖神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)十分依賴(lài)于輸入的圖結(jié)構(gòu)數(shù)據(jù)(即圖數(shù)據(jù)中各節(jié)點(diǎn)的關(guān)聯(lián))，大大影響了其魯棒性和普適性。一方面，現(xiàn)實(shí)系統(tǒng)中獲取的圖結(jié)構(gòu)數(shù)據(jù)難免包含噪聲信息，會(huì)存在多余邊或缺失邊的問(wèn)題；在學(xué)習(xí)過(guò)程中，GNN 很容易受到這些噪聲數(shù)據(jù)的影響，從而導(dǎo)致其性能下降。另一方面，對(duì)圖結(jié)構(gòu)的依賴(lài)也使得 GNN 無(wú)法應(yīng)用于沒(méi)有顯式結(jié)構(gòu)的非結(jié)構(gòu)數(shù)據(jù)學(xué)習(xí)，盡管這些數(shù)據(jù)中可能存在隱性的結(jié)構(gòu)信息。這種對(duì)輸入結(jié)構(gòu)的依賴(lài)，使得 GNN 難以應(yīng)用于廣泛存在于現(xiàn)實(shí)世界的非結(jié)構(gòu)數(shù)據(jù)當(dāng)中。

為了解決上述問(wèn)題，現(xiàn)有方法對(duì)圖結(jié)構(gòu)學(xué)習(xí)（graph structure learning，GSL）進(jìn)行研究，該技術(shù)旨在利用 GNN 對(duì)輸入圖結(jié)構(gòu)本身進(jìn)行學(xué)習(xí)和優(yōu)化。目前的圖結(jié)構(gòu)學(xué)習(xí)主要遵循有監(jiān)督范式，即：利用節(jié)點(diǎn)分類(lèi)這一下游任務(wù)的標(biāo)簽信息，對(duì)圖結(jié)構(gòu)和 GNN 進(jìn)行協(xié)同優(yōu)化。這種范式雖被證明有效，卻存在著一些局限性：

1. 依賴(lài)于標(biāo)簽信息，在有監(jiān)督 GSL 方法中，在進(jìn)行圖結(jié)構(gòu)優(yōu)化時(shí)人工標(biāo)注的標(biāo)簽在扮演了至關(guān)重要的角色，然而對(duì)標(biāo)簽數(shù)據(jù)的依賴(lài)限制了有監(jiān)督 GSL 的在更廣泛的無(wú)標(biāo)簽數(shù)據(jù)中的應(yīng)用；

2. 學(xué)習(xí)到的邊分布存在偏差，節(jié)點(diǎn)分類(lèi)通常以半監(jiān)督的形式進(jìn)行，只有一小部分節(jié)點(diǎn)是有標(biāo)簽的（如在 Cora 數(shù)據(jù)集有標(biāo)簽節(jié)點(diǎn)的比例為 140/2708 ），因此這些標(biāo)簽節(jié)點(diǎn)之間的連接及其鄰居會(huì)接收到更多的監(jiān)督，從而造成學(xué)到的邊分布存在不均勻和偏差；

3. 下游任務(wù)的局限性，在現(xiàn)有的方法中，結(jié)構(gòu)學(xué)習(xí)通常依賴(lài)節(jié)點(diǎn)分類(lèi)來(lái)提供監(jiān)督信號(hào)，因此學(xué)習(xí)到的圖結(jié)構(gòu)通常是任務(wù)特定而不是通用的，可能對(duì)于下游其他任務(wù)沒(méi)有幫助（如鏈接預(yù)測(cè)和節(jié)點(diǎn)聚類(lèi)）。

為了解決上述局限，文中提出了一種新的用于 GSL 的無(wú)監(jiān)督學(xué)習(xí)范式（unsupervised graph structure learning）。如圖 1 所示，該學(xué)習(xí)范式不依靠任何額外的標(biāo)簽信息，僅根據(jù)輸入數(shù)據(jù)本身對(duì)圖結(jié)構(gòu)進(jìn)行學(xué)習(xí)或改進(jìn)，因此學(xué)習(xí)到的圖結(jié)構(gòu)是通用的無(wú)偏的。針對(duì)新的學(xué)習(xí)范式，本文提出了一種基于結(jié)構(gòu)自引導(dǎo)的自監(jiān)督對(duì)比學(xué)習(xí)方法（StrUcture Bootstrapping Contrastive LearnIng fraMEwork, SUBLIME）。該方法主要有一下三點(diǎn)貢獻(xiàn)：

1. 提出了一種新的用于 GSL 的無(wú)監(jiān)督學(xué)習(xí)范式，相較于其他基于監(jiān)督學(xué)習(xí)的 GSL，該范式更具有實(shí)踐性。

2. 提出了一種新的無(wú)監(jiān)督 GSL 方法——SUBLIME，該方法采用對(duì)比學(xué)習(xí)技術(shù)，從原數(shù)據(jù)本身中獲取監(jiān)督信號(hào)來(lái)引導(dǎo)結(jié)構(gòu)學(xué)習(xí)，并同時(shí)利用學(xué)到的結(jié)構(gòu)信息對(duì)監(jiān)督信息進(jìn)行更新。

3. 大量實(shí)驗(yàn)證明了 SUBLIME 的有效性。

二、問(wèn)題定義

在介紹無(wú)監(jiān)督 GSL 之前，先給出圖的定義。給出一個(gè)屬性圖 ， 表示節(jié)點(diǎn)集合（）， 表示邊集合（）， 表示特征矩陣， 表示鄰接矩陣。

本文針對(duì)兩種輸入數(shù)據(jù)的情況，定義了兩種無(wú)監(jiān)督圖結(jié)構(gòu)學(xué)習(xí)問(wèn)題，即“結(jié)構(gòu)推理”（structure inference）和“結(jié)構(gòu)改進(jìn)”（structure refinement）。具體的，結(jié)構(gòu)推理用于一般性的數(shù)據(jù)（圖結(jié)構(gòu)未定義或缺失），該任務(wù)目標(biāo)是從非結(jié)構(gòu)化的數(shù)據(jù)中（僅包含特征矩陣 ）學(xué)習(xí)出潛在的圖結(jié)構(gòu) 。

結(jié)構(gòu)改進(jìn)的目標(biāo)則是從含噪聲的圖結(jié)構(gòu)數(shù)據(jù)（包含特征矩陣 和鄰接矩陣 ）中對(duì)原有的圖結(jié)構(gòu)進(jìn)行改進(jìn)得到改進(jìn)后的圖結(jié)構(gòu) 。本文假設(shè)學(xué)習(xí)得到的圖結(jié)構(gòu) 能夠更好的揭示節(jié)點(diǎn)之間的真實(shí)連接關(guān)系，并可被廣泛應(yīng)用于各種下游任務(wù)中。

三、方法

本文所提出的 SUBLIME 主要包含了兩個(gè)組件：圖結(jié)構(gòu)學(xué)習(xí)模塊（Graph Structure Learning Module）以及結(jié)構(gòu)自引導(dǎo)對(duì)比學(xué)習(xí)模塊（Structure Bootstrapping Contrastive Learning Module），SUBLIME 的結(jié)構(gòu)圖如圖 2 所示，在圖結(jié)構(gòu)學(xué)習(xí)模塊中，首先應(yīng)用圖學(xué)習(xí)器（Graph Learner）來(lái)建模圖結(jié)構(gòu)，然后通過(guò)后處理器（Post-Processor）對(duì)建模的圖結(jié)構(gòu)進(jìn)行規(guī)范化。

在結(jié)構(gòu)自引導(dǎo)對(duì)比學(xué)習(xí)模塊中，首先定義了學(xué)習(xí)者視圖（Learner view）和參考視角（Anchor View）用于對(duì)比。具體的，前者由學(xué)習(xí)到的圖結(jié)構(gòu)構(gòu)成，后者則從原始數(shù)據(jù)中初始化而來(lái)。然后分別對(duì)兩種視角應(yīng)用數(shù)據(jù)增強(qiáng)（Data Augmentation）。

接下來(lái)最大化兩種視角之間的互信息（Mutual Information），為圖結(jié)構(gòu)學(xué)習(xí)提供監(jiān)督信號(hào)。此外，文中還設(shè)計(jì)了一種結(jié)構(gòu)自引導(dǎo)機(jī)制，利用從學(xué)習(xí)者視角中學(xué)到的信息對(duì)參考視角進(jìn)行優(yōu)化。下面將對(duì)上述組件一一介紹。

3.1 圖學(xué)習(xí)器

圖學(xué)習(xí)器是 GSL 的關(guān)鍵組成部分，其用于學(xué)習(xí)一個(gè)粗略（sketched）鄰接矩陣 ，大多數(shù)現(xiàn)有的方法通常采用單一的圖學(xué)習(xí)器，無(wú)法適應(yīng)不同數(shù)據(jù)的特性。為了適應(yīng)不同輸入數(shù)據(jù)的需要，本文采用了四種圖學(xué)習(xí)器來(lái)建模圖結(jié)構(gòu)，包括一種全圖參數(shù)化學(xué)習(xí)器（FGP Learner），和三種基于度量學(xué)習(xí)的學(xué)習(xí)器（Metric Learning-based Learners）。通常圖學(xué)習(xí)器可以表示為 ， 為模型參數(shù)。

FGP 學(xué)習(xí)器對(duì)鄰接矩陣的每個(gè)元素都用一個(gè)可學(xué)習(xí)的參數(shù)來(lái)建模，并應(yīng)用一個(gè)非線性激活函數(shù) 來(lái)保證訓(xùn)練的穩(wěn)定性：

而基于度量學(xué)習(xí)的學(xué)習(xí)器中，首先會(huì)由一個(gè)基于神經(jīng)網(wǎng)絡(luò)的嵌入函數(shù)來(lái)得到節(jié)點(diǎn)嵌入，然后通過(guò)無(wú)參數(shù)的度量函數(shù)（比如余弦相似度）來(lái)得到鄰接矩陣中的而基于度量學(xué)習(xí)的學(xué)習(xí)器中，首先會(huì)由一個(gè)基于神經(jīng)網(wǎng)絡(luò)的嵌入函數(shù) 來(lái)得到節(jié)點(diǎn)嵌入，然后通過(guò)無(wú)參數(shù)的度量函數(shù) （比如余弦相似度）來(lái)得到鄰接矩陣中的值：

通過(guò)定義不同的嵌入函數(shù) ，本文提供了三種不同的學(xué)習(xí)器：1）注意力學(xué)習(xí)器（Attentive Learner）；2）多層感知機(jī)學(xué)習(xí)器（MLP Learner）；3）圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)器（GNN Learner）：采用 GNN 進(jìn)行節(jié)點(diǎn)嵌入的編碼。

注意力學(xué)習(xí)器采用注意力機(jī)制來(lái)生成的節(jié)點(diǎn)嵌入：

多層感知機(jī)學(xué)習(xí)器采用多層堆疊的 MLP 層來(lái)計(jì)算節(jié)點(diǎn)嵌入：

圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)器采用 GNN 進(jìn)行節(jié)點(diǎn)嵌入的編碼：

在 SUBLIME 中根據(jù)數(shù)據(jù)集特性選擇了最合適的學(xué)習(xí)器來(lái)建模圖結(jié)構(gòu) 。

3.2 后處理器

經(jīng)由圖學(xué)習(xí)器得到的鄰接矩陣 通常比較粗糙，無(wú)法具備真實(shí)圖結(jié)構(gòu)的許多特性。因此，文中使用后處理對(duì)這個(gè)鄰接矩陣進(jìn)一步優(yōu)化，從而產(chǎn)生一個(gè)精煉的圖鄰接矩陣。后處理器中的步驟主要分為 4 步：

1）稀疏化 Sparsification（基于kNN）：

2）對(duì)稱(chēng)化 Symmetrization（基于矩陣轉(zhuǎn)置求平均）與 3）非負(fù)化 Activation（基于 ReLU 激活函數(shù)）：

4）歸一化 Normalization（基于對(duì)稱(chēng)歸一化處理）：

式中 表示 的都矩陣。

通過(guò)上述一系列后處理步驟，最終得到一個(gè)稀疏、非負(fù)、對(duì)稱(chēng)且正歸一鄰接矩陣 。

3.3 多視角圖對(duì)比學(xué)習(xí)

當(dāng)對(duì)學(xué)習(xí)到的圖結(jié)構(gòu)（鄰接矩陣）進(jìn)行建模后，文中采用多視角對(duì)比學(xué)習(xí)的方式，通過(guò)從原數(shù)據(jù)中獲取監(jiān)督信號(hào)來(lái)指導(dǎo)圖結(jié)構(gòu)的優(yōu)化?；趯W(xué)到的鄰接矩陣，我們將其與特征矩陣 進(jìn)行結(jié)合，得到學(xué)習(xí)者視角（Learner View），記為 。

文中利用原始數(shù)據(jù)對(duì)參考視角（Anchor View）進(jìn)行初始化，該視角為圖結(jié)構(gòu)的學(xué)習(xí)提供指引。具體地，若原數(shù)據(jù)帶有圖結(jié)構(gòu)，我們會(huì)將該視角初始化為原始特征矩陣和鄰接矩陣：；若原數(shù)據(jù)不含圖結(jié)構(gòu)，將其中的鄰接矩陣初始化為單位矩陣：。

視角構(gòu)建完成后，文中設(shè)計(jì)兩種數(shù)據(jù)增廣方式：

1）隨機(jī)遮掩特征（Feature Masking），對(duì)于給定的特征矩陣 ，首先采樣遮掩向量 ，采樣過(guò)程服從參數(shù)為 的伯努利分布，隨機(jī)遮掩過(guò)程定義如下：

表示隨機(jī)丟棄連接操作符。

2）隨機(jī)丟棄連接（Edge Dropping），對(duì)于給定的鄰接矩陣 ，首先采樣遮掩矩陣 ，采樣過(guò)程服從參數(shù)為 的伯努利分布，隨機(jī)丟棄過(guò)程定義如下：

表示隨機(jī)丟棄連接操作符。

通過(guò)增大對(duì)比學(xué)習(xí)任務(wù)的難度，使模型能夠探索到更高質(zhì)量的圖結(jié)構(gòu)。

在 SUBLIME 中對(duì)學(xué)習(xí)者視角和參考視角同時(shí)使用了上述兩種增廣方式：

值得一提的是為了提高兩個(gè)視角間的差異性（上下文差異）。對(duì)于隨機(jī)遮掩特征，采用了不同的 probabilities，。但是對(duì)于隨機(jī)丟棄連接，文中使用了相同的 dropping probability，，因?yàn)閮蓚€(gè)視角的鄰接矩陣本身差異明顯。

下一步，采用節(jié)點(diǎn)級(jí)的對(duì)比學(xué)習(xí)模型來(lái)最大化兩個(gè)視角的互信息。具體地，增廣后兩個(gè)視角圖首先經(jīng)由兩層 GCN 的編碼，得到每個(gè)節(jié)點(diǎn)的表征：

表示基于 GCN 的 encoder， 是 encoder 的模型參數(shù)。

然后，經(jīng)過(guò)由兩層 MLP 網(wǎng)絡(luò)構(gòu)成的投影網(wǎng)絡(luò)，得到兩個(gè)視角對(duì)應(yīng)的投影矩陣：

最后，采用 NT-Xent 損失（Normalized Temperature-Scaled Cross-Entropy loss）函數(shù)來(lái)最大化兩個(gè)投影矩陣中對(duì)應(yīng)節(jié)點(diǎn)的相似度，從而最大化兩個(gè)視角的互信息：

指代余弦相似度函數(shù)， 為溫度系數(shù)， 與 同時(shí)計(jì)算。

3.4 結(jié)構(gòu)自引導(dǎo)機(jī)制

通過(guò)固定的參考鄰接矩陣 （定義為 或者 ）的指引，我們已經(jīng)可以采用該模型進(jìn)行結(jié)構(gòu)學(xué)習(xí)。然而，這樣的固定參考存在以下不足：1）原結(jié)構(gòu)中包含的噪聲邊會(huì)對(duì)學(xué)到的圖結(jié)構(gòu)產(chǎn)生誤導(dǎo)；2）固定的參考鄰接矩陣包含的信息有限，很難提供持續(xù)的指引；3）在學(xué)習(xí)過(guò)程中，容易對(duì)固定的結(jié)構(gòu)產(chǎn)生過(guò)擬合。

在自引導(dǎo)（Bootstrapping）的算法的啟發(fā)下，我們?cè)O(shè)計(jì)了一種結(jié)構(gòu)自引導(dǎo)機(jī)制（Structure Bootstrapping Mechanism）對(duì)參考鄰接矩陣進(jìn)行更新，從而提供可靠、持續(xù)、有效的結(jié)構(gòu)學(xué)習(xí)指引。具體地，我們基于 slow-moving 的思想，利用學(xué)到的鄰接矩陣 ，間歇地對(duì)參考鄰接矩陣 進(jìn)行更新 ：

一般來(lái)說(shuō)

取值要大于 0.99，用來(lái)保證訓(xùn)練的穩(wěn)定性。

受益與結(jié)構(gòu)自引導(dǎo)機(jī)制，SUBLIME 可以很好的解決上述的問(wèn)題。隨著更新過(guò)程，一些 中的噪聲邊權(quán)重逐漸降低。與此同時(shí)，學(xué)習(xí)目標(biāo) 隨著訓(xùn)練過(guò)程發(fā)生改變，其吸收了更多的有益信息來(lái)指導(dǎo)圖結(jié)構(gòu)的學(xué)習(xí)，緩解了過(guò)擬合的問(wèn)題。更重要的是，我們的結(jié)構(gòu)自引導(dǎo)機(jī)制利用所學(xué)的知識(shí)，反過(guò)來(lái)改善學(xué)習(xí)目標(biāo)，不斷推動(dòng)模型發(fā)現(xiàn)更優(yōu)的圖結(jié)構(gòu)。

四、實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

本文在 8 個(gè)數(shù)據(jù)集上展開(kāi)實(shí)驗(yàn)，包括 4 個(gè)圖結(jié)構(gòu)數(shù)據(jù)集（Cora、CiteSeer、PubMed、ogbn-arxiv）以及 4 個(gè)非結(jié)構(gòu)數(shù)據(jù)集（Wine、Cancer、Digits、20news）。我們?cè)趦蓚€(gè)下游任務(wù)（節(jié)點(diǎn)分類(lèi)和節(jié)點(diǎn)聚類(lèi)）上評(píng)估學(xué)習(xí)結(jié)構(gòu)的質(zhì)量，并和一系列先進(jìn)的方法進(jìn)行對(duì)比。

4.2 性能對(duì)比

文中在三個(gè)場(chǎng)景進(jìn)行對(duì)比：結(jié)構(gòu)推理下的節(jié)點(diǎn)分類(lèi)（表1），結(jié)構(gòu)改進(jìn)下的節(jié)點(diǎn)分類(lèi)（表2），以及結(jié)構(gòu)改進(jìn)下的節(jié)點(diǎn)聚類(lèi)（表3）。從實(shí)驗(yàn)結(jié)果可以看出，本文提出的方法在幾乎所有場(chǎng)景和數(shù)據(jù)集中都能取得最優(yōu)或次優(yōu)的性能，說(shuō)明了該方法能夠?qū)W習(xí)到高質(zhì)量且普適的圖結(jié)構(gòu)。

4.3 消融實(shí)驗(yàn)

通過(guò)改變超參數(shù) 的值，文中對(duì)結(jié)構(gòu)自引導(dǎo)機(jī)制開(kāi)展進(jìn)一步研究。實(shí)驗(yàn)結(jié)果可以看出，當(dāng) 時(shí)，SUBLIME 在三個(gè)數(shù)據(jù)集上都具有最佳的性能，說(shuō)明適中的更新強(qiáng)度能夠更好地更新參考視角。通過(guò)進(jìn)一步分析準(zhǔn)確率和損失函數(shù)的變化可以看出，當(dāng) 時(shí)，此時(shí)結(jié)構(gòu)自引導(dǎo)機(jī)制失效，在訓(xùn)練過(guò)程中會(huì)出現(xiàn)過(guò)擬合的情況，導(dǎo)致性能下降。當(dāng) 時(shí)，此時(shí)會(huì)高強(qiáng)度地更新參考視角，導(dǎo)致訓(xùn)練過(guò)程非常不穩(wěn)定，影響最終性能。

4.4 參數(shù)實(shí)驗(yàn)

本實(shí)驗(yàn)研究了兩個(gè)超參數(shù)對(duì)性能的影響，包括隨機(jī)遮掩特征的比率，以及 kNN 稀疏化中 k 的取值。從下圖的實(shí)驗(yàn)結(jié)果可以看出，適中的超參數(shù)取值能帶來(lái)最佳的性能，而過(guò)大/過(guò)小的取值都會(huì)導(dǎo)致模型性能的下降。

4.5 魯棒性分析

為了研究 SUBLIME 在含噪聲圖結(jié)構(gòu)下的性能，文中隨機(jī)地增加或刪除圖結(jié)構(gòu)中的邊，并觀測(cè)該方法在不同比率擾動(dòng)下的性能。由下圖可以看出，相比有監(jiān)督的結(jié)構(gòu)學(xué)習(xí)方法 Pro-GNN，SUBLIME 在兩個(gè)場(chǎng)景下都能取得更好或相當(dāng)?shù)男阅?。尤其在大量邊都被刪除的情況下，SUBLIME 仍然能學(xué)習(xí)到高質(zhì)量的圖結(jié)構(gòu)，遠(yuǎn)超其他方法的性能。

4.6 可視化

為了研究 SUBLIME 究竟學(xué)到了怎樣的圖結(jié)構(gòu)，我們對(duì)學(xué)到的部分圖結(jié)構(gòu)進(jìn)行可視化。我們考慮了兩個(gè)類(lèi)別（C 和 R）的節(jié)點(diǎn)，分別在訓(xùn)練集（L）和測(cè)試集（U）中選擇了 10 個(gè)節(jié)點(diǎn)進(jìn)行可視化。從下圖可以看出，SUBLIME 可以學(xué)習(xí)到大量同類(lèi)節(jié)點(diǎn)之間的連接。同時(shí)，相比有監(jiān)督方法 Pro-GNN，我們的方法能夠均勻地學(xué)習(xí)到每個(gè)節(jié)點(diǎn)之間潛在的連接，而不會(huì)出現(xiàn)邊分布偏差的情況。

五、總結(jié)

本文率先提出了無(wú)監(jiān)督圖結(jié)構(gòu)學(xué)習(xí)的范式，旨在不依賴(lài)標(biāo)簽信息的條件下，從數(shù)據(jù)本身中學(xué)習(xí)更普適、更高質(zhì)量的圖結(jié)構(gòu)。為了解決無(wú)監(jiān)督圖結(jié)構(gòu)學(xué)習(xí)問(wèn)題，本文提出了一種基于結(jié)構(gòu)自引導(dǎo)的自監(jiān)督對(duì)比學(xué)習(xí)方法 SUBLIME，通過(guò)最大化兩個(gè)視角的互信息的方式對(duì)結(jié)構(gòu)進(jìn)行建模、學(xué)習(xí)和優(yōu)化。實(shí)驗(yàn)證明，相比有監(jiān)督方法，我們的方法能夠?qū)W習(xí)到更高質(zhì)量的圖結(jié)構(gòu)。我們的方法有望應(yīng)用于各種實(shí)際應(yīng)用中，包括但不限于生物信息學(xué)研究，腦電波分析，交通流量預(yù)測(cè)以及計(jì)算機(jī)視覺(jué)等領(lǐng)域。