拜读了Jure Leskovec的《Representation Learning on Networks》才明白图神经网络到底在学什么,是如何学的,不同GNN模型之间的关系是什么。总的来说,不同类型的模型都是在探讨如何利用图的节点信息去生成节点(图)的embedding表示。
图表示学习的两大主流思想
- 线性化思想
- Deepwalk,Node2vec,LINE
- 图神经网络
- GCN,GraphSAGE,Gated GNN,subgraph embedding
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 节点
上述方法的大致思想都是:
- 定义节点对的相似性
- 优化embedding去近似它们的相似性
3.Random walk approaches
DeepWalk,Node2vec
Graph neural networks
图G:
- V 顶点集
- A 邻接矩阵
- \(X\in R^{m*|V|}\)为节点特征矩阵
- 文本、图像,例如社交网络中人口学信息
- 节点的度,聚类系数等
如何表示节点
核心思想:根据邻居节点生成节点的embedding
每个节点拥有独立的计算图
how to aggregate information across the layers
最简单的方法就是 求均值
其他方法......
定义loss训练模型
- 无监督
- 有监督
下面不同的GNN算法都是在探索如何利用邻域节点生成当前节点的embedding表示
GNN基础思想
\[\mathbf{h}_{v}^{k}=\sigma\left(\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}=\sigma\left(\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}=\sigma\left(\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}=\sigma\left(\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/