• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

图神经网络入门

开发技术 开发技术 2周前 (11-22) 8次浏览

拜读了Jure Leskovec的《Representation Learning on Networks》才明白图神经网络到底在学什么,是如何学的,不同GNN模型之间的关系是什么。总的来说,不同类型的模型都是在探讨如何利用图的节点信息去生成节点(图)的embedding表示

图表示学习的两大主流思想

  • 线性化思想
    • Deepwalk,Node2vec,LINE
  • 图神经网络
    • GCN,GraphSAGE,Gated GNN,subgraph embedding
目录
  • Node embedding
    • 1. Adjacency-based similarity
    • 2. Multi-hop similarity
    • 3.Random walk approaches
  • Graph neural networks

Node embedding

图神经网络入门

目标:编码节点使其在embedding空间的相似性近似为在原网络的相似性

  • 定义编码器encoder
  • 定义节点相似性函数
  • 优化参数使 (similarity(u, v) approx z_v^Tz_u)

可以看出,前两步是node embedding的核心。

第一个问题:如何映射节点到低维空间?

参考word2vec,借助embedding-lookup就可以

图神经网络入门图神经网络入门

第二个问题:如何定义节点相似性?

1. Adjacency-based similarity

  • Similarity function 定义为原网络中两节点之间的边的权重

  • 用点积近似边是否存在

    图神经网络入门

  • 找到使损失最小化的 embedding matrix (Z in R^{d*|V|})

2. Multi-hop similarity

考虑 k-hop 节点

上述方法的大致思想都是:

  1. 定义节点对的相似性
  2. 优化embedding去近似它们的相似性

3.Random walk approaches

DeepWalk,Node2vec

Graph neural networks

图G:

  • V 顶点集
  • A 邻接矩阵
  • (Xin R^{m*|V|})为节点特征矩阵
    • 文本、图像,例如社交网络中人口学信息
    • 节点的度,聚类系数等

如何表示节点

  • 核心思想:根据邻居节点生成节点的embedding

    图神经网络入门

    每个节点拥有独立的计算图

  • how to aggregate information across the layers

    • 最简单的方法就是 求均值

      图神经网络入门

      图神经网络入门

    • 其他方法……

  • 定义loss训练模型

    • 无监督
    • 有监督

下面不同的GNN算法都是在探索如何利用邻域节点生成当前节点的embedding表示

  • GNN基础思想

    [mathbf{h}_{v}^{k}=sigmaleft(mathbf{W}_{k} sum_{u in N(v)} frac{mathbf{h}_{u}^{k-1}}{|N(v)|}+mathbf{B}_{k} mathbf{h}_{v}^{k-1}right)
    ]

  • GCN

    [mathbf{h}_{v}^{k}=sigmaleft(mathbf{W}_{k} sum_{u in N(v) cup v} frac{mathbf{h}_{u}^{k-1}}{sqrt{|N(u)||N(v)|}}right)
    ]

  • GraphSAGE

    [mathbf{h}_{v}^{k}=sigmaleft(left[mathbf{W}_{k} cdot operatorname{AGG}left(left{mathbf{h}_{u}^{k-1}, forall u in N(v)right}right), mathbf{B}_{k} mathbf{h}_{v}^{k-1}right]right)
    ]

    AGG函数可以定义为:

    • Mean

      [mathrm{AGG}=sum_{u in N(v)} frac{mathbf{h}_{u}^{k-1}}{|N(v)|}
      ]

    • Pool

      [mathrm{AGG}=sigmaleft(left{mathrm{Q} mathrm{h}_{u}^{k-1}, forall u in N(v)right}right)
      ]

    • LSTM

      [mathrm{AGG}=mathrm{LSTM}left(left[mathbf{h}_{u}^{k-1}, forall u in pi(N(v))right]right)
      ]

  • Gated Graph Neural Networks

    [mathbf{m}_{v}^{k}=mathbf{W} sum_{u in N(v)} mathbf{h}_{u}^{k-1}
    ]

    [mathbf{h}_{v}^{k}=operatorname{GRU}left(mathbf{h}_{v}^{k-1}, mathbf{m}_{v}^{k}right)
    ]

上述方法都是nodel-level embeddings,如何embedding图?

  • Subgraph Embeddings

    图神经网络入门

    • 可以对子图的节点求和
    • 引入“虚拟节点”表示子图

以上内容仅是对图神经网络初步了解的学习,[1]非常适合入门GNN,推荐大家阅读,有问题欢迎交流。

[1] Jure Leskovec, 《Representation Learning on Networks》http://snap.stanford.edu/proj/embeddings-www/


喜欢 (0)