G5.3 每個路口看到的都一樣，模型分得出兩張圖嗎？

本篇重用1 篇

所有路口都說同一句話，怎麼知道道路繞成哪個形狀？

前面增加了 aggregation 的資訊量，但還有一個問題：模型每次只問附近，兩張 graph 的每個路口如果都收到相同訊息，會不會永遠分不開？

考慮六個 nodes。第一張連成一個六邊形 $C_6$ ，第二張連成兩個互不相連的三角形。第一張 connected，第二張不是；它們當然不是相同 graph。

但每個 node 都有兩個鄰居。先讓所有初始 features 相同， $h_i^0=c_0$ ，沒有額外 node ID、座標或 edge 差異。

任意 node 都看到自己的 $c_0$ ，和兩個 features 為 $c_0$ 的鄰居。對共享 message passing，每條 edge 的 message 都是

m_{ij}^0=\phi(c_0,c_0)=m_0.

Sum aggregation 是 $2m_0$ ；mean 是 $m_0$ ；max 也是相同向量。因此任意共享 update 都得到同一個 $c_1$ 。

兩張 graph 的所有 nodes 都沒有被分開。這不是某組參數剛好不好，而是送進函數的內容完全相同。

假設第 $\ell$ 輪所有 nodes 都是 $c_\ell$ 。每個 node 仍收到兩份相同訊息，所以第 $\ell+1$ 輪也是同一個 $c_{\ell+1}$ 。

這是 induction：初始相同，每輪相同，所以任意深度都相同。兩張 graph 又同樣有六個 nodes，sum readout 都是 $6c_\ell$ ，mean、max 也相同。

因此標準這類 MPNN 無法用這個 input 區分「一個六邊形」和「兩個三角形」。更多 layer 擴大了理論 receptive field，卻沒有製造可區分的內容。

Weisfeiler–Lehman test 的一階版本（1-WL） 用顏色表示目前可以辨認的 node type。每輪把「自己的顏色」與「鄰居顏色的 multiset」組合，為不同組合分配新顏色：

c_i^{\ell+1} =\operatorname{hash}\left(c_i^\ell,\ \{\!\{c_j^\ell:j\in\mathcal N(i)\}\!\}\right).

這裡 hash 是理想的唯一編碼：不同組合給不同顏色，不是實作中可能碰撞的短 hash。Double braces 表示保留重複次數的 multiset。

對兩張例子，每個 node 每輪都得到相同組合，所以 1-WL 也分不開。Xu 等人 [1] 將一般 neighborhood aggregation 的辨識能力與 1-WL 連結；GIN 的理想 injective updates 可以達到它，但沒有超過它的全部限制。

可以加入更豐富的結構資訊、幾何座標，或使用更高階、非標準的 graph architecture。但每一個選擇都要重新問：資訊是否真的來自任務？在重編號下如何變？

隨意加入唯一 row ID 很容易打破例子的相同輸入，卻也把本來不該影響答案的編號放進模型。Structural encoding 則應該依 graph 內容一致地生成與變換，不能只是換個名稱的 row ID。

Permutation equivariance 只排除不合理的編號依賴，沒有保證足以辨認所有內容差異。 下一篇會把這個不可辨識例子寫成測試，讓我們能指出失敗來自架構，還是訓練。

補充有了額外 features，這個反例的條件可能不再成立

若兩張 graph 的初始 node features 不同，或 edge attributes 明確提供不同資訊，induction 的第一步就可能失敗。不能只看到圖形相似，就把所有帶豐富輸入的模型也納入同一個不可能結論。

課堂提問

把這個例子的 GIN 加到一百層，就一定可以看出 connectedness 嗎？

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

在上述相同 features、共享局部更新與對稱 readout 下不行。每輪所有 nodes 都得到同一份輸入，induction 不因層數增加而失效。

在六邊形與兩個三角形之間切換，再增加訊息輪數。每個 node 都從相同 feature 出發、收到兩份相同訊息，因此 readout gap 始終為零。