计算机科学 ›› 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, Representation learning, Hierarchical Structure, Link prediction

中图分类号: 

  • 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] 王雪岑, 张昱, 刘迎婕, 于戈. 基于表示学习的在线学习交互质量评价方法[J]. 计算机科学, 2021, 48(2): 207-211.
[2] 丁钰, 魏浩, 潘志松, 刘鑫. 网络表示学习算法综述[J]. 计算机科学, 2020, 47(9): 52-59.
[3] 王慧, 乐孜纯, 龚轩, 武玉坤, 左浩. 基于特征分类的链路预测方法综述[J]. 计算机科学, 2020, 47(8): 302-312.
[4] 蒋宗礼, 李苗苗, 张津丽. 基于融合元路径图卷积的异质网络表示学习[J]. 计算机科学, 2020, 47(7): 231-235.
[5] 黄易, 申国伟, 赵文波, 郭春. 一种基于漏洞威胁模式的网络表示学习算法[J]. 计算机科学, 2020, 47(7): 292-298.
[6] 张志扬, 张凤荔, 陈学勤, 王瑞锦. 基于分层注意力的信息级联预测模型[J]. 计算机科学, 2020, 47(6): 201-209.
[7] 富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法[J]. 计算机科学, 2020, 47(5): 96-102.
[8] 袁榕, 宋玉蓉, 孟繁荣. 一种基于加权网络拓扑权重的链路预测方法[J]. 计算机科学, 2020, 47(5): 265-270.
[9] 李鑫超, 李培峰, 朱巧明. 一种基于改进向量投影距离的知识图谱表示方法[J]. 计算机科学, 2020, 47(4): 189-193.
[10] 马扬, 程光权, 梁星星, 李妍, 杨雨灵, 刘忠. 有向加权网络中的改进SDNE算法[J]. 计算机科学, 2020, 47(4): 233-237.
[11] 张虎, 周晶晶, 高海慧, 王鑫. 融合节点结构和内容的网络表示学习方法[J]. 计算机科学, 2020, 47(12): 119-124.
[12] 王慧, 乐孜纯, 龚轩, 左浩, 武玉坤. 基于特征学习的链路预测模型TNTlink[J]. 计算机科学, 2020, 47(12): 245-251.
[13] 吴勇, 王斌君, 翟一鸣, 仝鑫. 共引增强有向网络嵌入研究[J]. 计算机科学, 2020, 47(12): 279-284.
[14] 顾秋阳, 琚春华, 吴功兴. 融入深度自编码器与网络表示学习的社交网络信息推荐模型[J]. 计算机科学, 2020, 47(11): 101-112.
[15] 陈晓军, 向阳. STransH:一种改进的基于翻译模型的知识表示模型[J]. 计算机科学, 2019, 46(9): 184-189.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 舒娜,刘波,林伟伟,李鹏飞. 分布式机器学习平台与算法综述[J]. 计算机科学, 2019, 46(3): 9 -18 .
[2] 王海涛, 宋丽华, 向婷婷, 刘力军. 人工智能发展的新方向——人机物三元融合智能[J]. 计算机科学, 2020, 47(11A): 1 -5 .
[3] 陈训敏, 叶书函, 詹瑞. 基于多任务学习及由粗到精的卷积神经网络人群计数模型[J]. 计算机科学, 2020, 47(11A): 183 -187 .
[4] . 目录[J]. 计算机科学, 2020, 47(12): 0 .
[5] . 复杂系统的软件工程和需求工程专题前言[J]. 计算机科学, 2020, 47(12): 2 .
[6] 孟繁祎, 王莹, 于海, 朱志良. 复杂软件系统的重构技术:现状、问题与展望[J]. 计算机科学, 2020, 47(12): 1 -10 .
[7] 吴文峻, 于鑫, 蒲彦均, 汪群博, 于笑明. 微服务时代的复杂服务软件开发[J]. 计算机科学, 2020, 47(12): 11 -17 .
[8] 杨经纬, 魏子麒, 刘璘. 用户如何看待产品中的预测分析功能?——面向非功能性需求的调研报告[J]. 计算机科学, 2020, 47(12): 18 -24 .
[9] 贾经冬, 张筱曼, 郝璐, 谭火彬. 工业界需求工程关注点分析[J]. 计算机科学, 2020, 47(12): 25 -34 .
[10] 周凯, 任怡, 汪哲, 管剑波, 张芳, 赵言亢. 基于主题模型的Ubuntu操作系统缺陷报告的分类及分析[J]. 计算机科学, 2020, 47(12): 35 -41 .