Computer Science ›› 2021, Vol. 48 ›› Issue (3): 201-205.doi: 10.11896/jsjkx.191200156

• Artificial Intelligence • Previous Articles     Next Articles

Inductive Learning Algorithm of Graph Node Embedding Based on KNN and Matrix Transform

HE Miao-miao, GUO Wei-bin   

  1. School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China
  • Received:2019-12-26 Revised:2020-05-19 Online:2021-03-15 Published:2021-03-05
  • About author:HE Miao-miao,born in 1995,postgra-duate.Her main research interests include natural language processing and so on.
    GUO Wei-bin,born in 1968,Ph.D,professor,is a member of China Computer Federation.His main research interests include high performance computing,software engineering and big data.
  • Supported by:
    National Natural Science Foundation of China(61672227).

Abstract: Low-dimensional embedding of graph nodes is very useful in various prediction tasks,such as protein function prediction,content recommendation and so on.However,most methods cannot be naturally extended to invisible nodes.Graph Sample and Aggregate (Graph Sample and Aggregate,Grasage) algorithm can improve the speed of invisible node generation embedding,but it is easy to introduce noise data,and the representation ability of generated node embedding is not high.In this paper,an inductive learning algorithm based on KNN and matrix transformation for graph node embedding is proposed.Firstly,K neighbo-ring nodes are selected by KNN.Then aggregation information is generated by aggregation function.Finally,aggregation information and node information are calculated by matrix transformation and full connection layer,and new node embedding is obtained.In order to balance computing time and performance effectively,this paper proposes a new aggregation function,which uses maximum pooling as aggregation information output for neighbor node features,retains more neighbor node information and reduces computing cost.Experiments on two data sets of reddit and PPI show that the proposed algorithm achieves 4.995% and 10.515% improvement on micro-f1 and macro-f1,respectively.The experimental data fully show that the algorithm can greatly reduce noise data,improve the representation ability of node embedding,and quickly and effectively generate node embedding for invisible nodes and invisible graphs.

Key words: Aggregation function, KNN, Low dimensional embedding, Node embedding, Representation ability

CLC Number: 

  • TP391
[1]CAO S S,LU W,XU Q K.grarep:learning graph representations with global structural information[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management.ACM,2015:891-900.
[2]PEROZZI B,AL R R,SKIENA S.Deepwalk:Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Association for Computing Machinery,2014:701-710.
[3]ZHANG W P,LI Z J,LI R H,et al.Graph Structure Clustering Algorithm Based on MapReduce[J].Journal of Software,2018,29(3):627-641.
[4]WANG D,CUI P,ZHU W.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Association for Computing Machinery,2016:1225-1234.
[5]NG A Y,JORDAN M I,WEISS Y,et al.On spectral clustering:Analysis and an algorithm[C]//Proceedings from the Confe-rence,Neural Information Processing Systems 2001.Cambridge:Massachusetts Institute of Technology Press,2001:849-856.
[6]WILLIAM L,HAMILTON,YING Z T,et al.Inductive Repre-sentation Learning on Large Graphs[C]//Advances in Neural Information Processing Systems 30:Annual Conference on Neural Information Processing Systems 2017.2017:1024-1034.
[7]BANU S,CEMNUR A,JOOF S,et al.Microwave dielectricproperty based classification of renal calculi:Application of a kNN algorithm[J].Computers in biology and medicine,2019,98(1):4-24.
[8]ESTEBAN B,PATRICE A,PAULO G.PageRank for semi-supervised learning[J].Applied Network Science,2019,4(1):1-20.
[9]SHERVASHIDZE N,SCHWEITZER P,BORGWARDT K M,et al.Weisfeilerlehman graph kernels[J].Journal of Machine Learning Research,2011,12(3):2539-2561.
[10]DAI H,DAI B,SONG L.Discriminative embeddings of latentvariable models for structured data[C]//Proceedings of the 33nd International Conference on Machine Learning.JMLR,2016:2702-2711.
[11]GORI M,MONFARDINI G,SCARSELLI F.A new model for learning in graph domains[C]//IEEE International Joint Conference on Neural Networks.IEEE,2005:729-734.
[12]XU B B,CEN K T,HUANG J J,et al.A Survey of Convolution Neural Networks[J].Journal of Computer Science,2019,26 (10):1-31.
[13]SCARSELLI F,GORI M,TSOI A C,et al.The graph neural network model[J].IEEE Transactions on Neural Networks,2009,20(1):61-80.
[14]BRUNA J,ZAREMBA W,SZLAM A,et al.Spectral networks and locally connected networks on graphs[C]//proceedings from the 2nd International Conference on Learning Representations.ICLR,2014:2667-2674.
[15]KIPF T N,WELLING M.Semi-supervised classification withgraph convolutional networks[C]//5th International Conference on Learning Representations.OpenReview net,2016:5169-5179.
[16]NIEPERT M,AHMED M,KUTZKOV K.Learning convolu-tional neural networks for graphs[C]//Proceedings of the 33nd International Conference on Machine Learning.JMLR,2016:2014-2023.
[17]CHIEN C T,SU L L.Design of orthogonal graph filter bankwith known eigenvalues of Laplacian matrix[J].IET Signal Processing,2019,13(5):551-561.
[18]LAN Y D,DENG H F,CHEN T.Semi Supervised ClusteringAlgorithm Based on Graph Contraction[J].Computer Science,2012,39(4):236-239.
[19]DUWENAUD D K,MACLAURIN D,IPARRAGUIRRE J,et al.Convolutional networks on graphs for learning molecular fingerprints[C]//Advances in Neural Information Processing Systems 28:Annual Conference on Neural Information Proces-sing Systems science bibliography,2015:2224-2232.
[20]DANILO A,LUIGI C,GIAN L F,et al.A Shape Comparison Reinforcement Method Based on Feature Extractors and F1-Score[C]//Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems.ACM,2017:2594-2605.
[1] ZHANG Ren-jie, CHEN Wei, HANG Meng-xin, WU Li-fa. Detection of Abnormal Flow of Imbalanced Samples Based on Variational Autoencoder [J]. Computer Science, 2021, 48(7): 62-69.
[2] ZHAO Zhi-qiang, YI Xiu-shuang, LI Jie, WANG Xing-wei. Research on DoS Intrusion Detection Technology of IPv6 Network Based on GR-AD-KNN Algorithm [J]. Computer Science, 2021, 48(6A): 524-528.
[3] HUANG Ming, SUN Lin-fu, REN Chun-hua , WU Qi-shi. Improved KNN Time Series Analysis Method [J]. Computer Science, 2021, 48(6): 71-78.
[4] HAN Zhong-ming, ZHENG Chen-ye, DUAN Da-gao, DONG Jian. Associated Users Mining Algorithm Based on Multi-information Fusion Representation Learning [J]. Computer Science, 2019, 46(4): 77-82.
[5] BAO Zong-ming, GONG Sheng-rong, ZHONG Shan, YAN Ran, DAI Xing-hua. Person Re-identification Algorithm Based on Bidirectional KNN Ranking Optimization [J]. Computer Science, 2019, 46(11): 267-271.
[6] HE Ji-xing,CHEN Wen-bin,MOU Bin-hao. Coordination Filtering Personalized Recommendation Algorithm Considering Average
Preference Weight and Popularity Division
[J]. Computer Science, 2018, 45(6A): 493-496.
[7] LI Si-yao, ZHOU Hai-fang, FANG Min-quan. Research of Image Classification Algorithm Based on GPU [J]. Computer Science, 2018, 45(6A): 143-145.
[8] CHEN Jing-jie and CHE Jie. Fuel Flow Missing-value Imputation Method Based on Standardized Euclidean Distance [J]. Computer Science, 2017, 44(Z6): 109-111.
[9] FENG Fei, JIANG Bao-hua, LIU Pei-xue and CHEN Yu-jie. Application of Improved 2DPCA Algorithm in Face Recognition [J]. Computer Science, 2017, 44(Z11): 267-268.
[10] XUE Zhong-bin, BAI Li-guang, HE Ning, ZHOU Xuan, ZHOU Xin and WANG Shan. Throughput Oriented Real-time Query Processing Algorithm for Moving Objects in Road Network [J]. Computer Science, 2017, 44(3): 16-19.
[11] WANG Li, WANG Xin and MA Chao-dong. Distributed Caching Strategy for Data Exchange Program Based on Ontology and KNN Algorithm [J]. Computer Science, 2016, 43(Z11): 316-319.
[12] HUA Hui-you, CHEN Qi-mai, LIU Hai, ZHANG Yang and YUAN Pei-quan. Hybrid Kmeans with KNN for Network Intrusion Detection Algorithm [J]. Computer Science, 2016, 43(3): 158-162.
[13] WANG Pei-zhong, ZHENG Nan-shan and ZHANG Yan-zhe. Indoor Positioning Algorithm Based on Dynamic K Value and AP MAC Address Match [J]. Computer Science, 2016, 43(1): 163-165.
[14] XU Xiao-dan, YAO Ming-hai, LIU Hua-wen and ZHENG Zhong-long. Pre-processing Method of Multi-label Classification Based on kNN [J]. Computer Science, 2015, 42(5): 106-108.
[15] WANG Fei, QIN Xiao-lin, LIU Liang and SHEN Yao. Algorithm for k-Nearest Neighbor Join Based on Data Stream [J]. Computer Science, 2015, 42(5): 204-210.
Full text



No Suggested Reading articles found!