論文位址：A Generalization of Convolutional Neural Networks to Graph-Structured Data
GNN的做法是将一個圖結構的資料強行變化為一個類似規則的資料，進而實作1維的卷積。
傳統卷積：固定數量的鄰域節點排序後，與相同數量的卷積核參數相乘後求和。
那麼卷積就可以分為兩步：
1.建構鄰域(鄰節點固定且有序)
2.對鄰域的點和卷積核參數内積
但是對于圖結構資料而言：鄰域節點不固定，且圖結構無序。是以需要找到一個解決建構鄰域的方法。
解決思路：随機遊走，根據被選中的機率期望和大小選擇固定數量的鄰居節點。
實作：
首先定義
P P P矩陣 為圖上的随機遊走轉移矩陣， P i j P_{ij} Pij為i節點到j節點的轉移機率。
S S S矩陣 為相似度矩陣，可以了解為鄰接矩陣。
D D D矩陣 為度矩陣， D i i = ∑ j S i j D_{ii}=\sum_jS_{ij} Dii=∑jSij。
假設圖結構已知，則 S S S和 D D D已知，則 P P P定義如下：
P = D − 1 S P=D^{-1}S P=D−1S
上式子相當于對S進行歸一化，即使用歸一化的鄰接矩陣作為圖轉移矩陣。
多步轉移矩陣定義為 Q Q Q:
Q ( 0 ) = I , Q ( 1 ) = I + P , … Q ( k ) = ∑ j = 0 k P k Q^{(0)}=I,Q^{(1)}=I+P,\dots Q^{(k)}=\sum_{j=0}^kP^k Q(0)=I,Q(1)=I+P,…Q(k)=j=0∑kPk
其中 k k k為步數， Q i j ( k ) Q^{(k)}_{ij} Qij(k)表示i節點進過k步達到j的期望通路次數，可視化如下圖。
那麼選擇鄰域的問題解決了，可以根據期望通路次數來選擇需要的鄰域節點， π i ( k ) ( c ) \pi_i^{(k)}(c) πi(k)(c)表示節點的序号，表示該節點是經過 k k k步内由 i i i節點出發的通路期望第 c c c大的節點，那麼有節點期望通路大小排序:
Q i π i ( k ) ( 1 ) > Q i π i ( k ) ( 2 ) > ⋯ > Q i π i ( k ) ( N ) Q_{i\pi_i^{(k)}(1)}>Q_{i\pi_i^{(k)}(2)}>\dots>Q_{i\pi_i^{(k)}(N)} Qiπi(k)(1)>Qiπi(k)(2)>⋯>Qiπi(k)(N)
定義卷積：
每個點選取前 p p p個期望最大的作為鄰域節點，且順序由期望 Q Q Q決定。卷積核為 W W W，具有 p p p個參數。
舉例：