超边约束的异质超网络表示学习方法

王可可，朱宇，王晓英，黄建强，曹腾飞

超边约束的异质超网络表示学习方法

王可可，朱宇*，王晓英，黄建强，曹腾飞

（青海大学 计算机技术与应用系，西宁 810000）（∗通信作者电子邮箱zhuyu@qhu.edu.cn）

与普通网络相比，超网络具有复杂的元组关系（超边），然而现有的大多数网络表示学习方法并不能捕获元组关系。针对上述问题，提出一种超边约束的异质超网络表示学习方法（HRHC）。首先，引入一种结合团扩展和星型扩展的方法，从而将异质超网络转换为异质网络；其次，引入感知节点语义相关性的元路径游走方法捕获异质节点之间的语义关系；最后，通过超边约束机制捕获节点之间的元组关系，从而获得高质量的节点表示向量。在3个真实世界的超网络数据集上的实验结果表明，对于链接预测任务，所提方法在drug、GPS和MovieLens数据集上都取得了较好的结果；对于超网络重建任务，当超边重建比率大于0.6时，所提方法在drug数据集上的准确性（ACC）优于次优的Hyper2vec（biased 2nd order random walks in Hyper-networks），同时所提方法在GPS数据集上的ACC超过其他基线方法中次优的基于关联图的超边超边约束的异质超网络表示学习方法（HRHC-关联图）15.6个百分点。

网络表示；超网络；超边约束；链接预测；超网络重建

0 引言

网络在日常生活中无处不在，例如，社会网络、生物网络、大脑网络等。为了挖掘网络中蕴含的丰富的数据信息，网络表示学习［1］方法被提出并受到了广泛关注。网络表示学习，也称为网络嵌入，它的目的是为网络节点学习低维表示向量。节点表示向量可用于节点分类［2］、链接预测［3］和社区检测［4］等网络分析任务。具体地，节点分类预测节点的类别和标签，在网络安全中检测网络中的欺诈实体就属于节点分类问题；链接预测即预测节点之间是否存在潜在的链接（边），它的常见应用有社交网站的好友推荐、预测蛋白质之间的相互影响、预测犯罪嫌疑人的关系和商品推荐等；社区检测将节点划分为集群，它在生物信息领域被用来发现相同功能或结果的生物分子。

现有的大多数网络表示学习方法仅具有节点之间成对关系的普通网络设计，然而现实世界中的物体之间存在复杂的元组关系（超边），此时可以使用超网络对复杂的元组关系建模。根据超网络表示学习方法的特点，可以将它分为谱分析方法、神经网络方法和其他方法，按照建模思路再细分为展开式方法和非展开式方法［5］。其中：展开式谱分析方法的典型算法包括SE（Star Expansion）［6］、CE（Clique Expansion）［6］等；展开式神经网络方法将超图拉普拉斯矩阵代入传统图卷积神经网络，典型算法有HGNN（HyperGraph Neural Network）［7］。非展开式方法有非展开式谱分析方法和非展开式神经网络方法，其中，将非展开式神经网络方法进一步又划分为3种方法：基于自编码器、自注意力机制和卷积的方法，典型算法有Hyper2vec （biased 2nd order random walks in Hyper-networks）［8］、DHNE （Deep Hyper-Network Embedding）［9］、Hyper-SAGNN（a Self-Attention based Graph Neural Network for Hypergraphs）［10］、DHGNN （Dynamic HyperGraph Neural Networks）［11］等。

展开式方法和非展开式方法都各有优劣。展开式方法虽然直观灵活，但会丢失超网络结构信息；非展开式方法虽然没有分解超边，但也会有各自的缺点。例如Hyper2vec虽然在Skip-gram［12］框架中将有偏二阶随机游走策略应用于超网络，可以灵活地应用于各种类型的超网络，但是它没有充分考虑超边；DHNE通过结合多层感知器捕获元组关系，但它很难扩展到任意规模的超网络；Hyper-SAGNN相较于DHNE有更好的泛化性，但该模型计算的复杂度较高；DHGNN是动态超图构造模块和超图卷积模块的堆叠，然而该方法使用的数据集是由传统网络数据集构造的超网络数据集，因此该数据集并不算真正意义上的超网络数据集。

为了解决上述问题，本文提出一种超边约束的异质超网络表示学习方法（Heterogeneous hypernetwork Representation learning method with Hyperedge Constraint， HRHC），综合考虑节点之间的成对关系和元组关系。相较于基于平移约束的异质超网络表示学习（Heterogeneous hypernetwork Representation learning with the Translation Constraint， HRTC）［13］，本文方法可以看作拓扑派生模型、集合约束模型和平移约束模型的有机统一，它有效地将超边信息融合到超网络表示学习中，以学习高质量的节点表示向量。异质超网络的节点表示向量拥有广泛的应用场景，如趋势预测［14］、事件监测［15］和推荐系统［16］等各种在线应用，具有实际的应用价值。

本文的主要工作为：首先结合团扩展和星型扩展的方法，实现了异质超网络到异质网络的转换；其次通过感知节点语义相关性的元路径游走方法获取异质节点序列；最后提出了超边约束的异质超网络表示学习方法，将超边融入超网络表示学习过程。

1 问题定义

图1　异质超网络

2 预备知识

受文献［17］启发，文献［18］中提出将超图转换为2-截图+关联图和感知节点语义相关性的元路径游走方法，同时，本文还引用了文献［19］中的TransE（Translating Embeddings）模型。

2.1　超图转换为2-截图、关联图、2-截图+关联图

本节介绍超图转换为2-截图、关联图的详细策略［17］。

2.1.12-截图

2）与超边关联的任意两个节点之间两两相连。

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

图2　2-截图

2.1.2关联图

图3为图1对应的关联图。

图3　关联图

2.1.32-截图+关联图

2）若超边内部节点之间全部语义相关、全部语义不相关、部分节点之间语义相关，则2-截图+关联图分别为2-截图和关联图的完全组合图、关联图、关联图加上具有语义相关性节点之间的边［18］。

图4　二-截图+关联图

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

2.3　TransE模型

图5　TransE模型

3 HRHC

图6　HRHC的框架

3.1　拓扑派生目标函数

基于拓扑派生目标函数的模型学习了节点之间的成对关系。

因此，式（2）可以写为：

式（1）重新表示为：

3.2　集合约束目标函数

3.3　平移约束目标函数

此外，受TransE模型中平移机制的启发，通过引入平移机制为目标节点增加关系约束，即超边约束。

3.4　联合约束目标函数

HRHC细节如算法1所示。

算法1 HRHC。

/*将节点对应的向量进行初始化*/

7） end for

8） end for

9） end for

/*优化拓扑派生目标函数*/

14） end for

16） end for

/*优化集合约束目标函数*/

20） end for

/*优化平移约束目标函数*/

24） end for

26） end for

27） end for

4 实验与结果分析

4.1　数据集

一个药物网络、一个全球定位系统网络和一个电影网络被用来评估HRHC的性能。数据集详情如表1所示。

1）drug（https：//www.fda.gov/drugs）。该数据集来自食品药品监督管理局（Food and Drug Administration， FDA）不良事件报告系统（FDA Adverse Event Reporting System， FAERS）。它包括提交给FDA的不良事件和用药错误报告的信息。（用户，药物，反应）关系被看作超边，以构建超网络，即用户吃了具有一些副作用的药品将导致不良事件。

2）GPS（Global Positioning System）［20］。该数据集描述了用户在某个位置参加活动。（用户，位置，活动）关系被看作超边，用于超网络的构建。

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

表1　数据集详情

4.2　基线方法

DeepWalk［22］。是一个经典的网络表示学习方法，被用来学习节点表示向量。

node2vec［23］。引入深度优先和广度优先策略学习节点表示向量。

metapath2vec［24］。采用元路径的随机游走策略，来捕获异质节点之间的语义关系，以便于学习节点表示向量。

CoarSAS2hvec （Self-Avoid short sequence Sampling with the hin Coarsening procedure）［25］。通过HIN粗化和自避免短序列采样过程捕获异质网络的丰富信息，从而学习节点表示向量。

HRTC［13］。通过引入知识表示学习中的平移机制捕获节点之间的元组关系，从而学习节点表示向量。

Hyper2vec［8］。在超边上进行有偏二阶随机游走采样高阶关系，从而学习节点表示向量。

HPSG（Hyper-Path-based random walks + Skip-Gram）［26］。首先通过基于超路径的随机游走保留异质超网络的拓扑结构信息，其次通过Skip-gram模型学习节点表示向量。

HPHG（Hyper-Path-based random walks + Hyper-Gram）［26］。首先通过基于超路径的随机游走保留异质超网络的拓扑结构信息，其次通过Hyper-gram模型学习节点表示向量。

Event2vec［27］。将一个事件表示为多个对象之间的关系，然后利用事件嵌入学习对象嵌入。

4.3　链接预测

链接预测比较流行，例如个性化推荐、推荐系统是链接预测的典型应用。本节在GPS、MovieLens和drug这3个超网络数据集上进行链接预测实验。通过AUC（Area Under Curve）［28］评估HRHC的链接预测性能。

在链接预测中，在学习到节点和的表示向量和后，使用表2所列的二元算子［23］获取节点对的成对相似性。

表2　二元算子

从表2可以得到以下结果：

1）HRHC、HRTC、DeepWalk、node2vec、metapath2vec和CoarSAS2hvec分别在2-截图、关联图和2-截图+关联图上都进行了链接预测实验。因为HRHC针对超网络设计，所以该方法在3个超网络数据集上的链接预测效果均好于普通网络表示学习方法，即DeepWalk、node2vec、metapath2vec和CoarSAS2hvec。

2）在drug和GPS数据集上，HRHC优于超网络表示学习方法Hyper2vec和HPSG，接近超网络表示学习方法HPHG和Event2vec。原因是Hyper2vec和HPSG主要训练了节点之间的成对关系，而HRHC综合训练了节点之间的成对关系和元组关系（超边）。HPHG和Event2vec均适用于具有较高不可分解性的drug和GPS超网络。在MovieLens数据集上，HRHC优于特定训练节点之间的元组关系的超网络表示学习方法HPHG和Event2vec，接近特定训练节点之间的成对关系的超网络表示学习方法HPSG，原因是MovieLens超网络具有较低程度的不可分解性，即节点之间具有较强的相关性。

3）在3个超网络数据集上，HRHC优于超网络表示学习方法HRTC。原因是HRHC相较于HRTC方法增加了集合约束目标函数，并通过随机梯度上升算法使得式（10）达到平衡最优解，融入了更多有效的超边信息，因此HRHC较好地保留了超网络结构信息，从而获得了高质量的节点表示向量。

综上所述，通过综合考虑节点之间的成对关系和元组关系，HRHC学习了高质量的节点表示向量，可以较好地预测未知链接。

注：加粗表示最优值，下画线表示次优值。

4.4　超网络重建

节点的良好表示应该很好地保留原始网络的结构信息。评估节点表示质量的典型方法是重建网络。本节在GPS和drug数据集上进行超网络重建实验。

超网络重建［8］的准确性（ACCuracy， ACC）评价指标如式（25）所示：

由图7可知，在drug和GPS数据集上，HRHC在2-截图+关联图上的超网络重建效果均优于2-截图和关联图，特别地，在GPS超网络重建中，对基于2-截图+关联图的HRHC方法从=0.1到=1的ACC值求平均，以同样的区间对HRHC-关联图的ACC值求平均，两项差值为15.6，即HRCH-2-截图+关联图超过其他基线方法中次优的HRHC-关联图15.6个百分点。这说明了2-截图+关联图能够更好地保留超网络结构信息。在drug数据集上，在超边重建比率大于0.6时，HRHC的超网络重建效果优于其他基线方法；在GPS数据集上，HRHC整体都优于其他基线方法；此外，HRHC相较于其他基线方法，在增大超边重建比率时，HRHC的ACC值下降较为缓慢。上述结果表明超边约束机制能够充分考虑到超边，较好地保留超网络结构信息。

4.5　参数敏感度

图7　超网络重建

图8　参数敏感度分析

5 结语

为了应对超网络表示学习面临的挑战，本文提出超边约束的异质超网络表示学习方法，该方法综合考虑节点之间的成对关系和元组关系以学习高质量的节点表示向量。在3个超网络数据集上的实验结果表明，HRHC整体性能优于其他基线方法。尽管该方法通过超图到图的转换策略开展了超网络表示学习研究，并尝试在表示学习过程中融入超边，但是仍然会丢失一部分超网络结构信息，因此，今后的研究将不再对超边进行分解，而是将超边看成一个整体进行超网络表示学习研究。

[1] ZHU Y， YE Z L， ZHAO H X， et al. Text-enhanced network representation learning ［J］. Frontiers of Computer Science， 2020， 14（6）： 146322.

[2] SHEIKH N， KEFATO Z T， MONTRESOR A. Semi-supervised heterogeneous information network embedding for node classification using 1D-CNN ［C］// Proceedings of the 2018 Fifth International Conference on Social Networks Analysis， Management and Security. Piscataway： IEEE， 2018：177-181.

[3] 刘昱阳，李龙杰，单娜，等.融合聚集系数的链接预测方法［J］. 计算机应用， 2020， 40（1）： 28-35.（LIU Y Y， LI L J， SHAN N， et al. Link prediction method fusing clustering coefficients ［J］. Journal of Computer Applications， 2020， 40（1）： 28-35.）

[4] 陈吉成，陈鸿昶.基于张量建模和进化均值聚类的社区检测方法［J］. 计算机应用， 2021， 41（11）： 3120-3126.（CHEN J C， CHEN H C. Community detection method based on tensor modeling and evolutionary-means clustering ［J］. Journal of Computer Applications， 2021， 41（11）： 3120-3126.）

[5] 胡秉德，王新根，王新宇，等. 超图学习综述：算法分类与应用分析［J］. 软件学报， 2022， 33（2）： 498-523.（HU B D， WANG X G， WANG X Y， et al. Survey on hypergraph learning： algorithm classification and application analysis ［J］. Journal of Software， 2022， 33（2）：498-523.）

[6] AGARWAL S， BRANSON K， BELONGIE S. Higher order learning with graph ［C］// Proceedings of the 23rd International Conference on Machine Learning. New York： ACM， 2006： 17-24.

[7] FENG Y， YOU H， ZHANG Z， et al. Hypergraph neural networks ［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence and 31st Innovative Applications of Artificial Intelligence Conference and 9th AAAI Symposium on Educational Advances in Aritificial Intelligence. Palo Alto： AAAI Press， 2019： 3558-3565.

[8] HUANG J， CHEN C， YE F， et al. Hyper2vec： biased random walk for hyper-network embedding ［C］// Proceedings of the 2019 International Conference on Database Systems for Advanced Applications. Cham： Springer， 2019： 273-277.

[9] TU K， CUI P， WANG F， et al. Structural deep embedding for hyper-networks ［C］// Proceedings of the 32nd AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2018： 426-433.

[10] ZHANG R， ZOU Y， MA J. Hyper-SAGNN： a self-attention based graph neural network for hypergraphs ［EB/OL］. ［2019-11-06］. https：// arxiv.org/pdf/1911.02613.pdf.

[11] JIANG J， WEI Y， FENG Y， et al. Dynamic hypergraph neural networks ［C］// Proceedings of the 28th International Joint Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2019： 2635-2641.

[12] MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality ［C］// Proceedings of the 26th International Conference on Neural Information Processing Systems. Palo Alto： AAAI Press， 2013，2： 3111-3119.

[13] 刘贞国，朱宇，赵海兴，等.基于平移约束的异质超网络表示学习［J］. 中文信息学报， 2022， 36（12）： 74-84.（LIU Z G， ZHU Y， ZHAO H X， et al. Heterogeneous hypernetwork representation learning with the translation constraint ［J］. Journal of Chinese Information Processing， 2022， 36（12）： 74-84.）

[14] HONG S， ZHOU Z， ZIO E， et al. An adaptive method for health trend prediction of rotating bearings ［J］. Digital Signal Processing， 2014， 35： 117-123.

[15] MATHIOUDALKIS M， KOUDAS N. TwitterMonitor： trend detection over the twitter stream ［C］// Proceedings of the 29th ACM SIGMOD International Conference on Management of Data. New York： ACM， 2010： 1155-1158.

[16] JANNACH D， ZANKER M， FELFERNIG A， et al. Recommender Systems： An Introduction ［M］. New York： Cambridge University Press， 2010：1-10.

[17] BRETTO A. Hypergraph Theory： An Introduction ［M］. Cham： Springer， 2013： 43-49.

[18] 刘贞国，朱宇，刘连照，等.基于转化策略的异质超网络表示学习［J］.计算机应用研究， 2022， 39（11）： 3333-3339.（LIU Z G， ZHU Y， LIU L Z， et al. Heterogeneous hypernetwork representation learning with transformation strategy ［J］. Application Research of Computers， 2022， 39（11）： 3333-3339.）

[19] BORDES A， USUNIER N， GARCIA-DURÁN A. Translating embeddings for modeling multi-relational data ［C］// Proceedings of the 26th International Conference on Neural Information Processing Systems. Cham： Springer， 2013，2： 2787-2795.

[20] ZHENG V W， CAO B， ZHENG Y， et al. Collaborative filtering meets mobile recommendation： a user-centered approach ［C］// Proceedings of the 24th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2010： 236-241.

[21] HARPER F M， KONSTAN J A. The MovieLens datasets： history and context ［J］. ACM Transactions on Internet and Information Systems， 2016， 5（4）： 19.

[22] PEROZZI B， AL-RFOU R， SKIENA S. DeepWalk： online learning of social representations ［C］ // Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 701-710.

[23] GROVER A， LESKOVEC J. node2vec： scalable feature learning for networks ［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 855-864.

[24] DONG Y， CHAWLA N V， SWAMI A. metapath2vec： scalable representation learning for heterogeneous networks ［C］// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2017： 135-144.

[25] ZHAN L， JIA T. CoarSAS2hvec： heterogeneous information network embedding with balanced network sampling ［J］. Entropy， 2022， 24（2）： 276.

[26] HUANG J， LIU X， SONG Y. Hyper-path-based representation learning for hyper-networks ［C］// Proceedings of the 28th ACM International Conference on Information and Knowledge Management. New York： ACM， 2019： 449-458.

[27] FU G， YUAN B， DUAN Q， et al. Representation learning for heterogeneous information networks via embedding events ［C］// Proceedings of the 26th International Conference on Neural Information Processing Systems. Cham： Springer， 2019： 327-339.

[28] 杜航原，郝思聪，王文剑.结合图自编码器与聚类的半监督表示学习方法［J］. 计算机应用， 2022， 42（9）： 2643-2651.（DU H Y， HAO S C， WANG W J. Semi-supervised representation learning method combining graph auto-encoder and clustering ［J］. Journal of Computer Applications， 2022， 42（9）： 2643-2651.）

Heterogeneous hypernetwork representation learning method with hyperedge constraint

WANG Keke， ZHU Yu*， WANG Xiaoying， HUANG Jianqiang， CAO Tengfei

（，，810000，）

Compared with ordinary networks， hypernetworks have complex tuple relationships， namely hyperedges. However， most existing network representation learning methods cannot capture the tuple relationships. To solve the above problem， a Heterogeneous hypernetwork Representation learning method with Hyperedge Constraint （HRHC） was proposed. Firstly， a method combining clique extension and star extension was introduced to transform the heterogeneous hypernetwork into the heterogeneous network. Then， the meta-path walk method that was aware of semantic relevance among the nodes was introduced to capture the semantic relationships among the heterogeneous nodes. Finally， the tuple relationships among the nodes were captured by means of the hyperedge constraint to obtain high-quality node representation vectors. Experimental results on three real-world datasets show that， for the link prediction task， the proposed method obtaines good results on drug， GPS and MovieLens datasets. For the hypernetwork reconstruction task， when the hyperedge reconstruction ratio is more than 0.6， the ACCuracy （ACC） of the proposed method is better than the suboptimal method Hyper2vec（biased 2nd order random walks in Hyper-networks）， and the average ACC of the proposed method outperforms the suboptimal method， that is heterogeneous hypernetwork representation learning method with hyperedge constraint based on incidence graph （HRHC-incidence graph） by 15.6 percentage points on GPS dataset.

network representation; hypernetwork; hyperedge constraint; link prediction; hypernetwork reconstruction

This work is partially supported by National Natural Science Foundation of China （62166032）， Natural Science Foundation of Qinghai Province （2022-ZJ-961Q）.

WANG Keke， born in 1999， M. S. candidate. Her research interest is network representation learning.

ZHU Yu， born in 1986， Ph. D.， lecturer. His research interests include machine learning， network representation learning.

WANG Xiaoying， born in 1982， Ph. D.， professor. Her research interests include high-performance computing， green computing.

HUANG Jianqiang， born in 1985， Ph. D.， professor. His research interests include high-performance computing， performance analysis.

CAO Tengfei， born in 1987， Ph. D.， associate professor. His research interests include edge computing， privacy protection.

TP181

A

1001-9081（2023）12-3654-08

10.11772/j.issn.1001-9081.2022121908

2022⁃12⁃30；

2023⁃03⁃23；

2023⁃03⁃28。

国家自然科学基金资助项目（62166032）；青海省自然科学基金资助项目（2022⁃ZJ⁃961Q）。

王可可（1999—），女，河南濮阳人，硕士研究生，主要研究方向：网络表示学习；朱宇（1986—），男，山东菏泽人，副教授，博士，CCF会员，主要研究方向：机器学习、网络表示学习；王晓英（1982—），女，吉林双辽人，教授，博士，CCF高级会员，主要研究方向：高性能计算、绿色计算；黄建强（1985—），男，陕西西安人，教授，博士，CCF高级会员，主要研究方向：高性能计算、性能分析；曹腾飞（1987—），男，湖北钟祥人，副教授，博士，CCF高级会员，主要研究方向：边缘计算、隐私保护。