G5.1 鄰居很多的路口，訊息要怎麼算？

本篇重用1 篇

G5.0沿道路傳訊息，換路口編號後還是同一條規則嗎？

十個鄰居和兩個鄰居，可以直接比總和嗎？

上一篇用重編號的要求限制 message passing，但仍留下 aggregation 的選擇。若每個鄰居傳相同數值，鄰居多的路口會得到更大的總和；有時我們想先比較「附近通常是什麼狀態」，不希望一開始只被數量主導。

最直接的操作是除以鄰居數。這裡先建立 degree 的角色，再看 GCN 常用的對稱 normalization，而不只背一條矩陣公式。

令 $A$ 是 undirected adjacency。先補上每個 node 到自己的 edge：

\widetilde A=A+I.

Self-loop 讓自己的 feature 也進入這一輪 aggregation。定義

\widetilde d_i=\sum_j\widetilde A_{ij},\qquad \widetilde D=\operatorname{diag}(\widetilde d_1,\ldots,\widetilde d_n).

$\widetilde d_i$ 就是包含自己的鄰居數；有 self-loop，所以至少是 $1$ ，不必對零開 inverse。

同時考慮接收者與送出者的 degree

單純 row mean 會使用 $\widetilde D^{-1}\widetilde A$ 。GCN 常用的是

S=\widetilde D^{-1/2}\widetilde A\widetilde D^{-1/2}, \qquad S_{ij}=\frac{\widetilde A_{ij}}{\sqrt{\widetilde d_i\widetilde d_j}}.

它用兩個端點的 degree 調整 edge 權重。高 degree 的 node 不只作為接收者時被縮放，送出訊息時也被縮放；undirected graph 下， $S$ 保持對稱。

Row mean 與這種對稱 normalization 都是可選的設計，不是重編號要求唯一指定的公式。選完後，還要確認 degree 與 edge 權重能跟同一個 node 一起重編。

因此一般 $\sum_jS_{ij}$ 不必等於 $1$ ，不能把它完全當成普通 arithmetic mean。它是 degree-normalized 的加權 aggregation。

用共享 feature 矩陣 $W$ 與逐點 scalar activation $\sigma$ ，一層寫成

H^+=\sigma(SHW).

第 $i$ 列讀作 $\sigma(\sum_j S_{ij}h_jW)$ 。Kipf 與 Welling [1] 的 Graph Convolutional Network（GCN） 使用這個常見形式；原論文從 graph filtering 匯出它，我們這裡先從鄰居運算看懂每一項。

Degree 表也要一起換位置

重編 input， $\widetilde A'=P\widetilde A P^\top$ 。每個 node 的 degree 沒有改變，只是換 row，所以

\widetilde D'=P\widetilde D P^\top.

對角矩陣的平方根 inverse 也只是相同數字重排。因此

S'=PSP^\top.

再用 $H'=PH$ ：

\begin{aligned} H^{\prime+} &=\sigma((PSP^\top)(PH)W)\\ &=\sigma(PSHW)\\ &=P\sigma(SHW)=PH^+. \end{aligned}

第一步跟著 graph 重編，第二步用 $P^\top P=I$ ，第三步因 $\sigma$ 在每個 row 使用同樣運算。到這裡才完成 equivariance 的檢查。

Normalization 解決的是量級，不是所有辨識問題

若每個 node 有相同 feature，且 graph 中每個 node 的 degree 相同， $S$ 的各 row 加權和為 $1$ 。一輪後各 node 仍相同；多輪也可能仍無法看出某些拓樸差別。

所以 normalization 幫助控制不同 degree 的訊息量級，不等於更大的表達能力。若 target 需要直接辨認鄰居數量，mean-like aggregation 可能先把線索洗掉。

我們現在能運算、能證明編號一致，接下來要更直接地問：哪些不同鄰居集合會在 aggregation 後變成相同答案？

補充圖上的 convolution 不等於規則格點上的滑動 kernel

GCN 在不規則鄰居上共享 feature transform，沒有每個 node 都一致的左、右、上、下位置。若要理解它與 Laplacian、spectral filtering 的關係，需要另外建立 graph frequency；這留在擴充單元，不把兩種 convolution 直接當成同一個公式。

GCN 先加 self-loop，再用兩端 degree 正規化 edge，最後共同變換 features；重編時 S 和 H 一起換。

課堂提問

S= D⁻¹ᐟ² A D⁻¹ᐟ² 的每列都一定加總為一嗎？

先想一想，再展開看整理後的答案

不一定。只有 row normalization D⁻¹A 才直接有這個性質。對稱 normalization 同時使用兩端 degree；regular graph 是一個 row sum 恰好為一的特殊情況。

動手看一次

選擇 GCN-style normalization，拖動訊息輪數並重編 nodes。這裡直接計算 degree-normalized aggregation，讓我們檢查重編一致性。