論文筆記 | graph pre-training 系列論文

圖預訓練論文筆記

• • 1. Strategies for pre-training graph neural networks
  • 2. Multi-stage self-supervised learning for Graph Convolutional Networks on graphs with few labeled nodes
  • • Motivation
    • 具體方法
  • 3. GPT-GNN: Generative Pre-training of Graph Neural Networks
  • 4. Pre-training Graph Neural Networks for Generic Structural Feature Extraction
  • • Motivation
    • 具體方法
    • 分析
  • 5. Graph-BERT: Only Attention is Needed for Learning Graph Representation
  • 6. GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
  • 7. Deep Graph InfoMax

1. Strategies for pre-training graph neural networks

ICLR 2020

Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, Jure Leskovec

Stanford University, The University of Iowa, Harvard University

關鍵詞：GNN pre-training, node-level and graph level pre-training tasks

code and data

本文是針對圖資料做的預訓練，作者從兩個次元考慮，将預訓練任務劃分為四種。

本文使用了三個預訓練任務，分别為Attribute masking, Context prediction, supervised attribute prediction。

1. Attribute masking (node-level self-supervised learning)

将圖中15%的節點屬性或者邊屬性mask掉，利用GNN學習節點的embedding，最後接上一個線性模型去預測被mask掉的屬性值。

2. Context prediction (node-level)

利用subgraph去預測周圍的圖結構，目标是預訓練一個GNN模型，這個模型可以使得出現在類似結構中的節點embedding相近。

對于每個節點，有兩種表示，一種是基于k-hop鄰居節點的表示，一種是context graph embedding，圖示如下：

其中，中心節點的K-hop鄰居是指距離該中心節點的最短路徑小于等于K的節點，即上圖中藍色虛線圈内的節點。K-hop neighborhood embedding是指中心節點基于k階鄰居的向量表示，也就是利用GNN（main GNN）疊代k次，學習得到的表示。中心節點的context graph是指該中心節點 r 1 r_1 r1​-hop 到 r 2 r_2 r2​-hop 之間的部分，也就是上圖中小虛線紅圈和大虛線紅圈中間的部分。這個部分與節點的K-hop鄰居節點相交的節點稱為context anchor nodes。通過另一個GNN（context GNN）網絡學習得到節點embedding，然後将context anchor node embedding平均，得到context graph embedding。

得到了兩種表示之後，通過負采樣的方式聯合學習main GNN和context GNN。

這裡的 h v ( K ) T h_v^{(K)T} hv(K)T​ 是指中心節點v通過GNN疊代K次得到的節點表示， c v ′ G ′ c_{v'}^{G'} cv′G′​是context graph embedding。正樣本是中心節點v和v’是同一個節點，負樣本是随機選擇一個與v不同的節點。每個正樣本對應一個負樣本。

學習得到的main GNN作為預訓練後的模型。

3. Supervised attribute prediction (graph-level)

兩個node-level prediction的預訓練任務都是self-supervised的，這裡的graph-level預訓練任務是supervised的。其中的監督信号是圖的label，也就是通過圖的embedding預測其label。

4. graph-level structure prediction

對應的預訓練任務是structure similarity prediciton。相關的工作包括：modeling the graph edit distance (Bai et al., 2019) or predicting graph structure similarity (Navarin et al., 2018)。但是由于graph distance的groundtruth卻反，并且也沒有graph相似度的數值，較難進行預訓練，是以這篇文章就沒有考慮這方面的預訓練任務。

在實驗驗證方面，主要解答了三個問題：

1. 下遊任務中，有預訓練和沒有預訓練的對比，提升了9.4%
2. 本文的node-level和graph-level相結合的預訓練方式，先比于隻進行node-level或者graph-level的預訓練，效果提升5.4%
3. 本文預訓練使用的GIN圖神經網絡，相比于使用GCN、GraphSAGE、GAT等效果要好。

2. Multi-stage self-supervised learning for Graph Convolutional Networks on graphs with few labeled nodes

AAAI 2020

Ke Sun, Zhouchen Lin, Zhanxing Zhu

Peking University, Samsung Research China

key words：multi-stage training, self-supervised learning, few labeled data prediction

Motivation

[Li, Han, and Wu 2018]中解釋了GCN網絡分類效果好的原理，提出GCN的本質是Laplacian smoothing。平滑操作使得在同一個類别中的節點資訊趨同，然後易于分類。但是當GCN網絡深度增加，也有可能導緻over-smoothing，導緻不同類别的節點無法準确識别。

在Karate Club dataset（空手道俱樂部成員關系資料）上利用GCN學習節點表示。這個資料集包含34個節點，78條邊，兩個類别。

【故事：這個空手道俱樂部包含34名成員，管理者 John A 和教官 Mr. Hi 之間的一次沖突導緻這個俱樂部一分為二，一半的成員圍繞着 Mr. Hi 成立了一個新俱樂部，另一半成員要麼找到了新的教練，要麼放棄了空手道。是以，在對應的社交網絡中，節點也被劃分為兩個組，一組屬于Mr. Hi (Instructor) ，另一組屬于John A (Administrator)，其中節點0代表Mr. Hi，節點33代表John A。】

下圖展示了層數不同的GCN對節點進行表示的結果，隻有一成的GCN還無法将節點較好地劃分，兩層為最佳層數，之後，随着層數增加，節點又變得不可分。

這樣的内在特性使得GCN網絡不會太深，導緻标簽無法有效地傳播。是以，GCN在few labeled data上表現不佳。

除此之外，self-supervised learning可以使用資料集本身的資訊來構造僞标簽，是以，可以對few labeled data進行增強。

基于以上兩點，作者想要利用self-supervised learning對資料進行增強，并且設計一種基于GCN的高效訓練算法。

具體方法

作者提出Multi-Stage Self-Supervised Learning (M3S)算法，算法流程圖如下：

M3S可以分為兩個部分：

1. Multi-Stage Training

   

2. DeepCluster + Alignment

   DeepCluster是将節點劃分到k個cluster

   Alignment是将cluster和真正作為标簽的class進行對齊。

   

M3S訓練的完整過程：

1. GCN學習節點表示
2. 利用DeepCluster将節點劃分為k個cluster
3. 對于每個cluster，計算cluster的中心表示；對于每個class，計算每個class的中心表示；通過計算cluster和每個class的距離，确定cluster中未标注節點的pseudo label。
4. 選擇每個類别中置信度最高的節點，進行self-checking，通過的節點則加入labeled set。
5. 再執行下一個階段的訓練。

   

3. GPT-GNN: Generative Pre-training of Graph Neural Networks

KDD 2020

Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, Yizhou Sun

University of California, Microsoft Research

Key words: self-supervised attributed graph generation (attribute generation, edge generation)

本文主要是為了解決GNN在few labeled data上的學習問題。

受到自然語言進行中通過預訓練模型，然後遷移到少标簽樣本資料上的啟發，這裡要做一個GNN的預訓練。

預訓練的任務是self-supervised attributed graph generation，包括兩個具體的任務，分别是attribute generation和edge generation。

4. Pre-training Graph Neural Networks for Generic Structural Feature Extraction

arxiv 2020

Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, Yizhou Sun

University of California

keywords: self-supervised pre-training tasks, 3 levels of graph structures, graph corpus generation

Motivation

訓練GNN往往需要大量有标簽的圖資料，但是在很多場景中，有标簽的資料極少，并且較難進行人工标注。受到自然語言進行中預訓練方法的啟發，作者提出了一個預訓練的架構，希望能夠擷取一般性的圖結構資訊，這種資訊可以比較容易地遷移到下遊任務上去。

圖的結構資訊是包含多個層次的，比如：節點層次，邊層次，子圖層次。而目前的GNN預訓練模型往往隻針對其中一種結構層次進行預訓練，導緻泛化效果不佳。為了擷取多層次的圖結構資訊，作者提出了三個預訓練任務。

具體方法

從預訓練語料、預訓練架構、預訓練任務三個方面進行介紹。

1. 預訓練語料

   這裡使用的預訓練語料不是真實場景下的圖資料，而是由DCBM算法生成的圖資料。該算法生成圖資料的步驟是：首先設定有K個cluster，每個節點随機配置設定到一個cluster。然後遵循cluster内的節點連接配接多于cluster外的節點連接配接的原則，将節點連邊（這個過程也會對節點的度數有一定的限制，比如：節點度數的分布滿足power-law或者uniform）

是以，可以通過控制參數，生成多樣的圖結構，如下圖：

最終，為了預訓練GNN，生成了900個圖作為訓練集，124個圖作為驗證集，節點的個數在100-2000範圍内。

1. 預訓練架構

   GNN預訓練架構如下：

   

在預訓練階段，輸入是給定的圖，提取圖中節點的四方面特征（degree, Core-Number, Collective Influence, Clustering Coefficient），經過歸一化後進行拼接，然後輸入到一個非線性轉換器E，得到節點的初始向量表示。将這個向量表示作為GNN的輸入，輸出基于GNN計算得來的向量表示。最後根據三個自監督的預訓練任務更新模型的參數。

在進行下遊任務時，将GNN模型中的部分層固定，其他層根據下遊任務進行微調。

1. 預訓練任務

   1）Denoising Link Reconstruction （Edge-level）

   将圖中的一部分邊移除，然後訓練GNN網絡，預測兩個節點之間是否存在邊連接配接。

   

2）Centrality Score Ranking （Node-level）

根據GNN生成的節點表示，預測兩個節點的centrality相對排序，與真實的節點centrality比較，最小化損失。

3）Clustering Preserving （Subgraph-level）

給定一個節點，通過GNN生成的節點表示，預測該節點屬于的cluster，與真實的節點所屬cluster進行比較，最小化損失。

分析

創新點：

• 為3-level graph structural information 設計了三個對應的預訓練任務
• 使用生成的資料作為預訓練語料，可以控制資料的多樣性

不足：

• 生成的資料中，節點的初始表示依賴于節點在圖結構中的位置，沒有節點本身的語義特征，一些下遊任務中，節點本身的語義特征較為重要。
• 第三個預訓練任務，優化目标中未包含負樣本。

5. Graph-BERT: Only Attention is Needed for Learning Graph Representation

arxiv 2020

Jiawei Zhang, Haopeng Zhang, Congying Xia, Li Sun

Florida State University, University of Illinois at Chicago, Beijing University

Keywords: linkless subgraph batching, Graph-BERT architecture

本文關注GNN學習節點表示中存在的三個問題：

1. suspended animation problem
2. over-smoothing problem
3. hard to parallel computation for large-sized graph

前兩個問題是說當GNN的層數增加，圖表示性能反而會下降。這是因為GNN本身的特性（在之前的[Li, Han, and Wu 2018]論文中有原理的解釋）。第三個問題是說節點之間的内在互連性質，導緻并行性不佳，并且對于無法放入記憶體的大規模圖，處理起來就更加麻煩。

基于這三個問題，作者做了兩點改進：

1. 模型輸入形式的改進：與之前圖表示模型将整個圖作為輸入不同，這裡是将一個完整的圖，劃分為由每個節點組成的子圖，這些子圖組成batch，輸入到模型中，學習節點的表示。這樣可以達到高效學習節點表示的效果。
2. 預訓練模型架構的改進：将GNN架構改為基于BERT的Graph-BERT架構，這樣可以設計深層的網絡結構，并且模型的并行效率高。

模型架構圖如下：

上圖中主要包含五個部分，分别為：

1. linkless subgraph batching

   這個部分是想要從原本的完整圖中采樣子圖，然後輸入模型。采樣子圖的方式可以參考[Zhang et al. 2018]中的方法。但是這裡采用的是top-k intimacy sampling方法。

   這個方法的具體做法是：首先根據Pagerank算法計算出節點之間的親密度S(i, j)。對于每一個節點，根據親密度排序，選出與該節點top-k親密度的節點，作為該節點的上下文節點，組成子圖，這個子圖是由k+1個節點組成，這些節點直接沒有邊連接配接。

2. node input vector embedding

   這裡采用了四種方式的embedding，得到embedding之後進行加和操作，然後作為Graph-Transformer的初始輸入。

3. graph transformer based encoder

   這個部分就是将上面學到的初始表示輸入到模型中，得到每一層的表示。

4. representation fusion
5. functional component

預訓練任務有兩個：

1. Node Raw Attribute Reconstruction

   經過Graph-BERT得到的節點表示為z_i，通過一個全連接配接層和激活函數的作用，希望能還原到節點的初始表示。

   

優化的損失函數為：

1. Graph Structure Recovery

   根據Graph-BERT中學到的節點表示，預測節點之間是否有邊連接配接，與真實的節點之間親密度進行比較。

   

優化的損失函數為：

下遊任務有兩個：

1. node classification
2. graph clustering

實驗設定上，通過以下幾個方面進行了效果的驗證：

1. 預訓練時模型的收斂速度，說明預訓練模型可以很快收斂
2. 在模型層數增加時，模型在下遊任務上的表現。說明Graph-BERT在層數增加時，不會出現GNN網絡中常見的那兩個問題。
3. Graph-BERT模型和其他baseline在下遊任務上的表現對比。說明Graph-BERT比其他baseline方法好【但這裡的提升較小】
4. subgraph size k 對于模型在下遊任務上的表現和總的時間消耗的影響
5. 不同的graph residual對于模型在下遊任務上的表現的影響
6. 不同的初始化節點表示對于Graph-BERT性能的影響，說明raw feature embedding效果最大，整合四種表示形式，達到最優效果。
7. 有預訓練和沒有預訓練，下遊任務的表現。【這裡沒有預訓練的情況也是直接用的Graph-Bert的網絡架構】
8. 兩個預訓練任務對于模型性能的影響。

一點思考

1. 輸入模型的是subgraph，并行化效率提升，會不會造成語義稀疏性的問題？

2. graph data: node in graphs are orderless

   image/text data: pixel/words have their inferent order

   那麼，對于既有順序，又有跨順序連接配接的情況該如何處理？

6. GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training

KDD 2020

Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding

Tsinghua University, Microsoft Research, Renming University, DAMO Academy

Key words: graph-based contrastive pre-training, GNN, subgraph ( positive / negative instance ) construction

目前的大多數圖表示模型在特定領域的特定資料集上進行學習，無法遷移到其他資料集。而受到自然語言處理和圖像處理領域的預訓練模型的啟發，本文想要做的就是graph-based pre-training。

而做graph-based pre-training的一個重要問題是：how to design the pre-training tasks such that the universal strcutural patterns in and across networks can be captured and further transferred?

**本文借用contrastive learning 的思想設計graph pre-training任務，叫做subgraph instance discrimination。**而要做對比學習，就要确定三個問題，分别是：1. 怎樣确定subgraph instance，也就是确定樣本的格式；2. 怎樣定義相近的和不相近的instance pair，也就是設計正負樣本；3. 怎樣對子圖進行編碼？也就是encoder的架構。

這三個問題的解答是：1. 給定一個中心節點，其 r-ego network中的節點構成的圖成為該中心節點導出的子圖。這裡的r-ego類似r-hop的概念，但計算的是其他節點與中心節點的最短路徑；2. 定義相同的 r-ego network 中采樣出來的子圖是相近的，相反不同 r-ego network中采樣出來的子圖是不相近的；3. 使用GIN做為graph encoder。

如上圖所示，最左邊的兩個圖結構分别是紅色中心節點和藍色中心節點導出的 2-ego network，中間的4個 graph都是根據 2-ego network采樣出來的子圖。前兩個是在第一個 2-ego network中采樣出來的，後兩個是從第二個 2-ego network中采樣出來的。其中第一個子圖作為query graph，通過graph encoder學習每個子圖的表示。然後根據InfoNCE loss最小化 graph q和 k0的距離，最大化graph q 和 k1以及 k2的距離。

考慮到計算資源的限制，這裡使用到End-to-End和MoCO機制，來建構和維護詞典。【這裡不太了解其含義】

預訓練的語料是Facebook, IMDB, DBLP graphs。

一點思考

1. 文中提到GCC關注的是structural similarity, orthogonal to neighborhood similarity（代表性的有Deepwalk, LINE, node2vec等）

   為什麼不能兩方面的相似性都關注呢？

7. Deep Graph InfoMax

ICLR 2019

Petar Velickovic, William Fedus, William L. Hamilton, Pietro Lio, Yoshua Bengio, R Devon Hjelm

University of Cambridge, Google Brain, McGill University

Keywords: Mutual information maximization, context-instance(node representation - entire graph summarization representation)

code

本文是第一個将mutual information maximization應用到圖結構資料上，無監督地學習節點表示的工作，簡稱為DGI。主要是通過最大化local-global（node - entire graph）的互資訊。

要利用互資訊最大化，需要定義正負樣本。這裡的樣本是節點表示和整個圖表示的pair，節點表示是通過encoder學習得到的，整個圖的表示是通過readout将圖中所有節點的表示綜合成一個表示。

• 正樣本

  ( h i , s h_i, s hi​,s) pair

  其中 h i h_i hi​表示節點 v i v_i vi​的表示， s s s表示該節點所在的整個圖的表示。

  利用一個判别器： D : R F × R F → R D: R^F \times R^F \rightarrow R D:RF×RF→R計算節點表示和圖表示的比對程度。比如 D ( h i , s ) D(h_i, s) D(hi​,s) represents the probability scores assigned to this patch-summary pair.

• 負樣本

  ( h i ′ , s h_i', s hi′​,s) pair

  其中 h i ′ h_i' hi′​表示非正樣本的圖中的節點表示， s s s仍然為正樣本中的整個圖的表示。

  對于輸入包含多個圖的場景，可以選擇其他圖中的節點表示作為 h i ′ h_i' hi′​。但本文設定的場景時輸入僅包含一個圖（也就是 (X, A) as input），是以這裡用到了corruption function C : R N ∗ F × R N ∗ N → R M ∗ F × R M ∗ M C: R^{N * F} \times R^{N * N} \rightarrow R^{M * F} \times R^{M * M} C:RN∗F×RN∗N→RM∗F×RM∗M，将原圖轉換為另一個圖，然後選擇其中的節點表示作為 h i ′ h_i' hi′​。

• 損失函數

  利用交叉熵的思想列出損失函數

DGI模型的執行步驟為：

模型整體架構如下：