Page 91 - 《软件学报》2021年第12期

肖勇 等:基于 GAT2VEC 的 Web 服务分类方法 3755

游走中的属性顶点.因此,游走只包含 V a 的顶点.属性相似性较高的顶点组在随机游走中可能经常出现在一起.
类似于 G s ,我们执行γ a 次长度为λ a 的随机游走并构造一个语料库 W,w j 是指随机游走序列 w∈W 中的第 j 个顶点.
例如,图 4 中具有属性的随机游走路径可以是:[2,b,1,c,8,b,2,b,8].我们在路径中跳过属性节点,因此,相应的路径
是 w=[2,1,8,2,8],步长为 5,从顶点 2 开始,以顶点 8 结束.
1.3 表征学习

在得到结构和属性上下文以后,我们使用 SkipGram 模型共同学习基于这两个上下文的嵌入.具体来说,我
们从每个结构或属性上下文中选择顶点 v x ∈V s |V a ,并将其输入到 SkipGram.输入顶点 v x 是一个独热编码向量
{0,1} | s V ∪ V a | ,同时也是目标顶点,输出层产生关联上下文顶点到给定输入顶点的 2c 多项式分布.c 是上下文大小,
即在目标顶点之前或之后的预测顶点的数量.同样,输出顶点可以属于结构顶点,也可以属于属性顶点,这取决
于它们在随机游走中的共现性.
GWSC 方法的最终目的是,能够最大化目标顶点的结构和属性上下文概率.与以往的研究 [8,9] 类似,我们假
定当给定一个目标顶点时,其上下文顶点的概率彼此独立.因此,我们的目标函数定义如下:
||r | |w
|
L = log (pr − c : r c | )r + ∑∑ i ∑ ∑ log (p w − c : w w i ) (1)
c
∈
rR i= ∈ 1 w W i= 1
等式(1)可以写成:
||r | |w
L = log ( | ) + ∑∑ ∑ pr r i ∑ ∑ ∑ log (p w w i ) (2)
|
j
t
≤ ≤c
j
∈ r =R 1 − i c ≤≤c ∈ w W = 1 − i c t
≠ t i
≠ ji
其中,r −c :r c 和 w −c :w c 分别对应于 R 和 W 语料库中随机游走长度为 2c 的上下文窗口内的一系列顶点.公式的前
半部分使用结构上下文进行学习,后半部分从属性上下文中进行学习.如果|V a |=0,那么模型将变成 Deepwalk,也
就是说,只从结构中学习.当 r i 是结构上下文 r 中的中心顶点时,p(r j |r i )是第 j 个顶点的概率;而当 w i 是属性上下
文 w 中的中心顶点时,p(w t |w i )是第 t 个顶点的概率,这些概率可以用 softmax 函数来计算.概率 p(r j |r i )可计算为
exp( ( )rϕ T φ ( ))r
(| )r =
pr j i j i (3)
∑ s v ∈ s V exp( ( )v s T φ ( ))r i
ϕ
其中,ϕ(⋅),φ(⋅)分别表示上下文顶点或目标顶点.同样的,也可以用等式(3)计算 p(w t |w i ).
由于需要对图的所有顶点进行归一化处理,使得计算量很大.因此,我们用分层的 softmax 函数 [16] 来进行计
算.在这之后,使用 Huffman 编码来构造具有顶点作为叶节点的层次 softmax 的二叉树 [17] .因此,为了计算概率,
我们只需遵循从根节点到叶节点的路径.所以,叶节点 r j 出现在结构上下文中的概率是:
d
(| )r = ∏
pr j i ( p s h | ( ))rφ i (4)
h= 1
其中,d=log|V s |是树的深度,s h 是路径中的节点,s o 为根节点,且 s d =r j .此外,将 p(r j |r i )建模为二进制分类器,可以使计
算复杂度降至 O(log|V s |).这同样适用于计算属性上下文中顶点的概率.而考虑到我们是从两个上下文中计算概
率的,所以我们的整体计算复杂度应该是 O(log|V s |+log|V a |).
1.4 SVM分类
在得到了表征向量以后,我们需要将表征向量输入到分类器中进行训练.解决分类问题的方法有很多,主要
包括决策树、贝叶斯、K-近邻、人工神经网络、支持向量机(SVM)等.对于决策树,数据的准备往往是简单的,
且易于通过静态测试来对模型进行评测,但对于那些各类别样本数量不一致的数据,信息增益的结果往往偏向
于那些具有更多数值的特征.而贝叶斯所需估计的参数很少,对缺失数据不太敏感,算法也比较简单,但需要知
道先验概率,且分类决策存在错误率.K-近邻算法简单有效,重新训练的代价也较低,但该算法在分类时有个很
明显的缺点是:当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个
新样本时,该样本的 K 个邻居中大容量类的样本占多数.人工神经网络分类的准确度往往较高,并行分布处理能
力较强,但通常应用于大规模数据集,且需要大量的参数,如网络拓扑结构、权值和阈值的初始值,学习时间较长,