論文資訊

論文標題：Adaptive Graph Encoder for Attributed Graph Embedding
論文作者：Gayan K. Kulatilleke, Marius Portmann, Shekhar S. Chandra
論文來源：2020, KDD
論文地址：download
論文程式碼：download

1 Introduction

　　基於 GCN 的方法有三個主要缺點：

• • 圖折積濾波器和權值矩陣的糾纏會損害其效能和魯棒性；
  • 圖折積濾波器是廣義拉普拉斯平滑濾波器的特殊情況，但沒有保持最優的低通特性；
  • 現有演演算法的訓練目標通常是恢復鄰接矩陣或特徵矩陣，處理與現實不符；

　　AGE 由兩個模組組成：

• • 拉普拉斯平滑濾波器；
  • 自適應編碼器；

　　首先，一個GCN 編碼器由多個圖折積層組成，每一層包含一個圖折積濾波器 $H$、一個權值矩陣 ($W_1$、$W_2$) 和一個啟用函數。[35] 證明，濾波器和權值矩陣的糾纏並沒有為半監督圖表示學習提供效能增益，甚至損害了訓練效率，因為它加深了反向傳播的路徑。

　　 

　　其次，考慮圖折積濾波器， [18] 在理論上表明，它們實際上是應用於低通去噪的特徵矩陣上的拉普拉斯平滑濾波器 [28]。本文證明了現有的圖折積濾波器並不是最優的低通濾波器，因為它們不能過濾某些高頻噪聲。因此，它們不能達到最好的平滑效果。

　　最後，本文認為這些演演算法的訓練目標（重建鄰接矩陣 [23,31] 或特徵矩陣 [24,32]）與現實應用不相容。具體來說，重構鄰接矩陣是將鄰接矩陣設為地面真值成對相似度，但不適合於缺乏特徵資訊的情況。然而，恢復特徵矩陣將迫使模型記住特徵中的高頻噪聲，因此也是不合適的。

2 Method

　　整體框架：

　　 

　　組成部分：

• • a Laplacian smoothing filter
    • Laplacian Smoothing Filter: The designed filter $H$ serves as a low-pass filter to denoise the high-frequency components of the feature matrix  $\mathrm{X}$ . The smoothed feature matrix  $\tilde{\mathrm{X}}$  is taken as input of the adaptive encoder.
      
  • an adaptive encoder
    • Adaptive Encoder: To get more representative node embeddings, this module builds a training set by adaptively selecting node pairs which are highly similar or dissimilar. Then the encoder is trained in a supervised manner.　　

2.1 Laplacian Smoothing Filter

　　基本假設：圖上鄰居節點具有相似性。

2.1.1 Analysis of Smooth Signals

　　從圖訊號處理的角度來解釋圖平滑。以 $\mathbf{x} \in \mathbb{R}^{n}$ 作為圖訊號，每個節點被分配一個值向量。為測量圖訊號 $x$ 的平滑度，可以計算出圖拉普拉斯矩陣 $L$ 和 $x$ 上的瑞利商：

　　　　${\large R(\mathbf{L}, \mathbf{x})=\frac{\mathbf{x}^{\boldsymbol{\top}} \mathbf{L} \mathbf{x}}{\mathbf{x}^{\top} \mathbf{x}}=\frac{\sum\limits_{(i, j) \in \mathcal{E}}\left(x_{i}-x_{j}\right)^{2}}{\sum\limits_{i \in \mathcal{V}} x_{i}^{2}}}  \quad\quad\quad(1)$

　　PS：拉普拉斯矩陣的性質

　　$\begin{aligned}f^{T} L f &=f^{T} D f-f^{T} W f \\&=\sum \limits_{i=1}^{N} d_{i} f_{i}^{2}-\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N} w_{i j} f_{i} f_{j} \\&=\frac{1}{2}\left(\sum \limits_{i=1}^{N} d_{i} f_{i}^{2}-2 \sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N} w_{i j} f_{i} f_{j}+\sum \limits_{j=1}^{N} d_{j} f_{j}^{2}\right) \\&=\frac{1}{2}\left(\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N} w_{i j} f_{i}^{2}-2 \sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N} w_{i j} f_{i} f_{j}+\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N} w_{i j} f_{j}^{2}\right) \\&=\frac{1}{2} \sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N} w_{i j}\left(f_{i}-f_{j}\right)^{2}\end{aligned}$

　　$\text{Eq.1}$ 顯然是 $x$ 的標準化方差分數。平滑訊號應該在相鄰節點上分配相似的值。因此，假設瑞利商較低的訊號更平滑，接著給出特徵向量 $u_i$ 的光滑性度量：

　　　　${\large R\left(\mathbf{L}, \mathbf{u}_{i}\right)=\frac{\mathbf{u}_{i}^{\top} \mathbf{L} \mathbf{u}_{i}}{\mathbf{u}_{i}^{\top} \mathbf{u}_{i}}=\lambda_{i}}  \quad\quad\quad(2)$

　　$\text{Eq.2}$ 表示平滑的特徵向量與較小的特徵值相關聯，即較低的頻率。因此，基於$\text{Eq.1}$、$\text{Eq.2}$   $L$ 分解訊號 $x$):

　　　　$\mathbf{x}=\mathbf{U p}=\sum\limits _{i=1}^{n} p_{i} \mathbf{u}_{i} \quad\quad\quad(3)$

　　其中 $p_{i}$ 是特徵向量 $\mathbf{u}_{i}$ 的係數，那麼 $x$ 的平滑度是：

　　　　${\large R(\mathbf{L}, \mathbf{x})=\frac{\mathbf{x}^{\top} \mathbf{L} \mathbf{x}}{\mathbf{x}^{\top} \mathbf{x}}=\frac{\sum \limits_{i=1}^{n} p_{i}^{2} \lambda_{i}}{\sum \limits_{i=1}^{n} p_{i}^{2}}  }   \quad\quad\quad(4)$

　　因此，為獲得更平滑的訊號，本文濾波器的目標是在保留低頻分量的同時濾掉高頻分量。

2.1.2 Generalized Laplacian Smoothing Filter

　　如[28]所述，廣義拉普拉斯平滑濾波器為：

　　　　$\mathbf{H}=\mathbf{I}-k \mathbf{L}    \quad\quad\quad(5)$

　　採用 $\mathbf{H}$ 作為濾波器矩陣，濾波後的訊號 $\tilde{\mathbf{x}}$ 為：

　　　　${\large \tilde{\mathbf{x}}=\mathbf{H x}=\mathbf{U}(\mathbf{I}-k \Lambda) \mathbf{U}^{-1} \mathbf{U p}=\sum \limits_{i=1}^{n}\left(1-k \lambda_{i}\right) p_{i} \mathbf{u}_{i}=\sum \limits_{i=1}^{n} p^{\prime} \mathbf{u}_{i}  } \quad\quad\quad(6)$

　　因此，為實現低通濾波(low-pass filtering)，頻率響應函數 $1-k \lambda$ 應是一個遞減和非負函數。疊加 $t$ 次拉普拉斯平滑濾波器，將濾波後的特徵矩陣 $\tilde{\mathbf{X}}$ 表示為

　　　　$\tilde{\mathbf{X}}=\mathbf{H}^{t} \mathbf{X}   \quad\quad\quad(7)$

　　請注意，該過濾器根本是非引數化的。

2.1.3  The Choice of k

　　在實踐中，使用重整化技巧 $\tilde{\mathrm{A}}=\mathrm{I}+\mathbf{A}$，採用對稱歸一化圖拉普拉斯矩陣

　　　　$\tilde{\mathbf{L}}_{s y m}=\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{L}} \tilde{\mathbf{D}}^{-\frac{1}{2}}   \quad\quad\quad(8)$

　　此時濾波器為：

　　　　$\mathbf{H}=\mathbf{I}-k \tilde{\mathbf{L}}_{s y m}  \quad\quad\quad(9)$

　　注意，如果設定 $k=1$，濾波器將成為 GCN 濾波器。
　　為選擇最優 $k$，需要計算特徵值 $\tilde{\Lambda}$ 的分佈（由 $\tilde{\mathbf{L}}_{s y m}=\tilde{\mathbf{U}} \tilde{\Lambda} \tilde{U}^{-1}$ 分解得到）。

　　$\tilde{\mathbf{x}}$ 的平滑度是

　　　　${\large R(\mathbf{L}, \tilde{\mathbf{x}})=\frac{\tilde{\mathbf{x}}^{\top} \mathbf{L} \tilde{\mathbf{x}}}{\tilde{\mathbf{x}} \boldsymbol{\tilde { \mathbf { x } }}}=\frac{\sum_{i=1}^{n} p^{\prime}{ }_{i}^{2} \lambda_{i}}{\sum_{i=1}^{n} p^{\prime}{ }_{i}^{2}}}  \quad\quad\quad(10)$

　　因此，$p^{\prime}{ }_{i}^{2}$ 應隨 $\lambda_{i}$ 的增加而減少。將最大特徵值表示為 $\lambda_{\max }$，理論上，如果 $k>1 / \lambda_{\max }$ ，濾波器在 $\left(1 / k, \lambda_{\max }\right]$ 內不是低通，因為 $p^{\prime}{ }_{i}^{2}$ 在這個間隔內增加；如果 $k<1 / \lambda_{\max }$ 該濾波器不能使去出高頻噪聲部分。因此，$k=1 / \lambda_{\max }$ 是最優選擇。

　　[7] 證明了拉普拉斯特徵值的範圍在 $\text{0~2}$ 之間，因此GCN濾波器在 $(1,2]$ 區間內不是低通的。工作 [31] 相應地選擇了 $k=1/2$，然而，我們的實驗表明，在重整化後，最大特徵值 $\lambda_{\max }$ 將縮小到 $3/2$ 左右，這使得 $1/2$ 不是最優。在實驗中，我們計算每個資料集的 $\lambda_{\max }$，並設定 $k=1 / \lambda_{\max }$，並進一步分析了不同 $k$ 值的影響。

3 Adaptive Encoder

　　通過 $t$ 層拉普拉斯平滑過濾，輸出特徵更平滑，保持豐富的屬性資訊。本文自適應地選擇高相似度的節點對作為正訓練樣本，而低相似度的節點對作為負訓練樣本。

　　給定過濾後的節點特徵 $\tilde{\mathbf{X}}$，節點嵌入由線性編碼器 $f$ 進行編碼：

　　　　$\mathbf{Z}=f(\tilde{\mathbf{X}} ; \mathbf{W})=\tilde{\mathbf{X}} \mathbf{W}  \quad\quad\quad(11)$

　　其中，$\mathbf{W}$ 是權重矩陣。然後，為度量節點的成對相似度，利用餘弦相似度。相似度矩陣 $S$ 為：

　　　　$\mathrm{S}=\frac{\mathrm{ZZ}^{\boldsymbol{T}}}{\|\mathrm{Z}\|_{2}^{2}}   \quad\quad\quad(12)$

　　接下來，我們將詳細描述我們的訓練樣本選擇策略。

3.1 Training Sample Selection.

　　在計算相似矩陣後，對相似序列按降序排列。這裡 $r_{i j}$ 是節點對的排序位置  $\left(v_{i}, v_{j}\right)$。然後將正樣本的最大排序位置設為 $r_{p o s}$，將負樣本的最小排序位置設為 $r_{n e g}$。因此，為節點對 $\left(v_{i}, v_{j}\right)$ 生成的標籤為

　　$l_{i j}=\left\{\begin{array}{ll}1 & r_{i j} \leq r_{p o s} \\0 & r_{i j}>r_{n e g} \\\text { None } & \text { otherwise }\end{array}\right.   \quad\quad\quad(13)$

　　這樣，構造了一個包含  $r_{\text {pos }}$  個正樣本和  $n^{2}-r_{n e g}$  個負樣本的訓練集。在第一次構造訓練集時，由於編碼器沒有被認訓練， 直接使用平滑的特徵來初始化  $\mathbf{S}$  :

　　　　$\mathbf{S}=\frac{\widetilde{\mathbf{X}} \widetilde{\mathbf{X}}^{\mathbf{T}}}{\|\widetilde{\mathbf{X}}\|_{2}^{2}}   \quad\quad\quad(14)$

　　構造好訓練集後，可以用監督的方式訓練編碼器。在真實世界的圖中，不相似的節點對總是遠遠多於正節點對，因此在訓 練集中選擇多於  $r_{p o s}$  個負樣本。為了平衡正/負樣本，在每次迭代中隨機選擇  $r_{p o s}$  個負樣本。平衡訓練集用  $\mathcal{O}$  表示。因 此，交叉熵損失表示如下:

　　　　$\mathcal{L}=\sum \limits_{\left(v_{i}, v_{j}\right) \in O}-l_{i j} \log \left(s_{i j}\right)-\left(1-l_{i j}\right) \log \left(1-s_{i j}\right)   \quad\quad\quad(15)$

3.2 Thresholds Update

　　在實踐中，隨著訓練過程的進行，$r_{\text {pos }}$ 減少，而 $r_{n e g}^{s t}$ 呈線性增加。將初始閾值設定為 $r_{\text {pos }}^{s t}$ 和 $r_{n e g}^{s t}$，最終閾值設定為 $r_{\text {pos }}^{e d}$ 和 $r_{n e g}^{e d}$ 。有 $r_{\text {pos }}^{e d} \leq r_{\text {pos }}^{s t}$ 和 $r_{n e g}^{e d} \geq r_{\text {neg. }}^{s t}$。假設閾值被更新為 $T$次，我們將更新策略表示為

　　　　${\large r_{\text {pos }}^{\prime}=r_{p o s}+\frac{r_{\text {pos }}^{e d}-r_{\text {pos }}^{s t}}{T}}     \quad\quad\quad(16)$

　　　　${\large r_{n e g}^{\prime}=r_{n e g}+\frac{r_{n e g}^{e d}-r_{n e g}^{s t}}{T}}      \quad\quad\quad(17)$

　　隨著訓練過程的進行，每次閾值更新時，都會重建訓練集並儲存嵌入。

　　對於節點聚類，我們對儲存嵌入的相似矩陣進行譜聚類[22]，利用戴維斯堡丁索引[8](DBI)選擇最佳時期，在沒有標籤資訊的情況下測量聚類質量。對於鏈路預測，我們在驗證集上選擇執行得最好的歷元。Algorithm 1 給出了計算嵌入矩陣 $Z$ 的總體過程。

　　

4 Experiments

資料集

　　

節點聚類

　　 

-----------------------------------------------------------------------------------------------------

https://zhuanlan.zhihu.com/p/440760513

https://zhuanlan.zhihu.com/p/432080955