G5.2 取平均之後,還看得出鄰居有幾個嗎?
本篇重用1 篇
平均車流一樣,路口就一樣嗎?
兩個路口的鄰居車流分別是 與 。它們的平均都是 ,但一個很不均勻,另一個很平均。
又如 與 ,mean 和 max 都相同,鄰居數卻不同。如果 aggregation 已經把它們混在一起,後面的模型還能恢復差別嗎?
不能。相同的 aggregated input 送進同一個 update 函數,必然得到同一個輸出。這個瓶頸發生在學習前的表示,不是隻要多訓練幾次就能補回。
Sum 是否就永遠不會碰撞?
直接加原始數值也會碰撞: 與 的 sum 都是 。因此我們需要的不是「任何 sum 都好」,而是先把鄰居編碼成適合的 features,再加總。
若 feature 只有有限個類別,可以用 one-hot 向量表示每種顏色。加總後的每個分量就等於那種顏色出現的次數。例如紅、藍鄰居會得到
這個 sum 能完整保留該有限類別 multiset 的 multiplicity。連續 feature 的情況則更細緻,不能由 one-hot 例子直接推到固定小維度必然無碰撞。
自己與鄰居,要能分開
光有鄰居摘要,也要保留目前 node 的角色。Xu、Hu、Leskovec 與 Jegelka [1] 的 Graph Isomorphism Network(GIN) 使用
是 layer index, 是固定或可訓練 scalar;它讓自己的項與一般鄰居項有不同係數。不要把它和 Gaussian noise 或本課 G1 的 defect 混淆。
如果 ,自己與所有鄰居在 sum 裡待遇一樣,某些不同的「自己加鄰居」組合可能碰在一起。選擇合適係數與特徵函數,有助於保留自己是誰與鄰居 multiset 的差別。
MLP 再把這個摘要轉成新的 feature。Sum 與共享 MLP 仍符合 G5.0 的重編號 proof,所以加入辨識能力並沒有犧牲 permutation equivariance。
Injective 的保證在說什麼?
Injective(單射) 表示不同 input 不會得到相同 output。在這裡,如果不同鄰居 multiset 都能得到不同摘要,下一輪就有機會繼續區分它們。
GIN 的理論在指定的 feature domain、multiset 大小條件,以及足以實現所需 injective 函數的理想設定下,能匹配標準一階 Weisfeiler–Lehman test 的辨識能力。這不是說任意初始化、任意寬度的 MLP 都自動 injective,也不是說它能判斷所有 graph 是否相同。
補充有限類別的計數例子與連續特徵的理論,不要混用
One-hot sum 在有限 alphabet 上直接保留計數。真實模型的 hidden features 是連續向量,有限 embedding、activation 與訓練品質都影響碰撞。正文中的反例用來檢查機制;若聲稱具體網路有完整 injectivity,還要驗證其 domain 與函數條件。
如果每個鄰居從一開始就完全相同呢?
更好的 aggregation 可以減少資訊損失,但如果兩張 graph 每一輪提供給各 node 的 input 都相同,仍沒有內容讓更新分開它們。
下一篇會用一個六邊形與兩個三角形逐輪算。這能把「模型架構的上限」與「這一次沒有訓練好」分得更清楚。
課堂提問
只把 mean 改成 raw sum,是否就保證所有不同的連續鄰居 features 都能分開?
先想一想,再展開看整理後的答案
不保證。3 與 2 的 sum 仍相同。要談 injective aggregation,還要指定 feature encoding、domain 與 multiset 大小條件。
動手看一次
比較 sum 與 mean,再切換六邊形與兩個三角形。Sum 可以保留鄰居數量,但這兩張圖的 degree 相同,仍需要下一篇的表達能力分析。