Link Prediction Driven by High-Order Relations in Complete Graph

Zhang Huijuan; Huang Qinyang; Hu Shiyan; Yang Qing; Zhang Jingwei

doi:10.7544/issn1000-1239.202221045

Journal of Computer Research and Development > 2024 > 61(7): 1825-1835. > DOI: 10.7544/issn1000-1239.202221045

Zhang Huijuan, Huang Qinyang, Hu Shiyan, Yang Qing, Zhang Jingwei. Link Prediction Driven by High-Order Relations in Complete Graph[J]. Journal of Computer Research and Development, 2024, 61(7): 1825-1835. DOI: 10.7544/issn1000-1239.202221045

Citation:

PDF (1269 KB)

Link Prediction Driven by High-Order Relations in Complete Graph

1.
Guangxi Key Laboratory of Trusted Software (Guilin University of Electronic Technology), Guilin, Guangxi 541004
2.
Guangxi Key Laboratory of Automatic Detecting Technology and Instruments (Guilin University of Electronic Technology), Guilin, Guangxi 541004
3.
School of Computer Science and Information Security, Guilin University of Electronic Technology, Guilin, Guangxi 541004

Funds: This work was supported by the National Natural Science Foundation of China (62267002, 62167002，61862013), Guangxi Key Research and Development Program (Guike AB22080047), Guangxi Key Laboratory of Trusted Software ( KX202317), and Guangxi Key Laboratory of Automatic Detecting Technology and Instruments (YQ21102).

More Information

Author Bio:
Zhang Huijuan: born in 1996. Master. Her main research interests include big data analysis and recommendation systems

Huang Qinyang: born in 1996. Master. His main research interest includes artificial intelligence

Hu Shiyan: born in 1998. Master. Her main research interests include recommendation systems and big data analysis

Yang Qing: born in 1976. Master, professor. Her main research interest includes intelligent information process and recommendation

Zhang Jingwei: born in 1977. PhD, professor. Member of CCF. His main research interests include big data management, analysis and smart applications
Received Date: December 29, 2022
Revised Date: November 23, 2023
Available Online: April 09, 2024

Graphical Abstract

Abstract

Abstract

Graph convolutional network (GCN) has been widely used in recommendation systems due to its unique advantages in processing graph data. GCN propagates node attribute information by exploiting the dependencies between nodes in the graph, which greatly improves the accuracy of node representation and thus improves recommendation performance. However, existing GCN-based recommendation methods still have difficulty in modeling deeper layers due to the over-smoothing problem, which limits the representation of higher-order relationships between users and items. To this end, we propose a novel link prediction method driven by high-order relations among items in complete graph (short for LinkCG). The LinkCG method utilizes a heterogeneous graph consisting of a user-item interaction graph and a global graph representing implicit item associations to predict user-item links. By directly modeling item associations based on user interactions, LinkCG captures higher-order relationships and mitigates the issue of data sparsity. In addition, unlike node embedding-based methods, LinkCG improves the training process and enhances recommendation accuracy by assigning link weights that represent the degree of item association. Experimental results on three publicly available datasets show that LinkCG method, as a non-deep learning model containing only two hyperparameters, provides better performance compared with the deep learning-based baseline methods. The application on social relationship data further demonstrates LinkCG can capture rich enough information about user preferences from their historical interaction items.
- recommendation system,
- link prediction,
- complete graph,
- high-order relations,
- associated relationship

FullText(HTML)

References (38)

References

[1]	Covington P, Adams J, Sargin E. Deep neural networks for YouTube recommendations[C] //Proc of the 10th ACM Conf on Recommender Systems. New York: ACM, 2016: 191−198
[2]	任豪,刘柏嵩,孙金杨,等. 基于时间和关系感知的图协同过滤跨域序列推荐[J]. 计算机研究与发展,2023,60(1):112−124 Ren Hao, Liu Baisong, Sun Jinyang, et al. A time and relation-aware graph collaborative filtering for cross-domain sequential recommendation[J]. Journal of Computer Research and Development, 2023, 60(1): 112−124(in Chinese)
[3]	黄若然,崔莉,韩传奇. 推荐系统中稀疏情景预测的特征-类别交互因子分解机[J]. 计算机研究与发展,2022,59(7):1553−1568 Huang Ruoran, Cui Li, Han Chuanqi. Feature-over-field interaction factorization machine for sparse contextualized prediction in recommender systems[J]. Journal of Computer Research and Development, 2022, 59(7): 1553−1568 (in Chinese)
[4]	Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30−37 doi: 10.1109/MC.2009.263
[5]	Wang Xiang, He Xiangnan, Wang Meng, et al. Neural graph collaborative filtering[C] //Proc of the 42nd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2019: 165−174
[6]	He Xiangnan, Deng Kuan, Wang Xiang, et al. LightGCN: Simplifying and powering graph convolution network for recommendation[C] //Proc of the 43rd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2020: 639−648
[7]	Fan Wenqi, Liu Xiaorui, Jin Wei, et al. Graph trend networks for recommendations[J]. arXiv preprint, arXiv: 2108.05552, 2021
[8]	Huang Zan, Li Xin, Chen H. Link prediction approach to collaborative filtering[C] //Proc of the 5th ACM/IEEE-CS Joint Conf on Digital Libraries. New York: ACM, 2005: 141−142
[9]	Chiluka N, Andrade N, Pouwelse J. A link prediction approach to recommendations in large-scale user-generated content systems[C] // Proc of the 33rd European Conf on IR Research. Berlin: Springer, 2011: 189−200
[10]	Salton G, McGill M. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1983
[11]	Leicht E A, Holme P, Newman M E J. Vertex similarity in networks[J]. Physical Review E, 2006, 73(2): 026120 doi: 10.1103/PhysRevE.73.026120
[12]	Baluja S, Seth R, Sivakumar D, et al. Video suggestion and discovery for YouTube: Taking random walks through the view graph[C] //Proc of the 17th Int Conf on World Wide Web. New York: ACM, 2008: 895−904
[13]	Eksombatchai C, Jindal P, Liu J Z, et al. Pixie: A system for recommending 3+ billion items to 200+ million users in real-time[C] //Proc of the 27th World Wide Web Conf. New York: ACM, 2018: 1775−1784
[14]	Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 701−710
[15]	Chen C M, Tsai M F, Lin Y C, et al. Query-based music recommendations via preference embedding[C]//Proc of the 10th ACM Conf on Recommender Systems. New York: ACM, 2016: 79−82
[16]	Yang J H, Chen C M, Wang C J, et al. HOP-rec: High-order proximity for implicit recommendation[C]// Proc of the 12th ACM Conf on Recommender Systems. New York: ACM, 2018: 140−144
[17]	Chen C M, Wang C J, Tsai M F, et al. Collaborative similarity embedding for recommender systems[C]// Proc of the 28th World Wide Web Conf. New York: ACM, 2019: 2637−2643
[18]	Tang Jian, Qu Meng, Wang Mingzhe, et al. Line: Large-scale information network embedding[C]//Proc of the 24th Int Conf on World Wide Web. New York: ACM, 2015: 1067−1077
[19]	Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[C/OL]//Proc of the 5th Int Conf on Learning Representations. 2017[2022-10-21].https://openreview.net/forum?id=SJU4ayYgl
[20]	Velickovic P, Cucurull G, Casanova A, et al. Graph attention networks[C/OL]//Proc of the 6th Int Conf on Learning Representations. 2018[2022-10-21].https://openreview.net/forum?id=rJXMpikCZ
[21]	Xu K, Hu Weihua, Leskovec J, et al. How powerful are graph neural networks[C/OL]//Proc of the 7th Int Conf on Learning Representations. 2019[2022-10-21].https://openreview.net/forum?id=ryGs6iA5Km
[22]	Yu Junliang, Yin Hongzhi, Li Jundong, et al. Self-supervised multi-channel hypergraph convolutional network for social recommendation[C]//Proc of the 30th Web Conf. New York: ACM, 2021: 413−424
[23]	Chang Jianxin, Gao Chen, Zheng Yu, et al. Sequential recommendation with graph neural networks[C]//Proc of the 44th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2021: 378−387
[24]	Wang Ziyang, Wei Wei, Cong Gao, et al. Global context enhanced graph neural networks for session-based recommendation[C] //Proc of the 43rd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2020: 169−178
[25]	Chen Lei, Wu Le, Hong Richang, et al. Revisiting graph based collaborative filtering: A linear residual graph convolutional network approach[C] //Proc of the 32nd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2020: 27−34
[26]	Liben-Nowell D, Kleinberg J. The link prediction problem for social networks[C]//Proc of the 12th Int Conf on Information and Knowledge Management. New York: ACM, 2003: 556−559
[27]	Zhang Muhan, Li Pan, Xia Yinglong, et al. Revisiting graph neural networks for link prediction[J]. arXiv preprint, arXiv: 2010.16103, 2020
[28]	Fu H M, Poirson P, Lee K S, et al. Revisiting neighborhood-based link prediction for collaborative filtering[C] // Proc of the 31st Web Conf. New York: ACM, 2022: 1009–1018
[29]	Anand R, Jeffrey D U. Mining of Massive Datasets[M]. Cambridge, UK: Cambridge University Press, 2011
[30]	Lin T H, Gao Chen, Li Yong. Cross: Cross-platform recommendation for social e-commerce[C] //Proc of the 42nd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2019: 515−524
[31]	Zhang Jun, Gao Chen, Jin Depeng, et al. Group-buying recommendation for social e-commerce[C] //Proc of the 37th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2021: 1536−1547
[32]	Wu Le, Sun Peijie, Fu Yanjie, et al. A neural influence diffusion model for social recommendation[C] //Proc of the 42nd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2019: 235−244
[33]	Jamali M, Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C] //Proc of the 4th ACM Conf on Recommender systems. New York: ACM, 2010: 135−142
[34]	Yang Liangwei, Liu Zhiwei, Dou Yingtong, et al. Consisrec: Enhancing GNN for social recommendation via consistent neighbor aggregation[C] //Proc of the 44th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2021: 2141−2145
[35]	Yu Junliang, Yin Hongzhi, Li Jundong, et al. Enhance social recommendation with adversarial graph convolutional networks[J]. arXiv preprint, arXiv: 2004.02340, 2020
[36]	Sachdeva N, Manco G, Ritacco E, et al. Sequential variational autoencoders for collaborative filtering[C] //Proc of the 12th Int Conf on Web Search and Data Mining. New York: ACM, 2019: 600−608
[37]	Chae D K, Kim J, Chau D H, et al. Ar-cf: Augmenting virtual users and items in collaborative filtering for addressing cold-start problems[C]//Proc of the 43rd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2020: 1251−1260
[38]	Zhu Zirui, Gao Chen, Chen Xu, et al. Inhomogeneous social recommendation with hypergraph convolutional networks[J]. arXiv preprint, arXiv: 2111.03344, 2021

[1]	Ren Jiarui, Zhang Haiyan, Zhu Menghan, Ma Bo. Embedding Learning Algorithm for Heterogeneous Network Based on Meta-Graph Convolution[J]. Journal of Computer Research and Development, 2022, 59(8): 1683-1693. DOI: 10.7544/issn1000-1239.20220063
[2]	Yue Hongzhou, He Shuilong, Wang Jing. Analysis of Group Users’ Relationship Based on TikTok Mutual Contacts[J]. Journal of Computer Research and Development, 2022, 59(4): 796-812. DOI: 10.7544/issn1000-1239.20200779
[3]	Du Yuefeng, Li Xiaoguang, Song Baoyan. Discovering Consistency Constraints for Associated Data on Heterogeneous Schemas[J]. Journal of Computer Research and Development, 2020, 57(9): 1939-1948. DOI: 10.7544/issn1000-1239.2020.20190570
[4]	Qian Yuhua, Zhang Mingxing, Cheng Honghong. Association Learning: A New Perspective of Mining Association[J]. Journal of Computer Research and Development, 2020, 57(2): 424-432. DOI: 10.7544/issn1000-1239.2020.20190281
[5]	Zhang Chao, Li Deyu. Interval-Valued Hesitant Fuzzy Graphs Decision Making with Correlations and Prioritization Relationships[J]. Journal of Computer Research and Development, 2019, 56(11): 2438-2447. DOI: 10.7544/issn1000-1239.2019.20180314
[6]	Wan Changxuan, You Yun, Jiang Tengjiao, Liu Xiping, Liao Guoqiong, Liu Dexi. Personalized Investment Recommendation in P2P Lending Considering Friend Relationships and Expected Utilities of Investors[J]. Journal of Computer Research and Development, 2018, 55(10): 2307-2320. DOI: 10.7544/issn1000-1239.2018.20170632
[7]	Song Pan, Jing Liping. Exploiting Label Relationships in Multi-Label Classification with Neural Networks[J]. Journal of Computer Research and Development, 2018, 55(8): 1751-1759. DOI: 10.7544/issn1000-1239.2018.20180362
[8]	Gan Lixin, Wan Changxuan, Liu Dexi, Zhong Qing, Jiang Tengjiao. Chinese Named Entity Relation Extraction Based on Syntactic and Semantic Features[J]. Journal of Computer Research and Development, 2016, 53(2): 284-302. DOI: 10.7544/issn1000-1239.2016.20150842
[9]	Yang Dan, Shen Derong, Nie Tiezheng, Yu Ge, Kou Yue. Entity Association Mining Algorithm CFRQ4A in Heterogeneous Information Spaces[J]. Journal of Computer Research and Development, 2014, 51(4): 895-904.
[10]	Zhang Weiguo, Yin Xia, and Wu Jianping. A Computation Method of Path Diversity Based on AS Relationships[J]. Journal of Computer Research and Development, 2012, 49(1): 167-173.

Cited By

Cited by

Periodical cited type(2)

1.	刘嘉宇，李贺，谷莹，袁翠敏，祝琳琳. 基于高阶交互网络的在线群体观点演化机理模型构建研究. 情报理论与实践. 2025(02): 124-135 .
2.	邱馨锐，赵文，吴长汶，张斐，杨朝阳，李灿东，周常恩. 刍议高阶关系在中医隐性知识显性化研究中的关键作用. 福建中医药. 2024(08): 24-26+30 .