国家重点基础研究发展计划(973)(2014CB340501)
国家社会科学基金重大招标项目(13,&,ZD190)
国家自然科学基金(61572273)
中国科协青年人才托举计划(2016QNRC001)
清华大学自主科研项目(201510804 06)
[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
Figure 3
(Color online) The framework of CNRL (modified from
Figure 4
(Color online) Community detection results on Karate (Fast unfolding, CNRL-2, CNRL-4) (modified from
Figure 5
(Color online) The framework of TADW (modified from
Figure 6
The framework of CANE (modified from
Figure 7
(Color online) The framework of MMDW (modified from
Figure 8
(Color online) The visualization results of (a) DeepWalk and (b) MMDW (modified from
Figure 9
The framework of node2vec (modified from
Figure 10
(Color online) The framework of TransNet (modified from
Figure 11
(Color online) Link prediction results
Model | Graph type | ||
Undirected | Weighted | Directed | |
LLE | checkmark | – | – |
Laplace eigenmap | checkmark | checkmark | – |
DGE | checkmark | checkmark | checkmark |
Model | Target | Input | Output |
Word2vec | Words | Sentences | Word embeddings |
DeepWalk | Nodes | Node sequences | Node embeddings |
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 |
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.
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
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