圖神經網絡

圖結構 vs 網格結構

傳統的深度學習（如 CNN 和 RNN）在處理網格結構數據（如圖像、語音、文本）時表現良好，因為這些數據具有固定的空間結構。然而，真實世界中的很多數據并不遵循網格結構，而是以圖的形式存在，例如：

• 社交網絡
• 引文網絡
• 通信網絡
• 多智能體系統
• 分子結構
• 蛋白質相互作用網絡

這些圖結構數據的特點包括：

• 每個節點的鄰居數量不固定
• 鄰居之間沒有隱含的順序
• 卷積核大小不固定
• 權重無法按照固定順序排列

因此，CNN 等傳統架構無法直接應用于圖結構數據中。

圖卷積網絡（GCN）簡介

圖卷積網絡（GCN）旨在從圖數據中提取特征。核心思想是：

• 將節點的鄰居信息進行聚合
• 并通過權重參數進行變換
• 使得圖中的節點能夠學習到更好的表示

圖的表示形式（Preliminaries）

基本圖結構

一個圖通常記為 $G=(V,E)$，其中：

• V = { v i ∣ i = 1 , … , N } V = \{v_i \mid i = 1, \dots, N\} V={vi?∣i=1,…,N} 表示節點集合，共有 $N$ 個節點
• E = { e i j ∣ v i 與? v j 相連 } E = \{e_{ij} \mid v_i \text{ 與 } v_j \text{ 相連} \} E={eij?∣vi??與?vj??相連} 表示邊集合

圖的表示方式

1. 邊列表（Edge List）：所有邊組成的列表，如
   $$(a,b),(a,d),(a,e),(b,c),(b,d),(b,e),(c,d),(d,e)$$
2. 鄰接矩陣（Adjacency Matrix）：一個 $N\times N$ 的矩陣 $A$，其中 $A_{ij}=1$ 表示節點 $v_i$ 與 $v_j$ 有邊連接，否則為 0。
3. 具有自連接的鄰接矩陣（Adjacency matrix with self connections）：在2的基礎上，對角線全為1，自己和自己都為1
4. 帶權鄰接矩陣（Weighted Adjacency Matrix）：矩陣中的每個元素是邊的權重 $w_{ij}$。
5. 度矩陣（Degree Matrix）：一個對角矩陣 $D$，其中 $D_{ii}$ 表示節點 $v_i$ 的度數（連接的邊數）。

圖的基本屬性（Basic Properties）

• 稠密圖（Dense Graph）：邊的數量接近 $O(N^2)$，例如社交網絡中的名人圖譜。

• 稀疏圖（Sparse Graph）：邊的數量接近 $O(N)$，大部分節點只有少量連接。

  

• 有向圖 vs 無向圖：

  • 有向圖中每條邊有方向，鄰接矩陣可能是不對稱的。
  • 無向圖中邊沒有方向，鄰接矩陣是對稱的。

  

• 連通分量（Connected Components）：
  一個連通分量是一個子圖，其中任意兩個節點之間都有路徑相連。

圖神經網絡中的常用表示

• $G=(V,E)$：圖由節點集合 $V$ 和邊集合 $E$ 構成。

• V = { v i ∣ i = 1 , … , N } V = \{v_i \mid i = 1, \dots, N\} V={vi?∣i=1,…,N}：節點集合，包含 $|V|=N$ 個節點。

• E = { e i j ∣ v i 與? v j 有邊相連 } E = \{e_{ij} \mid v_i \text{ 與 } v_j \text{ 有邊相連} \} E={eij?∣vi??與?vj??有邊相連}：邊集合，記錄節點之間的連接關系。

• $X\in {\mathbb{R}}^{N\times d}$：節點屬性矩陣，$d$ 為每個節點的特征維度。

• 鄰接矩陣 $A\in {\mathbb{R}}^{N\times N}$，其中 A i j ∈ { 0 , 1 } A_{ij} \in \{0, 1\} Aij?∈{0,1} 表示邊 $e_{ij}$ 是否存在。

• 單位矩陣 $I_N$：$N\times N$ 的單位矩陣，用于表示節點的自連接（self-connection）。

• 帶自環的鄰接矩陣 $\hat{A}=A+I_N$：在原始鄰接矩陣基礎上加入自環。

• 節點的度數（Degree）：某個節點連接的邊的數量。

• 度矩陣 $D\in {\mathbb{R}}^{N\times N}$：從鄰接矩陣 $A$ 計算得出，是對角矩陣，其對角線元素表示每個節點的度。

• 自環度矩陣 $\hat{D}\in {\mathbb{R}}^{N\times N}$：從帶自環的鄰接矩陣 $\hat{A}$ 計算得到。

CNN 中的卷積 vs GCN 中的卷積

CNN 中的像素更新（標準卷積）

對于一張圖片的像素，使用 $3\times 3$ 卷積核：

$$h_i^{(l+1)}=\sigma (W_1^{(l)}{h}_1^{(l)}+W_2^{(l)}{h}_2^{(l)}+?+W_9^{(l)}{h}_9^{(l)})$$

GCN 中的節點更新（圖卷積）

使用公式：

$$H^{(l+1)}=\sigma ({\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}{H}^{(l)}{W}^{(l)})$$

其中：

• $\tilde{A}$ 是加入自環的鄰接矩陣
• $\tilde{D}$ 是其對應的度矩陣
• $H^{(l)}$ 是第 $l$ 層的節點表示
• $W^{(l)}$ 是可訓練參數矩陣
• $\sigma$ 是非線性激活函數

該形式實現了特征歸一化的圖卷積操作。

圖卷積操作的標準形式（Spatial Approach）

在空間方法（Spatial-based GCN）中，圖卷積的更新規則如下：

$$h_i^{(l+1)}=\sigma \left(h_i^{(l)}{W}_0^{(l)}+\sum _{j\in {\mathcal{N}}_i}\frac{1}{c_{ij}}{h}_j^{(l)}{W}_1^{(l)}\right)$$

其中：

• ${\mathcal{N}}_i$ 表示節點 $i$ 的鄰居集合
• $W_0^{(l)}$ 和 $W_1^{(l)}$ 為權重矩陣
• $c_{ij}$ 是歸一化常數（可設為固定值或可訓練）
• $\sigma$ 是非線性激活函數（如 ReLU）

優點：

• 權重共享，空間結構不變
• 排列的不變性
• 對節點順序不敏感（Permutation invariant）
• 線性復雜度O(E)，適用于大規模稀疏圖

缺點：

• 僅間接支持邊緣特征
• 多層堆疊需要殘差結構以避免過平滑（over-smoothing）
• 需要閘門機制/深度殘余連接(如果nodes太多，一半需要去掉一些信息)

Kipf & Welling 的 GCN 模型（2017）

Kipf & Welling 提出的圖卷積網絡是一種半監督學習方法，其更新公式為：

$$H^{(l+1)}=\sigma \left({\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}{H}^{(l)}{W}^{(l)}\right)$$

其中：

• $\tilde{A}=A+I$：加入自環的鄰接矩陣
• $\tilde{D}$ 是 $\tilde{A}$ 的度矩陣
• $W^{(l)}$ 是第 $l$ 層的權重矩陣
• $\sigma$ 是非線性激活函數

網絡結構如下：

1. 輸入：節點特征矩陣 $X$
2. 第一層圖卷積：$H^{(1)}=\text{ReLU}(\hat{A}X{W}^{(0)})$
3. 第二層輸出：$Z=\text{softmax}(\hat{A}{H}^{(1)}{W}^{(1)})$

該模型被廣泛用于半監督節點分類任務。

圖卷積更新公式的空間方法詳解

圖卷積的一般更新形式如下：

$$h_i^{(l+1)}=\sigma \left(h_i^{(l)}{W}_0+\sum _{j\in {\mathcal{N}}_i}\frac{1}{c_{ij}}{h}_j^{(l)}{W}_1\right)$$

其中：

• ${\mathcal{N}}_i$ 表示節點 $i$ 的鄰居集合；
• $W_0$ 是自身的權重矩陣；
• $W_1$ 是所有鄰居共享的權重矩陣；
• $c_{ij}$ 是歸一化因子（如鄰居數、可學習權重）；
• $\sigma$ 是非線性激活函數（如 ReLU）。

該空間方法強調局部鄰居信息聚合，具有如下性質：

• 權重共享，適應不同圖結構；
• 對鄰居節點的順序不敏感（Permutation Invariant）；
• 時間復雜度為 $O(E)$，適用于大規模圖。
• Applicable both in transductive(access to test set) and inductive(sperate test set)

GCN 計算示例

假設節點為 $a,b,c,d,e$，圖的鄰接矩陣 $A$ 為：

$$A=\left[\begin{array}{ccccc}0& 1& 0& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 0& 1& 0\\ 1& 1& 1& 0& 1\\ 1& 1& 0& 1& 0\end{array}\right]$$

加入自環后得到：

$$\tilde{A}=A+I=\left[\begin{array}{ccccc}1& 1& 0& 1& 1\\ 1& 1& 1& 1& 1\\ 0& 1& 1& 1& 0\\ 1& 1& 1& 1& 1\\ 1& 1& 0& 1& 1\end{array}\right]$$

該過程表示：每個節點與其鄰居（含自身）對應特征值相加，未做歸一化。
$$H^{(l+1)}=\sigma (\tilde{A}{H}^l{W}^l)$$

GCN 的特征歸一化

為避免特征總量隨度數增長，需對 $\tilde{A}$ 進行對稱歸一化：

$$\hat{A}={\tilde{D}}^{?1/2}\tilde{A}{\tilde{D}}^{?1/2}$$

$$H^{(l+1)}=\sigma ({\tilde{D}}^{?1}\tilde{A}{H}^l{W}^l)$$

其中，度矩陣 $\tilde{D}$ 為：
$$\tilde{D}=\left[\begin{array}{ccccc}4& 0& 0& 0& 0\\ 0& 5& 0& 0& 0\\ 0& 0& 3& 0& 0\\ 0& 0& 0& 5& 0\\ 0& 0& 0& 0& 4\end{array}\right]$$

$$D^{?1}\hat{A}=\left[\begin{array}{ccccc}\frac{1}{4}& \frac{1}{4}& 0& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& \frac{1}{5}\\ 0& \frac{1}{3}& \frac{1}{3}& \frac{1}{3}& 0\\ \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& \frac{1}{5}\\ \frac{1}{4}& \frac{1}{4}& 0& \frac{1}{4}& \frac{1}{4}\end{array}\right]$$
這樣更新會有個問題，ab ≠ ba，不是對稱矩陣，所以將D分成2個。

GCN 標準更新公式

標準 GCN 更新層表示如下：

$$H^{(l+1)}=\sigma \left({\tilde{D}}^{?1/2}\tilde{A}{\tilde{D}}^{?1/2}{H}^{(l)}{W}^{(l)}\right)$$

該式通過對鄰接矩陣的對稱歸一化：

• 保持了特征值分布的穩定；
• 實現了特征傳播不隨度數膨脹；
• 簡潔且高效，成為主流 GCN 實現方式。

該矩陣乘法等價于三步：

1. $H^{(l)}$ 通過權重矩陣 $W^{(l)}$ 投影；
2. 使用歸一化矩陣 $\hat{A}$ 聚合鄰居；
3. 應用非線性激活函數 $\sigma$。

GCN 中對稱歸一化公式的逐步推導與解釋

我們從標準的圖卷積操作出發：

$$H^{(l+1)}={\tilde{D}}^{?1/2}\tilde{A}{\tilde{D}}^{?1/2}{H}^{(l)}$$

關注第 $i$ 個節點的輸出 $H_i^{(l+1)}$，即第 $i$ 行的表示：

$$H_i^{(l+1)}={\left({\tilde{D}}^{?1/2}\tilde{A}{\tilde{D}}^{?1/2}{H}^{(l)}\right)}_i$$

將矩陣乘法拆解成向量形式：

1. 首先將左側乘法與右側拆分：

$$={\left({\tilde{D}}^{?1/2}\tilde{A}\right)}_i?{\tilde{D}}^{?1/2}H$$

2. 用求和展開：

$$=\left(\sum _k{\tilde{D}}_{ik}^{?1/2}{\tilde{A}}_{kj}\right){\tilde{D}}^{?1/2}H$$

3. 注意 $\tilde{D}$ 是對角矩陣，僅對角線非零，即 ${\tilde{D}}_{ik}^{?1/2}=0$ 當 $i\ne k$：

$$={\tilde{D}}_{ii}^{?1/2}\sum _j{\tilde{A}}_{ij}{\tilde{D}}_{jj}^{?1/2}{H}_j$$

將所有常數合并成一項，得到最終形式：

$$H_i^{(l+1)}=\sum _j\frac{1}{\sqrt{{\tilde{D}}_{ii}{\tilde{D}}_{jj}}}{\tilde{A}}_{ij}{H}_j$$

每個鄰居 $j$ 對 $H_i^{(l+1)}$ 的影響

該公式表示：

節點 $i$ 的新表示 $H_i^{(l+1)}$ 是其所有鄰居 $j$ 的表示 $H_j$ 的加權平均。

權重部分為：

$$w_{ij}=\frac{1}{\sqrt{{\tilde{D}}_{ii}{\tilde{D}}_{jj}}}$$

• ${\tilde{A}}_{ij}=1$ 表示 $j$ 是 $i$ 的鄰居（包括自環）
• $H_j$ 是鄰居 $j$ 的特征表示
• ${\tilde{D}}_{ii}$ 和 ${\tilde{D}}_{jj}$ 是節點 $i$ 和 $j$ 的度（含自環）

$j$ 如何對 $i$ 有更大的影響？

鄰居 $j$ 對節點 $i$ 的影響取決于 這個分母：

$$\sqrt{{\tilde{D}}_{ii}{\tilde{D}}_{jj}}$$

因此：

• 若 $j$ 的度數 ${\tilde{D}}_{jj}$ 越小，即 $j$ 越“稀疏”或不太活躍，它的特征 $H_j$ 在這個加權和中占比越大；
• 若 $j$ 是一個“中心節點”連接了很多鄰居（度很大），則 ${\tilde{D}}_{jj}$ 大，導致它對 $i$ 的影響反而被 弱化。

示例：

• 若 $i$ 和 $j$ 都只有 2 個連接（含自環），則權重為 $\frac{1}{\sqrt{2?2}}=0.5$
• 若 $j$ 是高階節點，${\tilde{D}}_{jj}=10$，則權重是 $\frac{1}{\sqrt{2?10}}\approx 0.22$
• 說明：低度的鄰居在信息傳播中影響力更大，高度節點被稀釋

GCN 模型結構與任務

Kipf & Welling 的 GCN 被廣泛用于半監督分類任務，模型結構如下：

• 輸入：特征矩陣 $X\in {\mathbb{R}}^{N\times d}$

• 第一層：
  $$H^{(1)}=\text{ReLU}(\hat{A}X{W}^{(0)})$$

• 輸出層：
  $$Z=\text{softmax}(\hat{A}{H}^{(1)}{W}^{(1)})$$

常見任務包括：

• 節點分類（Node Classification）：
  $${\hat{y}}_i=\text{softmax}(z_i)$$

• 邊預測（Link Prediction）：
  $$p(A_{ij})=\sigma (z_i^T{z}_j)$$

• 圖級分類（Graph Classification）：
  使用聚合操作如全局平均池化后接多層感知機（MLP）。
  $${\hat{y}}_i=\text{softmax}(\sum _n{z}_n)$$

GCN 模型僅需少量標注節點即可訓練整圖，是圖神經網絡的基礎模型之一。

譜方法（Spectral Approach）下的圖卷積網絡

譜方法通過圖拉普拉斯矩陣對圖信號進行傅里葉變換，并在頻域上實現卷積操作。該方法理論上完整嚴謹，是最早期圖卷積的基礎。

圖拉普拉斯矩陣的定義

• 非歸一化圖拉普拉斯矩陣：

  $$L=D?A$$

• 歸一化圖拉普拉斯矩陣：

  $$L^{\prime }=I?D^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}$$

其中 $A$ 是鄰接矩陣，$D$ 是度矩陣，$I$ 是單位矩陣。

卷積定理與頻域操作

在經典信號處理中，有如下結論：

在合適條件下，兩個信號卷積的傅里葉（或拉普拉斯）變換等于它們各自傅里葉變換的逐點乘積。

對于圖信號 $f$ 和濾波器 $h$，有：

$$f?h={\mathcal{F}}^{?1}\left[\mathcal{F}(f)?\mathcal{F}(h)\right]$$

一維傅里葉變換的本質

經典傅里葉變換是將信號 $f$ 展開在復指數函數基底 $e^{i\omega x}$ 上。這些復指數正是一維拉普拉斯算子的特征函數，滿足：

$$Lu=\lambda u$$

一維拉普拉斯算子與經典傅里葉變換的關系

經典傅里葉變換定義為：

$$\hat{f}(\xi )=?f,e^{2\pi i\xi t}?={\int }_{\mathbb{R}}f(t)e^{2\pi i\xi t}dt$$

即將信號 $f$ 展開為復指數函數 $e^{2\pi i\xi t}$ 的線性組合。

這些復指數函數 $e^{2\pi i\xi t}$ 是一維拉普拉斯算子 $\Delta$ 的特征函數。

我們來看具體推導：

$$?\Delta \left(e^{2\pi i\xi t}\right)=?\frac{{?}^2}{?t^2}{e}^{2\pi i\xi t}=(2\pi \xi {)}^2{e}^{2\pi i\xi t}$$

說明 $e^{2\pi i\xi t}$ 是 $\Delta$ 的特征函數，特征值為 $(2\pi \xi {)}^2$。

這一結論可抽象表達為：

$$Lu=\lambda u$$

其中：

• $L$ 是拉普拉斯算子（在圖上也記為 $L$）
• $u$ 是特征函數（在傅里葉中為 $e^{2\pi i\xi t}$）
• $\lambda$ 是對應特征值

這為圖譜方法中“頻域展開”提供了數學基礎：傅里葉基底是拉普拉斯算子的本征函數。

圖傅里葉變換與拉普拉斯特征分解

令 $L=U\Lambda U^T$ 為圖拉普拉斯矩陣的特征值分解（$U$ 為特征向量矩陣，$\Lambda$ 為對角特征值矩陣），則有：

• 圖傅里葉變換：

  $$\hat{f}=U^{T}f$$

  $$\hat{h}=U^{T}h$$

• 圖傅里葉逆變換：

  $$f=U\hat{f}$$

圖上的卷積操作

圖信號與濾波器的卷積在頻域中表示為：

$$f?h=U(\hat{f}\odot \hat{h})=U(U^{T}f\odot U^{T}h)$$

其中 $\odot$ 表示逐元素乘積。

第一版譜圖卷積（Spectral Network）

Bruna 等人提出的譜卷積形式為：

$$y=\sigma (U{g}_{\theta }(\Lambda )U^{T}x)$$

其中 $g_{\theta }(\Lambda )$ 是學習到的頻域濾波器：

$$g_{\theta }(\Lambda )=\left[\begin{array}{cccc}{\theta }_0& 0& ?& 0\\ 0& ?& & ?\\ ?& & ?& 0\\ 0& ?& 0& {\theta }_n\end{array}\right]$$

該方法缺點：

• 無空間局部性；
• 參數數量與節點數相同；
• 每次前向傳播需特征分解，開銷大。

第二版譜圖卷積：局部化濾波器

為了緩解參數過多的問題，提出使用多項式表示濾波器：

$$g_{\alpha }(\Lambda )=\sum _{k=0}^K{\alpha }_k{\Lambda }^k$$

對應卷積變為：

$$y=\sigma (U{g}_{\alpha }(\Lambda )U^{T}x)=\sigma \left(\sum _{k=0}^K{\alpha }_k{L}^{k}x\right)$$

優點：

• 不需特征分解；
• 有空間局部性（$k$ 階表示 $k$ 距離內鄰居）；
• 參數數為 $K$，小于 $n$。

第三版譜圖卷積：Chebyshev 多項式展開

用 Chebyshev 多項式對譜濾波器逼近，定義為：

$$T_0(x)=1,T_1(x)=x,T_k(x)=2x{T}_{k?1}(x)?T_{k?2}(x)$$

令：

$$\tilde{\Lambda }=\frac{2\Lambda }{{\lambda }_{\max }}?I$$

則濾波器近似為：

$$g_{\theta }(\tilde{\Lambda })\approx \sum _{k=0}^K{\theta }_k{T}_k(\tilde{\Lambda })$$

因此卷積可寫為：

$$y=\sigma \left(\sum _{k=0}^K{\theta }_k{T}_k(\tilde{L})x\right)$$

其中 $\tilde{L}=\frac{2L}{{\lambda }_{\max }}?I$

該方法是 Defferrard 等人提出，具有良好的數值穩定性與本地性。

GCN 的最終簡化形式（Kipf & Welling）

Kipf 和 Welling 在 2017 年提出了圖卷積網絡（GCN）的簡化譜方法，通過對 Chebyshev 多項式濾波器進行一階近似，得到了一種高效的圖卷積實現。

首先，從 Chebyshev 展開退化為一階近似，即取 $K=1$，并使用如下形式：

$$g_{\theta }?x\approx \theta \left(I+D^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}\right)x$$

為了提升模型表達能力并確保節點信息自保留，加入自環：

$$\tilde{A}=A+I$$

計算新的度矩陣：

$${\tilde{D}}_{ii}=\sum _j{\tilde{A}}_{ij}$$

最終得到了標準的 GCN 卷積層表達形式：

$$H^{(l+1)}=\sigma \left({\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}{H}^{(l)}{W}^{(l)}\right)$$

其中：

• $\tilde{A}$ 是加入自環的鄰接矩陣；
• $\tilde{D}$ 是 $\tilde{A}$ 對應的度矩陣；
• $H^{(l)}$ 是第 $l$ 層節點特征矩陣；
• $W^{(l)}$ 是第 $l$ 層可學習權重；
• $\sigma$ 是非線性激活函數，如 ReLU。

這一形式不再依賴拉普拉斯的特征分解，計算效率高，可在整個圖上批處理所有節點，是現代 GCN 應用中的標準實現。