چارچوب پیش‌بینی پیوند با استفاده از شبکه عصبی گرافی مبتنی بر زیرگراف

وحیدی پور, سید مهدی; کرمی, ریحانه

doi:10.22052/scj.2024.253458.1179

چارچوب پیش‌بینی پیوند با استفاده از شبکه عصبی گرافی مبتنی بر زیرگراف

نوع مقاله : مقاله پژوهشی

نویسندگان

دانشکده مهندسی برق و کامپیوتر، دانشگاه کاشان، کاشان، ایران

10.22052/scj.2024.253458.1179

چکیده

پیش‌بینی پیوند یکی از موضوع‌های مهم در تجزیه و تحلیل شبکه‌های پیچیده است. پیش‌بینی پیوند می‌تواند توسط یک رده‌بند انجام شود؛ به‌طوری‌که بردار ویژگی یک جفت گره، ورودی آن باشد. خروجی رده‌بند نشان می‌دهد که آیا میان آن جفت گره پیوندی پیش‌بینی می‌شود یا خیر (رده یک یا رده صفر). برای استخراج بردار ویژگی یک جفت گره می‌توان از شبکه‌های عصبی گرافی (GNN) استفاده نمود که در این صورت روش حل مساله پیش‌بینی پیوند مبتنی بر شبکه عصبی گرافی خواهد بود. در این مقاله، یک روش حل مساله پیش‌بینی پیوند مبتنی بر شبکه عصبی گرافی به نام Graph Auto Encoder (‌GAE) ‌به عنوان روش‌ پایه در نظر گرفته شده است. یکی از مشکل‌های اساسی در این روش‌ آن است که بردار ویژگی استخراج شده توسط شبکه عصبی گرافی به ازای جفت گره‌های متفاوت، می‌تواند یکسان باشد. برای رفع این مشکل، در این مقاله با استفاده از مفهوم زیرگراف روش پایه بهبود داده شده و چارچوب جدیدی با نام‌ Sub-Graph Auto Encoder (SGAE) پیشنهاد شده است. چارچوب‌ پیشنهادی بر اساس معیارهای مختلف ارزیابی و با روش‌ پایه‌ مقایسه شده است که نتایج نشان‌دهنده بهبود عملکرد آن‌ است. ‌به عنوان مثال روش SGAE ‌به طور متوسط نسبت به روش پایه GAE در معیارهای دقت، F1-Score، متوسط صحت و مساحت زیر نمودار صحت-فراخوانی، بهبود 5.5، 5، 5.75 و 5.87 را ایجاد کرده است.

کلیدواژه‌ها

موضوعات

هوش مصنوعی

عنوان مقاله [English]

Link prediction framework based on graph neural networks using subgraphs

نویسندگان [English]

Seyed Mehdi Vahidipour
Reyhane Karami

Electrical and Computer Engineering Department, University of Kashan, Kashan, Iran

چکیده [English]

Link prediction is one of the important topics in network analysis. Link prediction can be done by a classifier such that the feature vector of a pair of nodes is its input. The output of the classifier indicates whether a link is predicted between that pair of nodes (class one or class zero). To extract the feature vector of a pair of nodes, neural networks (GNN) can be used, in which case the method of solving the link prediction problem will be based on GNN. In this paper, a GNN-based link prediction problem solving method called GAE is considered as the basic method. One of the basic problems in this method is that the feature vector extracted by GNN can be the same for different pairs of nodes. To solve this problem, in this paper, using the concept of subgraph, the basic method is improved and a new framework called SGAE is proposed. The proposed framework has been compared with the basic methods based on different evaluation criteria, which shows its improved performance. For example, the SGAE method has improved 5.5, 5, 5.75 and 5.87 compared to the basic GAE method in terms of accuracy, F1-Score, average precision and area under the precision-recall curve.

کلیدواژه‌ها [English]

complex networks
Graph Neural Networks
link prediction
classification
subgraph
Graph Representation Learning

مراجع

[1] A. Kumar, S.S. Singh, K. Singh, and B. Biswas, “Link prediction techniques, applications, and performance: A survey,” Physica A: Stat. Mech. Appl., vol. 553, p. 124289, 2020, doi: 10.1016/j.physa.2020.124289.
[2] V. Martinez, F. Berzal, and J.-C. Cubero, “A survey of link prediction in complex networks,” ACM Comput. Surv., vol. 49, no. 4, pp. 1-33, 2016, doi: 10.1145/3012704.
[3] L. Lu and T. Zhou, “Link prediction in complex networks: A survey,” Physica A: Stat. Mech. Appl., vol. 390, no. 6, pp. 1150-1170, 2011, doi: 10.1016/j.physa.2010.11.027.
[4] M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” Adv. Neural Inf. Process. Syst., vol. 31, pp. 5171-5181, 2018, doi: 10.48550/arXiv.1802.09691.
[5] Y. Han, D. Guan, and W. Yuan, “Learning subgraph structure with LSTM for complex network link prediction,” in Proc. 15th Int. Conf. Adv. Data Mining Appl. (ADMA), 2019, pp. 34-47, doi: 10.1007/978-3-030-35231-8_3.
[6] A. Saxena, G. Fletcher, and M. Pechenizkiy, “NodeSim: Node similarity based network embedding for diverse link prediction,” EPJ Data Sci., vol. 11, no. 1, p. 24, 2022, doi: 10.1140/epjds/s13688-022-00336-8.
[7] J. Feng and S. Chen, “Link prediction based on orbit counting and graph auto-encoder,” IEEE Access, vol. 8, pp. 226773-226783, 2020, doi: 10.1109/ACCESS.2020.3045529.
[8] T.N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” arXiv preprint arXiv:1609.02907, 2016, doi: 10.48550/arXiv.1609.02907.
[9] T.N. Kipf and M. Welling, “Variational graph auto-encoders,” arXiv preprint arXiv:1611.07308, 2016, doi: 10.48550/arXiv.1611.07308.
[10] M. Zhang, P. Li, Y. Xia, K. Wang, and L. Jin, “Labeling trick: A theory of using graph neural networks for multi-node representation learning,” Adv. Neural Inf. Process. Syst., vol. 34, pp. 9061-9073, 2021.
[11] K. Teru, E. Denis, and W. Hamilton, “Inductive relation prediction by subgraph reasoning,” in Proc. Int. Conf. Mach. Learn., 2020, pp. 9448-9457, doi: 10.48550/arXiv.1911.06962.
[12] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proc. IEEE, vol. 86, no. 11, pp. 2278-2324, 1998, doi: 10.1109/5.726791.
[13] L. Li, S. Fang, S. Bai, S. Xu, J. Cheng, and X. Chen, “Effective link prediction based on community relationship strength,” IEEE Access, vol. 7, pp. 43233-43248, 2019, doi: 10.1109/access.2019.2908208.
[14] D. Jin et al., “A survey of community detection approaches: From statistical modeling to deep learning,” IEEE Trans. Knowl. Data Eng., vol. 35, pp. 1149-1170, 2021, doi: 10.1109/TKDE.2021.3104155.
[15] M. Gori, G. Monfardini, and F. Scarselli, “A new model for learning in graph domains,” in Proc. IEEE Int. Joint Conf. Neural Netw. (IJCNN), 2005, vol. 2, pp. 729-734, doi: 10.1109/IJCNN.2005.1555942.
[16] F. Scarselli, M. Gori, A.C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Trans. Neural Netw., vol. 20, no. 1, pp. 61-80, 2009, doi: 10.1109/TNN.2008.2005605.
[17] C. Gallicchio and A. Micheli, “Graph echo state networks,” in Proc. Int. Joint Conf. Neural Netw. (IJCNN), 2010, pp. 1-8, doi: 10.1109/IJCNN.2010.5596796.
[18] M. Zhang and Y. Chen, “Weisfeiler-Lehman Neural Machine for Link prediction,” in Proc. 23rd ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2017.
[19] K. Ragunathan, K. Selvarajah, and Z. Kobti, “Link prediction by analyzing common neighbors based subgraphs using convolutional neural network,” in Proc. Eur. Conf. Artif. Intell. (ECAI), 2020, pp. 1906-1913.
[20] K. Selvarajah, K. Ragunathan, Z. Kobti, and M. Kargar, “Dynamic network link prediction by learning effective subgraphs using CNN-LSTM,” in Proc. Int. Joint Conf. Neural Netw. (IJCNN), 2020, pp. 1-8, doi: 10.1109/IJCNN48605.2020.9207301.
[21] Y. Freund and R.E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” J. Comput. Syst. Sci., vol. 55, no. 1, pp. 119-139, 1997, doi: 10.1006/jcss.1997.1504.
[22] Y. Wang and L. Ming, “Global path link prediction method based on improved resource allocation,” J. Phys.: Conf. Ser., vol. 2522, no. 1, p. 012023, 2023, doi: 10.1088/1742-6596/2522/1/012023.
[23] J. Zhu et al., “SpotTarget: Rethinking the effect of target edges for link prediction in graph neural networks,” arXiv preprint arXiv:2306.00899, 2023, doi: 10.48550/arXiv.2306.00899.
[24] N.K. Ahmed, J. Neville, R.A. Rossi, and N. Duffield, “Efficient graphlet counting for large networks,” in Proc. IEEE Int. Conf. Data Mining (ICDM), 2015, pp. 1-10, doi: 10.1109/ICDM.2015.141.
[25] K. Abbas et al., “Application of network link prediction in drug discovery,” BMC Bioinf., vol. 22, no. 1, p. 187, Apr. 2021, doi: 10.1186/s12859-021-04082-y.
[26] S. Scellato, A. Noulas, and C. Mascolo, “Exploiting place features in link prediction on location-based social networks,” in Proc. 17th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2011, pp. 1046-1054, doi: 10.1145/2020408.2020575.
[27] X. Xian et al., “Generative graph neural networks for link prediction,” arXiv preprint arXiv:2301.00169, 2022, doi: 10.48550/arXiv.2301.00169.
[28] W. Gu, F. Gao, X. Lou, and J. Zhang, “Link prediction via graph attention network,” arXiv preprint arXiv:1910.04807, 2019, doi: 10.48550/arXiv.1910.04807.