Fast Sequence-Based Embedding with Diffusion Graphs

被引:37
作者
Rozemberczki, Benedek [1 ]
Sarkar, Rik [1 ]
机构
[1] Univ Edinburgh, Sch Informat, Edinburgh, Midlothian, Scotland
来源
COMPLEX NETWORKS IX | 2018年
基金
英国工程与自然科学研究理事会;
关键词
COMMUNITIES;
D O I
10.1007/978-3-319-73198-8_9
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
A graph embedding is a representation of graph vertices in a low- dimensional space, which approximately preserves properties such as distances between nodes. Vertex sequence-based embedding procedures use features extracted from linear sequences of nodes to create embeddings using a neural network. In this paper, we propose diffusion graphs as a method to rapidly generate vertex sequences for network embedding. Its computational efficiency is superior to previous methods due to simpler sequence generation, and it produces more accurate results. In experiments, we found that the performance relative to other methods improves with increasing edge density in the graph. In a community detection task, clustering nodes in the embedding space produces better results compared to other sequence-based embedding methods.
引用
收藏
页码:99 / 107
页数:9
相关论文
共 19 条
  • [1] Agarwal Nitin., 2009, ICWSM
  • [2] Many Random Walks Are Faster Than One
    Alon, Noga
    Avin, Chen
    Koucky, Michal
    Kozma, Gady
    Lotker, Zvi
    Tuttle, Mark R.
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (04) : 481 - 502
  • [3] [Anonymous], 2011, Large text compression benchmark
  • [4] The BioGRID interaction database: 2015 update
    Chatr-aryamontri, Andrew
    Breitkreutz, Bobby-Joe
    Oughtred, Rose
    Boucher, Lorrie
    Heinicke, Sven
    Chen, Daici
    Stark, Chris
    Breitkreutz, Ashton
    Kolas, Nadine
    O'Donnell, Lara
    Reguly, Teresa
    Nixon, Julie
    Ramage, Lindsay
    Winter, Andrew
    Sellam, Adnane
    Chang, Christie
    Hirschman, Jodi
    Theesfeld, Chandra
    Rust, Jennifer
    Livstone, Michael S.
    Dolinski, Kara
    Tyers, Mike
    [J]. NUCLEIC ACIDS RESEARCH, 2015, 43 (D1) : D470 - D478
  • [5] Finding local community structure in networks
    Clauset, A
    [J]. PHYSICAL REVIEW E, 2005, 72 (02)
  • [6] Fire M., 2011, Proceedings of the 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and IEEE Third International Conference on Social Computing (PASSAT/SocialCom 2011), P73, DOI 10.1109/PASSAT/SocialCom.2011.20
  • [7] Graph embedding techniques, applications, and performance: A survey
    Goyal, Palash
    Ferrara, Emilio
    [J]. KNOWLEDGE-BASED SYSTEMS, 2018, 151 : 78 - 94
  • [8] node2vec: Scalable Feature Learning for Networks
    Grover, Aditya
    Leskovec, Jure
    [J]. KDD'16: PROCEEDINGS OF THE 22ND ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2016, : 855 - 864
  • [9] Graph visualization and navigation in information visualization:: A survey
    Herman, I
    Melançon, G
    Marshall, MS
    [J]. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 2000, 6 (01) : 24 - 43
  • [10] McAuley J, 2012, LECT NOTES COMPUT SC, V7575, P828, DOI 10.1007/978-3-642-33765-9_59