Dynamic Network Link Prediction Based on Sequential Graph Convolution

Liu Linlan; Feng Zhenxing; Shu Jian

doi:10.7544/issn1000-1239.202220776

Journal of Computer Research and Development > 2024 > 61(2): 518-528. > DOI: 10.7544/issn1000-1239.202220776 CSTR: 32373.14.issn1000-1239.202220776

Liu Linlan, Feng Zhenxing, Shu Jian. Dynamic Network Link Prediction Based on Sequential Graph Convolution[J]. Journal of Computer Research and Development, 2024, 61(2): 518-528. DOI: 10.7544/issn1000-1239.202220776

Citation:

PDF (2378 KB)

Dynamic Network Link Prediction Based on Sequential Graph Convolution

1.
School of Information Engineering, Nanchang Hangkong University, Nanchang 330063
2.
School of Software, Nanchang Hangkong University, Nanchang 330063

Funds: This work was supported by the National Natural Science Foundation of China (62062050, 61962037).

More Information

Author Bio:
Liu Linlan: born in 1968. Bachelor, professor. Member of CCF. Her main research interests include software engineering and distributed system

Feng Zhenxing: born in 1998. Master candidate. Student member of CCF. His main research interests include network analysis and link prediction

Shu Jian: born in 1964. Master, professor. Senior member of CCF. His main research interests include complex networks, embedded system, and software engineering
Received Date: August 31, 2022
Revised Date: March 12, 2023
Available Online: January 22, 2024

Graphical Abstract

Abstract

Abstract

Dynamic network link prediction has become a hot topic in network science field because of its wide application prospect. However, the complexity of spatial correlation and temporal dependence in the evolution process of dynamic network links leads to the great challenges of dynamic network link prediction task. In this paper, a dynamic network link prediction model based on sequential graph convolution (DNLP-SGC) is proposed. On the one hand, because network snapshot sequence cannot effectively reflect the continuity of dynamic network evolution, the edge trigger mechanism is employed to modify the original network weight matrix, so as to make up loss timing information in discrete snapshot of dynamic network. On the other hand, from the view of network evolution and considering the feature similarity and historical interaction information between nodes, a temporal graph convolution method is proposed to extract node features in dynamic network, and the method integrates the spatial-temporal dependence of nodes effectively. Furthermore, the causal convolutional network is used to capture the potential global temporal features in the dynamic network evolution process to achieve dynamic network link prediction. Experimental results on two real dynamic network datasets show that DNLP-SGC outperforms the baseline model on three common indexes, such as precision, recall and AUC.
- dynamic network,
- link prediction,
- sequential graph convolution,
- global temporal feature,
- causal convolution

FullText(HTML)

References (22)

References

[1]	Watts D J, Dodds P S, Newman M E J. Identity and search in social networks[J]. Science, 2002, 296(5571): 1302−1305 doi: 10.1126/science.1070120
[2]	Ma Xiaoke, Tan Shiyin, Xie Xianghua, et al. Joint multi-label learning and feature extraction for temporal link prediction[J]. Pattern Recognition, 2022, 121: 108216 doi: 10.1016/j.patcog.2021.108216
[3]	Song Chao, Lin Youfang, Guo Shengnan, et al. Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temporal network data forecasting [C] //Proc of the 34th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2020: 914−921
[4]	Güne İ, Gündüz-Öğüdücü Ş, Çataltepe Z. Link prediction using time series of neighborhood-based node similarity scores[J]. Data Mining and Knowledge Discovery, 2016, 30(1): 147−180 doi: 10.1007/s10618-015-0407-0
[5]	Chuan P M, Son L H, Ali M, et al. Link prediction in co-authorship networks based on hybrid content similarity metric[J]. Applied Intelligence, 2018, 48(8): 2470−2486 doi: 10.1007/s10489-017-1086-x
[6]	Ran Yijun, Liu Siyuan, Yu Xiaoyao, et al. Predicting future links with new nodes in temporal academic networks[J]. Journal of Physics: Complexity, 2022, 3(1): 015006 doi: 10.1088/2632-072X/ac4bee
[7]	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
[8]	Grover A, Leskovec J. node2vec: Scalable feature learning for networks [C] //Proc of the 22nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2016: 855−864
[9]	Nguyen G H, Lee J B, Rossi R A, et al. Continuous-time dynamic network embeddings [C] // Proc of the 18th Web Conf (WWW’18). New York: ACM, 2018: 969−976
[10]	Chen Zhang, Yiming Fan, Yu Xie, et al. Dynamic network embedding via structural attention[J]. Expert Systems with Applications, 2021, 176: 114895 doi: 10.1016/j.eswa.2021.114895
[11]	Pareja A, Domeniconi G, Chen Jie, et al. EvolveGCN: Evolving graph convolutional networks for dynamic graphs [C] //Proc of the 34th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2020: 5363−5370
[12]	Lei Kai, Qin Meng, Bai Bo, et al. GCN-GAN: A non-linear temporal link prediction model for weighted dynamic networks [C] // Proc of the 38th IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2019: 388−396
[13]	Chen Jinyin, Zhang Jian, Xu Xuanheng, et al. E-LSTM-D: A deep learning framework for dynamic network link prediction [J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(6): 3699−3712
[14]	刘林峰,于子兴,祝贺. 基于门控循环单元的移动社会网络链路预测方法 [J]. 计算机研究与发展,2023, 60(3): 705−716 Liu Linfeng, Yu Zixing, Zhu He. A link prediction method based on gated recurrent units for mobile social network [J/OL]. Journal of Computer Research and Development, 2023, 60(3): 705−716 (in Chinese)
[15]	Chen Jinyin, Wang Xueke, Xu Xuanheng. GC-LSTM: Graph convolution embedded LSTM for dynamic network link prediction[J]. Applied Intelligence, 2022, 52(7): 7513−7528 doi: 10.1007/s10489-021-02518-9
[16]	Randall M J. Physiological time-series analysis using approximate entropy and sample entropy[J]. American Journal of Physiology Heart & Circulatory Physiology, 2000, 278(6): H2039
[17]	Bai Shaojie, Kolter J Z, Koltun V. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling[J]. arXiv preprint, arXiv: 1803. 01271, 2018
[18]	Veit A, Wilber M J, Belongie S. Residual networks behave like ensembles of relatively shallow networks [C] // Proc of the 30th Int Conf on Neural Information Processing Systems (NIPS’16). La Jolla, CA: NIPS, 2016: 550–558
[19]	Balduzzi D, Frean M, Leary L, et al. The shattered gradients problem: If resnets are the answer, then what is the question? [C] // Proc of the 34th Int Conf on Machine Learning. New York: PMLR, 2017: 342−350
[20]	Zhang Jingzhao, He Tianxing, Sra S, et al. Why gradient clipping accelerates training: A theoretical justification for adaptivity[J]. arXiv preprint, arXiv: 1905. 11881, 2019
[21]	KotzA D, Henderson D, Abyzov I, et al. CRAWDAD: Community resource for archiving wireless data [DB/OL]. Hanover, New Hampshire: Dartmouth College Libraries, [2022-10-10]. http://www.crawdad.org
[22]	Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need [C] // Proc of the 31st Advances in Neural Information Processing Systems. Cambridge, MA: MIT, 2017: 5998−6008

[1]	Fu Nan, Ni Weiwei, Jiang Zepeng, Hou Lihe, Zhang Dongyue, Zhang Ruyu. Directed Graph Clustering Algorithm with Edge Local Differential Privacy[J]. Journal of Computer Research and Development, 2025, 62(1): 256-268. DOI: 10.7544/issn1000-1239.202330193
[2]	Deng Xinguo, Zhang Xinhong, Chen Jiarui, Liu Qinghai, Chen Chuandong. A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440069
[3]	Shang Jing, Wu Zhihui, Xiao Zhiwen, Zhang Yifei. Graph4Cache: A Graph Neural Network Model for Cache Prefetching[J]. Journal of Computer Research and Development, 2024, 61(8): 1945-1956. DOI: 10.7544/issn1000-1239.202440190
[4]	Zhang Tianming, Xu Yiheng, Cai Xinwei, Fan Jing. A Shortest Path Query Method over Temporal Graphs[J]. Journal of Computer Research and Development, 2022, 59(2): 362-375. DOI: 10.7544/issn1000-1239.20210893
[5]	Zhang Xin, Li Xiaoguang. Spanner Algorithm for Directed Graph Stream[J]. Journal of Computer Research and Development, 2019, 56(3): 655-665. DOI: 10.7544/issn1000-1239.2019.20170680
[6]	Wang Juanjuan, Qiao Ying, Wang Hongan. Graph-Based Auto-Driving Reasoning Task Scheduling[J]. Journal of Computer Research and Development, 2017, 54(8): 1693-1702. DOI: 10.7544/issn1000-1239.2017.20170212
[7]	He Wei, Zhao Ruilian, and Zhu Qunxiong. Call-Graph-Based Interclass MM Path Generation[J]. Journal of Computer Research and Development, 2013, 50(2): 332-343.
[8]	Xu Shifeng, Gao Jun, Yang Dongqing, and Wang Tengjiao. Pass-Count-Based Path Query on Big Graph Datasets[J]. Journal of Computer Research and Development, 2010, 47(1): 96-103.
[9]	Yao Guohui, Zhu Daming, and Ma Shaohan. Approximating the Directed Minimum Degree Spanning Tree of Directed Acyclic Graph[J]. Journal of Computer Research and Development, 2009, 46(6): 1052-1057.
[10]	Wen Yanzhi, Lian Ruiqi, Wu Chengyong, Feng Xiaobing, and Zhang Zhaoqing. A Micro-Scheduling Method on Directed Cyclic Graph[J]. Journal of Computer Research and Development, 2005, 42(3).