基于有向超图自适应卷积的链接预测模型

doi:10.11772/j.issn.1001-9081.2023121847

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (1): 15-23.DOI: 10.11772/j.issn.1001-9081.2023121847

基于有向超图自适应卷积的链接预测模型

赵文博¹^,², 马紫彤¹^,², 杨哲¹^,²()

^1.苏州大学计算机科学与技术学院，江苏苏州 215008
^2.江苏省计算机信息处理技术重点实验室（苏州大学），江苏苏州 215006

收稿日期:2024-01-04 修回日期:2024-03-12 接受日期:2024-03-15 发布日期:2024-03-28 出版日期:2025-01-10
通讯作者: 杨哲
作者简介:赵文博（1998—），男，安徽淮北人，硕士研究生，CCF会员，主要研究方向：图机器学习、推荐系统；
马紫彤（1999—），女，江西赣州人，硕士研究生，CCF会员，主要研究方向：图表示学习、深度学习、推荐系统；
基金资助:
国家自然科学基金资助项目(62272332);教育部产学合作协同育人项目(220606363154256)

Link prediction model based on directed hypergraph adaptive convolution

Wenbo ZHAO¹^,², Zitong MA¹^,², Zhe YANG¹^,²()

^1.School of Computer Science and Technology，Soochow University，Suzhou Jiangsu 215008，China
^2.Jiangsu Provincial Key Laboratory for Computer Information Processing Technology （Soochow University），Suzhou Jiangsu 215006，China

Received:2024-01-04 Revised:2024-03-12 Accepted:2024-03-15 Online:2024-03-28 Published:2025-01-10
Contact: Zhe YANG
About author:ZHAO Wenbo， born in 1998， M. S. candidate. His research interests include graph machine learning， recommender systems.
MA Zitong， born in 1999， M. S. candidate. Her research interests include graph representation learning， deep learning， recommender systems.
Supported by:
National Natural Science Foundation of China(62272332);Ministry of Education’s Collaborative Education Program on Industry and Education(220606363154256)

摘要/Abstract

摘要：

图神经网络（GNN）为链接预测提供了多样化的解决方案，但由于普通图的结构限制，目前的相关模型在充分利用顶点间的高阶及不对称信息方面存在明显的不足。针对以上问题，提出一种基于有向超图自适应卷积的链接预测模型。首先，使用有向超图结构更充分地表示顶点间的高阶和方向信息，兼具超图和有向图的优势；其次，有向超图自适应卷积采用自适应信息传播方式替代传统有向超图中的定向信息传播方式，从而解决了有向超边尾部顶点不能有效更新嵌入的问题，同时解决多层卷积导致的顶点过度平滑问题。在Citeseer数据集上基于显式顶点特征的实验结果显示，在链接预测任务上，相较于有向超图神经网络（DHNN）模型，所提模型的ROC （Receiver Operating Characteristic）曲线下面积（AUC）指标提升了2.23个百分点，平均精度（AP）提升了1.31个百分点。因此，所提模型可以充分表达顶点间的关系，并有效提高链接预测任务的性能。

关键词: 图神经网络, 有向超图, 链接预测, 超图卷积, 表示学习, 自适应卷积

Abstract:

Although diverse solutions for link prediction have been provided by Graph Neural Networks （GNN）， the recent models have significant shortcomings in fully utilizing high-order and asymmetric information between vertices caused by the structural constraints of ordinary graphs. To address the above issues， a link prediction model based on directed hypergraph adaptive convolution was proposed. Firstly， the directed hypergraph structure was employed to represent high-order and directional information between vertices more sufficiently， possessing advantages of both hypergraphs and directed graphs. Secondly， an adaptive information propagation method was adopted by directed hypergraph adaptive convolution to replace the directional information propagation method in traditional directed hypergraphs， thereby solving the problem of ineffective updating of embeddings for tail vertices of directed hyperedges， and solving the problem of excessive smoothing of vertices caused by multi-layer convolution. Experimental results based on explicit vertex features on Citeseer dataset show that the proposed model achieves a 2.23 percentage points increase in the Area Under the ROC （Receiver Operating Characteristic） Curve （AUC） and a 1.31 percentage points increase in Average Precision （AP） compared to the Directed Hypergraph Neural Network （DHNN） model in link prediction task. Therefore， it can be concluded that this model expresses the relationships between vertices adequately and improves the accuracy of link prediction task effectively.

Key words: Graph Neural Network (GNN), directed hypergraph, link prediction, hypergraph convolution, representation learning, adaptive convolution

中图分类号:

TP391.4

赵文博, 马紫彤, 杨哲. 基于有向超图自适应卷积的链接预测模型[J]. 计算机应用, 2025, 45(1): 15-23.

Wenbo ZHAO, Zitong MA, Zhe YANG. Link prediction model based on directed hypergraph adaptive convolution[J]. Journal of Computer Applications, 2025, 45(1): 15-23.

图/表 12

表1 主要符号及其含义

Tab. 1 Main symbols and their meanings

符号	含义
$h v$ 、 $h e$	顶点及有向超边的特征向量
$H t a i l$ 、 $H h e a d$	有向超图尾部、头部关联矩阵
$X v ∈ R n × C 1$	有向超图顶点特征矩阵
$X e ∈ R m × C 1$	有向超图超边特征矩阵
$D v ∈ R n × n$	顶点的度矩阵
$D e ∈ R m × m$	有向超边的度矩阵
$W η$ 、 $W λ$	自适应因子对角矩阵
$r$ 、 $R$	顶点嵌入向量、顶点嵌入矩阵
$A$	图邻接矩阵
$G$ 、 $V$ 、 $E$	有向超图、顶点集、超边集
$α$ 、 $β$ 、 $λ$ 、 $η$	自适应因子
$n$ 、 $m$ 、 $C 1$ 、 $C 2$	矩阵维度
$s$ 、 $L$	预测分数、模型损失
$0$ 、 $I$	零矩阵、单位矩阵
$g$	顶点嵌入初始化操作
$F$	有向超图自适应卷积运算
$σ$	激活函数

表1 主要符号及其含义

Tab. 1 Main symbols and their meanings

符号	含义
$h v$ 、 $h e$	顶点及有向超边的特征向量
$H t a i l$ 、 $H h e a d$	有向超图尾部、头部关联矩阵
$X v ∈ R n × C 1$	有向超图顶点特征矩阵
$X e ∈ R m × C 1$	有向超图超边特征矩阵
$D v ∈ R n × n$	顶点的度矩阵
$D e ∈ R m × m$	有向超边的度矩阵
$W η$ 、 $W λ$	自适应因子对角矩阵
$r$ 、 $R$	顶点嵌入向量、顶点嵌入矩阵
$A$	图邻接矩阵
$G$ 、 $V$ 、 $E$	有向超图、顶点集、超边集
$α$ 、 $β$ 、 $λ$ 、 $η$	自适应因子
$n$ 、 $m$ 、 $C 1$ 、 $C 2$	矩阵维度
$s$ 、 $L$	预测分数、模型损失
$0$ 、 $I$	零矩阵、单位矩阵
$g$	顶点嵌入初始化操作
$F$	有向超图自适应卷积运算
$σ$	激活函数

图1 有向超图及其关联矩阵

Fig. 1 Directed hypergraph and its incidence matrix

图2 链接预测模型及有向超图的自适应卷积过程

Fig. 2 Adaptive convolutional process and link prediction model of directed hypergraphs

表2 数据集的统计信息

Tab. 2 Statistical information of datasets

数据集	顶点数	边数	数据类型
Amazon	13 752	287 209	交易关系
Citeseer^*	3 312	1 079	引用关系
Cora^*	2 708	1 579	引用关系
DBLP	43 413	22 535	共同作者
Survey	2 539	12 969	社交网络

图3 数据集中的有向图和有向超图结构示意图

Fig. 3 Schematic diagrams of directed graph and directed hypergraph structure in datasets

表3 基于显式顶点特征的链接预测实验结果 ( %)

Tab. 3 Experimental results of link prediction based on explicit vertex features

模型	Citeseer		Cora
模型	AUC	AP	AUC	AP
MLP	75.14	76.51	79.71	78.28
GCN	88.29	89.31	91.97	90.24
GraphSAGE	87.17	88.87	93.14	92.98
GAT	82.42	84.43	91.36	91.21
DiGCN	93.06	93.92	93.28	93.21
DiGAE	90.79	89.88	93.68	93.27
HGNN	92.83	92.51	82.93	82.33
HNHN	88.35	89.55	92.24	92.35
HGNN+	93.09	93.47	93.65	93.15
DHNN	93.16	94.03	93.71	93.29
DHAC	95.39	95.34	93.94	93.75

表4 基于隐式顶点特征的链接预测实验结果 ( %)

Tab. 4 Experimental results of link prediction based on implicit vertex features

模型	Amazon		Citeseer		Cora		DBLP		Survey
模型	AUC	AP	AUC	AP	AUC	AP	AUC	AP	AUC	AP
MLP	81.49	79.73	58.26	61.53	64.93	66.07	75.63	74.75	73.03	75.81
GCN	90.35	89.52	67.91	70.33	74.59	76.32	89.30	87.76	86.16	87.21
GraphSAGE	93.16	93.29	75.71	76.61	85.74	83.95	91.29	89.10	87.32	85.37
GAT	91.15	90.45	73.93	77.59	82.62	84.65	95.32	95.79	91.11	91.64
DiGCN	93.21	92.17	77.11	80.27	87.61	87.54	86.93	84.05	90.24	89.89
DiGAE	91.82	84.94	72.57	75.12	82.64	83.31	88.97	87.02	86.16	84.02
HGNN	92.38	91.43	77.49	79.16	87.33	86.29	88.61	86.96	84.62	87.61
HNHN	93.19	93.42	77.80	78.51	85.81	84.71	71.74	71.13	80.51	87.52
HGNN+	90.99	89.41	79.55	81.96	90.07	90.75	89.89	88.62	85.83	88.98
DHNN	93.13	92.76	80.81	80.41	89.56	88.56	88.42	87.51	90.37	89.47
DHAC	95.82	95.19	81.69	83.35	91.43	91.54	95.34	95.40	93.46	93.81

图4 不同卷积层数的AUC

Fig. 4 AUC with different convolutional layers

图5 不同卷积层数的AP

Fig. 5 AP with different convolutional layers

图6 不同卷积方向的AUC

Fig. 6 AUC with different convolutional directions

图7 不同卷积方向的AP

Fig. 7 AP with different convolutional directions

表5 嵌入维度实验结果

Tab. 5 Embedding dimension experimental results

嵌入维度	Citeseer		Cora
嵌入维度	AUC/%	AP/%	AUC/%	AP/%
4	76.91	77.97	87.45	86.97
8	78.52	80.61	90.24	89.10
16	80.26	81.81	91.18	90.54
32	81.48	82.79	91.36	91.12
64	81.69	83.35	91.43	91.54
128	81.83	83.51	90.93	92.33
256	81.35	83.55	91.24	91.35

参考文献 43

1	LIBEN-NOWELL D， KLEINBERG J. The link prediction problem for social networks ［C］// Proceedings of the 12th International Conference on Information and Knowledge Management. New York： ACM， 2003： 556-559.
2	ZHANG M， CHEN Y. Link prediction based on graph neural networks ［C］// Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2018： 5171-5181.
3	GILMER J， SCHOENHOLZ S S， RILEY P F， et al. Neural message passing for quantum chemistry ［C］// Proceedings of the 34th International Conference on Machine Learning. New York： JMLR.org， 2017： 1263-1272.
4	MICHELI A. Neural network for graphs： a contextual constructive approach ［J］. IEEE Transactions on Neural Networks， 2009， 20（3）： 498-511.
5	NIEPERT M， AHMED M， KUTZKOV K. Learning convolutional neural networks for graphs ［C］// Proceedings of the 33rd International Conference on International Conference on Machine Learning. New York： JMLR.org， 2016： 2014-2023.
6	BRUNA J， ZAREMBA W， SZLAM A， et al. Spectral networks and locally connected networks on graphs ［EB/OL］. ［2023-07-14］. .
7	DEFFERRARD M， BRESSON X， VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering ［C］// Proceedings of the 30th International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2016： 3844-3852.
8	KIPF T N， WELLING M. Semi-supervised classification with graph convolutional networks ［EB/OL］. ［2023-07-02］. .
9	BRETTO A. Hypergraph theory： an introduction， MATHENGIN ［M］. Cham： Springer， 2013.
10	ZHOU D， HUANG J， SCHÖLKOPF B. Learning with hypergraphs： clustering， classification， and embedding ［C］// Proceedings of the 19th Annual Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2006： 1601-1608.
11	FENG Y， YOU H， ZHANG Z， et al. Hypergraph neural networks ［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2019： 3558-3565.
12	GAO Y， FENG Y， JI S， et al. HGNN+： general hypergraph neural networks ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2023， 45（3）： 3181-3199.
13	OU M， CUI P， PEI J， et al. Asymmetric transitivity preserving graph embedding ［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 1105-1114.
14	ZHOU D， HUANG J， SCHÖLKOPF B. Learning from labeled and unlabeled data on a directed graph ［C］// Proceedings of the 22nd International Conference on Machine Learning. New York： ACM， 2005： 1036-1043.
15	TONG Z， LIANG Y， SUN C， et al. Digraph inception convolutional networks ［C］// Proceedings of the 34th International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2020： 17907-17918.
16	KOLLIAS G， KALANTZIS V， IDÉ T， et al. Directed graph auto-encoders ［C］// Proceedings of the 36th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2022： 7211-7219.
17	MA Y， HAO J， YANG Y， et al. Spectral-based graph convolutional network for directed graphs ［EB/OL］. ［2023-04-21］. .
18	KAMPFFMEYER M， CHEN Y， LIANG X， et al. Rethinking knowledge graph propagation for zero-shot learning ［C］// Proceedings of the 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2019： 11479-11488.
19	GALLO G， LONGO G， PALLOTTINO S， et al. Directed hypergraphs and applications ［J］. Discrete Applied Mathematics， 1993， 42（2/3）： 177-201.
20	XIAO G， LIAO J， TAN Z， et al. A two-stage framework for directed hypergraph link prediction ［J］. Mathematics， 2022， 10（14）： No.2372.
21	XIAO G， LIAO J， TAN Z， et al. Hyperbolic directed hypergraph-based reasoning for multi-hop KBQA ［J］. Mathematics， 2022， 10（20）： No.3905.
22	TRAN L H， TRAN L H. Directed hypergraph neural network ［EB/OL］. ［2023-09-15］. .
23	HAMMOND D K， VANDERGHEYNST P， GRIBONVAL R. Wavelets on graphs via spectral graph theory ［J］. Applied and Computational Harmonic Analysis， 2011， 30（2）： 129-150.
24	HAMILTON W， YING R， LESKOVEC J. Inductive representation learning on large graphs ［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2017： 1025-1035.
25	VELIČKOVIĆ P， CUCURULL G， CASANOVA A， et al. Graph attention networks ［EB/OL］. ［2023-01-11］. .
26	MORRIS C， RITZERT M， FEY M， et al. Weisfeiler and Leman go neural： higher-order graph neural networks ［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2019： 4602-4609.
27	HUANG J， YANG J. UniGNN： a unified framework for graph and hypergraph neural networks ［C］// Proceedings of the 30th International Joint Conference on Artificial Intelligence. California： ijcai.org， 2021： 2563-2569.
28	徐良奎，杨哲，吴国荣，等.多通道Laplacian矩阵融合的超图直推学习模型［J］.小型微型计算机系统， 2023， 44（11）： 2566-2575.
	XU L K， YANG Z， WU G R， et al. Hypergraph transduction learning model based on multi-channel Laplacian matrix fusion ［J］. Journal of Chinese Computer Systems， 2023， 44（11）： 2566-2575.
29	DONG Y， SAWIN W， BENGIO Y. HNHN： hypergraph networks with hyperedge neurons ［EB/OL］. ［2023-08-25］. .
30	BAI S， ZHANG F， TORR P H S. Hypergraph convolution and hypergraph attention ［J］. Pattern Recognition， 2021， 110： No.107637.
31	ZHANG X， HE Y， BRUGNONE N， et al. MagNet： a neural network for directed graphs ［C］// Proceedings of the 35th International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2021： 27003-27015.
32	AUSIELLO G， LAURA L. Directed hypergraphs： introduction and fundamental algorithms — a survey ［J］. Theoretical Computer Science， 2017， 658（Pt B）： 293-306.
33	HE K， ZHANG X， REN S， et al. Delving deep into rectifiers： surpassing human-level performance on ImageNet classification ［C］// Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway： IEEE， 2015： 1026-1034.
34	GLOROT X， BORDES A， BENGIO Y. Deep sparse rectifier neural networks ［C］// Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2011： 315-323.
35	RENDLE S， FREUDENTHALER C， GANTNER Z， et al. BPR： Bayesian personalized ranking from implicit feedback ［C］// Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. Arlington， VA： AUAI Press， 2009： 452-461.
36	SHCHUR O， MUMME M， BOJCHEVSKI A， et al. Pitfalls of graph neural network evaluation ［EB/OL］. ［2022-11-21］. .
37	ROSSI R A， AHMED N K. The network data repository with interactive graph analytics and visualization ［C］// Proceedings of the 29th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2015： 4292-4293.
38	SEN P， NAMATA G， BILGIC M， et al. Collective classification in network data ［J］. AI Magazine， 2008， 29（3）： 93-106.
39	TANG J， ZHANG J， YAO L， et al. ArnetMiner： extraction and mining of academic social networks ［C］// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2008： 990-998.
40	MOODY J. Peer influence groups： identifying dense clusters in large networks ［J］. Social Networks， 2001， 23（4）： 261-283.
41	LOBO J M， JIMÉNEZ-VALVERDE A， REAL R. AUC： a misleading measure of the performance of predictive distribution models ［J］. Global Ecology and Biogeography， 2008， 17（2）： 145-151.
42	EVERINGHAM M， VAN GOOL L， WILLIAMS C K I， et al. The PASCAL Visual Object Classes （VOC） challenge ［J］. International Journal of Computer Vision， 2010， 88（2）： 303-338.
43	KINGMA D P， BA J L. Adam： a method for stochastic optimization. ［EB/OL］. ［2021-03-11］. .

[1]	余肖生, 王智鑫. 基于多层次图对比学习的序列推荐模型[J]. 《计算机应用》唯一官方网站, 2025, 45(1): 106-114.
[2]	程子栋, 李鹏, 朱枫. 物联网威胁情报知识图谱中潜在关系的挖掘[J]. 《计算机应用》唯一官方网站, 2025, 45(1): 24-31.
[3]	杨兴耀, 陈羽, 于炯, 张祖莲, 陈嘉颖, 王东晓. 结合自我特征和对比学习的推荐模型[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2704-2710.
[4]	李顺勇, 李师毅, 胥瑞, 赵兴旺. 基于自注意力融合的不完整多视图聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2696-2703.
[5]	唐廷杰, 黄佳进, 秦进. 基于图辅助学习的会话推荐[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2711-2718.
[6]	杨航, 李汪根, 张根生, 王志格, 开新. 基于图神经网络的多层信息交互融合算法用于会话推荐[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2719-2725.
[7]	杜郁, 朱焱. 构建预训练动态图神经网络预测学术合作行为消失[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2726-2731.
[8]	杨帆, 邹窈, 朱明志, 马振伟, 程大伟, 蒋昌俊. 基于图注意力Transformer神经网络的信用卡欺诈检测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2634-2642.
[9]	杨莹, 郝晓燕, 于丹, 马垚, 陈永乐. 面向图神经网络模型提取攻击的图数据生成方法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2483-2492.
[10]	王清, 赵杰煜, 叶绪伦, 王弄潇. 统一框架的增强深度子空间聚类方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 1995-2003.
[11]	黎施彬, 龚俊, 汤圣君. 基于Graph Transformer的半监督异配图表示学习模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1816-1823.
[12]	林欣蕊, 王晓菲, 朱焱. 基于局部扩展社区发现的学术异常引用群体检测[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1855-1861.
[13]	汪炅, 唐韬韬, 贾彩燕. 无负采样的正样本增强图对比学习推荐方法PAGCL[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1485-1492.
[14]	郭洁, 林佳瑜, 梁祖红, 罗孝波, 孙海涛. 基于知识感知和跨层次对比学习的推荐方法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1121-1127.
[15]	徐大鹏, 侯新民. 基于网络结构设计的图神经网络特征选择方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 663-670.

基于有向超图自适应卷积的链接预测模型

Link prediction model based on directed hypergraph adaptive convolution

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 43

相关文章 15

编辑推荐

Metrics