基于集合约束的异质超网络表示学习

刘贞国，朱 宇，王晓英，黄建强，曹腾飞

（青海大学 计算机技术与应用系，西宁 810000）

0 概述

网络表示学习［1］也称为网络嵌入，其将网络中的每个节点映射到一个低维的向量表示空间，学习到的节点表示向量可以被用于节点分类［2-4］、链接预测［5-7］、社区检测［8-9］等网络分析任务。

现有的网络表示学习方法大多针对普通网络，其中，节点之间的关系是成对关系，即每条边只连接一对节点，而在现实生活中的数据对象之间的关系通常比较复杂，而且不一定是成对关系。例如，吉姆参加了一场在北京举行的学术会议，就形成了一种元组关系<吉姆，北京，会议>。捕获这种元组关系的网络通常称为超网络，其中，元组关系被看作超边。与普通网络相比，超网络逐渐变得更受欢迎，如何从超网络结构中挖掘有用信息变得十分有意义。然而，现有的大多数网络表示学习方法不能直接应用于超网络。鉴于上述事实，团扩展、星型扩展［10］和BTR［11］将超边分解为对边，然后学习节点表示，但是该类方法在超网络展开过程中会丢失超边信息。Hyper2vec［12］、HPSG［13］没有分解超边，而是基于超路径游走序列来捕获节点之间的成对关系，但是它们没有很好地捕获节点之间的元组关系。HPHG［13］和DHNE［14］可以很好地捕获节点之间的成对关系和元组关系，但是它们受限于固定大小和固定类型的异质超边。Hyper-SAGNN［15］相比于DHNE 和HPHG具有更好的泛化性，对输入元组的节点数目大小和类型没有要求，但是由于该方法构造了很多中间特征，其模型计算复杂度较高。

受到上述方法的启发，将结构复杂的超网络转化为结构简单的普通网络，以便于使用普通网络表示方法学习节点表示向量，同时考虑节点之间的成对关系和元组关系。本文提出一种基于集合约束的异质超网络表示学习方法HRSC。该方法通过结合团扩展和星型扩展策略将异质超网络转化为异质网络［16］，采用感知节点语义相关性的元路径游走算法来捕获异质节点之间的语义信息，并根据集合约束机制，在基于拓扑派生目标函数的模型上融入超边。

1 相关工作

超网络作为一种特殊的图结构化数据，逐渐受到研究者的广泛研究。团扩展、星型扩展［10］和BTR［11］是超网络学习的传统主流方法，它们将谱理论应用到超网络中，通过严密的数理推导来求解目标函数的最优解，其中，团扩展使得超边内部节点连接成完全图，即使得超边内部节点之间两两相连。星型扩展通过引入超边节点，使得超边内部节点与超边节点相连。BTR 使用超边内部距离最远的两个节点的连接边代替超边本身，大幅降低了展开过程的时间复杂度，但是当其应用于节点差异度较大的超网络时会丢失较多的结构信息。Hyper2vec［12］在拉普拉斯算子上加入导向函数，提出基于超边的有偏随机游走，使其能够适应不同的网络结构，从而更好地保留超网络结构信息。HPSG［13］基于超边的随机游走来构造节点的异质邻域，然后通过Skip-gram模型学习节点表示向量。DHNE［14］直接对超边进行建模，但该方法局限于固定大小的异质超边。HPHG［13］基于超边的随机游走节点序列上训练Hyper-gram 模型，更好地保留了超网络结构，实现了优于DHNE 的性能，但是其只适用于均匀超网络，很难扩展到任意规模的超网络。Hyper-SAGNN［15］使用自注意力机制对超图信息进行聚合，结合节点动态特征和静态特征对节点进行学习，对输入元组的节点类型、数目没有要求，相比DHNE 和HPHG 具有更好的泛化性，但由于该方法构造了很多中间特征，其模型计算复杂度较高。Event2vec［17］将多个对象之间关系建模为事件，通过在嵌入空间中保留事件一阶和二阶近似性学习节点表示向量。

与上述方法不同，HRSC 不仅可以捕获节点之间的成对关系和元组关系，而且可以平衡优化节点之间的成对关系和元组关系，以便于获得高质量的节点表示向量。在3 个不同类型的超网络数据集上的实验结果表明，HRSC 方法在链接预测和超网络重建任务中表现优异。

2 问题定义

超网络通常被抽象为超图H=(V,E)，其中，V=是T种类型的节点集合，Vt表示第t种类型的节点集合是超边集合。如果对于任意ei∊E均有|ei|=k，则称H为k-均匀超图；如果k=2，则超网络退化为传统网络；如果T≥2，则超网络定义为异质超网络。如图1 所示，给定一个异质超图H=(V,E)，其中，E={e1={a1,b1,c1},e2={a2,b2,c2},e3={a1,b1,c2}}，V={a1,b1,c1,a2,b2,c2}，a、b、c表示节点的类型。

图1 异质超图Fig.1 Heterogeneous hypergraph

定义1（异质超网络表示学习）给定一个异质超网络H=(V,E)。异质超网络表示学习为每个节点vi∊V学习一个低维向量rvi∊Rk，其中，k≪|V|。它的目的是使得学习到的向量显式地保留异质超网络结构信息，并且异质超网络结构中相邻的节点在向量表示空间中也相邻。

3 预备知识

文献［18］提出分别通过团扩展和星型扩展将超图转化为2-截图和关联图。受文献［18］的启发，文献［19］提出将超图转换为2-截图+关联图和感知节点语义相关性的元路径游走方法。下面详细介绍超图转换为2-截图、关联图、2-截图+关联图和感知节点语义相关性的元路径游走。

3.1 超图转换为2-截图、关联图与2-截图+关联图的方法

超图转换为2-截图、关联图与2-截图+关联图方法如下：

1）2-截图

超图H=(V,E)的2-截图（2-section graph）是满足以下条件的图S=(V',E')：

（1）V'=V，即S的节点 集合与H的节点集合相同。

（2）任意两个不同的节点之间连一条边，当且仅当它们同时与H的至少一条超边关联。

图2 是图1 超图对应的2-截图。

图2 2-截图Fig.2 2-section graph

2）关联图

超图H=(V,E)的关联图是满足以下条件的图I=(V',E')：

（1）V'=V∪E，即将超图H中的每条超边看成一个节点，I的节点集合是H的节点集合和超边集合的并集。

（2）vi∊V和ei∊E相邻，当且仅当vi∊ei。

图3 为图1 超图对应的关联图，其中e节点代表超边节点。

图3 关联图Fig.3 Incidence graph

3）2-截图+关联图

超图H=(V,E)的2-截图+关联图是满足以下条件的图I=(V',E')：

（1）V'=V∪E，即将超图H中的每条超边看成一个节点，I的节点集合是H的节点集合和超边集合的并集。

（2）对于vi∊V和ei∊E，当且仅当vi∊ei时，vi与ei相邻；对于∀vi,vj∊ei，当且仅当vi和vj节点之间语义相关，vi和vj相邻。

图4 为图1 超图对应的关联图，其中，b1和c1、b1和c2、b2和c2节点之间语义相关。

图4 2-截图+关联图Fig.4 2-section graph+incidence graph

3.2 感知节点语义相关性的元路径游走

在2-截图+关联图G=(V,E)上的感知节点语义相关性的元路径游走定义如下：

其中：Ri表示Vi和Vi+1类型节点之间存在语义相关；Re表示Vj和Vj+1类型节点之间通过超边节点关联；R=R1◦∙∙∙◦Ri◦∙∙∙◦Re◦∙∙∙◦Rl-1表 示V1和Vl类型节点之间的复合关系。与传统随机游走相比，采用感知节点语义相关性的元路径游走获取的异质节点序列，可以更好地保留超网络中节点之间的元组关系和增强节点之间的成对关系。

4 HRSC 方法

HRSC 方法的框架如图5 所示。该框架包括2 个主要部分：（a）基于拓扑派生目标函数的模型；（b）基于集合约束目标函数的模型。其中，Ev和θv分别表示嵌入矩阵和参数向量，ev和ew分别为v和w对应的向量，v和w分别表示目标节点和与目标节点关联的超边。

图5 HRSC 框架Fig.5 HRSC framework

4.1 拓扑派生目标函数

采用基于感知节点语义相关性游走来获取的异质节点序列C作为HRSC 方法的输入，通过基于拓扑派生目标函数的模型来捕获序列C上节点之间的成对关系。下面详细介绍拓扑派生目标函数。

对于目标节点v∊C，当v的上下文节点为c∊context(v)时，将c视为正样本，将非上下文节点Neg(v)视为负样本。节点的标签定义如下：

p(u|v)表示在已知目标节点v的条件下预测其上下文节点u概率。对于给定节点序列C，最大化拓扑派生目标函数如下：

对于每一个节点v，嵌入向量ev是v作为目标节点的表示向量，参数向量θv是v作为上下文节点时的表示向量，则p(u|v)定义如下：

通过最大化L1将超网络拓扑结构融入到超网络表示学习中来捕获节点之间的成对关系。

4.2 集合约束目标函数

上述基于拓扑派生目标函数的模型仅采用近似于超图的2-截图+关联图作为输入来学习节点表示向量，没有充分地捕获节点之间的元组关系，即超边。为了更好地捕获节点之间的元组关系，提出一种基于集合约束目标函数的模型，该模型将与节点关联的超边集合融入到超网络表示学习中。下面详细介绍集合约束目标函数。

对于目标节点v∊C，w表示与目标节点关联的超边，Tv表示与目标节点关联的超边集合，如果将w看作节点，Tv也表示与目标节点v相关联的节点集合。将目标节点v视为正样本，对于w∊Tv，NEG(w)表示目标节点v的负样本子集。节点标签定义如下：

对于目标节点v，通过集合约束机制，将与节点相关联的超边集合作为约束条件融入到节点的表示学习过程中。集合约束目标函数的计算公式如下：

通过最大化L2，将与节点相关联的超边集合融入到超网络表示学习过程中来捕获节点之间的元组关系。

4.3 联合优化目标函数

通过联合优化拓扑派生目标函数和集合约束目标函数，可以同时捕获节点之间的成对关系和元组关系。与其他超网络表示学习方法相比，HRSC 在2 个层次上进行了改进：1）在超网络拓扑结构层次上，HRSC 捕获了节点之间的成对关系；2）在节点-超边层次上，HRSC 捕获了节点之间的元组关系。通过上述改进，HRSC 有效地融合超边到超网络表示学习中。

为了便于计算，将拓扑派生函数L1和集合约束L2取对数后相加，并最大化联合优化目标函数如下：

其中：β是平衡基于拓扑派生目标函数的模型和基于集合约束目标函数的模型的调和因子。为了便于推导，将L简记为L(v,u,δ,w)，即：

通过使用随机梯度上升（SGA）算法来优化目标函数L(v,u,δ,w)，给出L(v,u,δ,w)的4 种梯度。

首先，关于θu的梯度计算如下：

其中，λ是HRSC 方法的学习率；当L(u)=1 和L(u)=0时，分别更新正负样本节点的参数向量。

其次，利用ev和θu的对称性计算L(v,u,δ,w)关于ev的梯度如下：

因此，对θδ的更新公式如式（15）所示，当L(δ|v)=1 或L(δ|v)=0 时，分别更新正负样本节点的参数向量。

最后，利用ew和θδ的对称性计算L(v,u,δ,w)关于ew的梯度如下：

根据上述分析，HRSC 方法的具体描述如算法1所示。

算法1HRSC algorithm

4.4 复杂度分析

在算法1 中，基于拓扑派生目标函数的模型和基于集合约束目标函数的模型分别捕获了节点之间的成对关系和元组关系，其时间复杂度如下：O(C∙(context ∙ (Neg+1)+∙ (NEG+1))∙2d∙(|V|+|E|))，其中表示与v关联的超边集合的最大基数；Neg和NEG 分别表示拓扑派生目标函数和集合约束目标函数的负采样样本大小。由于|V|和|E|通常较大，因此HRSC 的时间复杂度大约为O(|V|+|E|)，接近于HPHG 和Event2vec 的时间 复杂度，高 于DHNE 的 时间复杂度。

5 实验

5.1 数据集

为了全面评估本文提出方法的效果，本文使用3 个超网络数据集，即药物网络、GPS 网络和社会网络。数据集的详细统计如表1 所示。

表1 数据集统计Table 1 Dataset statistics

1）drug：该数据集来自FDA 不良事件报告系统（FAERS），包括提交给FDA 的不良事件和用药错误报告的信息。元组关系（用户，药物，反应）被看作超边来构建超网络。

2）GPS［20］：该数据集描述了一个用户在某个位置参加活动。元组关系（用户，位置，活动）被看作超边来构建超网络。

3）MovieLens［21］：该数据 集描述 了来自 于MovieLens 的个人标记活动。元组关系（用户，电影，标签）被看作超边来构建超网络。

5.2 基线方法

基线方法主要有以下8 种：

1）deepwalk［22］将随机游走获取的节点序列作为Skip-gram 模型的输入来获得节点表示向量。

2）node2vec［23］采用有偏随机游走策略学习节点表示向量。

3）metapath2vec［24］采用基于元路径的随机游走策略学习节点表示向量。

4）Coarsas2hvec［25］通过HIN 粗化和自避免短序列采样过程捕获异质网络的丰富的信息，从而学习节点表示向量。

5）Hyper2vec［12］采用基于超边的二阶随机游走策略学习节点表示向量。

6）HPSG［13］基于超路径的随机游走结合Skipgram 模型学习节点表示向量。

7）HPHG［13］基于超路径的随机游走结合Hypergram 模型学习节点表示向量。

8）Event2vec［17］通过学习事件嵌入来学习对象嵌入。

HRSC 方法基于2-截图+关联图来捕获节点之间的成对关系和元组关系来学习节点表示向量。

5.3 链接预测

本节在3 个超网络数据集上进行链接预测实验，通过AUC［26］值来评估HRSC 方法。实验随机选取80%的边集作为训练集，对于全部方法，取6 次AUC 平均值。以drug 数据集为例，HRSC 方法对于2-截图、关联图分别采用方案φ1、φ2进行采样，对于2-截图+关联图采用感知节点语义相关性的元路径游走方案φ3进行采样［19］。链接预测结果如表2 所示。

表2 链接预测结果Table 2 Link prediction results %

由表2 可知，HRSC 方法在2-截图、关联图、2-截图+关联图上的AUC 值优于deepwalk、node2vec、metapath2vec、Coarsas2hvec 普通网络学习方法。HRSC 方法在drug 和GPS 超网络上的AUC 值优于超网络表示学习方法Hyper2vec 和HPSG。原因是这两个超网络的内部节点之间的元组关系较强，因此特定地训练节点之间成对关系的方法Hyper2vec和HPSG 表现不佳。HRSC 方法在MovieLens 超网络上的AUC 值优于HPHG 和Event2vec，在drug 和GPS 超网络上的AUC 值接近HPHG 和Event2vec。原因是MovieLens超网络的内部节点之间的元组关系较弱，成对关系较强，因此特定地训练成对关系的方法表现较好，比如Coarsas2hvec、Hyper2vec和HPSG。

5.4 超网络重建

选取drug 和GPS 超网络进行超网络重建实验。超网络重建［13］的评估指标定义如式（18）所示：

其中：对重建超边的元组相似性按照升序排序，ni=1表示第i个重建超边存在于原超网络中，否则ni=0；χ为重建的总超边数；ρ为重建超边的比率。

超网络重建实验如图6 所示，HRSC 方法在drug和GPS 超网络上的重建性能优于普通网络表示学习方法deepwalk、node2vec、metapath2vec 和Coarsas2hvec。原因是HRSC 方法捕获了节点之间元组关系，即超边。超网络表示学习方法Event2vec、Hyper2vec、HPSG 和HPHG 在较大重建超边比率时，超网络重建性能不佳，而HRSC 在各个比率的超边重建中都表现出了稳定的性能，且HRSC 在GPS 超网络上显著优于其他基线方法，这表明了HRSC 方法的有效性和鲁棒性。

图6 超网络重建Fig.6 Hypernetwork reconstruction

5.5 参数敏感度分析

参数β是一个平衡基于拓扑派生目标函数的模型和基于集合约束目标函数的模型的调和因子。当β=0时，HRSC 只能捕获节点之间的成对关系。当0<β≤1时，HRSC 可以同时捕获节点之间的成对关系和元组关系。设置0 ≤β≤1，取各个超边重建比率的平均值AACC（ρ）。通过超网络重建任务分析参数β的影响。

由图7 可知，当β=0 时，HRSC 方法仅捕获了节点之间的成对关系，没有考虑节点之间的元组关系；随着β的增大，节点之间的元组关系被融入到节点表示向量中，HRSC 方法分别在β=0.6 和β=0.7 时达到最大，表明元组关系的重要性在增强；继续增大β，超网络重建性能开始下降，表明成对关系的重要性在增强。

图7 参数β 的敏感度分析Fig.7 Sensitivity analysis of parameter β

6 结束语

本文提出一种异质超网络表示学习方法HRSC。该方法采用集合约束机制将超边融入到超网络表示学习中来学习高质量的节点表示向量。实验 结果表明，HRSC 方法在drug、GPS、MovieLens 3 个超网络上的平均性能均优于基线方法。由于超边分解会带来信息损失，下一步将不再分解超边，而是在集合约束基础上引入超路径，以便于更好地处理异质超网络。