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

本篇重用1 篇

G4.5實作：Transformer 的排列、位置與 mask

同樣幾個路口，路接法不同，交通也不同

G3 讓集合模型忽略沒有意義的名單順序；G4 又讓每個點依內容與附帶關係選擇參考對象。現在若參考關係來自真實道路，我們就要先把它明確記下來：只有一群地標，還不知道道路連到誰。公館站和台大正門距離很近，不代表每個方向都能直接透過；單行道與道路連線會改變交通。

因此這次要多提供一份資訊：哪些點之間有關係？ 把路口當成 nodes，道路當成 edges，就得到 graph（圖）。點的屬性與連線都會影響答案，但「這個路口存成 node 3 還是 node 8」仍不應有影響。

Adjacency 表記錄的不是座標

設有 $n$ 個路口， $H\in\mathbb R^{n\times d}$ 記錄各路口的 features。用 $A\in\mathbb R^{n\times n}$ 記錄連線：

A_{ij}= \begin{cases} 1,&j\text{ 的訊息可以送到 }i,\\ 0,&\text{否則}. \end{cases}

這叫 adjacency matrix（鄰接矩陣）。本單元大部分例子先用 undirected graph，此時 $A=A^\top$ ；有向圖則要固定 row 與 column 各代表哪個方向。

如果只把 features 換順序，卻沒把 $A$ 一起換，公館站的資訊就可能接到原本屬於另一個路口的道路。重編號必須作用在全部關係上。

為什麼 adjacency 兩邊都要乘 permutation？

設新第 $i$ 個 node 是原第 $\pi(i)$ 個 node。新表的 $A'_{ij}$ 要記錄原來的 $\pi(j)$ 與 $\pi(i)$ 是否相連：

A'_{ij}=A_{\pi(i),\pi(j)}.

Row 換一次，column 也換一次，所以

A'=PAP^\top,\qquad H'=PH.

這是 graph input 的 permutation action。 $P^\top$ 不是另一個獨立重排，它是同一個 $P$ 的 inverse，讓兩個索引對應同一批重新命名。

例如三個路口原本是 $1-2-3$ 。把名字交換後，圖還是同一條三點道路；把 edge $1-2$ 刪掉，則是真的改變 graph。重新表示與重新連線，不能混在一起。

模型應怎麼回應？

若輸出每個路口的壅塞程度 $Y=F(A,H)$ ，要求

F(PAP^\top,PH)=PF(A,H).

這是 node-level equivariance。若輸出整個路網是否壅塞， $f(A,H)$ 則要求

f(PAP^\top,PH)=f(A,H).

這是 graph-level invariance，通常可以在 equivariant node features 後接對稱 readout。

這些式子沒有要求模型忽略連線。相反地，連線是真正的資料內容，編號才是可以忽略的表示差異。如果兩張圖的連線不等價，模型可以給不同答案；只是後面會看到，某些架構未必看得出所有差異。

想知道這裡塞不塞，先問接過來的路口

附近道路的車流可能馬上送到這裡。我們先選一個局部做法：一輪只讀自己與相鄰路口，逐條道路處理送來的資訊，再更新這個路口。 這是 locality 的設計假設；重編號的 symmetry 沒有禁止我們讀取更遠或全局的資訊。

但逐條道路要怎麼處理？假設同一條道路從「node 1 送到 node 2」改存成「node 3 送到 node 2」，車量與道路寬度都沒變，算出的訊息也不該變。這讓我們先對中間的訊息提出要求，而不只要求最後答案碰巧相同。

換了編號，不能換處理同一道路的規則

用 $h_i$ 表示接收者狀態、 $h_j$ 表示送出者狀態， $e_{ij}$ 是道路寬度等屬性。若讓每個存檔編號使用自己的 $\phi_{ij}$ ，同一份資料重編後就可能改用不同函數。

我們要求每份訊息跟 edge 一起重編。代入同一份內容時，就要有

\phi_{ij}(h_{\pi(i)},h_{\pi(j)},e_{\pi(i),\pi(j)}) = \phi_{\pi(i),\pi(j)}(h_{\pi(i)},h_{\pi(j)},e_{\pi(i),\pi(j)}).

對所有合法內容與重編都成立時，同一種 edge 角色就不能因列號換掉函數。因此用一個共享的 $\phi$ ，

m_{ij}=\phi(h_i,h_j,e_{ij}).

共享的是處理方法，不是訊息的數值。不同車量或道路寬度，仍可以算出不同訊息；如果 edge 有真實型別，也能把型別放進 $e_{ij}$ ，依內容區分，而不是依編號區分。

鄰居表換順序，摘要也不能改變

收到多條道路的訊息後，我們需要一份摘要。假設兩個鄰居的訊息是 $1,3$ ，卻規定「表裡第一個加一次，第二個加兩次」，就得到 $7$ ；換個存放順序， $3+2(1)$ 卻變成 $5$ 。

道路沒有改，摘要卻改了。因此，要讓摘要本身也跟著同一個 node 重編，aggregation 必須對鄰居排列 invariant。寫成

m_i=\operatorname{Agg}\!\left(\{m_{ij}:j\in\mathcal N(i)\}\right), \qquad h_i^+=\eta(h_i,m_i).

$\mathcal N(i)$ 是能送到 $i$ 的鄰居；大括號表示不依排列，但同樣訊息來了兩份，仍保留兩份。更新函數 $\eta$ 也在各 nodes 共享，理由相同：路口換編號，不能改用另一套更新。

我們先選最容易計算與檢查的 sum：

m_i=\sum_{j\in\mathcal N(i)}m_{ij}.

Mean、max 或符合重編規則的 attention 也能用，並不是 symmetry 只允許 sum。它們保留的資訊不同：兩條路與十條路若傳相同訊息，mean 可能一樣，sum 卻不同，這件事後面會仔細檢查。

局部逐邊處理、共享 message 與 update、順序無關的 aggregation，到這裡才接成 message passing。Gilmer 等人 [1] 將這些角色統整成 Message Passing Neural Networks（MPNNs）。我們構造的是一種符合要求的 GNN，不是說所有 equivariant graph models 都只能採用它。

換了名字，訊息還會送到同一個人嗎？

令新 node $i$ 對應原 node $\pi(i)$ 。Features 是 $h_i'=h_{\pi(i)}$ ，道路屬性是 $e_{ij}'=e_{\pi(i),\pi(j)}$ ，鄰居則滿足

j\in\mathcal N'(i) \quad\Longleftrightarrow\quad \pi(j)\in\mathcal N(\pi(i)).

因為所有 edges 使用同一個 $\phi$ ，

m_{ij}'=\phi(h_{\pi(i)},h_{\pi(j)},e_{\pi(i),\pi(j)}) =m_{\pi(i),\pi(j)}.

把鄰居加起來，再令 $\ell=\pi(j)$ ：

\begin{aligned} m_i' &=\sum_{j\in\mathcal N'(i)}m_{\pi(i),\pi(j)}\\ &=\sum_{\ell\in\mathcal N(\pi(i))}m_{\pi(i),\ell}\\ &=m_{\pi(i)}. \end{aligned}

最後更新 $h_i^{\prime+}=\eta(h_{\pi(i)},m_{\pi(i)})=h_{\pi(i)}^+$ 。所以整層 equivariant。

這個證明與 $\phi,\eta$ 是否線性無關。關鍵是共享運算、正確搬動 edges、以及不依順序的 aggregation，不是「用了 graph 套件」就自然成立。

一輪只能聽到誰？

假設初始 feature 只描述 node 自己。一輪更新後， $h_i$ 包含自己與一條 edge 內的鄰居；第二輪讀取鄰居的第一輪狀態，就間接收到兩條 edges 以內的訊息。

用 induction 看，第 $\ell$ 輪至多看到 graph distance 不超過 $\ell$ 的部分。這叫 receptive field（可觀察範圍）。它是道路連線的距離，不一定是地圖上的 Euclidean distance。

多層擴大範圍，但也可能把訊息平均得太像，或把大量遠方資訊壓進固定維度。這些限制會在第二階段深入；目前先注意，多層不代表所有 graph 都能分開。

補充共享是對角色共享，不是把所有 edge features 設成一樣

每條道路可以有自己的 $e_{ij}$ ，共同的 $\phi$ 讀取不同資料。若直接使用 edge 的存檔序號當特徵，序號也必須有合理 action；否則共享函數仍可能讀到不該影響答案的表示資訊。

每個 node 用共同規則產生 edge messages，對鄰居加總，再用共同 update 更新自己的狀態。

課堂提問

不同道路有不同寬度，會不會破壞 message passing 的 permutation equivariance？

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

不會，只要寬度屬性隨 edge 一起重編。共享的是處理寬度的方法，不是要求所有道路寬度相同。

動手看一次

拖動訊息輪數，觀察每個路口的值如何依 adjacency 更新，再重編 nodes。每一輪都使用相同的 message 與 update 規則。

搜尋筆記