此為中央大學資工系蔡宗翰老師提供給修課學生的參考資料的handout，為Jure Leskovec 課程的Graph Neural Network投影片的簡略解說，在此分享給有興趣的同好。這可不是完整的介紹文章，請對照原投影片使用。
投影片來源：http://web.stanford.edu/class/cs224w/slides/08-GNN.pdf
前面的標號為頁碼。
- Node embeddings
將輸入圖的所有節點映射到d維空間，使得相像的節點被映射在附近 - 讓嵌入空間中的相似度（例如內積）逼近原本網路中的相似度
- 需要定義similarity(u,v)及ENC(u)及ENC(v)
- 兩個重要元素：編碼器ENC(v)與相似度函數
- 由淺層的編碼器開始。在嵌入矩陣中，節點i的向量對應到第i欄
- 單隱藏層將u映射到嵌入Zu, 透過某個函數f。例如將u的每一個鄰居v的嵌入Zv都當成是輸入。
- 淺層編碼器的缺點
＊輸入需要O|V|這麼多個參數，節點間未共享參數，每個點有自己的嵌入
＊無法為訓練時未見過的節點產生嵌入向量
＊無法納入節點本身的特徵 - 深度圖編碼器：ENC(v)=圖構的多層非線性轉換。這些深度編碼器都可以和節點相似度函數合起來用。
- 深度圖編碼器
輸入一圖，取卷積 - 網路遠比影像或文字複雜：(a)節點沒有固定順序或參考點 (b) 多半是動態的，且特徵為多模態。
- 由影像到圖
轉換鄰居的信息並合併之 - 真實世界的圖比前頁的圖要複雜
- 簡易法
＊將鄰接矩陣與特徵連接，餵入深度神經網路
＊這方法的問題為：(a) 有O(N)個參數 (b) 無法套用到大小相異的圖 (c) 節點順序變動會影響到輸出 - 本地網路鄰域：描述匯總策略、定義計算圖
堆疊多層 - V是點集合；A是鄰接矩陣；X是mx|V|的節點特徵矩陣
節點特徵：
＊社交網路是用戶資料、用戶圖片
＊節點若沒特徵，可以用one-hot編碼來指出某個節點，或是用全1向量 - 圖卷積網路。想法：節點的鄰域定義了一個計算圖
(1) 決定節點計算圖 (2) 傳播和轉換信息
學習如何在整個圖上傳播信息以計算節點特徵 - 匯總鄰居：基於本地網路鄰域生成節點嵌入
- 直覺：節點使用神經網路匯總來自鄰居的信息（每個方框都是神經網路）
- 直覺：每個節點都基於其鄰域定義一個計算圖！
- 模型可以是任意深度的：
§節點在每一層都有嵌入
§節點𝑢的第0層嵌入是其輸入特徵𝑥𝑢
§K層嵌入從K跳之外的節點獲取信息 - 鄰居聚合：不同方法的分別在於如何跨層聚合信息
- 基本方法：平均來自鄰居的信息並套用神經網路
- 將第0層嵌入初始為節點特徵
非線性函數；鄰居們上一層嵌入的平均； v的上一層嵌入
Zv：在K層鄰居聚合之後所得到的嵌入 - 訓練模型：必須在嵌入上定義損失函數
- Wk與Bk是待訓練的矩陣
我們可以將這些嵌入餵給任何損失函數，並進行隨機梯度下降以訓練權重參數 - 非監督式訓練
＊僅使用圖結構，讓“相似”節點具有相似的嵌入
＊損失函數可以是基於Random walks、圖分解、或圖中的節點接近度 - 監督式訓練：直接以某個監督式學習任務訓練模型（例如，節點分類）
- 編碼器輸出為節點嵌入；節點類別標籤；分類權重
- 模型設計：(1)定義鄰域匯總函數 (2)在嵌入上定義損失函數
- (3)在一個點集合（一批計算圖）上訓練
- (4)為點產生所需的嵌入（包含訓練時未曾見過的點）
- 所有節點共享相同的匯總參數
- 例如，以來自生物A的蛋白質相互作用圖訓練模型，並在有關生物B的新數據上生成嵌入
- 許多應用程序設置不斷遇到以前看不見的節點，需要“即時”生成新的嵌入
- 總結：通過匯總鄰域信息來生成節點嵌入
§我們看到了這個想法的基本變體
§關鍵區別在於不同方法如何跨層匯總信息
Next：描述GraphSAGE圖神經網絡架構 - 到目前為止，我們已透過取鄰居們的（加權）平均值來匯總鄰居訊息。
有更好的方法嗎？ - 可將𝑁(𝑢)中的向量集映射到單個向量的任何微分函數
對每一層的每個點嵌入套用L2歸一化
連接鄰居嵌入和自嵌入 - 各種匯總鄰居法
＊取平均
＊池化：變換鄰居向量並套用對稱向量函數 （每個元素取平均值或最大值）
＊LSTM - 關鍵思想：根據本地鄰域生成節點嵌入，節點用神經網路匯總來自鄰居們的“消*息”
＊圖卷積網絡：平均鄰域信息和堆疊神經網絡
＊GraphSAGE：泛化的鄰域聚合 - 通過（稀疏）矩陣運算可以有效地執行許多匯總
- 𝛼vu = 1 / |𝑁（𝑣）| 是節點𝑢到節點𝑣的消息的權重因子（重要性）
𝛼vu是根據圖的結構特性明確定義的
所有鄰居𝑢∈𝑁（𝑣）對節點同樣重要 - 我們能比簡單的鄰域聚合做得更好嗎？
我們可以隱式定義加權因子𝜶𝒗𝒖嗎？
目標：對圖中每個節點的不同鄰居指定任意重要性
想法：按照注意力計算圖中每個節點的嵌入：
＊節點注意他們鄰居的消息
＊隱式地為附近的不同節點指定不同的權重 - 讓𝛼uv被計算為注意力機制𝒂的副產物：
𝒂基於各組節點(u,v)的訊息，計算注意力係數𝒆𝒗𝒖：
＊𝒆𝒗𝒖表示節點u的消息對節點v的重要性
＊使用softmax函數歸一化係數，以便在不同鄰域之間可比較：
＊下一步：注意機制𝑎的形式是什麼？ - 注意力機制𝑎：
＊該方法與𝑎的選擇無關。例如，使用簡單的單層神經網絡。𝑎可以具有參數，需要對其進行估算。
＊𝑎的參數是一起被訓練的：以端到端的方式學習參數以及權重矩陣（即神經網絡的其他參數）
多頭注意力：可穩定注意力機制的學習過程：
＊給定某層中的注意力操作被獨立地複製R次（每個副本具有不同的參數）
＊輸出匯總（通過串聯或相加） - 主要優點：允許（隱式）為不同的鄰居指定不同的重要性值（𝜶𝒗𝒖）
＊計算效率高：注意係數的計算可以在圖的所有邊上並行化；匯總可以在所有節點上並行化
＊存儲效率高：稀疏矩陣運算不需要存儲超過O（V + E）個項；固定數量的參數，與圖形大小無關
＊直觀的本地化：僅注意本地網路鄰居
＊歸納能力：這是一種共享的逐邊機制；並不依賴於全局圖結構 - 基於GAT的節點嵌入的t-SNE圖：節點顏色：7個刊物類
邊緣厚度：節點𝑖與節點𝑗之間的歸一化注意係數，跨越八個注意力頭 - 圖：2B圖釘，1B板，20B邊
＊圖是動態的：需要應用於新節點而無需模型重新訓練
＊豐富的節點特徵：內容，圖像 - PinSage圖卷積網絡：
＊目標：在包含數十億個物件的Pinterest圖中為節點（例如，圖釘/圖像）生成嵌入
＊關鍵：從附近節點借信息
＊例如床欄杆看起來像花園圍欄，但門和床在圖中很少相鄰
＊圖釘嵌入對於各種任務至關重要，例如針推薦，分類，聚類，排名（諸如“相關圖釘”，“搜索”，“購物”，“廣告”之類的服務） - 目標：將節點映射到d維嵌入，以便將相關的節點緊密地嵌入在一起
- 如何將訓練和節點嵌入的推論擴展到具有數十億個節點和數百億個邊的圖形？
＊比任何先前的圖神經網絡應用程式大10,000倍的數據集
關鍵創新：
＊子樣本鄰域可有效地進行GPU批處理
＊生產者-消費者CPU-GPU訓練管線
＊否定樣本的課程學習（主要思想是模仿人類學習的特點，由簡單到困難來學習課程《在機器學習裡就是容易學習的樣本和不容易學習的樣本》，這樣容易使模型找到更好的局部最優，同時快速訓練的速度。）
＊MapReduce可以進行有效的推理 - 三項關鍵創新：
1. 動態圖卷積
§對節點周圍的鄰域進行採樣並動態構建計算圖
§圍繞特定節點執行局部圖卷積
§訓練過程中不需要整個圖 - 2. 通過隨機遊走構造卷積
§在完整的鄰域上進行卷積是不可行的：如何選擇要進行卷積的節點的鄰居集？§重要性池化：以〈模擬隨機步行並選擇訪問量最高的鄰居〉來定義基於重要性的鄰域
3. 高效的MapReduce推論
§自下而上的節點嵌入匯總使其適用於MapReduce。也就是將所有節點上的每個聚合步驟分解為MapReduce中的三個操作，即map，join和reduce - 使用CNN產生的視覺嵌入
使用Word2vec產生的文字嵌入
將兩者合併 - Pixie是一種純粹基於圖的方法，它使用有偏的隨機遊走通過模擬從查詢Pin開始的隨機遊走來生成排名分數。檢索得分最高的項目作為建議。[Eksombatchai等，2018]
- 數據預處理很重要：
§使用重新正規化技巧
§方差縮放的初始化
§網絡數據白化
ADAM優化器：ADAM自然會降低學習率
ReLU激活函數通常效果很好
輸出層沒有激活功能：如果用一個函數構建多層，則容易出錯
為每一層添加偏差項
大小為64或128的GCN層已經足夠 - 人類基因網路
- 蛋白質交互作用預測
