1 導引

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

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

這里\(\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應該能夠捕捉到圖的結構不變量，也即定義為當對輸入圖的結構屬性造成較大變化（如擾動一定數量的邊）時編碼器輸出的不變量，形式化地表示如下：

這里\(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轉移矩陣）為

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

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

這里\(\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}}\)的特征值和特征向量。不失一般性，我們假設

這里我們近似\(\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}}\)重寫為

我們定義\(\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\)是一個有圖增廣的有效對:

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

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

這里\(\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}}\)而言，其上界可表示如下：

最小化對比損失等價于最小化其上界。所以，較大的\(\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}+}\)的優化目標（最大化）：

該優化目標包含了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}-}\)同理）

這里\(\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}_{+}\)的行和與列和：

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

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

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

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

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

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

定義拓撲增廣\(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\)則翻轉邊，否則不變。增廣圖則通過下式來采樣得到：

這里\(\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\)可以被形式化為如下問題：

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

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

這里\(\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\)為例，其更新過程如下：

這里\(\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}}\)在最大化局部節點表征和全局圖表征之間的跨視圖相似度，旨在保留局部相似性和全局不變量：

這里\(I(X_1, X_2)\)計算的是變量\(X_1\)和\(X_2\)之間的互信息，可以采用InfoNCE做為它的下界（參見我的博客《遷移學習：互信息的變分上下界》）。具體地，設余弦相似度為\(\cos(\cdot, \cdot)\)，則互信息可以估計如下：

這里\(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方法：

可見\(\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}^* = \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\)的相似度來度量視圖的相似度。作者規定只有當增廣視圖相似時才接受該對視圖，以避免潛在的噪聲增廣：

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

參考

• [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.