Cross-Dependency Inference in Multi-Layered Networks: A Collaborative Filtering Perspective

Abstract

The increasingly connected world has catalyzed the fusion of networks from different domains, which facilitates the emergence of a new network model—multi-layered networks. Examples of such kind of network systems include critical infrastructure networks, biological systems, organization-level collaborations, cross-platform e-commerce, and so forth. One crucial structure that distances multi-layered network from other network models is its cross-layer dependency, which describes the associations between the nodes from different layers. Needless to say, the cross-layer dependency in the network plays an essential role in many data mining applications like system robustness analysis and complex network control. However, it remains a daunting task to know the exact dependency relationships due to noise, limited accessibility, and so forth. In this article, we tackle the cross-layer dependency inference problem by modeling it as a collective collaborative filtering problem. Based on this idea, we propose an effective algorithm F<scp;>ascinate</scp;> that can reveal unobserved dependencies with linear complexity. Moreover, we derive F<scp;>ascinate</scp;>-ZERO, an online variant of F<scp;>ascinate</scp;> that can respond to a newly added node timely by checking its neighborhood dependencies. We perform extensive evaluations on real datasets to substantiate the superiority of our proposed approaches.

References

1. Federico Battiston, Vincenzo Nicosia, and Vito Latora. 2014. Structural measures for multiplex networks. Physical Review E 89, 3 (2014), 032804.
2. Michele Berlingerio, Michele Coscia, Fosca Giannotti, Anna Monreale, and Dino Pedreschi. 2011. Foundations of multidimensional network analysis. In Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE, 485--489.
3. John S. Breese, David Heckerman, and Carl Kadie. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., 43--52.
4. Sergey V. Buldyrev, Roni Parshani, Gerald Paul, H. Eugene Stanley, and Shlomo Havlin. 2010. Catastrophic cascade of failures in interdependent networks. Nature 464, 7291 (2010), 1025--1028.
5. Chen Chen, Jingrui He, Nadya Bliss, and Hanghang Tong. 2015. On the connectivity of multi-layered networks: Models, measures and optimal control. In Proceedings of the 2015 IEEE 15th International Conference on Data Mining (ICDM). IEEE, 715--720.
6. Chen Chen, Hanghang Tong, Lei Xie, Lei Ying, and Qing He. 2016. FASCINATE: Fast cross-layer dependency inference on multi-layered networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 765--774.
7. Wei Chen, Wynne Hsu, and Mong Li Lee. 2013. Making recommendations from multiple domains. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 892--900.
8. Allan Peter Davis, Cynthia J. Grondin, Kelley Lennon-Hopkins, Cynthia Saraceni-Richards, Daniela Sciaky, Benjamin L. King, Thomas C. Wiegers, and Carolyn J. Mattingly. 2015. The comparative toxicogenomics database’s 10th year anniversary: Update 2015. Nucleic Acids Research 43, D1 (2015), D914--D920.
9. Chris Ding, Tao Li, Wei Peng, and Haesun Park. 2006. Orthogonal nonnegative matrix t-factorizations for clustering. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 126--135.
10. Jianxi Gao, Sergey V. Buldyrev, Shlomo Havlin, and H. Eugene Stanley. 2011. Robustness of a network of networks. Physical Review Letters 107, 19 (2011), 195701.
11. Jianxi Gao, Sergey V. Buldyrev, H. Eugene Stanley, and Shlomo Havlin. 2012. Networks formed from interdependent networks. Nature Physics 8, 1 (2012), 40--48.
12. David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry. 1992. Using collaborative filtering to weave an information tapestry. Communications of the ACM 35, 12 (1992), 61--70.
13. Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. 2016. Fast matrix factorization for online recommendation with implicit feedback. In Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’16). 549--558.
14. Lenwood S. Heath and Allan A. Sioson. 2009. Multimodal networks: Structure and operations. IEEE/ACM Transactions on Computational Biology and Bioinformatics 6, 2 (2009), 321--332.
15. Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative filtering for implicit feedback datasets. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM’08). IEEE, 263--272.
16. Mikko Kivelä, Alex Arenas, Marc Barthelemy, James P. Gleeson, Yamir Moreno, and Mason A. Porter. 2014. Multilayer networks. Journal of Complex Networks 2, 3 (2014), 203--271.
17. Yehuda Koren. 2009. Collaborative filtering with temporal dynamics. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 447--456.
18. Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 8 (2009), 30--37.
19. Daniel D. Lee and H. Sebastian Seung. 2001. Algorithms for non-negative matrix factorization. In Proceedings of the Advances in Neural Information Processing Systems. 556--562.
20. Bin Li, Qiang Yang, and Xiangyang Xue. 2009. Can movies and books collaborate? Cross-domain collaborative filtering for sparsity reduction. In Proceedings of the 21st International Jont Conference on Artifical Intelligence, Vol. 9. 2052--2057.
21. Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Trevino Robert, Jiliang Tang, and Huan Liu. 2016a. Feature selection: A data perspective. (2016). arXiv:1601.07996.
22. Jundong Li, Xia Hu, Liang Wu, and Huan Liu. 2016b. Robust unsupervised feature selection on networked data. In Proceedings of the 2016 SIAM International Conference on Data Mining. SIAM, 387--395.
23. Liangyue Li, Hanghang Tong, Nan Cao, Kate Ehrlich, Yu-Ru Lin, and Norbou Buchler. 2015. Replacing the irreplaceable: Fast algorithms for team member recommendation. In Proceedings of the 24th International Conference on World Wide Web. ACM, 636--646.
24. Yanen Li, Jia Hu, ChengXiang Zhai, and Ye Chen. 2010. Improving one-class collaborative filtering by incorporating rich user information. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management. ACM, 959--968.
25. Chuan-bi Lin. 2007. Projected gradient methods for nonnegative matrix factorization. Neural Computation 19, 10 (2007), 2756--2779.
26. Jialu Liu, Chi Wang, Jing Gao, Quanquan Gu, Charu C. Aggarwal, Lance M. Kaplan, and Jiawei Han. 2015b. GIN: A clustering model for capturing dual heterogeneity in networked data. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 388--396.
27. Rui Liu, Wei Cheng, Hanghang Tong, Wei Wang, and Xiang Zhang. 2015a. Robust multi-network clustering via joint cross-domain cluster alignment. In Proceedings of the 2015 IEEE International Conference on Data Mining (ICDM’15). IEEE Computer Society, Washington, DC, 291--300.
28. Zhongqi Lu, Weike Pan, Evan Wei Xiang, Qiang Yang, Lili Zhao, and ErHeng Zhong. 2013. Selective transfer learning for cross domain recommendation. In Proceedings of the SIAM International Conference on Data Mining. SIAM, 641--649.
29. Hao Ma. 2013. An experimental study on implicit social recommendation. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 73--82.
30. Jingchao Ni, Hanghang Tong, Wei Fan, and Xiang Zhang. 2014. Inside the atoms: Ranking on a network of networks. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1356--1365.
31. Jingchao Ni, Hanghang Tong, Wei Fan, and Xiang Zhang. 2015. Flexible and robust multi-network clustering. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 835--844.
32. Rong Pan, Yunhong Zhou, Bin Cao, Nathan N. Liu, Rajan Lukose, Martin Scholz, and Qiang Yang. 2008. One-class collaborative filtering. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM’08).IEEE, 502--511.
33. Roni Parshani, Sergey V. Buldyrev, and Shlomo Havlin. 2010. Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition. Physical Review Letters 105, 4 (2010), 048701.
34. Sabry Razick, George Magklaras, and Ian M. Donaldson. 2008. iRefIndex: A consolidated protein interaction database with provenance. BMC Bioinformatics 9, 1 (2008), 1.
35. Vittorio Rosato, L. Issacharoff, F. Tiriticco, Sandro Meloni, S. Porcellinis, and Roberto Setola. 2008. Modelling interdependent infrastructures using interacting dynamical models. International Journal of Critical Infrastructures 4, 1--2 (2008), 63--79.
36. Arunabha Sen, Anisha Mazumder, Joydeep Banerjee, Arun Das, and Randy Compton. 2014. Identification of k most vulnerable nodes in multi-layered network using a new model of interdependency. In Proceedings of the 2014 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS’14). IEEE, 831--836.
37. Jia Shao, Sergey V. Buldyrev, Shlomo Havlin, and H. Eugene Stanley. 2011. Cascade of failures in coupled network systems with multiple support-dependence relations. Physical Review E 83, 3 (2011), 036116.
38. Ajit P. Singh and Geoffrey J. Gordon. 2008. Relational learning via collective matrix factorization. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 650--658.
39. Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: Extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 990--998.
40. Marc A. Van Driel, Jorn Bruggeman, Gert Vriend, Han G. Brunner, and Jack A. M. Leunissen. 2006. A text-mining analysis of the human phenome. European Journal of Human Genetics 14, 5 (2006), 535--542.
41. Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393, 6684 (1998), 440--442.
42. Chang Xu, Dacheng Tao, and Chao Xu. 2013. A survey on multi-view learning. (2013). arXiv preprint arXiv:1304.5634 .
43. Jingwei Xu, Yuan Yao, Hanghang Tong, XianPing Tao, and Jian Lu. 2015. Ice-breaking: Mitigating cold-start recommendation problem by rating comparison. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI’15). 3981--3987. http://ijcai.org/Abstract/15/559
44. Deqing Yang, Jingrui He, Huazheng Qin, Yanghua Xiao, and Wei Wang. 2015. A graph-based recommendation across heterogeneous domains. In Proceedings of the 24rd ACM International Conference on Conference on Information and Knowledge Management. ACM, 463--472.
45. Yuan Yao, Hanghang Tong, Guo Yan, Feng Xu, Xiang Zhang, Boleslaw K. Szymanski, and Jian Lu. 2014. Dual-regularized one-class collaborative filtering. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. ACM, 759--768.
46. Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei-Ying Ma. 2016. Collaborative knowledge base embedding for recommender systems. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 353--362.
47. Xiaodong Zheng, Hao Ding, Hiroshi Mamitsuka, and Shanfeng Zhu. 2013. Collaborative matrix factorization with multiple similarities for predicting drug-target interactions. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM.
48. Dawei Zhou, Jingrui He, K. Seluk Candan, and Hasan Davulcu. 2015. MUVIR: Multi-view rare category detection. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI’15). 4098--4104.
49. Yao Zhou and Jingrui He. 2016. Crowdsourcing via tensor augmentation and completion. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16). 2435--2441. http://www.ijcai.org/Abstract/16/347

Index Terms

• Information systems

  • Information systems applications