網絡表示學習

陳維政，張　巖，李曉明

（北京大學信息科學技術學院 北京 100871）

4 評測方法和應用場景

可以從定量和定性兩個角度評測網絡表示學習算法的性能，為此需要結合具體的應用場景。在當前的網絡表示學習的相關工作中，最常見的定量評測方法是節點標簽預測任務，表1列舉了一些常見的網絡數據及其對應的節點和標簽。

表1 網絡數據示例

在標簽預測任務中，網絡里部分節點的標簽是已知的，目的是推斷出其他節點的標簽。通常的過程是首先學習出每個節點的向量表示，然后利用已知標簽的節點訓練分類器（常用的分類器有logistics regression和SVM等），然后以其余節點的向量表示作為輸入，預測它們的標簽。如果在網絡表示學習的過程中利用到了標簽信息，通常可以提高標簽預測任務的性能^[15,45]，即半監督的網絡表示學習可能會優于無監督的網絡表示學習，這是因為前者學習到的網絡向量表示是和預測任務相關的。

常用的定性評測方法則是對網絡進行可視化展示^[6,9,31,45]，具體做法是對節點的向量表示進行降維，從而將網絡中的節點都映射到二維空間上的一個點。通常需要節點標簽信息，在可視化展示中，標簽相同的節點之間距離應該盡可能小。常用的高維向量降維工具有t-SNE^[45]、PE^[20]、PCA等。參考文獻[31]給出了利用t-SNE對一個論文合作網絡進行可視化的樣例^[31]，其中每一個節點代表一個用戶，每一種顏色代表一個研究領域，同一顏色的節點越集中則表明網絡表示學習算法的性能越好。

網絡表示學習中一個重要的參數是向量空間的維度k，在實驗環節需要調整參數k的設置。k的值過小，則學習到的節點向量的表示能力不足；k的值過大，算法的計算量會大大增加。在概率生成式算法中，k就是主題或者社團的個數。在基于深度學習的網絡表示學習算法中，k的取值一般是3位數。

5 結束語

本文總結了網絡表示學習的主要方法，并特別介紹了基于深度學習的網絡表示學習的最新進展。深度學習在社會網絡分析領域的應用還處于方興未艾的探索階段，但已有工作的結果是令人感到鼓舞的，基于深度學習的網絡表示學習算法（如Deepwalk、LINE）在網絡節點標簽預測任務上的表現，已經超越了傳統的基于譜的方法^[13]、基于最優化的方法^[46]。然而，這兩個算法缺少在其他社會網絡分析任務中的應用案例，普適性不足。基于以上分析，本文設想了未來兩個值得探索的研究方向。

雖然標簽預測任務十分常見，但是SNA領域還有很多其他重要的任務，比如影響力最大化、鏈接預測、社團檢測等，這些任務和標簽預測任務有著很大的不同：一方面，可以考慮針對特定的社會網絡分析任務，設計網絡表示學習模型；另一方面，無監督的網絡表示學習算法是否對多種任務具有普適性也值得探究。

現實中存在著大量的異構網絡，而且節點都對應著豐富的標簽、文本、圖像、語音等多媒體信息。如何使基于深度學習的網絡表示學習算法可以同時利用網絡的結構和節點自身的特征信息，是一個重要的問題。這涉及如何設計網絡結構，如何從網絡中采樣節點對等細節。TADW算法通過和Deepwalk等價的矩陣分解方法，在同構網絡的表示學習中融入了節點自身的文本信息，這也為從矩陣分解的視角看待網絡表示學習的擴展提供了有益的啟示。

參考文獻

[1] Mairal J, Ponce J, Sapiro G, et al. Superviseddictionary learning. Proceedings of the 2009 Conference on Neural InformationProcessing Systems, Vancouver, Canada, 2009:1033~1040

[2] Roweis S T, Saul L K. Nonlinear dimensionalityreduction by locally linear embedding. Science, 2000, 290(5): 2323~2326

[3] Hyv?rinen A, Oja E. Independent componentanalysis: algorithms and applications. Neural networks, 2000, 13(4~5): 411~430

[4] Lee H, BattleA, Rain R, et al. Efficient sparsecoding algorithms. Proceedings of the 2006 Conference on Neural InformationProcessing Systems. Vancouver, Canada, 2006:801~808

[5] Bengio Y, Courville A, Vincent P. Representationlearning: a review and new perspectives. IEEE Transactions on Pattern Analysisand Machine Intelligence, 2013, 35(8): 1798~1828

[6] Chen M, Yang Q, Tang X O. Directed graphembedding. Proceedings of the20th International Joint Conference on ArtificialIntelligence (IJCAI), Hyderabad, India, 2007:2707~2712

[7] Kannan R,Vempala S. Spectral algorithms.Theoretical Computer Science, 2009, 4(3~4):157~288

[8] Brand M, Huang K. A unifying theorem forspectral embedding and clustering. Proceedings of the Ninth InternationalConference onWorkshop on Artificial Intelligence and Statistics, Florida, USA,2003

[9] Le T, Lauw H W. Probabilistic Latent DocumentNetwork Embedding. Proceedings of 2014 IEEE International Conference on DataMining (ICDM), Shenzhen, China, 2014:270~279

[10] Wojciech C, Brooks M J. A note on the locallylinear embedding algorithm. International Journal of Pattern Recognition andArtificial Intelligence, 2009, 23(8): 1739~1752

[11] Belkin M, Niyogi P. Laplacian eigenmaps andspectral techniques for embedding and clustering. Proceedings of AnnualConference on Neural Information Processing Systems(NIPS), 2001:585~591

[12] Tang L, Liu H. Relational learning via latentsocial dimensions. Proceedings of the 15th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining,Paris, France, 2009:817~826

[13] Newman M. Modularity and community structure innetworks. Proceedings of the National Academy of Sciences, 2006, 103(23):8577~8582

[14] Zhou D Y, Huang J Y, Sch?lkopf B. Learning fromlabeled and unlabeled data on a directed graph. Proceedings of the 22ndInternational Conference on Machine Learning, Bonn, Germany, 2005: 1036~1043

[15] Jacob Y, Denoyer L, Gallinari P. Learninglatent representations of nodes for classifying in heterogeneous socialnetworks. Proceedings of the 7th ACM International Conference on Web Search andData Mining, New York, USA, 2014: 373~382

[16] Yang J, Leskovec J. Modeling informationdiffusion in implicit networks. Proceedings of 2010 IEEE 10th InternationalConference on Data Mining (ICDM), Sydney, Australia, 2010: 599~608

[17] Bourigault S, Lagnier C, Lamprier S, et al. Learning social network embeddings for predicting information diffusion.Proceedings of the 7th ACM International Conference on Web Search and DataMining, New York, USA, 2014: 393~402

[18] Nallapati R, Ahmed A, Xing E, et al. Jointlatent topic models for text and citations. Proceedings of the 14th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining, Las Vegas,USA, 2008: 542~550

[19] Chang J, Blei D. Relational topic models fordocument networks. International Conference on Artificial Intelligence andStatistics, Clearwater Beach, Florida, USA, 2009: 81~88

[20] Iwata T, Saito K, Ueda N, et al. Parametricembedding for class visualization. Neural Computation, 2007, 19 (9): 2536~2556

[22] Gopalan P, Blei D. Efficient discovery ofoverlapping communities in massive networks. Proceedings of the NationalAcademy of Sciences, 2013,110 (36): 14534~14539

[22] Gopalan P, Mimno D, Gerrish S, et al. Scalableinference of overlapping communities. Proceedings of the 2012 Conference onNeural Information Processing Systems, Lake Tahoe, USA, 2012: 2249~2257

[23] Hu Z T, Yao J J, Cui B, et al. Community leveldiffusion extraction. Proceedings of the 2015 ACM SIGMOD InternationalConference on Management of Data, Melbourne, Victoria, Australia, 2015:1555~1569

[24] Kobourov S. Spring embedders and force directedgraph drawing algorithms. arXiv preprint 2012, arXiv:1201.3011, 2012

[25] Fruchterman T, Reingold E. Graph drawing byforce-directed placement. Software-Practice & Experience, 1991, 21(11):1129~1164

[26] Kamada T, Satoru Kawai. An algorithm fordrawing general undirected graphs. Information Processing Letters, 1989, 31(1):7~15

[27] Bastian M, Heymann S, Jacomy M. Gephi: an opensource software for exploring and manipulating networks. Proceedings of theThird International Conference on Weblogs and Social Media, San Jose,California, USA, 2009: 361~362

[28] Ellson J, Gansner E, Koutsofios L, et al.Graphviz-open source graph drawing tools. Graph Drawing. Berlin Heidelberg:Springer, 2002

[29] Bengio Y, Goodfellow I, Courville A. DeepLearning, 2015

[30] Perozzi B, Al-Rfou R, Skiena S. Deepwalk:online learning of social representations. Proceedings of the 20th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining. New York City,USA, 2014: 701~710

[31] Tang J, Qu M, Wang M Z, et al. LINE:large-scale information network embedding. Proceedings of the 24thInternational Conference on World Wide Web, Florence, Italy, 2015: 1067~1077

[32] Mikolov T, Sutskever I, Chen K, et al.Distributed representations of words and phrases and their compositionality.Proceedings of the 2013 Conference on Neural Information Processing Systems,Lake Tahoe, USA, 2013: 3111~3119

[33] Mikolov T, Chen K, Corrado G, et al. Efficientestimation of word representations in vector space. arXiv preprintarXiv:1301.3781, 2013

[34] Mikolov T, Yih W T, Zweig G. Linguisticregularities in continuous space word representations. Proceedings of the 2013Conference on NAACL and SEM, Atlanta, USA, 2013: 746~751

[35] Hinton G E. Learning distributedrepresentations of concepts. Proceedings of the Eighth Annual Conference on theCognitive Science Society, Amherst, Mass, USA, 1986: 1~12

[36] Bengio Y, Ducharme R, Vincent P, et al. Aneural probabilistic language model. The Journal of Machine Learning Research,2003(3): 1137~1155

[37] Morin F, Bengio Y. Hierarchical probabilisticneural network language model. Proceedings of the 10th International WorkshopConference on Artificial Intelligence and Statistics, Barbados, 2005: 246~252

[38] Collober R, Weston J. A unified architecturefor natural language processing: deep neural networks with multitask learning.Proceedings of the 25th International Conference on Machine Learning, Helsinki,Finland, 2008: 160~167

[39] Gutmann M, Hyv?rinen A. Noise-contrastiveestimation: a new estimation principle for unnormalized statistical models.Proceedings on International Conference on Artificial Intelligence andStatistics, Sardinia, Italy, 2010: 297~304

[40] Yang C, Liu Z Y. Comprehend deepwalk as matrixfactorization. arXivpreprint arXiv:1501.00358, 2015

[41] Goldberg Y, Levy O. word2vec Explained:deriving Mikolov et al.'s negative-sampling word-embedding method. arXivpreprint arXiv:1402.3722, 2014

[42] Li Y T, Xu L L, Tian F, et al. Word embeddingrevisited: anew representation learning and explicit matrix factorizationperspective. Proceedings of the 24th International Joint Conference onArtificial Intelligence, Buenos Aires, Argentina, 2015: 3650~3656

[43] Yang C, Liu Z Y, Zhao D L, et al. Networkrepresentation learning with rich text information. Proceedings of the 24thInternational Joint Conference on Artificial Intelligence, Buenos Aires,Argentina, 2015:2111~2117

[44] Yu H F, Jain P, Kar P, et al. Large-scalemulti-label learning with missing labels. arXiv preprint arXiv:1307.5101, 2013

[45] Tang J, Qu M, Mei Q Z. PTE: predictive textembedding through large-scale heterogeneous text networks. Proceedings of the21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Sydney,Australia, 2015

[46] Ahmed A, Shervashidze N, Narayanamurthy S,et al. Distributed large-scale natural graph factorization. Proceedings of the22nd International Conference on World Wide Web, Rio, Brazil, 2013: 37~48

---

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的《大数据》2015年第3期“网络大数据专题”——网络表示学习（下）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。