基于路径相互关注的网络嵌入算法

doi:10.13232/j.cnki.jnju.2019.04.007

南京大学学报(自然科学版) ›› 2019, Vol. 55 ›› Issue (4): 573–580.doi: 10.13232/j.cnki.jnju.2019.04.007

所属专题：测试专题

基于路径相互关注的网络嵌入算法

钱付兰(),黄鑫,赵姝,张燕平

安徽大学计算机科学与技术学院，合肥，230601

收稿日期:2019-05-28 出版日期:2019-07-30 发布日期:2019-07-23
通讯作者: 钱付兰 E-mail:qianfulan@hotmail.com
基金资助:
国家重点研究与发展项目(2017YFB1401903);国家自然科学基金(61673020, 61702003,61876001);安徽省自然科学基金(1808085MF175)

Path⁃based mutual attention algorithm for network embedding

Fulan Qian(),Xin Huang,Shu Zhao,Yanping Zhang

School of Computer Science and Technology, Anhui University, Hefei, 230601, China

Received:2019-05-28 Online:2019-07-30 Published:2019-07-23
Contact: Fulan Qian E-mail:qianfulan@hotmail.com

摘要/Abstract

摘要：

网络嵌入，或者称为网络表示学习，旨在将网络中的节点映射到表示空间中，生成低维稠密的向量，从而在保留网络结构信息的前提下对网络中的节点进行表示，而后通过已有的机器学习方法解决诸如链接预测、节点分类、社团发现和网络可视化等下游任务.随机游走算法可以很好地探索网络中节点的局部结构，然而之前的基于随机游走的表示学习算法只能为节点产生一种角色嵌入，没有考虑到和不同邻居进行交互时节点扮演的不同角色嵌入.因此，提出一种基于路径相互关注的网络嵌入算法，使用节点随机游走产生的上下文信息，通过注意力机制为每个节点生成上下文相互关注的节点嵌入.在真实数据集上的实验结果表明，与三个经典的网络嵌入算法相比，该算法具有更好的表现.

关键词: 网络表示学习, 随机游走, 相互关注, 注意力机制

Abstract:

Network embedding,or network representation learning,aims to map nodes in the network into the representation space and generate low?dimensional dense vectors to represent the nodes in the network while preserving the network structure information,then solve downstream tasks such as link prediction,node classification,community discovery and network visualization through existing machine learning methods. The random walk algorithm can well explore the structure of nodes in the network. However,the previous representation learning algorithm based on random walk can only generate one kind of embedding for one node,without considering that the nodes play different roles when interacting with different neighbors. Therefore,this paper proposes a network embedding algorithm based on mutual attention of paths. Through the context information generated by random walks of nodes,each node generates a node embedding in which contexts are of mutual attention. And our algorithm has better performance than the three classic network embedding algorithms.

Key words: network representation learning, random walk, mutual attention, attention mechanism

中图分类号:

TP391

钱付兰, 黄鑫, 赵姝, 张燕平. 基于路径相互关注的网络嵌入算法[J]. 南京大学学报(自然科学版), 2019, 55(4): 573–580.

Fulan Qian, Xin Huang, Shu Zhao, Yanping Zhang. Path⁃based mutual attention algorithm for network embedding[J]. Journal of Nanjing University(Natural Sciences), 2019, 55(4): 573–580.

图/表 7

图1

图2

表1

表2

表3

表4

图3

参考文献 22

1	HamiltonW L,YingR,LeskovecJ. Representa?tion learning on graphs：methods and applications. 2017，arXiv：1709.05584.
2	涂存超,杨成,刘知远等. 网络表示学习综述. 中国科学：信息科学,2017,47(8)：980-996.
	TuC C,YangC,LiuZ Y,et al. Network representation learning：an overview. Scientia Sinica(Informationis),2017,47(8)：980-996.
3	ChenH C,PerozziB,Al?RfouR,et al. A tutorial on network embeddings. 2018,arXiv：1808.02590.
4	ZhangD K,YinJ,ZhuX Q,et al. Network representation learning： a survey. IEEE Transactions on Big Data,2018,doi：10.1109/TBDATA.2018.2850013. doi: 10.1109/TBDATA.2018.2850013
5	CaiH Y,ZhengV W,ChangK. A comprehensive survey of graph embedding：problems,techniques,and applications. IEEE Transactions on Know?ledge and Data Engineering,2018,30(9)：1616-1637.
6	TuC C,LiuH,LiuZ Y,et al. Cane：context?aware network embedding for relation modeling∥Proceedings of the 55^th Annual Meeting of the Association for Computational Linguistics. Vancouver,Canada：Association for Computa?tional Linguistics,2017：1722-1731.
7	YangC,LiuZ Y,ZhaoD L,et al. Network representation learning with rich text information∥Proceedings of the 24^th International Conference on Artificial Intelligence. Buenos Aires,Argentina：AAAI Press,2015：2111-2117.
8	SunX F,GuoJ,DingX,et al. A general framework for content?enhanced network repre?sentation learning. 2016,arXiv：1610.02906.
9	RoweisS T,SaulL K. Nonlinear dimensionality reduction by locally linear embedding. Science,2000,290(5500)：2323-2326.
10	BelkinM,NiyogiP. Laplacian eigenmaps and spectral techniques for embedding and clustering∥Proceedings of the 14^th International Conference on Neural Information Processing Systems. Vancouver,Canada： MIT Press,2001：585-591.
11	WangD,CuiP,ZhuW. Structural deep network embedding∥Proceedings of the 22^nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco,CA,USA：ACM,2016：1225-1234.
12	MikolovT,SutskeverI,ChenK,et al. Distributed representations of words and phrases and their compositionality∥Proceedings of the 26^th International Conference on Neural Information Processing Systems. Lake Tahoe,NV,USA：MIT Press,2013：3111-3119.
13	PerozziB,Al?RfouR,SkienaS. Deepwalk：online learning of social representations∥Proceedings of the 20^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York,NY,USA：ACM,2014：701-710.
14	TangJ,QuM,WangM Z,et al. Line：large?scale information network embedding∥Proceedings of the 24^th International Conference on World Wide Web. Florence,Italy：ACM,2015：1067-1077.
15	GroverA,LeskovecJ. node2vec：scalable feature learning for networks∥Proceedings of the 22^nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco,CA,USA：ACM,2016：855-864.
16	KalchbrennerN,GrefenstetteE,BlunsomP. A convolutional neural network for modelling sentences. 2014,arXiv：1404.2188.
17	HuB T,LuZ D,LiH,et al. Convolutional neural network architectures for matching natural language sentences∥Proceedings of the 27^th International Conference on Neural Information Processing Systems. Montreal,Canada：MIT Press,2014：2042-2050.
18	Dos SantosC,TanM,XiangB,et al. Attentive pooling networks. 2016,arXiv：1602.03609.
19	KingmaD P,BaJ. Adam：a method for stochastic optimization. 2014,arXiv：1412.6980.
20	McCallumA K,NigamK,RennieJ,et al. Automating the construction of internet portals with machine learning. Information Retrieval,2000,3(2)：127-163.
21	LeskovecJ,KleinbergJ,FaloutsosC. Graphs over time：densification laws,shrinking diameters and possible explanations∥Proceedings of the 11^th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. Chicago,IL,USA：ACM,2005：177-187.
22	NewmanM E J. Finding community structure in networks using the eigenvectors of matrices. Physical Review E,2006,74(3)：036104,doi：10.1103/PhysRevE.74.036104. doi: 10.1103/PhysRevE.74.036104

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

数据集	Cora	HepTh	NetScience
Vertices	2277	1038	1461
Edges	5214	1990	2742
Type	directed	directed	undirected
Labels	7	-	-

训练比例	15%	25%	35%	45%	55%	65%	75%	85%	95%
Deepwalk	56.0	63.0	70.2	75.5	80.1	85.2	85.3	87.8	90.3
LINE	55.0	58.6	66.4	73.0	77.6	82.8	85.6	88.4	89.3
Node2vec	55.9	62.4	66.1	75.0	78.7	81.6	85.9	87.3	88.2
PMANE	62.2	66.4	70.3	78.2	81.9	86.7	88.0	90.0	90.5

训练比例	15%	25%	35%	45%	55%	65%	75%	85%	95%
Deepwalk	55.2	66.0	70.0	75.7	81.3	83.3	87.6	88.9	88.0
LINE	53.7	60.4	66.5	73.9	78.5	83.8	87.5	87.7	87.6
Node2vec	57.1	63.6	69.9	76.2	84.3	87.3	88.4	89.2	89.2
PMANE	59.6	67.0	74.3	81.5	85.2	89.4	89.5	91.1	92.9

训练比例	15%	25%	35%	45%	55%	65%	75%	85%	95%
Deepwalk	80.6	83.5	90.1	94.5	95.3	97.4	98.2	98.4	97.6
LINE	77.8	81.5	88.4	92.0	94.2	96.8	97.8	98.4	98.7
Node2vec	80.5	85.5	89.8	93.8	95.0	97.3	97.4	98.0	97.2
PMANE	81.8	85.6	91.8	94.6	96.2	97.5	98.3	98.6	98.8

[1]	朱伟,张帅,辛晓燕,李文飞,王骏,张建,王炜. 结合区域检测和注意力机制的胸片自动定位与识别[J]. 南京大学学报(自然科学版), 2020, 56(4): 591-600.
[2]	徐扬,周文瑄,阮慧彬,孙雨,洪宇. 基于层次化表示的隐式篇章关系识别[J]. 南京大学学报(自然科学版), 2019, 55(6): 1000-1009.
[3]	郑文萍,刘韶倩,穆俊芳. 一种基于相对熵的随机游走相似性度量模型[J]. 南京大学学报(自然科学版), 2019, 55(6): 984-999.
[4]	曹欣怡,李鹤,王蔚. 基于语料库的语音情感识别的性别差异研究[J]. 南京大学学报(自然科学版), 2019, 55(5): 758-764.
[5]	顾健伟, 曾　诚, 邹恩岑, 陈　扬, 沈　艺, 陆　悠, 奚雪峰. 基于双向注意力流和自注意力结合的机器阅读理解[J]. 南京大学学报(自然科学版), 2019, 55(1): 125-132.
[6]	朱　尧, 朱启海, 毛晓蛟, 杨育彬. 基于有监督显著性检测的目标跟踪[J]. 南京大学学报(自然科学版), 2017, 53(4): 747-.
[7]	梁晋1,2，梁吉业1,2*，赵兴旺1,2. 一种面向大规模社会网络的社区发现算法[J]. 南京大学学报(自然科学版), 2016, 52(1): 159-166.
[8]	曹江中^1*，陈佩²，戴青云³，凌永权¹. 基于Markov随机游走的谱聚类相似图构造方法[J]. 南京大学学报(自然科学版), 2015, 51(4): 772-780.
[9]	施静静，张鹏，阮雅端，陈启美*. 多媒体信息网络相似度计算方法研究[J]. 南京大学学报(自然科学版), 2015, 51(2): 290-296.

基于路径相互关注的网络嵌入算法

Path⁃based mutual attention algorithm for network embedding

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 22

相关文章 9

Metrics

本文评价

推荐阅读 10