基于引力作用融合节点和边的图嵌入模型
Graph Embedding Model Based on the Fusion of Nodes and Edges by Gravity
DOI: 10.12677/AAM.2023.1212484, PDF,   
作者: 杨春生, 刘士虎*, 高海燕：云南民族大学数学与计算机科学学院，云南 昆明
关键词: 图；随机游走；万有引力；图嵌入；Graph； Random Walk； Universal Gravitation； Graph Embedding
摘要: 基于随机游走的图嵌入模型主要集中在随机游走策略的选择，最新的图嵌入模型ProbWalk就是通过边的权重构建概率转移矩阵来获取高精度的嵌入向量。ProbWalk模型只是考虑了边的信息对于基于随机游走的图嵌入模型的影响，而DeepWalk模型只考虑了节点的信息的影响，因此这样无法兼顾图中节点和边的信息，不能很好地反映图的拓扑结构。针对这个问题，提出了一种综合考虑图中节点和边的图嵌入模型，即利用万有引力融合图中节点和边的信息。实验结果表明，在Dolphins、Polbooks、Brazil、Europe和PB五个数据集上，用所提模型得到的节点向量表示进行节点分类的F1-Micro平均准确率比DeepWalk模型高出28.5个百分点，F1-Macro平均准确率比DeepWalk模型高出26.7个百分点。
Abstract: Graph embedding model based on random walk mainly focuses on the selection of random walk strategy. ProbWalk model that is the latest graph embedding technology is to construct probability transfer matrix through the weight of edges to obtain high-precision embedding vectors. ProbWalk model only considers the influence of edge information on the graph embedding model based on random walk, while DeepWalk model only considers the influence of node information, so they can’t take into account the information of nodes and edges in the graph, and can’t well reflect the topolo-gy of the graph. To solve this problem, a graph embedding model considering the nodes and edges in the graph is proposed, which uses gravity to fuse the information of nodes and edges in the graph. The experimental results show that on the five datasets of Dolphins, Pollbooks, Brazil, Europe and PB, the average accuracy of F1-Micro for node classification based on the node vector obtained by the proposed model is 28.5 percentage points higher than that of DeepWalk model, and the average accuracy of F1-Macro is 26.7 percentage points higher than that of DeepWalk model.
文章引用：杨春生, 刘士虎, 高海燕. 基于引力作用融合节点和边的图嵌入模型[J]. 应用数学进展, 2023, 12(12): 4914-4926. https://doi.org/10.12677/AAM.2023.1212484

参考文献

[1] Song, Y., Gu, Y., Li, F., et al. (2020) Survey on AI Powered New Techniques for Query Processing and Optimization. Journal of Frontiers of Computer Science and Technology, 14, 1081-1103.
[2] Ruan, Y.R., et al. (2017) Node Im-portance Measurement Based on Neighborhood Similarity in Complex Net-Work. Journal of Physics, 66, 1-8. [Google Scholar] [CrossRef] 
[3] Guo, Y., Li, M., Pu, X., et al. (2010) PRED_PPI: A Server for Pre-dicting Protein-Protein Interactions Based on Sequence Data with Probability Assignment. BMC Research Notes, 3, Arti-cle No. 145. [Google Scholar] [CrossRef] [PubMed]
[4] 罗浩, 闫光辉, 张萌, 等. 融合多元信息的多关系社交网络节点重要性研究[J]. 计算机研究与发展, 2020, 57(5): 954-970.
[5] 刘维, 陈崚. 复杂网络中的链接预测[J]. 信息与控制, 2020, 49(1): 1-23.
[6] Tang, H., Chen, K. and Jia, K. (2020) Unsupervised Domain Adaptation via Structurally Regularized Deep Clustering. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Seattle, 14-19 June 2020, 8725-8735. [Google Scholar] [CrossRef] 
[7] 杨旭华, 王磊, 叶蕾, 等. 基于节点相似性和网络嵌入的复杂网络社区发现算法[J]. 计算机科学, 2021, 49(3): 121-128.
[8] Belkin, M. and Niyogi, P. (2001) Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In: Advances in Neural Information Processing Systems 14, MIT Press, Cambridge, 585-591. [Google Scholar] [CrossRef] 
[9] Roweis, S.T. and Saul, L.K. (2000) Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 290, 2323-2326. [Google Scholar] [CrossRef] [PubMed]
[10] Luo, D., Nie, F., Huang, H. and Ding, C.H. (2011) Cauchy Graph Embedding. Proceedings of the 28th International Conference on Machine Learning (ICML-11), Bellevue, 28 June-2 July 2011, 553-560.
[11] Wang, X, Ji, H., Shi, C., et al. (2019) Heterogeneous Graph Attention Network. In: Proceedings of International Conference on World Wide Web, ACM Press, New York, 2022-2032. [Google Scholar] [CrossRef] 
[12] Wang, D., Cui, P. and Zhu, W. (2016) Structural Deep Network Embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, 1225-1234. [Google Scholar] [CrossRef] 
[13] Mikolov, T., Chen, K., Corrado, G., et al. (2013) Efficient Estima-tion of Word Representations in Vector Space.
[14] Perozzi, B., Al-Rfou, R. and Skiena, S. (2014) Deepwalk: Online Learning of Social Representations. In: Proceedings 20th International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, 701-710. [Google Scholar] [CrossRef] 
[15] Grover, A. and Leskovec, J. (2016) node2vec: Scalable Feature Learning for Networks. In: Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, ACM Press, New York, 855-864. [Google Scholar] [CrossRef] [PubMed]
[16] Perozzi, B., Kulkarni, V., Chen, H., et al. (2017) Don’t Walk, Skip: Online Learning of Multi-Scale Network Embeddings. In: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ACM Press, New York, 258-265. [Google Scholar] [CrossRef] 
[17] Chen, H., Perozzi, B., Hu, Y., et al. (2018) Harp: Hierarchical Rep-resentation Learning for Networks. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, Louisiana, 2127-2134. [Google Scholar] [CrossRef] 
[18] Schlötterer, J., Wehking, M., Rizi, F.S., et al. (2019) Investigating Extensions to Random Walk Based Graph Embedding. 2019 IEEE International Conference on Cognitive Computing (ICCC), Milan, 8-13 July 2019, 81-89. [Google Scholar] [CrossRef] 
[19] Zhou, Y., Wu, C. and Tan, L. (2021) Biased Random Walk with Restart for Link Prediction with Graph Embedding Method. Physica A: Statistical Mechanics and Its Applications, 570, Article ID: 125783. [Google Scholar] [CrossRef] 
[20] Wu, X., Pang, H., Fan, Y., et al. (2021) ProbWalk: A Random Walk Approach in Weighted Graph Embedding. Procedia Computer Science, 183, 683-689. [Google Scholar] [CrossRef] 
[21] 腊志垚, 钱育蓉, 冷洪勇, 等. 基于随机游走的图嵌入研究综述[J]. 计算机工程与应用, 2022, 58(13): 1-13.
[22] 祁志卫, 王笳辉, 岳昆, 等. 图嵌入方法与应用: 研究综述[J]. 电子学报, 2020, 48(4): 808-818.
[23] Goyal, P. and Ferrara, E. (2018) Graph Embedding Techniques, Applications, and Performance: A Survey. Knowledge-Based Systems, 151, 78-94. [Google Scholar] [CrossRef] 

为你推荐