计算机科学 ›› 2021, Vol. 48 ›› Issue (2): 100-104.doi: 10.11896/jsjkx.191200033

• 数据库&大数据&数据科学 • 上一篇    下一篇

一种基于层级信息优化的有向网络表示学习方法

李鑫超, 李培峰, 朱巧明   

  1. 苏州大学计算机科学与技术学院 江苏 苏州215006; 江苏省计算机信息技术处理重点实验室 江苏 苏州215006
  • 收稿日期:2019-12-03 修回日期:2020-04-28 出版日期:2021-02-15 发布日期:2021-02-04
  • 通讯作者: 李培峰(pfli@suda.edu.cn)
  • 作者简介:20175227013@stu.suda.edu.cn
  • 基金资助:
    国家自然科学基金(61836007,61772354,61773276)

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).

摘要: 网络表示方法旨在将每个节点映射到低维向量空间,并保留节点在网络中的结构关系。有向网络的环中节点相互可达,破坏了非对称传递性,影响了模型对网络整体结构信息的学习。为削弱有向网络的环在表示学习中的影响,增强模型对全局结构信息的感知,文中提出了一种针对有向网络表示学习的优化方法。该方法借助TrueSkill方法获取节点的层级信息,将该信息转化为边权重并引入表示学习过程。文中将此方法应用到已有的多种有向网络表示学习方法中,多个有向网络数据集上的链接预测和节点分类任务的实验结果表明,所提方法的性能相比原有方法得到了明显提升。

关键词: 表示学习, 层级信息, 链路预测, 有向网络

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

中图分类号: 

  • 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] 宋杰, 梁美玉, 薛哲, 杜军平, 寇菲菲.
基于无监督集群级的科技论文异质图节点表示学习方法
Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level
计算机科学, 2022, 49(9): 64-69. https://doi.org/10.11896/jsjkx.220500196
[2] 徐涌鑫, 赵俊峰, 王亚沙, 谢冰, 杨恺.
时序知识图谱表示学习
Temporal Knowledge Graph Representation Learning
计算机科学, 2022, 49(9): 162-171. https://doi.org/10.11896/jsjkx.220500204
[3] 黄璞, 杜旭然, 沈阳阳, 杨章静.
基于局部正则二次线性重构表示的人脸识别
Face Recognition Based on Locality Regularized Double Linear Reconstruction Representation
计算机科学, 2022, 49(6A): 407-411. https://doi.org/10.11896/jsjkx.210700018
[4] 李勇, 吴京鹏, 张钟颖, 张强.
融合快速注意力机制的节点无特征网络链路预测算法
Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism
计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[5] 赵学磊, 季新生, 刘树新, 李英乐, 李海涛.
基于路径连接强度的有向网络链路预测方法
Link Prediction Method for Directed Networks Based on Path Connection Strength
计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[6] 蒋宗礼, 樊珂, 张津丽.
基于生成对抗网络和元路径的异质网络表示学习
Generative Adversarial Network and Meta-path Based Heterogeneous Network Representation Learning
计算机科学, 2022, 49(1): 133-139. https://doi.org/10.11896/jsjkx.201000179
[7] 王营丽, 姜聪聪, 冯小年, 钱铁云.
时间感知的兴趣点推荐方法
Time Aware Point-of-interest Recommendation
计算机科学, 2021, 48(9): 43-49. https://doi.org/10.11896/jsjkx.210400130
[8] 赵金龙, 赵中英.
基于异质信息网络表示学习与注意力神经网络的推荐算法
Recommendation Algorithm Based on Heterogeneous Information Network Embedding and Attention Neural Network
计算机科学, 2021, 48(8): 72-79. https://doi.org/10.11896/jsjkx.200800226
[9] 杨如涵, 戴毅茹, 王坚, 董津.
基于表示学习的工业领域人机物本体融合
Humans-Cyber-Physical Ontology Fusion of Industry Based on Representation Learning
计算机科学, 2021, 48(5): 190-196. https://doi.org/10.11896/jsjkx.200500023
[10] 钱胜胜, 张天柱, 徐常胜.
多媒体社会事件分析综述
Survey of Multimedia Social Events Analysis
计算机科学, 2021, 48(3): 97-112. https://doi.org/10.11896/jsjkx.210200023
[11] 龚追飞, 魏传佳.
基于改进AdaBoost算法的复杂网络链路预测
Link Prediction of Complex Network Based on Improved AdaBoost Algorithm
计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[12] 王雪岑, 张昱, 刘迎婕, 于戈.
基于表示学习的在线学习交互质量评价方法
Evaluation of Quality of Interaction in Online Learning Based on Representation Learning
计算机科学, 2021, 48(2): 207-211. https://doi.org/10.11896/jsjkx.201000042
[13] 富坤, 赵晓梦, 付紫桐, 高金辉, 马浩然.
基于不完全信息的深度网络表示学习方法
Deep Network Representation Learning Method on Incomplete Information Networks
计算机科学, 2021, 48(12): 212-218. https://doi.org/10.11896/jsjkx.201000015
[14] 龚追飞, 魏传佳.
基于拓扑相似和XGBoost的复杂网络链路预测方法
Complex Network Link Prediction Method Based on Topology Similarity and XGBoost
计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026
[15] 黄寿孟.
一种基于监督学习的异构网链路预测模型
Heterogeneous Network Link Prediction Model Based on Supervised Learning
计算机科学, 2021, 48(11A): 111-116. https://doi.org/10.11896/jsjkx.210300030
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!