圖像化神經網路(1)：Graph Neural Network小簡介
首先感謝各位讀者的支持，追蹤的人數達到100的小里程碑，算是一個開始吧。
這篇要來談談圖像神經網路(graph neural network，GNN)。深度學習裡，無論是CV或是NLP，處理的都是具有相當結構的資料：例如影像，其架構規則在於畫素(pixel)，在圖片中，其位置和順序是有規律的。如果是影片，其架構規則變成影像，每一幀影像的順序是固定的。而在文字裡，字母之間和文字之間的順序也是固定的。這樣固定的結構，讓我們可以設計出比較平整的輸入端(input)，配合規律的計算方式(如卷積網路CNN)，訓練我們想要的模型。
然而，現實世界充滿架構和規律不固定的資料。例如：化合物的結構，雖然構成化合物的成分原子，具有一定的規則，然而其充滿彈性，不同化合物間的結構差異很大。除此之外，他們的順序性和上面提到的資料結構也有所不同：一個甲基和一個羫基的組合，並沒有如圖片裡(哪一個畫素一定在哪一個畫素的左/右邊)這樣的順序性。像這樣的資料，我們可以圖像描述其結構，但處理方式卻無法沿用既有的深度學習架構，必須有所調整。這就是GNN發展的背景。
本文來自[1]。有興趣的讀者可以前往閱讀。除此之外，其內容還有一部分的互動體驗，個人很推薦可以去看看。在稍後介紹到對應的段落時，如果有互動體驗區，會加註，讓大家方便參考。
進入正文前，建議讀者具備基本的深度學習或神經網路的運算原理/概念，否則可能會更抽象。
圖像(graph)的定義
在進入GNN前，應該再好好定義什麼是圖像。圖像的資料組成包含以下三種：
- 端點(Vertex，俗稱Node)：資料節點。通常是成員，例如化合物中的原子，或人際關係圖的人。儲存有節點本身的屬性，或是值，以及與其相鄰(或有互動關係)的端點。
- 連結(Edge，俗稱Link)：節點間的連線。主要描述節點間的關聯性，例如化合物中的共價鍵，或人際關係圖中的關聯。會儲存連結強度(類似權重)。連結可具有方向性(directed)。
- 整體(Global)：對應整個圖像。主要是這個圖像的屬性，例如化合物的名稱，其性質，或者人際關係圖的屬性(家庭、社會、公司)。儲存有代表這個圖像的資料，有時即為標註。在某些情況下，會用一個節點代表整體，該節點不和圖像內節點有任何直接連結，稱為master node。
將資料轉換成圖像結構
前面提到，影像或文字的資料結構型態和分子這類的結構不同。影像或文字的資料結構較為嚴謹，且比較講究順序性。事實上，正因為其結構較嚴謹，所以也可以轉換成圖像結構。怎麼說?
先看看影像。如下：
這是一個具有25個畫素的影像，根據顏色可以分為兩類。每個畫素依據其所在圖片的座標命名。這些畫素彼此之間，就現有的資料來看，位置是其最明顯的關聯。所以，以0–0畫素來說，它和1–0(在其左邊)、0–1(在其上方)、1–1(在其左上)有關聯。在比較中間的畫素，如1–1，其最多可和周圍8個畫素有關聯。如果把這些畫素的關聯轉換成矩陣，可以得到如下的結果：
藍色標記表示對應到的兩個畫素之間有關聯。對應的圖像結構如下：
很直觀，對吧?
如果是文字呢?
文字比起影像有更強調順序性，例如：graphs在are的前面，和在are的後面，意思不一樣。要解讀文意，文字的前後順序必須保留，因此對應的圖像中，連結具有方向性。
實務而言，當然不需要刻意將影像和文字轉成圖像結構來分析，因為已經具備其他有效的分析方式。然而，透過關聯矩陣轉換成圖像結構的概念，可以幫助我們了解將其他資料轉換成圖像結構的過程，例如，分子結構。
原子間的關聯，很完美的符合圖像結構的概念 — 可能比影像和文字轉換更好理解。但還是看一下它的關聯矩陣，以及最後的圖像結構：
值得注意的是，分子結構是3D的 — 表示它可能翻轉。翻轉之後，如果按照固定的順序(如從左到右)觀察結構，其排列的樣子會和翻轉前不一樣。然而，它應該還是同一個分子。這個變化，和剛剛圖片或文字的轉換結果就不太一樣了。
再看一個例子。如果從歌劇<奧賽羅>分析裡面人物的社交關係：
圖像結構可以解決什麼樣類型的問題?
應該是說，從圖像結構延伸出來，可以處理怎麼樣的問題。簡單來說，對應圖像的三個元素，可以處理三種問題：
- Graph-level task：處理整個圖像性質的問題。例如，預測某分子是否具有毒性，具有什麼氣味，或者這個關係圖屬於哪種方面的(家庭、學校、社會)。這很像深度學習裡的分類問題。
- Node-level task：處理圖像內節點的問題。判斷某節點的性質、屬性，甚至是值。例如，在人際關係圖中的某個人，和誰比較親近，甚至是屬於哪一派[2]。對應到深度學習，有點像CV裡segmentation的問題：這個畫素是否屬於某個物件的一部分?還是背景?
想多了解segmentation，請看出道作
3. Edge-level task：有點像是垃圾桶分類，其他圖像相關的問題，不屬於上述兩者的，都歸類在這邊。其中一個例子是對於場景的理解：我們在圖片中可以圈選出各個物件，但如果要知道物件之間的關聯性，就要用圖像分析。如下圖：
這是一個格鬥比賽的圖片，可以看到兩位選手、裁判和觀眾，及舞台。經過圈選處理之後，可以得到各個物件。
如果我們輸入一個圖像，對應各物件的位置。預期的輸出是描述各物件的關聯性。
利用機器學習處理圖像問題
建立資料格式
無論是機器學習或深度學習，如同最上面討論的，他們對輸入的資料有一定程度的結構要求，例如在圖片，就需要一固定大小，而在文字，也有一固定字數要求。其原因在於，輸入模型的資料會被轉換成矩陣，而矩陣的規格通常是固定的。
圖像結構並不總是滿足這種方式，因此要直接把現有的架構拿來使用，不是很直觀。幸好，還是有辦法的。對於端點、連結、整體，其儲存的資訊對應其所在的位置，可以做出一個對應矩陣，由此即可將這些資訊變換成模型輸入需要的格式。舉例來說，在某個人際關係圖有5個人，記錄了他們的年齡
要轉化成矩陣，只需要變成
或更簡單的，如果我們在命名順序上已經固定(例如順時針方向)，
即可。同樣的方法在連結和整體圖像的資訊也都適用。
但，圖像結構還有一個不好處理的資訊，就是關聯性。端點和端點之間的互動關係，並沒有被儲存在上述的任何一種元素裡。一種解決方法是用上面提過的關聯矩陣，但這種矩陣相當鬆散(有值的內容佔矩陣裡很少的空間)，而且，如果端點太多，很可能會讓矩陣要擴大到很可觀的程度(儲存空間：N²)。
關聯矩陣還有一個問題。如果我們將矩陣內的端點任意調動排序，則呈現出來的矩陣將會相當不同。以上面提到過的<奧賽羅>裡的人際關係，僅僅是對調裡面列舉的人物順序，就可以產生兩個截然不同的關聯矩陣，但其對應的人際關係仍然是一樣的：
我們縮小一點範圍好了。假設今天只有四個人物，彼此之間都有互動關係，那總共可以得出多少不一樣的關聯矩陣?很簡單，四個人任意排列，每一種組合都可以產生一個新的關聯矩陣，所以是4! = 24。只四個人就可以衍生出24種指涉同樣關係的關聯矩陣，可想而知，如果到歌劇那樣複雜的人物數目和關係，其可能的關聯矩陣可以衍生出多少。
既然關聯矩陣也不適合，那有沒有其他資料格式可以做到呢?有一個做法是用數組，或串列的方式記錄相連的兩個端點，稱為adjacency list。這一段推薦讀者去原網頁的互動區體驗一下，因為在那裡，讀者可以用滑鼠指向端點或連結，而旁邊對應的會告訴你，現在指的端點/連結，位於串列中的哪一個元素。這邊只截圖給大家參考，也方便大家在網頁中尋找。
這是一個具有8個端點的圖像。其端點的順序為順時鐘，從4點鐘方向的亮黃端點開始為第0個，依次到2–3點鐘方向那個暗黃端點為第7個。連結的排序，由低到高，但指向都是由高到低。所以先看第0個端點，有兩個與它連結，分別是第1個和第2個，因此前兩個為[1,0]和[2,0]。接下來，第2個端點還有一個連結，但來自於第6個，因此先跳過，挑了[4,3]做為第三個元素。接下來的連結除了[6,2]之外，均從第7個端點發出，因此排[6,2]。最後三個從第7個端點出發的連結，由小到大排：[7,3]、[7,4]、[7,5]。完成之後(或建立當下)，就可以把它轉成張量(tensor)了。
要注意的是，這裡是直接用端點的順位當作端點的值。然而，實務上這些端點多半是一個向量。因此，關於端點的那個串列(或張量)，就不會是[n_nodes]，而是[n_nodes,node_dim]維度的張量了。利用這個方法，可以把原先關聯矩陣需要的多達n²空間，減少許多(因為通常不是每個節點之間都有關聯性)。而且資料儲存是比較緊密的，不像關聯矩陣是鬆散的。此外，由於建立了連結的唯一性，這樣的格式並不怕端點任意排序造成的混亂，依然可以清楚知道哪兩個端點有連結，由此保證翻轉不變性(permutation invariant)。這是要拿來訓練神經網路的資料格式中，很重要的一個性質。
圖像神經網路(Graphic Neural Network, GNN)
GNN有其條件的。和其他深度學習的神經網路一樣，它必須在最佳轉換圖像的各個值(端點、連結、全體)的情況下，仍保持資料的不變性(即上述的permutation invariant)。GNN的輸入端是代表圖像的資料，其輸出也仍是代表圖像的資料(graph-in, graph-out)。
最簡單的GNN構造
這是一層GNN。裡面含有獨立的多層感知器(multi-layer perceptron，MLP)，對應到各自的處理項目：端點、連結，和整體。
由於先前已經將圖像轉換成張量了，這邊就可以套用我們熟悉的方法：乘以權重，加上bias，使用啟動函數…等等。輸出的仍然是張量，而且是照原本的方式(端點、連結、整體)。將一層層GNN堆起來，就是圖像深度學習了。
要注意的是，雖然圖像裡的張量經過運算，但其關聯性卻不需運算(這個部分不需要更新)。同時，輸入的向量總數和輸出的向量總數也一樣，但其內容有改變。
GNN的預測
前面提到過圖像結構可以處理的問題。我們也了解簡單的GNN運作的原理，但要如何利用它達成這些任務?
以分類任務為例，如果有一個二元分類任務，要將圖像中的任一節點分類，這是相對直觀的事情：只要在最後輸出的這些向量上面加個分類器就可以了，這個分類器通常是一個函數，但也可以是一個模型 — 處理向量的模型。
但事情有的時候不是這麼簡單。例如，圖像裡我們只有連結的資訊，而沒有端點的，但我們仍然要預測端點的分類。此時，我們要收集連結上的資訊，並把它們傳遞到端點上以進行預測。常用的做法叫「池化」(pooling)：
- 集合(gather)所有要收集的資訊，通常是以串接(concatenate)的形式(註：並排放置，組成一個矩陣)
- 聚集(aggregate)所有的資訊，通常用加法的方式
如果看文字還是不太懂的讀者可以到原網站去看示意圖，是可以互動的。
回到分類問題，如果我們要用連結的資訊來預測端點的分類，那就是pooling端點相關的連結，再接上分類器，如圖：
反之，如果是要用端點的資訊來預測連結的分類，那就將連結對應的端點資訊集合起來，再接上分類器：
如果我們只有端點的資訊，卻要預測整體圖像的分類，那就要將全部端點的資訊都集結起來了。這個和一般深度學習，池化層(poooling layer)做的事情很類似。
由此，我們大概可以把整個GNN進行分類任務的流程串起來：
GNN負責處理圖像轉換的資料，並確保其形式；因應分類任務的需求和資料目前的狀況，可以做對應的轉換(例如需要pooling的話)；最後將處理好的向量送進分類器，得到預測。整個過程裡面，包括GNN的運算，以及分類器的運算，都是可微分的。
關於微分、梯度、反向傳播：請看這篇
至此，一個簡單的GNN建立完成。值得注意的是，目前我們沒什麼動用到關聯性的資訊：只有在需要pooling的時候，才需要參考關聯性的資訊。目前為止，基本上各端點、各連結，乃至於整體的資訊，基本上是獨立被運用的。
在圖像內傳遞訊息
剛剛建立的基礎GNN，使用pooling是為了因應預測的標的缺乏對應資訊，所以透過關聯性，找到相關的端點/連結，並將他們的資訊集結到目標，以便進行預測。這表示pooling本身可以讓資訊在端點和連結間交流之外，同時也使用到關聯性的資訊。藉由這個方式，我們更新的向量裡會帶有來自其他位置的資訊，而這些位置的資訊能出現在這邊，暗示關聯性的存在。所以更新的向量裡同時也包含了關聯性。
在即使端點或連結的資訊都具備的情境下，我們依然可以使用pooling，就是要利用到關聯性的資訊。在這個情境下，我們把它稱作訊息傳遞(message passing)，他們的差別在於，pooling是在最後一層要進入分類器之前才這樣操作，而訊息傳遞在每一層的GNN都可以做。步驟如下：
- 和上面一樣，把向量聚集起來。
- 和上面一樣，集合向量，通常用累加(sum)的方式。
- 將這個向量(現在叫message了)透過一個可更新的函數傳遞，這個函數通常是一個神經網路。
這個流程是不是有點熟悉?和周圍位置的資訊一起收集，進到運算，然後傳到下一層，重複這個步驟…那不就是卷積神經網路(CNN)嗎?沒錯，在CNN裡，相鄰位置集結資訊的是圖片的畫素，而在這裡，GNN的訊息傳遞收集的是相鄰位置的端點/連結。差別在於：CNN有固定的規格，而訊息傳遞端看關聯性決定，比較有彈性。
我們再以端點的訊息傳遞為例。第一層的GNN，收集的是某個端點周圍，有直接關連性的端點的資訊。再堆疊一層之後，雖然重複這個步驟，但別忘了，它周圍那些端點，在上一層也跟他做過一樣的動作 — 蒐集周圍直接關聯性的資訊。所以在第二層，這個端點可以藉由只集結周圍有直接關聯性的端點的資訊，就收集到間接關聯性端點的資訊了。如此層層疊加，疊到一定層數的時候，一個端點可能可以囊括整個圖像一大部分，甚至是整體端點的資訊，只是所含資訊量的比重，隨端點關聯性遠近有所不同而已。
連結的訊息傳遞
如果是儲存在連結的訊息，要套用訊息傳遞的方法，可不可行?理論上也可行。利用類似在端點操作的方法，把周圍的連結資訊集結起來就可以了。然而，連結的資訊有時包含其所連結的端點。圖像中，端點和連結的個數，以及其向量(或張量)的維度不一定，也不需要一致。但也因此，資訊中摻雜端點與連結的時候，就會遇到問題。解決辦法是用映射(可以用線性的)，將端點的向量空間投射到連結的向量空間，將資訊整合好之後，再投射回來，或往下傳遞到神經網路。
在這個示意圖中，三個項目的向量是可以任意切換的。我們可以只使用端點的向量，更新它；或者我們可以使用連結的向量，利用映射的方式整合，之後再映射回端點，更新的端點裡便含有連結的資訊。如果再加上後續的神經網路，排列組合更多。如何挑選其順序和組合?這就是GNN設計的研究領域了。
舉個例子來說，有一種「編織」型態的GNN[3]，取用四種組合來更新端點及連結的資訊：(1) 端點-端點(線性) (2) 連結-連結(線性) (3) 端點-連結(整合在連結) (4)連結-端點(整合在端點)。
一切取決於需求。無論什麼組合，向量的整合會在進入神經網路前完成，然後才能更新目標的資訊。
加入整體的訊息
前面提到利用訊息傳遞的方式，可以讓端點掌握到一定範圍內其他端點的資訊。然而，如果要讓單一端點取得遙遠的端點資訊，這樣的方法還是有問題。一是隨著距離越遠，端點能得到的資訊越少。二是訊息傳遞的層數有極限，如果圖像的架構大於層數，某些端點的資訊就無法獲得。如果硬要擴大層數使其能容納圖像，那運算的所需容量將會迅速上升，對於成本和時間都是負擔。
所以這邊提出一個做法：設立一個向量代表整體的資訊，這個向量被稱作master node或context vector。這個向量和全部的端點以及連結都有連繫(空間上的)，可做為橋樑聯繫彼此，同時也藉由訊息交換建立代表整體的資訊。如此一來，可以提供更豐富而複雜的資訊。
這些資訊可以僅僅是透過串接，然後更新；也可以用前面提過的方法，把他們映射到同一個空間，再進行加總，之後進入到可更新的神經網路。
GNN遊樂園
這裡強烈推薦讀者移駕到原文去使用互動功能，體驗一下GNN運作的模式。作者使用一個GNN來做小分子的分類模型，預測的是分子的氣味，這是一個已經有100年歷史，結合化學、物理、神經科學的題目。為了簡化模型，作者把它設計成預測分子是否具有「嗆辣味」(pungent)。例如蒜、辣椒都具有這種味道。根據研究，這可能和烯丙醇(allyl alcohol)分子有關。另外一種分子piperitone也具有這種味道。
每個分子都是一個圖像，端點就是原子，裡面含有經過one-hot encoding處理的類別資訊(碳、氮、氧、氟)。連結是鍵，一樣含有經過one-hot encoding處理的類別資訊(單鍵、雙鍵、三鍵、芳香類)。
模型搭建使用一個序列型GNN(即將GNN堆疊，有序性的)，配上一個具有sigmoid函數的線性模型分類器以做預測。作者並提供一些參數，可讓讀者用來調整模型架構的：
- GNN層數
- 各值(端點、連結、整體)在模型內的維度。可更新的函數是一層MLP和Relu啟動函數，以及一層標準化層
- 集合的時候要用什麼方法：有max、mean和sum
- 可更新的值(端點、連結、整體)種類，以二元方式設計。基礎模型是全部關掉，各端點、連結之間無訊息傳遞，只能用本身的資訊去更新。隨著打開各個值，彼此可以交流，模型也會變得更立體。
為了更好了解模型如何做分類，作者「偷看」模型的倒數第二層，即進入最後的線性分類器之前的狀況(activation)。因為這些向量都是高維度的，作者使用主成分分析(PCA)試著在讓其降到二維的同時，還能保有向量的主要特徵，並據此作圖。好的模型應該能把預測的結果劃分成清楚的界限，但由於模型簡單化，而且降維之後難保不流失資訊，有可能還是不那麼清楚。
其實作者還提供了一個參數可以調整：訓練次數(epoch)，在右下角那個橫棒。我自己操作，大概10 epoch之後，模型表現就趨於穩定了。
根據經驗累積的GNN設計
從不同的參數調整組合之中，不知道讀者有沒有找到讓結果(AUC)更高的方法?我嘗試的時候，有發現整體的資訊還蠻重要的：如果三個值只能選一個打開做訊息傳遞，那選擇整體，會讓模型的表現最好。值的維度好像影響比較小。當然，如果要看模型的表現，資料的狀況佔很大的因素。
首先看到參數量對模型表現的影響。
在走勢上，參數量的確和模型表現有一些正相關。GNN是個有效率的模型，在還不須很多參數的時候(大約3000)，模型已經有比較穩定的好表現了。
再來是值的維度。
提升值的維度，對於模型的平均表現和最差表現有幫助，但在最佳表現上則沒什麼影響。值的維度會對應參數量，所以這個圖和上個圖可以呼應：較好表現的那群分布，其實從較低的參數量就有了，但到較高的參數量時，並沒有再繼續提升最佳表現。
然後是GNN層數。
這裡和上面不同的是，模型表現的上限和均值，隨著層數堆疊之後有上升。最大的差別在只有一層和疊第二層的時候，再往上就沒什麼變了。反過來說，模型表現的下限竟然也跟著變低!
一個解釋是某些資料不適合集合太多端點的資訊。隨著層數堆疊，端點會蒐集更多周圍端點的資訊，但同時讓自身端點的資訊量比例下降，產生「稀釋效應」[4]。這次使用的資料集有沒有這個狀況呢?
從集合資訊的方式看，使用什麼方法幾乎沒有差別。
但看訊息傳遞的種類就有差了。大方向趨勢是隨著有參與交換訊息的值種類越多，模型表現越好。由於本次任務是預測分子是否具有嗆辣味，這是一個整體評估型的任務，因此，能收集到越貼近整體資訊的模型，表現越好。
原子的類型顯然比鍵結類型更能決定分子的氣味，這很直觀。因此反映在圖表上的，只用連結資訊做傳遞的模型表現最差。
到這邊為止，關於初步介紹GNN的架構和運作就告一個段落了。GNN比較有趣的是「架構圖像」這一塊，因為它充滿彈性，對應的模型也要有彈性。由此可以推演出很多變化，而不會被架構所局限。
下一篇將會討論一些GNN比較細節的概念，也是這篇文章的最後1/3。歡迎大家繼續追蹤。
參考資料
[1] A Gentle Introduction to Graph Neural Networks. https://distill.pub/2021/gnn-intro/
[2] An Information Flow Model for Conflict and Fission in Small Groups.
W.W. Zachary. J. Anthropol. Res., Vol 33(4), pp. 452–473. The University of Chicago Press. 1977.
[3] Molecular graph convolutions: moving beyond fingerprints. S. Kearnes, K. McCloskey, M. Berndl, V. Pande, P. Riley. J. Comput. Aided Mol. Des., Vol 30(8), pp. 595–608. 2016.
[4] Principal Neighbourhood Aggregation for Graph Nets. G. Corso, L. Cavalleri, D. Beaini, P. Lio, P. Velickovic. 2020.
