vec2Link: Unifying Heterogeneous Data for Social Link Prediction

ABSTRACT

Recent advances in network representation learning have enabled significant improvements in the link prediction task, which is at the core of many downstream applications. As an increasing amount of mobility data becoming available due to the development of location technologies, we argue that this resourceful user mobility data can be used to improve link prediction performance. In this paper, we propose a novel link prediction framework that utilizes user offline check-in behavior combined with user online social relations. We model user offline location preference via probabilistic factor model and represent user social relations using neural network embedding. Furthermore, we employ locality-sensitive hashing to project the aggregated user representation into a binary matrix, which not only preserves the data structure but also speeds up the followed convolutional network learning. By comparing with several baseline methods that solely rely on social network or mobility data, we show that our unified approach significantly improves the performance.

References

1. Michael Backes, Mathias Humbert, Jun Pang, and Yang Zhang. 2017. walk2friends: Inferring Social Links from Mobility Profiles. In CCS .
2. Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2017. A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications. (2017). arxiv: 1709.07604v1
3. Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015. GraRep: Learning Graph Representations with Global Structural Information. In CIKM .
4. Moses Charikar. 2002. Similarity estimation techniques from rounding algorithms. In STOC .
5. Ye Chen, Michael Kapralov, Dmitry Pavlov, and John F Canny. 2009. Factor Modeling for Advertisement Targeting. In NIPS .
6. Sanjoy Dasgupta, Charles F Stevens, and Saket Navlakha. 2017. A neural algorithm for a fundamental computing problem. Science , Vol. 358, 6364 (2017), 793--796.
7. Michel X Goemans and David P Williamson. 1995. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM (1995).
8. Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In KDD .
9. William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Representation Learning on Graphs: Methods and Applications. IEEE Data Eng. Bull. , Vol. 40, 3 (2017), 52--74.
10. Hsun-Ping Hsieh, Rui Yan, and Cheng-Te Li. 2015. Where You Go Reveals Who You Know: Analyzing Social Ties from Millions of Footprints. In CIKM .
11. Qinghao Hu, Peisong Wang, and Jian Cheng. 2018. From Hashing to CNNs: Training Binary Weight Networks via Hashing. In AAAI .
12. Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC .
13. David Liben-Nowell and Jon M Kleinberg. 2003. The link prediction problem for social networks. In CIKM .
14. Bin Liu, Hui Xiong, Spiros Papadimitriou, Yanjie Fu, and Zijun Yao. 2015. A General Geographical Probabilistic Factor Model for Point of Interest Recommendation. TKDE (2015).
15. Hao Ma, Chao Liu, Irwin King, and Michael R Lyu. 2011. Probabilistic factor models for web site recommendation. In SIGIR .
16. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. In KDD .
17. L. F. Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. 2017. struc2vec: Learning Node Representations from Structural Identity. In KDD .
18. Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In NIPS .
19. Ryan Spring and Anshumali Shrivastava. 2017. Scalable and Sustainable Deep Learning via Randomized Hashing. In KDD .
20. Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In WWW .
21. Cheng Wang, Jieren Zhou, and Bo Yang. 2017b. From Footprint to Friendship: Modeling User Followership in Mobile Social Networks From Check-in Data. In SIGIR .
22. Dashun Wang, Dino Pedreschi, Chaoming Song, Fosca Giannotti, and Albert-László Barabási. 2011. Human mobility, social ties, and link prediction. In KDD .
23. Hongjian Wang, Zhenhui Li, and Wang-Chien Lee. 2014. PGT: Measuring Mobility Relationship Using Personal, Global and Temporal Factors. In ICDM .
24. Pinghui Wang, Feiyang Sun, Di Wang, Jing Tao, Xiaohong Guan, and Albert Bifet. 2017a. Inferring Demographics and Social Networks of Mobile Device Users on Campus From AP-Trajectories. In WWW .

Index Terms

• Networks

  • Network types

    • Overlay and other logical network structures

      • Online social networks

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Social networks