An Efficient Bet-GCN Approach for Link Prediction.

Rahul Saxena; Spandan Pankaj Patil; Atul Kumar Verma; Mahipal Jadeja; Pranshu Vyas; Vikrant Bhateja; Jerry Chun Wei Lin

doi:10.9781/ijimai.2023.02.001

Authors

Rahul Saxena Malaviya National Institute of Technology Jaipur
Spandan Pankaj Patil Malaviya National Institute of Technology Jaipur
Atul Kumar Verma Malaviya National Institute of Technology Jaipur
Mahipal Jadeja Malaviya National Institute of Technology Jaipur
Pranshu Vyas Malaviya National Institute of Technology Jaipur
Vikrant Bhateja Veer Bahadur Singh Purvanchal University
Jerry Chun Wei Lin Western Norway University of Applied Sciences

DOI:

https://doi.org/10.9781/ijimai.2023.02.001

Keywords:

Graph Convolution Network (GCN), Graph Theory, Link Prediction, Network Centrality, Social Network

Abstract

The task of determining whether or not a link will exist between two entities, given the current position of the network, is called link prediction. The study of predicting and analyzing links between entities in a network is emerging as one of the most interesting research areas to explore. In the field of social network analysis, finding mutual friends, predicting the friendship status between two network individuals in the near future, etc., contributes significantly to a better understanding of the underlying network dynamics. The concept has many applications in biological networks, such as finding possible connections (possible interactions) between genes and predicting protein-protein interactions. Apart from these, the concept has applications in many other areas of network science. Exploration based on Graph Neural Networks (GNNs) to accomplish such tasks is another focus that is attracting a lot of attention these days. These approaches leverage the strength of the structural information of the network along with the properties of the nodes to make efficient predictions and classifications. In this work, we propose a network centrality based approach combined with Graph Convolution Networks (GCNs) to predict the connections between network nodes. We propose an idea to select training nodes for the model based on high edge betweenness centrality, which improves the prediction accuracy of the model. The study was conducted using three benchmark networks: CORA, Citeseer, and PubMed. The prediction accuracies for these networks are: 95.08%, 95.07%, and 95.3%. The performance of the model is comprehensive and comparable to the other prior art methods and studies. Moreover, the performance of the model is evaluated with 90.13% for WikiCS and 87.7% for Amazon Product network to show the generalizability of the model. The paper discusses in detail the reason for the improved predictive ability of the model both theoretically and experimentally. Our results are generalizable and our model has the potential to provide good results for link prediction tasks in any domain.

Downloads

Download data is not yet available.

References

M. Sun, J. Chen, Y. Tian, Y. Yan, “The impact of online reviews in the presence of customer returns,” International Journal of Production Economics, vol. 232, p. 107929, 2021, doi: 10.1016/j.ijpe.2020.107929.

M. S. Ullal, C. Spulbar, I. T. Hawaldar, V. Popescu, R. Birau, “The impact of online reviews on e-commerce sales in india: A case study,” Economic Research- Ekonomska Istraživanja, vol. 34, no. 1, pp. 2408–2422, 2021, doi: 10.1080/1331677X.2020.1865179.

M. Caro-Martínez, G. Jiménez-Díaz, J. A. Recio-García, “Local model-agnostic explanations for black- box recommender systems using interaction graphs and link prediction techniques,” International Journal of Interactive Multimedia and Artificial Intelligence, pp. 1–11, 2021, doi: 10.9781/ijimai.2021.12.001.

D. Medel, C. González-González, S. V. Aciar, “Social relations and methods in recommender systems: A systematic review,” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 7, no. 4, pp. 7–17, 2022, doi: 10.9781/ijimai.2021.12.004.

N. N. Daud, S. H. Ab Hamid, M. Saadoon, F. Sahran, N. B. Anuar, “Applications of link prediction in social networks: A review,” Journal of Network and Computer Applications, vol. 166, p. 102716, 2020, doi: 10.1016/j.jnca.2020.102716.

S. Sledzieski, R. Singh, L. Cowen, B. Berger, “Sequence- based prediction of protein-protein interactions: a structure-aware interpretable deep learning model,” bioRxiv, 2021, doi: 10.1016/j.cels.2021.08.010.

M. Lim, A. Abdullah, N. Jhanjhi, M. K. Khan, M. Supramaniam, “Link prediction in time-evolving criminal network with deep reinforcement learning technique,” IEEE Access, vol. 7, pp. 184797–184807, 2019, doi: 10.1109/ACCESS.2019.2958873.

H. Huang, J. Tang, L. Liu, J. Luo, X. Fu, “Triadic closure pattern analysis and prediction in social networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 12, pp. 3374–3389, 2015, doi: 10.1109/ TKDE.2015.2453956.

M. S. Granovetter, “The strength of weak ties,” American journal of sociology, vol. 78, no. 6, pp. 1360–1380, 1973.

Y. Bi, W. Wu, L. Wang, “Community expansion in social network,” in International Conference on Database Systems for Advanced Applications, 2013, pp. 41–55, Springer.

E. Abbe, A. S. Bandeira, G. Hall, “Exact recovery in the stochastic block model,” IEEE Transactions on information theory, vol. 62, no. 1, pp. 471–487, 2015, doi: 10.1109/TIT.2015.2490670.

C. Matias, V. Miele, “Statistical clustering of temporal networks through a dynamic stochastic block model,” Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 79, no. 4, pp. 1119–1141, 2017.

A. K. Gupta, N. Sardana, “Significance of clustering coefficient over jaccard index,” in The International Conference on Contemporary Computing, 2015, pp. 463–466, IEEE.

D. Liben-Nowell, J. Kleinberg, “The link-prediction problem for social networks,” Journal of the American society for information science and technology, vol. 58, no. 7, pp. 1019–1031, 2007, doi: 10.1145/956863.956972.

S. Cohen, B. Kimelfeld, G. Koutrika, “A survey on proximity measures for social networks,” in Search computing, 2012, pp. 191–206, Springer.

S. Zhang, H. Tong, J. Xu, R. Maciejewski, “Graph convolutional networks: a comprehensive review,” Computational Social Networks, vol. 6, no. 1, pp. 1–23, 2019, doi: 10.1186/s40649-019-0069-y.

Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, S. Y. Philip, “A comprehensive survey on graph neural networks,” IEEE transactions on neural networks and learning systems, vol. 32, no. 1, pp. 4–24, 2020, doi: 10.1109/TNNLS.2020.2978386.

T. Derr, Y. Ma, W. Fan, X. Liu, C. Aggarwal, J. Tang, “Epidemic graph convolutional network,” in Proceedings of the 13th International Conference on Web Search and Data Mining, 2020, pp. 160–168.

H. Kashima, T. Kato, Y. Yamanishi, M. Sugiyama, K. Tsuda, “Link propagation: A fast semi-supervised learning algorithm for link prediction,” in Proceedings of the 2009 SIAM international conference on data mining, 2009, pp. 1100–1111, SIAM.

R. Raymond, H. Kashima, “Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs,” in Joint european conference on machine learning and knowledge discovery in databases, 2010, pp. 131–147, Springer.

A. K. Menon, C. Elkan, “Link prediction via matrix factorization,” in Joint european conference on machine learning and knowledge discovery in databases, 2011, pp. 437–452, Springer.

S. Gao, L. Denoyer, P. Gallinari, “Temporal link prediction by integrating content and structure information,” in Proceedings of the 20th ACM international conference on Information and knowledge management, 2011, pp. 1169–1174.

Z. Zeng, K.-J. Chen, S. Zhang, H. Zhang, “A link prediction approach using semi-supervised learning in dynamic networks,” in The International Conference on Advanced Computational Intelligence, 2013, pp. 276–280, IEEE.

L. Berton, J. Valverde-Rebaza, A. de Andrade Lopes, “Link prediction in graph construction for supervised and semi-supervised learning,” in The International Joint Conference on Neural Networks, 2015, pp. 1–8, IEEE.

T. N. Kipf, M. Welling, “Variational graph auto- encoders,” arXiv preprint arXiv:1611.07308, 2016.

H. Yang, S. Pan, P. Zhang, L. Chen, D. Lian, C. Zhang, “Binarized attributed network embedding,” in IEEE International Conference on Data Mining, 2018, pp. 1476–1481, IEEE.

P. V. Tran, “Multi-task graph autoencoders,” arXiv preprint arXiv:1811.02798, 2018.

R. Hisano, “Semi-supervised graph embedding approach to dynamic link prediction,” in International Workshop on Complex Networks, 2018, pp. 109–121, Springer.

S. Pan, R. Hu, G. Long, J. Jiang, L. Yao, C. Zhang, “Adversarially regularized graph autoencoder for graph embedding,” arXiv preprint arXiv:1802.04407, 2018.

X. Di, P. Yu, R. Bu, M. Sun, “Mutual information maximization in graph neural networks,” in The International Joint Conference on Neural Networks, 2020, pp. 1–7, IEEE.

T. Zhang, K. Zhang, X. Li, L. Lv, Q. Sun, “Semi- supervised link prediction based on non-negative matrix factorization for temporal networks,” Chaos, Solitons & Fractals, vol. 145, p. 110769, 2021, doi: 10.1016/j.chaos.2021.110769.

E. Bastami, A. Mahabadi, E. Taghizadeh, “A gravitation-based link prediction approach in social networks,” Swarm and evolutionary computation, vol. 44, pp. 176–186, 2019, doi: 10.1016/j.swevo.2018.03.001.

W. Gu, F. Gao, R. Li, J. Zhang, “Learning universal network representation via link prediction by graph convolutional neural network,” Journal of Social Computing, vol. 2, no. 1, pp. 43–51, 2021, doi: 10.23919/JSC.2021.0001.

M. Shabaz, U. Garg, “Predicting future diseases based on existing health status using link prediction,” World Journal of Engineering, 2021, doi: 10.1108/WJE-10-2020-0533.

M. Wang, L. Qiu, X. Wang, “A survey on knowledge graph embeddings for link prediction,” Symmetry, vol. 13, no. 3, p. 485, 2021, doi: 10.3390/sym13030485.

F. J. Roethlisberger, W. J. Dickson, Management and the worker, vol. 5. Psychology press, 2003.

R. Saxena, M. Jadeja, “Network centrality measures: role and importance in social networks,” in Principles of Social Networking, 2022, pp. 29–54, Springer.

U. Brandes, S. P. Borgatti, L. C. Freeman, “Maintaining the duality of closeness and betweenness centrality,” Social Networks, vol. 44, pp. 153– 159, 2016, doi: 10.1016/j.socnet.2015.08.003.

O. Shchur, M. Mumme, A. Bojchevski, S. Günnemann, “Pitfalls of graph neural network evaluation,” arXiv preprint arXiv:1811.05868, 2018.

P. Mernyei, C. Cangea, “Wiki-cs: A wikipedia-based benchmark for graph neural networks,” arXiv preprint arXiv:2007.02901, 2020.

Z. Zhang, X. Wang, W. Zhu, “Automated machine learning on graphs: A survey,” arXiv preprint arXiv:2103.00742, 2021.

M. Kaur, H. Kaur, “Implementation of enhanced graph layout algorithm for visualizing social network data using networkx library,” International Journal of Advanced Research in Computer Science, vol. 8, no. 3, 2017, doi: 10.26483/ijarcs.v8i3.2998.

R. Rossi, N. Ahmed, “The network data repository with interactive graph analytics and visualization,” in Twenty-ninth AAAI conference on artificial intelligence, 2015.

A. Grover, J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855–864.

P. Jiang, S. Huang, Z. Fu, Z. Sun, T. M. Lakowski, P. Hu, “Deep graph embedding for prioritizing synergistic anticancer drug combinations,” Computational and structural biotechnology journal, vol. 18, pp. 427–438, 2020, doi: 10.1016/j.csbj.2020.02.006.

K. Tayal, R. Nikhil, S. Agarwal, K. Subbian, “Short text classification using graph convolutional network,” in NIPS workshop on Graph Representation Learning, 2019.

P. Cao, Z. Zhu, Z. Wang, Y. Zhu, Q. Niu, “Applications of graph convolutional networks in computer vision,” Neural Computing and Applications, pp. 1–19, 2022, doi: 10.1007/s00521-022-07368-1.

N. Kourtellis, G. D. F. Morales, F. Bonchi, “Scalable online betweenness centrality in evolving graphs,” IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 9, pp. 2494–2506, 2015, doi: 10.1109/ICDE.2016.7498421.

W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, C.-J. Hsieh, “Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks,” in Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp. 257–266.