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

本文率先提出了無監(jiān)督圖結構學習的范式，旨在不依賴標簽信息的條件下，從數據本身中學習更普適、更高質量的圖結構。

作者 | Yuki

研究方向 | 推薦系統(tǒng)，圖神經網絡

論文題目：

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

一、前言

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

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

1. 依賴于標簽信息，在有監(jiān)督 GSL 方法中，在進行圖結構優(yōu)化時人工標注的標簽在扮演了至關重要的角色，然而對標簽數據的依賴限制了有監(jiān)督 GSL 的在更廣泛的無標簽數據中的應用；

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

3. 下游任務的局限性，在現有的方法中，結構學習通常依賴節(jié)點分類來提供監(jiān)督信號，因此學習到的圖結構通常是任務特定而不是通用的，可能對于下游其他任務沒有幫助（如鏈接預測和節(jié)點聚類）。

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

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

2. 提出了一種新的無監(jiān)督 GSL 方法——SUBLIME，該方法采用對比學習技術，從原數據本身中獲取監(jiān)督信號來引導結構學習，并同時利用學到的結構信息對監(jiān)督信息進行更新。

3. 大量實驗證明了 SUBLIME 的有效性。

二、問題定義

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

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

結構改進的目標則是從含噪聲的圖結構數據（包含特征矩陣 和鄰接矩陣 ）中對原有的圖結構進行改進得到改進后的圖結構 。本文假設學習得到的圖結構 能夠更好的揭示節(jié)點之間的真實連接關系，并可被廣泛應用于各種下游任務中。

三、方法

本文所提出的 SUBLIME 主要包含了兩個組件：圖結構學習模塊（Graph Structure Learning Module）以及結構自引導對比學習模塊（Structure Bootstrapping Contrastive Learning Module），SUBLIME 的結構圖如圖 2 所示，在圖結構學習模塊中，首先應用圖學習器（Graph Learner）來建模圖結構，然后通過后處理器（Post-Processor）對建模的圖結構進行規(guī)范化。

在結構自引導對比學習模塊中，首先定義了學習者視圖（Learner view）和參考視角（Anchor View）用于對比。具體的，前者由學習到的圖結構構成，后者則從原始數據中初始化而來。然后分別對兩種視角應用數據增強（Data Augmentation）。

接下來最大化兩種視角之間的互信息（Mutual Information），為圖結構學習提供監(jiān)督信號。此外，文中還設計了一種結構自引導機制，利用從學習者視角中學到的信息對參考視角進行優(yōu)化。下面將對上述組件一一介紹。

3.1 圖學習器

圖學習器是 GSL 的關鍵組成部分，其用于學習一個粗略（sketched）鄰接矩陣 ，大多數現有的方法通常采用單一的圖學習器，無法適應不同數據的特性。為了適應不同輸入數據的需要，本文采用了四種圖學習器來建模圖結構，包括一種全圖參數化學習器（FGP Learner），和三種基于度量學習的學習器（Metric Learning-based Learners）。通常圖學習器可以表示為 ， 為模型參數。

FGP 學習器對鄰接矩陣的每個元素都用一個可學習的參數來建模，并應用一個非線性激活函數 來保證訓練的穩(wěn)定性：

而基于度量學習的學習器中，首先會由一個基于神經網絡的嵌入函數來得到節(jié)點嵌入，然后通過無參數的度量函數（比如余弦相似度）來得到鄰接矩陣中的而基于度量學習的學習器中，首先會由一個基于神經網絡的嵌入函數 來得到節(jié)點嵌入，然后通過無參數的度量函數 （比如余弦相似度）來得到鄰接矩陣中的值：

通過定義不同的嵌入函數 ，本文提供了三種不同的學習器：1）注意力學習器（Attentive Learner）；2）多層感知機學習器（MLP Learner）；3）圖神經網絡學習器（GNN Learner）：采用 GNN 進行節(jié)點嵌入的編碼。

注意力學習器采用注意力機制來生成的節(jié)點嵌入：

多層感知機學習器采用多層堆疊的 MLP 層來計算節(jié)點嵌入：

圖神經網絡學習器采用 GNN 進行節(jié)點嵌入的編碼：

在 SUBLIME 中根據數據集特性選擇了最合適的學習器來建模圖結構 。

3.2 后處理器

經由圖學習器得到的鄰接矩陣 通常比較粗糙，無法具備真實圖結構的許多特性。因此，文中使用后處理對這個鄰接矩陣進一步優(yōu)化，從而產生一個精煉的圖鄰接矩陣。后處理器中的步驟主要分為 4 步：

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

2）對稱化 Symmetrization（基于矩陣轉置求平均）與 3）非負化 Activation（基于 ReLU 激活函數）：

4）歸一化 Normalization（基于對稱歸一化處理）：

式中 表示 的都矩陣。

通過上述一系列后處理步驟，最終得到一個稀疏、非負、對稱且正歸一鄰接矩陣 。

3.3 多視角圖對比學習

當對學習到的圖結構（鄰接矩陣）進行建模后，文中采用多視角對比學習的方式，通過從原數據中獲取監(jiān)督信號來指導圖結構的優(yōu)化?；趯W到的鄰接矩陣，我們將其與特征矩陣 進行結合，得到學習者視角（Learner View），記為 。

文中利用原始數據對參考視角（Anchor View）進行初始化，該視角為圖結構的學習提供指引。具體地，若原數據帶有圖結構，我們會將該視角初始化為原始特征矩陣和鄰接矩陣：；若原數據不含圖結構，將其中的鄰接矩陣初始化為單位矩陣：。

視角構建完成后，文中設計兩種數據增廣方式：

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

表示隨機丟棄連接操作符。

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

表示隨機丟棄連接操作符。

通過增大對比學習任務的難度，使模型能夠探索到更高質量的圖結構。

在 SUBLIME 中對學習者視角和參考視角同時使用了上述兩種增廣方式：

值得一提的是為了提高兩個視角間的差異性（上下文差異）。對于隨機遮掩特征，采用了不同的 probabilities，。但是對于隨機丟棄連接，文中使用了相同的 dropping probability，，因為兩個視角的鄰接矩陣本身差異明顯。

下一步，采用節(jié)點級的對比學習模型來最大化兩個視角的互信息。具體地，增廣后兩個視角圖首先經由兩層 GCN 的編碼，得到每個節(jié)點的表征：

表示基于 GCN 的 encoder， 是 encoder 的模型參數。

然后，經過由兩層 MLP 網絡構成的投影網絡，得到兩個視角對應的投影矩陣：

最后，采用 NT-Xent 損失（Normalized Temperature-Scaled Cross-Entropy loss）函數來最大化兩個投影矩陣中對應節(jié)點的相似度，從而最大化兩個視角的互信息：

指代余弦相似度函數， 為溫度系數， 與 同時計算。

3.4 結構自引導機制

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

在自引導（Bootstrapping）的算法的啟發(fā)下，我們設計了一種結構自引導機制（Structure Bootstrapping Mechanism）對參考鄰接矩陣進行更新，從而提供可靠、持續(xù)、有效的結構學習指引。具體地，我們基于 slow-moving 的思想，利用學到的鄰接矩陣 ，間歇地對參考鄰接矩陣 進行更新 ：

一般來說

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

受益與結構自引導機制，SUBLIME 可以很好的解決上述的問題。隨著更新過程，一些 中的噪聲邊權重逐漸降低。與此同時，學習目標 隨著訓練過程發(fā)生改變，其吸收了更多的有益信息來指導圖結構的學習，緩解了過擬合的問題。更重要的是，我們的結構自引導機制利用所學的知識，反過來改善學習目標，不斷推動模型發(fā)現更優(yōu)的圖結構。

四、實驗

4.1 實驗設置

本文在 8 個數據集上展開實驗，包括 4 個圖結構數據集（Cora、CiteSeer、PubMed、ogbn-arxiv）以及 4 個非結構數據集（Wine、Cancer、Digits、20news）。我們在兩個下游任務（節(jié)點分類和節(jié)點聚類）上評估學習結構的質量，并和一系列先進的方法進行對比。

4.2 性能對比

文中在三個場景進行對比：結構推理下的節(jié)點分類（表1），結構改進下的節(jié)點分類（表2），以及結構改進下的節(jié)點聚類（表3）。從實驗結果可以看出，本文提出的方法在幾乎所有場景和數據集中都能取得最優(yōu)或次優(yōu)的性能，說明了該方法能夠學習到高質量且普適的圖結構。

4.3 消融實驗

通過改變超參數 的值，文中對結構自引導機制開展進一步研究。實驗結果可以看出，當 時，SUBLIME 在三個數據集上都具有最佳的性能，說明適中的更新強度能夠更好地更新參考視角。通過進一步分析準確率和損失函數的變化可以看出，當 時，此時結構自引導機制失效，在訓練過程中會出現過擬合的情況，導致性能下降。當 時，此時會高強度地更新參考視角，導致訓練過程非常不穩(wěn)定，影響最終性能。

4.4 參數實驗

本實驗研究了兩個超參數對性能的影響，包括隨機遮掩特征的比率，以及 kNN 稀疏化中 k 的取值。從下圖的實驗結果可以看出，適中的超參數取值能帶來最佳的性能，而過大/過小的取值都會導致模型性能的下降。

4.5 魯棒性分析

為了研究 SUBLIME 在含噪聲圖結構下的性能，文中隨機地增加或刪除圖結構中的邊，并觀測該方法在不同比率擾動下的性能。由下圖可以看出，相比有監(jiān)督的結構學習方法 Pro-GNN，SUBLIME 在兩個場景下都能取得更好或相當的性能。尤其在大量邊都被刪除的情況下，SUBLIME 仍然能學習到高質量的圖結構，遠超其他方法的性能。

4.6 可視化

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

五、總結

本文率先提出了無監(jiān)督圖結構學習的范式，旨在不依賴標簽信息的條件下，從數據本身中學習更普適、更高質量的圖結構。為了解決無監(jiān)督圖結構學習問題，本文提出了一種基于結構自引導的自監(jiān)督對比學習方法 SUBLIME，通過最大化兩個視角的互信息的方式對結構進行建模、學習和優(yōu)化。實驗證明，相比有監(jiān)督方法，我們的方法能夠學習到更高質量的圖結構。我們的方法有望應用于各種實際應用中，包括但不限于生物信息學研究，腦電波分析，交通流量預測以及計算機視覺等領域。