logo

SCIENTIA SINICA Informationis, Volume 47 , Issue 8 : 980-996(2017) https://doi.org/10.1360/N112017-00145

Network representation learning: an overview

More info
  • ReceivedJun 30, 2017
  • AcceptedAug 1, 2017
  • PublishedAug 23, 2017

Abstract


Funded by

国家重点基础研究发展计划(973)(2014CB340501)

国家社会科学基金重大招标项目(13,&,ZD190)

国家自然科学基金(61572273)

中国科协青年人才托举计划(2016QNRC001)

清华大学自主科研项目(201510804 06)


References

[1] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2014. 701--710. Google Scholar

[2] Battista G D, Eades P, Tamassia R. Algorithms for drawing graphs: an annotated bibliography. Comp Geometry, 1994, 4: 235-282 CrossRef Google Scholar

[3] Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement. Softw-Pract Exper, 1991, 21: 1129-1164 CrossRef Google Scholar

[4] Kamada T, Kawai S. An algorithm for drawing general undirected graphs. Inf Processing Lett, 1989, 31: 7-15 CrossRef Google Scholar

[5] Kobourov S G. Spring embedders and force directed graph drawing algorithms,. arXiv Google Scholar

[6] Roweis S T. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000, 290: 2323-2326 CrossRef PubMed ADS Google Scholar

[7] Saul L K, Roweis S T. An introduction to locally linear embedding. 2000. urlhttp://www.cs.toronto.edu/roweis/lle/publications.html. Google Scholar

[8] Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. In: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, Vancouver, 2001. 585--591. Google Scholar

[9] Tang L, Liu H. Leveraging social media networks for classification. Data Min Knowl Disc, 2011, 23: 447-478 CrossRef Google Scholar

[10] Chen M, Yang Q, Tang X. Directed graph embedding. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence, Hyderabad, 2007. 2707--2712. Google Scholar

[11] Tang L, Liu H. Relational learning via latent social dimensions. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 2009. 817--826. Google Scholar

[12] Mikolov T, Sutskever I, Chen K, et al. Distributed representations of words and phrases and their compositionality. In: Proceedings of Advances in Neural Information Processing Systems, Lake Tahoe, 2013. 3111--3119. Google Scholar

[13] Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space,. arXiv Google Scholar

[14] Mikolov T, Karafiát M, Burget L, et al. Recurrent neural network based language model. In: Proceedings of International Speech Communication Association, Makuhari, 2010. 1045--1048. Google Scholar

[15] Tang J, Qu M, Wang M, et al. Line: large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, Florence, 2015. 1067--1077. Google Scholar

[16] Yang C, Liu Z, Zhao D, et al. Network representation learning with rich text information. In: Proceedings of the 24th International Conference on Artificial Intelligence, Buenos Aires, 2015. 2111--2117. Google Scholar

[17] Cao S, Lu W, Xu Q. Grarep: learning graph representations with global structural information. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Melbourne, 2015. 891--900. Google Scholar

[18] Yang C, Sun M S, Liu Z Y, et al. Fast network embedding enhancement via high order proximity approximation. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), Melbourne, 2017. Google Scholar

[19] Wang D, Cui P, Zhu W. Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, 2016. 1225--1234. Google Scholar

[20] Yang J, Leskovec J. Overlapping community detection at scale: a nonnegative matrix factorization approach. In: Proceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, 2013. 587--596. Google Scholar

[21] Ou M, Cui P, Pei J, et al. Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, 2016. 1105--1114. Google Scholar

[22] Tu C, Wang H, Zeng X, et al. Community-enhanced network representation learning for network analysis,. arXiv Google Scholar

[23] Griffiths T L, Steyvers M. Finding scientific topics. Proc Natl Acad Sci USA, 2004, 101: 5228-5235 CrossRef PubMed ADS Google Scholar

[24] Tu C C, Liu H, Liu Z Y, et al. CANE: context-aware network embedding for relation modeling. In: Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, Vancouve, 2017. 1722--1731. Google Scholar

[25] Tu C C, Zhang W C, Liu Z Y, et al. Max-Margin DeepWalk: discriminative learning of network representation. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), New York, 2016. Google Scholar

[26] Li J Z, Zhu J, Zhang B. Discriminative deep random walk for network classification. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, Berlin, 2016. 1004--1013. Google Scholar

[27] Grover A, Leskovec J. Node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, 2016. 855--864. Google Scholar

[28] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations, Toulon, 2017. Google Scholar

[29] Yang Z, Cohen W, Salakhutdinov R. Revisiting semi-supervised learning with graph embeddings. In: Proceedings of the 33rd International Conference on International Conference on Machine Learning, New York, 2016. Google Scholar

[30] Tu C C, Zhang Z Y, Liu Z Y, et al. TransNet: translation-based network representation learning for social relation extraction. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), Melbourne, 2017. Google Scholar

  • Figure 1

    (Color online) The flow chart of NRL

  • Figure 2

    (Color online) The framework of SDNE (modified from [19])

  • Figure 3

    (Color online) The framework of CNRL (modified from [22])

  • Figure 4

    (Color online) Community detection results on Karate (Fast unfolding, CNRL-2, CNRL-4) (modified from [22])

  • Figure 5

    (Color online) The framework of TADW (modified from [16])

  • Figure 6

    The framework of CANE (modified from [24])

  • Figure 7

    (Color online) The framework of MMDW (modified from [25])

  • Figure 8

    (Color online) The visualization results of (a) DeepWalk and (b) MMDW (modified from [14])

  • Figure 9

    The framework of node2vec (modified from [27])

  • Figure 10

    (Color online) The framework of TransNet (modified from [30])

  • Figure 11

    (Color online) Link prediction results

  • Table 1   The comparison of LLE, Laplace eigenmap, and DGE
    Model Graph type
    Undirected Weighted Directed
    LLE checkmark
    Laplace eigenmap checkmark checkmark
    DGE checkmark checkmark checkmark
  • Table 2   The comparison between DeepWalk and word2vec
    Model Target Input Output
    Word2vec Words Sentences Word embeddings
    DeepWalk Nodes Node sequences Node embeddings
  • Table 3   The comparison of various NRL methods
    Method Matrix Accuracy Speed Performance
    Spectral clustering L Precise Fast Low
    DeepWalk $\sum_{k=1}^K \frac{A^k}{K}$ Approximate Fast Medium
    GraRep $A^k, k=1,\dots, K$ Precise Slow High
  • Table 4   Classification results on Cora
    Accuracy (%) Time (s)
    10%$^{\rm a)}$ 50%$^{\rm a)}$ 90%$^{\rm a)}$
    GF 50.8 (68.0) 61.8 (77.0) 64.8 (77.2) 4 (+0.1)
    SC 55.9 (68.7) 70.8 (79.2) 72.7 (80.0) 1 (+0.1)
    DeepWalk 71.3 (76.2) 76.9 (81.6) 78.7 (81.9) 31 (+0.1)
    LINE$_{1{\rm st}}$ 64.8 (70.1) 76.1 (80.9) 78.9 (82.2) 62 (+0.1)
    LINE$_{2{\rm nd}}$ 63.3 (73.3) 73.4 (80.1) 75.6 (80.3) 67 (+0.1)
    node2vec 76.9 (77.5) 81.0 (81.6) 81.4 (81.9) 56 (+0.1)
    TADW 78.1 (84.4) 83.1 (86.6) 82.4 (87.7) 2 (+0.1)
    GraRep 70.8 (76.9) 78.9 (82.8) 81.8 (84.0) 67 (+0.3)

    a) The number means training ratio.

  • Table 5   Classification results on BlogCatalog
    Macro-F1 (%) Micro-F1 (%) Time (s)
    1%$^{\rm a)}$ 5%$^{\rm a)}$ 9%$^{\rm a)}$ 1%$^{\rm a)}$ 5%$^{\rm a)}$ 9%$^{\rm a)}$
    GF 6.6 (7.9) 9.8 (11.3) 10.3 (12.2) 17.0 (19.6) 22.2 (25.0 23.7 (26.7) 19 (+1)
    SC 8.4 (9.3 13.1 (14.8 14.5 (17.0 19.4 (20.3) 26.9 (28.1) 29.0 (31.0) 10 (+1)
    DeepWalk 12.4 (13.6) 18.3 (20.1) 20.4 (22.0) 24.9 (26.4) 31.5 (33.7) 33.7 (35.9) 935 (+1)
    LINE$_{1{\rm st}}$ 11.1 (12.2) 16.6 (18.3) 18.6 (20.1) 23.1 (24.7) 29.3 (31.6) 31.8 (33.5) 241 (+1)
    LINE$_{2{\rm nd}}$ 10.3 (11.2) 15.0 (16.8) 16.5 (18.3) 21.5 (25.0 27.9 (31.6 30.0 (33.6 244 (+1)
    node2vec 12.5 (13.0) 19.2 (19.8) 21.9 (22.5) 25.0 (27.0) 31.9 (34.5) 35.1 (37.2) 454 (+1)

    a) The same as in Table 4.

  • Table 6   Classification results on Flickr
    Macro-F1 (%) Micro-F1 (%) Time (s)
    1%$^{\rm a)}$ 5%$^{\rm a)}$ 9%$^{\rm a)}$ 1%$^{\rm a)}$ 5%$^{\rm a)}$ 9%$^{\rm a)}$
    GF 4.3 (5.2 4.9 (5.4 5.0 (5.4) 21.1 (21.8) 22.0 (23.1) 21.7 (23.4) 241 (+8)
    SC 8.6 (10.9 11.6 (14.3 12.3 (15.0 24.1 (29.2 27.5 (34.1 28.3 (34.7 102 (+8)
    DeepWalk 10.5 (11.6 17.1 (17.8) 19.1 (19.8) 31.8 (33.1) 36.3 (36.7) 37.3 (37.6) 9,292 (+8)
    LINE$_{1{\rm st}}$ 10.3 (10.7) 16.0 (16.6) 17.6 (18.2) 32.0 (32.7) 35.9 (36.4) 36.8 (37.2) 2,664 (+8)
    LINE$_{2{\rm nd}}$ 7.8 (8.5) 13.1 (13.5) 14.7 (15.2) 30.0 (31.0) 34.2 (34.4) 35.1 (35.2) 2,740 (+8)

    a) The same as in Table 4.