论文：BiANE: Bipartite Attributed Network Embedding (SIGIR-2020)
作者： Wentao Huang, Yuchen Li, Yuan Fang, Ju Fan, Hongxia Yang
新零售智能引擎事业群出品
前言
网络数据是一种常见的数据表示形式，可以用来建模现实世界中的多种应用场景。网络表示学习（又称作图嵌入学习），作为一种建模网络数据的模型，近年来受到学界和工业界的广泛重视，得到了极大发展。网络表示学习旨在把复杂的网络图数据结构嵌入到低维的连续向量空间中，并且使每一个节点的特征信息在低维空间中得到反馈。近年来，大量的网络表示学习方法和模型被不断提出并且在链路预测、节点分类、网络可视化等相关的实际任务上有很好的表现指标。
然而，大部分的网络表示学习模型都是针对同构网络、异构网络或属性网络提出的，没有专门针对属性二部图提出的网络表示学习模型。属性二部图是一种特殊的网络结构，可以用来建模多种现实运用场景。以上图所示的电商消费为例，图上的节点分为两种类型（用户、商品），每个节点附带有一些描述的属性信息。图上仅存在一种类型的边，分别连接着两种不同类型的端点，表示节点之间的交互关系（购买）。
该文针对目前研究相对欠缺的属性二部图，提出了一种新的表示学习模型BiANE（Bipartite Attributed Network Embedding）。BiANE可以对属性二部图上的组间信息关联度和组内信息关联度进行建模，并且有效捕获属性信息和结构信息之间的关联性。此外，BiANE引入了一个动态正例采样过程，在保证模型可扩展性的同时，实时更新节点在表示学习空间中的采样分布，增强BiANE的学习效果。
相关研究及其不足
网络表示学习
网络表示学习的相关技术在近些年来受到了各行各业的大量关注，许多模型被相继提出。DeepWalk、node2vec、metapath2vec等方法借鉴了Skip-gram的思想学习节点表示向量，GCN等则借用图卷积操作学习节点的向量表示。 然而这些方法，或是无法建模属性二部图的组内信息关联度，或是无法捕获属性信息和结构信息之间的关联性，故不能在属性二部图上获得较好的表示学习效果。
二部图的建模研究
现有的工作对二部图的研究多侧重于推荐排序或点击率预估，如BPR、RankALS、DeepFM等等。这些方法的输出往往是一个标量分值，不具备表示向量那样的丰富表达能力。近年来提出的BiNE是第一个针对二部图表示学习的模型，然而它无法对属性、结构信息关联性建模，因而不适用与属性二部图的表示学习。
负例采样策略
网络表示学习需要采样一定的负例进行训练。负例采样策略可分为静态策略或动态策略。静态策略采用预定义的采样分布，无法反映出训练过程中节点在向量空间中的信息变化过程。动态策略虽能实时更新采样分布，但其计算复杂度过大，制约模型的可扩展性。
BiANE模型介绍
针对上述相关研究的缺陷，该文提出了一个新的表示学习模型BiANE。BiANE模型的训练过程大致可分为组内信息关联度建模和组间信息关联度建模两个部分。BiANE首先对组内信息关联度进行建模。BiANE根据节点所属的不同类型对节点进行分组，若组内两个节点连着另一个组内的同一个节点，则称它们彼此为intra-partition neighbors，根据这种“邻居”关系，可在组内构建intra-partition network。
在每个组内，BiANE分别提取节点的属性信息和结构信息。在属性信息提取上，分别对连续型属性和离散型属性采取归一化和one-hot处理，并把所有处理后的值进行拼接。在结构信息提取上，则通过下式得到节点高阶结构特征。
对于提取到的属性特征和结构特征，分别引入两个自编码器，通过优化自编码器损失函数学习得到关于属性、结构信息的表示向量。
同时，BiANE对每个组内的intra-partition neighbors之间的一阶拓补结构进行建模，若两个节点互为“邻居”，则分别优化它们之间属性、结构向量的联合概率，使有关向量在表示空间中的位置逐渐接近。
接着，BiANE对属性信息和结构信息之间的关联性进行建模。对图上任意节点，它的属性信息和结构信息既彼此互补，又潜在一致，这种关系被称作属性信息和结构信息之间的关联性。BiANE引入两个额外的转换核，将编码器学到的属性向量和结构向量投影到一个潜在的向量空间中，并在该空间内，优化相同节点属性向量和结构向量的联合概率，以捕获属性、结构信息之间的关联性。
在上述训练过程中，有关损失函数皆使用预定义的静态负例采样进行训练，然而该分布不能在训练过程中动态更新，无法反映节点在向量空间中的信息变化过程。而动态更新采样分布的时间开销过大，容易制约模型的可扩展性。因此，BiANE引入了一种动态正例采样策略增强模型的训练效果。BiANE在转化核输出的向量空间中构建关于每一个节点向量的最近邻搜索的索引结构，并返回关于每个向量的k个最近邻。所返回的k的最近邻作为节点在向量空间中的训练“正例”。这些“正例”向量在表示空间中的位置被互相推近。同时由于结合了传统的负例的静态负例采样策略，“无关”的节点向量在空间中的位置被相互推远。两种采样策略相结合，得到一个动态更新的采样分布
为了保证模型的可扩展性，BiANE在最近邻检索过程中采用了HNSW数据结构。HNSW在低维空间上能保证较低的时间复杂度（O(n logn)），故限制引入的转化核将向量转化至低维空间上（如：16、32维），以保证时间复杂度。引入动态正例采样后的损失函数如下，其中p ̃为基于HNSW的动态正例采样分布。
之后，BiANE对属性二部图组间信息关联度进行建模。在每个组内，将属性自编码器和结构自编码器的编码器输出向量进行拼接得到节点的最终向量表示。然后根据属性二部图上存在的边，优化不同组内的节点之间的组间信息关联度：
最后，BiANE将所有训练损失函数结合，通过联合训练的形式优化模型，得到最终的节点表示向量。
实验
该文在三个数据集上进行有关实验，数据集的有关统计信息如下表所示：
首先，进行了链路预测的实验，结果如下表示：
观察发现，BiANE模型在三个数据集上取得了较好的表现。结合一些对比方法可以发现，对组内信息关联度进行建模可以有效增强模型的学习效果。
其次是关于节点分类的实验，有关实验结果如下所示：
观察发现，对属性信息的提取能够显著增强表示学习模型的在节点分类任务上的表现。同时，由于BiANE模型能够有效对属性、结构信息关联性进行建模，所以再次取得了最优的分类指标。
接下来，是关于BiANE的模型消融分析实验。在这里实验设置了若干对照模型，通过链路预测和节点分类两个任务，分别对BiANE模型的属性信息建模、结构信息建模、属性信息结构信息关联性以及动态正例采样策略的进行消融分析。实验结果如下所示：
观察发现，对属性信息和结构信息的关联性建模能够有效融合节点的属性特征和结构特征，加强学习向量的表达能力。同时，由于动态正例采样策略引入可以实时更新、改善训练过程中模型的采样分布，使模型的学习效果得到进一步增强。
最后，是关于模型效率的分析，在此选用基于Softmax函数的重要性采样分布进行效率对比，分别统计基于HNSW采样和重要性采样完成一轮采样所需要的时间，结果如下图所示：
观察发现，基于HNSW的动态采样策略在效率上显著优于重要性采样策略，且在低维空间（16维）中的时间优势更加明显，也证明了引入使向量降维的转化核可以有效降低训练的时间复杂度，保证模型的可扩展性。
结语
该文提出了一种针对属性二部图的网络表示学习模型BiANE，能够分别对属性二部图的组内信息关联度和组间信息关联度进行建模。同时，BiANE引入关于属性、结构信息之间关联性训练环节，加强对属性信息和结构信息建模的效果。此外，BiANE在传统的静态负例采样策略基础上，设置了一个动态正例采样策略，实时更新训练过程中的采样分布。相关实验表明，BiANE模型能够有效适用于属性二部图的表示学习任务，并具备一定的可扩展性。
更多信息检索技术内容请查看：独家下载！《SIGIR 顶会论文解读》电子书重磅发布