From Properties to Links: Deep Network Embedding on Incomplete Graphs

ABSTRACT

As an effective way of learning node representations in networks, network embedding has attracted increasing research interests recently. Most existing approaches use shallow models and only work on static networks by extracting local or global topology information of each node as the algorithm input. It is challenging for such approaches to learn a desirable node representation on incomplete graphs with a large number of missing links or on dynamic graphs with new nodes joining in. It is even challenging for them to deeply fuse other types of data such as node properties into the learning process to help better represent the nodes with insufficient links. In this paper, we for the first time study the problem of network embedding on incomplete networks. We propose a Multi-View Correlation-learning based Deep Network Embedding method named MVC-DNE to incorporate both the network structure and the node properties for more effectively and efficiently perform network embedding on incomplete networks. Specifically, we consider the topology structure of the network and the node properties as two correlated views. The insight is that the learned representation vector of a node should reflect its characteristics in both views. Under a multi-view correlation learning based deep autoencoder framework, the structure view and property view embeddings are integrated and mutually reinforced through both self-view and cross-view learning. As MVC-DNE can learn a representation mapping function, it can directly generate the representation vectors for the new nodes without retraining the model. Thus it is especially more efficient than previous methods. Empirically, we evaluate MVC-DNE over three real network datasets on two data mining applications, and the results demonstrate that MVC-DNE significantly outperforms state-of-the-art methods.

References

1. Galen Andrew, Raman Arora, Jeff Bilmes, and Karen Livescu. 2013. Deep canonical correlation analysis. In International Conference on Machine Learning. 1247--1255.
2. Mikhail Belkin and Partha Niyogi. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, Vol. 15, 6 (2003), 1373--1396.
3. Daniel Benyamin, Michael C McGinley, Michael Aaron Hall, and Nicholas J Bina. 2009. Social advertisement network. (May 18. 2009). US Patent App. 12/467,981.
4. Jianping Cao, Senzhang Wang, Fengcai Qiao, Hui Wang, Feiyue Wang, and S. Yu Philip. 2016. User-guided large attributed graph clustering with multiple sparse annotations Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 127--138.
5. Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015. Grarep: Learning graph representations with global structural information Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, 891--900.
6. Dumitru Erhan, Yoshua Bengio, Aaron Courville, Pierre Antoine Manzagol, Pascal Vincent, and Samy Bengio. 2010. Why Does Unsupervised Pre-training Help Deep Learning? Journal of Machine Learning Research Vol. 11, 3 (2010), 625--660.
7. Tom Fawcett. 2006. An introduction to ROC analysis. Pattern Recognition Letters Vol. 27, 8 (2006), 861--874.
8. Fangxiang Feng, Xiaojie Wang, and Ruifan Li. 2014. Cross-modal retrieval with correspondence autoencoder Proceedings of the 22nd ACM international conference on Multimedia. ACM, 7--16.
9. Francois Fouss, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on knowledge and data engineering, Vol. 19, 3 (2007).
10. Felix A. Gers, Jürgen Schmidhuber, and Fred Cummins. 2000. Learning to forget: Continual prediction with LSTM. Neural computation, Vol. 12, 10 (2000), 2451--2471.
11. Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 855--864.
12. G. E. Hinton, S Osindero, and Y. W. Teh. 1989. A fast learning algorithm for deep belief nets. Neural Computation, Vol. 18, 7 (1989), 1527--1554.
13. Qingbo Hu, Sihong Xie, Shuyang Lin, Senzhang Wang, and S Yu Philip. 2016. Clustering Embedded Approaches for Efficient Information Network Inference. Data Science and Engineering Vol. 1, 1 (2016), 29--40.
14. Diederik Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).
15. Jure Leskovec and Julian J. Mcauley. 2012. Learning to discover social circles in ego networks Advances in neural information processing systems. 539--547.
16. Chaozhuo Li, Senzhang Wang, Dejian Yang, Zhoujun Li, Yang Yang, and Xiaoming Zhang. 2017 a. PPNE: Property Preserving Network Embedding. In DASFAA. Springer, 163--179.
17. Chaozhuo Li, Senzhang Wang, Dejian Yang, Zhoujun Li, Yang Yang, and Xiaoming Zhang. 2017 b. Semi-Supervised Network Embedding. In DASFAA. Springer, 131--147.
18. Ping Li, Trevor J. Hastie, and Kenneth W. Church. 2006. Very sparse random projections. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 287--296.
19. David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. journal of the Association for Information Science and Technology, Vol. 58, 7 (2007), 1019--1031.
20. Jiquan Ngiam, Aditya Khosla, Mingyu Kim, Juhan Nam, Honglak Lee, and Andrew Y Ng. 2011. Multimodal deep learning. In Proceedings of the 28th international conference on machine learning (ICML-11). 689--696.
21. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research Vol. 12 (2011), 2825--2830.
22. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 701--710.
23. Sam T. Roweis and Lawrence K. Saul. 2000. Nonlinear dimensionality reduction by locally linear embedding. science, Vol. 290, 5500 (2000), 2323--2326.
24. Ruslan Salakhutdinov and Geoffrey Hinton. 2009. Semantic hashing. International Journal of Approximate Reasoning, Vol. 50, 7 (2009), 969--978.
25. Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine, Vol. 29, 3 (2008), 93.
26. Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. Line: Large-scale information network embedding. Proceedings of the 24th International Conference on World Wide Web. ACM, 1067--1077.
27. Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: extraction and mining of academic social networks Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 990--998.
28. Joshua B. Tenenbaum, Vin De Silva, and John C. Langford. 2000. A global geometric framework for nonlinear dimensionality reduction. science, Vol. 290, 5500 (2000), 2319--2323.
29. Cunchao Tu, Weicheng Zhang, Zhiyuan Liu, and Maosong Sun. 2016. Max-margin DeepWalk: discriminative learning of network representation Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016). 3889--3895.
30. Daixin Wang, Peng Cui, and Wenwu Zhu. 2016. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1225--1234.
31. Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. 2017. Community Preserving Network Embedding. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4--9, 2017, San Francisco, California, USA. 203--209. http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14589
32. Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. 2015. Network Representation Learning with Rich Text Information. Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2111--2117.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Dimensionality reduction and manifold learning

• Information systems

  • Information systems applications

    • Data mining