使⽤DGL 实现基于闲鱼图进⾏边分类算法
鼓手英文闲鱼图算法解析和使⽤DGL 进⾏实现
2019年阿⾥闲鱼团队在CIKM 2019上发了⼀篇进⾏Spam评论的检测算法，⽤到了GNN的思想。论⽂显⽰结果⽐较好。但是由于⾸先它们并没有开放数据，且也没开源算法的具体实现⽅法，同时还没有对其中的Attention部分给出具体的公式，所以没法进⾏复现。虽然这篇论⽂拿了CIKM 2019的最佳应⽤研究论⽂，但是这种⽆法复现的论⽂，是否应该给最佳还是要打个问号。
最近由于项⽬，需要使⽤这个算法，便尝试使⽤⽬前⽐较好的GNN实现框架——DGL进⾏了复现。经过两次迭代后，很顺利地完成了其中最核⼼部分公式的实现。这⾥对这次的⼯作进⾏⼀下总结，并形成⼀个使⽤DGL的教程，供⼤家参考。
闲鱼算法的核⼼部分是对于“⽤户”->“评论”->“商品”构建的⼆部图。其基本的数据结构如下图：
在这个图⾥，“⽤户”-通过“评论”-对“商品”-进⾏交互，由此构成了⼀个⼆部图。其中“⽤户”和“商品”是点，⽽“评论”是边。
算法的核⼼任务是对边进⾏分类，即发现那些不正常的评论⾏为。
典型的机器学习⽅法是对评论进⾏特征提取，⽐如text2vec，同时把⽤户和商品的信息也进⾏特征提取。然后合并这三组特征，再送⼊分类器中，⽐如 XGboost等。
但是这种⽅法并没有充分利⽤到边和点之间的关联关系，因此闲鱼团队采⽤了基于GNN的算法，同时另外还加⼊了通过KNN构建的评论之间的相似图，进⼀步加⼊了⼀些信息。这样就利⽤了⽤户、商品、评论和它们之间的关系，理论上采⽤了更多的信息，提升了分类的效果。但是由于论⽂没有数据和实现的细节，所以也没法确切的评估效果到底好不好。后⽂也会讨论⼀下采⽤这个算法碰到的问题。⼀、算法原理这个部分的算法的基本原理就是：通过Attention机制把“⽤户”+“评论”的特征发送给“商品”，并结合“商品”已有的特征，更新“商品”的特征；通过Attention机制把“商品”+“评论”的特征发送给“⽤户”，并结合“⽤户”已有的特征，更新“⽤户”的特征；“⽤户”+“评论”+“商品”特征发给“评论”，并更新“评论”的特征；
最后使⽤“⽤户”“笔记”“评论”作为特征进⾏“评论”的分类。其中，是的意思。
这⾥的Attention的含义是，通过⼀些可学习的权重，来发现那些对于识别有问题的评论更重要的特征，并且通过GNN来把“⽤户”和“商品”的特征⾃动组合给“评论”，从⽽不⽤再去做⼈⼯的特征⼯程。
⼆、具体的公式
根据上⾯介绍的算法原理，这⾥把论⽂⾥的公式梳理⼀下。这并不会按照论⽂⾥的公式顺序来写，但是会给出原⽂⾥的公式编号。⾸先给出GNN的层上的值的定义：
层
层这⾥⾯，指代“评论”所代表的边；指代“⽤户”节点；指代“商品”节点。对应的是每⼀层的特征维度数。
⾸先来写原论⽂⾥的公式(6)，这是对⼀个节点计算它所有的相邻节点和连接的边的隐藏层的值进⾏合并。同样的操作也对节点进⾏，所以有两个。
公式6：把点和边的特征进⾏关于“⽤户”类型的节点：关于“商品”类型的节点：U E I ∣∣∣∣∣∣concatenate L −1L h ∈e l −1
R (1,D )e l −1h ∈e l R (1,D )e l h ∈u l −1
R (1,D )u l −1h ∈u l R (1,D )u l h ∈i l −1R (1,D )i l −1
h ∈i l R (1,D )i l e u i D u i e i concat H =IE l −1
{concat (h ,h ),∀e =i l −1
e l −1(u ,i )∈E (u )}H =UE l −1{concat (h ,h ),∀e =u l −1e l −1(u ,i )∈I (u )}
这⾥计算后得到的的维度是不固定的，因为这⾥是⼀个节点的所有的边的集合，所以是⼀个不定⾏数，但是列数量是固定维度：。同样的情况对于也是⼀样的，的⾏数量不定，列的维度是固定的：。这两个计算出来的矩阵将会被⽤于在公式(7)⾥⾯计算Attension机制。但是这⾥原⽂写的很含糊，它虽然引⽤了⽂献24，但是并没有给出具体的计算⽅法，⽽采⽤基础的加权点积Attention⽅法是不⾏的，所以需要⾃⼰想办法。我这⾥采⽤了⽂献24⾥⾯的思想，给和都进⾏了维度变换。从⽽保证它们的维度⼀致，能进⾏加权点积注意⼒计算。
公式 5和7： 完成Attention的计算
对于“⽤户”类型节点：对于“商品”类型节点：这⾥的两个权重矩阵和就是⽤来进⾏维度变换的⼯具，不然在计算的时候会⽆法完成维度对齐。背后的原因是因为和
需要各⾃和进⾏，他们是相互关联的。除⾮和的维度⼀样，不然不能直接进⾏后续计算。
Attention计算：
原⽂⾥没有对的计算给出具体的计算公式，所以这⾥按照⼀般的注意⼒⽅式进⾏了设计。⾸先，把公式5⾥⾯括号⾥⾯的计算先定义：
， ， 下⾯是计算的4步：
第⼀步： ，。其中，是点积计算。这⾥的点积是⼴播性的计算，所以计算后的和就变成了⼀个⼀⾏列的向量。是⼀个不定的值，是每个节点的边的数量，也就是的⾏数。
第⼆步： ，。
这⾥对第⼀步计算出的每个节点的边的值做计算，归⼀化到之间。
第三步：，。
这⼀步是把上⾯的到的经过后的值再次和⼴播相乘，这⾥的乘不是矩阵乘，⽽是类似Numpy的⼴播乘。完成对原始矩阵加权计算。
第四步：，。最后⼀步就是把第三步计算出的值，按列求和，从⽽在完成Attension的计算后，不定⾏的矩阵就变成了⼀个⼀⾏的向量。
经过后，和运算后得到了⼀⾏的向量，其维度也就是的维度。和运算后得到了⼀⾏的向量，其维度也就是
的维度。最后完成公式5和7⾥的的⾮线性函数，得到和。到这⾥消息传递的⼯作已经完成，下⾯进⼊节点聚合的公式(8)。
公式8
对于“⽤户”类型节点：对于“商品”类型节点：公式3：
计算每个边的 层的值。本质就是把上⼀层的边的值和两端的两个节点的值到⼀起，然后进⾏线性变换，最后进⾏⼀下⾮线性变换。由于是把上⼀层的3个隐藏层的值concat在⼀起，所以权重矩阵的输⼊维度就是：，⽽权重矩阵的输出维度就是：三、⽤DGL 完成模型的构建
现在各种GNN模型层出不穷，但是要实现出这些模型，只⽤TensorFlow或者PyTorch写就很累。秉承着不重复造轮⼦的思想，要实现GNN就需要别⼈写的框架。DGL是⽬前⾮常好的实现GNN的框架。
H IE l −1
D +e l −1D i l −1H U
E l −1H UE l −1D +e l −1D u l −1
orderskey H H =N (u )l σ(W ∗U l ATTN (W ∗U AU l −1h ,W ∗u l −1AIE l −1H ))
IE l −1H =N (i )l σ(W ∗I l ATTN (W ∗I AI l −1h ,W ∗i
enterprisl −1AUE l −1H ))UE l −1W A ∗l −1W A ∗E l −1ATTN ∗u i e concat u i ATTN ATTN =h ^u −1l −1W ∗AU l −1h u l −1=H ^IE l −1W ∗AIE l −1H IE l −1=h ^i −1l −1W ∗AI l −1h i l −1=H ^UE l −1W ∗AUE l −1H UE
l −1ATTN A =attn _u ⊙h ^u −1l −1H ^IE l −1A =attn _i ⊙h ^i −1l −1
H ^UE l −1⊙A attn _u A attn _i x x H ∗E l −1A =attn _u softmax (A )attn _u A =attn _i softmax (A )attn _i attn softmax (0,1)=H ^IE l H ∗IE l −1A attn _u =H ^UE l H ∗UE l −1A attn _i softmax attn H ∗E l −1H ∗E l −1H =IE l sum (,dim =H
nonexclusive
^IE l −1)H =UE l sum (,dim =H ^UE l
−1)ATTN H IE l W U l H N (u )l H UE l W I l H N (I )l σH N (u )l H N (i )l h =u l concat (V ∗U l h ,H )
u l −1N (u )l h =i l concat (V ∗I l h ,H )
i
l −1N (i )l l h e l concat h =e l σ(W ∗E l concat (h ,h ,h ))
e l −1u l −1i l −1h W E l
D _W
E _input =D +e l −1D +u l −1D i l −1D e
l
要实现上⾯的咸鱼算法，就可以使⽤DGL⾥⾯的消息传递+节点聚合、更新功能，特别是DGL已经实现了基于边的softmax功能，这样就可以在实现Attention的时候⾮常⽅便。
下⾯的代码实现会⽤上⾯的插图⾥展⽰的这个⾮常简单的例⼦来演⽰。
3.1 定义Graph
闲鱼的算法针对的是⼀个单向的⼆部图。在DGL⾥，实现这个⼆部图的⽅法很多，下⾯给出⼀个直接的定义⽅法。这⾥需要注意的是，为了计算从“商品”到“⽤户”的消息传递计算，需要多定义⼀种边的类型。
co_g = dgl .bipartite ([(0,0),(1,0),(2,0),(1,1),(1,2),(3,1),(4,1),(4,2)], 'ur', 'comment_on', 'item')
cb_g = dgl .bipartite ([(0,0),(0,1),(0,2),(1,1),(2,1),(1,3),(1,4),(2,4)], 'item', 'commented_by', 'ur')
graph = dgl .hetero_from_relations ([co_g , cb_g ])
3.2 定义模型结构
使⽤DGL构建⼀个GNN模型的⽅法⽐较多，这⾥由于我们需要定制化实现消息传递和聚合，所以需要单独构建GNN的⼀层。
这⾥定义模块的核⼼是确定中间计算过程的维度值。这是整个模型最有奇技淫巧的地⽅。所以要深⼊地讨论⼀下。
1. 注意上⾯的公式5的第⼀步中，需要进⾏内积运算，因此需要内积计算的两边的维度⼀致。
2. 同时和在公式8⾥⾯的维度没有确定，这就需要⾃⼰定，代码⾥采⽤输出维度的⼀半下取整来作为它们的维度。
H N (u )l H )N (i )l
class layer(nn.Module):
"""
This layer is designed specifically for ur Xianyu Graph algorithm.
"""
def__init__(lf, d_u_in, d_u_out, d_e_in, d_e_out, d_i_in, d_i_out):
super(layer, lf).__init__()
lf.act = F.relu
# The Weight in formula (3). U a different way to implement concatinate and linear transform
lf.W_Ee = nn.Linear(d_e_in, d_e_out, bias=Fal)
lf.W_Eu = nn.Linear(d_u_in, d_e_out, bias=Fal)
lf.W_Ei = nn.Linear(d_i_in, d_e_out, bias=Fal)
botfly# weight parameter in formula (7), will do it in two ways, u->i and i->u
# 1. i -> u
lf.d_attn_ie_in = d_e_in + d_i_in
lf.d_attn_u_out = lf.d_attn_ie_in
lf.W_ATTN_ie = nn.Linear(lf.d_attn_ie_in, lf.d_attn_u_out, bias=Fal)
lf.W_ATTN_u = nn.Linear(d_u_in, lf.d_attn_u_out, bias=Fal)
# 2. u -> i
lf.d_attn_ue_in = d_e_in + d_u_in
lf.d_attn_i_out = lf.d_attn_u_out
lf.W_ATTN_ue = nn.Linear(lf.d_attn_ue_in, lf.d_attn_i_out, bias=Fal)
lf.W_ATTN_i = nn.Linear(d_i_in, lf.d_attn_i_out, bias=Fal)
# weight parameter in formula (5)
lf.d_wu_in = lf.d_attn_u_out
lf.d_wu_out =int(d_u_out /2)
lf.W_nu = nn.Linear(lf.d_wu_in, lf.d_wu_out, bias=Fal)
lf.d_wi_in = lf.d_attn_i_out
stamplf.d_wi_out =int(d_i_out /2)
lf.W_ni = nn.Linear(lf.d_wi_in, lf.d_wi_out, bias=Fal)
footmen
# weight parameters in formula (8）
isunlf.d_vu_out = d_u_out - lf.d_wu_out
lf.W_u = nn.Linear(d_u_in, lf.d_vu_out, bias=Fal)
lf.d_vi_out = d_i_out - lf.d_wi_out
母语英语lf.W_i = nn.Linear(d_i_in, lf.d_vi_out, bias=Fal)
四舍五入英文3.3 实现前向计算
模型的定义和forward的实现都在这个layer⾥⾯实现。这⾥forward的输⼊是图的结构graph，以及点和边的特征。
def forward(lf, graph, u_feats, e_feats, i_feats):
"""
Specificlly For this algorithm, feat_dict has 3 types of features:
'Ur': l-1 layer's ur features, in dict {'u': features}
'Edge': l-1 layer's edge features, in dict {'e': features}
'Item': l-1 layer's note features, in dict {'i': features}
This version, we have one edge but two types:
- 'comment_on'
- 'commented_by'
:param graph: bi-partitie
:return:
"""
# assign values
graph.edges['comment_on'].data['e']= e_feats
graph.edges['commented_by'].data['e']= e_feats
# formula 6
graph.apply_edges(lambda edges:{'h_ie': th.cat([edges.src['i'], edges.data['e']], dim=-1)}, etype='commented_by')
graph.apply_edges(lambda edges:{'h_ie': th.cat([edges.src['i'], edges.data['e']], dim=-1)}, etype='commented_by')
graph.apply_edges(lambda edges:{'h_ue': th.cat([edges.src['u'], edges.data['e']], dim=-1)}, etype='comment_on')
# formula 7, lf_attension
graph.edges['commented_by'].data['h_attne']= lf.W_ATTN_ie(graph.edges['commented_by'].data['h_ie'])
graph.edges['comment_on'].data['h_attne']= lf.W_ATTN_ue(graph.edges['comment_on'].data['h_ue'])
# Step 1: dot product
graph.apply_edges(fn.e_dot_v('h_attne','h_attnu','edotv'), etype='commented_by')
graph.apply_edges(fn.e_dot_v('h_attne','h_attni','edotv'), etype='comment_on')
# Step 2. softmax
graph.edges['commented_by'].data['sfm']= edge_softmax(graph['commented_by'], graph.edges['commented_by'].data['edotv']) graph.edges['comment_on'].data['sfm']= edge_softmax(graph['comment_on'], graph.edges['comment_on'].data['edotv'])
# Step 3. Broadcast softmax value to each edge, and then attention is done
graph.apply_edges(lambda edges:{'attn': edges.data['h_attne']* edges.data['sfm'].unsqueeze(dim=0).T},
etype='commented_by')
graph.apply_edges(lambda edges:{'attn': edges.data['h_attne']* edges.data['sfm'].unsqueeze(dim=0).T},
etype='comment_on')
# Step 4. Aggregate attention to dst,ur nodes, so formula 7 is done
graph.update_py_e('attn','m'), fn.sum('m','agg_u'), etype='commented_by')
graph.update_py_e('attn','m'), fn.sum('m','agg_i'), etype='comment_on')
# formula 5
# formula 8
# formula 3 and 4
# first compute 3 matrix multiply
graph.edges['comment_on'].data['h_e']= lf.W_Ee(e_feats)
graph.edges['commented_by'].data['h_e']= lf.W_Ee(e_feats)
# formula 3, add them up
graph.apply_edges(fn.u_add_e('h_u4e','h_e','h_ue'), etype='comment_on')
graph.apply_edges(fn.e_add_v('h_ue','h_i4e','e'), etype='comment_on')
graph.edges['comment_on'].data['e']= lf.act(graph.edges['comment_on'].data['e'])
graph.edges['commented_by'].data['e']= graph.edges['comment_on'].data['e']
u_feats = des['ur'].data['u']
e_feats = graph.edges['comment_on'].data['e']
i_feats = des['item'].data['i']
return u_feats, e_feats, i_feats
上⾯代码⾥⾯出现的edge_softmax函数是DGL的模块，处于pytorch.softmax包内。
3.4 构建整个GNN⽹络
完成了模型的⼀层后，下⾯就可以定义整个GNN的⽹络。这⾥使⽤了2层的架构。
