臺灣博碩士論文加值系統

多關係網路在現實世界中相當普及，但由於其複雜的結構而難以分析。一個比較可行的方式是將此網路的每一項目資訊表現為一個帶資訊的特徵向量。然而，現有的嵌入方式多半只有考慮單一鏈結關係或是忽略了結構資訊。此外，有些方式需要特別為參數做調整，比較不適合做在非監督式的學習表示任務。
在這份論文中我們提出一個藉由最大化給定的網路中觀察到每個節點和每種關係的機率而保留鏈接結構的非監督式多關係網路表示方法『MUSE』，額外的節點資訊也將會在我們的設計中保留下來。此外，MUSE 也有著對效能影響不大的參數及藉由對邊抽樣的方式達到規模可伸縮性的特性。大量對不同實際網路資料的應用實驗也可以顯示出我們模型的效率及堅定性。

Multi-relational networks are ubiquitous in real world. It is, however, difficult to be analyzed due to the complex structure of the network. A plausible approach to analyze such network is to embed the entity information as an informative feature vector. However, present embedding methods either consider only single-relational information, or neglect the importance of structural information. In addition, some of them require fine-tuning of hyperparameters, which might not be feasible for an unsupervised embedding generation task.
In this work we propose MUSE, a Multi-relational Unsupervised link-Structure preserving Embeddings method, which learns the representations for each node and relation by maximizing the likelihood of observations on the given network. Additional node attributes are also preserved under our design. Besides, MUSE features less sensitive hyperparameters and scalablility by edge-sampling strategy. The extensive experiments on various real-world applications also demonstrate the effectiveness and robustness of our model.

誌謝 ii
摘要 iii
Abstract iv
1 Introduction 1
2 Related Work 4
2.1 RandomWalk based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
2.2 Community based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Translation based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Methodology 7
3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.2 Design Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Link Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
3.4 Node Attributes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
3.5 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
4 Experiments 13
4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
4.2 Link Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Node Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.4 Multi-label Classification . . . . . . . . . . . . . . . . . . . . . . . . . .17
4.5 Parameter Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.6 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5 Discussions and Conclusions 22
5.1 Discussion: Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Discussion: Fewer Hyperparameter . . . . . . . . . . . . . . . . . . . . . . .23
5.3 Discussion: Additional Attributes. . . . . . . . . . . . . . . . . . . . . . .23
5.4 Discussion: Proximity Preserving . . . . . . . . . . . . . . . . . . . . . . .24
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.6 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Bibliography 26

[1] K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data , pages 1247–1250. AcM, 2008.
[2] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pages 2787–2795, 2013.
[3] B.-J. Breitkreutz, C. Stark, T. Reguly, L. Boucher, A. Breitkreutz, M. Livstone, R. Oughtred, D. H. Lackner, J. Bähler, V. Wood, K. Dolinski, and M. Tyers. The biogrid interaction database: 2008 update. Nucleic Acids Research, pages D637–D640, 2008.
[4] 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, pages 855–864. ACM, 2016.
[5] C.-C. Hsu, Y.-A. Lai, W.-H. Chen, M.-H. Feng, and S.-D. Lin. Unsupervised ranking using graph structures and node attributes. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 771–779. ACM, 2017.
[6] G. Ji, S. He, L. Xu, K. Liu, and J. Zhao. Knowledge graph embedding via dynamic mapping matrix. In ACL (1), pages 687–696, 2015. 24
[7] D. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[8] L. v. d. Maaten and G. Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(Nov):2579–2605, 2008.
[9] M. Mahoney. Large text compression benchmark, 2011.
[10] G. A. Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39–41, 1995.
[11] 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, pages 701–710. ACM, 2014.
[12] S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence, pages 452–461. AUAI Press, 2009.
[13] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale informationnetworkembedding. In Proceedings of the 24th International Conference on World Wide Web, pages 1067–1077. ACM, 2015.
[14] D. Wang, P. Cui, and W. Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1225–1234. ACM, 2016.
[15] Y. Wang, Y. Tong, and M. Zeng. Ranking scientific articles by exploiting citations, authors, journals, and time information, 2013.
[16] G. Wiederhold. Movies, 1999.
[17] R. Zafarani and H. Liu. Social computing data repository at ASU, 2009.