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无处不在

文章插图
Graph Intelligence helps

文章插图
It’s the right time now!Gartner预测，graph技术在数据和分析创新中的使用率从2021年的10% ，到2025年会增长到80% 。我们目前正在经历从early adoption到early mainstream的穿越大峡谷期间，既不太早也不太晚，时间刚刚好。

文章插图
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:

文章插图

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

如何表示图不同的表示方式会指向不同的计算模式。

文章插图
如何计算图如下图所示，图的计算步骤如下：

遍历图中的所有结点，或者采样图中的一些结点。每次选择其中一个结点，称为目标结点(target node);
一个-层的GNN至少需要聚合目标结点的L-跳领域的信息。因此，我们需要以围绕目标结点构造一个L-跳的ego network 。图中是一个2-跳ego network的例子，其中绿色结点是第1跳，蓝色结点是第2跳；
计算并更新ego-network里的每个结点的embedding 。embeddings会使用到图的结构信息和结点与边的特征。

文章插图
那么，这些embedding是如何计算和更新的呢？主要是使用Message Passing的计算方法。Message Passing有一些计算范式如GAS(Gather-ApplyEdge-Scatter), SAGA(Scatter-ApplyEdge-Gather-ApplyVertex)等。我们这里介绍归纳得比较全面的SAGA计算范式。假设需要计算和更新下图中的

文章插图
:

文章插图

Scatter Propagate message from source vertex to edge.

文章插图

ApplyEdge Transform message along each edge.

文章插图

Gather Gather transformed message to the destination vertex.

文章插图

ApplyVertex Transform the gathered output to get updated vertex.

文章插图
公式如下：

文章插图
分析一下，会发现，SAGA模式中ApplyEdge和ApplyVertex是传统deep learning中的NN(Neural Network)操作，我们可以复用；而Scatter和Gather是GNN新引入的操作。即， Graph Computing = Graph Ops + NN Ops 。