技術文章 » 圖機器學習：從圖譜角度來理解圖增廣

圖機器學習：從圖譜角度來理解圖增廣

2023-10-23 15:02:59

1 導引

圖對比學習（Graph Contrastive Learning, GCL）[1][2][3] 旨在以自監督的方式學習圖的節點表徵，其流程如下圖所示：

具體而言，先以特定方式對原圖\(\mathbf{A}\)進行增廣，得到兩個增廣後的檢視（view）\(\mathbf{V}_1\)和\(\mathbf{V_2}\)做為對比對（也可以是原圖和增廣後的檢視做為對比對），並經由GCN進行編碼得到兩個增廣檢視中的節點embeddings。接著，對於某個目標節點\(i\)，我們需要使其在某個增廣檢視中的embedding去接近在另一個增廣檢視中的正樣本embedding，而遠離負樣本embedding。以這種方式建立的模型能夠辨別相似與不相似的節點。一些圖對比學習方法會使用經典的InfoNCE損失來作為優化目標：

\[\mathcal{L}\left(\boldsymbol{h}_i^{\mathbf{V}_1}, \boldsymbol{h}_i^{\mathbf{V}_2}\right)=\log \frac{\exp \left(\mathcal{D}\left(\boldsymbol{h}_i^{\mathbf{V}_1}, \boldsymbol{h}_i^{\mathbf{V}_2}\right) / \tau\right)}{\exp \left(\mathcal{D}\left(\boldsymbol{h}_i^{\mathbf{V}_1}, \boldsymbol{h}_i^{\mathbf{V}_2}\right) / \tau\right)+\sum_{k \neq i} \exp \left(\theta\left(\boldsymbol{h}_{i}^{\mathbf{V}_1}, \boldsymbol{h}_{\mathbf{k}}^{\mathbf{V}_2}\right) / \tau\right)} \]

這裡\(\boldsymbol{h}^{\mathbf{V}_1}\)和\(\boldsymbol{h}^{\mathbf{V}_2}\)分別是在增廣檢視\(\mathbf{V}_1\)和\(\mathbf{V}_2\)中節點\(i\)的embeddings；\(\mathcal{D}(\cdot, \cdot)\)是一個相似性度量，比如餘弦相似度；\(\tau\)是溫度引數。總loss為：\(\mathcal{L}_{\text {InfoNCE }}=\sum_i \frac{1}{2}\left(\mathcal{L}\left(\boldsymbol{h}_{i}^{\mathbf{V}_1}, \boldsymbol{h}_{i}^{\mathbf{V}_2}\right)+\mathcal{L}\left(\boldsymbol{h}_{i}^{\mathbf{V}_2}, \boldsymbol{h}_{i}^{\mathbf{V}_1}\right)\right)\)。

結構不變數（structural invariance） 我們在部落格《尋找領域不變數：從生成模型到因果表徵》中提到過，自監督學習/對比學習本質上是在從資料中提取出在多個領域/檢視中的不變數（invariance）。同理，理想的GCL應該能夠捕捉到圖的結構不變數，也即定義為當對輸入圖的結構屬性造成較大變化（如擾動一定數量的邊）時編碼器輸出的不變數，形式化地表示如下：

\[\mathcal{L}_{\mathrm{CCL}}(\mathbf{A}, t(\mathbf{A}), \boldsymbol{\Theta}) \leq \sigma, \text { s.t. } t(\mathbf{A})=\operatorname{argmax}_{\|\mathbf{A}-t(\mathbf{A})\|_{1}\leqslant \epsilon} \mathcal{D}(p(\mathbf{A}), p(t(\mathbf{A}))) \]

這裡\(t(\cdot)\)為對圖所採用的拓撲增廣，\(\mathcal{D}(\cdot, \cdot)\)為距離度量，\(p(\cdot)\)為表示圖結構屬性的向量值函數，比如圖的直徑、圖是否連通、圖的聚類係數等。

為了經由GCL來捕捉結構不變數，有效的增廣應該關注于敏感的邊，對這些邊的擾動能夠輕易地造成較大的圖屬性改變。接著在最小化對比損失\(\mathcal{L}_{\text{GCL}}\)的過程中，造成結構不穩定的邊會被視為噪聲，從而和這些邊相關的資訊會被編碼器忽視（也即InfoMin準則[4]）。不過，均勻隨機的邊擾動很難做為有效的增廣來使用，這啟發我們去構思比均勻擾動更好的圖增廣方法。

圖譜（graph spectrum） 我們知道圖譜可以做為許多圖的結構屬性的一個綜合性總結，包括聚類係數、連通性等等。那麼，基於圖譜的圖增廣方法就是順理成章的了（參見我的部落格《譜圖論：Laplacian運算元及其譜性質》），這種增廣方法我們一般稱為圖的譜增廣（spectral augmentation）。在介紹具體的譜增廣方法之前，我們先來回顧一下譜圖論的一些基本定義。

設\(\mathcal{G}=(\mathcal{V}, \mathcal{E})\)為無向圖，這裡\(\mathcal{V}\)為節點集合且\(\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}\)為邊集合。所有的邊形成了鄰接矩陣\(\mathbf{A}\in\{0, 1\}^{N\times N}\)，這裡\(\mathbf{A}_{ij}\in\{0, 1\}\)表示\(\mathcal{V}\)中的節點\(i\)和\(j\)之間的關係。節點的度矩陣\(\mathbf{D}=\operatorname{diag}\left(d_1, \ldots d_n\right)\)，這裡\(d_i=\sum_{j \in \mathcal{V}} \mathbf{A}_{i j}\)是節點\(i\in\mathcal{V}\)的度。圖\(\mathcal{G}\)常常和節點特徵矩陣\(\mathbf{X} = [\boldsymbol{x_1}, \boldsymbol{x_2}, \cdots, \boldsymbol{x_N}]\in\mathbb{R}^{N\times d}\)相關聯，這裡\(\boldsymbol{x}_i\)是節點\(i\in\mathcal{V}\)的\(d\)維特徵向量。設\(\mathbf{L} = \mathbf{D} - \mathbf{A}\)為圖\(\mathcal{G}\)的未歸一化圖Laplacian矩陣。若我們設對稱歸一化鄰接矩陣（即我們在部落格《譜圖論：Laplacian二次型和Markov轉移運算元》中所提到的Markov轉移矩陣）為

\[\hat{\mathbf{A}} = \mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}， \]

則對稱歸一化圖Laplacian矩陣可以定義為：

\[\hat{\mathbf{L}} = \mathbf{I}_n - \hat{\mathbf{A}} = \mathbf{D}^{-\frac{1}{2}}(\mathbf{D} - \mathbf{A})\mathbf{D}^{-\frac{1}{2}} \]

由於\(\hat{\mathbf{L}}\)是對稱歸一化的，則其特徵分解（譜分解）為：

\[\hat{\mathbf{L}} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\top}， \]

這裡\(\mathbf{\Lambda}=\operatorname{diag}\left(\lambda_1, \ldots, \lambda_N\right)\)與\(\mathbf{U} = [\boldsymbol{u}^T_1,\cdots, \boldsymbol{u}^T_N]\in \mathbb{R}^{N\times N}\)分別為\(\hat{\mathbf{L}}\)的特徵值和特徵向量。不失一般性，我們假設

\[0 \leq \lambda_1 \leq \cdots \leq \lambda_N<2\quad (\lambda_N\approx 2) \]

這裡我們近似\(\lambda_N\approx 2\)[5]。令\(\mathcal{F}_{\mathcal{L}}=\left\{\lambda_1, \cdots, \lambda_{\lfloor N / 2\rfloor}\right\}\)表示圖低頻分量（low-frequency components）的幅值，\(\mathcal{F}_{\mathcal{H}}=\left\{\lambda_{[N / 2]+1}, \ldots, \lambda_N\right\}\)為圖高頻分量（high-frequency components）的幅值。圖譜定義為這些不同頻率的分量的幅值集合，我們將其表示為\(\varphi(\lambda)\)。直觀上，圖譜表示了圖頻率的增強和減弱情況。此外，我們將\(\hat{\mathbf{L}}\)重寫為

\[\hat{\mathbf{L}} = \lambda_1 \cdot \boldsymbol{u}_{\mathbf{1}} \boldsymbol{u}_{\mathbf{1}}^{\top}+\cdots+\lambda_N \cdot \boldsymbol{u}_N \boldsymbol{u}_N^{\top}， \]

我們定義\(\boldsymbol{u}_i \boldsymbol{u}_i^{\top} \in \mathbb{R}^{N \times N}\)為和\(\lambda_i\)相關的特徵空間，記為\(\mathbf{S}_i\)。

2 論文閱讀

2.1 NIPS2022 《Revisiting graph contrastive learning from the perspective of graph spectrum》

本文的思路在於：好的增廣能夠使圖高頻訊號之間的差異大於低頻訊號。這基於一個事實：GNN是低通濾波器，也即能較好地去篩選出低頻的訊號，使得節點特徵更加平滑（相似節點特徵相似，預測結果相似）[6]。對於節點標籤一致的同構圖（本文所關注的物件）而言，低頻資訊差異性更小的話可以更好地把圖同構的資訊保留住。不過需要注意的是，該準則只在同構圖的前提下成立，否則對於異構圖的話高頻資訊就會更加有用。作者將使得低頻之間差異小的增廣對稱為最優對比對（optimal contrastive pair），如下圖所示：

可見對於最優對比對\(V_1\)和\(V_2\)而言，低頻分量幅值\(\phi\)的差異相比高頻分量更小。這裡的幅值（縱軸）\(\phi\)為鄰接矩陣\(\mathbf{A}\)對應分量的特徵值\(\kappa\)，其與歸一化Laplacian矩陣特徵值（橫軸）\(\lambda\)的關係為\(\kappa = 1 - \lambda (\lambda \in [0, 2], \kappa \in [-1,1])\)。注意，上述關係是針對某一個檢視而言的，但某個檢視中的分量在其它檢視的幅值相對於原檢視橫軸肯定就不滿足此關係了，所以上圖中\(V_2\)的線滿足\(\kappa = 1 - \lambda\)但\(V_1\)的線就不滿足。

形式化地說，本文提出的圖增廣準則（Graph augmentation rule, GAME）如下：給定兩個隨機增廣\(\mathbf{V}_1\)和\(\mathbf{V}_2\)，設它們的圖譜分別為\(\phi_{\mathbf{V}_1}(\lambda)\)和\(\lambda_{\mathbf{V}_2}(\lambda)\)。則對\(\forall \lambda_m \in [1, 2]\)（高頻）與\(\lambda_n \in [0, 1]\)（低頻）, 當下列條件滿足時\(\mathbf{V}_1\)和\(\mathbf{V}_2\)是一個有圖增廣的有效對:

\[\left|\phi_{\mathbf{V}_1}\left(\lambda_m\right)-\phi_{\mathbf{V}_2}\left(\lambda_m\right)\right|>\left|\phi_{\mathbf{V}_1}\left(\lambda_n\right)-\phi_{\mathbf{V}_2}\left(\lambda_n\right)\right| \]

作者將這樣的一個增廣對定義為最優對比對。

有了這樣一個準則之後，我們如何確定需要變化哪一些邊呢？通過矩陣擾動理論（matrix perturbation theory）[7]，我們能夠找到鄰接矩陣的變化量和特徵值變化量之間的關係：

\[\Delta \lambda_i=\lambda_i^{\prime}-\lambda_i=\boldsymbol{u}_i^{\top} \Delta \mathbf{A} \boldsymbol{u}_i-\lambda_i \boldsymbol{u}_i^{\top} \Delta \mathbf{D} \boldsymbol{u}_i+\mathcal{O}(\|\Delta \mathbf{A}\|), \]

這裡\(\lambda^{\prime}_i\)為變化之後的特徵值，\(\Delta \mathbf{A}={\mathbf{A}}^{\prime}-\mathbf{A}\)為增廣之後邊的變化量，而\(\mathbf{D}\)為度矩陣相應的變化量。注意這裡不能使用特徵值分解來獲得\(\mathbf{A}^{\prime}\)的特徵值\(\lambda^{\prime}\)，因為所得到的\(\lambda^{\prime}\)相對於之前\(\mathbf{A}\)的\(\lambda\)是無序的。也就是說，對於\(\mathbf{A}\)的某個特徵值\(\lambda_i\)，我們不能確定\(\mathbf{A}^{\prime}\)的哪個特徵值在分解後與其對應，所以在這種情況下我們就不能計算\(\lambda_i\)的改變數\(\Delta \lambda_i\)。

作者按照上述等式計算每次增廣後的鄰接矩陣特徵值\(\{\lambda^{\prime}_i\}\)，並將它們的圖譜給繪製出來。此外，作者還設定了多種圖增廣方式做為對比，如下圖所示：

上圖中的虛線左半部分為增廣前的Laplacian矩陣的圖譜和鄰接矩陣的圖譜，虛線右半部分為採用不同增廣方法進行增廣後的鄰接矩陣的圖譜。可以看到，如果將鄰接矩陣\(\mathbf{A}\)的譜做為幅值，PPP Matrix、Heat Matrix、Distance這三種增廣方式最符合我們的效果：他們在低頻\(\mathcal{F}_{\mathcal{L}}\)上隨\(\mathbf{A}\)的幅值變化小，在高頻\(\mathcal{F}_{\mathcal{H}}\)上隨\(\mathbf{A}\)的幅值變化大（圖中紅框中所示的內容）。因此，它們的表現優於上圖中的其它增廣方式。

作者還在理論層面分析了GAME法則和對比損失\(\mathcal{L}_{\text{infoNCE}}\)的關係。給定鄰接矩陣\(\mathbf{A}\)和其所生成的增廣\(\mathbf{V}\)，\(\mathbf{A}\)和\(\mathbf{V}\)第\(i\)個頻率的幅值分別是\(\lambda_i\)和\(\gamma_i\)。對於所要最小化的InfoNCE損失\(\mathcal{L}_{\text{infoNCE}}\)而言，其上界可表示如下：

\[\mathcal{L}_{\text {InfoNCE }} \leq \frac{1+N}{2} \sum_i \theta_i\left[2-\left(\lambda_i-\gamma_i\right)^2\right] \]

最小化對比損失等價於最小化其上界。所以，較大的\(\theta_i\)會被賦給較小的\((\lambda_i - \gamma_i)^2\)（以更關注低頻資訊）。同時，如果\(\lambda_i \approx \gamma_i\)，則這兩個對比增廣可以被視為是共用在\(i\)頻率的不變數。因此，通過對比學習，編碼器會從譜域去強調兩個對比增廣之間的不變數。回憶我們之前所說的，GAME法則意味著各個增廣在\(\mathcal{F}_{\mathcal{L}}\)的差異應該較小，而圖對比學習則嘗試捕捉兩個增廣共同的低頻資訊。因此，GAME法則指出了一個操縱編碼器來捕捉低頻資訊的一個通用的策略，並取得了更好的表現。

接下來我們來看學習一個通用的且利於圖對比的變換\(\Delta_{\mathbf{A}}\)來用於鄰接矩陣\(\mathbf{A}\)，以產生對應的增廣\(\mathbf{A}\_\)（\(\Delta_A = \mathbf{A}\_ - \mathbf{A}\)）。這裡\(\mathbf{A}\)和\(\mathbf{A}\_\)要求是最優對比對。

首先，作者將\(\Delta \mathbf{A}\)分解為了\(\Delta \mathbf{A} = \Delta_{\mathbf{A}+} - \Delta_{\mathbf{A}-}\)，這裡\(\Delta_{\mathbf{A}+}\)和\(\Delta_{\mathbf{A}-}\)分別表示加的邊和刪除的邊。接著，我們來看如何學得\(\Delta_{\mathbf{A}+}\)，\(\Delta_{\mathbf{A}\_}\)同理。

作者設計了下列的關於\(\Delta_{\mathbf{A}+}\)的優化目標（最大化）：

\[\mathcal{J}=\underbrace{\left\langle\mathcal{C}, \Delta_{\mathbf{A}+}\right\rangle^2}_{\text {Matching Term }}+\underbrace{\epsilon H\left(\Delta_{\mathbf{A}+}\right)}_{\text {Entropy Reg. }}+\underbrace{\left\langle\mathbf{f}, \Delta_{\mathbf{A}+} \mathbb{1}_n-\mathbf{a}\right\rangle+\left\langle\mathbf{g}, \Delta_{\mathbf{A}+}^{\top} \mathbb{1}_n-\mathbf{b}\right\rangle}_{\text {Lagrange Constraint Conditions }}, \]

該優化目標包含了3個組成部分：

  • \(\left\langle\mathcal{C}, \Delta_{\mathbf{A}}\right\rangle^2\)：該項是匹配項，旨在使對圖的改變數\(\Delta_{\mathbf{A}+}\)和餘弦定義好的矩陣\(\mathcal{C}\)是「匹配」或相似的。這裡\(\langle \mathbf{A}, \mathbf{Q}\rangle = \sum_{ij}\mathbf{P}_{ij}\mathbf{Q}_{ij}\)，\(\mathbf{C} = \mathbf{U}g(\lambda)\mathbf{U}^T\)（\(g(\lambda)\)為關於\(\mathbf{A}\)的單調遞增函數）。這裡的動機在於，根據GAME法則，若設\(\phi_{\Delta}(\lambda)=\left|\phi_{\mathbf{A}}(\lambda)-\phi_{\mathbf{A}_{-}}(\lambda)\right|\)，則我們需要\(\phi_{\Delta}(\lambda_m) > \phi_{\Delta}(\lambda_n), \forall \lambda_m\in [1, 2] \text{ and } \lambda_n \in [0, 1]\)，因此我們需要規定\(\phi_{\Delta}(\lambda)\)應該是一個單調遞增函數。由於\(\mathcal{C}\)會指導\(\Delta_{\mathbf{A}+}\)來捕捉圖譜的變化量（\(\phi_{\Delta}(\lambda)\)），我們自然會將\(\mathcal{C}\)中的\(g(\lambda)\)設定為一個單調遞增函數。事實上，圖Laplacian矩陣\(\mathcal{L}\)的圖譜就滿足我們這裡對\(g(\lambda)\)的要求，因此我們可以簡單地設\(\mathcal{C} = \mathcal{\Theta}\mathcal{L}\)，這裡\(\Theta\)是一個在訓練中更新的引數。

  • \(\epsilon H\left(\Delta_{\mathbf{A}+}\right)\)：該項為熵正則，旨在增加所學得的\(\Delta_{\mathbf{A}+}\)的不確定性，促使更多的邊（\(\Delta_{\mathbf{A}+}\)中的條目）能夠加入到優化中來。這裡\(H(\mathbf{P})=-\sum_{i, j} \mathbf{P}_{i, j}\left(\log \left(\mathbf{P}_{i, j}\right)-1\right)\)，\(\epsilon\)是該項的權重。

  • \(\left\langle\boldsymbol{f}, \Delta_{\mathbf{A}+} \mathbf{1}_n-\boldsymbol{a}\right\rangle\)和\(\left\langle\boldsymbol{g}, \Delta_{\mathbf{A}+}^{\top} \mathbf{1}_n-\boldsymbol{b}\right\rangle\)：分別對\(\Delta_{\mathbf{A}+}\)的行向量和列向量做拉格朗日約束，使得變化不要太大。這裡\(\boldsymbol{f}\in \mathbb{R}^{N}\)和\(\boldsymbol{g}\in\mathbb{R}^N\)是拉格朗日乘子，\(\boldsymbol{a}\in\mathbb{R}^N\)和\(\boldsymbol{b}\in \mathbb{R}^N\)是概率分佈（本文定義為節點的度分佈）。

不過，要求解這個問題也是不容易的，因為它是個離散優化問題。本文證明了它有下列解：

\[\Delta_{\mathbf{A}+}=\operatorname{diag}(\boldsymbol{u}) \exp \left(2\langle\mathcal{C}, \Delta_{A+}^{\prime}\rangle\mathcal{C} / \epsilon\right) \operatorname{diag}(\boldsymbol{v})=\mathbf{U}_{+} \mathbf{K}_{+} \mathbf{V}_{+} \]

（\(\Delta_{\mathbf{A}-}\)同理）

這裡\(\mathbf{U}_{+}=\operatorname{diag}\left(\boldsymbol{u}_i\right)=\operatorname{diag}\left(\exp \left(\frac{\boldsymbol{f}_i}{\epsilon}\right)\right)\)，\(\mathbf{V}_{+}=\operatorname{diag}\left(\boldsymbol{v}_j\right)=\operatorname{diag}\left(\exp \left(\frac{\boldsymbol{g}_j}{\epsilon}\right)\right)\)。為了進一步計算\(\mathbf{U}_{+}\)和\(\mathbf{V}_{+}\)，作者根據拉格朗日約束條件來約束\(\Delta \mathbf{A}_{+}\)的行和與列和：

\[\boldsymbol{u}=\left(\mathbf{K}_{+} \boldsymbol{v}\right)=\boldsymbol{a} \text { and } \boldsymbol{v} *\left(\mathbf{K}_{+}^{\top} \boldsymbol{u}\right)=\boldsymbol{b} \]

接著，作者採用Sinkhorn迭代來解決這個矩陣縮放（matrix scaling）問題：

\[\boldsymbol{u}^{(l+1)} = \boldsymbol{a} /\left(\mathbf{K}_{+} \boldsymbol{v}^{(0)}\right) \text { and } \boldsymbol{v}^{(l+1)}= \boldsymbol{b} /\left(\mathbf{K}_{+}^{\mathrm{T}} \boldsymbol{u}^{(l+1)}\right) \]

最後，算得\(\Delta_{\mathbf{A}}=\Delta_{\mathbf{A}+}-\Delta_{\mathbf{A}-}\)，從而得到圖增廣：

\[\mathbf{A}_{-}=\mathbf{A}+\eta \cdot \mathbf{S} \odot \Delta_{\mathbf{A}} \]

本文的完整演演算法如下圖所示：

2.2 ICLR2023 《Spectral augmentation for self-supervised learning on graphs》

本文的思路是好的圖增廣應儘量使圖譜（特徵值）的變化量更大。因此本文先通過一個預計算（pre-computing）的步驟來先獲得好的增廣，然後再在此基礎上進行圖對比（自監督）學習。預計算的過程即求解下列優化問題：

\[t(\mathbf{A})=\operatorname{argmax}_{\|\mathbf{A}-t(\mathbf{A})\|_1 \leq \epsilon} \mathcal{D}(\operatorname{eig}(\operatorname{Lap}(\mathbf{A})), \operatorname{eig}(\operatorname{Lap}(t(\mathbf{A})))) \]

可以看到，這裡兩個圖結構之間的距離是基於圖譜來進行度量的。作者認為一個有效的拓撲增廣應該更關注那些對圖譜產生大的擾動的敏感邊，然後通過對比學習來消除其影響。基於這一原則，作者設計了相應的譜增廣策略。

定義拓撲增廣\(T(\mathbf{A})\)，其每一項\(A_{ij}\)都為服從伯努利分佈\(\mathcal{B}(\Delta_{ij})\)的隨機變數。所有伯努利分佈的引數構成了一個概率矩陣\(\Delta\in[0, 1]^{n\times n}\)。我們可以取樣邊擾動矩陣\(\mathbf{E}\in\{0, 1\}^{n\times n}\)，這裡\(E_{ij}\sim \mathcal{B}(\Delta_{ij})\)表示是否對節點\(i\)和\(j\)之間的邊進行翻轉，如果\(E_{ij}=1\)則翻轉邊，否則不變。增廣圖則通過下式來取樣得到：

\[t(\mathbf{A})=\mathbf{A}+\mathbf{C} \odot \mathbf{E},\quad \mathbf{C}=\overline{\mathbf{A}}-\mathbf{A}， \]

這裡\(\bar{\mathbf{A}}\)為鄰接矩陣\(\mathbf{A}\)的補矩陣，經由\(\overline{\mathbf{A}}=\mathbf{1}_n \mathbf{1}_n^{\top}-\mathbf{I}_n-\mathbf{A}\)計算，這裡\(\left(\mathbf{1}_n \mathbf{1}_n^{\top}-\mathbf{I}_n\right.)\)表示無自環的全連線圖。因此，\(\mathbf{C}=\overline{\mathbf{A}}-\mathbf{A} \in\{-1, 1\}^{n\times n}\)表示對每個節點對的邊新增或刪除操作。如果\(C_{ij}=1\)，則在節點\(i\)和\(j\)之間新增邊，如果\(C_{ij}=-1\)則移除邊。採用Hadamard積\(\mathbf{C}\odot \mathbf{E}\)來最終確定對圖有效的邊擾動。

由於\(\mathbf{E}\)是服從伯努利分佈的隨機變數所組成的矩陣，則所取樣的增廣圖的期望為\(\mathbb{E}[t(\mathbf{A})]=\mathbf{A}+\mathbf{C} \odot \mathbf{\Delta}\)。因此，\(\Delta\)的設計決定了拓撲增廣的模式。以均勻隨機地移除邊為例，當\(C_{ij}=-1\)時\(\Delta_{ij}\)被設定為固定的dropout rate，否則將其設定為0。

最大化譜變化量 不同於直接為\(\Delta\)設定固定值做為均勻隨機擾動，作者提出由圖譜來指導\(\Delta\)的優化。具體來說，這裡需要在期望上來搜尋一個\(\Delta\)以最大化原始圖和從概率矩陣中取樣的增廣圖之間的譜差距。將\(\mathbf{A}\)的未歸一化Laplacian矩陣表示為\(\text{Lap}(\mathbf{A})\)，則其圖譜可以被計算為\(\mathbf{\Lambda} = \text{eig}(\text{Lap}(\mathbf{A}))\)。於是，在單個增廣branch中搜尋所需要的\(\Delta\)可以被形式化為如下問題：

\[\text { Single-way scheme } \operatorname{SPAN}_{\text {single }}: \max _{\Delta \in \mathcal{S}}\|\operatorname{eig}(\operatorname{Lap}(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}))-\operatorname{eig}(\operatorname{Lap}(\mathbf{A}))\|_F^2 \]

這裡\(\mathcal{S}=\left\{\mathbf{s} \mid \mathbf{s} \in[0,1]^{n \times n},\|\mathbf{s}\|_1 \leq \epsilon\right\}\)與\(\epsilon\)控制擾動的強度。上式提供的是一個增廣branch的檢視。擴充套件到兩個branch的增廣框架則為如下形式：

\[\text { Double-way SPAN } \text { double }: \max _{\boldsymbol{\Delta}_1, \boldsymbol{\Delta}_2 \in \mathcal{S}}\left\|\operatorname{eig}\left(\operatorname{Lap}\left(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}_1\right)\right)-\operatorname{eig}\left(\operatorname{Lap}\left(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}_2\right)\right)\right\|_F^2 \]

上式帶來了更好的靈活性，但也使得優化問題變得更難解，因此我們需要對問題進行進一步轉換。基於三角不等式，我們可以去最大化其下界做為替代：\(\max _{\Delta_1, \Delta_2 \in \mathcal{S}}\left\|\operatorname{eig}\left(\operatorname{Lap}\left(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}_1\right)\right)\right\|_2^2-\left\|\operatorname{eig}\left(\operatorname{Lap}\left(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}_2\right)\right)\right\|_2^2\)。這樣，\(\Delta_1\)和\(\Delta_2\)就能夠獨立地朝著相反的方向進行優化：最大化一個branch的圖譜範數，與此同時最小化另一個。而這最終會匯出下列的目標函數：

\[\text { Opposite-direction scheme SPAN } \text { opposite }: \max _{\boldsymbol{\Delta}_1 \in \mathcal{S}} \mathcal{L}_{\mathrm{GS}}\left(\boldsymbol{\Delta}_1\right) \text {, and } \min _{\boldsymbol{\Delta}_2 \in \mathcal{S}} \mathcal{L}_{\mathrm{GS}}\left(\boldsymbol{\Delta}_2\right) \]

這裡\(\mathcal{L}_{\mathrm{GS}}(\boldsymbol{\Delta})=\|\operatorname{eig}(\operatorname{Lap}(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}))\|_F^2\)度量了採用\(\Delta\)的增廣正規化的圖譜範數。對於增廣正規化\(T_1(\mathbf{A})\)，\(\Delta_1\)生成的檢視總體上具有比原始圖更大的譜範數，而對於\(T_2(\mathbf{A})\)，\(\Delta_2\)生成的檢視則具有較小的譜。我們可以將它們理解為為輸入圖設定了譜邊界，以訓練編碼器來捕捉到重要且對該區域內的擾動魯棒的資訊。

優化\(\Delta_1\)和\(\Delta_2\) 上式可以採用投影梯度下降（對\(\Delta_2\)）與上升（對\(\Delta_1\)）來求解（關於投影（次）梯度下降法可參見我的部落格《數值優化：經典一階確定性演演算法及其收斂性分析》）。以\(\Delta_2\)為例，其更新過程如下：

\[\boldsymbol{\Delta}_2^{(t)}=\mathcal{P}_{\mathcal{S}}\left[\boldsymbol{\Delta}_2^{(t-1)}-\eta_t \nabla \mathcal{L}_{\mathrm{GS}}\left(\boldsymbol{\Delta}_2^{(t-1)}\right)\right] \]

這裡\(\eta_t > 0\)為步驟\(t\)的學習率，而\(\mathcal{P}_{\mathcal{S}}(\mathbf{a})=\operatorname{argmin}_{\mathbf{s} \in \mathcal{S}}\|\mathbf{s}-\mathbf{a}\|_2^2\)為在約束集\(\mathcal{S}\)上關於\(\mathbf{a}\)的投影運算元。這裡的梯度\(\nabla \mathcal{L}_{\text{GS}}(\Delta^{(t-1)}_2)\)可以通過鏈式法則計算，其中會用到特徵值對矩陣求導的閉式解：對於一個實對稱矩陣\(\mathbf{L}\)，其第\(k\)個特徵值的導數為\(\partial \lambda_k / \partial \mathbf{L}=\boldsymbol{u}_k \boldsymbol{u}_k^{\top}\)[8]，這裡\(\boldsymbol{u}_k\)為對應的特徵向量。注意導數計算要求特徵值互異，但這對於自同構（automorphism）圖並不滿足[9]。為了避免這種情況，作者向鄰接矩陣中新增了一個小噪聲項，例如\(\mathbf{A}+\mathbf{C} \odot \boldsymbol{\Delta}+\varepsilon \times\left(\mathbf{N}+\mathbf{N}^{\top}\right) / 2\)，這裡\(\mathbf{N}\)中的每一項都從均勻分佈\(\mathcal{U}(0, 1)\)中取樣，且\(\epsilon\)是一個很小的常數。新增這樣的噪聲基本上都會打破圖的自同構，從而實現特徵值的有效梯度計算。

在預計算好概率矩陣\(\Delta_1\)和\(\Delta_2\)之後，我們就可以由\(\Delta_1\)和\(\Delta_2\)來設定增廣模式。對於對比學習的每輪迭代，我們取樣兩個增廣圖\(t_1(\mathbf{A}) \sim T\left(\mathbf{A} \mid \boldsymbol{\Delta}_1\right)\)和\(t_2(\mathbf{A}) \sim T\left(\mathbf{A} \mid \boldsymbol{\Delta}_2\right)\)。增廣圖之後會被輸入一個圖編碼器\(f_{\theta}\)，從而產生兩組節點表徵\(\mathbf{H}^{(1)}, \mathbf{H}^{(2)} \in \mathbb{R}^{n \times d^{\prime}}\)。之後我們應用讀出函數\(g_{\phi}\)來聚合並變換節點表徵以得到圖表徵\(\boldsymbol{z}^{(1)}, \boldsymbol{z}^{(2)} \in \mathbb{R}^{d^{\prime}}\)。最後，給定訓練圖\(\mathcal{G}\)，採用對比目標函數\(\mathcal{L}_{\text{GCL}}\)在最大化區域性節點表徵和全域性圖表徵之間的跨檢視相似度，旨在保留區域性相似性和全域性不變數：

\[\text { GCL-TAGS : } \min _{\theta, \phi} \mathcal{L}_{\mathrm{GCL}}\left(t_1(\mathbf{A}), t_2(\mathbf{A}), \theta, \phi\right)=-\frac{1}{|\mathcal{G}|} \sum_{G \in \mathcal{G}}\left(\frac{1}{n} \sum_{i=1}\left(I\left(\mathbf{H}_i^{(1)}, \boldsymbol{z}^{(2)}\right)+I\left(\mathbf{H}_i^{(2)}, \boldsymbol{z}^{(1)}\right)\right)\right) \\ \begin{aligned} \text{s.t.} \quad & t_i(\mathbf{A}) \sim T\left(\mathbf{A} \mid \boldsymbol{\Delta}_i\right), \quad i \in\{1,2\}, \\ & \boldsymbol{\Delta}_1=\operatorname{argmax}_{\boldsymbol{\Delta} \in \mathcal{S}} \mathcal{L}_{\mathrm{GS}}(\boldsymbol{\Delta}),\quad \boldsymbol{\Delta}_2=\operatorname{argmin}_{\Delta \in \mathcal{S}} \mathcal{L}_{\mathrm{GS}}(\boldsymbol{\Delta}) \end{aligned} \]

這裡\(I(X_1, X_2)\)計算的是變數\(X_1\)和\(X_2\)之間的互資訊，可以採用InfoNCE做為它的下界（參見我的部落格《遷移學習：互資訊的變分上下界》）。具體地，設餘弦相似度為\(\cos(\cdot, \cdot)\)，則互資訊可以估計如下：

\[I\left(\mathbf{H}_i^{(a)}, \boldsymbol{z}^{(b)}\right)=\log \frac{\exp \left(\cos \left(\mathbf{H}_i^{(a)}, \boldsymbol{z}^{(b)}\right)\right)}{\sum_{j=1}^n \exp \left(\cos \left(\widetilde{\mathbf{H}}_j, \boldsymbol{z}^{(b)}\right)\right)} \]

這裡\(a\)和\(b\)為增廣檢視的索引，\(\widetilde{\mathbf{H}}\)為該batch中其它負例的節點表徵。

2.3 AISTATS2023 《Spectral Augmentations for Graph Contrastive Learning》

本文提出了兩種圖資料增廣的策略：譜圖裁剪（spectral graph cropping）和圖頻率分量的重排（graph frequency component reordering）。此外，作者也提出了兩種後處理（post-processing）的增廣質量增強機制。第一種作者稱為增廣濾波（augmentation filtering），基於表徵相似度來選擇候選的增廣；第二種作者稱為本區域性-全域性表徵對齊（local-global embedding alignment），對齊在增廣之間共用的節點表徵。本文方法的整體框架流程如下圖所示：

如上圖所示，最開始的兩個必備步驟是構建自我中心網路（ego-net，即包含節點\(i\)、\(i\)的鄰居節點及\(i\)與鄰居節點之間所有邊的子圖）和隨機遊走以得到節點的embeddings。而隨後的步驟都是按照概率（\(p_{\text{filter}}，p_{\text{crop}}，p_{\text{align}}，p_{\text{mask}}，p_{\text{reorder}}\)）來選擇性出現的，包括增廣過濾，譜裁剪，embeddings對齊，隨機embeddings掩碼，頻率分量重排。注意，這裡的兩個步驟（即掩碼或重排）只能二選一。圖中的\(t_{\text{max}}\)表示在過濾步驟中所允許嘗試的最大次數。

使用特徵向量的圖裁剪 我們知道對於影象而言，沿著\((x, y)\)軸裁剪畫素的影象裁剪增廣是非常高效的。而做為影象裁剪的推廣，作者引入了去除圖節點的圖裁剪增廣，該增廣使用圖Laplacian矩陣\(\mathbf{L}_i\)兩個最小的非零特徵值\(\lambda_2\)，\(\lambda_3\)所對應的特徵向量。設\(\boldsymbol{x}(v)\)表示在第二個特徵向量中賦給節點\(v\)的值（即\(\boldsymbol{u}_2\in \mathbb{R}^N\)的第\(v\)行），相似地\(\boldsymbol{y}(v)\)表示第三個特徵向量中賦給節點\(v\)的值（即\(\boldsymbol{u}_3\in \mathbb{R}^N\)的第\(v\)行），則可定義譜裁剪增廣如下：\(G_i\left[x_{\min }, x_{\max }, y_{\min }, y_{\max }\right]\)（裁剪後的檢視）為節點\(v\in G_i\)的集合，滿足\(x_{min}\leqslant \boldsymbol{x} (v) \leqslant x_{\text{max}}\)與\(y_{\text{min}}\leqslant \boldsymbol{y}(v) \leqslant y_{\text{max}}\)。

基於頻率的位置embedding重排 我們知道影象是由RGB編碼得到的多通道資料，不同通道對應著可見光譜的不同頻率。關於影象已經有了成功的重排增廣，這啟發我們引入一個新的圖增廣，該圖增廣將會重排圖各頻率分量的結構位置embeddings。我們知道結構位置embeddings\(\mathbf{H}_i\)可以由圖Laplacian矩陣的分解得到（其列為對應各頻率分量的特徵向量，其第\(v\)行為節點\(v\)的embedding）[10][11]，於是這裡可以考慮去重排\(\mathbf{H}_i\)的各列。

然而，任意的重排並不能產生一個好的增廣。為了匯出一個位置embedding，歸一化Laplacian矩陣\(\mathbf{L}_i\)並不是用於分解的有效選擇。由特徵分解可以匯出一個著名的隨機遊走embedding方法：

\[\log \left(\sum_{j=1}^r\left(\mathbf{I}-\mathbf{L}_i\right)^r\right) \mathbf{D}_i^{-1}=\log \left(\mathbf{U}_i\left(\sum_{j=1}^r\left(\mathbf{I}-\mathbf{\Lambda}_i\right)^r\right) \mathbf{U}_i^{\mathbf{T}}\right) \mathbf{D}_i^{-1} \]

可見\(\sum_{j=1}^r\left(\mathbf{I}-\mathbf{L}_i\right)^r\)在譜分解中代替了\(\left(\mathbf{I}-\mathbf{L}_i\right)\)。正如鄰接矩陣\(\mathbf{A}_i\)編碼了圖的一階鄰域資訊(邊)，\(\mathbf{A}^2_i\)編碼了二階資訊，\(\mathbf{A}^3_i\)編碼了三階資訊等。使用更大的\(r\)可以整合embeddings中更高階的資訊。最佳的\(\mathbf{H}\)為\(\sum_{j=1}^r(1-\lambda)^j\)中前\(k\)個值所對應的\(\mathbf{U}\)的列（特徵向量）。沒有必要重複特徵值分解來獲得新的embeddings，因為高階embeddings可以通過重排特徵向量（按照\(\sum_{j=1}^r\left(1-\lambda_w\right)^j\)的降序）來得到。

embeddings對齊 作者還提出了一種基於embeddings對齊的增廣質量增強機制，該機制可以產生更好的增廣。該機制是後處理的，也即需要在進行增廣並學得embeddings後再進行調整。給定圖\(G_t\)中的兩個節點\(v\)和\(v^{\prime}\)，並通過圖嵌入方法來產生\(G_t\)的embedding矩陣\(\mathbf{H}_{t}\)。這裡\(\mathbf{H}_t\)中對應節點\(v\)的那一行提供了對應的節點embedding\(\boldsymbol{h}_v\)。考慮兩個檢視\(G^{\prime}_i\)，\(G^{\prime\prime}_i\)和節點\(v_i\)滿足\(v_i \in G^{\prime}_i, v_i \in G^{\prime\prime}_i\)。給定\(G^{\prime}_i, G^{\prime\prime}_i\)的embeddings \(\mathbf{H}^{\prime}_i\), \(\mathbf{H}^{\prime\prime}_i\)，則對齊指的是去尋找一個正交矩陣\(\mathbf{Q}\)滿足\(\mathbf{H}^{\prime\prime}_i \mathbf{Q}\approx \mathbf{H}^{\prime}_i\)。這裡之所以要對齊的原因是每個節點\(v_i\)的結構embeddings（在\(\mathbf{H}^{\prime}_i\)，\(\mathbf{H}^{\prime\prime}_i\)中對應節點\(v_i\)的每一行）是有差異的，我們需要去糾正它。注意，直接對齊是難以優化的（和我們在2.2節中面臨的情況類似），故這裡還需要使用原始的子圖embeddings矩陣\(\mathbf{H}_{t, G_i}\)做為橋樑（\(\mathbf{H}_{t, G_i}\)為將所有\(v_j\in G_i\)對應的行\(j\)收集得到的子矩陣）。最後，問題就可以形式化為：找到正交矩陣\(\mathbf{Q}\)，\(\mathbf{Q}^{**}\)，使得

\[\mathbf{Q}^*=\min_\mathbf{Q} \|\mathbf{H}_i^{\prime} \mathbf{Q}-\mathbf{H}_{t, G_i}\lVert^2_{F},\quad \mathbf{Q}^{**}=\min_\mathbf{Q} \|\mathbf{H}_i^{\prime\prime} \mathbf{Q}-\mathbf{H}_{t, G_i}\lVert^2_{F} \]

該問題有閉式解\(\mathbf{Q}^* = \mathbf{U}\mathbf{V}^{\text{T}}\)，這裡\(\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\text{T}}\)為\((\mathbf{H}^{\prime}_i)^{\text{T} }\mathbf{H}_{t, G_i}\)的奇異值分解（\(\mathbf{Q}^{**}\)同理，這裡和我們在部落格《知識圖譜實體對齊：無監督和自監督的方法》中所求解的問題類似）。這裡所得到的解滿足\(\mathbf{H}_i^{\prime} \mathbf{Q}^* \approx \mathbf{H}_{t, G_i}\)與\(\mathbf{H}_i^{\prime \prime} \mathbf{Q}^{* *} \approx \mathbf{H}_{t, G_i}\)。於是，我們可以通過使用\(\mathbf{H}_i^{\prime} \mathbf{Q}^*, \mathbf{H}_i^{\prime\prime} \mathbf{Q}^{**}\)來代替\(\mathbf{H}_i^{\prime}, \mathbf{H}^{\prime\prime}_i\)，以減少錯位所導致的負面差距，最終獲得更好的圖增廣。作者將此稱為對齊。

增廣過濾 文章還提出了一個選擇候選增廣的策略，稱為增廣濾波。同embeddings對齊一樣，這個也是個後處理步驟。考慮\(G^{\prime}_i，G^{\prime\prime}_i\)這兩個檢視，這兩個檢視由節點\(a_i\)（節點\(a_i\)在\(G_t\)中的自我中心網路為\(G_i\)）進行隨機遊走得到。設\(\boldsymbol{z}_{G^{\prime}_i}=\sum_{v_j\in G^{\prime}_i} \boldsymbol{h}_{j}\)（\(\boldsymbol{z}_{G^{\prime\prime}_i}\)同理），則我們能夠通過\(\langle \boldsymbol{z}_{G_i^{\prime}}, \boldsymbol{z}_{G_i^{\prime \prime}} \rangle\)的相似度來度量檢視的相似度。作者規定只有當增廣檢視相似時才接受該對檢視，以避免潛在的噪聲增廣：

\[\frac{\left\langle \boldsymbol{z}_{G^{\prime}}, \boldsymbol{z}_{G^{\prime \prime}}\right\rangle}{\left\|\boldsymbol{z}_{G^{\prime}}\right\|\left\|\boldsymbol{z}_{G^{\prime \prime}}\right\|}>1-c, \quad \text{for some constant } 0\leqslant c \leqslant 1 \]

正如上面的框架圖所示，作者將這一過濾步驟和隨機遊走結合，以接受候選節點。這裡值得注意的是應用相似性過濾在經驗上表現得比其它的選擇要好，比如多樣性過濾。

參考

  • [1] Veličković P, Fedus W, Hamilton W L, et al. Deep graph infomax[J]. arXiv preprint arXiv:1809.10341, 2018.
  • [2] Hassani K, Khasahmadi A H. Contrastive multi-view representation learning on graphs[C]//International conference on machine learning. PMLR, 2020: 4116-4126.
  • [3] Zhang H, Wu Q, Yan J, et al. From canonical correlation analysis to self-supervised graph neural networks[J]. Advances in Neural Information Processing Systems, 2021, 34: 76-89.
  • [4] Tian Y, Sun C, Poole B, et al. What makes for good views for contrastive learning?[J]. Advances in neural information processing systems, 2020, 33: 6827-6839.
  • [5] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.
  • [6] 南京大學人工智慧學院-數位訊號處理：07 調變、解調和濾波
  • [7] Stewart G W, Sun J. Matrix perturbation theory[J]. (No Title), 1990.
  • [8] Rogers L C. Derivatives of eigenvalues and eigenvectors[J]. AIAA journal, 1970, 8(5): 943-944.
  • [9] Godsil C D. On the full automorphism group of a graph[J]. Combinatorica, 1981, 1: 243-256.
  • [10] Chung F R K. Spectral graph theory[M]. American Mathematical Soc., 1997.
  • [11] Hamilton W L. Graph representation learning[M]. Morgan & Claypool Publishers, 2020.