GNN (09) 圖卷積的兩條路徑

⏪ 上篇傳送門

[embed]GNN (08) Graph Laplacian 特徵分解 ⏪ 上篇傳送門medium.com

在前兩篇文章中，我們成功從梯度與散度推導出 Graph Laplacian L = KᵀK，再透過特徵分解 L = UΛUᵀ 建立圖上的頻域座標系，應證了圖上的「局部性」等價於頻域中「平滑性」的對應關係。

現在，若給定一張圖 G = (V, E) 與節點上的特徵 f，我們該如何設計一個可學習的卷積操作，使它能夠捕捉圖的局部結構、並在訓練中自動調整參數呢？

Bruna et al. (2014) 於《Spectral Networks and Deep Locally Connected Networks on Graphs》一文中最早系統性地回答這個問題，他提出了兩條路徑，分別是 Spatial Construction 與 Spectral Construction。接下來，就讓我們逐一探索這兩者演算法的設計思路吧！

Spatial Construction

既然卷積的核心是對局部鄰域做加權求和，那麼直接在圖的空間域中定義鄰域，再對鄰域內的節點特徵做加權聚合，就是最自然的圖卷積。

定義 Reception Field

對於圖 G = (Ω, W)，其中 Ω 是節點集合、W 是邊的權重矩陣，Spatial Construction 透過設定一個閾值 δ > 0，將節點 j 的鄰域定義為：

[embed]

這個定義只保留權重超過閾值的邊，讓每個節點只關注與它「夠近」的鄰居。若對照 CNN 的 Locality 歸納偏置，即是假設有意義的資訊存在於局部區域，遠處的節點對當前節點的影響可以忽略。

階層式多尺度聚和

僅有局部聚合還不夠。CNN 之所以能夠捕捉從細節到全域的多尺度特徵，正是因為它透過池化層逐步收縮空間，讓深層 kernel 的感知域越來越大。Spatial Construction 在圖上複製了這個機制，透過階層式聚合（hierarchical agglomerative clustering）建立多尺度的鄰域結構。

具體做法是：將節點集合 Ω₀ = Ω 逐層合併，第 k 層將前一層的節點分組為 dₖ 個簇（cluster），形成新的節點集合 Ωₖ。每個簇對應原始圖中的一組節點，類比於 CNN 中 pooling 之後的一個「超像素」。整個過程類似於把房子依地址合併成街區、再把街區合併成城市、再把城市合併成省份，每一層的「節點」代表的是上一層節點的聚合。

第 k 層的計算公式為：

[embed]

• x_{k,i}：第 k 層第 i 個特徵圖（feature map）的訊號，定義在節點集合 Ωₖ 上
• F_{k,i,j}：第 k 層從第 i 個輸入特徵圖到第 j 個輸出特徵圖的稀疏濾波矩陣，非零位置由鄰域 Nₖ 決定
• h：非線性激活函數
• Lₖ：第 k 層的 pooling 算子，將同一個簇內的特徵聚合為單一值
• fₖ：第 k 層的特徵圖數量（對應 CNN 的 channel 數）

每一層的計算將 fₖ₋₁ 維的訊號（定義在 Ωₖ₋₁ 上）轉換為 fₖ 維的訊號（定義在 Ωₖ 上），同時犧牲空間解析度、換取更豐富的特徵表達。這與 CNN 的卷積-池化機制在結構上完全一致。

Pros & Cons

Spatial Construction 的優點是對圖的假設極少，它 不要求圖有特定的全域結構，只要能定義局部鄰域即可。對於低維、有良好局部結構的圖，可以有效捕捉局部幾何特徵（例如地理網絡、分子圖）。

然而，這類早期的 Spatial Construction 方法存在一個關鍵限制。在 CNN 中，同一個 kernel 可以在影像的各個位置重複使用，這種權重共享機制大幅提升了模型的參數效率與泛化能力。但 在圖結構中，由於每個節點的鄰域大小不一，且鄰域內節點之間不存在自然的排列順序，若直接為每個鄰域學習一組獨立的濾波參數，將導致模型的參數量隨節點數增加，且難以在不同圖結構之間共享所學到的模式。

這個問題在早期並沒有明確的解法，直到後續研究引入了以 鄰域聚合 為核心的設計思路，透過定義 對節點排列不敏感的 aggregation 函數，使得所有節點可以共享同一組參數。這樣的轉變不僅解決了權重共享的問題，也奠定了現代 Graph Neural Networks 的基本架構。

Spectral Construction

既然空間域中無法定義統一的鄰域順序，不妨繞道頻域，在 Graph Laplacian 的特徵值空間中定義卷積，再將結果映射回空間域。

頻域卷積的數學基礎

在前篇文章中，我們建立了圖傅立葉變換：對圖上的訊號 f，其頻域表示為 f̂ = Uᵀf，其中 U 是 Graph Laplacian 的特徵向量矩陣。逆變換為 f = Uf̂。

在連續空間，根據卷積定理（convolution theorem），空間域的卷積等價於頻域的逐點乘積。將這個定理搬到圖上，對訊號 x 與濾波器 h 的圖卷積定義為：

[embed]

其中 ĥ ∈ ℝⁿ 是濾波器在頻域的表示（即濾波器對每個特徵值的響應），⊙ 是逐元素乘積。整個操作的流程是：將訊號 x 透過 Uᵀ 變換到頻域，在頻域對每個頻率分量乘以對應的濾波器係數 ĥᵢ，再透過 U 變換回空間域。

在這個框架下，可學習的參數是濾波器的頻域表示 ĥ。若將 diag(ĥ) 記為對角矩陣 F，則每一層的計算為：

[embed]

其中 F_{k,i,j} 是對角矩陣，對角線元素是可學習的頻域濾波係數。

施加平滑性約束以維持局部性

基於上述結果，若直接針對每個特徵值學習獨立的濾波係數，則每個濾波器需要 n 個參數（根據節點數）。對於有數萬個節點的圖，這個參數量完全無法承受。

另一個問題在於，目前我們尚未對濾波器施加任何限制。如果濾波器在頻域中是任意的，意即每個頻率所對應的參數彼此獨立，則濾波器在頻譜上的分布可能呈現高度不規則的形態。在這種情況下，我們無法確保其在空間域中的對應操作具有局部性，甚至可能導致每個節點的輸出都受到整張圖的影響，從而演變為一種全域性的混合，完全失去原本希望保留的局部結構。

因此，Spectral Construction 需要對頻域濾波係數施加平滑性約束。Bruna et al. (2014) 提出的做法是：只學習 q 個稀疏的「錨點係數」α₁, α₂, …, αq（其中 q ≪ n），再用三次樣條插值（cubic spline interpolation）在特徵值排列的一維座標系上插值，得到所有 n 個特徵值對應的濾波係數：

[embed]

其中 K 是固定的 n × q 三次樣條核矩陣，α_{k,i,j} ∈ ℝq 是可學習的 q 個錨點係數。當 q 固定、與 n 無關時，每個濾波器的參數量降至 O(1)，不再受圖的節點數量影響。

這個平滑性約束不只是工程上壓縮參數的技巧，更是有嚴格的數學意義。它強制濾波器在相鄰特徵值上的響應相近，從而保證濾波器在空間域是局部化的。這正是前幾篇文章所證明「空間域局部性 ↔ 頻域平滑性」等價關係的直接應用。

Pros & Cons

Spectral Construction 的最大優點，是它以某種形式實現了權重共享：每個濾波器的頻域係數是全域定義的，對圖上所有位置都使用相同的頻率響應函數，因此不同位置之間確實共享了參數。這是 Spatial Construction 無法做到的。

然而，Spectral Construction 依然存在三個重要限制，後來的 GNN 研究都是為了克服這些限制而發展出來的：

1. 計算成本高昂。每一層都需要計算 UᵀxU，即兩次與特徵向量矩陣的矩陣乘法，計算複雜度為 O(n²)，對大型圖完全不可行。
2. 圖結構固定。特徵向量矩陣 U 是針對特定圖的 Laplacian 計算而來的，無法遷移到不同拓樸結構的圖。這意味著同一個模型無法在不同的圖上使用，違背了深度學習模型應具備的泛化能力。
3. 特徵向量的排列無意義。如第二篇文章提到的，圖的 Laplacian 特徵向量並不像標準傅立葉基底那樣有全域統一的幾何意義 — — 相似特徵值的特徵向量，描述的不一定是相似的空間模式。將特徵值在一維座標系上排列並施加平滑性約束，是一個工程上的近似，缺乏嚴格的數學保證。

Spatial V.S. Spatial Construction

若進一步將 Spatial 與 Spectral Construction 並排比較，可以更加清楚兩條路徑的設計權衡：

鄰域定義方式

Spatial Construction 在空間域直接定義鄰域，透過 閾值 δ 篩選有效邊，鄰域的幾何意義較為直觀；Spectral Construction 則在頻域定義濾波器，透過平滑性約束確保空間域的局部操作，但這個對應關係是間接的，不如空間域直觀。

權重共享

Spatial Construction 無法在不同節點間共享權重，因為每個節點的鄰域大小與排列不同；Spectral Construction 的頻域濾波係數是全域共享的，在某種意義上實現了跨位置的參數共享，但這個共享依賴於特定圖的 Laplacian 特徵向量，無法遷移到不同的圖。

計算複雜度

Spatial Construction 的計算複雜度為 O(|E|)，與邊的數量線性相關，對稀疏圖友善；Spectral Construction 需要計算完整的特徵向量矩陣 U（O(n²) 空間）與兩次矩陣乘法（O(n²) 計算），對大型圖完全不可行。

圖的遷移性

Spatial Construction 只依賴圖的局部連接結構，可以在不同大小、不同拓樸的圖上使用；Spectral Construction 的特徵向量是針對特定圖計算的，無法遷移，意即同一個模型面對不同的圖，需要重新計算 Laplacian 的特徵分解。

架構驗證

事實上，在本篇論文的年代尚未針對圖結構資料有太多著墨，因此研究者在模型測試階段所採用的資料並非真正的圖結構資料，而是基於 MNIST 二維影像的模擬資料集。

研究者在測試階段的目標有二：

1. 當規則網格失去規則性時，GNN 是否依然有效？
2. 當資料所在的空間本身就是彎曲的非歐空間時，GNN 是否有效？

為此，研究者分別設計了對應兩階段資料後處理方法，分別是：

1. subsampled MNIST
2. subsampled spherical MNIST（將影像投影至球面）

在第一階段中，所謂 subsample 是從完整的 784 個像素隨機挖掉大部分，只保留 400 個不規則分布的點。每一張圖片都實施固定的採樣流程，換句話說每個樣本的圖結構都相同，僅有像素強度差異（對應節點特徵值），因此本次測試任務屬於單圖（single graph）問題。

在第二階段中，研究者進一步將 subsampled MNIST 投影到三維球面上的 4096 個隨機採樣點，同時加入隨機旋轉，因此該階段的干擾變數共有彎曲的流形結構，以及旋轉不變性等兩項挑戰。

Subsampled MNIST

Subsampled Spherical MNIST without Smoothness Restriction

研究者為了驗證在前述反覆提及的「空間域局部性 ↔ 頻域平滑性」對應關係，將學習好的濾波器投影回 400 個採樣像素位置以方便觀察。每個像素被賦予一個數值，以顏色深淺表示，暖色代表正值，冷色代表負值，顏色越深代表數值絕對值越大。

透過上面兩組樣本的比較，我們可以發現在 Subsampled MNIST 基於空間域濾波器的組別其顏色分布非常集中。只有少數幾個鄰近的像素點有明顯的正值或負值，其餘大部分位置接近零（顏色淡），這代表濾波器只對某個局部區域的訊號響應，對其他位置不感興趣，這就是空間局部性的直接呈現。

反觀在 Subsampled Spherical MNIST 基於無平滑性約束的頻域濾波器組別，顏色分散在整個畫面，幾乎每個像素都有明顯的正值或負值，沒有集中的區域。這代表這個濾波器對影像上所有位置的訊號都有響應，是一個全域的濾波器，故局部資訊可能無法被有效利用。

下面一組樣本展示了相同樣本下施加平滑性約束後的結果，可以發現有顏色的區域重新變得集中，雖然不如空間方法那樣精確，但明顯地出現了幾個局部的色塊，其餘位置顏色淡化。這代表平滑性約束成功地讓頻譜濾波器在空間域恢復了局部性。

Subsampled Spherical MNIST with Smoothness Restriction

本篇文章介紹了 Bruna et al. (2014) 提出的兩種圖卷積構造，Spatial Construction 直接在空間域定義多尺度的局部鄰域，透過階層式聚合實現類 CNN 的多尺度特徵提取。它對圖的假設少、計算友善，但無法在不同節點間共享權重，參數量隨圖的大小線性增長。

Spectral Construction 在 Graph Laplacian 的頻域中定義卷積，以頻域平滑性約束實現空間局部性，以稀疏錨點係數加插值將每個濾波器的參數量降至 O(1)。它實現了某種形式的全域參數共享，但計算代價高昂、無法遷移到不同的圖。

兩種構造共同確立了整個 GNN 領域的研究核心：空間域方法計算高效、直觀，但難以定義統一的參數共享；頻域方法數學嚴謹、有卷積定理的保障，但計算昂貴、依賴特定圖的結構。後續的模型迭代都在嘗試以不同方法化解這些問題。

⏩ 下篇傳送門

[embed]GNN (10) ChebNet：在頻域定義鄰域 在上一篇文章中，儘管 Bruna et al. (2014) 的 Spectral Construction 在數學上嚴謹地定義了圖上的卷積，但其每一層計算都需要與特徵向量矩陣 U 做兩次矩陣乘法 (前向與反向的圖傅立葉變換），複雜度為…medium.com

Reference

1. 謝秉翰（2026）。圖神經網路概論［課程］。國立臺灣大學。
2. Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2014). Spectral networks and deep locally connected networks on graphs. ICLR.
3. Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. ICLR.
4. Anthropic. (2025). Claude Sonnet 4.6 [Large language model]. https://claude.ai