1. 首頁 > 生活百科 > >

GNN 101

生活百科GNN 101

GNN 101

姚偉峰http://www.cnblogs.com/Matrix_Yao/
  • GNN 101
    • Why
      • Graph無處不在
      • Graph Intelligence helps
      • It’s the right time now!
    • What
      • 如何建模圖
        • Different Types of Graph
      • 如何表示圖
      • 如何計算圖
      • 不同的圖數據集規模
      • 不同的圖任務
    • How
      • Workflow
      • 軟件棧
      • SW Challenges
        • Graph Sampler
        • Scatter-Gather
        • More
    • Finishing words
    • References
WhyGraph無處不在
GNN 101

文章插圖
Graph Intelligence helps
GNN 101

文章插圖
It’s the right time now!Gartner預測，graph技術在數據和分析創新中的使用率從2021年的10% ， 到2025年會增長到80% 。我們目前正在經歷從early adoption到early mainstream的穿越大峽谷期間，既不太早也不太晚，時間剛剛好 。
GNN 101

文章插圖
What如何建模圖
A graphis an ordered pair= (, ) comprising:
  • , a set of vertices (or nodes)
  • ?{(,)|,∈}, a set of edges (or links), which are pairs of nodes
Example:
GNN 101

文章插圖
Different Types of Graph
  • Are edges directed? Directed Graph vs. Undirected Graph
  • Are there multiple types of nodes or multiple types of edges? Homogeneous Graph vs Heterogeneous Graph
如何表示圖不同的表示方式會指向不同的計算模式 。
GNN 101

文章插圖
如何計算圖如下圖所示，圖的計算步驟如下：
  • 遍歷圖中的所有結點，或者采樣圖中的一些結點 。每次選擇其中一個結點 ， 稱為目標結點(target node);
  • 一個-層的GNN至少需要聚合目標結點的L-跳領域的信息 。因此，我們需要以圍繞目標結點構造一個L-跳的ego network 。圖中是一個2-跳ego network的例子，其中綠色結點是第1跳，藍色結點是第2跳；
  • 計算并更新ego-network里的每個結點的embedding 。embeddings會使用到圖的結構信息和結點與邊的特征 。

GNN 101

文章插圖
那么，這些embedding是如何計算和更新的呢？主要是使用Message Passing的計算方法 。Message Passing有一些計算范式如GAS(Gather-ApplyEdge-Scatter), SAGA(Scatter-ApplyEdge-Gather-ApplyVertex)等 。我們這里介紹歸納得比較全面的SAGA計算范式 。假設需要計算和更新下圖中的
GNN 101

文章插圖
:
GNN 101

文章插圖
  • Scatter Propagate message from source vertex to edge.

GNN 101

文章插圖
  • ApplyEdge Transform message along each edge.

GNN 101

文章插圖
  • Gather Gather transformed message to the destination vertex.

GNN 101

文章插圖
  • ApplyVertex Transform the gathered output to get updated vertex.

GNN 101

文章插圖
公式如下：
GNN 101

文章插圖
分析一下，會發現，SAGA模式中ApplyEdge和ApplyVertex是傳統deep learning中的NN(Neural Network)操作，我們可以復用；而Scatter和Gather是GNN新引入的操作 。即 ， Graph Computing = Graph Ops + NN Ops 。
GNN 101

文章插圖
不同的圖數據集規模
  • One big graph 可能高達數十億的結點，數百億的邊 。

GNN 101

文章插圖
  • Many small graphs

GNN 101

文章插圖
不同的圖任務
  • Node-level prediction 預測圖中結點的類別或性質

GNN 101

文章插圖