# graph-learn: A Graph Neural Network Platform and applications of GNN
## graph-learn 簡介
(圖一) 2019年舉辦機器學習和計算神經科學相關的學術會議——神經訊息處理大會(NeurIPS)，其於12月8日的 Expo Day 所安排的議程。

---

於圖一可以看到各大科技公司龍頭紛紛在 NeurIPS 展示他們所研發的先進技術，為了和 Facebook, Google, Microsoft 和百度等大公司較勁，阿里巴巴集團拿出旗下計算平台事業團隊與達摩智能計算實驗室所共同開發的 AliGraph 進行現場展演，足以看出阿里巴巴對這項計畫的重視。

目前 Aligraph 的 Github 頁面已更名為 [graph-learn](https://github.com/alibaba/graph-learn)，然而論文發表的當時，名稱仍為Aligraph，以下會以新名稱稱呼之。graph-learn 在阿里巴巴集團裡面隸屬於另一個更大架構的計劃——[GraphScope](https://graphscope.io/) 之下，負責處理圖神經網路的計算，整個 GraphScope 的目標是希望提供使用者一站式可以處理完圖計算任務的平台，該平台底層以分散式叢集電腦來支持各式的圖計算所需要的操作，GraphScope 整合了阿里巴巴旗下三個開源項目來完成這樣的目標，這些項目除了graph-learn，還有負責圖訊息分析的 [GRAPE](https://github.com/alibaba/libgrape-lite) 以及互動介面的 [MaxGraph](https://github.com/alibaba/GraphScope/tree/main/interactive_engine)。

graph-learn 主要面向的是工業級別的巨量圖論資訊，例如: 數以億計的圖資料節點，以及數以十億計的連結，這樣的圖論資料，graph-learn 都能以優於其他類似計算平台的效率來完成下游的圖神經網路任務，常見的應用場景有電商平台上的商品推薦、目標客群分類或是支付平台的詐欺偵測等，graph-learn 已經在阿里巴巴集團的營運場景中實地被使用，並驗證其作為圖神經網路計算引擎的效率。

## graph-learn 架構與技術介紹
(圖二) graph-learn 的系統架構

---

上圖為 graph-learn 的系統架構 [[1]](https://arxiv.org/abs/1902.08730)，其中藍色方框處是 graph-learn 提供給使用者的底層系統支援，從最下層的儲存到一些計算圖神經網路需要用的操作，包括採樣、aggregation 與 combination 等，graph-learn 都提供了抽象化的 API 介面給使用者直接呼叫；在演算法層方面，graph-learn 有以自身為工具，開源一些常用的圖神經網路模型，例如: [Graph Convolutional Network (GCN)](https://github.com/alibaba/graph-learn/tree/master/examples/tf/gcn), [Graph Attention Network (GAT)](https://github.com/alibaba/graph-learn/tree/master/examples/tf/gat) 和 [GraphSAGE (Graph SAmple and aggreGatE)](https://github.com/alibaba/graph-learn/tree/master/examples/tf/graphsage) 等，你可以直接拿來佈署在既有的服務上，實現你需要的應用功能，例如電商平台維運商會希望對 user nodes 和 item nodes 做 link prediction ，以推薦消費者可能會喜歡的商品，或是對 user nodes 做分類，以對消費者做市場區隔，提供廣告商可以對哪些目標客群投放廣告較為有效的資訊。

在上述過程中，graph-learn 的使用者完全無須擔心底層的圖資訊在分散式儲存後，該如何做存取等問題，而圖神經網路的研究者也可以此平台為基底，專心於演算法的設計上，以節省時間不用去開發那些不同模型往往都共用的基本操作。

以下介紹一些 graph-learn 使用的技術，探討他們如何達到時間與空間上的計算效率，首先，graph-learn有特別設計拿來儲存帶有特徵訊息的異質圖(attributed heterogeneous graph，簡稱 AHG) 的機制。

### 異質圖
異質圖的概念相對於同質圖，同質圖代表圖中每個節點都是同樣類型，每個邊也都是互為同類，雖然不同節點指稱的對象不同，但在處理時並不會區分彼此，舉一反例可以想像電商平台上，若把消費者與商品都轉變為圖上的節點來處理，而邊的關係以購買行為來定義的話，這時就會產生出一個二分圖，消費者間並不會有連結，同樣地，商品間也不會有連結，與此同時，由於圖裡面的不同節點開始有不同的意義，我們會把這樣的圖歸類為異質圖。同理，圖上的邊也可有同質或是異質的特性，端看邊與邊之間我們定義他們的性質有沒有差異，若是邊有不同的種類(例如: 電商平台上的點擊、加入購物車或購買等行為，我們定義為不同類型的邊)，那我們也會將此類圖視為異質圖(圖五上)。
### 特徵異質圖 (attributed heterogeneous graph, AHG)
建立於此之上，若是每個點與邊，都能帶有特定的特徵(attribute)，則進一步定義這種圖為 AHG。graph-learn 在儲存這類圖的方法上，為了減少同類型的特徵大量地重複儲存而浪費空間，會將所有節點與邊的特徵集合(attribute set)統一處理為 table 的形式(如圖三的**I~V~**與**I~E~**) ，而原始圖的節點與邊的資訊則用鄰接串列的形式儲存(adjacency list)，相較於鄰接矩陣的資料結構表示法，鄰接串列較不像鄰接矩陣一樣，因為資料稀疏性的緣故，而浪費太多空間來儲存資料點為0的 cells。

相較於沒有把特徵集合拉出來儲存的方法，此機制可以把空間複雜度從原本的 O[(圖的節點數)\*(節點 degree 的平均)\*(平均 attribute 需要的儲存長度)] 優化到 O[(圖的節點數)\*(節點 degree 的平均) + (attribute set 的數量)\*(平均 attribute 需要的儲存長度)]，由於特徵集合的大小通常遠小於圖的節點數量，因此這樣的方法可以較有效率地利用儲存空間。
(圖三) graph-learn 儲存特徵異質圖 (AHG) 之機制示意圖

---

### graph-learn 的快取機制
為了能儲存巨量規模的圖資訊，graph-learn 需將圖分散式儲存在不同機器的硬碟中，而當圖的節點走訪需要從一台機器橫跨到另一台的資料存取時，為了縮短這樣龐大的時間成本，graph-learn 使用快取的方法，來加速處理，至於該如何決定哪些資料點值得放入快取記憶體中，graph-learn 採取一個簡單卻有效的機制。

我們會希望常被使用到的節點可以有越高的機率停留在快取記憶體中越好，因此 graph-learn 使用了一套評定資料點重要性的方法，其概念為，當一個節點被越多其他的鄰居所指向時，則我們會認為這個節點的重要度越高，那麼 graph-learn 傾向把此節點指向的輸出節點，都放入其各自所在的 partition 的快取，如此一來，快取記憶體的使用率會較高；然而，graph-learn 同時還考慮另一個因素，那就是如果這個目標節點的輸出節點數量過於龐大，那麼要將其所有輸出節點都放入快取的話，會造成過大的儲存成本，因此，在考慮目標節的的重要性時，也會同時把這項成本放入考量，最終的重要度計算公式設計為: Importance (v) = (節點 v 的 input degree)/(節點 v 的 output degree)，對圖中的所有節點計算重要度後排序，將分數最高的幾個重要節點，其所有輸出節點放入快取記憶體中，並就此固定不再依 GNN 計算過程而更新快取。

圖四為實驗三種不同快取機制的效果比較，y軸為在分散式儲存系統中存取圖資訊的時間成本(ms)，x軸為將不同比例的節點放入快取記憶體，折線圖的總體趨勢可以觀察到，放入越多的節點進入快取，可以降地較多時間成本，而 graph-learn 提出的重要度計算快取機制(藍線)，比起紅色的隨機挑選節點放入快取的方法，在不同的x軸比例下，都是有較高優化的；相對而言，使用綠色的 LRU (Least Recently Used)快取機制，效能表現反而比隨機選取還要來得差，其原因在於，LRU cache 會引發頻繁地快取汰換，將快取記憶體中最久以前被使用到的資料點更新成這次被使用的資料點，這樣額外的時間成本，反而拖累了系統整體的時間效率表現，使得y軸的時間成本並不會隨著存入越多的節點資料進快取而改善。


(圖四) graph-learn 使用的快取機制與其他方法在時間成本之比較，x軸為放入快取記憶體的節點比例。

## GNN 的商業應用

這部分內容主要參考自[Top Applications of Graph Neural Networks 2021](https://medium.com/criteo-engineering/top-applications-of-graph-neural-networks-2021-c06ec82bfc18)[2]這篇文章，作者為Sergei Ivanov。
GNN主要是將Neural Network推廣到非歐幾里得空間的資料上，例如社交網絡、物理系統、生物網絡、知識圖譜等。例如CNN能夠處理處理大量且區域關聯複雜度高的資料，其中的卷積層具有局部加權平均的特性，能夠提取區域特徵，而圖(graph)是最典型的區域關聯性結構，圖中的區域為節點的鄰居(neighbors)，節點間會由邊(edges)來互相傳遞資訊。因此許多可以由圖來表達的問題，適合使用GNN的架構。
GNN相關的應用大致上可以分為五個方向:推薦系統(Recommender Systems)、組合優化(Combinatorial Optimization)、電腦視覺(Computer Vision)、自然科學(物理、化學等)與藥物發現(Drug Discovery)。
1. 推薦系統
在推薦系統中，GNN已經有非常廣泛的應用，許多電子商務平台也已經使用GNN來建立他們的推薦系統，例如[Uber Eats (2019)](https://eng.uber.com/uber-eats-graph-learning/)、[Alibaba(AliGraph, 2019)](https://arxiv.org/abs/1902.08730), 、Pinterest([PinSage](https://arxiv.org/abs/1806.01973)/[PinnerSage](https://medium.com/pinterest-engineering/pinnersage-multi-modal-user-embedding-framework-for-recommendations-at-pinterest-bfd116b49475), 2018/2020)、Amazon([P-Companion, 2020](https://www.amazon.science/publications/p-companion-a-principled-framework-for-diversified-complementary-product-recommendation))等。在推薦系統中，GNN將用戶與商品間的行為以圖來表示，用戶或是商品為節點，邊則是代表行為，例如
(圖五) (上)Alibaba的[Attributed Heterogeneous Graph(AHG)](https://arxiv.org/abs/1902.08730)；(下)Amazon的[Behavior-based Product Graph(BGP)](https://www.amazon.science/publications/p-companion-a-principled-framework-for-diversified-complementary-product-recommendation)。

---

* Uber Eats的推薦系統分為兩種:根據用戶過去的喜好推薦類似的餐廳或食物，或是根據用戶資訊推薦其他類似用戶的喜好，但因為推薦具有區域的限制(例如外送範圍)，因此資料量較少。
* Alibaba的Aligraph則是為了在大量資料上能夠即時性的使用GNN而提出的平台。
* PinSage是Pinterest根據GCN(Graph Convolutional Network)提出的推薦系統架構，根據用戶的喜好推薦個人化的內容，PinnerSage則是將PinSage推廣到multi-embeddings，根據用戶不同的興趣領域分別推薦，例如一個用戶對鞋子、繪畫與科幻有興趣，同時與這三種興趣最接近的推薦也許反而會是不相關的東西，例如(圖六)。
* Amazon的P-Companion則是Complementary product recommendation (CPR)，在用戶購買商品時推薦同時具有相關性與多樣性的互補商品。

(圖六) [一位用戶的三種興趣](https://medium.com/pinterest-engineering/pinnersage-multi-modal-user-embedding-framework-for-recommendations-at-pinterest-bfd116b49475)。

---

2. 組合優化
組合優化問題是在有限的集合中找到最佳解，基礎的例如旅行推銷員問題(travelling salesman problem, TSP)與最小生成樹(Minimum spanning tree, MST)等，實際上在金融、物流、能源、生命科學與硬體設計的方面都有許多重要的應用，而大部分這樣的問題都可以用圖來表示，因此也有許多團隊使用GNN來解決組合優化的問題。
晶片由無數邏輯元件與記憶體組成，並能夠以圖來表示。[Google Brain team (2020)](https://ai.googleblog.com/2020/04/chip-design-with-deep-reinforcement.html)在晶片設計中使用GNN在短時間內完成晶片設計，最佳化晶片的功率消耗、面積與性能，例如Google的TPU。另外在混和整數線性規劃 (mixed-integer linear program, MILP) 問題上，也有許多團隊 ([Gasse et al.,2019](https://arxiv.org/abs/1906.01629); [Nair et al.,2020](https://arxiv.org/abs/2012.13349))提出以GNN架構來解決的方法。

3. 電腦視覺
在電腦視覺方向，透過場景圖(Scene Graph)可以將影像表達為一連串相互關聯的物件(圖七)。場景圖的應用包含影像檢索(Image Retrieval)、圖像問答(Visual Question Answering, VQA)([Hildebrandt et al., 2020](https://arxiv.org/abs/2007.01072?fbclid=IwAR2jZ1UIIz_0BSlcaIMv-V0PkQlOERAPC1h0Flb8kfbBrWAICCxVEajg8wQ))、圖像描述(Image Captioning)([Yang et al., 2019](https://openaccess.thecvf.com/content_CVPR_2019/html/Yang_Auto-Encoding_Scene_Graphs_for_Image_Captioning_CVPR_2019_paper.html?fbclid=IwAR05L26F_6t4IxrhEevNZXjdVMch4MWTSG3aDNNBA93VorHHdQH-RgUObE4))、圖像生成(Image Generation)([圖八，Ashual et al., 2019](https://arxiv.org/abs/1909.05379?fbclid=IwAR0_AG3JCEetRoknbO4C02qemJBgPqmJt2-BgJUJm97AXfGxP-beIEXYZFk))等，很多團隊對於這些應用根據GNN架構提出解決的方法。另外在影像的特徵匹配上，Magic Leap根據GNN提出[SuperGlue (2020)](https://arxiv.org/abs/1911.11763)這個方法，在實時的3D影片中做影像的特徵匹配(Feature Matching)，可以應用在SLAM、SfM等。


(圖七) [場景圖(Scene Graph)](https://cs.stanford.edu/~danfei/scene-graph/)。

(圖八) [影像生成範例](https://arxiv.org/abs/1909.05379)，從上至下: schematic illustration panel、場景圖與最後生成的圖片。

---

4. 自然科學
自然科學方向是指在物理、化學上，粒子或分子間的交互作用可以用圖來表示，GNN能夠預測這類的系統。在物理上，[Sanchez-Gonzalez et al.](https://sites.google.com/view/learning-to-simulate/home#h.p_hjnaJ6k8y0wo) 提出一個模擬動態複雜物理系統的GNN架構，可以預測數千到數萬粒子等級的運動，例如水、沙子或是膠體組成的運動(圖九)。[Bapst et al.](https://deepmind.com/blog/article/Towards-understanding-glasses-with-graph-neural-networks) 也提出以GNN架構來理解玻璃轉化(Glass Transition)。另外在高能物理中，[Fermilab](https://news.fnal.gov/2020/09/the-next-big-thing-the-use-of-graph-neural-networks-to-discover-particles/) 利用GNN分析處理大型強子對撞機實驗的數百萬張圖像，並選擇那些可能與發現新粒子有關的圖像。

(圖九) [複雜物理系統模擬圖](https://arxiv.org/abs/2002.09405)，模擬在不同初始條件下單一或混和材料在某一時間點的運動狀態。紅色為膠體，藍色為水，土黃色為沙子，黑色線條為剛性物體。

---
- [ ] 在化學上由Facebook AI Research與CMU合作的 [Open Catalyst project](https://opencatalystproject.org/) 目的在將可再生能源透過化學反應儲存為其他燃料的方法，並尋找能加速化學反應的催化劑，並使用GNN來預測可能的催化劑。

5. 藥物發現
在生物學中，在分子尺度下，圖中的邊能夠表示兩個原子間的鍵結，或是蛋白質中胺基酸殘基間的交互作用；而在更大的尺度下，圖可以表現更複雜的結構，例如蛋白質、mRNA、代謝產物(metabolites)等。相關的應用有目標識別、分子性質預測、高通量篩選、de-novo drug design、蛋白質工程與藥物再利用等。


(圖十) 藥物發現各種應用的時間線([Gaudelet et al., 2020](https://arxiv.org/abs/2012.05716))

## 其他圖神經網路計算架構
表一、附上現今常見的 GNN 計算平台及其開源程式碼連結供讀者參考[[3]](https://www.sciencedirect.com/science/article/pii/S2666651021000012)

## Authors
王仁德 朱文亞

## References
[1] R. Zhu, K. Zhao, H. Yang, W. Lin, C. Zhou, B. Ai, Y. Li, and J. Zhou, “Aligraph: A comprehensive graph neural network platform”. in Proceedings of the 45th International Conference on Very Large Data Bases, 2019.
[2] https://medium.com/criteo-engineering/top-applications-of-graph-neural-networks-2021-c06ec82bfc18
[3] Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., & Sun, M, “Graph neural networks: A review of methods and applications”. AI Open, 2020.