Computer Science ›› 2021, Vol. 48 ›› Issue (2): 100-104.doi: 10.11896/jsjkx.191200033

• Database & Big Data & Data Science • Previous Articles     Next Articles

Directed Network Representation Method Based on Hierarchical Structure Information

LI Xin-chao, LI Pei-feng, ZHU Qiao-ming   

  1. School of Computer Sciences and Technology,Soochow University,Suzhou,Jiangsu 215006,China; Provincial Key Laboratory for Computer Information Processing Technology,Suzhou,Jiangsu 215006,China
  • Received:2019-12-03 Revised:2020-04-28 Online:2021-02-15 Published:2021-02-04
  • About author:LI Xin-chao,born in 1995,postgra-duate.His main research interests include natural language processing and representation learning.
    LI Pei-feng,born in 1971,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include natural language processing and machine learning.
  • Supported by:
    The National Natural Science Foundation of China(61836007,61772354,61773276).

Abstract: Network embedding aims to embed each vertex into a low dimensional vector space and preserves certain structural relationships among the vertices in the networks.However,in the directed networks,vertexes can be reached by each other if they are in the same circle,which damages asymmetric transitivity preservation and makes representation learning model hard to capture global information of complex directed networks.This paper proposes an improved representation learning model for directed networks,which weakens the influence of circles in representation learning and enhances the ability of model to obtain global structure information.The proposed method uses TrueSkill to inference hierarchy of a directed graph and compute weight of each edge using hierarchy information.At last,this paper applies this method to some existing embedding models,and then conducts experiments on tasks of link prediction and node classification on several open source datasets.Experimental results show that the proposed method is highly scalable and effective.

Key words: Directed network, Hierarchical Structure, Link prediction, Representation learning

CLC Number: 

  • TP391.1
[1] CAI H Y,ZHENG V W,CHANG K.A Comprehensive Survey of Graph Embedding:Problems,Techniques and Applications[J].IEEE Transactions on Knowledge and Data Engineering,2017,30(9):1616-1637.
[2] LIBEN-NOWELL D,KLEINBERG J.The link-prediction pro-blem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.
[3] CHANDOLA V,BANERJEE A,KUMAR V.Anomaly Detection:A Survey[J].ACM Computing Surveys,2009,41(3):1-72.
[4] WANG X,CUI P,WANG J,et al.Community preserving network embedding[C]//The 31st AAAI Conference on Artificial Intelligence.2017.
[5] WEI X K,XU L CH,CAO B K,et al.Cross view link prediction by learning noise-resilient representation consensus[C]//The 26th International Conference on World Wide Web.Internatio-nal World Wide Web Conferences Steering Committee.2017:1611-1619.
[6] TOMAS M,LLYA S,CHEN K,et al.Distributed representations of words and phrases and their compositionality[C]//NIPS 2013.Cambridge,MA:MIT Press,2013:3111-3119.
[7] TANG L,LIU H.Leveraging social media networks for classification[J].Data Mining and Knowledge Discovery,2011,23(3):447-478.
[8] CAO S H,LU W,XU Q K.GraRep:Learning Graph Representations with Global Structural Information[C]//ACM International on Conference on Information & Knowledge Management.ACM,2015.
[9] OU M D,CUI P,PEI J,et al.Asymmetric Transitivity Preserving Graph Embedding[C]//The 22nd ACM SIGKDD International Conference.ACM,2016.
[10] WANG D,CUI P,ZHU W.Structural Deep Network Embedding[C]//The 22ndACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2016:1225-1234.
[11] TIAN F,GAO B,CUI Q,et al.Learning deep representationsfor graph clustering[C]//The Twenty-Eighth AAAI Confe-rence on Artificial Intelligence.2014.
[12] PEROZZI B,AI-RFOU R,SKIENA S.DeepWalk:Online Lear-ning of Social Representations[C]//The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.ACM,2014:701-710.
[13] TANG J,QU M,WANG M,et al.Line:Large-scale information network embedding[C]//The 24th International Conference on World Wide Web.International World Wide Web Conferences Steering Committee.2015:1067-1077.
[14] GROVER A,LESKOVEC J.node2vec:Scalable Feature Lear-ning for Networks[C]//The 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2016:855-864.
[15] ZHOU C,LIU Y,LIU X,et al.Scalable graph embedding for asymmetric proximity[C]//The 31st AAAI Conference on Artificial Intelligence.2017.
[16] ABU-EL-HAIJA S,PEROZZI B,AL-RFOU R.Learning edge representations via low-rank asymmetric projections[C]//The 2017 ACM on Conference on Information and Knowledge Mana-gement.ACM,2017:1787-1796.
[17] ABU-EL-HAIJA S,PEROZZI B,AL-RFOU R,et al.WatchYour Step:Learning Node Embeddings via Graph Attention[C]//Neural Information Processing Systems (NIPS).2018:9180-9190.
[18] SUN J,AJWANI D,NICHOLSON P K,et al.Breaking Cycles in Noisy Hierarchies[C]//the 2017 ACM on Web Science Conference.ACM,2017:151-160.
[19] HERBRICH R,MINKA T,GRAEPEL T.TrueSkill:A Bayesian Skill Rating System[C]//Neural Information Processing Systems (NIPS).2007.
[20] GUPTE M,SHANKAR P,LI J,et al.Finding Hierarchy in Directed Online Social Networks[C]//The 20th International Conference on World Wide Web(WWW 2011).Hyderabad,India,DBLP,2011.
[1] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[2] HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[3] XU Yong-xin, ZHAO Jun-feng, WANG Ya-sha, XIE Bing, YANG Kai. Temporal Knowledge Graph Representation Learning [J]. Computer Science, 2022, 49(9): 162-171.
[4] LI Zong-min, ZHANG Yu-peng, LIU Yu-jie, LI Hua. Deformable Graph Convolutional Networks Based Point Cloud Representation Learning [J]. Computer Science, 2022, 49(8): 273-278.
[5] HUANG Pu, DU Xu-ran, SHEN Yang-yang, YANG Zhang-jing. Face Recognition Based on Locality Regularized Double Linear Reconstruction Representation [J]. Computer Science, 2022, 49(6A): 407-411.
[6] LI Yong, WU Jing-peng, ZHANG Zhong-ying, ZHANG Qiang. Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism [J]. Computer Science, 2022, 49(4): 43-48.
[7] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[8] JIANG Zong-li, FAN Ke, ZHANG Jin-li. Generative Adversarial Network and Meta-path Based Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(1): 133-139.
[9] WANG Ying-li, JIANG Cong-cong, FENG Xiao-nian, QIAN Tie-yun. Time Aware Point-of-interest Recommendation [J]. Computer Science, 2021, 48(9): 43-49.
[10] ZHAO Jin-long, ZHAO Zhong-ying. Recommendation Algorithm Based on Heterogeneous Information Network Embedding and Attention Neural Network [J]. Computer Science, 2021, 48(8): 72-79.
[11] YE Hong-liang, ZHU Wan-ning, HONG Lei. Music Style Transfer Method with Human Voice Based on CQT and Mel-spectrum [J]. Computer Science, 2021, 48(6A): 326-330.
[12] HU Xin-tong, SHA Chao-feng, LIU Yan-jun. Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis [J]. Computer Science, 2021, 48(5): 124-129.
[13] YANG Ru-han, DAI Yi-ru, WANG Jian, DONG Jin. Humans-Cyber-Physical Ontology Fusion of Industry Based on Representation Learning [J]. Computer Science, 2021, 48(5): 190-196.
[14] CHEN Heng, WANG Wei-mei, LI Guan-yu, SHI Yi-ming. Knowledge Graph Completion Model Using Quaternion as Relational Rotation [J]. Computer Science, 2021, 48(5): 225-231.
[15] QIAN Sheng-sheng, ZHANG Tian-zhu, XU Chang-sheng. Survey of Multimedia Social Events Analysis [J]. Computer Science, 2021, 48(3): 97-112.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!