收稿日期：２０２０ ０６ ２０；修回日期：２０２０ ０８ １３ 基金项目：国家自然科学基金资助项目（６１８７２１６１，６１６０２０５７，６１９７６１０３）；吉林省科技发展计划资助项目（
２０１８１０１３２８ＪＣ）；吉林省科技厅优秀青年人才基金资助项目（２０１７０５２００５９ＪＨ）；吉林省技术攻关项目（２０１９０３０２０２９ＧＸ）；吉林省发改委项目（２０１９Ｃ０５３Ｇ ８）；吉林省教育厅科研项目（ＪＪＫＨ２０１９１２５７ＫＪ）
作者简介：杨伟英（１９９５ ），女，山东潍坊人，硕士研究生，主要研究方向为深度学习、数据挖掘及网络表示；王英（１９８１ ），女（通信作者），黑龙江哈尔滨人，教授，博导，博士，主要研究方向为机器学习、社交网络、数据挖掘和搜索引擎（ｗａｎｇｙｉｎｇ２０１０＠ｊｌｕ．ｅｄｕ．ｃｎ）；吴越（１９９６ ），男，山西长治人，硕士研究生，主要研究方向为机器学习、数据挖掘及异质信息网络表示． 杨伟英ａ，ｂ，王 英ａ，ｂ，ｃ ，吴 越ｂ
，ｃ
（吉林大学ａ．软件学院；ｂ．符号计算与知识工程教育部重点实验室；ｃ．计算机学院，长春１３０
０１２）摘 要：如何采用超边建模网络数据中的多元关联关系，实现潜在超边链接关系的预测具有重要的现实意义。
现有方法主要集中于研究具有成对关系的网络数据，然而，直接将现有的链接预测方法用于超图网络中的超边链接预测具有一定的局限性。因此，提出基于异质变分超图自动编码器的超边链接预测模型（ｈｅｔｅｒｏｇｅｎｅｏｕｓｖａｒｉ
ａｔｉｏｎａｌｈｙｐｅｒｇｒａｐｈａｕｔｏｅｎｃｏｄｅｒ
，ＨＶＧＡＥ）。首先，利用超图卷积实现变分超图自动编码器，将超图网络数据转换成一种低维空间表示；其次，加入节点近邻度函数，最大程度地保留其结构信息，从而构建异质超图网络超边链接预测模型。针对三种不同类型的超图网络进行实验，结果表明相比其他的基准方法，ＨＶＧＡＥ模型获得了较好的预测结果，说明其能够较好地解决超图网络中的超边链接预测问题。关键词：异质信息网络；变分图自动编码器；表示学习；链接预测；超图中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１００１ ３６９５（２０２１）０５ ０４２ １５０８ ０６ｄｏｉ：１０．１９７３４／ｊ．ｉｓｓｎ．１００１ ３６９５．２０２０．０６．０１９１ Ｅｘｐｌｏｒｉｎｇｈｅｔｅｒｏｇｅｎｅｏｕｓｖａｒｉａｔｉｏｎａｌｈｙｐｅｒｇｒａｐｈ
ａｕｔｏｅｎｃｏｄｅｒｆｏｒｈｙｐｅｒ ｅｄｇｅｌｉｎｋｐｒｅｄｉｃｔｉｏｎ
卷积编码
ＹａｎｇＷｅｉｙｉｎｇａ，ｂ，ＷａｎｇＹｉｎｇａ，ｂ，ｃ ，ＷｕＹｕｅ
ｂ，ｃ
（ａ．ＣｏｌｌｅｇｅｏｆＳｏｆｔｗａｒｅ，ｂ．ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳｙｍｂｏｌＣｏｍｐｕｔａｔｉｏｎ＆ＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ｃ．ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉ ｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３００１２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｈｏｗｔｏｕｓｅｈｙｐｅｒ ｅｄｇｅｔｏｍｏｄｅｌｔｈｅｍｕｌｔｉｐｌｅａｓｓｏｃｉａｔｉｏｎｒｅｌａｔｉｏｎｓｈｉｐｉｎｎｅｔｗｏｒｋｄａｔａａｎｄｒｅａｌｉｚｅｔｈｅｐｒｅｄｉｃｔｉｏｎｏｆ
ｐｏｔｅｎｔｉａｌｈｙｐｅｒ ｅｄｇｅｌｉｎｋｒｅｌａｔｉｏｎｓｈｉｐｈａｓｉｍｐｏｒｔａｎｔｐｒａｃｔｉｃａｌｓｉｇｎｉｆｉｃａｎｃｅ．Ｅｘｉｓｔｉｎｇｌｉｎｋｐｒｅｄｉｃｔｉｏｎｍｅｔｈｏｄｓｍａｉｎｌｙｆｏｃｕｓｏｎｎｅｔｗｏｒｋｓｗｉｔｈｐａｉｒｗｉｓｅｒｅｌａｔｉｏｎｓｈｉｐｓ．Ｈｏｗｅｖｅｒ，ｄｉｒｅｃｔｌｙａｐｐｌｙｉｎｇｅｘｉｓｔｉｎｇｌｉｎｋｐｒｅｄｉｃｔｉｏｎｍｅｔｈｏｄｓｔｏｈｙｐｅｒ ｅｄｇｅｌｉｎｋｐｒｅｄｉｃｔｉｏｎ
ｉｎｈｙｐｅｒｇｒａｐｈｎｅｔｗｏｒｋｓｈａｓｃｅｒｔａｉｎｌｉｍｉｔａｔｉｏｎｓ．Ｔｈｅｒｅｆｏｒｅ
，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｈｙｐｅｒ ｅｄｇｅｌｉｎｋｐｒｅｄｉｃｔｉｏｎｍｏｄｅｌ，ｃａｌｌｅｄＨＶＧＡＥ（ｈｅｔｅｒｏｇｅｎｅｏｕｓｖａｒｉａｔｉｏｎａｌｈｙｐｅｒｇｒａｐｈａｕｔｏｅｎｃｏｄｅｒ）ｂａｓｅｄｏｎｈｅｔｅｒｏｇｅｎｅｏｕｓｖａｒｉａｔｉｏｎａｌｈｙｐｅｒｇｒａｐｈａｕｔｏｅｎｃｏｄｅｒ．Ｆｉｒｓｔｌｙ，ｔｈｉｓｍｅｔｈｏｄｕｓｅｄｈｙｐｅｒｇｒａｐｈｃｏｎｖｏｌｕｔｉｏｎｔｏｒｅａｌｉｚｅｖａｒｉａｔｉｏｎａｌｈｙｐｅｒｇｒａｐｈａｕｔｏｅｎｃｏｄｅｒ，ａｎｄｃｏｎｖｅｒｔｅｄｔｈｅｈｙｐｅｒｇｒａｐｈｎｅｔｗｏｒｋｄａｔａｉｎｔｏａｌｏｗ ｄｉｍｅｎｓｉｏｎｒｅｐｒｅｓｅｎｔａｔｉｏｎ．Ｔｈｅｎｉｔａｄｄｅｄｎｏｄｅｓｎｅａｒ ｎｅｉｇｈｂｏｒｓｉｍｉｌａｒｉｔｙｆｕｎｃｔｉｏｎｔｏｒｅｔａｉｎｔｈｅｓｔｒｕｃｔｕｒａｌｉｎｆｏｒｍａｔｉｏｎｔｏｔｈｅｌａｒｇｅｓｔｄｅｇｒｅｅ，ｓｏａｓｔｏｃｏｎｓｔｒｕｃｔｈｅｔｅｒｏｇｅｎｅｏｕｓｈｙｐｅｒ ｅｄｇｅｌｉｎｋｐｒｅｄｉｃｔｉｏｎｍｏｄｅｌ．Ｅｘｐｅｒｉｍｅｎｔｓｏｎｔｈｒｅｅｄｉｆｆｅ
ｒｅｎｔｔｙｐｅｓｏｆｈｙｐｅｒｇｒａｐｈｎｅｔｗｏｒｋｓ
，
ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔＨＶＧＡＥｍｏｄｅｌｈａｓｇａｉｎｅｄｂｅｔｔｅｒｐｒｅｄｉｃｔｉｏｎｒｅｓｕｌｔｃｏｍｐａｒｅｄｗｉｔｈｔｈａｔｏｆｏｔｈｅｒｂａｓｅｌｉｎｅｍｅｔｈｏｄｓ，ｉｎｄｉｃａｔｉｎｇｔｈａｔｉｔｃａｎｂｅｔｔｅｒｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｈｙｐｅｒ ｅｄｇｅｌｉｎｋｐｒｅｄｉｃｔｉｏｎｉｎｔｈｅｈｙｐｅｒｇｒａｐｈｎｅｔｗｏｒｋ．Ｋｅｙｗｏｒｄｓ：ｈｅｔｅｒｏｇｅｎｅｏｕｓｉｎｆｏｒｍａｔｉｏｎｎｅｔｗｏｒｋ；ｖａｒｉａｔｉｏｎａｌｇｒａｐｈａｕｔｏｅｎｃｏｄｅｒ；ｒｅｐｒｅｓｅｎｔａｔｉｏｎｌｅａｒｎｉｎｇ；ｌｉｎｋｐｒｅｄｉｃｔｉｏｎ；ｈｙｐｅｒｇｒａｐｈ
０ 引言
网络是表达实体间联系的一种重要形式，真实世界的数据通常被组织成图结构的方式。图数据分析在数据挖掘任务中
起着重要的作用，包括节点分类［
１］、链接预测［２］、图聚类［３］等。这些任务适用于各种图数据，包括蛋白质—蛋白质相互作用网络、社交媒体和引文网络。然而，由于图数据分析具有较高的计算代价和较低的并行性，所以处理图数据是一项具有挑战性的任务。最近图表示学习技术的发展为处理复杂图数据提供了便利。图表示学习的基本思想是学习网络节点隐层的低维表示，同时保留网络拓扑结构、节点内容和其他信息。
例如，网上购物往往需要在社交网络中到有共同兴趣的相似用户。
因此，如何学习节点的隐层表示［
４］
是一个重要的问题。对于同质信息网络，Ｔａｎｇ等人［５］
提出ＬＩＮＥ模型，通过对节点一阶
和二阶相似度进行建模，根据权重对边进行采样训练学习节点
的分布式表示。Ｇ
ｒｏｖｅｒ等人［６］
提出ｎｏｄｅ２ｖｅｃ模型通过增加两个参数改变随机游走策略，采用广度优先和深度优先遍历节点，在学习节点表示过程中同时考虑了局部和全局特征信息。
对于异质信息网络，Ｄｏｎｇ等人［７］
提出ｍｅｔａｐａｔｈ２ｖｅｃ模型，基于元路径（ｍｅｔａ ｐａｔｈ）指导随机游走过程，然后使用异质ｓｋｉｐ ｇｒａｍ训练模型，建模结构上和语义上相近的节点，能够同时捕捉不同类型节点之间的语义和结构联系。然而，此类方法大多为浅层模型，其表达能力不足。
另一方面，以上方法都假定对象之间的关系是成对的，这意味着每条边只连接两个节点（图１（ａ）：在一个普通图中，用一条线表示的每条边只连接两个节点）。然而，在现实生活中对象实体之间的关系往往是较为复杂的单对多或者多对多的多元关联关系，例如，在社交网络中，用户对电影进行评价，将
第３８卷第５期２０２１年５月 计算机应用研究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＶｏｌ．３８Ｎｏ．５
Ｍａｙ２０２１
用户、电影和标签作为节点，用户的评价看做一个事件作为图的边，每条边可以连接两个以上的节点。在这种情况下，其关系不再是二元的（成对的），而是三元、四元或更多元的。在解决该类问题时，如果简单地把多元关系强制转换为二元关联关系，那么将会丢失很多有用的信息。由此引出超图的概念［８］，利用超边同时连接多个节点的特殊图网络（图１（ｂ）：在超图中，每条边由一个有
颜的椭圆表示，连接两个以上的节点）。如Ｆａｃｅｂｏｏｋ和新浪微博等构成的社交网络［９］，用户之间的关系复杂多样，可能包含多个实体，如果仅将其建模为两两节点之间的链接关系，那么将会忽略很多复杂关联关系的信息，因此，通过超边定义三个或三个以上实体构成的关系，形成超图，从而预测节点间存在的超边链接关系十分重要。
异质超图的超边链接预测问题的形式化描述。本文基于异质信息网络构建超图，在表示学习过程中，考虑了不同类型节点。
定义１ 异质信息网络［２４］
。异质信息网络可定义为Ｇ＝（Ｖ，Ｅ），其中Ｖ是所有节点的集合，Ｅ为所有边的集合。一个
异质图通过节点类型映射函数Φ：Ｖ→Ａ和边类型映射函数ψ
：Ｅ→ 相关联， 和 表示一组预定义的节点类型和边类型，｜ ｜＋｜ ｜
＞２。定义２ 超图［２４］
。超图（ｈｙｐｅｒｇｒａｐｈ）是一种广义上的图，其边可以与任意数量的节点连接。对于给定的超图网络，采用
图（
ｇｒａｐｈ）对其建模，超图与普通图的主要区别在于图中边上节点的个数不同，在普通图中，一条边包含两个节点，在超图
中，边被称为超边（
ｈｙｐｅｒ ｅｄｇｅ），一条超边包含多个节点，如图１（ｂ）所示。给定一个超图网络，将其建模为超图 ＝（ ，ε），其中， ＝｛ｖ１，ｖ２，…，ｖｎ｝是超图网络的有限节点集，ε＝｛ε１
，ε２，…，εｉ｝为超边集合，对于任意一条超边εｉ∈ε是节点集Ｖ的一个子集。如果一个超图中，所有的超边最多只包含两个节
点，那么超图就会退化为普通图，如图１
（ａ）所示。定义３ 超图关联矩阵［２４］。超图关联矩阵用Ｈ｜Ｖ｜×｜ε
｜表示，定义了节点和超边的关系。对于给定的超图 ＝（ ，ε），若节点ｖｉ∈εｊ，则ｆ（ｖｉ，εｊ
）＝１，否则为０。定义４ 超图网络的一阶近邻性［２４］
。超图网络的一阶近邻性度量了节点之间的ｎ元近邻度。对于任意ｎ个节点ｖ１，ｖ２，…，ｖｎ
，如果这ｎ个节点之间存在超边，则这ｎ个节点的一阶近邻性被定义为１，但这意味着ｎ个节点的任何子集都没有一阶近邻性。一阶近邻是指现实世界中若干实体的不可分解的近邻性。
例如，图２（ｃ）中，〈ｕ１，ｍ１，ｔ２〉、〈ｕ１，ｍ２，ｔ１〉、〈ｕ２，ｍ２，ｔ１〉、〈ｕ２，ｍ１，ｔ２〉为四条超边，不同超边的内部节点具有一阶近邻性。例如，（ｕ１，ｍ１，ｔ２）在一条超边内，因此，ｕ１、ｍ１、ｔ２具有一阶近邻性。
定义５ 超图网络的二阶近邻性［２４］
。超图网络的二阶近邻性是指两个节点相对于其邻域结构的邻近性。即两个节点具有共同的邻域集合则说明这两个节点具有二阶近邻性。
例如，在图２（ｃ）中，ｕ１的邻域集合为｛（ｍ２，ｔ１），（ｍ１
，ｔ２）｝，ｕ２的邻域集合为｛（ｍ２，ｔ１），（ｍ１，ｔ２
）｝，它们有共同的邻域集合，因此，ｕ１和ｕ２
具有二阶近邻性。
问题描述。给定一个异质信息网络Ｇ＝（Ｖ，Ｅ），对于多种
类型的节点集合Ｖ和关系集合Ｅ
（在这里仅考虑节点的类型）抽取形成超图网络 ＝（ ，ε
），通过超边构建得到超图网络关联矩阵Ｈ。将超图关联矩阵Ｈ与其转置ＨＴ相乘得到超图邻
接矩阵Ｍ，
ＨＶＧＡＥ模型的输入为整个超图邻接矩阵Ｍ及其特征矩阵Ｘ，因此，基于超图的表示学习即学习映射函数 ： →
Ｚ∈
｜Ｎ｜×｜Ｄ｜
，其中，Ｚ为学习到的节点表示，尽可能完整地保留了超图网络中的高阶邻接关系和结构信息，
Ｄ是节点的特征维度，得到节点的低维向量表示Ｚ后，将Ｚ用于链接预测任务，从而预测超图网络中的潜在超边链接关系。
３ 超边链接预测模型ＨＶＧＡＥ
３ １ ＨＶＧＡＥ模型框架
本文基于异质超图网络的超边链接预测模型ＨＶＧＡＥ包
括异质变分超图自动编码器部分、超边邻近度函数部分和超边
链接预测部分三个主要模块，其整体框架图如图３所示。首先，将异质信息网络组织成超图网络，并将超图邻接矩阵及特征矩阵作为输入，通过超图卷积实现变分超图自动编码器，聚集其近邻特征；其次，加入节点近邻度函数，学习节点的一阶近邻性；最后，将学习到的隐层表示向量应用于超边链接预测任务，
挖掘其潜在的超边链接关系。
码器部分进行改进提出超图自动编码器。超图自动编码器的编码部分设计为两层超图卷积网络ＨＧＣＮ（ｈｙｐｅｒｇｒａｐｈｃｏｎｖｏｌｕ ｔｉｏｎａｌｎｅｔｗｏｒｋ），通过利用神经网络将图结构直接嵌入到低维空间中。对于给定的超图 ＝（Ｍ，Ｘ），其中，Ｍ是邻接矩阵，Ｘ是特征矩阵，超图上的卷积网络实际上是一个谱图卷积运算，用函数ｆ（Ｚｔｌ，Ｍｔ｜Ｗｌ）表示
＝（Ｍ，Ｘ）；Ｚｔｌ＋１＝φ（Ｚｔｌ，Ｍｔ｜Ｗｌ）（５）其中：Ｚｔｌ是ｔ类型节点经过ｌｔｈ卷积后对应的节点的输出特征；Ｗｌ是ｌｔｈ的参数。
传统的图卷积网络通过图的拉普拉斯矩阵的特征值和特征向量来研究图的性质，对于一个有Ｎ个节点的图Ｇ而言，其经过对称归一化的拉普拉斯矩阵 定义为
＝Ｄ－１２（Ｄ－Ａ）Ｄ－１２（６）其中：Ｄ是Ｇ的度矩阵；Ａ是维度为Ｎ×Ｎ的邻接矩阵。而在超图上的拉普拉斯矩阵定义为
＝Ｉ－Ｄ－１２ＭｔＷＤ－１ＭｔＴＤ－１２（７）其中：Ｄ是超图的度矩阵；Ｉ为单位矩阵。
基于上述操作，可以定义任意深度网络。然而，在式（７）中存在部分节点未参与传播过程，并且其信息也不会被邻居节点更新的情况。为了克服这一问题，令＾
Ａ＝Ｉ＋Ａ表示加入自环的原始异质信息网络，因此，重新定义了超图卷积函数。
ｆ（Ｚｔｌ，Ｍｔ｜Ｗｌ）＝σ（Ｄ－１２ＭｔＷＤ－１ＭｔＴＤ－１２＋＾
Ａ）Ｚｔｌ
()
Θ（８）其中：σ是激活函数；Θ作为卷积核其值在训练过程中不断被更新。
３ ２ ４ ＨＶＧＡＥ模型
异质变分超图自动编码器是在图自动编码（３．２．２节）的基础上的拓展，其最大的特点是首先做了一个预设，即编码的结果不是某个确定的值，而是一个范围。本文使用的是平均值和方差，即多个节点编码结果值，平均分布在均值两侧的方差范围内。异质变分超图自动编码器由推理（ｉｎｆｅｒｅｎｃｅｍｏｄｅｌ）模型和生成模型（ｇｅｎｅｒａｔｉｖｅｍｏｄｅｌ）两部分组成。与图自动编码器相比，其变分过程主要体现在推理模型中。
ａ）推理模型。通过进行推理，得到隐层变量Ｚ。主要是通过一个函数ｆ得到均值向量μ和方差σ２，在这里函数ｆ被定义为两层ＨＧＣＮ（３．２．３节），推理模型可用公式表述为
μｔ＝ＨＧＣＮμ（Ｘｔ，Ｍｔ）（９）
σｔ＝ＨＧＣＮσ（Ｘｔ，Ｍｔ）（１０）ＨＧＣＮ（Ｘｔ，Ｍｔ）＝珦ＭｔＲｅＬＵ（珦ＭｔＸｔＷ０）Ｗ１（１１）对于每一个输入ｉ，有
ｑ（Ｚｔｉ｜Ｘｔｉ，Ｍｔｉ）＝ Ｎｉ＝１ｑ（Ｚｔｉ｜Ｘｔｉ，Ａｔｉ）（１２）
ｑ（Ｚｔｉ｜Ｘｔｉ，Ｍｔｉ）＝ （Ｚｔｉ｜μｔｉ，ｄｉａｇ（σｔ２ｉ））（１３）其中：ｐ（·）表示一个概率值，符合高斯分布。
ｂ）生成模型。在得到隐层变量Ｚ之后，将通过生成模型来重构邻接矩阵珦Ｍ。对于这部分，本文使用内积来重构矩阵中的每个元素得到重构邻接矩阵珦Ｍ：
ｐ（珦Ｍｔ｜Ｚｔ）＝ Ｎｉ＝１ｐ（珦Ｍｔｉｊ｜Ｚｔｉ，Ｚｔｊ）（１４）
ｐ（珦Ｍｔｉｊ＝１｜Ｚｔｉ，Ｚｔｊ）＝σ（ＺｔｉＴＺｔｊ）（１５）其中：生成模型的概率分布ｑ（·）是由内积给出的；σ表示为ｓｉｇｍｏｉｄ函数。
ｃ）学习过程。将学习过程中的损失函数分为构造损失和隐层变量约束损失两部分。构造损失是看构造的邻接矩阵是否与输入矩阵相似；另一个损失是利用ＫＬ散度来衡量隐层变量的分布与正态分布的相似程度。为了训练变分超图自动编
码器，本文优化了变分下界目标函数
Ｒ
，定义为
Ｒ＝Ｅｑ（Ｚｔ｜Ｘｔ，Ｍｔ）［ｌｏｇｐ（Ｍｔ｜Ｚｔ）］＋ＫＬ（ｑ（Ｚｔ｜Ｘｔ，Ｍｔ）‖ｐ（Ｚｔ））
（１６）其中：ＫＬ（ｑ（·）‖ｐ（·））定义了ＫＬ散度，进一步取高斯先验分布ｐ（Ｚ）＝∏
ｉ
ｐ（Ｚ
ｉ
）＝∏
ｉ
Ｎ（Ｚ｜０，Ｉ）。
变分超图自动编码器的目标是最小化输入和输出之间的重新测量误差，重建过程将使具有相似邻域的节点具有相似的隐层表示，从而保留二阶邻近性。由于输入特征是超图网络的邻接矩阵，而邻接矩阵通常是非常稀疏的。为了加速模型，提出只重构邻接矩阵中的非零元素。重构误差为
１
Ｎ
∑
ｉ
Ｎ
｜ｓｉｇｎ（Ｍ） （Ｍ－珦Ｍ）｜（１７）其中：ｓｉｇｎ是符号函数； 表示Ｈａｄａｍａｒｄ积。
此外，在超图网络中，节点往往具有多种类型，形成了异构的超图网络。考虑到不同类型节点的特殊性，需要学习不同类型节点的唯一隐层空间。在本文模型中，每个异构类型的实体都有对应的低维表示。那么对于所有类型的节点，损失函数定义为
１＝
１
Ｎ
∑
ｉ
Ｎ
｜ｓｉｇｎ（Ｍｔｉ） （Ｍｔｉ－珦Ｍｔｉ）｜（１８）同一超边内的节点具有高度的一阶近邻性，可以学习到节点的局部邻域特征，生成更鲁棒的表示。因此，采用多层感知机实现节点近邻度函数的建模。如图３所示，采用两个全连接
层实现。以ａ、ｂ、ｃ三种类型的节点为例，将三个节点（ｖ
ｉ
，ｖ
ｊ
，
ｖ
ｋ
）的嵌入（Ｚａ
ｉ
，Ｚｂ
ｊ
，Ｚｃ
ｋ
）串联起来作为多层感知机的输入。最终将其映射到概率空间中，得到近邻度为
Ｓｉｊｋ＝σ（Ｗ×（Ｚａｉ＋Ｚｂｊ＋Ｚｃｋ））（１９）其中：σ为ｓｉｇｍｏｉｄ函数。最终，优化目标函数为
２＝－（ ｉｊｋｌｏｇＳｉｊｋ＋（１－ ｉｊｋ）ｌｏｇ（１－Ｓｉｊｋ））（２０）为了保持超图网络的一阶和二阶邻近性，本文结合式（１６）（１８）联合最小化ＨＶＧＡＥ模型的目标函数。
ｔ＝ １＋α ２＋ Ｒ（２１）４ 实验
本章从实验角度详细介绍使用本文提出的方法构建面向超图网络的超边链接预测模型，并且在三个真实数据集上进行了测试。
４ １ 数据集
为了全面评估ＨＶＧＡＥ模型的有效性，在ＧＰＳ、ＭｏｖｉｅＬｅｎｓ和ｄｒｕｇ三个数据集上测试。数据集的详细统计信息如表１所示。
表１ 实验数据集
Ｔａｂ．１ Ｓｔａｔｉｓｔｉｃｓｏｆｔｈｅｄａｔａｓｅｔ
ｄａｔａｓｅｔｓｎｏｄｅ＃（Ｖ）＃（Ｅ）
ＧＰＳｕｓｅｒｌｏｃａｔｉｏｎａｃｔｉｖｉｔｙ１４６７０５１４３６
ＭｏｖｉｅＬｅｎｓｕｓｅｒｍｏｖｉｅｔａｇ１９４３５６１０８０４０４６４１２ｄｒｕｇｕｓｅｒｄｒｕｇｒｅａｃｔｉｏｎ１２１０７７６３９８１７１７５６ ａ）ＧＰＳ［２５］。数据集给
出了用户在某个位置加入某个活动。本文利用（ｕｓｅｒ，ｌｏｃａｔｉｏｎ，ａｃｔｉｖｉｔｙ）关系建立超图网络的超边。其中，有１４６个作者节点，７０个位置节点，６个活动节点，超边数为１４３６条。
ｂ）ＭｏｖｉｅＬｅｎｓ［２６］。数据集记录了来自ＭｏｖｉｅＬｅｎｓ（ｈｔｔｐｓ：／／ｍｏｖｉｅｌｅｎｓ．ｏｒｇ／）的个人标签活动。每部电影至少有一种类型。本文利用（ｕｓｅｒ，ｍｏｖｉｅ，ｔａｇ）关系形成超图网络的超边。其中，用户节点为１９４３个，电影节点为５６１０个，标签节点为８０４０个，超边数为４６４１２条。
ｃ）ｄｒｕｇ数据集（ｈｔｔｐ：／／ｗｗｗ．ｆｄａ．ｇｏｖ／Ｄｒｕｇｓ／）来自ＦＤＡ不良事件报告系统（ＦＡＥＲＳ）。它包含提交给的不良事件和药物错误报告的信息食品及药物管理局。本文利用（ｕｓｅｒ，ｄｒｕｇ，ｒｅ ａｃｔｉｏｎ）关系构建超图网络，即如使用者有某些反应而服用某些药物，则会引起不良反应。其中，使用者节点为１２个，药物节点为１０７７个，反应节点为６３９８个，超边数为１７１５６条。
４ ２ 对比模型
为了更好地评价ＨＶＧＡＥ模型，将其与以下基准方法进行
·
１
１
５
１
·
第５期杨伟英，等：面向异质变分超图自动编码器的超边链接预测模型
比较。ａ）ＤＨＮＥ。文献［２４］提出的深度超网络嵌入模型，用于学习具有不可分解的超边的超网络。其主要通过自动编码器学习不同类型节点的隐层表示，并通过一个元组相似函数建模节点相似度。
ｂ）ＡＥ。文献［２７］提出的自动编码器（ａｕｔｏｅｎｃｏｄｅｒ）是一种ｓｅｌｆ ｓｕｐｅｒｖｉｓｅｄ技术，它由编码器和解码器两部分组成，试图将输入复制到输出从而学习图形嵌入，通过隐藏层将学习输入节点的低维稠密表示。
ｃ）ＧＡＥ。文献［２８］提出的基于同质信息网络的图自动编码器模型，编码器使用图卷积层获得每个节点的网络嵌入，在应用非线性激活函数后，解码器重建图形邻接矩阵。通过最小化真实邻接矩阵和重建的邻接矩阵之间的差异来训练网络，获得节点的表示。
ｄ）ＶＧＡＥ。文献［２９］提出的将均值和方差引入编码过程中，使得编码结果由一个确定的值变为一个范围，即目标值应当平均分布在一个范围内，以保证编码空间的最大化利用。
ｅ）ＲＷＲ ＧＡＥ。文献［３０］提出了基于随机游走的方法来对图自动编码器学习到的表示进行正则化，通过最小化图数据重构误差实现无监督学习节点的表示向量。
ｆ）ＨＶＧＡＥ。本文提出的基于异质变分超图自动编码器的超边链接预测模型，基于超图视角研究链接预测问题，同时，将变分图自动编码器引入超图领域，为之后的超图研究提供了新思路。
ｇ）ＨＶＧＡＥ １
。本文方法的变体，不采用联合优化方式，只采用超图自动编码器的重构损失函数，如式（
１８）所示。在此过程中，并没有加入用于保持超图一阶邻近性的目标函数。
ｈ）ＨＶＧＡＥ ２
。本文方法的另一种变体，其目标函数只采用维持超图一阶近邻性的节点近邻性函数，如式（２０）所示。４ ３ 度量标准
在机器学习中，ＡＵＣ和ＡＰ是一种常见的模型评估指标，
主要用于评价预测正例负例概率值，因此，常被用于作为链接预测的评价指标，其主要基于混淆矩阵计算真正率和假正率，然后通过ＲＯＣ面积来衡量链接预测的准确率。
测试集上每个模型的ＲＯＣ曲线下的面积（ＡＵＣ）和平均精度（ＡＰ）分数，其公式为
ＡＵＣ＝∑ｅ∈Ｅ
ｒａｎｋｅ－ＮＥ（１＋ＮＥ
）２
ＮＥ×ＮＥ
×１００％
（２２）
其中：Ｅ是超边集合；ＮＥ为正样本数目；ＮＥ为负样本的数目；
ｒａｎｋｅ为通过预测得分来表示的超边的排名。
ＡＰ＝∑ｐ
ｒｅｃｉｓｉｏｎＮｔｏｔａｌ
×１００％
（２３）
其中：ｐｒｅｃｉｓｉｏｎ表示正确预测的超边数／总超边数。４ ４ 参数设置
本文基于ＰｙＴｏｒｃｈ框架实现了ＨＶＧＡＥ模型，对于实验参数设置使用Ｋｉｐｆ和Ｗｅｌｌｉｎｇ［１］
提供的超参数为图自动编码器相关超参数。通过在三个数据集上学习节点的隐层表示从而证明ＨＶＧＡＥ模型在链接预测任务上的鲁棒性。模型通过迭代完成优化过程，实验结果取多次实验的最优值。在实验过程中，首先，在文献［２４］提出的超边不可分割性的基础上，进行数据集处理，将超图关
联矩阵转换成超图邻接矩阵，进而将超图邻接矩阵作为模型的输入。这些模型均在一个不完整版本的数据集上进行训练，即其中部分引用链接（边）被删除，而所有的节点特征被保留。本文从先前删除边和相同数量的随机抽样的未连接节点对（非边）中形成验证和测试集。根据模型对超边和非超边的正确分类能力来比较。验证集和测试集分别包含５％和１０％的链接。验证集用于超参数的优化。对于
ＨＶＧＡＥ按照文献［３１］中描述的那样初始化权重，使用
Ａｄａｍ［３２］
优化器进行２００次迭代训练，学习率为０．０１，中间隐层大小分别设置为３２和１６。对比方法中，重新复现了ＡＥ和ＤＨＮＥ模型，对于ＡＥ，将隐层大小设置为１２８、３２、１６，对于ＤＨＮＥ的自动编码器部分隐层大小设置为１２８、６４、３２、１６；而对于ＧＡＥ、ＶＧＡＥ、ＲＷＲ ＧＡＥ的参数设置本文均采用原文中提供的参量数设置。以上方法学习率和迭代次数均与本文模型相同。４ ５ 实验结果分析
本文在三个数据集上进行了实验，实验结果表明，相比于其他模型本文方法在异质超图网络的链接预测问题上取得了
更好的实验结果，对比结果如表２所示。可以看出，
ＨＶＧＡＥ模型的综合效果最好，对于ＧＰＳ数据集，ＨＶＧＡＥ其ＡＵＣ指标比结果最差的自动编码器（
ａｕｔｏｅｎｃｏｄｅｒ，ＡＥ）提高了１３．６９％，相比变分图自动编码器（ＶＧＡＥ）提高了１．７９％；其ＡＰ评价指标比ＡＥ提高了８．８６％，比ＶＧＡＥ提高了０．１８％。对于Ｍｏｖｉｅ Ｌｅｎｓ数据集，ＨＶＧＡＥ其ＡＵＣ指标比ＡＥ提高了１２．８４％，比ＲＷＲ ＧＡＥ提高了０．０５％；其ＡＰ指标比ＡＥ提高了７．８１％，相比ＨＶＧＡＥ １提高了０
．０９％。对于ｄｒｕｇ数据集，ＡＥ表现最差，ＲＷＲ ＧＡＥ表现相对较好，ＨＶＧＡＥ比ＡＥ提高了３４．２８％，相比ＲＷＲ ＧＡＥ提高了０．１８％，对于ＡＰ指标，ＧＡＥ表现最差，ＶＧＡＥ在其他模型中相对表现较好，本文ＨＶＧＡＥ模型的ＡＰ指标提高了２３．１９％。对于ＡＥ和ＧＡＥ，由于它们均采用的是自动编码器学习节点的隐层表示，所以，将其应用在超图表示学习时，由于自动编码器自身的限制，其学习到的节点表示能力不足，尤其是ＡＥ，其大多应用在同质信息网络中，对于节点类型的区分能力明显不足。而对于ＧＡＥ、ＶＧＡＥ、ＲＷＲ ＧＡＥ模型，其都是基于图自动编码器的方法，但是由于它们均针对成对的同质网络展开研究，其对于超边的建模能力不足，其结果并不是很理想。对于ＨＶＧＡＥ １和ＨＶＧＡＥ ２为Ｈ
ＶＧＡＥ的两种变体，实验结果表明，
ＨＶＧＡＥ模型采用变分超图自动编码器结合节点近邻度函数联合优化，在超图链接预测问题上取得了较好的效果。
表２ 超边链接预测模型对比结果Ｔａｂ．２ Ｒｅｓｕｌｔｏｆｈｙｐｅｒ ｅｄｇｅｌｉｎｋｐｒｅｄｉｃｔｉｏｎ
ｍｅｔｈｏｄＧＰＳＭｏｖｉｅＬｅｎｓｄｒｕｇＡＵＣＡＰＡＵＣＡＰＡＵＣ
ＡＰ
ＡＥ０．７９９３０．８５９２０．７８３００．８４１４０．６２３９０．７３５８ＧＡＥ０．８７４８０．８８２００．９０１６０．９０１１０．９５３２０．９３８３ＤＨＮＥ０．８９４００．９１３１０．８６７００．８７１１０．９５７２０．９５３３ＶＧＡＥ
０．９１８３
０．９２７００．９００７０．９１４３０．９６４００．９６７７ＲＷＲ ＧＡＥ０．９１６３０．９１０３０．９１０９０．９１０７０．９６４９０．９６６６ＨＶＧＡＥ １０．９０７６０．９１４００．９０６５０．９２０６０．９６４２０．９５９０ＨＶＧＡＥ ２０．８９８９０．９０５７０．９０９７０．９１８６０．９６４３０．９６４４ＨＶＧＡＥ
０．９３６２
０．９４７８
０．９１１４
０．９１９５
０．９６６７０．９６８６
５ 模型性能分析
５ １ 节点近邻度函数分析
ＨＶＧＡＥ模型除了引入超图卷积，将变分图自动编码器拓
展到超图学习领域，还在此基础上添加了节点近邻度函数，判断节点是否在一条超边内，从而捕获超图网络中节点的一阶近邻性。本文中节点近邻度函数采用多层感知机实现，其中，多层感知机的层数对优化结果具有一定的影响，因此，本文分别分析了全连接层对链接预测结果的影响，如图４所示，将全连接层数分别设置为１～４层，观察其在三个数据集上的表现性能。如图４（ａ）所示，可以看到在ＧＰＳ数据集上，其效果最为明
显，这主要是因为Ｇ
ＰＳ数据集较小，受全连接层的影响较大，当层数ｌ＝１时，链接预测性能最差，当ｌ＝２时，链接预测结果
·２１５１·计算机应用研究第３８卷
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议