1. bookVolumen 9 (2019): Heft 1 (January 2019)
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2449-6499
Erstveröffentlichung
30 Dec 2014
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
access type Uneingeschränkter Zugang

On Graph Mining With Deep Learning: Introducing Model R for Link Weight Prediction

Online veröffentlicht: 20 Aug 2018
Volumen & Heft: Volumen 9 (2019) - Heft 1 (January 2019)
Seitenbereich: 21 - 40
Eingereicht: 20 Oct 2017
Akzeptiert: 13 Nov 2017
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2449-6499
Erstveröffentlichung
30 Dec 2014
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
Abstract

Deep learning has been successful in various domains including image recognition, speech recognition and natural language processing. However, the research on its application in graph mining is still in an early stage. Here we present Model R, a neural network model created to provide a deep learning approach to the link weight prediction problem. This model uses a node embedding technique that extracts node embeddings (knowledge of nodes) from the known links’ weights (relations between nodes) and uses this knowledge to predict the unknown links’ weights. We demonstrate the power of Model R through experiments and compare it with the stochastic block model and its derivatives. Model R shows that deep learning can be successfully applied to link weight prediction and it outperforms stochastic block model and its derivatives by up to 73% in terms of prediction accuracy. We analyze the node embeddings to confirm that closeness in embedding space correlates with stronger relationships as measured by the link weight. We anticipate this new approach will provide effective solutions to more graph mining tasks.

[1] A. Hannun, C. Case, J. Casper, B. Catanzaro, G. Diamos, E. Elsen, R. Prenger, S. Satheesh, S. Sengupta, A. Coates et al, Deep speech: Scaling up end-to-end speech recognition, arXiv preprint arXiv:1412.5567, 2014.Search in Google Scholar

[2] K. Simonyan and A. Zisserman, Very deep convolutional networks for large-scale image recognition, arXiv preprint arXiv:1409.1556, 2014.Search in Google Scholar

[3] K. Yao, G. Zweig, M.-Y. Hwang, Y. Shi, and D. Yu, Recurrent neural networks for language understanding. in INTERSPEECH, 2013, pp. 2524–2528.10.21437/Interspeech.2013-569Search in Google Scholar

[4] O. Barkan and N. Koenigstein, Item2vec: neural item embedding for collaborative filtering, in Machine Learning for Signal Processing (MLSP), 2016 IEEE 26th International Workshop on. IEEE, 2016, pp. 1–6.10.1109/MLSP.2016.7738886Search in Google Scholar

[5] A. Grover and J. Leskovec, node2vec: Scalable feature learning for networks, in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016, pp. 855–864.10.1145/2939672.2939754Search in Google Scholar

[6] D. Liben-Nowell and J. Kleinberg, The link-prediction problem for social networks, Journal of the Association for Information Science and Technology, vol. 58, no. 7, pp. 1019–1031, 2007.Search in Google Scholar

[7] M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki, Link prediction using supervised learning, in SDM06: Workshop on Link Analysis, Counterterrorism and Security, 2006.Search in Google Scholar

[8] J. Zhao, L. Miao, J. Yang, H. Fang, Q.-M. Zhang, M. Nie, P. Holme, and T. Zhou, Prediction of links and weights in networks by reliable routes, Scientific Reports, vol. 5, 2015.10.1038/srep12261Search in Google Scholar

[9] L. A. Adamic and E. Adar, Friends and neighbors on the web, Social Networks, vol. 25, no. 3, pp. 211–230, 2003.10.1016/S0378-8733(03)00009-1Search in Google Scholar

[10] T. Murata and S. Moriyasu, Link prediction of social networks based on weighted proximity measures, in IEEE/WIC/ACM International Conference on Web Intelligence (WI). IEEE, 2007, pp. 85–88.10.1109/WI.2007.52Search in Google Scholar

[11] H. A. Taha, Operations Research: An Introduction (For VTU). Pearson Education India, 1982.Search in Google Scholar

[12] P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social Networks, vol. 5, no. 2, pp. 109–137, 1983.10.1016/0378-8733(83)90021-7Search in Google Scholar

[13] C. Aicher, A. Z. Jacobs, and A. Clauset, Learning latent block structure in weighted networks, Journal of Complex Networks, p. cnu026, 2014.10.1093/comnet/cnu026Search in Google Scholar

[14] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, Distributed representations of words and phrases and their compositionality, in Advances in Neural Information Processing Systems, 2013, pp. 3111–3119.Search in Google Scholar

[15] T. Mikolov, W.-t. Yih, and G. Zweig, Linguistic regularities in continuous space word representations. in NAACL HLT, vol. 13, 2013, pp. 746–751.Search in Google Scholar

[16] Q. Le and T. Mikolov, Distributed representations of sentences and documents, in Proceedings of the 31st International Conference on Machine Learning (ICML-14), 2014, pp. 1188–1196.Search in Google Scholar

[17] B. Perozzi, R. Al-Rfou, and S. Skiena, Deepwalk: Online learning of social representations, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014, pp. 701–710.10.1145/2623330.2623732Search in Google Scholar

[18] P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol, Extracting and composing robust features with denoising autoencoders, in Proceedings of the 25th International Conference on Machine Learning. ACM, 2008, pp. 1096–1103.10.1145/1390156.1390294Search in Google Scholar

[19] G. E. Hinton and R. R. Salakhutdinov, Reducing the dimensionality of data with neural networks, Science, vol. 313, no. 5786, pp. 504–507, 2006.Search in Google Scholar

[20] X. Feng, Y. Zhang, and J. Glass, Speech feature denoising and dereverberation via deep autoencoders for noisy reverberant speech recognition, in Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on. IEEE, 2014, pp. 1759–1763.10.1109/ICASSP.2014.6853900Search in Google Scholar

[21] C.-Y. Liou, W.-C. Cheng, J.-W. Liou, and D.-R. Liou, Autoencoder for words, Neurocomputing, vol. 139, pp. 84–96, 2014.10.1016/j.neucom.2013.09.055Search in Google Scholar

[22] O. Abdel-Hamid, A.-r. Mohamed, H. Jiang, L. Deng, G. Penn, and D. Yu, Convolutional neural networks for speech recognition, IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 22, no. 10, pp. 1533–1545, 2014.Search in Google Scholar

[23] A. Van den Oord, S. Dieleman, and B. Schrauwen, Deep content-based music recommendation, in Advances in Neural Information Processing Systems, 2013, pp. 2643–2651.Search in Google Scholar

[24] A. Krizhevsky, I. Sutskever, and G. E. Hinton, Imagenet classification with deep convolutional neural networks, in Advances in Neural Information Processing Systems, 2012, pp. 1097–1105.Search in Google Scholar

[25] R. Collobert and J. Weston, A unified architecture for natural language processing: Deep neural networks with multitask learning, in Proceedings of the 25th International Conference on Machine Learning. ACM, 2008, pp. 160–167.10.1145/1390156.1390177Search in Google Scholar

[26] A. M. Elkahky, Y. Song, and X. He, A multi-view deep learning approach for cross domain user modeling in recommendation systems, in Proceedings of the 24th International Conference on World Wide Web. ACM, 2015, pp. 278–288.10.1145/2736277.2741667Search in Google Scholar

[27] R. Socher, Y. Bengio, and C. D. Manning, Deep learning for nlp (without magic), in Tutorial Abstracts of ACL 2012. Association for Computational Linguistics, 2012, pp. 5–5.Search in Google Scholar

[28] R. Socher, J. Bauer, C. D. Manning, and A. Y. Ng, Parsing with compositional vector grammars. in ACL (1), 2013, pp. 455–465.Search in Google Scholar

[29] R. Socher, A. Perelygin, J. Y.Wu, J. Chuang, C. D. Manning, A. Y. Ng, C. Potts et al., Recursive deep models for semantic compositionality over a sentiment treebank, in Proceedings of the Conference on Empirical Methods on Natural Language Processing (EMNLP), vol. 1631, 2013, p. 1642.Search in Google Scholar

[30] Y. Shen, X. He, J. Gao, L. Deng, and G. Mesnil, A latent semantic model with convolutional-pooling structure for information retrieval, in Proceedings of the 23rd ACM International Conference on Information and Knowledge Management. ACM, 2014, pp. 101–110.10.1145/2661829.2661935Search in Google Scholar

[31] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, Learning representations by back-propagating errors, Cognitive Modeling, vol. 5, no. 3, p. 1, 1988.Search in Google Scholar

[32] Y. A. LeCun, L. Bottou, G. B. Orr, and K.-R. Müller, Efficient backprop, in Neural Networks: Tricks of the Trade. Springer, 2012, pp. 9–48.10.1007/978-3-642-35289-8_3Search in Google Scholar

[33] J. Mairal, F. Bach, J. Ponce, and G. Sapiro, Online learning for matrix factorization and sparse coding, The Journal of Machine Learning Research, vol. 11, pp. 19–60, 2010.Search in Google Scholar

[34] S. Smale and D.-X. Zhou, Learning theory estimates via integral operators and their approximations, Constructive Approximation, vol. 26, no. 2, pp. 153–172, 2007.10.1007/s00365-006-0659-ySearch in Google Scholar

[35] Y. LeCun, Y. Bengio, and G. Hinton, Deep learning, Nature, vol. 521, no. 7553, pp. 436–444, 2015.Search in Google Scholar

[36] V. Colizza, R. Pastor-Satorras, and A. Vespignani, Reaction–diffusion processes and metapopulation models in heterogeneous networks, Nature Physics, vol. 3, no. 4, pp. 276–282, 2007.10.1038/nphys560Search in Google Scholar

[37] R. K. Pan, K. Kaski, and S. Fortunato, World citation and collaboration networks: uncovering the role of geography in science, Scientific Reports, vol. 2, 2012.10.1038/srep00902350935023198092Search in Google Scholar

[38] M. A. Porter, P. J. Mucha, M. E. Newman, and C. M. Warmbrand, A network analysis of committees in the us house of representatives, Proceedings of the National Academy of Sciences of the United States of America, vol. 102, no. 20, pp. 7057–7062, 2005.Search in Google Scholar

[39] T. Opsahl and P. Panzarasa, Clustering in weighted networks, Social Networks, vol. 31, no. 2, pp. 155–163, 2009.10.1016/j.socnet.2009.02.002Search in Google Scholar

[40] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard et al., Tensorflow: A system for large-scale machine learning. in Operating Systems Design and Implementation (OSDI), vol. 16, 2016, pp. 265–283.Search in Google Scholar

[41] F. M. Harper and J. A. Konstan, The movielens datasets: History and context, ACM Transactions on Interactive Intelligent Systems (TiiS), vol. 5, no. 4, p. 19, 2015.10.1145/2827872Search in Google Scholar

Empfohlene Artikel von Trend MD

Planen Sie Ihre Fernkonferenz mit Scienceendo