abstract

在大规模数据上使用GCN做数据挖掘

introduction

• a random-walk-based GCN–PinSage 处理 3 billion nodes and 18 billion edges的图
• 为了在大规模图上运行，使用了On-the-fly convolutions；Producer-consumer minibatch construction； Efficient MapReduce inference
• 同时，使用的减少网络的复杂度的方法：Constructing convolutions via random walks；Importance pooling
• 使用Curriculumtraining来学习

related work

method

GCN的方法：一个节点可以形成一个local network，对很多个节点的local network进行GCN，这样，GCN网络的权重被每个network共享。

problem setup

• 将Pinterest上的pin和board组成二分图
• pin可以看成item，board可以看成用户定义的contexts 或 collections。同时pin/item有information，有text和image features。
• embedding item 考虑了item的information，也就是text和image，同时也考虑了网络的结构
• 目的是为了embedding pin也就是item，来通过相似的item推荐（nearest neighbor lookup，given a pin, find related pins），或者是来ranking这些item。

model architecture

localized convolution operation：首先输入node feature，然后学习NN，来transform和aggregate图的feature，从而得到node的embedding。

Forward propagation algorithm

这个算法是整个图的圈出来的部分：

Importance-based neighborhoods

如何确定用户的邻居？
之前的GCN中是通过k-hot，
本片论文使用random work找到top T nodes
这里的方法是参考了一篇论文。

Stacking convolutions

在算法1 中使用层叠，也就是当前的点的表达用之前得到的表达，也就是点u的邻居节点不再使用初始值，而是使用通过那个邻居节点的邻居节点得到的向量来进行输入。也就是下图红色方框圈出的部分：

Note that the model parameters in Algorithm 1 (Q, q, W, and w) are shared across the nodes but differ between layers.
注意，其中的参数是在同层的点中share的，不同层不share。
也就是我们要学习的参数有：
(Q(k),q(k),W(k),w(k),∀k ∈ {1,…,K}) k表示第k层。

model training

• 目标函数max-margin ranking loss，其实就是hinge loss（svm的loss）
• 建立一个set L 里面是pair（q，i），q和i是相关的，使i被更好的推荐给query item q。也就是使用网络embedding出的q和i的向量要比较相似。

loss function：

解释一下变种的hinge loss：
l(y,y′)=max(0,m−y+y′)
其中，y是正样本的得分，y’是负样本的得分，m是margin（自己选一个数）
即我们希望正样本分数越高越好，负样本分数越低越好，但二者得分之差最多到m就足够了，差距增大并不会有任何奖励。
我们可以看到，如果证样本的得分较大，副样本的得分较小，在max后，得到0，相反得到m−y+y′，因为m−y+y′>0，并且要min loss，所以在两个得分相差不大或者负样本得分高的时候进行更新。

Multi-GPU training with large minibatches

Producer-consumer minibatch construction.

Sampling negative items

Node Embeddings via MapReduce

以上这些就不再写了，可以看论文，都是描述性的话，总体就是如何快速计算大数据。

总结

我觉得这个论文的方法和我之前做推荐系统的时候用的random work+skip gram 很像。。。