視頻連接：2020 CCF 沈華偉 GNN
1.概述
卷積神經網路的成功的原因：能夠學習到資料中區域資訊，通過區域化卷積核，實際上是一種引數共享的方式，
然后通過逐層堆疊的方式，把區域的卷積核變成多尺度的層次模式，從而實作特征學習的一個效果，
1.1 區域卷積核：
平移不變性，可以得到與位置無關的一些pattern
2.卷積的遷移
2.1難點
怎么將歐氏空間的卷積轉移到非歐氏空間（non-Euclidean domain）中，比如說graph，其結構是非規則的難以定義卷積，
影像與網路：
我們可以想象為一個規則的網路，像素代表一個節點，其卷積核可以簡單的定義，但是真實世界中的網路，要遠比上述網路復雜，
真實網路節點的度分布差異非常大，有類似核心節點（微博大V），也有類似邊緣節點，不像影像抽象出的網路只有上下左右存在度，
每個節點的鄰居數不同，所以很難定義滿足平移不變性的卷積核，這是圖上定義卷積的很大的一個難點，
2.2 網路卷積的運用
CNN遷移到圖上定義圖上，總體來說還是這兩點：
如何定義圖上的卷積；定義圖上的pooling（下采樣這樣的操作），但是pooling和具體的任務相關，如果和節點相關，也就不需要下采樣，
2.2.1 卷積：
兩個函式點積之后，做積分，生成第三個函式
信號處理中，g即一個方波；f即為是個信號，橫軸為時間，
離散情況下，如影像中，卷積核即為一個patch，在影像的像素上滑動，抽取區域的信號，
舉例：擲骰子，兩次骰子，和為8的概率是多少？（2+6；3+5；4+4；5+3；6+2五種情況的概率之和）
2.2.2 圖上卷積：
定義有兩種方法，
一種是空間方法，但是網路中每個節點的鄰域大小多少不一致，很難有進展；
另一種是譜方法，將原來的圖 從節點域里變化到譜域里（利用卷積定理和傅里葉變換實作），在譜域里再定義卷積核，面臨的挑戰：其卷積不再區域化，會帶來網路特征較大范圍的改變，
2.2.3 譜方法：
輸入圖G，W為其帶權重的鄰接矩陣，每個節點還有一個d維的特征，則n個節點形成特征矩陣X:Shape(n, d)，每一個維度都理解成定義在這n個節點的一個信號，類似于影像中RGB三維特征，
這里可以看出，圖的處理，本質上也與信號處理程序類似，
圖拉普拉斯（Graph Laplacian）：
參考信號處理的方式，我們有圖拉普拉斯（Graph Laplacian）方式進行處理：實際上對信號求導數操作，獲得信號在圖上的平滑程度，稱之為拉普拉斯算子
（1）拉普拉斯矩陣：
拉普拉斯矩陣式帶權度矩陣與帶權鄰接矩陣之差，度矩陣是一個對角陣，每一行的元素維鄰接矩陣該行之和，
但是我們常用其normalized版本，數學性質更好，I是單位矩陣，
通過拉普拉斯矩陣即可實作將信號轉移到譜域中去，
（2）圖傅里葉變換
參考連接：1、2、3
上面我們說到，圖上的信號一般表達為一個向量，假設有n個節點，在這一節，我們將圖上的信號記為：
每一個節點上有一個信號值，類似于影像上的像素值，
傅里葉反變換的本質，是把任意一個函式表示成了若干個正交基函式的線性組合，
圖上的信號如果要進行傅里葉變換，我們也需要找到一組正交基，來表達x，
任意的圖上的信號可以表示為：
所以，圖上的傅里葉變換，實際上是求一個表示的引數（權重），最終我們取這個表示的引數（權重），來替代這組信號，就是在譜域里面的表達，
（3）在譜域上定義卷積：
圖上的傅里葉變換只是一個手段，定義卷積利用的是卷積定理
卷積定理是傅立葉變換滿足的一個重要性質，卷積定理指出，兩個函式的卷積的傅立葉變換是兩個函式分別傅立葉變換后的乘積，（百度百科）
因此可得：
兩個信號，一個x一個y，
- 分別做傅里葉變換后，取其權重，得到兩信號在譜域上的表示，進行點積操作；
- 然后進行傅里葉逆變換，就可以得到在節點域的卷積操作，
所以，我們將UTy作為卷積核，與信號x進行點積操作，再進行逆變換，
總結：
- 把信號x變換到譜域中（這一步需要傅里葉變換），
- 在譜域中，定義一個卷積核（設初始值，反向傳播進行調整），與信號x在譜域中的表達做點積，
- 最后進行逆變換，把譜域中的卷積轉換到空間域或者說節點域中
這是CNN作者的原始方法，譜方法但是存在缺陷（挑戰）
- 依賴 拉普拉斯矩陣的特征分解，時間復雜度高，O(n3)，且特征向量是稠密的計算代價太高，
- n*n的拉普拉斯矩陣求特征向量復雜度是O(n2)
- 在節點域上不是區域化的，
3.缺陷改進
3.1ChebyNet：引數化卷積核；
這里使用了拉普拉斯矩陣的特征值，改造卷積核，
原來的卷積核是反向傳播演算法得到的，這里將它改造，寫成一個由固定對角陣形成的多項式，這個對角陣，就是拉普拉斯矩陣的特征值形成的對角陣，經過簡化變換，可以發現卷積操作只剩拉普拉斯矩陣和輸入信號，β為引數，實際上通常K很小 0-9 六度分割，
三個好處：
不需要特征分解了，時間復雜度降低到O(K|E|)，卷積操作變為區域化的操作，
3.2 繼續改進：Graph Wavelet Neural Network
ICLR2019,圖小波神經網路:paper
chebNet的主要作業：
把原來自由的卷積核，用多項式函式做引數化，實作了圖卷積核取值空間的約束，進而不再依賴逆傅里葉變換，也實作了區域化，
作者更改傅里葉基為小波基
但是這樣操作，時間復雜度較高O(n*p*q)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/18165.html
標籤：其他
上一篇：弱特征會影響強特征嗎？
下一篇：哪位大神有搞過cs架構的自動化不