Link prediction model based on directed hypergraph adaptive convolution

doi:10.11772/j.issn.1001-9081.2023121847

Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (1): 15-23.DOI: 10.11772/j.issn.1001-9081.2023121847

• Artificial intelligence • Previous Articles Next Articles

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)

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

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

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

通讯作者: 杨哲
作者简介:赵文博（1998—），男，安徽淮北人，硕士研究生，CCF会员，主要研究方向：图机器学习、推荐系统；
马紫彤（1999—），女，江西赣州人，硕士研究生，CCF会员，主要研究方向：图表示学习、深度学习、推荐系统；
基金资助:
国家自然科学基金资助项目(62272332);教育部产学合作协同育人项目(220606363154256)

Abstract

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

摘要：

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

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

CLC Number:

TP391.4

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.

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

Figures/Tables 12

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$	有向超图自适应卷积运算
$σ$	激活函数

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$	有向超图自适应卷积运算
$σ$	激活函数

Fig. 1 Directed hypergraph and its incidence matrix

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

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	社交网络

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

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

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

Fig. 4 AUC with different convolutional layers

Fig. 5 AP with different convolutional layers

Fig. 6 AUC with different convolutional directions

Fig. 7 AP with different convolutional directions

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

References 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]	Zidong CHENG, Peng LI, Feng ZHU. Potential relation mining in internet of things threat intelligence knowledge graph [J]. Journal of Computer Applications, 2025, 45(1): 24-31.
[2]	Shunyong LI, Shiyi LI, Rui XU, Xingwang ZHAO. Incomplete multi-view clustering algorithm based on self-attention fusion [J]. Journal of Computer Applications, 2024, 44(9): 2696-2703.
[3]	Yu DU, Yan ZHU. Constructing pre-trained dynamic graph neural network to predict disappearance of academic cooperation behavior [J]. Journal of Computer Applications, 2024, 44(9): 2726-2731.
[4]	Tingjie TANG, Jiajin HUANG, Jin QIN. Session-based recommendation with graph auxiliary learning [J]. Journal of Computer Applications, 2024, 44(9): 2711-2718.
[5]	Tingjie TANG, Jiajin HUANG, Jin QIN, Hui LU. Session-based recommendation based on graph co-occurrence enhanced multi-layer perceptron [J]. Journal of Computer Applications, 2024, 44(8): 2357-2364.
[6]	Shibin LI, Jun GONG, Shengjun TANG. Semi-supervised heterophilic graph representation learning model based on Graph Transformer [J]. Journal of Computer Applications, 2024, 44(6): 1816-1823.
[7]	Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861.
[8]	Jie GUO, Jiayu LIN, Zuhong LIANG, Xiaobo LUO, Haitao SUN. Recommendation method based on knowledge‑awareness and cross-level contrastive learning [J]. Journal of Computer Applications, 2024, 44(4): 1121-1127.
[9]	Dapeng XU, Xinmin HOU. Feature selection method for graph neural network based on network architecture design [J]. Journal of Computer Applications, 2024, 44(3): 663-670.
[10]	Beijing ZHOU, Hairong WANG, Yimeng WANG, Lisi ZHANG, He MA. Recommendation method using knowledge graph embedding propagation [J]. Journal of Computer Applications, 2024, 44(10): 3252-3259.
[11]	Yunhua ZHU, Bing KONG, Lihua ZHOU, Hongmei CHEN, Chongming BAO. Multi-view clustering network guided by graph contrastive learning [J]. Journal of Computer Applications, 2024, 44(10): 3267-3274.
[12]	Yirui HUANG, Junwei LUO, Jingqiang CHEN. Multi-modal dialog reply retrieval based on contrast learning and GIF tag [J]. Journal of Computer Applications, 2024, 44(1): 32-38.
[13]	Wei TONG, Liyang HE, Rui LI, Wei HUANG, Zhenya HUANG, Qi LIU. Efficient similar exercise retrieval model based on unsupervised semantic hashing [J]. Journal of Computer Applications, 2024, 44(1): 206-216.
[14]	Chunlei WANG, Xiao WANG, Kai LIU. Multimodal knowledge graph representation learning： a review [J]. Journal of Computer Applications, 2024, 44(1): 1-15.
[15]	Runchao PAN, Qishan YU, Hongfei XIONG, Zhihui LIU. Collaborative recommendation algorithm based on deep graph neural network [J]. Journal of Computer Applications, 2023, 43(9): 2741-2746.

Link prediction model based on directed hypergraph adaptive convolution

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 43

Related Articles 15

Recommended Articles

Metrics