• 研究动机
• 文章贡献
• 本文方法
  • 整体思想
  • autoencoder
  • 预处理器
  • 深度森林编码生成器
• 实验结果
  • 数据集和实验设置
  • 节点分类
  • 节点聚类
  • 用户推荐
  • 消融实验
  • 调参实验
• 优点和创新点

作者单位：

1. College of Artificial Intelligence Technology, Changchun Institute of Technology, Changchun 130012, China
2. School of Computer Technology and Engineering, Changchun Institute of Technology, Changchun 130012, China
3. School of Chemistry and Life Sciences, Changchun University of Technology, China
4. School of Electronics Engineering and Computer Science, Peking University, China

研究动机

很多现实问题都可以用图数据结构进行形式化，目前的做法是将图数据转化为低维、高密度的 embedding 表示，可以看作是一种深度特征提取学习。虽然基于自编码器(AE)的图嵌入(GE)方法在静态网络应用中性能优异，但它们通常局限于由带有属性和未加权边的节点组成的网络。同时现有的方法很难充分挖掘深度学习的本质优势，大多数方法通常是将节点属性和网络拓扑以统一的表示进行连接，对组合数据进行编码。

文章贡献

本文设计了一种基于深度森林的embedding 学习方法 GraphDF，该方法可以实现以资源为中心的加权属性图的属性和拓扑信息的嵌入。提出的图预处理器包括基于自注意机制的潜在隐含特征挖掘、基于相似性和模块化相关转换对潜在隐含关系特征的深度一般信息挖掘。使编码器所提取的原始特征包含更全面的信息，以用于更广泛和更深的嵌入应用。还引入了一种新的特征提取器和相关的嵌入表示生成器，它利用多粒度扫描和深度级联森林在确保局部收敛的同时全局优化图嵌入表示。该方法避免了过多的约束和偏差，具有较强的泛化和判别能力，通过 7 个数据集实验结果表明 GraphDF 方法优于最先进的嵌入方法。

本文方法

整体思想

为了实现更全面有效的 graph embedding，本文采用了 multi-task 预处理来提取高密度的深度集成特征，实现从原始图数据空间到一阶张量潜在空间的映射机制。具体来说，本文实现了一种基于 deep forest 驱动的 auto-encoder 嵌入生成器，如下图所示。

该模型有几个关键组件：预处理器、auto-coder 和 深度森林编码生成器(deep forest encoding generator)。

同时提出了两层特征级联的思想，实现了特征的高效压缩以及原始特征属性和迭代特征属性的集成优化。初始映射的基本 auto-coder 将节点属性 A 和局部增强拓扑结构 AD 自然地结合到初始映射中，基于 GCN 的基本 auto-coder 可以更好地实现结构信息加权邻接矩阵的融合嵌入。

autoencoder

在将包含原始矩阵和局部增强的块放入其中之前，使用 GCN 作为一阶初始映射的基本 autoencoder。给定图 G 的邻接矩阵 AD，属性矩阵 A，则可以构造模型为：

每个图卷积层表示为：

公式中的符号含义如下表所示：

Decoder 利用深度森林编码生成器最终得到的嵌入对图像进行重构，在给定最终的图嵌入 Z 的情况下，使用全连接神经网络的内积得到重构的图 Gˆ：

使用交叉熵作为损失函数：

预处理器

在以资源为中心的图中，属性矩阵中节点的属性和拓扑的相似性是很重要的，原始信息的 embedding 不能很好地容纳和利用这种信息。为了正确度量每个节点对的相似性，需要集成具有属性相似性的拓扑，使用如下公式计算出每个节点 v_i 的局部邻居集：

公式中的符号含义如下表所示：

使用 TF-IDF 余弦相似度来计算节点的属性相似度，设 X_i 为节点 v_i 的属性向量，则其第 t 个属性 x_it 的 TF-IDF 值 x'_it 如下:

接着计算节点 v_i 与节点 v_j 之间的余弦距离 cos(X'_i, X'_j) 作为属性的相似度。通过引入权重参数，可以计算相似矩阵 Sim 如下:

为了在特征 embedding 中更好地保留和挖掘图的拓扑语义信息，配合相似矩阵对属性信息进行局部增强。引入模块化思想进一步保留网络拓扑信息和结构属性，并将模块化矩阵 MM 作为最终输入模块之一，定义如下:

除了上述图 embedding 的局部相似性和模块化增强之外，还引入了 self-attention 机制进一步提取原始数据矩阵的全局固有性质，构造新的 n∗m' 维模块，如下所示。

公式中的符号含义如下表所示，3 个矩阵都在 0~1 的取值范围以高斯分布随机初始化。

本文的方法是针对以资源为中心的加权图的 embedding 问题设计的，资源的位置信息和序列逻辑很可能对应用场景有用。因此将位置 embedding 集成到自关注模块中，形成最终的 A' 如下公式所示，其中 pos 表示原始位置的编码，I 表示编码顺序以控制奇偶编码公式的切换。

在 AD 的基础上，通过 self-attention 机制和位置 embedding 得到新的 AD' 模块。预处理器算法的伪代码如下所示。

深度森林编码生成器

A、AD'、A'、A_ξ、AD_λ 由 AD 输入基本 autoencoder 进行初始映射，生成对应的原始向量，将所有的 5 个向量串联成维度大小为 μ 的长向量 η 作为深度森林编码生成器的输入数据，如下公式所示。

E_DFEG 设置两个扫描窗口 W1 和 W2，W1 设为 [(0.1μ)±1]，W2 设为 (0.3μ±1)。以扫描窗口 W1 为例，E_DFEG 通过完全随机森林 A1 和随机森林 A2 分别产生 S 个 ψ_W1 维的特征实例，将这 2S 个实例串接成一个 2Sψ_W1维的特征向量，该特征向量与 W2 中的 2Sψ_W2 维特征向量一起作为G_DFEG 的输入。
在 G_DFEG 的多粒度级联森林中，每层级联森林由 4 个森林组成，其中 2 个是完全随机森林，另外 2 个是随机森林，每个单独的森林由多棵决策树组成.每个节点根据所选择的特征 f 对接收到的数据进行分割，并进行分割运算得到 R ^* 。父节点的数据被分为两个子集 R1 和 R2，然后在所选特征空间中随机取 i 个特征作为候选分割属性 Γ ^* 的集合。取候选数为 c ={√r, 1}，其中 c=1 对应于完全随机树。一层级联森林完成训练后，将当前层所有森林的决策结果组合起来，得到一个 4Ψ 维特征向量F'=(F ^* ₁,F ^* ₂,F ^* ₃,F ^* ₄) 作为本层的输出。
将该层的输出特征作为增强特征，与多粒度特征集中下一层粒度的特征向量合并，得到增强的训练样本集。重复训练过程 M 次，生成最终嵌入结果 Z=F^fin=(F ^* _1fin,F ^* _2fin,F ^* _3fin,F ^* _4fin)。
GraphDF 算法的伪代码如下，考虑到随机森林中矩阵计算和决策树计算的并行性，总时间复杂度为 O(T·M³+n²+ T·L/Max{W1,W2})，其中 n 为节点数、L 为 η 的维数，T 为随机森林中的树数。

实验结果

数据集和实验设置

实验使用了7 个具有不同样本数量和特征的公开数据集，两种网页网络图(Cornell、Texas、Washington、Wisconsin)和文档网络图(Citeseer, Cora、Pubmed)数据集信息如下表所示。

将 GraphDF 方法与 12 种 embedding 方法进行了比较，分别是使用图拓扑的方法：DeepWalk、LINE、GraRep、Node2Vec，和同时使用语义和拓扑信息的方法：TriDNR、VGAE、AANE、SNE、ARVGE、WMCNE-LE、DGI 和 AMIL。节点分类任务使用准确率(AC)作为性能指标，节点聚类任务还使用归一化互信息 NMI 作为额外的指标，用户推荐任务同时使用 AC 和 recall 进行性能评估。
所有数据集和所有提到的方法生成的 embedding 向量的维度设置为 64，比较方法的参数均按原作者的方法设置。GraphDF 使用经典的两层 GCN 作为初始 Encoder，第一层包含 128 个单元，第二层包含 64 个单元。Decoder 采用 3 层全连接神经网络，前两层包含 512 个单元，最后一层包含 1 个单元，前两层的激活函数是 ReLU(·)，最后一层的 Sigmoid(·)。这些模型使用 pytorch 实现，学习率设置为 0.001。

节点分类

节点分类任务是将每个节点分类到一个标签作为目标，进行图嵌入之后使用 LibSVM 和 LibLINEAR 对节点进行分类，每个数据集都运行十折交叉验证。实验的结果如下表所示，可见 GraphDF 在 LibSVM 和 LibLINEAR 上的结果都优于其他方法。

节点聚类

节点聚类的目标是位每个节点分配一个不同的聚类，进行嵌入之后使用 k-means 实现。结果如下表所示，可见 GraphDF 整体上优于其他方法。

用户推荐

此处比较了 GraphDF 和基线方法在用户推荐中应用嵌入的效果，使用 LASTFM 数据集，它包含来自在线音乐系统的 1892 名用户和 17632 名艺术家。80% 的用户-艺术家关系构成训练数据，剩下的 20% 作为测试数据集，推荐艺人列表 Ru 通过基本协同过滤算法得到。实验结果如下图所示，GraphDF 方法在准确率和召回率方面都优于这些基线方法。

消融实验

此处验证本文的设置是否优于没有双滑动窗口和级联森林的简单生成器，具有单窗口和单层森林的方法称为 GraphDFNDNC。同样，AC和NMI仍然被选择作为绩效指标。实验结果如下表所示，可见本文的设置性能较优。

调参实验

此处验证嵌入维数对模型性能的影响，选择 16、32、64、128 作为测试维数。实验结果如下图所示，可见 GraphDF 在改变图嵌入维度方面的性能是相对稳定的。

优点和创新点

个人认为，本文有如下一些优点和创新点可供参考学习：

1. 本文基于深度森林模型对图嵌入问题进行了一种实现，将最后一层输出的增强向量作为嵌入向量输出，具有一定的新意；
2. 提出的预处理器包含语义、拓扑、高阶信息等多种信息，并与 GCN 的原始属性矩阵和邻接矩阵相结合，能保证得到的 embedding 向量包含结构语义和深度属性。